Page 1 of 2 12 LastLast
Results 1 to 30 of 59

Thread: M01 - Order 01 context mixer

  1. #1
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts

    M01 - Order 01 context mixer

    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!

  2. #2
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,979
    Thanks
    376
    Thanked 347 Times in 137 Posts
    Thank you!

  3. #3
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Some results...

    sfc.tar:
    Code:
    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:
    Code:
    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.

  4. #4
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,979
    Thanks
    376
    Thanked 347 Times in 137 Posts
    Interesting source!

    BTW, can you provide binary (.EXE)?

  5. #5
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks toffer!

  6. #6
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by encode View Post
    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.

  7. #7
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

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

    ENJOY!
    Attached Files Attached Files

  8. #8
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Thanks for the compile.

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

  9. #9
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,979
    Thanks
    376
    Thanked 347 Times in 137 Posts
    Quote Originally Posted by LovePimple View Post
    Here's a Win32 executable for people to try...

    ENJOY!

  10. #10
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,979
    Thanks
    376
    Thanked 347 Times in 137 Posts
    Quote Originally Posted by toffer View Post
    @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.

  11. #11
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by encode View Post
    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.

  12. #12
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Smile

    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

  13. #13
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    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

  14. #14
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  15. #15
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks toffer!

  16. #16
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    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
    Attached Files Attached Files
    Last edited by Shelwien; 1st June 2008 at 18:25.

  17. #17
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Here's my own speed optimised compiles. One for Pentium Pro or later, the other for P3 or later.

    ENJOY!
    Attached Files Attached Files

  18. #18
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Shelwien View Post
    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).

    Code:
    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:
    Code:
    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
    Last edited by toffer; 1st June 2008 at 18:37.

  19. #19
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    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.

  20. #20
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by Shelwien View Post
    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?

  21. #21
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by LovePimple View Post
    GCC 4.3.0.
    Could you tell me the compiler switches? And did you use feedback optimization?

  22. #22
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    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?

  23. #23
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by LovePimple View Post
    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?!

  24. #24
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    You didn't answer my question.

  25. #25
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by LovePimple View Post
    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.

  26. #26
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Thanks!

  27. #27
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,239
    Thanks
    192
    Thanked 968 Times in 501 Posts
    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

  28. #28
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...

  29. #29
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts

    Thumbs up

    Quote Originally Posted by Shelwien View Post
    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.

  30. #30
    Programmer toffer's Avatar
    Join Date
    May 2008
    Location
    Erfurt, Germany
    Posts
    587
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

Page 1 of 2 12 LastLast

Similar Threads

  1. Context mixing
    By Cyan in forum Data Compression
    Replies: 7
    Last Post: 4th December 2009, 18:12
  2. Paq mixer theory
    By Shelwien in forum Data Compression
    Replies: 0
    Last Post: 22nd November 2009, 01:32
  3. CMM fast context mixing compressor
    By toffer in forum Forum Archive
    Replies: 171
    Last Post: 24th April 2008, 13:57
  4. Mixer vs 2D SSE
    By Shelwien in forum Forum Archive
    Replies: 26
    Last Post: 8th March 2008, 12:58
  5. fpaq0f new order 0 model
    By Matt Mahoney in forum Forum Archive
    Replies: 31
    Last Post: 5th February 2008, 22:08

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •