Improves compression ratio for small windowLog #1624
Conversation
noticeably improves compression ratio when window size is small (< 18). enwik7 level 19 windowLog `dev` `smallwlog` improvement 23 3.577 3.577 0.02% 22 3.536 3.538 0.06% 21 3.462 3.467 0.14% 20 3.364 3.377 0.39% 19 3.244 3.272 0.86% 18 3.110 3.166 1.80% 17 2.843 3.057 7.53% 16 2.724 2.943 8.04% 15 2.594 2.822 8.79% 14 2.456 2.686 9.36% 13 2.312 2.523 9.13% 12 2.162 2.361 9.20% 11 2.003 2.182 8.94%
fast mode does the same thing as before : it pre-emptively invalidates any index that could lead to offset > maxDistance. It's supposed to help speed. But this logic is performed inside zstd_fast, so that other strategies can select a different behavior.
apparently not guaranteed on all platforms, replaced by UINT_MAX.
There was a problem hiding this comment.
I see ZSTD_window_enforceMaxDist() is also used in zstd_ldm.c. Do you plan to extend this modification to that compressor? I guess the large-window nature of LDM makes this probably not valuable for ratio purposes. But it still might be nice to bring it into alignment so we can remove ZSTD_window_enforceMaxDist() entirely?
The other thing I'm wondering about is the forceWindow option. Does this remove the incompatibility between forceWindow and attachDict? My sense is that it does. I guess we can merge this and I can then experiment with removing that exclusion.
|
Indeed, I intentionally left I think it can still be achieved as an improvement over this patch.
I'm not sure, this consequence does not look obvious to me. |
To ensure that all detected matches remain within window size,
the current strategy is to preemptively invalidate all indexes
that could end up being too far while compressing next block.
This is good for speed, as checking if a match is within distance is now a trivial comparison.
This roughly invalidates one block worth of data, which is about 128 KB.
It's then progressively restored as compression progress through the block. But temporarily, the window size has been truncated by up to 128 KB.
This is bad for compression ratio, but the impact is low, as long as the window size is large, relative to the block size.
As the window size is reduced, this is no longer the case.
Especially when
wlog <= 17, the window size is now equal to the block size. Hence, this strategy invalidates all history before each block (assuming each block is full), making each block effectively independent. This has a big impact on compression ratio.In this patch, the logic is changed so that each strategy selects how to best deal with maximum offset distance, aka, the window size.
Logic for
fastanddouble_fastis unchanged, as these single-probe strategies want to spend very little time per attempt.Logic for all strategies >=
greedyis modified, to accepts all candidates, up to maximum window size. This makes them more effective in combination with small window sizes.Example on
enwik7at level19:devAs expected, improvement increases as window size decreases. It's negligible at
wlog = 23, then roughly doubles with each reduction ofwlog.On reaching
wlog = 17, there is a visible bump. After that, the gain stabilize around +8-9%, which is quite significant.