8 ms·
Sorting the files in an archive is a great trick to know for efficiency ( https://www.gwern.net/Archiving-URLs#sort-key-compression-trick https://www.gwern.net/
by gwern 6y ago
Sorting the files in an archive is a great trick to know for efficiency ( https://www.gwern.net/Archiving-URLs#sort-key-compression-trick https://www.gwern.net/Archiving-URLs#sort-key-compression-tr... ); the more redundant your files are, the better it works and the savings can be enormous. Two near-duplicate files next to each other in a compressor's stream are basically free; space them by a few dozen megabytes, and you pay full-price...
- tayo42 6y agoIsn't the whole point of compression algorithms to find string of bytes that are the same? Why does it struggle if its out of order or not next to each other? Seems simple to detect and handle?
- diegoperini 6y agoSimple but time consuming to detect I presume.
- mrec 6y agoDue to limited memory, I think most compression algos have a window of "stuff they've seen recently" which they use to detect duplicates. If the duplicate is of something too far back, it's fallen out of the window and been forgotten.
- jtolmar 6y agoCompression formats have to be small themselves, so they make tradeoffs on what data they can point at to make copies of. Most formats prioritize recent data, since that tends to be the most similar.
- jtvjan 6y agoThe 'window size' dictates how far back the algorithm can look for redundant data. If you set it too high, people without enough core memory might not be able to decompress your archive.
- duskwuff 6y agoAnd the window size for gzip is only 32 kB -- it "forgets" context pretty quickly. gzip was written in 1992, so it had to run under much tighter memory constraints than necessarily make sense today. Modern compressors like xz (LZMA) use much more memory for context. Under extreme settings and when working with large files, they can use gigabytes of memory.
- dmurray 6y agoIs this really true? Surely they should be able to decompress it with virtual memory - you tell them exactly where to look for each operation. On the other hand, it will take you much longer to compress the file if your lookback window is larger than your available memory.
- jtvjan 6y agoThey're stream compressors, so they don't want to rely on being able to seek in the file. Even with swap, you'll have to cut it off somewhere; swap space isn't infinite.
- derefr 6y agoIf you know your compressor has enough memory to hold the whole plaintext at once, but your decompressor doesn't, why not do extra work on the compression end with the whole plaintext in memory to emit an optimal "dynamic" Huffman alphabet, i.e. a code that gets patched by each new compressed block, rather than resetting to a completely new dictionary for each new block? I presume the tightest packing possible would be achieved by converting the entire document into a Huffman-encoded sequence of references into a single unified strings table; breaking that strings table down recursively using largest-common-substring until satisfied; and then packing the resulting strings tree into something more like an intrusive prefix trie where offsets are implicit IDs. The problem would, of course, be the size of the resulting trie. But you could always make the document into bytecode for a compressor VM (RAR-alike) where one opcode is "insert nodes {KV1, KV2, ...} into the prefix trie", and another opcode is "drop nodes {K1, K2, ...} from the prefix trie", such that the trie "window" used over the document would grow and shrink over time. Then you could optimize for redundant re-definitions of identical trie nodes in the compressed data, vs. total in-memory trie "window" size at any given time. If the decompression wasn't required to be streaming, but rather could advance-allocate an mmap(2)ed file to write to, then you could also have a jump opcode, so that you could organize the Huffman-code trie-prefix definitions in an optimal order to minimize definition redundancy, trading off for making the compressed representation out-of-order relative to the plaintext it decompresses to. The compressor would put the "spine" of the document all together at the beginning, together with the frontloaded rootmost trie-node definitions; then gradually undefine them, replacing them with less-frequently-used nodes needed to decode context-free "islands" of content.
- dmw_ng 6y agoIt depends on a lot on the compressor. Ancient junk like gzip/deflate only has a 32kb window, more modern compressors like zstd can do 512mb or more. Larger window means potentially much more work during compression, and larger RAM requirements during decompression, so its not exactly free
- bscphil 6y agoMakes me wonder how tar+zstd would perform for the StackOverflow user. They were using xz, which is hardly ancient junk.
- loeg 6y agoxz is more than ten years old now :-).
- craftinator 6y agoIn terms of standard Linux tools, that's hardly ancient.
- StavrosK 6y agoHell, it's barely gone from "bleeding edge" to mere "cutting edge".
- Blikkentrekker 6y agoMost tools do not become obsolete as quickly. Unlinking a path is hardly something that sees cutting edge improvements, cryptographic hashing, filesystems, and compression is something that is.
- scaladev 6y ago>xz It may not be ancient, but it's certainly not the greatest compression format out there. I found this article to be very informative: https://www.nongnu.org/lzip/xz_inadequate.html https://www.nongnu.org/lzip/xz_inadequate.html (The author worked on lzip so it's probably somewhat biased, but facts are facts.)
- burnte 6y agoSliding sindow effects. Most compression algos don't keep the entire set of files to be compressed in memory, they have a sliding window where the only lok back and ahead X bytes.
- eyelidlessness 6y agoI know there are fundamental limits on compression and I know I don’t know the first thing about implementing a modern compression algorithm. With that said: > Most compression algos don't keep the entire set of files to be compressed in memory This makes sense, but why keep the uncompressed data in memory? If the memory constraint is your biggest concern and you’re not CPU conscious, compare the outputs rather than the inputs. If you’re concerned about collisions, do a second pass to validate. I’m certain the best minds on the topic are already aware of these and either using them or have ruled them out for reasons I can’t anticipate. I really hope, that likely being the case, I’ll get a chance to learn in responses and not just unexplained downvotes.
- chmod775 6y ago> Isn't the whole point of compression algorithms to find string of bytes that are the same? No. The goal of compression algorithms is to describe an object approximately (lossy) or accurately (lossless) using the smallest number of [insert unit] possible. In some cases looking for strings of bytes that are the same serves well enough. Examples of lossy algorithms that don't just look for same strings of bytes are audio and video codecs. An example of lossless compression that works differently would be compressing "123456789" as "1 to 9". > Seems simple to detect and handle? Sure. If you've got infinite memory and time. Depending on your format you may also need to read the whole input before you can start writing the first byte.
- LeoPanthera 6y agoA good ugly hack is to reverse the filenames before sorting them, which has the side effect of grouping all the same file extensions together.
- duskwuff 6y ago7za will do this for you when running with the -mqs option.
- pmarreck 6y agoWhy isn't this the default? Or does it mean you have to use another option when de-7zipping in order to reverse them back?
- duskwuff 6y agoIt's not always beneficial. If directories contain groups of files with closely related content but different extensions, keeping those groups together may yield better compression results than reordering the files by extension.
- megablast 6y agoSorting by what?? Type.