facebook / facebook/zstd

Possible Search Improvement

オープン
#2,587 コメント 3 件 リアクション 3 件 担当者 0 名 GitHub で見る
optimization
主要言語
C
スター
27.9k
フォーク
2.6k
平均マージ
1日 3時間
マージ済み PR(30日)
8

説明

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

In my [Go Zstd Compressor](https://github.com/klauspost/compress/tree/master/zstd#zstd) I have found an [alternate search](https://github.com/klauspost/compress/pull/364) 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](https://github.com/facebook/zstd/blob/dev/lib/compress/zstd_lazy.c#L359), where it would take the best found match and check if the end-of-match can give a better result.

コントリビューションガイド

コントリビューションガイドを開く

評価

この issue はまだ評価されていません。

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。