M01 - Order 01 context mixer

[toffer]

Hi all!

Since nobody seemed to be interested in my ideas for a two bit bithistory submodel and new mixing/sse approaches i've decided to implement it on my own. The results look promising and it's open source. See main.cpp for details.

Here it is: http://freenet-homepage.de/toffer_86/m01.tar.bz2

Have fun!

[encode]

Thank you!

[toffer]

Some results...

sfc.tar:

cm@e051 ~/shared/projects/m01/bin/Release $ ./m01 c ~/shared/temp/testset/sfc.tar /tmp/tst
M01 v0.0 by C. Mattern  May 29 2008
Experimental file compressor.
Encoding...done. 19694315/53145600 (2.965 Bpc) in 36.510 s

enwik8:

cm@e051 ~/shared/projects/m01/bin/Release $ ./m01 c ~/shared/temp/testset/enwik8 /tmp/tst
M01 v0.0 by C. Mattern  May 29 2008
Experimental file compressor.
Encoding...done. 44217671/100000000 (3.537 Bpc) in 59.310 s

I would be obliged for some more tests/comparisions/comments.

BTW: I might modify the source to make the context mixer asymmetric (as suggested within the source) this weekend... would be very interesting.

[encode]

Interesting source!

BTW, can you provide binary (.EXE)?

[LovePimple]

Thanks toffer!

[toffer]

Interesting source!

BTW, can you provide binary (.EXE)?

Maybe later, atm i'm changing some interiors of cmm4 Seems like you're not using codeblocks?

I could provide a 64 bit linux binary.

[LovePimple]

Here's a Win32 executable for people to try...

ENJOY!

[toffer]

Thanks for the compile.

@encode - i wonder which ide/editors you use for development?

[encode]

Here's a Win32 executable for people to try...

ENJOY!

[encode]

@encode - i wonder which ide/editors you use for development?

I use Microsoft Visual Studio 2005. With this tool finally we have a 64-bit file support.

[toffer]

I use Microsoft Visual Studio 2005. With this tool finally we have a 64-bit file support.

It's a matter of your C library implementation. Since i use both, win32 and linux i prefer codeblocks and gcc 4.

[LovePimple]

Quick test on my AMD Sempron 2400+, Windows XP SP2...

ENWIK9: 430,194,670 bytes/1,000,000,000 bytes (3.442 Bpc) in 1021.188 s

ENWIK8: 44,217,671 bytes/100,000,000 bytes (3.537 Bpc) in 101.875 s

[LovePimple]

MC SFC test...

A10.jpg > 830,889
AcroRd32.exe > 1,808,871
english.dic > 941,272
FlashMX.pdf > 3,890,705
FP.LOG > 4,991,265
MSO97.DLL > 2,175,822
ohs.doc > 1,374,974
rafale.bmp > 1,071,257
vcfiu.hlp > 1,306,231
world95.txt > 1,308,573

Total = 19,699,859 bytes

[toffer]

Hi!

Here is an improved version with asymmetric context mixing:

http://freenet-homepage.de/toffer_86/m01a_080601.7z

The weights are simply written to the compressed stream every 32kBytes. A weight model would compensate most of the compression loss.

[LovePimple]

Thanks toffer!

[Shelwien]

http://shelwien.googlepages.com/cm200805.htm update

Well, it is asymmetric, but kinda in a wrong way.
That is, the original build has 50% slower decompression,
and with my builds its supposedly as expected, but it looks
more like it has the same decompression speed as before,
but slower compression to make it asymmetric

[LovePimple]

Here's my own speed optimised compiles. One for Pentium Pro or later, the other for P3 or later.

ENJOY!

[toffer]

http://shelwien.googlepages.com/cm200805.htm update

Well, it is asymmetric, but kinda in a wrong way.
That is, the original build has 50% slower decompression,
and with my builds its supposedly as expected, but it looks
more like it has the same decompression speed as before,
but slower compression to make it asymmetric

This is really strange. On my machine decompression is about 25% faster than compression and compression is a tiny bit slower than the non-asymetric variations (like your builds).

G:\projects\m01\bin\Release>m01.exe c f:\enwik\enwik100 f:\enwik100.m01
M01 v0.0 by C. Mattern  Jun  1 2008
Experimental file compressor.
Encoding...done. 44421623/100000000 (3.554 Bpc) in 88.813 s
60213 63649 59529 62775 64461
54816 58955 61973 58817 62129
30679 55016 56916 60296 59052
27061 25505 50114 64737 58959
28816 43512 51624 57333 62023

60261 63099 62370 61359 64562
54203 57706 61913 61184 63540
29202 55213 56704 56050 56550
24837 38443 53595 58924 55219
24513 29971 56458 49406 62076

G:\projects\m01\bin\Release>m01.exe d f:\enwik100.m01 f:\enwik100.org
M01 v0.0 by C. Mattern  Jun  1 2008
Experimental file compressor.
Decoding...done. 44421623/100000000 (3.554 Bpc) in 68.015 s

And i tried your Intel C version:

F:\>m01a_Qxi_ipo_prof.exe c f:\enwik\enwik100 f:\enwik100.m01a
M01a v0.1 by C. Mattern  Jun  1 2008
Experimental file compressor.
Encoding...done. 44421623/100000000 (3.554 Bpc) in 82.031 s

F:\>m01a_Qxi_ipo_prof.exe d f:\enwik100.m01a f:\enwik100.org
M01a v0.1 by C. Mattern  Jun  1 2008
Experimental file compressor.
Decoding...done. 44421623/100000000 (3.554 Bpc) in 59.015 s

[Shelwien]

My results for fpaq-likes are best of 5, so its really the speed of your code on intel cpu.

Also http://shelwien.googlepages.com/cm200805.htm updated.
No luck again.

[toffer]

My results for fpaq-likes are best of 5, so its really the speed of your code on intel cpu.

Also http://shelwien.googlepages.com/cm200805.htm updated.
No luck again.

Would you mind to test on a single, large file? This would make the speed differences more pronounced.

This turns out to be really strange...

LovePimple, what compiler did you use?

[toffer]

GCC 4.3.0.

Could you tell me the compiler switches? And did you use feedback optimization?

[LovePimple]

You were too quick!

I don't normally use feedback optimization. I use a little program of my own that goes thru the compiler switches, tests each compile, and (hopefully) produces the quickest executable.

Which compiler do you use?

[toffer]

You were too quick!

I don't normally use feedback optimization. I use a little program of my own that goes thru the compiler switches, tests each compile, and (hopefully) produces the quickest executable.

Which compiler do you use?

The only optimization related switch - O3 and normally feedback optimization -fprofile-generate and -fprofile-use. Surprisingly your results seem to be better?!

[LovePimple]

You didn't answer my question.

[toffer]

You didn't answer my question.

Whoops

Atm on my windows machine:

mingw32-c++-sjlj.exe (GCC) 4.2.1-sjlj (mingw32-2)
Copyright (C) 2007 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

And gcc 4.3 under linux.

[LovePimple]

Thanks!

[Shelwien]

Profile-based optimization based only on the compression profile could hurt decompression speed.
Actually, that _always_ happens with IntelC, but it also allows to have multiple profile dumps.
And to collect both the compession and compression statistics for GCC,
I had to implement that "test" option in fpaq0pv4+.

Also this:
[m01.exe]
M01a v0.1 by C. Mattern Jun 1 2008
Experimental file compressor.
Encoding...done. 44421623/100000000 (3.554 Bpc) in 31.578 s
M01a v0.1 by C. Mattern Jun 1 2008
Experimental file compressor.
Decoding...done. 44421623/100000000 (3.554 Bpc) in 53.687 s

[m01a_Qxi_ipo_prof.exe]
M01a v0.1 by C. Mattern Jun 1 2008
Experimental file compressor.
Encoding...done. 44421623/100000000 (3.554 Bpc) in 31.843 s
M01a v0.1 by C. Mattern Jun 1 2008
Experimental file compressor.
Decoding...done. 44421623/100000000 (3.554 Bpc) in 23.063 s

[toffer]

I checked it - you are right. Profiling was just done for encoding. Doesn't gcc merge the profiles? I think i'll have to do a workaround :/
I hardly found any good resources about this optimization option on the net...

[LovePimple]

My results for fpaq-likes are best of 5, so its really the speed of your code on intel cpu.

Also http://shelwien.googlepages.com/cm200805.htm updated.
No luck again.

Thanks for adding my compiles to your test.

[toffer]

Good afternoon!

To increase confusion i made another version of this demo coder - m012. It is symmetric and adds an order 2 model.

Any ideas on improving this kind of mixer? If one had a look in trash.cpp from m01a, you might have noticed other update functions. I tried iterative coding cost minimization and an approx. version of this - compression is worse in both cases and unfortunately they are slower

http://freenet-homepage.de/toffer_86...0.01_080601.7z

I'm looking forward to comments.

Greets