5 ms·
Micro-Optimizing .tar.gz Archives by Changing File Order
- m463 6y agoThis is an interesting take on things. Decompressing using a different algorithm like .bz2 or .xz is noticeably slower, so sticking with gz and shuffling the files might split the difference.
- mr__y 6y agoThis would come with a cost of longer compression times - either multiple attempts with random shuffling or pre-compression file ordering optimization process. For resources that are compressed once and then distributed and decompressed multiple times this would be quite interesting solution
- m463 6y agoI got curious and looked it up. On this page [1] it looks like uncompressing with gzip vs bzip2 vs xz is: gzip bzip2 xz 1 6.771 24.23 13.251 2 6.581 24.101 12.407 3 6.39 23.955 11.975 4 6.313 24.204 11.801 5 6.153 24.513 11.08 6 6.078 24.768 10.911 7 6.057 23.199 10.781 8 6.033 25.426 10.676 9 6.026 23.486 10.623 so gzip has the fastest decompression. That said, xz is in the ballpark and can be significantly smaller. [1] https://www.rootusers.com/gzip-vs-bzip2-vs-xz-performance-comparison/ https://www.rootusers.com/gzip-vs-bzip2-vs-xz-performance-co...
- vardump 6y agoI wonder how zstd would compare.
- JoshTriplett 6y agozstd is faster and smaller. If you can choose the format, zstd beats deflate across the board, on every front except for compatibility with things that only understand deflate. Also, if you need to use deflate for compatibility, use https://github.com/zlib-ng/zlib-ng https://github.com/zlib-ng/zlib-ng , which is substantially faster than either zlib or gzip.
- joseluisq 6y agoYeah, and it is IETF standard since 2018 https://tools.ietf.org/html/rfc8478 https://tools.ietf.org/html/rfc8478
- dependenttypes 6y agoIs it though? In https://quixdb.github.io/squash-benchmark/unstable/ https://quixdb.github.io/squash-benchmark/unstable/ deflate beats zstd at least in some tests.
- joseluisq 6y agoYeah, but zstd beats deflate in others. For example the latest MySQL 8 https://dev.mysql.com/worklog/task/?id=13442 https://dev.mysql.com/worklog/task/?id=13442
- JoshTriplett 6y agoIt's universally faster if you compress threaded, and otherwise it's generally still a win.
- m463 6y agoI've never heard of zstd (thanks!), but it seems it's right under my nose. "Arch Linux added support for zstd as a package compression method in October 2019 with the release of the pacman 5.2 package manager, and in January 2020 switched from xz to zstd for the packages in the official repository. Arch uses zstd -c -T0 --ultra -20 -, the size of all compressed packages combined increased by 0.8% (compared to xz), the decompression speed is 1300% faster, decompression memory increased by 50 MiB when using multiple threads, compression memory increases but scales with the number of threads used." https://en.wikipedia.org/wiki/Zstandard https://en.wikipedia.org/wiki/Zstandard
- andruby 6y agothis is my go-to comparison of different compression algorithms [0] TL;DR zstd is faster, smaller and has a wider range than gzip. For maximum compression, plzip seems to be the best. [0] https://community.centminmod.com/threads/round-4-compression-comparison-benchmarks-zstd-vs-brotli-vs-pigz-vs-bzip2-vs-xz-etc.18669/ https://community.centminmod.com/threads/round-4-compression...
- mannschott 6y agoYea, I used to do this with a little script. The strategy I used, which worked well when I was compressing and archiving workspaces (which might often contain checkouts of different branches of the same project) was essentially this: find * -print | rev | sort | rev | tar --create --no-recursion --files-from - | gzip This clusters file types together and within file types and within that files with the same base name close together. This worked surprisingly well for my use cases, though you can imagine that packing and unpacking times were impacted by the additional head seeks caused by the rather arbitrary order in which this accesses files.
- m463 6y agoOn the other hand SSDs have cut at least 20% off head seek times. ;)
- joseluisq 6y agoA small experiment with a 143M directory. $ tar -zcvf file.tar.gz directory/ $ du -sh directory.tar.gz 57M directory.tar.gz $ find directory/* -print | rev | sort | rev | \ tar --create --no-recursion --files-from - | \ gzip -c > directory.tar.gz $ du -sh directory.tar.gz 55M directory.tar.gz 3.51% (2MB) reduction makes many sense here.
- david_draco 6y agoAwesome! I will use this. I would like this even more if it stopped at filenames (ignored paths) and when equal, sorted by file sizes.
- mannschott 6y agoThis will already sort equal file names together. If I wanted to combine that with file sizes, I'd probably do some kind of decorate | sort | undecorate dance on each line produced by find. Where decorate would add the start of each line the things you want to sort by and undecorate would remove them again.
- throwaway8941 6y ago
- xuhu 6y agoUnpacking already packed files before adding them to the archive could also improve compression, if the packed files contain common parts (or were packed in a less sophisticated format).
- hyperman1 6y agoTrue. The java world it was common to put a jar (zipfile) in a war (zipfile). If you modify the jar so every file in it is stored instead of deflated, then package it in a war, the resulting file can be a lot smaller.
- Hello71 6y agohttps://github.com/schnaader/precomp-cpp https://github.com/schnaader/precomp-cpp
- xuhu 6y agoSome results here, impressive: http://schnaader.info/precomp_results.php http://schnaader.info/precomp_results.php
- wolf550e 6y agoBecause DEFLATE uses a small 32KB window, this task is just matching the last 32KB of one file with the first 32KB of another file for most redundancy. A tool can do those estimations to find the best matching file to put in the archive after the current file, without doing the huffman coding when doing it. For cases like multiple checkouts of the same repo in a single archive, you want real long range compression like lrzip or zstd --long. And in the end, using zstd would be a win over DEFLATE every time. Just stop using DEFLATE unless you have to for compatibility with something that can't do zstd.
- vanderZwan 6y agoThe fact that most of us use DEFLATE without ever realizing that it's optimized for hardware specs from many decades ago, and especially this 32KB window part, is is pretty much the "grandma's cooking secret"[0] of compression, isn't it? [0] https://www.snopes.com/fact-check/grandmas-cooking-secret/ https://www.snopes.com/fact-check/grandmas-cooking-secret/
- zxcvbn4038 6y agoThat is the beauty of deflate! It was fast on hardware many decades ago and it does well on today’s hardware as well. It has found a real sweet spot between execution time and memory consumption. You can pick up a few extra percent here and there but often requiring massive increases in one and/or the other, or specific knowledge of what your compressing (images, audio, assembker output, etc)
- wolf550e 6y agoNo, compression technology has advanced a lot since DEFLATE. Today's general purpose compressors beat DEFLATE at all points on the Pareto frontier (any network/disk speed, any compression ratio vs CPU time trade-off). Use zstd. If you need even more speed, use lz4. If you need even more compression, use LZMA (or if it's natural language text use ppmd).
- 6y ago
- mnw21cam 6y agoIf I recall, the LZX [0] compression program on the Amiga, way back when, used to do this. It re-ordered the list of files according to some detected type or other before compressing in groups. It called these groups "merge groups" [1]. [0] https://en.wikipedia.org/wiki/LZX https://en.wikipedia.org/wiki/LZX [1] http://xavprods.free.fr/lzx/optsmmgs.html http://xavprods.free.fr/lzx/optsmmgs.html
- formerly_proven 6y ago"Merge groups" sound like solid compression, i.e. compressing multiple files together. Note that .tar.XYZ is always fully solid, while something like .zip compresses each file individually, and something like .7z has a solid block size. That's the main reason why .tar.gz usually compresses better than .zip, despite zip usually using deflate, just like gz.
- mnw21cam 6y agoYes, that's right. The useful bit is making sure that similar files are put in the same group (or otherwise within the search window of the compression algorithm, which for LZX was 64kB, and for deflate is 32kB).
- metafunctor 6y agoThe biggest ”whoa” effect I've had in a while with gz archives was using pigz --rsyncable. It's so much faster than single-threaded gzip, and borgbackup can do block-level deduplication on the result. Perfect for database dumps, for example.
- diroussel 6y agoLinks for the lazy: https://zlib.net/pigz/ https://zlib.net/pigz/ Made by: https://en.wikipedia.org/wiki/Mark_Adler https://en.wikipedia.org/wiki/Mark_Adler
- david_draco 6y agoA big help could be sorting files by extension, and sorting by filename. For example, the same file name in many sub-directories is probably going to have similar content. For example: a/index.txt b/index.txt a/img/index.txt a/img/logo.png a/img/test.css a/foo.css Edit: this is what mannschott's script does.
- siscia 6y agoMaybe I am missing something, but this approach is doomed to fail / produce small gains. A tar file is a concatenation of different 512 bytes of data. The first block contains the metadata of the file, and the next blocks contains the content. Of those first 512 bytes of data, only the first 100 bytes contains the text. Trying to play with the orders of files to make 100 bytes of data fit next to each other in block of 512 bytes, it does not seems a successful approach. gzip use a 32kb windows, that can include up to 64 tar headers. At the very best we are saving 100bytes * 64 => 6400 bytes alright 7kb every 32kb. For an optimal compression of the (32-7)/32 => 78%. The author says that the standard gzip compressed to 45768 / 337920 => 13% I believe there are better approaches...
- Kuinox 6y agoYeah, like stop using tar, and use a better format like Zip Archives.
- david_draco 6y agozip seems to be the only widely supported compressed archive format that supports extracting a file content by jumping to the data location, and easy deletion of individual files.
- throwaway2048 6y agoZip archives do not support unix permissions
- Kuinox 6y agoOne more reason to use zip archives then !
- qwerty456127 6y agoI can't stop wondering (sincerely, not for a "holywar" sake or anything) why we still use tar.whatever today, when ~99% of us have never seen a tape drive. .tar.gz felt such a wild step backwards after 7z when I switched from Windows to Linux. Why can't we just introduce links and access rights metadata to 7z or something and use a modern, feature-rich archive format which wouldn't require you to decompress everything just to get a clue if there is a particularly named file in there?
- vbezhenar 6y agoBecause tar gz works on any unix and 7z requires installing additional software. Whether you want that or not depends on your use-case. It's a good example of "good enough" software which is hard to phase out. That said, recently I've found that CentOS 8 minimal did not have tar installed. So may be it's worth to start using something modern like zip or even 7z.
- ekimekim 6y agoThe simplicity of the tar format has certain advantages, such as ensuring an implementation in a variety of languages and platforms. The seperation of "group files into an archive" and "compress these bytes" can also be very useful. For example, it means I can play around with the latest and greatest compression formats without needing to wait for a version of tar that has that format built-in. Overall, I think it appeals to the "unix philosophy" - composing two independent tools (tar and gzip) instead of having one integrated solution. The "tape drive" part is legacy cruft, certainly, but in practice its removal doesn't improve things enough that people find it worth the compatability break. I'm not going to claim this is better than the more modern feature-rich archive formats, but hopefully this helps you understand the other side of the argument a little better.
- lifthrasiir 6y ago> Overall, I think it appeals to the "unix philosophy" - composing two independent tools (tar and gzip) instead of having one integrated solution. The unix philosophy in this case breaks down when you need to access individual files. One possible "unixy" solution would be .gz.tar as opposed to .tar.gz, but it is not universally supported as .tar.gz is.
- nisa 6y agoYou can get even better results by sorting the files by content similarity: http://neoscientists.org/~tmueller/binsort/ http://neoscientists.org/~tmueller/binsort/
- andruby 6y agoVery cool! > binsort <dir> | tar -T- --no-recursion -czf out.tar.gz > Binsorting the distribution of abiword 2.8.6 (44029103 bytes in 3391 files) on a quadcore CPU takes approx. 12s, and produces a tar.gz more than 14% smaller than without processing. 14% is an amazing improvement.
- jakozaur 6y agoZstd is superior to gz. It also got larger window. I wonder why adoption of better compression formats is so slow.
- zomg 6y agoalways remember the xkcd comic "tar", which will never get old! :) https://xkcd.com/1168/ https://xkcd.com/1168/
- gwern 6y agoI had some archives which are heavily redundant (web mirrors & scrape mirrors by date), and so I looked into file order compression: https://www.gwern.net/Archiving-URLs#sort---key-compression-trick https://www.gwern.net/Archiving-URLs#sort---key-compression-... On my particular use-case, the compression gains are enormous. It's particularly impressive because as far as any enduser is concerned, it's just like any other compressed XZ tarball.