"Implementing ppmc with hash tables"

[RichSelian]

I've just read this article by Arturo San Emeterio Campos and made a working order-4-2-1-0-(-1) implementation (https://github.com/richox/slimox), but I found it even slower than high order PPMd. Does a hash table implementation always perform worse than one based on context trie, or do I misunderstand something?

[Piotr Tarsa]

Order-2 and lower ones could be implemented with direct lookup. Higher orders generally needs hashing, but you can hide some memory latency by using prefetching.

Trees probably uses cache more effectively, especially when you do context mixing.

[Cyan]

Yes, large hash table typically cost a lot in term of cache misses. Likely culprit.

[RichSelian]

Order-2 and lower ones could be implemented with direct lookup. Higher orders generally needs hashing, but you can hide some memory latency by using prefetching.

Trees probably uses cache more effectively, especially when you do context mixing.

I've read your TarsaLZP code and saw that trick (but I got SegmentFault when prefetching enabled ), now I'm thinking of running arithmetic coder in another thread

[Piotr Tarsa]

What CPU do you have? Prefetching shouldn't cause SegFaults even if one tries to prefetch inaccessible piece of memory. But prefetching can cause bad opcode/ unrecognized instruction when CPU doesn't support prefetching (in this case, prefetching requires CPU with SSE2).

Arithmetic coder in another thread could help at encoding, where you can delay encoding until you have a sufficiently large batch of symbols to encode. At decoding you would need the threads synchronized and synchronization is costly on common CPUs.

[RichSelian]

What CPU do you have? Prefetching shouldn't cause SegFaults even if one tries to prefetch inaccessible piece of memory. But prefetching can cause bad opcode/ unrecognized instruction when CPU doesn't support prefetching (in this case, prefetching requires CPU with SSE2).

Arithmetic coder in another thread could help at encoding, where you can delay encoding until you have a sufficiently large batch of symbols to encode. At decoding you would need the threads synchronized and synchronization is costly on common CPUs.

I downloaded this version: http://encode.su/attachment.php?atta...5&d=1353267497

compiled with these options:
gcc -std=c99 -msse2 -O3 main.c -o tarsalzp (completed)
gcc -std=c99 -msse2 -O3 main.c -DGCC_SSE -o tarsalzp (completed)
gcc -std=c99 -msse2 -O3 main.c -DGCC_PREFETCH -o tarsalzp (completed)
gcc -std=c99 -msse2 -O3 main.c -DGCC_PREFETCH -DGCC_SSE -o tarsalzp (segment fault)

Running on archlinux-i686, gcc-4.7.2, CPU: AMD-E350 1.6GHz

It's very strange that when I debug with valgrind no error happened and compression completed, but running it directly leads to segment fault.

[RichSelian]

gdb alsa complained with SEGSIGV at encodeSymbol (nextSymbol=nextSymbol@entry=127, mispredictedSymbol=mispredictedSymbol@entry=181) at encoder.h:157

b.m = __builtin_ia32_pand128(b.m, c.m);

[Piotr Tarsa]

Very strange indeed. For now I don't have an idea on what could go wrong. I have a netbook with the same CPU so I may be able to debug it if it will occur to me.

[Piotr Tarsa]

I have tested both most recent version and the version you've linked and it seems that everything works correctly when I test on maximumcompression.com's test files.

I'm running netbook with AMD E-350 1.6 GHz (the same as yours), Ubuntu 12.04 64-bit, 64-bit compiles (compiler was complaining about missing bits/predefs.h or smth like that when I chose 32-bit compilation) and both vector and prefetch optimizations turned on.


The project is a NetBeans project, so you could download NetBeans (version 7.2 or newer) and Ubuntu 12.04 64-bit LiveCD to replicate my environment and then compile (from NetBeans) and test the program again. There are NetBeans configurations for either enabling or disabling of SSE optimizations.