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

Thread: PAQ9 preview

  1. #1
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    Here is a preview of PAQ9
    http://cs.fit.edu/~mmahoney/compression/paq9a.zip

    It uses the same archive format and command line interface as lpq1 (based on lpaq1) with similar compression ratio, but a little slower. For highly redundant files (like fp.log), compression is faster. It lacks models for specific file types like exe, bmp, wav, jpeg, etc. I plan to add those later. I plan to have the file type detected automatically (or by command line options) and only turn on the models needed. This should improve speed over paq8, which has most of the models on at once.

    paq9a has an LZP preprocessor. It codes a match using one bit and a literal using 9 bits, which are modeled separately. This speeds up compression of highly redundant files but also hurts compression because you have to include the mispredicted byte as context for modeling the literals. As a compromise, only matches of length 12 or more are coded and only longer contexts include the extra byte.

    I also experimented with a different form of context mixing. Instead of mixing all the contexts at once (using a neural network), I used a chain of 2 input mixers (again a neural network). I am not sure if this compresses better, though.

    Also, I reimplemented the APM (SSE) as a 2 input mixer with one input fixed. This saves memory and reduces the number of free parameters, which should help for small files or rapidly changing data.

    paq9a -1 (19 MB)
    824,845 a10.jpg.paq9a-1
    1,255,208 acrord32.exe.paq9a-1
    487,957 english.dic.paq9a-1
    3,643,525 FlashMX.pdf.paq9a-1
    395,669 fp.log.paq9a-1
    1,654,770 mso97.dll.paq9a-1
    754,253 ohs.doc.paq9a-1
    757,053 rafale.bmp.paq9a-1
    499,172 vcfiu.hlp.paq9a-1
    470,607 world95.txt.paq9a-1
    10,743,059 bytes

    paq9a -9 (1585 MB)
    823,883 a10.jpg.paq9a-9
    1,235,497 acrord32.exe.paq9a-9
    457,932 english.dic.paq9a-9
    3,633,260 FlashMX.pdf.paq9a-9
    392,231 fp.log.paq9a-9
    1,610,168 mso97.dll.paq9a-9
    727,424 ohs.doc.paq9a-9
    739,561 rafale.bmp.paq9a-9
    493,760 vcfiu.hlp.paq9a-9
    431,508 world95.txt.paq9a-9
    10,545,224 bytes

    19,974,112 enwik8.paq9a-9 539 510 sec. (comp + decomp)
    165,193,368 enwik9.paq9a-9 4200 sec.
    (still testing decompression)

  2. #2
    Member
    Join Date
    Oct 2007
    Location
    Germany, Hamburg
    Posts
    408
    Thanks
    0
    Thanked 5 Times in 5 Posts
    Hey, nice to read . But I don?t get it. Will paq and lpaq be the same and only difference will be some small features and the special file modells? Compression now seems to be little over lpaq8 (on general files). Without beeing into context mixing my thoughts were, that lpaq uses many less modells (without counting the modells for special files). Thats the reason why it is faster but with less compression. Is the overall compression not finished yet?
    Also you wrote LZP will be used. But it has no better compression and isn?t faster (only on files where LZP works well).
    That were the things I only wondered about, reading your post

  3. #3
    Moderator

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

    Mirror: Download

  4. #4
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    Thanks Matt!

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

    It is very suprising to me, that your lzp coding scheme is exactly the same i'm working on to improve speed in my cm implementation. If you want to get things faster (i did some experiments) use the cm hashing table to store the lzp stuff. In orders 4 and 6 a hash bucket has 3 instead of 4 nibble models - there's no big hit in compression loss (cm only) but the 16 bytes offer space for lzp pointers and a small match length model (nonlinear quantization of lengths). To predict the next character i mix orders 6, 4, a special one (some "synthetic" stuff). Btw which lzp orders work best? I found order 4 and 5 or 6 to do well. Have you done any experiments in directly modeling the next predicted character by match length (as you do in lzp) - this is something on my todo list. Maybe i can avoid some work. I noticed that you can gain speed and compression in just combining the highest 3 or 4 order's predictions - lower orders seem to be "noisier".

    And something else - happy new year!
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  6. #6
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    876
    Thanks
    474
    Thanked 175 Times in 85 Posts
    Dear Matt,

    I have tested your new PAQ9a and here are the results:

    PAQ9a reached 38th place; compressed to 1.848.055.180 bytes in 22042 seconds;
    LPAQ7e reached 46th place; compressed to 1.874.189.389 bytes in 16475 seconds.

    I like the tendancy to faster PAQ variants; with filetype specialized filters it can outperform PAQ8 one day. The LZP is also good.

    D:TESTSETS>paq9a a 3d.paq9a -8 3d.tar
    3d.tar 239679488 -> 73949466
    -> 73949477 in 964.16 sec
    HashTable<16> 99.6100% full, 50.9763% utilized of 524288 KiB
    LZP hash table 96.8708% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 136045762 literals, 103633726 matches (43.2385% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a 3d.paq9a -8 bmp.tar
    Cannot overwrite archive 3d.paq9a

    D:TESTSETS>paq9a a bmp.paq9a -8 bmp.tar
    bmp.tar 623902208 -> 344260272
    -> 344260284 in 4551.50 sec
    HashTable<16> 99.6106% full, 59.0046% utilized of 524288 KiB
    LZP hash table 100.0000% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 606104885 literals, 17797323 matches (2.8526% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a psx.paq9a -8 psx.tar
    psx.tar 649017344 -> 284624019
    -> 284624031 in 2850.43 sec
    HashTable<16> 99.6098% full, 57.7057% utilized of 524288 KiB
    LZP hash table 99.9933% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 378434752 literals, 270582592 matches (41.6911% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a bin.paq9a -8 bin.tar
    bin.tar 97058304 -> 26086295
    -> 26086307 in 413.94 sec
    HashTable<16> 99.4529% full, 44.2300% utilized of 524288 KiB
    LZP hash table 75.0790% full of 131072 KiB
    LZP buffer 72.3141% full of 131072 KiB
    LZP 61591868 literals, 35466436 matches (36.5414% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a dna.paq9a -8 dna.txt
    dna.txt 73370264 -> 17192886
    -> 17192898 in 371.34 sec
    HashTable<16> 99.6090% full, 32.5051% utilized of 524288 KiB
    LZP hash table 29.0954% full of 131072 KiB
    LZP buffer 54.6651% full of 131072 KiB
    LZP 60280595 literals, 13089669 matches (17.8406% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a drv.paq9a -8 driver.tar
    driver.tar 347785216 -> 49897899
    -> 49897914 in 840.58 sec
    HashTable<16> 99.6088% full, 49.2641% utilized of 524288 KiB
    LZP hash table 92.7042% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 116071640 literals, 231713576 matches (66.6255% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a enc.paq9a -8 enc.tar
    enc.tar 350370304 -> 85092841
    -> 85092853 in 1175.57 sec
    HashTable<16> 99.6109% full, 52.5981% utilized of 524288 KiB
    LZP hash table 97.3972% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 155114609 literals, 195255695 matches (55.7284% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a fnt.paq9a -8 fonts.tar
    fonts.tar 15106560 -> 5911348
    -> 5911362 in 77.54 sec
    HashTable<16> 73.6286% full, 27.1049% utilized of 524288 KiB
    LZP hash table 26.4846% full of 131072 KiB
    LZP buffer 11.2553% full of 131072 KiB
    LZP 10868044 literals, 4238516 matches (28.0575% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a freedb.paq9a -8 freedb.txt
    freedb.txt 728757760 -> 94161780
    -> 94161795 in 2335.89 sec
    HashTable<16> 99.5277% full, 40.7194% utilized of 524288 KiB
    LZP hash table 96.1098% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 312801226 literals, 415956534 matches (57.0775% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a gb.paq9a -8 gb.txt
    gb.txt 160734208 -> 32842004
    -> 32842015 in 770.54 sec
    HashTable<16> 94.6364% full, 34.6240% utilized of 524288 KiB
    LZP hash table 80.0652% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 118212523 literals, 42521685 matches (26.4547% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a mod2.paq9a -8 mod2.tar
    mod2.tar 63442944 -> 36097513
    -> 36097526 in 380.53 sec
    HashTable<16> 99.6061% full, 46.6298% utilized of 524288 KiB
    LZP hash table 78.1020% full of 131072 KiB
    LZP buffer 47.2687% full of 131072 KiB
    LZP 52107215 literals, 11335729 matches (17.8676% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a nokia.paq9a -8 nokia.tar
    nokia.tar 28546560 -> 2109822
    -> 2109836 in 37.23 sec
    HashTable<16> 36.3129% full, 12.7470% utilized of 524288 KiB
    LZP hash table 10.6137% full of 131072 KiB
    LZP buffer 21.2688% full of 131072 KiB
    LZP 5568090 literals, 22978470 matches (80.4947% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a o2.paq9a -8 o2.tar
    o2.tar 306484224 -> 234730263
    -> 234730274 in 2164.58 sec
    HashTable<16> 99.6091% full, 59.8792% utilized of 524288 KiB
    LZP hash table 99.9501% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 264656508 literals, 41827716 matches (13.6476% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a wav.paq9a -8 wav.tar
    wav.tar 605648896 -> 479196804
    -> 479196816 in 4557.05 sec
    HashTable<16> 99.6096% full, 63.8175% utilized of 524288 KiB
    LZP hash table 100.0000% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 602996740 literals, 2652156 matches (0.4379% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a sav.paq9a -8 sav2.tar
    sav2.tar 151070720 -> 50532061
    -> 50532074 in 551.07 sec
    HashTable<16> 99.6100% full, 47.1710% utilized of 524288 KiB
    LZP hash table 85.6420% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 73987941 literals, 77082779 matches (51.0243% matched)
    Used 799221 KiB memory

    D:TESTSETS>paq9a a src.paq9a -8 sources.tar
    sources.tar 209364992 -> 31369702
    -> 31369718 in 545.28 sec
    HashTable<16> 99.5867% full, 43.0527% utilized of 524288 KiB
    LZP hash table 80.1746% full of 131072 KiB
    LZP buffer 100.0000% full of 131072 KiB
    LZP 74930635 literals, 134434357 matches (64.2105% matched)
    Used 799221 KiB memory

  7. #7
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    Quote Originally Posted by Simon Berger
    But I don?t get it.
    Of course the goal is better speed and better compression. I have not achieved that yet. The purpose of releasing the code was to start a discussion. The idea was to use LZP to speed up compression of highly redundant data and to model the higher order contexts. Unfortunately it hurts compression so I will need to fix that or abandon the approach. I compensated by adding more models, which is why it is slower than lpaq1. paq9a has some sparse models which improve compression of binary files, but text is a bit worse.

    paq9 is probably a poor choice for a name right now, because it is not yet ready to be a successor to paq8. That is my eventual goal, however. I am not happy about the speed of paq8, which is my reason for experimenting with new architectures.

    Another major change is using chains of 2 input mixers. (Eugene Shelwien mentioned this idea, going from low to high orders). This idea might be too messy for combining lots of contexts, but I want to avoid too many models to get better speed. Instead, I want to use the file type to select the best models. I designed the code to make it easy to mix different types of compression this way (right now, just compress or store).

    I did try adding a bit history to the LZP hash table to provide more context for the match probability, but this did not work, at least not as well as using low order contexts.

  8. #8
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    Quote Originally Posted by toffer
    Btw which lzp orders work best?
    The higher the better. I used order 12 as a tradeoff between speed and compression. If I only had to model the matches and not the literals, I found orders as low as 2 worked best. (I looked up context hashes of orders 6, 3, and 2). To model the match probability I used the match length, and for lower orders (up to about 10) I also used the offset (quantized on a log scale). Small offsets are usually more likely to be matched. Then I adjusted the probability using low order contexts. It seemed like there was a lot of overlap in the contexts I used for modeling matches and literals, but I didnt try to combine them.

    The problem with modeling literals is that the distribution depends on what byte was predicted (since it is removed from the literal distribution). This means the predicted byte has to be added to the context, which increases the model size and hurts compression. This is mainly a problem for low orders where the predicted byte is more likely to vary in the same context.

  9. #9
    Tester
    Stephan Busch's Avatar
    Join Date
    May 2008
    Location
    Bremen, Germany
    Posts
    876
    Thanks
    474
    Thanked 175 Times in 85 Posts
    I like both the idea and the goals of PAQ9 and I am sure it will become a PAQ8 successor. 2 years ago, PAQ7 was not as powerful as PAQAR, but in the end later variants were both much faster and compressed better.

    Please, Matt, keep up the excellent work on PAQ9 and don't abandon it.


    Yours,
    Stephan

  10. #10
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    3,985
    Thanks
    377
    Thanked 353 Times in 141 Posts
    2 Matt:
    There are many things to try with LZP.

    You may use a fixed order for LZP - order-8 and higher.
    No need in match legths - predicted/not predicted only stuff.

    Code:
     
    if (tab[hash] == c) // predicted 
    ... 
    else // nope 
    ... 
     
    tab[hash] = c; // update

    Overall, I will suggest to minimize LZP in PAQ - i.e. use LZP for highest orders only (instead of a match model).

    A kind of PPMDet (PPMZ).

    You may also use a special structure for chars - i.e. keep count of a byte and if it frequently seen, do not replace it with another.

    In addition, a tricky model can be used with LZP - a special flag model (predicted/not predicted char) additionally to partial literal model update - regardless of an LZP you may update the main model.

    And so on...

  11. #11
    Programmer giorgiotani's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    166
    Thanks
    3
    Thanked 2 Times in 2 Posts
    Nice to see PAQ9, I hope it may grow up as a very good research thread like PAQ8 and LPAQ* are!

  12. #12
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    571
    Thanks
    219
    Thanked 205 Times in 97 Posts
    The (de)compression speed asymmetry makes PAQ9 a good candidate for a merge with Precomp:

    lprepaq -t+ 5 FlashMX.pdf: (No precompression)
    4526946 -> 3631849, 55.47 s
    lprepaq 5 FlashMX.pdf:
    4526946 -> 2242369, 190.37 s

    paq9a -3 FlashMX.pdf:
    4526946 -> 3636325, 95.19 s
    paq9a -3 FlashMX.pcf:
    26936624 -> 2295579, 133.88 s

    Note how lprepaq gets about 3,5 times slower because the temporary PCF file has almost 27 MB, while paq9a is just 1,5 times slower. Same for paq8o8(pre), although I'll soon release a faster version of paq8o8pre that handles PDF images as BMPs and gains much speed doing so.
    http://schnaader.info
    Damn kids. They're all alike.

  13. #13
    Moderator

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

    Test machine: Intel PIII @750 MHz, 512 MB RAM with Windows 2000 Pro + SP4 operating system

    Test file: enwik8

    PAQ9A Settings: -5

    enwik8 100000000 -> 20689913
    -> 20689924 in 1849.11 sec
    HashTable<16> 99.6114% full, 43.8024% utilized of 65536 KiB
    LZP hash table 99.3974% full of 16384 KiB
    LZP buffer 100.0000% full of 16384 KiB
    LZP 76831446 literals, 23168554 matches (23.1686% matched)
    Used 111093 KiB memory
    The test was also timed with AcuTimer v1.2:
    Elapsed Time: 00 00:30:50.969 (1850.969 Seconds)
    Same test with LPQ1
    enwik8 100000000 -> 19888389
    -> 19888399 in 1169.14 sec

    Elapsed Time: 00 00:19:29.662 (1169.662 Seconds)
    and LPAQ8 (5)
    100000000 -> 20614034 in 1280.671 sec. using 102 MB memory

    Elapsed Time: 00 00:21:22.279 (1282.279 Seconds)

  14. #14
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    Quote Originally Posted by encode
    2 Matt:
    There are many things to try with LZP.

    You may use a fixed order for LZP - order-8 and higher.
    No need in match legths - predicted/not predicted only stuff.


    if (tab[hash] == c) // predicted
    ...
    else // nope
    ...

    tab[hash] = c; // update

    The problem with this approach is that the match length is useful for modeling the match probability. This allows very long matches to be compressed to almost nothing, like this (2 copies of Calgary corpus). You cant do this with fixed orders.

    C:&#92;res>paq9a a x calgary&#92;* calgary&#92;*
    calgary&#92;BIB 111261 -> 23588
    calgary&#92;BOOK1 768771 -> 202716
    calgary&#92;BOOK2 610856 -> 128383
    calgary&#92;GEO 102400 -> 47632
    calgary&#92;NEWS 377109 -> 93212
    calgary&#92;OBJ1 21504 -> 8886
    calgary&#92;OBJ2 246814 -> 57876
    calgary&#92;PAPER1 53161 -> 11619
    calgary&#92;PAPER2 82199 -> 17788
    calgary&#92;PIC 513216 -> 43494
    calgary&#92;PROGC 39611 -> 9495
    calgary&#92;PROGL 71646 -> 11467
    calgary&#92;PROGP 49379 -> 8311
    calgary&#92;TRANS 93695 -> 12151
    calgary&#92;BIB 111261 -> 41
    calgary&#92;BOOK1 768771 -> 89
    calgary&#92;BOOK2 610856 -> 75
    calgary&#92;GEO 102400 -> 33
    calgary&#92;NEWS 377109 -> 63
    calgary&#92;OBJ1 21504 -> 19
    calgary&#92;OBJ2 246814 -> 79
    calgary&#92;PAPER1 53161 -> 19
    calgary&#92;PAPER2 82199 -> 21
    calgary&#92;PIC 513216 -> 199
    calgary&#92;PROGC 39611 -> 18
    calgary&#92;PROGL 71646 -> 25
    calgary&#92;PROGP 49379 -> 21
    calgary&#92;TRANS 93695 -> 36
    -> 677711 in 18.03 sec

  15. #15
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,475
    Thanks
    26
    Thanked 121 Times in 95 Posts
    why not just use matchmodel from lpaq?

    ie. get probability from matchmodel and when probability is higher than x (x may be fixed or variable) or we've matcher last y bits (y is a threshold) then disable all other models.

  16. #16
    Expert
    Matt Mahoney's Avatar
    Join Date
    May 2008
    Location
    Melbourne, Florida, USA
    Posts
    3,255
    Thanks
    306
    Thanked 779 Times in 486 Posts
    The matchmodel doesn't give you the speedup. With LZP you only model 1 bit per byte instead of 8. Notice the percent matched and the speed difference:

    C:
    esmaxcomp>..paq9a a x1 flashmx.pdf
    flashmx.pdf 4526946 -> 3631654
    -> 3631670 in 36.13 sec
    HashTable<16> 86.1691% full, 31.1660% utilized of 262144 KiB
    LZP hash table 21.3184% full of 65536 KiB
    LZP buffer 6.7457% full of 65536 KiB
    LZP 4123617 literals, 403329 matches (8.9095% matched)
    Used 406005 KiB memory

    C:
    esmaxcomp>..paq9a a x2 fp.log
    fp.log 20617071 -> 391464
    -> 391475 in 15.00 sec
    HashTable<16> 4.3259% full, 1.4494% utilized of 262144 KiB
    LZP hash table 2.4792% full of 65536 KiB
    LZP buffer 30.7218% full of 65536 KiB
    LZP 1363990 literals, 19253081 matches (93.3842% matched)
    Used 406005 KiB memory

  17. #17
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,426
    Thanks
    223
    Thanked 1,053 Times in 565 Posts
    Compiled paq9a myself.
    http://shelwien.googlepages.com/paq9a.exe
    Seems to be 10% faster.

  18. #18
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    I tried to test your 10% faster version of PAQ9A on my Intel P3 @750 MHz machine. I wanted to compare compression time with the time from my previous test.

    Fatal Error: This program was not built to run on the processor in your system.
    The allowed processors are: Intel(R) Pentium(R) 4 and compatible Intel processor
    s. Enables new optimizations in addition to Intel processor-specific optimizatio
    ns.
    I guess I wont be testing this one after all!

  19. #19
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,426
    Thanks
    223
    Thanked 1,053 Times in 565 Posts
    Well, here you go: http://shelwien.googlepages.com/paq9a_p3.exe
    Still should be faster than gcc version, I think.

  20. #20
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Thanks Shelwien! Will test it now and post results later.

  21. #21
    Moderator

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

    enwik8 100000000 -> 20689913
    -> 20689924 in 1779.02 sec
    HashTable<16> 99.6114% full, 43.8024% utilized of 65536 KiB
    LZP hash table 99.3974% full of 16384 KiB
    LZP buffer 100.0000% full of 16384 KiB
    LZP 76831446 literals, 23168554 matches (23.1686% matched)
    Used 111093 KiB memory

    Elapsed Time: 00 00:29:40.739 (1780.739 Seconds)

  22. #22
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,426
    Thanks
    223
    Thanked 1,053 Times in 565 Posts
    What about this then?
    http://shelwien.googlepages.com/paq9a_p3_91.exe
    Prev version was built with IntelC 10, and this one is 9.1 -
    could be better for old CPUs.

  23. #23
    Moderator

    Join Date
    May 2008
    Location
    Tristan da Cunha
    Posts
    2,034
    Thanks
    0
    Thanked 4 Times in 4 Posts
    Thanks Shelwien! Results below...

    enwik8 100000000 -> 20689913
    -> 20689924 in 1769.71 sec
    HashTable<16> 99.6114% full, 43.8024% utilized of 65536 KiB
    LZP hash table 99.3974% full of 16384 KiB
    LZP buffer 100.0000% full of 16384 KiB
    LZP 76831446 literals, 23168554 matches (23.1686% matched)
    Used 111093 KiB memory

    Elapsed Time: 00 00:29:31.715 (1771.715 Seconds)
    Mirror of all three optimised versions: Download

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

    You said, that lzp lengths are modeled best (best in the sense of order n) under an order 2 context? Have you tried to approximate the length model by quantization?

    Some terminilogy: what is a match length? Just the matching length starting past the lzp pointer, or matching context (preceeding the pointer) and the length succseeding the pointer.
    M1, CMM and other resources - http://sites.google.com/site/toffer86/ or toffer.tk

  25. #25
    Member
    Join Date
    Jan 2008
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts
    > Here is a preview of PAQ9
    > http://cs.fit.edu/~mmahoney/compression/paq9a.zip
    > It uses the same archive format and command line interface as lpq1
    > (based on lpaq1) with similar compression ratio, but a little slower

    And the benefit is ???

    Tests:

    {B} BLUE.PNG
    209'409 bytes


    {H} HDPMI.TAR
    733'696
    Source code

    Code:
     
    PKZIP 2.50 -exx DPMI32 
     
    {B} 0.5s gave up 
    {H} 0.7s 188'342 
     
    KZIP default 
     
    {B}  1s gave up 
    {H} 20s 181'360 
     
    7-ZIP LZMA 
     
    {B} 0.5s 211'978 :-((( 
    {H}   2s 153'822 
     
    PAQ 
     
    {B}  8  s 209'247 -5 :-) 
    {H} 11  s 119'321 -5 
    {H} 12.5s 119'262 -6

    PAQ can "compress" even hard-core optimized PNG
    7-ZIP miserably fails here

    PAQ9 seems faster than older versions. Algorithm looks promisingly simple

    Some (sorry if stupid) questions:

    1. Why do you use C++ rather than C ?

    2. How much faster could it be if written in ASM instead of C++ ?

    3. It's a memory hog. Does it really use all the required almost 2 GiB of RAM (-9), even if the file to compress is < 1 MiB ?

  26. #26
    Member
    Join Date
    May 2008
    Location
    Kuwait
    Posts
    335
    Thanks
    36
    Thanked 36 Times in 21 Posts
    png is already compressed and the 2731b diff. is rather typical even if you compress bigger PNG .. so its the archive format result ..

  27. #27
    Member
    Join Date
    Jan 2007
    Location
    Moscow
    Posts
    239
    Thanks
    0
    Thanked 3 Times in 1 Post
    My 2 cents:
    1. C is no way faster then C++ today. May be C is easier to optimise, but modern complilers make the job with C++ rather good. And C++, of course, has much more insruments to make developement more rapid.
    2. ASM as language has no preferences comparing with C/C++. Most optimising compilers produce better machine code than intermediate ASM programmer. Anyway, some part of PAQ7-8 is written in ASM, because no compiler can beat experienced
    human brains The advantage is not as big as it could be some time ago. Modern processors are too complex and don't allow even ASM programmer to take 100% control over them.
    3. It's no sense esimating compressors on such a small files. Test them on your most common data, or on big enough files. And i don't see much sense compressing already compressed data too.

  28. #28
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,475
    Thanks
    26
    Thanked 121 Times in 95 Posts
    Quote Originally Posted by nimdamsk
    C is no way faster then C++ today.
    i would say rather that well written c++ code has equal speed to pure c code. rtti or other things in c++ that are done at runtime slows down programs but theyre optional (and rarely used).

    c++ libraries can be faster than c libs. for eqample take sorting into consideration. std::sort is way faster than stdlib qsort() because c++ has operator overloading which makes comparing elements with std::sort way faster than executing external function as its done in qsort.

    and c++ allows to write fast code faster than in pure c.

    Quote Originally Posted by nimdamsk
    Anyway, some part of PAQ7-8 is written in ASM, because no compiler can beat experienced
    human brains
    its mainly caused by the fact that c++ doesnt have native support for streaming processing - simd: mxx, sse and others. particularly c++ doesnt have support for packed data types.

    Quote Originally Posted by nimdamsk
    Modern processors are too complex and dont allow even ASM programmer to take 100% control over them.
    what are you saying??? i (as asm programmer) have 100 % control over the processor and system. its just getting harder.



    matt:
    i would rather concentrate on speeding up match model and abandon lzp model.

    eg. if there was lots of redundancy seen in the recent data (and of course all bits was matched by match model) then use only one (longest) context in match model. and i suggest using rather short contexts.

    for compressing repetitions that are over (say) 120 bytes long i would use preprocessing. ie. use some special symbol for marking lzp match (as in lzp preprocessor for ppmdj). and use some heuristics for determining the beginning of a match (ie. we can delay outputting a match when we know that well get higher probability of a match/ match code in later contexts).

  29. #29
    Member
    Join Date
    Jan 2007
    Location
    Moscow
    Posts
    239
    Thanks
    0
    Thanked 3 Times in 1 Post
    Quote Originally Posted by donkey7
    what are you saying??? i (as asm programmer) have 100 % control over the processor and system. its just getting harder.
    As you have no CPU microcode sources you have to believe CPU vendor, and they must not tell you all the truth. As you dont have full CPU scheme you cant think about 100% control over it. All you can is believing manuals and try to analyse yours "black box" CPU output.

  30. #30
    Member
    Join Date
    Jun 2009
    Location
    Kraków, Poland
    Posts
    1,475
    Thanks
    26
    Thanked 121 Times in 95 Posts
    i haven't? look at: http://agner.org/optimize/
    there's optimization manual for all intel x86 intel processors starting from pentium (afaik first x86 processor with risc core). and they tells how any instruction is decoded and executed.

    i don't have cpu scheme but i have all timings and other information (about instruction decoding, microcode execution and data flow) so i can compute exact number of processor ticks needed to execute code without actually executing it.

    optmizing for 486 and earlier processors was simpler because they executed only one instruction at once. newer processors can execute few instructons at once (more than one) but programmers know how they're executed.

Page 1 of 2 12 LastLast

Similar Threads

  1. ZPAQ 1.05 preview
    By Matt Mahoney in forum Data Compression
    Replies: 11
    Last Post: 30th September 2009, 05:26
  2. FreeArc 0.40 preview
    By Bulat Ziganshin in forum Forum Archive
    Replies: 16
    Last Post: 17th August 2007, 10:28

Posting Permissions

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