BCM v0.01 - New BWT+CM-based compressor

[encode]

His current Mcomp V2.0 seems to use 4 cores for BWT :

mcomp_x32
LibMComp Demo Compressor (v2.00).
Copyright (c) 2008 M Software Ltd.
mcomp [options] pofile(s)

Options:
    -m[..]    Compression method:
              b    - BZIP2.
              c    - Experimental DMC codec.
              d    - Optimised deflate (df - fast, dx - max)
             d64  - Optimised deflate64 (d64f - fast, d64x - max)
              lz   - Optimised LZ (lzf - fast, lzx - max)
              f    - Optimised ROLZ (ff - fast, fx - max)
              f3   - Optimised ROLZ3 (f3f - fast, f3x - max)
              p    - PPMd var.J.
              sl   - Bitstream (LSB first).
              sm   - Bitstream (MSB first).
              w    - Experimental BWT codec.
    -MNN[k,m] Model size (in kb (default) or Mb, default 64M).
    -oNN      Order (for Bitstream and PPMd).
    -np       Display no progress information.

mcomp_x32 -mw fp.log  fplog_mw.mcomp

LibMComp Demo Compressor (v2.00).
Copyright (c) 2008 M Software Ltd.
Thread pool size = 4
Using 1280Mb (4 threads)
100%
From 20617071 => To 559960
Elapsed time: 5.355s      (3759.82kps)

Hm, cool! Never heard about this new MCOMP version...
Will check it out!

[joerg]

LibMComp Demo Compressor (v2.00).
Copyright (c) 2008 M Software Ltd.

Thread pool size = 4
---
mcomp_x32 -np -mb d:db.dmp mo-b
From 648331264 => To 40075288 Elapsed time: 250.894s (2523.52kps)
---
mcomp_x32 -np -mf3f d:db.dmp mo-f3f
From 648331264 => To 40981130 Elapsed time: 296.906s (2132.45kps)
---
mcomp_x32 -np -mf3x d:db.dmp mo-f3x
From 648331264 => To 26982492 Elapsed time: 2750.229s (230.21kps)
---
mcomp_x32 -np -mw -M64m d:db.dmp mo-w64
mcomp_x32 -np -mw -M80m d:db.dmp mo-w80
mcomp_x32 -np -mw -M82m d:db.dmp mo-w82
mcomp_x32 -np -mw -M84m d:db.dmp mo-w84
mcomp_x32 -np -mw -M86m d:db.dmp mo-w86
mcomp_x32 -np -mw -M88m d:db.dmp mo-w88
mcomp_x32 -np -mw -M89m d:db.dmp mo-w89
mcomp_x32 -np -mw -M92100k d:db.dmp mo-w9x
mcomp_x32 -np -mw -M92159k d:db.dmp mo-w9y
---
Using 1280Mb (4 threads)
From 648331264 => To 31929712 Elapsed time: 173.199s (3655.54kps)
-------- 1280Mb (4 threads)
From 648331264 => To 31929712 Elapsed time: 156.254s (4051.97kps)
Using 1600Mb (4 threads)
From 648331264 => To 31190161 Elapsed time: 177.600s (3564.95kps)
Using 1640Mb (4 threads)
From 648331264 => To 32005923 Elapsed time: 191.748s (3301.92kps)
Using 1680Mb (4 threads)
From 648331264 => To 31997373 Elapsed time: 177.641s (3564.13kps)
Using 1720Mb (4 threads)
From 648331264 => To 31889912 Elapsed time: 170.698s (3709.10kps)
-------- 1720Mb (4 threads)
From 648331264 => To 31889912 Elapsed time: 172.465s (3671.10kps)
Using 1760Mb (4 threads)
From 648331264 => To 31547194 Elapsed time: 175.458s (3608.48kps)
Using 1780Mb (4 threads)
From 648331264 => To 31423789 Elapsed time: 169.694s (3731.04kps)
-------- 1780Mb (4 threads)
From 648331264 => To 31423789 Elapsed time: 173.917s (3640.45kps)
Using 1798Mb (4 threads)
From 648331264 => To 31385818 Elapsed time: 171.175s (3698.76kps)
-------- 1798Mb (4 threads)
From 648331264 => To 31385818 Elapsed time: 189.617s (3339.03kps)
Using 1799Mb (4 threads)
From 648331264 => To 31382770 Elapsed time: 178.445s (3548.07kps)
-------- 1799Mb (4 threads)
From 648331264 => To 31382770 Elapsed time: 171.091s (3700.58kps)

---
if run the program several times
there were all times different results in Elapsed time - the "To" - result is the same in each case
---
especially the -mw (BWT) have occupied the 4 cores up to 99 % (windows average system usage rate)
the -mf3x shows 26 % (windows average system usage rate)
---

interesting result in my quick test of mcomp_x32

1. the best result for compress ratio has "-mf3x" = "ROLZ3 max"
(the best result over all compressors has PAQ8o

2. -mw (BWT) seems to be significantly faster then -mb (BZIP)

3. for -mw (BWT) the compression ratio seems to have a optimum
for memory -M80m
- better compression then -M64m
- better then -M88m too

That means within BWT more memory
not means automatically better compression ratio ?!
maybe some implementation problem ?
mcomp_x32 can not allocate memory more then 1800 MBytes ?

4. BWT - implementation uses 4 cores and is

ASK:
There are 2 programs
pbzip2 (multi core parallel bzip2) and mgzip (multi processor smp gzip).
Has anyone a win32-binary of this programs for test purposes?

[encode]

Good news about BCM. Currently I'm working very heavy on a new release. Mostly it's about my optimizer and new CM stuff. Of course I added a stable enough sorting to be OK with 'pht.psd' and many other files - new BCM processes them FAST!

[toffer]

Did you make your optimizer non-bruteforce meanwhile?

[encode]

Not yet!

At the same time CM with lots of models and dynamic mixing is FAR more tunable than dummy PPM...

[pat357]

Good news about BCM. Currently I'm working very heavy on a new release. Mostly it's about my optimizer and new CM stuff. Of course I added a stable enough sorting to be OK with 'pht.psd' and many other files - new BCM processes them FAST!

I'm really looking forward to the new BCM !
I had mixed feelings at the time you stopped the development (of course due other priorities), so I'm glad to see it will be back !!

[encode]

I've made a very simple CM. The performance is about the same as with BWT from the newest MCOMP.EXE, but FASTER! Maybe the speed will be the main goal, especially I'm talking about really fast decompression. CM represents a few different counters with different contexts, no SSE, APM, etc. just static mixing - this makes it FAST! At the same time the compression is really OK! In addition, new BCM will have an EXE filter...
So, what do you prefer:

• Fast and efficient BWT (as mcomp.exe)
• Fast enough with the best BWT performance possible

[nanoflooder]

Two switches, -fast and -best

[m^2]

The more efficient one.

[encode]

Two switches, -fast and -best

Well, the thing is, fast and best are two different programs.

The more efficient one.

Indeed, with previous versions of BCM I noticed that at the decoding, the unsorting stage runs very quick and the bottleneck is actual CM decoding.

Now I'm building principally new CM model, keeping in mind simplicity, but at the same time I compare my results with other BWT coders like mcomp -mw, BBB, Blizzard, ...

[m^2]

Actually I didn't mean decoding efficiency, but any trade off between encoding and decoding that you like.
Do you think you can decode as efficiently as lz algorithms?
If yes - ok, go for it. But from my (very limited) experience with BWT packers, they don't excel here.

[encode]

Actually I didn't mean decoding efficiency, but any trade off between encoding and decoding that you like.
Do you think you can decode as efficiently as lz algorithms?
If yes - ok, go for it. But from my (very limited) experience with BWT packers, they don't excel here.

Of course a modern BWT may not catch the LZMA's decompression speed. However, at the same time BWT has much better text and other compression for example. At the same time BWT is MUCH faster at decoding than CM and PPM achieving nearly the same or even better compression!

[m^2]

Of course a modern BWT may not catch the LZMA's decompression speed. However, at the same time BWT has much better text and other compression for example. At the same time BWT is MUCH faster at decoding than CM and PPM achieving nearly the same or even better compression!

I should have specified:
If you can achieve good efficiency on any reasonably sized set of files, that's perfectly fine.
Just beat dict+lzma.

Added: You're unlikely to beat bcj2+lzma on exe files, maybe it's better to add dict/xwrt and Bulat's mm?
And remove data that it won't be able to compress well from your training set. It only hurts.

[encode]

Small comparison of BCM v0.02 and Dummy BCM v0.03 (Not fully optimized yet):

3200.txt (16,013,962 bytes)

BCM v0.02: 3,813,827 bytes, enc: 16 sec, dec: 7 sec
BCM v0.03: 3,753,618 bytes, enc: 6 sec, dec: 5 sec

For comparison BBB results:

BBB f: 3,922,287 bytes, enc: 22 sec, dec: 13 sec
BBB fm16: 3,686,490 bytes, enc: 26 sec, dec: 14 sec

[encode]

7z Ultra -> 4,563,571 bytes

[encode]

And PPMX:

PPMX v0.05: 3,963,050 bytes, enc: 11 sec, dec. 11 sec

Looks like BCM should be my flagship compressor...

[nanoflooder]

Can't wait to test it

[encode]

After yet another day of optimization BCM became one of the strongest and fastest BWT available!

Some testing results:

calgary.tar (3,152,896 bytes)
BCM -> 787,078 bytes
BLIZ -> 790,491 bytes
BBB -> 798,705 bytes
MCOMP -> 800,402 bytes

book1 (768,771 bytes)
BCM -> 211,554 bytes
BLIZ -> 212,130 bytes
BBB -> 213,162 bytes
MCOMP -> 217,403 bytes

[encode]

3200.txt -> 3,675,343 bytes

[m^2]

Is it faster than rings / grzip?

[encode]

Is it faster than rings / grzip?

Never tested... BCM is too strong to compare with them...

[joerg]

cant wait to test your new BCM v0.03

excuse me please

for now bcm001 and bcm002 compress better than balz

but rings 1.3 and rings 1.5c wins clearly
on textfile or oracle-dmp-file (size and time is lower)

The Testfile db.dmp (Oracle-dump-file) has 648331264 bytes.

bcm001 compress to 31.927.387 bytes 22 min
bcm002 compress to 31.022.446 bytes 17 min
---
RINGS v.1.3 (FCM Fast Context Mixing) file compressor. Only for testing
Copyright ? 2007 by Nania Francesco Antonio (Italy). All rights reserved.

rings13 c db.dmp c:\tdbri13 compress to 26356464 bytes time= 101.83 s
---
RINGS v.1.5c (FCM Fast Context Mixing) file compressor. Only for testing
Copyright 2007-2008 by Nania Francesco Antonio (Italy). All rights reserved.

rings15c c 2 db.dmp c:\tdbri2 compress to 30505178 bytes time= 104.59 s
rings15c c 3 db.dmp c:\tdbri3 compress to 28717515 bytes time= 92.70 s
rings15c c 4 db.dmp c:\tdbri4 compress to 27461544 bytes time= 93.69 s
rings15c c 5 db.dmp c:\tdbri5 compress to 26580793 bytes time= 89.43 s
rings15c c 6 db.dmp c:\tdbri6 compress to 25955867 bytes time= 180.32 s
rings15c c 7 db.dmp c:\tdbri7 compress to 25649655 bytes time= 152.19 s


best regards