TarsaLZP yet again

[Piotr Tarsa]

I'm rewriting TarsaLZP once again. Shelwien recently told that there is rather a scarcity of coders written in managed/ dynamic languages, so I'd come up with an idea to rewrite TarsaLZP in several languages. For now I'm rewriting it once again in Java, but I plan to do JavaScript (for Google V8 at least) version shortly, after the Java version is at least roughly polished.

I've published the project on GitHub: https://github.com/tarsa/TarsaLZP and current snapshot compile is in attachment. Small tip: if you set lzpLowContextLength = lzpHighContextLength and lzpLowMaskSize = lzpHighMaskSize then program will create only one model. GUI version has more information currently (some of it is in tooltips) than CLI version, so I recommend playing with GUI version before playing with CLI version.

Suggestions and constructive criticism is welcomed. Particularly I'm interested in suggestions how to do command line interface, as I haven't done any serious CLI before. Source code is not commented right now, but I plan to change it when project will mature a bit.

[Shelwien]

Maybe you'd want to add this:

tenc.bat:
 @echo off
 java -Xmx1400m -jar TarsaLZP.jar encode fi=%1 fo=%2 %3 %4 %5 %6 %7 %8 %9

tdec.bat
 @echo off
 java -Xmx1400m -jar TarsaLZP.jar decode fi=%1 fo=%2 %3 %4 %5 %6 %7 %8 %9

Example:
 tenc.bat BOOK1 x
 tdec.bat x y

Btw, more than 1400m doesn't work on my XP.

[Piotr Tarsa]

Thanks for the scripts.

Do you have 64-bit Java? Newest 64-bit Java 7 update should provide best speed.

[Piotr Tarsa]

Slightly off-topic question:

I've studied http://compression.ru/sh/coders6a.rar a bit and in shcoder.cdr there is something like that:

     range <<= 8;
//     range = (range<<8)+255;

Such rescaling is only present in shcoder.cdr and it is additionally commented. I've tried addind 255 after shifting left by 8 in my shindlet-like coder but it resulted in broken files. Why adding 255 should or shouldn't work in different coder types?

[Shelwien]

range shift like that can be used if you keep actual_range-1 in the range variable.
In theory it can slightly improve precision, because normally we can't store 2^32 in a 32-bit range var.
But we can store 2^32-1 and do freq*range as freq*range+freq, etc.

In practice, there's no sense in this usually (it doesn't even save one byte), but
it may be useful if you want to encode unmodified input with a rangecoder -
normally even if you'd set all symbol probabilities to 1/256, the output would
be still slightly garbled.

And btw, as to your coder, I think its more interesting to port it to C/C++ first.

[Piotr Tarsa]

Just to let you know that the project isn't dead: I've managed to produce a working JavaScript port. I need to polish it a bit more before publishing on GitHub, but I'm attaching here a preview version. It will work correctly only in Chrome browser and will work best in 64-bit Chrome, because 32-bit version has low memory limits. Should produce files that are bit-identical to those produced by Java version - if not, then there's a bug.

[Piotr Tarsa]

I have pushed the Javascript version to repository and also done a Python port which also is in the repository. The Javascript version should now work in Opera and Firefox too (earlier it worked only under Chrome). Maybe even Interner Explorer 9, but I haven't tested that.

I haven't done thorough tests, but I have some rough timings for encoding enwik8:
- Java: 17 secs
- JavaScript: 120 secs
- Python (PyPy): 190 secs
- Python (CPython): 2900 secs

Tested under:
- Oracle JDK 7 update 9,
- Chrome 23,
- PyPy 1.9.0
- CPython 2.7.3

All tests done on Ubuntu 12.04 64-bit, Core 2 Duo E8400 3 GHz, DDR2 1000 MHz CL5 8 GiB. All versions produce bit identical files when given bit identical inputs and the same options.


I'm working now on a C version.

[Matt Mahoney]

Interesting. I think C will be the fastest.

[Black_Fox]

- Python (PyPy): 190 secs
- Python (CPython): 2900 secs

Is there any chance ShedSkin would work too?

[thometal]

could you test vala ( http://en.wikipedia.org/wiki/Vala_%2...ng_language%29 )as programming language also? It may very interesting how it compare to c and java.

[Piotr Tarsa]

Matt:
This is to be expected :]

Black_Fox:
I had to change code a little, but I failed to come up with translatable solution. I ended up with a code that I've attached to this post. The problem is with IO - read() method return a string instead of an byte array and I don't know how to overcome that.

I don't even know if I'm doing I/O properly in my Python implementations. If some Python expert could look at code and detect some unnecessary overhead (like using a text I/O sometimes instead of binary I/O exclusively) then I would be glad.

thometal:
Isn't vala a superset of C? If so, then it should be very comparable in performance, because if I feed the vala compiler with slightly modified (or even completely unmodified) then no performance should be lost in translation back to strict C.

[Black_Fox]

I had to change code a little, but I failed to come up with translatable solution. I ended up with a code that I've attached to this post. The problem is with IO - read() method return a string instead of an byte array and I don't know how to overcome that.

Sorry, I don't know how to code in Python, cannot help

Isn't vala a superset of C?

Vala seems to me as a C language superset suited for developing in GNOME/GTK ecosystem with C# syntax, so I'd say yes. But if there's anyone already skilled enough, there's another rather exotic language - Rust (which aims to be around C++ performance-wise).

[thometal]

Vala isnt a subset of c, it just uses the gobject lib to generate c, so you will be able to program in a high level language with good performance, so far i know vala is something c|c++ <= c#|java but not sure. but iam interessted in benachmarks because i think it would be c/c++ equal but fast than java but how fast?

[Piotr Tarsa]

Black_Fox:
I am thinking of popular languages, exotic ones aren't well supported. I thought of Haskell, but my algorithm is purely imperative and imperative Haskell is a bad thing :P I'll probably do a Ruby and Scala port, but I'll wait for JDK8 Developer Preview first - on JRuby site, its devs are saying that JDK8 has improved invokedynamic implementation, so that should provide a performance boost for JRuby. Scala does some bytecode optimization in the process of compiling so it wouldn't be a terrible surprise if Scala code would end up faster than Java code.

On the other hand, nowadays it's relatively easy to develop a high performance compiler for own programming language by just implementing a frontend to e.g. LLVM/ GCC and LLVM/ GCC will do all the heavy optimization work.

thometal:
I wrote superset, not subset. In other words: I meant that any C program could probably be changed a little to become a valid Vala program. Therefore I would expect very similiar performance after small modifications.

[Matt Mahoney]

Who programs in Vala?

[thometal]

me if i would program very time critical things =P) because i dont wanna fight against pointers und cryptic compiler output =P but look https://live.gnome.org/Vala/Document...eloped_in_Vala

[m^2]

I had to change code a little, but I failed to come up with translatable solution. I ended up with a code that I've attached to this post. The problem is with IO - read() method return a string instead of an byte array and I don't know how to overcome that.

I don't even know if I'm doing I/O properly in my Python implementations. If some Python expert could look at code and detect some unnecessary overhead (like using a text I/O sometimes instead of binary I/O exclusively) then I would be glad.

array.fromfile and tofile allow you to read/write a file directly.
BTW, I notice that you have pyc, but not pyo files. This suggests that you run w/out optimisation. Use -OO switch when using CPython.
Also, if your code is Python 2, it's better to use xrange instead of range.
Though I'm not an expert, it's likely that I miss a lot.

[m^2]

Also, could you try Jython too?

[Piotr Tarsa]

Though I'm not an expert, it's likely that I miss a lot.

But your hints are valuable

As to Jython, I'll try. However, you're free to try yourself.


Today I've made a working C port. It's not polished yet, but is seems to work, at least on enwik8.


C version is much faster, not far off of twice as fast as Java version. Previously I've timed using built-in timers, now I've measured time with "time" utility from GNU/Linux.

C version:

time dist/Release/GNU-Linux-x86/tarsalzp encode fi=/home/piotrek/datacomp/enwik/enwik8 fo=/home/piotrek/Pulpit/clzp
TarsaLZP
Author: Piotr Tarsa

Completed!

real	0m13.392s
user	0m12.909s
sys	0m0.304s

Java version:

time java -jar dist/TarsaLZP.jar encode fi=/home/piotrek/datacomp/enwik/enwik8 fo=/home/piotrek/Pulpit/javalzp
TarsaLZP
Author: Piotr Tarsa

Completed!

real	0m21.528s
user	0m21.045s
sys	0m0.264s

Tommorow I'll try to add prefetching. If it pan out, then C version should be twice as fast as Java version on enwik8. I'll have to test both versions on enwik9 too as I suspect that on enwik8 the results aren't very meaningful - JITing takes some time, so with enwik9 the overhead of compiling at runtime should be minimized.

C version is attached (sources + makefile + Linux 64-bit binaries).

[Piotr Tarsa]

Today I've made a new C version, this time I've fixed bugs in command line parsing and added prefetching that actually works, but only on encoding.

Compile with -std=c99 -O3 -march=native -DGCC_PREFETCH and preferably for 64-bit architecture.

Encoding without prefetching:

piotrek@p5q-pro:~/NetBeansProjects/TarsaLZP$ time dist/Release/GNU-Linux-x86/tarsalzp encode fi=/home/piotrek/datacomp/enwik/enwik8 fo=/home/piotrek/Pulpit/clzp lzpLowMaskSize=25 lzpHighMaskSize=30
TarsaLZP
Author: Piotr Tarsa

Completed!

real	0m17.219s
user	0m15.905s
sys	0m1.192s

Encoding with prefetching:

piotrek@p5q-pro:~/NetBeansProjects/TarsaLZP$ time dist/ReleaseP/GNU-Linux-x86/tarsalzp encode fi=/home/piotrek/datacomp/enwik/enwik8 fo=/home/piotrek/Pulpit/clzp lzpLowMaskSize=25 lzpHighMaskSize=30
TarsaLZP
Author: Piotr Tarsa

Completed!

real	0m12.259s
user	0m10.853s
sys	0m1.220s

Decoding - without prefetching, as prefetching didn't work in that case:

piotrek@p5q-pro:~/NetBeansProjects/TarsaLZP$ time dist/ReleaseP/GNU-Linux-x86/tarsalzp decode fi=/home/piotrek/Pulpit/clzp fo=/home/piotrek/Pulpit/cdec
TarsaLZP
Author: Piotr Tarsa

Completed!

real	0m18.830s
user	0m17.397s
sys	0m1.252s

As to options, program should tell about available options and their default values. If you're curious what are valid options there's validation function:

bool optionsValid() {
        return lzpLowContextLength > ppmOrder
                && lzpLowContextLength <= lzpHighContextLength
                && lzpHighContextLength <= 8
                && lzpLowMaskSize >= 15
                && lzpLowMaskSize <= 30
                && lzpHighMaskSize >= 15
                && lzpHighMaskSize <= 30
                && ppmOrder >= 1
                && ppmOrder <= 2
                && ppmInit >= 1
                && ppmInit <= 127
                && ppmStep >= 1
                && ppmStep <= 127
                && ppmLimit >= ppmInit * 256
                && ppmLimit <= 32767 - ppmStep;
    }

Guidance for setting options:
In general increasing *MaskSize always helps, but memory usage grows exponentially with that parameters. For example if you set lzpHighMaskSize to 30, then high LZP model will consume 2^30 uint16_t's, ie 2 GiB of memory. Context lengths are tuned for enwik8/ enwik9, probably for less compressible files lower values would be better. ppmOrder on small files (far below one megabyte) probably should be set to 1. For incompressible files set ppmInit to some relatively high value, like 60 and set ppmStep to something lower, like 20.

If you set lzpLowMaskSize == lzpHighMaskSize and lzpLowContextLength == lzpHighContextLength then effectively there will be one LZP model and program should work faster.

[Nania Francesco]

Hi Piotr, there is so much that we felt, always a great and fantastic job. I think that is a great compressor TarsaLZP PPM + LZP but that must be corrected with files that contain a strong entropy. Just insert a simple parser to entropy and optionally copy data directly by imposing a neutral probabilities.

[Piotr Tarsa]

I have pushed a new Python version to repository. It's now translatable by ShedSkin to C++ without worrying warnings (ie. ShedSkin complaints that two functions aren't used but I assume that this can be safely ignored). Unfortunately, running 'make' in directory with generated C++ sources yields a lot of errors from the G++ compiler, due to weird errors introduced by ShedSkin during translation.

Changing from range to xrange doesn't make any visible change with PyPy.

If someone is a Python fan (I'm surely not a Python fan) then he can investigate the problem with ShedSkin and compare various Python implementations. Also please note that the Python implementation may be somewhat suboptimal, eg with respect to Long class which is used as an emulation of 8 byte array (field context of class Common). But Python version is very comparable to JavaScript one and even then Chrome yields noticeably better performance that PyPy.


Francesco:
I understand. If I insert the heuristics to detect incompressible sequences then I would want to employ some on-line algorithm, ie decide before encoding of every byte if I should encode it using order -1 or order 2. I'll think about it.


PS:
-OO doesn't seem to bring any speedup for CPython.

[Piotr Tarsa]

Yet another C version.

By Francesco's request, I've made a simple cost estimator that I use to skip compression of incompressible sequences. Also I've added SIMD optimizations in the encoder.

Compile with:
gcc -march=native -O3 -DGCC_PREFETCH -DGCC_SSE -std=c99



Edit:
Tested on enwik9. Compiled with options above, under Ubuntu 12.04 64-bit, Core 2 Duo E8400 @ stock, RAM 8 GiB DDR2 @ 1000 MHz:

piotrek@p5q-pro:/tmp/lzp$ time ~/NetBeansProjects/TarsaLZP/dist/ReleaseG/GNU-Linux-x86/tarsalzp encode fi=~/corpora/enwik/enwik9 fo=out lzpLowMaskSize=25 lzpHighMaskSize=30 && ls -al
TarsaLZP
Author: Piotr Tarsa

Completed!

real	1m35.956s
user	1m32.754s
sys	0m2.360s
razem 203508
drwxrwxr-x  2 piotrek piotrek      4096 lis 18 15:38 .
drwxrwxrwt 15 root    root         4096 lis 18 15:38 ..
-rw-rw-r--  1 piotrek piotrek 208382864 lis 18 15:40 out
piotrek@p5q-pro:/tmp/lzp$ time ~/NetBeansProjects/TarsaLZP/dist/ReleaseG/GNU-Linux-x86/tarsalzp decode fi=out | md5sum
TarsaLZP
Author: Piotr Tarsa

Completed!
e206c3450ac99950df65bf70ef61a12d  -

real	2m28.199s
user	2m28.069s
sys	0m2.412s

Memory usage was about 2.1 GiB.

[Nania Francesco]

Yet another C version.

By Francesco's request, I've made a simple cost estimator that I use to skip compression of incompressible sequences. Also I've added SIMD optimizations in the encoder.

Compile with:
gcc -march=native -O3 -DGCC_PREFETCH -DGCC_SSE -std=c99



Edit:
Tested on enwik9. Compiled with options above, under Ubuntu 12.04 64-bit, Core 2 Duo E8400 @ stock, RAM 8 GiB DDR2 @ 1000 MHz:

piotrek@p5q-pro:/tmp/lzp$ time ~/NetBeansProjects/TarsaLZP/dist/ReleaseG/GNU-Linux-x86/tarsalzp encode fi=~/corpora/enwik/enwik9 fo=out lzpLowMaskSize=25 lzpHighMaskSize=30 && ls -al
TarsaLZP
Author: Piotr Tarsa

Completed!

real	1m35.956s
user	1m32.754s
sys	0m2.360s
razem 203508
drwxrwxr-x  2 piotrek piotrek      4096 lis 18 15:38 .
drwxrwxrwt 15 root    root         4096 lis 18 15:38 ..
-rw-rw-r--  1 piotrek piotrek 208382864 lis 18 15:40 out
piotrek@p5q-pro:/tmp/lzp$ time ~/NetBeansProjects/TarsaLZP/dist/ReleaseG/GNU-Linux-x86/tarsalzp decode fi=out | md5sum
TarsaLZP
Author: Piotr Tarsa

Completed!
e206c3450ac99950df65bf70ef61a12d  -

real	2m28.199s
user	2m28.069s
sys	0m2.412s

Memory usage was about 2.1 GiB.

Piotr can't wait to test the program at WCC but I must point out that the program gives error in some file (A10.JPG for example).
The results seem to be pretty interesting I must say.
Hi !

[Piotr Tarsa]

What kind of error? A10.jpg is encoded and decoded without problem on my system and the decoded output is identical to source.

[Nania Francesco]

What kind of error? A10.jpg is encoded and decoded without problem on my system and the decoded output is identical to source.

The length of the source file is different from that of the decompressed file and the file does not open, for example from windows. Try the dos command "comp source dest".

I compiled out the online version with Codebloks and Gcc 4.6.1

You can put online your compiled version.

[Piotr Tarsa]

Ouch, I have only Linux binaries. Installing a programming environment on Windows would take some time. I'll try to do that however. It would be also nice if someone other could test the program on Windows in the meantime.

BTW:
Does the program say "Completed!" at the end all the time? If it says something else then copy the message here.

[Bulat Ziganshin]

Piotr, you need the usual trick:

#include <io.h>

#include <fcntl.h>



#ifdef _WIN32

    setmode (fileno(stdin), O_BINARY);

    setmode (fileno(stdout),O_BINARY);

#endif

[Piotr Tarsa]

Thanks Bulat. I assume I should do that on the beginning. On my Linux system my IDE doesn't see <io.h> file so I've enclosed that with #ifdef also. I've also added some more diagnostic messages.

PS:
I'm using fopen(filename, "rb") to open input files and fopen(filename, "wb") to open output files. Do I need to use setmode on the opened files also?

[Bulat Ziganshin]

no. probably Nania employes stdin/stdout in his testing

also i see that you don't check malloc() results. 32-bit windows system may be unable to alloc 1.9gb to single program