[libzstd] Optimize ZSTD_insertBt1() for repetitive data #1635
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
We would only skip at most 192 bytes at a time before this diff. This was added to optimize long matches and skip the middle of the match. However, it doesn't handle the case of repetitive data. This patch keeps the optimization, but also handles repetitive data by taking the max of the two return values. ``` > for n in $(seq 9); do echo strategy=$n; dd status=none if=/dev/zero bs=1024k count=1000 | command time -f %U ./zstd --zstd=strategy=$n >/dev/null; done strategy=1 0.27 strategy=2 0.23 strategy=3 0.27 strategy=4 0.43 strategy=5 0.56 strategy=6 0.43 strategy=7 0.34 strategy=8 0.34 strategy=9 0.35 ``` At level 19 with multithreading the compressed size of `silesia.tar` regresses 300 bytes, and `enwik8` regresses 100 bytes. In single threaded mode `enwik8` is also within 100 bytes, and I didn't test `silesia.tar`. Fixes Issue facebook#1634.
Cyan4973
approved these changes
Jun 6, 2019
Merged
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
We would only skip at most 192 bytes at a time before this diff.
This was added to optimize long matches and skip the middle of the
match. However, it doesn't handle the case of repetitive data.
This patch keeps the optimization, but also handles repetitive data
by taking the max of the two return values.
Before:
After:
At level 19 with multithreading the compressed size of
silesia.tarregresses 300 bytes, andenwik8regresses 100 bytes. In single threaded modeenwik8is also within 100 bytes, and I didn't testsilesia.tar. The compression speed is not significantly effected.The regression tests show changes in the order of single digit number of bytes.
Fixes Issue #1634.