Page 3 of 8 FirstFirst 12345 ... LastLast
Results 61 to 90 of 239

Thread: Ultra-fast LZ

  1. #61
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    I can't help you with Windows, but maybe others can.
    Here you have a ZFS source tour:
    http://hub.opensolaris.org/bin/view/...oup+zfs/source

    You may be also interested in a LZO patch:
    http://www.wizy.org/wiki/ZFS_on_FUSE#LZO_Compression
    Last edited by m^2; 20th March 2011 at 02:08.

  2. #62
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    865
    Thanks
    463
    Thanked 260 Times in 107 Posts
    Thanks, the LZO patch is a good starting point

    Regards

  3. #63
    Tester
    Black_Fox's Avatar
    Join Date
    May 2008
    Location
    [CZE] Czechia
    Posts
    471
    Thanks
    26
    Thanked 9 Times in 8 Posts
    NTFS-3g is able to read and write transparently compressed files, so that could be some starting point in Windows FS-built-in compression.
    Last edited by Black_Fox; 20th March 2011 at 22:32. Reason: typo
    I am... Black_Fox... my discontinued benchmark
    "No one involved in computers would ever say that a certain amount of memory is enough for all time? I keep bumping into that silly quotation attributed to me that says 640K of memory is enough. There's never a citation; the quotation just floats like a rumor, repeated again and again." -- Bill Gates

  4. #64
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    865
    Thanks
    463
    Thanked 260 Times in 107 Posts
    Good point Black_Fox; sounds good,

    but where should the code be inserted ?
    Probably a driver model i guess; where to find such information ...

  5. #65
    Tester
    Black_Fox's Avatar
    Join Date
    May 2008
    Location
    [CZE] Czechia
    Posts
    471
    Thanks
    26
    Thanked 9 Times in 8 Posts
    ReactOS is far away from this yet and other projects AFAIK don't have the need to make any drop-in replacements, I don't know. Some very basic info about the compression is here: http://msdn.microsoft.com/en-us/library/Aa364219
    I think Encode did performance tests against NTFS LZ some time ago, but he most likely did not plug his code into NTFS.
    I am... Black_Fox... my discontinued benchmark
    "No one involved in computers would ever say that a certain amount of memory is enough for all time? I keep bumping into that silly quotation attributed to me that says 640K of memory is enough. There's never a citation; the quotation just floats like a rumor, repeated again and again." -- Bill Gates

  6. #66
    Member
    Join Date
    May 2007
    Location
    Poland
    Posts
    91
    Thanks
    8
    Thanked 4 Times in 4 Posts
    This, if done right, could seriously speed up file transfers. SSD speeds with good old GMR technology (for compressable files ofc)? Me want!

  7. #67
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    2 Shelwien
    What do you think, what kind of bit codes are most efficient for match length/offset coding? (128...256 KB window)

  8. #68
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Most likely, for match length
    000
    001
    010
    ...
    111 00000000
    111 00000001
    etc.
    Is better than
    1
    01
    001
    000
    ...
    or
    1 xx
    01 xxxx
    00 xxxxxxxx
    and such codes

  9. #69
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,423
    Thanks
    223
    Thanked 1,052 Times in 565 Posts
    Dump the symbols (lengths or whatever) to a file and process it with http://encode.su/threads/1183-Huffman-code-generator
    (it can be also easily modified to work with alphabet size >256)
    Then you can reorder the codes however you like, but huffman code lengths are the most efficient, there's a mathematical proof of that.

  10. #70
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Current results on ENWIK8:

    Fast -> 43303422
    Normal -> 37321031
    Max -> 36596773

    Still no Huffman or arithmetic coding, just Bit I/O. And it is FAST!

  11. #71
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Dictionary?

  12. #72
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    128 KB

  13. #73
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Well well, stronger than LZSS with such a small window? Nice.

  14. #74
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts

    Exclamation

    New performance and comparison of a DEBUG build - i.e. it's unoptimized. With release build I'm expecting the decompression times to be much closer to ULZ 0.02!

    No code has to be inserted here.

    A quick note. New ULZ has the smallest dictionary of all my programs:
    ULZ 0.03 - 128 KB
    LZSS - 256 KB
    ULZ 0.02 - 512 KB

    It compresses better due to:
    + Better LZ-output encoding - variable bit codes VS byte aligned ones
    + Optimized parsing

    And the huge difference can be seen on binary files:

    MPTRACK.EXE (1,159,172 bytes)
    ULZ 0.03a, cx -> 595,631 bytes
    LZSS 0.01, ex -> 651,281 bytes
    ULZ 0.02, c6 -> 657,110 bytes

    So, compared to Deflate, we've got about the same compression level with notable faster decompression...

  15. #75
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Interesting thing. The longest offsets are the most frequently used ones. At least with ENWIK8. Since the longest match that can be found is usually distant. Hence the common LZH logic is not essentially correct. At the same time short offsets should not be too redundant...

  16. #76
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    New results:

    ENWIK8
    128K -> 36,107,259 bytes
    256K -> 35,306,349 bytes
    512K -> 34,643,338 bytes

    ENWIK9
    128K -> 320,750,811 bytes
    256K -> 312,955,293 bytes
    512K -> 306,579,737 bytes

    world95.txt
    128K -> 808,018 bytes
    256K -> 768,213 bytes
    512K -> 737,721 bytes

    OSHO.TXT
    128K -> 60,806,644 bytes
    256K -> 59,035,580 bytes
    512K -> 57,658,231 bytes

    bookstar
    128K -> 14,597,144 bytes
    256K -> 14,138,705 bytes
    512K -> 13,760,371 bytes

    3200.txt
    128K -> 6,130,489 bytes
    256K -> 5,963,436 bytes
    512K -> 5,841,495 bytes



    256K looking good!

  17. #77
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Got a nice results with a Fast mode and a New Match Finder:
    ENWIK8 -> 39,385,478 bytes in about one second!

  18. #78
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts

    Talking

    New results (timings are for a DEBUG build):

    No code has to be inserted here.

    Any comments / suggestions?

  19. #79
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Could you give us decompression times? It looks that 1MB sucks, but I'd like to see how does is affect decompression.
    And why DEBUG?

  20. #80
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts

    Exclamation

    'DEBUG' is because of a dummy Visual C++ compile. Currently, I'm just concentrating on the actual implementation. I will do some experiments with compilers and their options later.

    Okay, here are the results for a slightly improved version:

    512K
    Compressing...
    100000000 -> 34390122 in 16.6 sec
    Decompressing...
    34390122 -> 100000000 in 0.5 sec
    Compressing...
    1000000000 -> 304633215 in 146.8 sec
    Decompressing...
    304633215 -> 1000000000 in 4.2 sec

    1M
    Compressing...
    100000000 -> 33576587 in 35.2 sec
    Decompressing...
    33576587 -> 100000000 in 0.5 sec
    Compressing...
    1000000000 -> 296783310 in 284.5 sec
    Decompressing...
    296783310 -> 1000000000 in 4.1 sec

    The decompression with 1 MB is actually faster. The the goal of this software is the FASTEST decompression possible. To be on par with QuickLZ, LZOP or SNAPPY - my LZ77 decoder has the same complexity as the fastest codecs on the planet. At the same time new LZ77 has the COMPRESSION!

  21. #81
    Member
    Join Date
    May 2007
    Location
    Poland
    Posts
    91
    Thanks
    8
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by encode View Post
    New results (timings are for a DEBUG build):

    No code has to be inserted here.

    Any comments / suggestions?
    I like 1MB fast best. Slower modes are not really worth it

  22. #82
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Quote Originally Posted by jethro View Post
    I like 1MB fast best. Slower modes are not really worth it
    Actually worth it. Since the decompression speed is not affected.

  23. #83
    Member
    Join Date
    May 2007
    Location
    Poland
    Posts
    91
    Thanks
    8
    Thanked 4 Times in 4 Posts
    Interesting, then those modes are definitely worth keeping.
    Have you thought then about support drag&drop aka paq style (compression and decompression) to go with super-fast speed?

  24. #84
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Such user interface can be added in one minute. Just currently in my mind the algorithm only. It is mainly done, but I need to carefully choose the algorithm parameters. Such as window size.

  25. #85
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    Added a nice feature. Now you can concatenate compressed streams. Say, you compressed:
    book1 to book1.cru
    book2 to book2.cru
    book3 to book3.cru

    now if you will concatenate all files:

    copy /b book1.cru+book2.cru+book3.cru books.cru

    new lz77 compressor will able to decompress that "books.cru" into one file that will be just like all uncompressed files concatenated together.

  26. #86
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    That's a nice feature. zpaq does that too, also bzip2 I think.

  27. #87
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    I'm close to release a new LZ77 encoder called CRUSH. It has 512 KB dictionary. The compression power is favored over compression speed. Although Fast mode is pretty fast, in Normal and Max mode I specially kept a slower match finder that will able to find more matches thus providing a higher compression. The decompression is just extremely fast at any compression mode!

    More detailed description of compression modes:

    • Fast - Fast string searching. Greedy parsing.
    • Normal - Best string searching. Greedy parsing.
    • Max - Best string searching. Advanced lazy matching with 1-byte lookahead. I tested lazy matching with 2-byte lookahead and it's not the best idea here, since the literals are sent unencoded, and generally speaking sending extra literals is a bad idea.


    Actually, CRUSH in Normal mode is somewhat similar to ULZ at Max mode. The main difference is that CRUSH uses variable length bit codes (not Huffman).

    Can it replace Deflate? Probably. Currently, CRUSH has a slower compression (Normal and Max modes), the Fast mode is much faster than Deflate, providing yet a nice compression. The main key is an extremely fast decompression. The decoder is extremely simple and can fit in a few lines of code. Usually, CRUSH has a notable higher compression than Deflate. Anyway, in some cases and due to fact that CRUSH does not encode literals sending them unencoded, Deflate may outperform CRUSH in terms of compression, especially on poor compressible files. Furthermore, currently, CRUSH may increase size of already compressed files like A10.jpg. Anyway, since CRUSH processes blocks independently, I will add a support for unencoded blocks. At least I will do so for the decoder. Unlike nearly all my compressors, I will keep a backward compatibility in CRUSH - i.e. whatever I do with the encoder, I'll keep decoder untouched. As example I may reserve an extra features in he decoder, that may not be available currently in the encoder (like unencoded blocks)...

    So anyways, results on ENWIKs:

    ENWIK8 -> 33,849,317 bytes
    ENWIK9 -> 299,705,455 bytes

    Yet better than SLUG and others, providing unmatched decompression speed...


  28. #88
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts

    Cool

    OK, continue talking to myself. After some experiments I did some changes:

    Increased dictionary size to 1 MB. It's make sense.

    Now Max mode is more like an Extreme mode - really exhaustive string searching in pair with more optimized parsing. Normal mode is just the most balanced in terms of compression ratio vs compression time. Fast mode is really something interesting - it's fast and compression is good enough.

    Changed the memory usage - increased buffer from 32 MB to 64 MB and increased hash sizes from 20-bit hashes to 24-bit hashes.
    Now CRUSH needs about 192 MB for compression, and, 64 MB for decompression. (Previously CRUSH use 40 MB for compression and 32 for decompression)

    Interesting thing, new CRUSH compresses ENWIK9 better than some arith(+rolz) based coders like irolz...

  29. #89
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,984
    Thanks
    377
    Thanked 352 Times in 140 Posts
    ENWIK8 -> 32,988,847 bytes
    ENWIK9 -> 291,350,973 bytes

    Any comments?

  30. #90
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,611
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by encode View Post
    OK, continue talking to myself
    We're listening, we just have nothing to comment.

    Quote Originally Posted by encode View Post
    ENWIK8 -> 32,988,847 bytes
    ENWIK9 -> 291,350,973 bytes

    Any comments?
    But if you ask:
    Looks good.

Page 3 of 8 FirstFirst 12345 ... LastLast

Tags for this Thread

Posting Permissions

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