lz4 speed sudden changes

[smjohn1]

Not sure if people here have noticed, lz4's compression and decompression speeds change dramatically at block size 64KB. Cannot figure out the reason(s). Any thoughts?

Here are some simple tests on an Intel(R) Xeon(R) CPU E3-1220 v5 @ 3.00GHz, running Red Hat Enterprise Linux Server release 6.10 (kernel 2.6.32). Granted, it is a quite old machine. Not sure if newer machines will have the same results:

vigeland -19- <~> lz4 -b1 enwik8
1#enwik8 : 100000000 -> 57262281 (1.746), 327.9 MB/s ,3000.0 MB/s

vigeland -20- <~> lz4 -b1 -B7 enwik8
using blocks of size 4096 KB
1#enwik8 : 100000000 -> 57285873 (1.746), 333.3 MB/s ,3000.0 MB/s

vigeland -21- <~> lz4 -b1 -B6 enwik8
using blocks of size 1024 KB
1#enwik8 : 100000000 -> 57358020 (1.743), 333.3 MB/s ,3000.0 MB/s

vigeland -22- <~> lz4 -b1 -B5 enwik8
using blocks of size 256 KB
1#enwik8 : 100000000 -> 57645644 (1.735), 330.6 MB/s ,2916.7 MB/s

vigeland -23- <~> lz4 -b1 -B4 enwik8
using blocks of size 64 KB
1#enwik8 : 100000000 -> 57001007 (1.754), 285.7 MB/s ,2307.7 MB/s

As can be seen from the above results, compression ratio doesn't change much for various block sizes, but both compression and decompression speeds decrease a lot at block size 64KB.

Any convincing explanations?

[Cyan]

`lz4` (fast mode) will consider smaller match lengths when presented with a "small" input.
Small being defined as <= 64 KB.

This helps compression ratio, but at the expense of some speed.

Exact differences vary depending on file content,
with `enwik` being a rather extreme example, as it contains a lot of overlapping tiny matches.
Most other data sources (binary, structured schema) are different, with typically fewer but larger matches.
In these other cases, the difference is less pronounced.

[smjohn1]

OK, but this should only affect compression speed, not decompression speed, as decompression doesn't care whether matches are small or not. Correct?

Also where exactly are the lines of "consider smaller match lengths when presented with a "small" input" in v1.9.2? I like to see what happens if these lines are removed or changed?

Thanks.

`lz4` (fast mode) will consider smaller match lengths when presented with a "small" input.
Small being defined as <= 64 KB.

This helps compression ratio, but at the expense of some speed.

Exact differences vary depending on file content,
with `enwik` being a rather extreme example, as it contains a lot of overlapping tiny matches.
Most other data sources (binary, structured schema) are different, with typically fewer but larger matches.
In these other cases, the difference is less pronounced.

[Cyan]

decompression doesn't care whether matches are small or not. Correct?

Nope, incorrect

where exactly are the lines of "consider smaller match lengths when presented with a "small" input" in v1.9.2?

https://github.com/lz4/lz4/blob/dev/lib/lz4.c#L657

[smjohn1]

Nope, incorrect

Is it because recovering smaller (shorter) matches is slower than longer matches or literals?

https://github.com/lz4/lz4/blob/dev/lib/lz4.c#L657

Thanks, for enwik8, compression ratio improves as well, from 1.754 to 1.775, beside the decompression speed. Will check with more files.