ot

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.

> 512GB is a huge block size for bzip3

Sorry! That was a typo, it should have been 512MB (now fixed). Still huge.

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.