O(1) doesn't mean constant, it means bounded by a constant. An algorithm can be faster with small n and converge to a horizontal asymptote as n goes to infinity, and it would still be O(1).
In a real machine there is no infinity, but hundreds of GBs of memory are "infinity enough" compared to the cache size [1]. So asymptotic analysis is still a decent model.
I'm surprised that even a CS professor confuses this.
[1] Ok if we want to be pedantic memory access is logarithmic due to the traversal of page tables, but you can use huge pages.
The benchmarks are disingenuous, to the point of looking cherry-picked. The block size for bzip3 is set to 512MB, but the window size for zstd is left to its default (8MB I believe for high levels). So in this corpus, which is made up of all versions of Perl source code concatenated, the window is too small to see all the identical files and just match them.
Also corpora made out of very long repetitions are pretty much the best case scenario for BWT-based compressors.
If we match the window size of zstd to that of bzip3 we get dramatically different results:
% gzcat *.gz | time zstd -T8 -16 | wc -c # baseline
2819113884
zstd -T8 -16 2054.50s user 3.47s system 783% cpu 4:22.80 total
% gzcat *.gz | time zstd -T8 -16 --long=29 | wc -c
196405076
zstd -T8 -16 --long=29 1083.06s user 2.41s system 783% cpu 2:18.55 total
Almost 15x smaller than the baseline, and more than 2x smaller than bzip3, also CPU time halves (since long matches are found earlier, so there's less work to do).
(the baseline number is slightly different because I don't have the exact Perl version set used by the author)
Also, in the benchmarks using lrzip, which would make the window size less relevant, zstd is not even compared.
> That always seemed annoying to me. They couldn't allocate 5 more bits somewhere to let the decompressor autodetect longer window sizes?
I believe this is just to prevent the decompressor from arbitrarily blowing up memory usage based on the input; I think if you want to accept long windows you can just always decompress with --long=63 regardless of whether the input needs it? (you will run out of RAM decompressing a long=63 file though of course)
These command line parameters change the maximum the decompressor will allow. It's 128 MiB by default in the command line decompressor; other uses (like the "zstd" content coding for HTTP in web browsers) use a lower limit of 8 MiB (see https://www.rfc-editor.org/rfc/rfc9659.html).
2^27 is 128 megabytes. How much RAM do you want the decompressor to have to allocate for every file? Especially since you can't tell, by looking only at the file size of a compressed file, how many bytes it will decompress to. You could read the file header, but if it's a malicious "zip bomb" type of file, the header could be lying.
If the header says the file is smaller than it really is, you've already allocated a small widow by the time you realize it lied, so it doesn't harm you here.
If the header says the file is bigger than it really is, it can get you to allocate a pointlessly large window. But if a large allocation is the goal, they can make the file actually decompress that big without affecting the compressed size. So lying is pointless.
I just tried a tar file of a git clone of the linux kernel sources where the most recent commit is 72c395024dac5e215136cbff793455f065603b06 (early Feb of this year). zstd -19 got a slightly smaller size (3582930348 bytes vs bz3 -b 511's 3597411687 bytes or 0.4% advantage to zstd). More significantly 4-core zstd decompression was 2.05 seconds vs a whopping 297 seconds for bzip3 -dj4 - 145x or over 2 orders of magnitude slower (about as much time to decode as to encode in the first place). bzip3 1.5.3 compiled with gcc-16.1.0. Granted, the .git objects are all compressed already and uncompressed tar-ball was only 5426667520 bytes, but even so...A lot of people care about fast(-ish) decompression. Maybe I did something wrong? Maybe `rm -rf .git` first would be a better benchmark?
This was my point too, but related to LZMA(2?) / xz, as the exact parameters were not specified while it supports setting compression level up to -9e, and the dictionary size can be controlled directly as well (in addition to quite a lot of fine-tuning knobs), increasing it up to 1536 MiB.
Can you tell me what the zstd invocation is that corresponds to the default invocation of bzip3, which uses block size 16 MiB (according to the man page)?
I got some really good results with bzip3 compression Wikipedia XML dumps, and I would like to check if it's actually better or if I was just calling zstd wrong.
If you want a 16MB window, use `--long=24` (2^24 is 16M). (I believe this is larger than the default window for zstd level 3, but smaller than the default window at higher compression levels.)
Wow, that is widely disingenuous, I don't really think there is any excuse for that, I don't believe someone deep in compression algorithms wouldn't know they could adjust the block size, and 512GB is a huge block size for bzip3, as it needs to basically all be in memory so you can't pretend that's just 'the standard value'.
> The present understanding is that the tale's moral supports team effort and recognition of the vital part that all members play in it. In more authoritarian times, however, the fable was taken to affirm direction from the centre.
Thanks, this is very useful. Reading it I was wondering how applications typically exploit the asymmetric fence, I hope the article you linked help in that regard.
I did a POC afterwards. For linux it was a bit PITA since /proc text had to be parsed to track context switches w/ associated full MB. For Mac OS on the ppc also bit PITA since Apple tried to hide their unix api and some stuff involved calling the mach micro kernel.
A weird, inscrutable project management tool for the shell written in Perl 4 and Guile Scheme, that the ten people in the world who learned to operate it swear it is the greatest piece of productivity software ever invented.
Well, I've got to admit I've haven't read HN using emacs. Is there such a .el thing avalabnle somewhere? It would be great to read HN as it was with usenet news. Not joking, that would be excellent tools I'd like to have !
Exactly. Being precise about logarithmic vs linear utilizations is key here. I tried making a similar point about the inefficiency of IEEE-754 redundant NaN encodings here: https://arxiv.org/pdf/2508.05621
Having ~a quadrillion redundant bitstrings all mapping to NaN sounds pretty bad, but logarithmic/information utilization-wise, this is actually not too bad.
I've been looking at the 8087 NaN circuitry lately. Having 2^53 (or whatever) values for NaN was supposedly a feature: "the large number of NAN values that are available, provide the sophisticated programmer with a tool that can be applied to a variety of special situations." For example, the different NaN values could hold debugging information to track down errors.
You'll see some scripting languages (ab)use this. Where the native "number" type is a 64 bit float and only one NaN bit pattern is a real NaN. The others smuggle a pointer to an object in the lower bits. This way you don't spend any memory overhead indicating if a given variable contains a primitive or an object.
That's a false dichotomy: you optimize both the application and the allocator.
A 0.5% improvement may not be a lot to you, but at hyperscaler scale it's well worth staffing a team to work on it, with the added benefit of having people on hand that can investigate subtle bugs and pathological perf behaviors.
exactly. I can think of at least 5 different projects I have been on where a better allocator would made a world of difference. I can also think of another 5 where it probably would have been a waste of time to even fiddle with.
One project I spent a bunch of time optimizing the write path of I/O. It was just using standard fwrite. But by staging items correctly it was an easy 10x speed win. Those optimizations sometimes stack up and count big. But it also had a few edges on it, so use with care.
In a real machine there is no infinity, but hundreds of GBs of memory are "infinity enough" compared to the cache size [1]. So asymptotic analysis is still a decent model.
I'm surprised that even a CS professor confuses this.
[1] Ok if we want to be pedantic memory access is logarithmic due to the traversal of page tables, but you can use huge pages.
reply