I wondered if it was possible to do anything more efficient than decompressing from the start of the file up to the point. It appears that the answer is no. However, on some CPUs (Skylake)
zcat | tail doesn't ramp the CPU up to full clock speed. See below. A custom decoder could avoid that problem and save the pipe write system calls, and maybe be ~10% faster. (Or ~60% faster on Skylake if you don't tweak power-management settings).
The best you could do with a customized zlib with a
skipbytes function would be to parse the symbols in a compression block to get to the end without doing the work of actually reconstructing the decompressed block. This could be significantly faster (probably at least 2x) than calling zlib's regular decode function to overwrite the same buffer and move forward in the file. But I don't know if anyone's written such a function. (And I think this doesn't actually work unless the file was written specially to allow the decoder to restart at a certain block).
I was hoping there was a way to skip through Deflate blocks without decoding them, because that would be much faster. The Huffman tree is sent at the start of each block, so you can decode from the start of any block (I think). Oh, I think the decoder state is more than the Huffman tree, it's also the previous 32kiB of decoded data, and this isn't reset / forgotten across block boundaries by default. The same bytes can keep being referenced repeatedly, so might only appear literally once in a giant compressed file. (e.g. in a log file, the hostname probably stays "hot" in the compression dictionary the whole time, and every instance of it references the previous one, not the first one).
zlib manual says you have to use
Z_FULL_FLUSH when calling
deflate if you want the compressed stream to be seekable to that point.
It "resets the compression state", so I think without that, backwards references can go into the previous block(s). So unless your zip file was written with occasional full-flush blocks (like every 1G or something would have negligible impact on compression), I think you would have to do more of the work of decoding up to the point you want than I was initially thinking. I guess you probably can't start at the start of any block.
The rest of this was written while I was thinking it would be possible to just find the start of the block containing the first byte you want, and decode from there.
But unfortunately, the start of a Deflate block doesn't indicate how long it is, for compressed blocks. Incompressible data can be coded with an uncompressed block type that has a 16-bit size in bytes at the front, but compressed blocks don't: RFC 1951 describes the format pretty readably. Blocks with dynamic Huffman coding have the tree at the front of the block (so the decompressor doesn't have to seek in the stream), so the compressor has to have kept the whole (compressed) block in memory before writing it.
The maximum backwards-reference distance is only 32kiB, so the compressor doesn't need to keep much uncompressed data in memory, but that doesn't limit the block size. Blocks can be multiple megabytes long. (This is large enough for disk seek to be worth it even on a magnetic drive, vs. sequential read into memory and just skipping data in RAM, if it was possible to find the end of the current block without parsing through it).
zlib makes blocks as long as possible:
According to Marc Adler, zlib only starts a new block when the symbol buffer fills up, which with the default setting is 16,383 symbols (literals or matches)
I gzipped the output of
seq (which is extremely redundant and thus probably not a great test), but
pv < /tmp/seq1G.gz | gzip -d | tail -c $((1024*1024*1000)) | wc -c on that runs at only ~62 MiB/s of compressed data on a Skylake i7-6700k at 3.9GHz, with DDR4-2666 RAM. That's 246MiB/s of decompressed data, which is chump change compared to
memcpy speed of ~12 GiB/s for block sizes too large to fit in cache.
energy_performance_preference set to the default
balance_power instead of
balance_performance, Skylake's internal CPU governor decides to only run at 2.7GHz, ~43 MiB /s of compressed data. I use
sudo sh -c 'for i in /sys/devices/system/cpu/cpufreq/policy[0-9]*/energy_performance_preference;do echo balance_performance > "$i";done' to tweak it. Probably such frequent system calls don't look like real CPU-bound work to the power-management unit.)
zcat | tail -c is CPU bound even on a fast CPU, unless you have very slow disks. gzip used 100% of the CPU it ran on (and ran 1.81 instructions per clock, according to
tail used 0.162 of the CPU it ran on (0.58 IPC). The system was otherwise mostly idle.
I'm using Linux 4.14.11-1-ARCH, which has KPTI enabled by default to work around Meltdown, so all those
write system calls in
gzip are more expensive than they used to be :/
Having the seek built-in to
zcat (but still using the regular
zlib decode function) would save all those pipe writes, and would get Skylake CPUs to run at full clock speed. (This downclocking for some kinds of load is unique to Intel Skylake and later, which have offload the CPU frequency decision making from the OS, because they have more data about what the CPU is doing, and can ramp up / down faster. This is normally good, but here leads to Skylake not ramping up to full speed with a more conservative governor setting).
No system calls, just rewriting a buffer that fits in L2 cache until you reach the starting byte position you want, would probably make a few % difference at least. Maybe even 10%, but I'm just making up numbers here. I haven't profiled
zlib in any detail to see how big a cache footprint it has, and how much the TLB flush (and thus uop-cache flush) on every system call hurts with KPTI enabled.
There are a few software projects which do add a seek index to the gzip file format. This doesn't help you if you can't get anyone to generate seekable compressed files for you, but other future readers may benefit.
Presumably neither of these projects have a decode function that knows how to skip through a Deflate stream without an index, because they're only designed to work when an index is available.