15 ms·
Why are tar.xz files 15x smaller when using Python's tar compared to macOS tar?
- war1025 6y agoUnrelated to the issue in the post, but a few years back we ran into an annoying oddity in the Python zipfile module [1]. By default, when you create a new zipfile object to create a .zip archive with, it stores the data uncompressed. Only noticed the issue when a 100MB zip file suddenly became 3MB after I had edited one of the files and re-saved the archive. [1] https://docs.python.org/3/library/zipfile.html https://docs.python.org/3/library/zipfile.html
- Jiocus 6y agoThis isn't an oddity or issue with Python zip creation, it's expected behaviour as per ISO/IEC WD 21320-1[1]. > The compression method shall be either 0 (“stored”) or 8(“deflated”). The format does not prescribe a compression algorithm (many could be available for use). It's merely a container. [1] ISO/IEC WD 21320-1, Document Container File - Part 1: Core - https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.397.7181&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39...
- bawolff 6y agoWhat defaults python chooses is an oddity within python.
- masklinn 6y agoYes, it's clearly documented but very much unexpected the first time 'round. The reason for the default is probably that python can be built with none of zlib, bzip2 or lzma support: > If ZIP_DEFLATED, ZIP_BZIP2 or ZIP_LZMA is specified but the corresponding module (zlib, bz2 or lzma) is not available, RuntimeError is raised. in which case only STORED is available, therefore that's the only possible default, any other would lead to zipfile raising errors out of the box for some people. It would probably have been a better idea to just not use a default, and require the compression method to always be specified, at least when opening zipfiles with modes other than "r".
- duskwuff 6y agoTBH, Python's zipfile should probably just require zlib. Without that module, it's basically useless (can't open most ZIP files, can't emit compressed ZIP files).
- Aachen 6y agoActually, I've argued the opposite in the past. Any file that is of any significant size is already compressed: images, audio, video, gifs, PDFs, game map/save data... even documents (and by extension, spreadsheets and presentations) are compressed these days (because they're... zips! It's zips all the way down). Compression in your zip archive implementation is unnecessary complexity at this point. Compressing archives most only makes sense if you have some huge (many many millions of lines) set of source code because that's a lot of data, more than one file that you want to compress, and low entropy in those files. Only in that combination does zip with compression make sense over uncompressed archives or compression without archive format. Of course, zip can shoehorn both functions that you usually don't need together into one format and we're usually not CPU-bound anyway so I totally see why you might as well always apply a small amount of compression, but I would beg to differ if you say "it's basically useless to have zip without compression support". There are more cases where zip with compression is completely redundant than cases where it helps you.
- duskwuff 6y ago
- jasode 6y agoFyi... not mentioned explicitly in that Q&A is the related concept : https://en.wikipedia.org/wiki/Solid_compression https://en.wikipedia.org/wiki/Solid_compression [EDIT to reply] : >The difference was just the order in which the files were concatenated. Yes, right. My link just emphasizes the files concatenation aspect (e.g. tar is one example) for people who base the intuition on the ZIP format in which files' order doesn't matter because each file is compressed separately.
- simias 6y agoNote that in both cases the archive was first put into a single tar file, then compressed. That's how all tar formats function. The difference was just the order in which the files were concatenated.
- masklinn 6y agoThe point GP is making is that tars are "solid" archives, so compression can span files, which means putting files with lots of redundancy between them next to one another will yield much better compression ratios than orderings which are essentially random. That is somewhat unintuitive to people used to zip archives, because zip contents are compressed independently, so the ordering really doesn't matter (at least to the compression ratio).
- simias 6y agoAah ok, that makes sense, sorry for the confusion. I didn't know zip worked that way, although in hindsight that explains why it's so simple and fast to extract and/or modify only a part of a .zip archive, even on old computers.
- masklinn 6y ago> although in hindsight that explains why it's so simple and fast to extract and/or modify only a part of a .zip archive, even on old computers. That is also because zips have a « central directory », so to modify or add one of the files you just need to add a new record then update the central directory. If you don’t care too much for size you can literally just append them to the existing zip file and leave both the old record (for updates) and the old central directory.
- nomy99 6y agoAlso a bit unrelated, but at my work place we reimplemented tar algorithm so we can run it in a lambda/state machine. We used the s3 multipart upload to help with the file transfer bit. The performance was phenomenal. On avg we were tar'ing 20gb in 15 seconds or so, a lot faster than on my pc.
- OskarS 6y agoTar (as opposed to gzip) is almost entirely I/O bound, it's just reading from the filesystem, adding some headers and then outputting it again. Whatever speed your I/O runs at, you will basically tar at that speed as well.
- banana_giraffe 6y agoYep. One of the biggest speed improvements I got out of a process that creates large tar balls was moving it to use pbzip2 to allow the compression to use multiple cores.
- gnulinux 6y agoI don't understand this comment. You can run arbitrary code in AWS lambda, you can just run "tar". Why did you need to reimplement it?
- 411111111111111 6y agoIt wasn't always like that though. I think they added custom runtimes around 2yrs ago... Your options were very limited before that.
- sgt 6y agoEven better when you switch on the --lossy option in gzip.
- Aachen 6y agoWas hoping for an Easter egg, but it just says unrecognized option? At least on my phone it does, iirc that's a Debian Buster install that I haven't updated in three years.
- xmprt 6y agoI might be overexplaining but it's a joke because lossy compression of a gzip would end up with you losing data that could render the entire file unreadable.
- Aachen 6y agoYeah, that much was clear, just thought it might refer to a hidden option that triggers a funny message, but it didn't for me so perhaps it was a macOS' gzip thing or an ancient/recent gzip version thing.
- ObscureScience 6y agoI assume you're joking... I've never heard of lossy compression in this kinds of formats, as there's no general way to determine what can be discarded without affecting the utility of the data. There's no such option in any implementation of gzip I've found...
- dheera 6y agoWhat version of gzip has a lossy option?
- ben509 6y agoIt's a joke. Lossy compression can only work with specific formats where information loss is acceptable, theoretically anything but in practice usually audio and video. If gzip tried to do lossy compression, not knowing what the data is, it would have to randomly corrupt data.
- gwern 6y agoSorting 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 ago
- jaynetics 6y agotl;dr: the python lib adds files to the archive sorted by the last modification date by default. this happened to be better in this case, but macOS tar had the same results when using the appropriate sorting flag. Makes me wonder: considering the speed of modern SSDs, would it make sense for compression tools to try various sortings by default, or compare files up front?
- tomatocracy 6y agoAnother option is to use something like lrzip as the compressor - not sure if it would have helped in this instance but it incorporates a step which looks for long-range redundancy which can make a huge difference in these sorts of scenarios.
- JulianWasTaken 6y agoSeems better to have some separate higher level metacompression tool which does the heuristic searching across many possible compression formats and parameters.
- duskwuff 6y agoThis is precisely the approach taken by the Hydra metacompressor in the (closed-source) Oodle compression library: http://cbloomrants.blogspot.com/2017/02/oodle-hydra.html http://cbloomrants.blogspot.com/2017/02/oodle-hydra.html
- masklinn 6y ago> macOS tar had the same results when using the appropriate sorting flag. No, macOS has the same results when using gnutar which provides sorting option. bsdtar (which macOS provides out of the box) has no such option. It just stores files in whichever order you provide them (on the command-line, via the CLI) or it finds them (for recursive tar, so whichever order the directory returns them in).
- js2 6y ago> macOS tar had the same results when using the appropriate sorting flag They had to install and use GNU tar to gain the `--sort` option. macOS (BSD) tar doesn't have it. (You could emulate the behavior by using `find` and passing the member names in on the command-line.)
- userbinator 6y agoIf I compare the two tar archives directly, they seem different I like the fact that this user considered whether the filesystem was lying about the size. It's interesting to see the problem-solving approach; my next step would be to hexdump both and see if one isn't actually compressed as much as it could be, then decompress and inspect the tars. I'm not sure whether it's true here, but one situation that leads to seemingly randomly-ordered files is when the archiver tries to be faster by using multiple threads. The XZ blocksize is another variable to consider.
- 0xdky 6y agoFWIK, compression works by de-duplication. Finding duplicate patterns is limited to a window. If similar patterns are close to each other, there is a higher probability of finding such duplicates in the window leading to better compression. When the files are not sorted, this randomly distributed files with similar patterns beyond the compression window leading to poor compression. If there is an option to increase the size of window, that would be a good experiment. This is very similar to `git repack` window and depth parameters. Larger the window and depth, you get better compressed packs. Wonder if a sort based on diffs (group similar files together) would help get best compression. The cost of such sorting might outweigh the benefits.
- fuzzy2 6y agoThat’s not the case here. What you describe is basically compression in “solid blocks”. `xz`, however, is (in practice virtually always) fully solid. It allows greater compression efficiency at the expense of random access, which is not possible at all. The order matters because it “defines” what the algorithm’s dictionary will look like.
- verytrivial 6y agoI think it's right regarding the limited horizon of the window. Any dynamic compression scheme that evolves knowledge of the input stream will have this property. The tar block being compressed here is many orders of magnitude larger than the window, so the order in which the compressor sees the stream matters. It is somewhat more complicated because e.g. dynamic Huffan coding rarely applied to raw streams but to a series of one or more encoders such as run-length, but the reasoning remains that if the window or coded/dynamic dictionary size is much larger than the data stream, compression can improve with input permutation. Back in the 90s I recall an unpopular but very efficient encoder called UltraCompressor[1] which had some input permutation heruristics, "solid" compression, and damage recovery to boot! [1] http://www.compression.ru/arctest/self/uc.htm http://www.compression.ru/arctest/self/uc.htm
- mxcrossb 6y agoThere’s a lot of research in the field of scientific computing aimed at exactly this kind of data. You can definitely gain a lot of your floating point data is varying slowly.
- TheGuyWhoCodes 6y agoThis isn't really specific to tar. For example if you save data to parquet, sorting the data before persisting it can make a huge difference in the size of the file AND the predicate pushdown performance (as you can skip more pages especially if you sort by the column you filter on)
- chrisdbanks 6y agoDo any compression algorithms use and approximate matching technique like ssdeep to sort the files by similarity before compression starts? It might be slower but if the compression was 15x better then it might be worth it in some scenarios.
- thomasmg 6y agoSorting chunks by similarity: commonly used tools don't do that. Most archive tools only sort by file type. I wrote a tool that chunks the data (into variable-sized blocks, to re-sync if there are multiple files that have different length prefixes, but that's another story), and then sorts the chunks by LSH (locality sensitive hash). LSH is used by search engines to detect similar text. It can compress directories that contain multiple version of e.g. source code very well (e.g. trunk, branches). https://github.com/h2database/h2database/blob/master/h2/src/tools/org/h2/dev/fs/ArchiveTool.java https://github.com/h2database/h2database/blob/master/h2/src/... I discussed this approach with a researcher in this area in January 2020. AFAIK there is active research in this area, specially to compress DNA sequences. But he also wasn't aware of papers or research in this area for general-purpose data compression. So, I think this area is largely uncharted. I would be interested (as a hobby side project) to help, if somebody is interested. Summary: * Regular compression algorithms use a certain "window size": this can be 32 KB, or 2 GB, or so. But sorting chunks can be faster faster and can improve the compression rate. * Regular compression tools can sort by file name and file type. * Data de-duplication tools (e.g. enterprise backup tools) chunk the data in a smart way, but then only support exact duplicates (not near duplicates). * Locality sensitive hashing: it is not used in common compression tools so far AFAIK.
- gwern 6y agoYou can use binsort to sort the file list upfront by similarity of contents, which is usable with tar and zip and so can be piped into any other compression you want (every once in a great while when I can't come up with a good filename-based sort, I try out binsort); and lrzip attempts to do long-range similarity detection without changing order to do something similar.
- jwilk 6y agotarfile sorts names only since Python 3.7: https://bugs.python.org/issue30693 https://bugs.python.org/issue30693
- usr1106 6y agoNice trick with the sorting. We use xz compressed Linux root filesystem images quite a bit. I wonder whether having arranged the files in the filesystem images could achieve a significant saving. Unlikely to be a factor of 15, but 20-30 wouldn't be bad either.
- gspr 6y agoSemi-related fun fact: I've experienced a large speedup doing MD5 checksumming with Python's hashlib instead of md5sum(1).
- Theodores 6y agoI want to know how well Brotli fares with this. Browser and server support for Brotli and Brotli with static compression is the future rather than these MS-DOS things from a long time ago.