Originally Posted by

**Cyan**
It requires the decoder to build the same table

True, but it's not true for LZRW1 and LZRW1-a, which are simple LZSS.

Originally Posted by

**Cyan**
but is fairly fast and efficient on the compression side.

It's not efficient for decompression (look at QuickLZ results which encodes an index to a hash table). I was not able to get even 300 MB/s with something similar to LZRW2+. But with LZSS I can get decompression speed up to 700 MB/s with just one core (look also at decompression speed of Snappy or LZF).

In-memory test (compression and decompression) with ENWIK8 using 1 core of Athlon X4 2.8 GHz (32-bit compilation under gcc 4.5.2 (MinGW) -O3 -fomit-frame-pointer -fstrict-aliasing -fforce-addr -ffast-math --param inline-unit-growth=999 -DNDEBUG):

Code:

lzjb 2010 = 842 ms (115 MB/s), 100000000 -> 68711273, 410 ms (238 MB/s)
lzo 2.04 1x = 964 ms (101 MB/s), 100000000 -> 53481944, 374 ms (261 MB/s)
fastlz 0.1 -1 = 614 ms (159 MB/s), 100000000 -> 55239233, 390 ms (250 MB/s)
fastlz 0.1 -2 = 723 ms (135 MB/s), 100000000 -> 54163013, 362 ms (269 MB/s)
lzf 3.6 vf = 738 ms (132 MB/s), 100000000 -> 53945381, 267 ms (365 MB/s)
lzf 3.6 uf = 667 ms (146 MB/s), 100000000 -> 57695415, 276 ms (353 MB/s)
lzrw1 = 891 ms (109 MB/s), 100000000 -> 59669043, 438 ms (222 MB/s)
lzrw1-a = 830 ms (117 MB/s), 100000000 -> 59448006, 372 ms (262 MB/s)
lzrw2 = 749 ms (130 MB/s), 100000000 -> 55312164, 464 ms (210 MB/s)
lzrw3 = 722 ms (135 MB/s), 100000000 -> 52468327, 488 ms (200 MB/s)
lzrw3-a = 1574 ms (62 MB/s), 100000000 -> 47874203, 484 ms (201 MB/s)
snappy 1.0 = 472 ms (206 MB/s), 100000000 -> 58350605, 199 ms (490 MB/s)
quicklz 1.5.0 -1 = 429 ms (227 MB/s), 100000000 -> 52334371, 381 ms (256 MB/s)
quicklz 1.5.0 -2 = 1140 ms (85 MB/s), 100000000 -> 45883075, 442 ms (220 MB/s)

Originally Posted by

**Cyan**
trying to find out which table size would be "optimal" for this scheme, i unsurprisingly concluded that such "optimal size" was different depending on the file to be compressed.

It's a common problem in compression e.g. choosing the optimal order for PPM.

Originally Posted by

**Cyan**
The question is : how to find this "optimal size", without brute-forcing all possibilities ?

1. Take into account a size of input data (bigger file size = bigger hash size).

2. You can brute-force only some part of data (e.g. 10% or 100 KB). If hash size = 2^13 you can try 2^12, 2^13, and 2^14. Then check results for 2^12 and 2^14 and go in a direction of a size which gives better compression.