Possible Search Improvement

[klauspost]

Is your feature request related to a problem? Please describe.

In my Go Zstd Compressor I have found an alternate search method that gives good improvements in cases where multiple candidates are searched and checked for match length.

In short the strategy is to use the current search strategy and when there is a match calculate a hash starting at input[match_start + match_length]. This will give a hash that can potentially continue the current match.

To check if the new match is better, the (offset_at_hash - match_len) is simply checked and scored as a regular candidate. In the linked code I also check the previous match offset and I've found that to also give a good improvement, mainly in machine generated data (JSON, CSV, marshalled data).

I've found that even with many candidates checked this can still yield good improvements that are worth the cost. I don't know if this has been tried+rejected, but I thought I would forward my findings.

Describe the solution you'd like

This could possibly fit in the lazy matcher, where it would take the best found match and check if the end-of-match can give a better result.

[Cyan4973]

Thanks @klauspost, I believe it's a good idea,
and if I understand it correctly, a similar implementation currently exists in lz4hc (albeit in 2 fairly different variants).

The same idea has been attempted in the past with zstd, but did not end up being beneficial enough.
It was a surprising outcome.
Back then, the tentative explanation was that this strategy was probably valid with long chains of candidates, i.e. high compression modes.
Thing is, in zstd, we don't reach that condition, because when the nb of searches becomes too large, we then switch to a binary tree.
And the binary tree is not compatible with this technique.

That being said, in the next release, we are updating the lazy match finder in a big way, thanks to @senhuang42 latest rowhash PR.
This is a large enough change for a release, so on short term, we won't add more complexity on top of it.

But the thing is, I suspect the described technique could end up being a good fit for the new data layout.
In which case, it would prove a good complement, and could push the rowhash territory even further into higher compression modes, thus grabbing a few slots from the binary tree implementation.

This remains to be implemented and tested though.
I would tentatively expect such experiment to happen later this year (H2 2021).

[klauspost]

@Cyan4973 Thanks! Yes, it depends a lot on the search strategy whether it is a benefit.

I mostly found it a benefit for middle-ish cases (levels 5-12 ish) when you don't search too far back (in the chain) and you only check one or two bytes ahead on a match for a better one. For faster modes I only rarely, if at all check the match length similar to your dfast.

You are correct, the improvements aren't as great on 'old-school' datasets (10gb.tar, enwik9, silecia). But with the amount of machine generated data being compressed I have personally put those a bit aside for machine generated datasets (JSON, CSV, msgpack & other serialized data) where the tradeoff is much more in favor.

Anyway, just wanted to add this info in case it could be useful.

[chelsinchaos]

@Cyan4973 & @klauspost I can confirm the improved performance improvements of the <index+match_length> search method proposed here. My company has been using this search step as our first pass on our encoder for a little over three years now. It works particularly well on M2M and serialized data as @klauspost mentions and does lack significantly on the corpus data sets.

Here is a link to a screenshot of the single pass (just <index+match_length>) run on a couple hundred TDMS files generated from some autonomous vehicles: https://drive.google.com/file/d/1yWQmmyDOfOg3-JhDCKRRoT0BSADYhOQn/view?usp=sharing