Results 1 to 18 of 18

Thread: decompression is ~1000 times slower than compression?

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    242
    Thanks
    42
    Thanked 99 Times in 51 Posts

    decompression is ~1000 times slower than compression?

    Can you think of a compressor with compression speed thousand times higher than decompression speed?
    Do you know publications mentioning or discussing such unusual cases?

  2. #2
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,537
    Thanks
    758
    Thanked 676 Times in 366 Posts
    paq on multi-core cpu. its algorithm allows to execute all models independent at compression, but not at decompression

  3. #3
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    242
    Thanks
    42
    Thanked 99 Times in 51 Posts
    Quote Originally Posted by Bulat Ziganshin View Post
    paq on multi-core cpu. its algorithm allows to execute all models independent at compression, but not at decompression
    Let's consider a 4-core CPU. Should compression be ~4 times faster than decompression, after implementation is optimized for a 4-core CPU ? Will only one core be occupied during decompression?

  4. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,775
    Thanks
    276
    Thanked 1,206 Times in 671 Posts
    Yeah, it should be possible to make paq 4x faster on a quadcore.
    Comparing versions fully speed-optimized to 1 and 4 cores is another
    matter though, as paq is not really optimized as it is.

    But anyway, its a bit hard, but possible too
    (decompression being much slower than compression)
    For example, if we'd implement a "normal" BWT compressor
    and reduced-memory decompressor (like in bwmonstr).

    Also there're quite a few other cases where normally additional
    complexity is added to the compressor, but its possible to make
    the compressor a bit faster and decompressor much slower.
    I mean stuff like ABS coder, code stream (de)interleaving and
    various transforms.

    Also such cases might be common in recompression - for example,
    instead of detecting the deflate settings at compression side in precomp,
    we could just store the inflate'd data and a hash of original block, and
    leave the bruteforce to decoder.

    Anyway, I can think of more examples if necessary, and they might
    even make some sense (usually the encoding speed can be slightly
    improved at the cost of significant decompression slow-down),
    but its not quite practical anyway :)
    Last edited by Shelwien; 25th April 2010 at 08:42.

  5. #5
    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 Alexander Rhatushnyak View Post
    Let's consider a 4-core CPU. Should compression be ~4 times faster than decompression, after implementation is optimized for a 4-core CPU ? Will only one core be occupied during decompression?
    There are 1000+ core machines out there, so if we take aside possible scaling issues, 1000 fold difference is possible.

  6. #6
    Member Alexander Rhatushnyak's Avatar
    Join Date
    Oct 2007
    Location
    Canada
    Posts
    242
    Thanks
    42
    Thanked 99 Times in 51 Posts
    Quote Originally Posted by m^2 View Post
    There are 1000+ core machines out there, so if we take aside possible scaling issues, 1000 fold difference is possible.
    Do you mean that only one core will be busy during decompression? When you get predictions from models, why can't you process half models on another core? After the bit is successfully decompressed, why can't you update half models on one core, and half models on another core?

  7. #7
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,775
    Thanks
    276
    Thanked 1,206 Times in 671 Posts
    Of course, there're some options for paralleling in decoding too, but very limited.
    If the file was encoded sequentially, you basically can't decode the next bit,
    until you know the previous bits (speculative decoding is possible, but doesn't
    really change anything).
    Sure its still possible to run parts on different cores, but with sync on each bit,
    it would likely end up being slower than single-threaded version.

  8. #8
    Member
    Join Date
    Apr 2010
    Location
    El Salvador
    Posts
    43
    Thanks
    0
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Alexander Rhatushnyak View Post
    Can you think of a compressor with compression speed thousand times higher than decompression speed?
    Do you know publications mentioning or discussing such unusual cases?
    An algorithm which works with integer prime-factor multiplication for example. The inverse integer factorization is dead slow. There exist satelite link image compressors which work that way. Don't have the reference in the moment. I think a lot image compressors which have to compress on very simple machines which are not exchangeable (taking out the cartridge, no possibility of a cable, and so on) compress faster than decompress. The destination has all resources necessary.

  9. #9
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,257
    Thanks
    307
    Thanked 795 Times in 488 Posts
    Quote Originally Posted by Ethatron View Post
    An algorithm which works with integer prime-factor multiplication for example. The inverse integer factorization is dead slow. There exist satelite link image compressors which work that way. Don't have the reference in the moment.
    I think that would be RSA encryption rather than compression.

  10. #10
    Member
    Join Date
    Apr 2010
    Location
    El Salvador
    Posts
    43
    Thanks
    0
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Matt Mahoney View Post
    I think that would be RSA encryption rather than compression.
    The referred image compressor may have used error correcting codes based on primes, as satelite links may suffer from severe signal distortion. Too bad I don't find the paper, and I'm allready using full searches.

  11. #11
    Member
    Join Date
    Apr 2010
    Location
    El Salvador
    Posts
    43
    Thanks
    0
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Alexander Rhatushnyak View Post
    Can you think of a compressor with compression speed thousand times higher than decompression speed?
    Do you know publications mentioning or discussing such unusual cases?
    Another "common" case would be if you have an complex implicit set of rules, and you create a source-string for that it's too complex to maintain related statistics. The sender may instantly produce the next symbol, while the receiver has to apply and exclude all rules which are violated to reach the unique valid set of possible symbols. The trellis code is an example if this kind of implicity.

    Other trivial case, when the compressor has a huge amount of memory and the decompressor almost none you may have 1:1000 ratios.

Similar Threads

  1. Decompression speed test
    By m^2 in forum Data Compression
    Replies: 8
    Last Post: 17th August 2010, 23:42
  2. Best decompression on embedded device
    By ikes in forum Data Compression
    Replies: 7
    Last Post: 16th February 2009, 21:05
  3. Data decompression on in-memory kernel
    By cregd in forum Data Compression
    Replies: 8
    Last Post: 27th January 2009, 17:24
  4. Compiler related: Intel's code slower on AMD-CPUs?!
    By Vacon in forum Data Compression
    Replies: 5
    Last Post: 10th May 2008, 17:56
  5. Fast decompression of big files
    By SvenBent in forum Forum Archive
    Replies: 16
    Last Post: 8th March 2008, 19:17

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
  •