Yann Collet [Fri, 31 Mar 2023 18:13:52 +0000 (11:13 -0700)]
fix decompression with -o writing into a block device
decompression features automatic support of sparse files,
aka a form of "compression" where entire blocks consists only of zeroes.
This only works for some compatible file systems (like ext4),
others simply ignore it (like afs).
Triggering this feature relies of `fseek()`.
But `fseek()` is not compatible with non-seekable devices, such as pipes.
Therefore it's disabled for pipes.
However, there are other objects which are not compatible with `fseek()`, such as block devices.
Changed the logic, so that `fseek()` (and therefore sparse write) is only automatically enabled on regular files.
Note that this automatic behavior can always be overridden by explicit commands `--sparse` and `--no-sparse`.
Yoni Gilad [Tue, 22 Mar 2022 16:24:09 +0000 (18:24 +0200)]
seekable_format: Add unit test for multiple decompress calls
This does the following:
1. Compress test data into multiple frames
2. Perform a series of small decompressions and seeks forward, checking
that compressed data wasn't reread unnecessarily.
3. Perform some seeks forward and backward to ensure correctness.
Yoni Gilad [Thu, 17 Feb 2022 17:46:29 +0000 (19:46 +0200)]
seekable_format: Prevent rereading frame when seeking forward
When decompressing a seekable file, if seeking forward within
a frame (by issuing multiple ZSTD_seekable_decompress calls
with a small gap between them), the frame will be unnecessarily
reread from the beginning. This patch makes it continue using
the current frame data and simply skip over the unneeded bytes.
Han Zhu [Tue, 28 Mar 2023 21:33:50 +0000 (14:33 -0700)]
Remove clang-only branch hints from ZSTD_decodeSequence
Looking at the __builtin_expect in ZSTD_decodeSequence:
{ size_t offset;
#if defined(__clang__)
if (LIKELY(ofBits > 1)) {
#else
if (ofBits > 1) {
#endif
ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
From profile-annotated assembly, the probability of ofBits > 1 is about 75%
(101k counts out of 135k counts). This is much smaller than the recommended
likelihood to use __builtin_expect which is 99%. As a result, clang moved the
else block further away which hurts cache locality. Removing this
__built_expect along with two others in ZSTD_decodeSequence gave better
performance when PGO is enabled. I suggest to remove these branch hints and
rely on PGO which leverages runtime profiles from actual workload to calculate
branch probability instead.
Han Zhu [Mon, 27 Mar 2023 22:57:55 +0000 (15:57 -0700)]
Inline BIT_reloadDStream
Inlining `BIT_reloadDStream` provided >3% decompression speed improvement for
clang PGO-optimized zstd binary, measured using the Silesia corpus with
compression level 1. The win comes from improved register allocation which leads
to fewer spills and reloads. Take a look at this comparison of
profile-annotated hot assembly before and after this change:
https://www.diffchecker.com/UjDGIyLz/. The diff is a bit messy, but notice three
fewer moves after inlining.
In general LLVM's register allocator works better when it can see more code. For
example, when the register allocator sees a call instruction, it partitions the
registers into caller registers and callee registers, and it is not free to do
whatever it wants with all the registers for the current function. Inlining the
callee lets the register allocation access all registers and use them more
flexsibly.
W. Felix Handte [Mon, 27 Mar 2023 15:24:47 +0000 (11:24 -0400)]
[contrib/pzstd] Detect and Select Maximum Available C++ Standard
Rather than remove the flag entirely, as proposed in #3499, this commit uses
the newest C++ standard the compiler supports. This retains the selection of
using only standardized features (excluding GNU extensions) and keeps the
recency requirements of the codebase explicit.
Tested with various versions of `g++` and `clang++`.
Tobias Hieta [Wed, 22 Mar 2023 21:13:57 +0000 (22:13 +0100)]
Disable linker flag detection on MSVC/ClangCL.
This fixes compilation with clang-cl on Windows. There
is a bug in cmake so that check_linker_flag() doesn't give
the correct result when using link.exe/lld-link.exe.
Details in CMake's gitlab: https://gitlab.kitware.com/cmake/cmake/-/issues/22023
Nick Terrell [Fri, 10 Mar 2023 01:26:07 +0000 (17:26 -0800)]
[lazy] Skip over incompressible data
Every 256 bytes the lazy match finders process without finding a match,
they will increase their step size by 1. So for bytes [0, 256) they search
every position, for bytes [256, 512) they search every other position,
and so on. However, they currently still insert every position into
their hash tables. This is different from fast & dfast, which only
insert the positions they search.
This PR changes that, so now after we've searched 2KB without finding
any matches, at which point we'll only be searching one in 9 positions,
we'll stop inserting every position, and only insert the positions we
search. The exact cutoff of 2KB isn't terribly important, I've just
selected a cutoff that is reasonably large, to minimize the impact on
"normal" data.
This PR only adds skipping to greedy, lazy, and lazy2, but does not
touch btlazy2.
The speed difference for clang at level 12 is real, but is probably
caused by some sort of alignment or codegen issues. clang is
significantly slower than gcc before this PR, but gets up to parity with
it.
I also measured the ratio difference for the HC match finder, and it
looks basically the same as the row-based match finder. The speedup on
random data looks similar. And performance is about neutral, without the
big difference at level 12 for either clang or gcc.
Peter Pentchev [Sat, 18 Mar 2023 20:32:42 +0000 (22:32 +0200)]
Fix a Python bytes/int mismatch in CLI tests
In Python 3.x, a single element of a bytes array is returned as
an integer number. Thus, NEWLINE is an int variable, and attempting
to add it to the line array will fail with a type mismatch error
that may be demonstrated as follows:
[roam@straylight ~]$ python3 -c 'b"hello" + b"\n"[0]'
Traceback (most recent call last):
File "<string>", line 1, in <module>
TypeError: can't concat int to bytes
[roam@straylight ~]$
Nick Terrell [Tue, 24 Jan 2023 20:21:49 +0000 (12:21 -0800)]
Deprecated bufferless and block level APIs
* Mark all bufferless and block level functions as deprecated
* Update documentation to suggest not using these functions
* Add `_deprecated()` wrappers for functions that we use internally and
call those instead
Yonatan Komornik [Mon, 13 Mar 2023 22:34:13 +0000 (15:34 -0700)]
Add salt into row hash (#3528 part 2) (#3533)
Part 2 of #3528
Adds hash salt that helps to avoid regressions where consecutive compressions use the same tag space with similar data (running zstd -b5e7 enwik8 -B128K reproduces this regression).
Yonatan Komornik [Mon, 13 Mar 2023 20:20:49 +0000 (13:20 -0700)]
Add init once memory (#3528) (#3529)
- Adds memory type that is guaranteed to have been initialized at least once in the workspace's lifetime.
- Changes tag space in row hash to be based on init once memory.
Yonatan Komornik [Mon, 13 Mar 2023 17:00:03 +0000 (10:00 -0700)]
[Bugfix] row hash tries to match position 0 (#3548)
#3543 decreases the size of the tagTable by a factor of 2, which requires using the first tag position in each row for head position instead of a tag.
Although position 0 stopped being a valid match, it still persisted in mask calculation resulting in the matches loops possibly terminating before it should have. The fix skips position 0 to solve this problem.
Yonatan Komornik [Fri, 10 Mar 2023 22:15:04 +0000 (14:15 -0800)]
Reduce RowHash's tag space size by x2 (#3543)
Allocate half the memory for tag space, which means that we get one less slot for an actual tag (needs to be used for next position index).
The results is a slight loss in compression ratio (up to 0.2%) and some regressions/improvements to speed depending on level and sample. In turn, we get to save 16% of the hash table's space (5 bytes per entry instead of 6 bytes per entry).
Yann Collet [Fri, 10 Mar 2023 01:48:35 +0000 (17:48 -0800)]
Improved seekable format ingestion speed for small frame size
As reported by @P-E-Meunier in https://github.com/facebook/zstd/issues/2662#issuecomment-1443836186,
seekable format ingestion speed can be particularly slow
when selected `FRAME_SIZE` is very small,
especially in combination with the recent row_hash compression mode.
The specific scenario mentioned was `pijul`,
using frame sizes of 256 bytes and level 10.
This is improved in this PR,
by providing approximate parameter adaptation to the compression process.
Tested locally on a M1 laptop,
ingestion of `enwik8` using `pijul` parameters
went from 35sec. (before this PR) to 2.5sec (with this PR).
For the specific corner case of a file full of zeroes,
this is even more pronounced, going from 45sec. to 0.5sec.
These benefits are unrelated to (and come on top of) other improvement efforts currently being made by @yoniko for the row_hash compression method specifically.
The `seekable_compress` test program has been updated to allows setting compression level,
in order to produce these performance results.
Current timeout is too small for some slower machines, e.g. most modern riscv64 boards,
where tests fail with the following diagnostics:
Traceback (most recent call last):
File "/usr/src/RPM/BUILD/zstd-1.5.4-alt2/tests/./cli-tests/run.py", line 734, in <module>
success = run_tests(tests, opts)
File "/usr/src/RPM/BUILD/zstd-1.5.4-alt2/tests/./cli-tests/run.py", line 601, in run_tests
tests[test_case.name] = test_case.run()
File "/usr/src/RPM/BUILD/zstd-1.5.4-alt2/tests/./cli-tests/run.py", line 285, in run
return self.analyze()
File "/usr/src/RPM/BUILD/zstd-1.5.4-alt2/tests/./cli-tests/run.py", line 275, in analyze
self._join_test()
File "/usr/src/RPM/BUILD/zstd-1.5.4-alt2/tests/./cli-tests/run.py", line 330, in _join_test
(stdout, stderr) = self._test_process.communicate(timeout=self._opts.timeout)
File "/usr/lib64/python3.10/subprocess.py", line 1154, in communicate
stdout, stderr = self._communicate(input, endtime, timeout)
File "/usr/lib64/python3.10/subprocess.py", line 2006, in _communicate
self._check_timeout(endtime, orig_timeout, stdout, stderr)
File "/usr/lib64/python3.10/subprocess.py", line 1198, in _check_timeout
raise TimeoutExpired(
subprocess.TimeoutExpired: Command '['/usr/src/RPM/BUILD/zstd-1.5.4-alt2/tests/cli-tests/compression/window-resize.sh']' timed out after 60 seconds
Nick Terrell [Tue, 7 Mar 2023 23:15:40 +0000 (15:15 -0800)]
Add ZSTD_set{C,F,}Params() helper functions
* Add ZSTD_setFParams() and ZSTD_setParams()
* Modify ZSTD_setCParams() to use ZSTD_setParameter() to avoid a second path setting parameters
* Add unit tests
* Update documentation to suggest using them to replace deprecated functions
Adds initialization of clevel to static cdict (#3525) (#3527)
- Initializes clevel in `ZSTD_CCtxParams_init`
- Adds CI workflow for msan fuzzers runs without optimization (`-O0`)
- Fixes Makefile to correctly pass on user defined `MOREFLAGS` and `FUZZER_FLAGS` in cases they have been overwritten
Nick Terrell [Wed, 22 Feb 2023 22:49:08 +0000 (14:49 -0800)]
[bug-fix] Fix rare corruption bug affecting the block splitter
The block splitter confuses sequences with literal length == 65536 that use a
repeat offset code. It interprets this as literal length == 0 when deciding the
meaning of the repeat offset, and corrupts the repeat offset history. This is
benign, merely causing suboptimal compression performance, if the confused
history is flushed before the end of the block, e.g. if there are 3 consecutive
non-repeat code sequences after the mistake. It also is only triggered if the
block splitter decided to split the block.
All that to say: This is a rare bug, and requires quite a few conditions to
trigger. However, the good news is that if you have a way to validate that the
decompressed data is correct, e.g. you've enabled zstd's checksum or have a
checksum elsewhere, the original data is very likely recoverable. So if you were
affected by this bug please reach out.
The fix is to remind the block splitter that the literal length is actually 64K.
The test case is a bit tricky to set up, but I've managed to reproduce the issue.
Thanks to @danlark1 for alerting us to the issue and providing us a reproducer!
Sutou Kouhei [Tue, 14 Feb 2023 21:38:50 +0000 (06:38 +0900)]
Don't require CMake 3.18 or later
fix #3500
CMake 3.18 or later was required by #3392. Because it uses
`CheckLinkerFlag`. But requiring CMake 3.18 or later is a bit
aggressive. Because Ubuntu 20.04 LTS still uses CMake 3.16.3:
https://packages.ubuntu.com/search?keywords=cmake
This change disables `-z noexecstack` check with old CMake. This will
not break any existing users. Because users who need `-z noexecstack`
must already use CMake 3.18 or later.
Yonatan Komornik [Tue, 14 Feb 2023 02:00:13 +0000 (18:00 -0800)]
CI workflow to test external compressors dependencies
Implemented CI workflow for testing compilation with external compressors and without them. This serves as a sanity check to avoid any code dependencies on libraries that may not always be present. (Reference: #3497 for a bug fix related to this issue.)
Yonatan Komornik [Sun, 12 Feb 2023 20:32:31 +0000 (12:32 -0800)]
Fix zstd-dll build missing dependencies (#3496)
* Fixes zstd-dll build (https://github.com/facebook/zstd/issues/3492):
- Adds pool.o and threading.o dependency to the zstd-dll target
- Moves custom allocation functions into header to avoid needing to add dependency on common.o
- Adds test target for zstd-dll
- Adds github workflow that buildis zstd-dll
projects / thirdparty / zstd.git / log
