Results 1 to 7 of 7

Thread: SHARC/DENSITY updates

  1. #1
    Member
    Join Date
    Aug 2013
    Location
    France
    Posts
    77
    Thanks
    27
    Thanked 26 Times in 11 Posts

    SHARC/DENSITY updates

    Hello everyone,

    Nice to hear from you again and happy new year ! I've been off to other projects but I finally have some time to spend on my compression library project hence this post !
    As a *DISCLAIMER* I'm the author of sharc/density but it does not mean that the following benchmarks or results are inaccurate.

    First a quick presentation for anyone interested, all the software here is open source :
    sharc is a simple command-line archiver, GPL, C99 compatible which serves as a frontend to density (https://github.com/centaurean/sharc)
    density is the compression library, BSD licensed and C99 compatible as well (https://github.com/centaurean/density)
    • its aim is maximum efficiency, or speed combined with compression ratio, I'll discuss this later
    • the 2 algorithms currently available in density (more coming) look simple on the surface (dictionary based for one, shifting dictionaries and predictions for the other) but sometimes simple algos make wonders
    • a lot of craft was put into code optimization for absolute speed
    • it is fully streamable
    • it has a very simple to use API


    I know everyone's curious about benchmarks (me included) so here we go, compared to LZO and LZ4 which are the most similar compression algorithms I can think of in terms of performance :

    Benchmark
    Platform : Macbook Pro, OSX 10.10.1, 2.3 GHz Intel Core i7, 8Go 1600 MHz DDR, SSD
    All programs were compiled with their standard options (standard makefile) using clang (note that I also tried with gcc-4.9 and it makes no difference whatsoever). They were run a minimum of 5 times and chronometered using the best "User" value from the "time" program. They are of course all single-threaded otherwise this would make no sense.
    The file used was the world famous enwik8 but any compressible data would do !

    Click image for larger version. 

Name:	Capture d’écran 2015-01-07 à 03.13.40.png 
Views:	242 
Size:	151.7 KB 
ID:	3343

    A measure of efficiency ?
    What is a good measure of efficiency ? that's a tough question... one thing is for sure though, for a compression library there are only two measurables which are speed and ratio.
    If, let's say, speed and ratio are of equal importance, we could use the following formula : efficiency = (1/ratio)/roundtrip-time, here are the results:

    Program | Efficiency (1), higher is better
    sharc -c1 | 7,63
    sharc -c2 | 4,20
    lz4 -1 | 3,08
    lz4 -9 | 0,56
    lzop -1 | 2,61
    lzop -9 | 0,17

    But of course everyone will agree that usually the difficulty of having a better ratio grows much quicker than the difficulty of having a faster algorithm. In an extreme case, let's say that the ratio is massively more useful for us than the speed.
    A good measure of efficiency in that case would be something like : efficiency = (1/(ratio ^ 10))/roundtrip-time, yes that's ratio elevated at a power of 10 so we are pretty sure it is REALLY more important. The table is now :

    Program | Efficiency (10), higher is better
    sharc -c1 | 604,07
    sharc -c2 | 1239,01
    lz4 -1 | 484,98
    lz4 -9 | 865,78
    lzop -1 | 430,06
    lzop -9 | 483,53

    The result values jump through the roof because of the powers, so let's just express them as a percentage of the sum of all values, and let's walk through ratio powers of 1 to 10, this is what we get :

    Click image for larger version. 

Name:	efficiency.png 
Views:	231 
Size:	63.4 KB 
ID:	3341

    lower axis : ratio powers

    Thank you for reading, and let me know what you think !

  2. Thanks (3):

    Bulat Ziganshin (7th January 2015),Intrinsic (8th January 2015),Matt Mahoney (7th January 2015)

  3. #2
    Member
    Join Date
    Aug 2013
    Location
    France
    Posts
    77
    Thanks
    27
    Thanked 26 Times in 11 Posts

    SHARC 1.0 / DENSITY 0.11.1 beta

    For those interested, I've just release SHARC 1.0 / DENSITY 0.11.1 beta.

    Quick benchmark
    File used : enwik8 (100 MB)
    Platform : MacBook Pro, OSX 10.10.1, 2.3 GHz Intel Core i7, 8Go 1600 MHz DDR, SSD
    Timing : using the *time* function, and taking the best *user* value after multiple runs

    Click image for larger version. 

Name:	bench.png 
Views:	201 
Size:	124.4 KB 
ID:	3362

    Have a nice day !

  4. #3
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,610
    Thanks
    30
    Thanked 65 Times in 47 Posts
    I tried to integrate density with fsbench. I base my patch on yours, but have found some bugs in your integration code and an issue that may be a bug in density.

    Integration issues:
    * some compilers require explicit -c99 to compile, fixed in the attatched patch
    * there was no error checking in the encoder, it's important on incompressible data, fixed
    * there was no error checking in the decoder, it's less important as long as everything works, but it doesn't. fsbench sets osize to be exactly as large as needed. Density decoding always fails then. I tried +16 bytes (there's some padding in fsbench anyway), still an error. +256 fixed the issue and I could successfully decode, but that's more than I have. Should I tweak the value and just push as it is or await a fix from you? BTW, w/out error checking decoding speed may be inflated as you don't decompress everything
    Attached Files Attached Files

  5. Thanks:

    gpnuma (1st February 2015)

  6. #4
    Member
    Join Date
    Aug 2013
    Location
    France
    Posts
    77
    Thanks
    27
    Thanked 26 Times in 11 Posts
    Quote Originally Posted by m^2 View Post
    I tried to integrate density with fsbench. I base my patch on yours, but have found some bugs in your integration code and an issue that may be a bug in density.

    Integration issues:
    * some compilers require explicit -c99 to compile, fixed in the attatched patch
    * there was no error checking in the encoder, it's important on incompressible data, fixed
    * there was no error checking in the decoder, it's less important as long as everything works, but it doesn't. fsbench sets osize to be exactly as large as needed. Density decoding always fails then. I tried +16 bytes (there's some padding in fsbench anyway), still an error. +256 fixed the issue and I could successfully decode, but that's more than I have. Should I tweak the value and just push as it is or await a fix from you? BTW, w/out error checking decoding speed may be inflated as you don't decompress everything
    Hello m^2 thanks for your implementation.

    Yes there is a minimum output overhead which has to be ensured at all times, it avoids a number of boundary checks as a counterpart of using a ridiculously low amount of extra memory, and it has the following values :
    Code:
    DENSITY_CHAMELEON_DECODE_MINIMUM_OUTPUT_LOOKAHEAD = 256 bytes
    
    DENSITY_MANDALA_DECODE_MINIMUM_OUTPUT_LOOKAHEAD = 128 bytes
    So as you rightly found, 256 bytes extra is perfectly fine for the decompression to function properly for the 2 (so far) available algorithms.
    To me everything you did was right ! And I don't plan to fix this overhead requirement as it's a benefit for speed at an almost negligible cost.
    Last edited by gpnuma; 1st February 2015 at 00:34.

  7. #5
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,610
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Maybe you can have 2 decompression implementations, one that you use *MINIMUM_OUTPUT_LOOKAHEAD bytes from the end and another, with stricter bounds checks, for those last few bytes. It costs more code (which matters sometimes), but should be just as fast and easier to use. Actually in Nakamichi-M I used 3 decoding loops: initial one with checks for reading before the buffer, main one that did minimal checking and a tail one that checked everything.
    When it comes to ease of use, I suggest that you add a simple function that compresses a buffer in one shot, just like the one in fsbench but even simpler. For most users it's the best thing they can use anyway and the initial implementation costs would be much better.

    There is a copy-paste error in API:
    DENSITY_STREAM_STATE_STALL_ON_INPUT, // there is not enough space left in the output buffer to continue.

    And YGPM.

    ADDED: I need a clarification. Let's assume that I have a buffer. I compress it and then decompress, there's no data corruption in between. I know exactly how much space does the decompression output need. Shall I alloc *MINIMUM_OUTPUT_LOOKAHEAD more or just trick the decompressor to think I have this many?
    Last edited by m^2; 1st February 2015 at 22:58.

  8. #6
    Member
    Join Date
    Aug 2013
    Location
    France
    Posts
    77
    Thanks
    27
    Thanked 26 Times in 11 Posts
    Quote Originally Posted by m^2 View Post
    When it comes to ease of use, I suggest that you add a simple function that compresses a buffer in one shot, just like the one in fsbench but even simpler. For most users it's the best thing they can use anyway and the initial implementation costs would be much better.
    There was one in the 0.9.x series, I removed it in the latest version because the stream API is now very easy to use, but you're right there's probably a use case for this I'm going to consider it again.

    Quote Originally Posted by m^2 View Post
    There is a copy-paste error in API:
    DENSITY_STREAM_STATE_STALL_ON_INPUT, // there is not enough space left in the output buffer to continue.
    Corrected thanks.

    Quote Originally Posted by m^2 View Post
    ADDED: I need a clarification. Let's assume that I have a buffer. I compress it and then decompress, there's no data corruption in between. I know exactly how much space does the decompression output need. Shall I alloc *MINIMUM_OUTPUT_LOOKAHEAD more or just trick the decompressor to think I have this many?
    When your "osize" parameter is not big enough, there's a good chance you'll get a DENSITY_STREAM_STATE_STALL_ON_OUTPUT return code (asking you to provide another output buffer), when density checks for those *MINIMUM_OUTPUT_LOOKAHEAD extra bytes left at the end, depending on the size of your buffer.
    So you're right : those extra bytes will not be used and yes you could trick the decompressor to think you have that many available and it would be "happy". It's just a little bit of a dangerous programming style.

    The stream API is very flexible so it's usable for one-shot buffer compression/decompression, but its general use case is more oriented for limited size inputs/outputs - networks communication for example, when you don't know how much bytes you'll receive on each call to your socket read function - so technically all the return codes should be dealt with, not just the most obvious ones (see sharc for an example of this) but in fsbench's case it's definitely unnecessary as you do compression roundtrips basically.

  9. #7
    Member m^2's Avatar
    Join Date
    Sep 2008
    Location
    Ślůnsk, PL
    Posts
    1,610
    Thanks
    30
    Thanked 65 Times in 47 Posts
    Quote Originally Posted by gpnuma View Post
    Corrected thanks.
    I'd use the words "there is not enough data (...)" in that comment.

Similar Threads

  1. zpaq updates
    By Matt Mahoney in forum Data Compression
    Replies: 2618
    Last Post: 29th November 2020, 01:36
  2. SHARC / DENSITY news and updates
    By gpnuma in forum Data Compression
    Replies: 18
    Last Post: 15th February 2018, 19:59
  3. libzling updates!
    By RichSelian in forum Data Compression
    Replies: 3
    Last Post: 23rd April 2014, 11:23
  4. LIBSSC : SHARC's algorithms unleashed
    By gpnuma in forum Data Compression
    Replies: 131
    Last Post: 18th April 2014, 22:19
  5. comprox updates
    By RichSelian in forum Data Compression
    Replies: 1
    Last Post: 6th November 2011, 00:19

Posting Permissions

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