Results 1 to 5 of 5

Thread: LZ77 Performance Issues

  1. #1
    Member
    Join Date
    Aug 2011
    Location
    Canada
    Posts
    113
    Thanks
    9
    Thanked 22 Times in 15 Posts

    LZ77 Performance Issues

    Hello, I'm new here. I came to this forum because I have a general interest in data compression.

    I have written code for several simple compression algorithms, and most of them are working correctly. However, the performance for the LZ77 based code is very poor. I use a ring buffer for IO buffering and store the offset to the next byte of the same value in the buffer, so that not every position in the window is checked for a match. It currently runs at about 100 kb/s for a 1kb window on a 2ghz computer. I was wondering if anyone had any suggestions to improve the performance of the algorithm. Thanks to everyone in advance.



    Also, I created a fast preprocessor for entropy coders. It runs at over 100 mb/s and has moderate gains on compression ratio. Here are some benchmarks:

    enwik8 100,000,000 bytes
    enwik8 -> Huff0 -> output 63,081,072 bytes
    enwik8 -> PrePred -> Huff0 -> output 50,986,908 bytes

    7z.dll 1,478,656 bytes
    7z.dll -> Huff0 -> output 1,059,865 bytes
    7z.dll -> PrePred -> Huff0 -> output 892,123 bytes
    Attached Files Attached Files

  2. #2
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts
    i suggest you to start with the same thing as eugene roshal or igor pavlov started m,any years ago - download and learn zlib sources. lz77 part is in deflate.c and it's greatly documented

  3. #3
    Member
    Join Date
    Aug 2011
    Location
    Canada
    Posts
    113
    Thanks
    9
    Thanked 22 Times in 15 Posts
    Thanks! I'll look into that.

  4. #4
    Member
    Join Date
    Mar 2011
    Location
    Google Switzerland
    Posts
    19
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Quote Originally Posted by david_werecat View Post
    I use a ring buffer for IO buffering and store the offset to the next byte of the same value in the buffer, so that not every position in the window is checked for a match. It currently runs at about 100 kb/s for a 1kb window on a 2ghz computer. I was wondering if anyone had any suggestions to improve the performance of the algorithm. Thanks to everyone in advance.
    First of all, I'd run a profiler over your code ? it sounds like your match checking is what's taking up time, but it's always hard to say without a profiler.

    FWIW, the usual way of speeding up match finding is storing not just a pointer to the previous _byte_ with the same value, but the previous 3 or 4 bytes (or whatever is your minimum match length). This is typically done using a hash table, and then just ignoring any results you get that are outside your window.

    /* Steinar */

  5. #5
    Member
    Join Date
    Aug 2011
    Location
    Canada
    Posts
    113
    Thanks
    9
    Thanked 22 Times in 15 Posts
    Thanks! That should give a large efficiency increase. I'm still trying to work with the zlib source code, but this is probably easier to implement.

Similar Threads

  1. Raising performance bar in arithmetic coding
    By stbit in forum Data Compression
    Replies: 43
    Last Post: 28th April 2011, 10:07
  2. BCM 0.11 - A high performance BWT compressor
    By encode in forum Data Compression
    Replies: 44
    Last Post: 29th October 2010, 23:45
  3. Better compression performance across time?
    By Trixter in forum Data Compression
    Replies: 16
    Last Post: 17th June 2008, 00:35
  4. balz v1.00 - new LZ77 encoder is here!
    By encode in forum Forum Archive
    Replies: 61
    Last Post: 17th April 2008, 23:57
  5. Fast arithcoder for compression of LZ77 output
    By Bulat Ziganshin in forum Forum Archive
    Replies: 13
    Last Post: 15th April 2007, 18:40

Posting Permissions

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