BIT Archiver

[osmanturan]

Thank you, tested That's very decent improvement during just one day!

Your benchmarking is fast too. Thanks a lot! I can't figure out why you get worser speed than BIT 0.2b. Can you confirm that disk trashing or anything else?

Here is another test result for ENWIK9
185,887,585 bytes @ 573 KB/sec (1702.558 Seconds)

So, BIT just climb up to rank #30 on LTCB!

[Black_Fox]

No trashing I'm aware of. Could it be because of smaller cache compared to Intel Core CPUs or higher optimization target than are Athlons?

[osmanturan]

In BIT 0.3, I had removed a bit large lookup table which is implemented for avoiding slow division. In BIT 0.4, I reduced the neural network weight sets. Also, some hardware prefetching was added to NN weights and hash entry locating function. As you see, the changes are mainly for increasing cache efficiency. I really don't understand those AMD's systems.

In old days, I have some problems like that. For my game engine, I tried AMD's assembly source code about fast memory copying (implemented several methods in one function: hardware prefetching, software prefetching, temporal moves etc). They says in a paper speeds-up to hundreds of MB per seconds against regular memcpy. But, I tried it for Intel CPU's. Interestingly, my unrolled copying routine much more faster! It was purely written in delphi!

[LovePimple]

Here is another the fresh release of BIT. There is some small compression releated tweaks. Overall, there is 0.7-1.2% compression gain. Also, the "non-exists file bug" have been fixed (thanks Intrinsic). Here is some tests for "best" profile:

Here is the link of the new release:
http://www.osmanturan.com/bit04.zip

Thanks Osman!

[LovePimple]

Compression speed seems to be the same as BIT v0.3 on my old Intel Pentium 3 @750 MHz, 512 MB RAM, Windows 2000 SP4 machine...

bit4 a calgary_bit04_normal -m lwcx -p normal -files calgar.tar

Bit Archiver v0.4 (Aug  1 2008 19:30:18)
(c) 2007-2008, Osman Turan

WARNING: EXPERIMENTAL RELEASE. DO NOT USE FOR REAL BACKUPS!

Archive not found. Creating a new archive: calgary_bit04_normal

Compressing: calgar.tar
Processed:      3152896/     3152896 bytes (Speed:      104 KB/s)

Compressed Size: 740147 bytes
        
Elapsed Time: 29.393 seconds

[osmanturan]

Why don't all computer have at least a Core2 Duo performance for BIT? In BIT 0.4, a really big lookup was reduced. There must be another things for chopping them without losing the compression.

[LovePimple]

Test Machine: AMD Sempron 2400+, Windows XP SP2

Bit Archiver v0.3 (Jul 31 2008 11:11:11)
(c) 2007-2008, Osman Turan

WARNING: EXPERIMENTAL RELEASE. DO NOT USE FOR REAL BACKUPS!

Archive not found. Creating a new archive: calgary_bit03_best

Compressing: calgar.tar
Processed:      3152896/     3152896 bytes (Speed:      115 KB/s)

Compressed Size: 733 KB (751,533 bytes)

        Elapsed Time: 26.812 seconds

bit4 a calgary_bit04_best -m lwcx -p best -files calgar.tar

Bit Archiver v0.4 (Aug  1 2008 19:30:18)
(c) 2007-2008, Osman Turan

WARNING: EXPERIMENTAL RELEASE. DO NOT USE FOR REAL BACKUPS!

Archive not found. Creating a new archive: calgary_bit04_best

Compressing: calgar.tar
Processed:      3152896/     3152896 bytes (Speed:      118 KB/s)

Compressed Size: 722 KB (739,425 bytes)

        Elapsed Time: 26.093 seconds

Performance seems to be slightly improved on my AMD Sempron 2400+, Windows XP SP2 machine.

[osmanturan]

@LovePimple:
Finally, I saw a very tiny speed improvement. Luckily, there is also compression gain too. I have downloaded some papers from AMD site. Let's figure out why those systems are very slow for my compressor.

BTW, I really want to catch <700KB for calgary and 10-10,5 MB for SFC. Any ideas for improving it without too much speed loss?

[toffer]

Correct me, if i'm wrong...

- you use a NN for weighting, so you need to input probabilities
- you use some counter model, which needs divisions

... so you need a division *per probability input*? This makes things horribly slow, for sure. You should use a directly probability based counter model.

[osmanturan]

Correct me, if i'm wrong...

- you use a NN for weighting, so you need to input probabilities
- you use some counter model, which needs divisions

... so you need a division *per probability input*? This makes things horribly slow, for sure. You should use a directly probability based counter model.

I use a NN for weighting. And I use semi-stationary counters which need division. At "Counter Prediction" stage, the division and a lookup based quantization has occured for NN.

Honestly, current profiling version doesn't tell too much thing. I'll implement it in a different way.

[toffer]

How large is your quantisation table?

If you want to get a quick answer regarding a speedup, just replace your counter model with one, which doesn't need a division. Compression can be gained by optimization, of course.

[osmanturan]

My mixer very similar as PAQ's one. The quantization before mixing is well-known stretch() itself. It's 8KB lookup.

Edit: I forgot to answer for counters. I have used your counters in couple of weeks ago. Speed increased. But, I didn't retest with current schema. I'll test it again. BTW, can you give me some optimized counter parameters for each order-n model to see that they are really good for my compressor? Else I'll use 43 11 combination for all models.

[toffer]

Do you use a table to avoid divisions?

[osmanturan]

No, I removed it - it was in BIT 0.2b. Interestingly, this only benefits for Core2 Duo. AMD's processor speed hurt actually by doing this. You can see the results on Black Fox benchmark.

[LovePimple]

Test Machine: AMD Sempron 2400+, Windows XP SP2

Test Files: ENWIK8, ENWIK9

bit4 a enwik8.bit -m lwcx -p best -files enwik8

Bit Archiver v0.4 (Aug  1 2008 19:30:18)
(c) 2007-2008, Osman Turan

WARNING: EXPERIMENTAL RELEASE. DO NOT USE FOR REAL BACKUPS!

Archive not found. Creating a new archive: enwik8.bit

Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      138 KB/s)

Compressed Size: 20.6 MB (21,686,636 bytes)

        Elapsed Time: 704.500 seconds

bit4 a enwik9.bit -m lwcx -p best -files enwik9

Bit Archiver v0.4 (Aug  1 2008 19:30:18)
(c) 2007-2008, Osman Turan

WARNING: EXPERIMENTAL RELEASE. DO NOT USE FOR REAL BACKUPS!

Archive not found. Creating a new archive: enwik9.bit

Compressing: enwik9
Processed:   1000000000/  1000000000 bytes (Speed:      141 KB/s)

Compressed Size: 177 MB (185,887,585 bytes)

        Elapsed Time: 6913.813 seconds

No disk thrashing during the test.

[osmanturan]

@LovePimple:
Thanks for deeply testing. AMD's results are really interesting. One of my friend have reached 854 KB/sec for a very big bitmap file (~75 MB) with BIT 0.4. I have never see this result in this forum. Maybe I should inspect both systems: the slowest and fastest (of course on modern CPUs. Not historical P3 750MHz). So, I may catch bottlenecks.

Edit: BTW, first of all I must change my counter model which have a single division for each modelled bit. Shelwien pointed out that can be the reason. Because, Core2 Duo processor have a faster division algorithm. Also, toffer pointed out this problem. I'm able to see the next step in the horizon: linear counters

[osmanturan]

Test File: 76,800,056 bytes (a BMP file)

Compressed with "best" option into 4,742,292 bytes

Core2 Quad (Q6600) 2.4 GHz (2x64 KB L1, 2x4096 L2, 800 MHz FSB), 2 GB 800 MHz RAM
854 KB/sec (87.859 seconds)

Core2 Quad (Q6600) 2.4 GHz (2x64 KB L1, 2x4096 L2, 800 MHz FSB), 2 GB 1200 MHz RAM
877 KB/sec (85.504 seconds)

So, I think main bottleneck is computation - especially the division. Not memory access. Else I would expect larger difference in this test. Let's digging...

[pat357]

I did a test with the different BIT versions using the Shelwien's testdata.(379.710.414 bytes)
Here are the speeds indicated by BIT04, BIT02b ,BIT03 and BIT04_2nd for the different files. (pasted from Excel).
I did the test twice for BIT04 (last column)

bit04 bit02b bit03 bit4_2nd
bookstar 537 572 586 540
enwik8 579 605 642 580
finn_lst 653 644 696 649
cyg_bin.tar 551 550 571 551
cyg_lib.tar 654 654 696 671
mkv 418 406 420 417

average 565 572 602 568

compression results :
BIT 04 : 129.071.385 (Ratio 33.9%)
BIT 02b : 131.189.230 (Ratio 34.5%)
BIT 03 : 130.417.974 (Ratio 34.3%)

Based on this data, it seems that BIT 03 is the fastest on my system (696 KB/s on enwik8 & cyg_lib.tar). BIT v04 is the slowest.
System C2Q E6600 2.4MHz / 4GB RAM 533FSB / Vista Prem.
The complete log with all timings and ratio's is included in attachment.

I hope this may give you more insight on where the real bottleneck lies.

[osmanturan]

Hi everyone,
Again there is a new version. In this release, I did some tweaks before diving into linear counters (this release still uses old counter model). Compression improved. But, I can't say anything about speed. Because, an optimizer is currently running on my computer. So, I can't measure the speed correctly. But, some tweaks were done for speed too. So, I expect a tiny improvement. Here is some test results:

SFC
a10.jpg -> 832,108 bytes
AcroRd32.exe -> 1,371,100 bytes
english.dic -> 561,751 bytes
FlashMX.pdf -> 3,684,453 bytes
FP.log -> 576,575 bytes
MSO97.dll -> 1,728,172 bytes
ohs.doc -> 817,498 bytes
rafale.bmp -> 762,904 bytes
vcfiu.hlp -> 619,901 bytes
world95.txt -> 508,854 bytes
SFC Total -> 11,463,316 bytes

brosur1.tif -> 3,484,632 bytes
calgary.tar -> 739,653 bytes
design2.tif -> 11,316,652 bytes
enwik8 -> 21,676,636 bytes
valley.cmb -> 8,630,156 bytes

In this release, I also provided a x64 compilation. Honestly, I didn't test it properly. But, you should try Here is the link:

http://www.osmanturan.com/bit05.zip

I want to thank both Shelwien and Toffer for their great support in this release. I hope, I would provide the next release with optimized linear counters.

Edit: Added SFC Total...

Edit2: Err...I forgot the change the version number in executable. So, I've uploaded it again. Only "version number string" has changed. There isn't any compression specific changes.

[pat357]

A comparison between BIT v05, BIT v04 and BIT v0.2b on enwik8
(C2Q E6600 2.4Ghz / 4GB RAM 533Mhz / Vista Prem) :

G:\test\enwik8>xtime bit5 a enwik8_bit05__pbest -m lwcx -p best -files enwik8
XTIME v1.2
Copyright (c) 2008 by LovePimple
Bit Archiver v0.5 (Aug  7 2008 12:25:17)
(c) 2007-2008, Osman Turan
Archive not found. Creating a new archive: enwik8_bit05__pbest
Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      564 KB/s)
        Elapsed Time: 173.021 seconds
Elapsed Time: 173.043 Seconds

G:\test\enwik8>xtime bit4 a enwik8_bit04__pbest -m lwcx -p best -files enwik8
XTIME v1.2
Copyright (c) 2008 by LovePimple
Bit Archiver v0.4 (Aug  1 2008 19:30:18)
(c) 2007-2008, Osman Turan
Archive not found. Creating a new archive: enwik8_bit04__pbest
Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      579 KB/s)
        Elapsed Time: 168.591 seconds
Elapsed Time: 168.600 Seconds

G:\test\enwik8>xtime bit02b a enwik8_bit02b__mem9 -m lwcx -mem 9 -files enwik8
XTIME v1.2
Copyright (c) 2008 by LovePimple
Bit Archiver v0.2b (Jun 14 2008 11:35:57)
(c) 2007-2008, Osman Turan
Archive not found. Creating a new archive: enwik8_bit02b__mem9
Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      607 KB/s)
        Elapsed Time: 160.837 seconds
Elapsed Time: 160.971 Seconds

It seems that BIT v05 runs slower than BIT 04 and BIT02b on my system..
Any idea why this is ?

[osmanturan]

@pat357:
Still not sure what is the bottleneck. But, I found the bottleneck on AMD systems. Draft version of new BIT worked ~50% faster on an AMD system. But, there is not a huge performance on my system (Core2 Duo 2.2GHz, 2GB RAM). So, I don't expect a huge speed gain on your system too.

BTW, my friend has just tested the same file (a huge bitmap) with the new version on his system:

Core2 Quad (Q6600) 2.4 GHz (2x64 KB L1, 2x4096 L2, 800 MHz FSB), 2 GB 800 MHz RAM

840 KB/s (89.342 seconds)

Hmm. Speed was dropped as you see (854 KB/s -> 840 KB/s). Luckily, I'm happy to see some compression improvement.

[Sportman]

I also provided a x64 compilation. Honestly, I didn't test it properly. But, you should try

64bit version is working http://www.metacompressor.com/uploads.aspx

[osmanturan]

64bit version is working http://www.metacompressor.com/uploads.aspx

Thanks! If it's possible, could you test it on other test sets too? Seems current BIT highly compress the "file7" testset.

[LovePimple]

Hi everyone,
Again there is a new version. In this release, I did some tweaks before diving into linear counters (this release still uses old counter model). Compression improved. But, I can't say anything about speed. Because, an optimizer is currently running on my computer. So, I can't measure the speed correctly. But, some tweaks were done for speed too. So, I expect a tiny improvement.

Here is the link:
http://www.osmanturan.com/bit05.zip

I want to thank both Shelwien and Toffer for their great support in this release. I hope, I would provide the next release with optimized linear counters.

Thanks Osman!

Mirror: Download

[Black_Fox]

Thanks Osman! Made a little test (everything -m lwcx -p best, C2Q Q6600 @2.4 GHz, 2GB RAM @666 MHz, Vista Ultimate SP1 x64, used ENWIK:

BIT 0.4

PexTimer v2.0
Copyright (c) 2007 by LovePimple

Bit Archiver v0.4 (Aug  1 2008 19:30:18)
(c) 2007-2008, Osman Turan

WARNING: EXPERIMENTAL RELEASE. DO NOT USE FOR REAL BACKUPS!

Archive not found. Creating a new archive: bit04.bit

Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      600 KB/s)

        Elapsed Time: 162.578 seconds
Elapsed Time:  00  00:02:42.860  (162.860 Seconds)

BIT 0.5

PexTimer v2.0
Copyright (c) 2007 by LovePimple

Bit Archiver v0.5 (Aug  7 2008 12:25:17)
(c) 2007-2008, Osman Turan

WARNING: EXPERIMENTAL RELEASE. DO NOT USE FOR REAL BACKUPS!

Archive not found. Creating a new archive: bit05.bit

Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      585 KB/s)

        Elapsed Time: 166.953 seconds
Elapsed Time:  00  00:02:47.247  (167.247 Seconds)

BIT 0.5 x64

PexTimer v2.0
Copyright (c) 2007 by LovePimple

Bit Archiver v0.5 (Aug  7 2008 12:26:11)
(c) 2007-2008, Osman Turan

WARNING: EXPERIMENTAL RELEASE. DO NOT USE FOR REAL BACKUPS!

Archive not found. Creating a new archive: bit05_64.bit

Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      486 KB/s)

        Elapsed Time: 200.688 seconds
Elapsed Time:  00  00:03:20.869  (200.869 Seconds)

[osmanturan]

Hi everyone,
Here is the new version: BIT 0.6. I mainly played with speed optimizations in this release. I tried linear counters with context merging for both speed and compression. Honestly, parameter optimizations have not finished completely. So, on some files I expect some compression loss. Here is some test results:

a10.jpg -> 834,842 bytes
AcroRd32.exe -> 1,367,945 bytes
english.dic -> 513,068 bytes
FlashMX.pdf -> 3,687,211 bytes
FP.log -> 585,570 bytes
MSO97.dll -> 1,733,570 bytes
ohs.doc -> 807,426 bytes
rafale.bmp -> 765,584 bytes
vcfiu.bit17 -> 614,537 bytes
world95.txt 537,306 bytes
Total SFC: 11,447,059 bytes

brosur1.tif -> 3,469,784 bytes
calgary.test -> 744,494 bytes
design2.tif -> 11,183,527 bytes
enwik8 -> 22,260,001 bytes
valley.cmb -> 8,628,361 bytes

I underlined better results. When parameter optimization will be completed, I believe the other results will be improved too.

Here is the link: http://www.osmanturan.com/bit06.zip

[pat357]

For comparison Bit v6-v5-v4-v3 and v2b on enwik8 :

Test system : C2Q E6600 2.4Ghz / 4GB RAM 2x266MHhz / Vista Prem.

Bit06_p_best
Bit Archiver v0.6 (Aug 12 2008 15:40:03)
(c) 2007-2008, Osman Turan
Archive not found. Creating a new archive: enwik8__bit06_p_best_nr6.bit
Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      654 KB/s)
        Elapsed Time: 149.340 seconds
User Time    =   149.183 = 00:02:29.183 =  99%
Process Time =   150.026 = 00:02:30.026 = 100%
Global Time  =   149.370 = 00:02:29.370 = 100%
--> 22,260 %
========================================================
Bit05_p_best
Bit Archiver v0.5 (Aug  7 2008 12:25:17)
(c) 2007-2008, Osman Turan
Archive not found. Creating a new archive: enwik8__bit05_p_best_nr6.bit
Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      570 KB/s)
        Elapsed Time: 171.289 seconds
User Time    =   170.649 = 00:02:50.649 =  99%
Process Time =   171.351 = 00:02:51.351 = 100%
Global Time  =   171.289 = 00:02:51.289 = 100%
--> 21.677 %
========================================================
Bit04_p_best
Bit Archiver v0.4 (Aug  1 2008 19:30:18)
(c) 2007-2008, Osman Turan
Archive not found. Creating a new archive: enwik8__bit04_p_best_nr6.bit
Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      585 KB/s)
        Elapsed Time: 166.812 seconds
User Time    =   165.641 = 00:02:45.641 =  99%
Process Time =   166.421 = 00:02:46.421 =  99%
Global Time  =   166.812 = 00:02:46.812 = 100%
--> 21.687 %
========================================================
Bit03_p_best
Bit Archiver v0.3 (Jul 31 2008 11:11:11)
(c) 2007-2008, Osman Turan
Archive not found. Creating a new archive: enwik8__bit03_p_best_nr6.bit
Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      643 KB/s)
        Elapsed Time: 151.742 seconds
User Time    =   150.743 = 00:02:30.743 =  99%
Process Time =   151.617 = 00:02:31.617 =  99%
Global Time  =   151.758 = 00:02:31.758 = 100%
-->  21.847 %
========================================================
Bit02b_mem9
Bit Archiver v0.2b (Jun 14 2008 11:35:57)
(c) 2007-2008, Osman Turan
Archive not found. Creating a new archive: enwik8__bit02_mem9_nr6.bit
Compressing: enwik8
Processed:    100000000/   100000000 bytes (Speed:      604 KB/s)
        Elapsed Time: 161.602 seconds
User Time    =   160.057 = 00:02:40.057 =  98%
Process Time =   160.837 = 00:02:40.837 =  99%
Global Time  =   161.757 = 00:02:41.757 = 100%
--->  21.972 %

Yeah !! The speed from v3 seems to be back and is even surpassed by the new bit6 !
On enwik( this is the fastest Bit ever ! Congrats Osman !

--edit- almost forgot to mention it; it seems to have lost a bit on the compression ratio... but Osman is probably fixing that for the next release

[osmanturan]

@pat357:
Thanks a lot for your valuable support! With this release, LWCX mode is getting more closer to the end. There are only some tweaks to left for improving compression. After completing them, I'll go on speed again. So, you may see some tiny speed improvement on next releases. I hope, I can catch 700 kb/sec on your system for ENWIK8.

Edit: About compression loss.
Actually this is due to parameters which I used. The optimization process is still running on my computer and the avarage compression gain is very small for per hours (Honestly, my current optimizer is very bad for finding best parameters). Also, I may change my mixer. It may gain compression besides speed. We'll see the mentioned improvements on next release

[LovePimple]

Hi everyone,
Here is the new version: BIT 0.6. I mainly played with speed optimizations in this release. I tried linear counters with context merging for both speed and compression. Honestly, parameter optimizations have not finished completely. So, on some files I expect some compression loss.

When parameter optimization will be completed, I believe the other results will be improved too.

Thanks Osman!

Mirror: Download

[pat357]

What dataset do you use to optimize ?
How does the optimization work ?
Is is like first defining a "profit" (output size, speed) and then searching for a min/max for this profit ?
I'm just just thinking loud...I know virtual nothing regarding this process..... But I'm very eager to know how you do this !
How many "iterations" do you for example need to optimize the defined profit ?