17 ms·
Apple Open-Sources its Compression Algorithm LZFSE
- dchest 10y agohttps://news.ycombinator.com/item?id=11944975 https://news.ycombinator.com/item?id=11944975
- legulere 10y agoAnd even earlier: https://news.ycombinator.com/item?id=11922453#11925386 https://news.ycombinator.com/item?id=11922453#11925386
- jordyjordy 10y agoWe are bank of hackers based in the UK, US, Canada we offer services such as school grades change, DDOS, database hack, credit, criminal records, bank transfer, social network hack, emails, password retrieval and all forms of hack, contact GURULEADS hackers today via email demonteco@outlook.com
- DeepYogurt 10y agoHere's the github link https://github.com/lzfse/lzfse https://github.com/lzfse/lzfse
- deleted 10y ago[deleted]
- DiabloD3 10y agoSo... basically a clone of LZ4?
- awalton 10y agoBasically an Apple-specific reimplementation of Zstd: https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd
- DiabloD3 10y agoSo, worse than LZ4 for what Apple seems to be using it for. Why didn't they just use LZ4? Confusing company, they are.
- shmerl 10y agoThey are very much into NIH, seemingly out of paranoid fear of patent attacks (though not sure how it can protect them).
- dchest 10y agoThis is a baseless speculation. First of all, Apple provides LZ4 in libcompression. Secondly, LZFSE uses Lempel–Ziv algorithm and ANS coder invented by Jarek Duda (https://arxiv.org/abs/1311.2540 https://arxiv.org/abs/1311.2540): https://developer.apple.com/library/ios/documentation/Performance/Reference/Compression/index.html https://developer.apple.com/library/ios/documentation/Perfor...
- nicky0 10y agoCan I just say I really appreciate your contributions on this thread. Answering crass company-bashing with well-referenced and informative replies.
- dchest 10y agoThank you :)
- twitch_checksum 10y agoWell, many people nowadays pretend that, as if they read Jarek's paper, understood it and came out with a genuine implementation of their own. But Jarek's ANS paper was first out in 2007, and almost no one paid attention to it, because it was plain inscrutable. Many years later, it took an individual to create FSE (https://github.com/Cyan4973/FiniteStateEntropy https://github.com/Cyan4973/FiniteStateEntropy), to prove that it could be transformed into something actually useful and competitive. Since then, the paper has been updated a few times, borrowing a few points from FSE in order to become more readable. But it's still very hard to read. In contrast, FSE code can be copy/pasted. And all of a sudden, lot of versions have popped out over Internet. By pure chance, they all look like derivatives of FSE or Fabian Giesen's rANS, but they pay tribute to Jarek's ANS paper, because quite clearly it is the source of their work, and prior existence of an actual open source implementation which works and looks pretty damn close to theirs was purely accidental. This is not paying tribute where it's due.
- nodesocket 10y agoInteresting to see a benchmark against .zip and .gz in terms of file reduction and uncompress time.
- nodesocket 10y agoIf you want to see some crazy C code, check out this file from the GitHub repo: https://github.com/lzfse/lzfse/blob/master/src/lzvn_encode_base.c https://github.com/lzfse/lzfse/blob/master/src/lzvn_encode_b...
- ghayes 10y agoIt looks like it was run through a Javascript minifier.
- drinchev 10y agoExcerpt from the link : if (D == D_prev) { if (L == 0) { *q++ = 0xF0 + (x + 3); // XM! } else { *q++ = (L << 6) + (x << 3) + 6; // LLxxx110 } *(uint32_t *)q = literal; q += L; // non-aligned access OK } else if (D < 2048 - 2 * 256) { // Short dist D>>8 in 0..5 *q++ = (D >> 8) + (L << 6) + (x << 3); // LLxxxDDD *q++ = D & 0xFF; *(uint32_t *)q = literal; q += L; // non-aligned access OK } else if (D >= (1 << 14) || M == 0 || (x + 3) + M > 34) { // Long dist *q++ = (L << 6) + (x << 3) + 7; *(uint16_t *)q = D; q += 2; // non-aligned access OK *(uint32_t *)q = literal; q += L; // non-aligned access OK } else { // Medium distance x += M; M = 0; *q++ = 0xA0 + (x >> 2) + (L << 3); *(uint16_t *)q = D << 2 | (x & 3); q += 2; // non-aligned access OK *(uint32_t *)q = literal; q += L; // non-aligned access OK }
- barsonme 10y agoBlows my mind that people can come up with this stuff. I'm assuming they came up with the mathematical proofs first and translated that into code, so that has something to do with it, correct? It looks a lot like some crypto algorithms which are a nearly direct translation of the mathematical formulas. It's not that it's incredibly difficult to follow, but it's just very "math like".
- lokedhs 10y agoThat is my experience. Maths people are not renowned for their ability to write readable or maintainable code. I recently needed an implementation of the Simplex Noise algorithm (that I could port to Common Lisp). I ended up using this one, which works but the code certainly does nothing to help understanding: https://github.com/josephg/noisejs/blob/master/perlin.js https://github.com/josephg/noisejs/blob/master/perlin.js Note that the Javscript implementation is also a port from another language (whose implementation I have failed to find).
- benmarten 10y agoI just quickly tested it, in terms of highest compression ratio it still does not beat xz, e.g. `tar -cf -FILE | xz -c9e > FILE.tar.xz` https://blog.benmarten.me/2016/04/01/Compress-Files-With-Highest-Compression/ https://blog.benmarten.me/2016/04/01/Compress-Files-With-Hig...
- amock 10y agoThat's not a useful comparison. LZFSE is meant to be very fast and energy efficient while xz is meant for high compression while using lots of CPU and memory.
- deleted 10y ago[deleted]
- Someone 10y agoThat's not surprising, given that they went for compression and decompression speed and for energy usage. Their goal seems to have been to be at least as good as zlib at compressing stuff using less energy and doing it faster (that often correlates quite well with energy use on modern CPUs, as it allows them to drop to low energy states faster)
- a_imho 10y agoCould you give me some pointers on the actual numbers? My searches came back with nothing. I'm especially interested how they benchmarked the energy consumption.
- sjwright 10y agoMost likely they would infer energy usage from resource consumption.
- Someone 10y agohttp://asciiwwdc.com/2015/sessions/712 http://asciiwwdc.com/2015/sessions/712 is the best pointer I know, but it does not give details. My guesses would be that they have a simulator that computes/estimates power usage, and that they have CPU setups where they measure power usage directly. I doubt they regularly do the "compress things till you run out of battery" thing that that talk mentions. That takes too long, and cannot be used to measure small changes in power usage.
- OneNoteIsFree 10y agoCorrect me if I'm wrong but isn't the algorithm open?
- svckr 10y agoWith energy efficiency as a primary goal I was expecting way more use of explicit SIMD instructions. The InfoQ post mentions xcodebuild, but there is also a Makefile. I really appreciate the presence of a no-nonsense Makefile. No autoconf, no pkgconfig, just plain and simple make. Also, because nobody mentioned it: yes, it compiles on Linux out of the box.
- sjwright 10y agoIt's entirely possible that Apple have a SIMD-optimised version targeting their in-house CPUs but have chosen only to open source their reference implementation.
- gsnedders 10y ago> With energy efficiency as a primary goal I was expecting way more use of explicit SIMD instructions. I remember reading one paper whose conclusion was running SIMD instructions can be bad for power consumption: while you need the processor in a higher power state for longer without, you can keep the SIMD unit powered off. [Edit: That said, I have no idea how true this is for the modern Intel CPUs yet alone Apple's custom SoCs.]
- astrange 10y agoThis can be true if it's the only time it's used, but when memcpy and everything use the SIMD operations, it's a lost cause. Instead you just want to go as fast as possible, so you can go back to sleep. They call it "race to idle".
- eln1 10y agoIt is poorly optimized for 32bits - some benchmarks: http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compression?p=48519&viewfull=1#post48519 http://encode.ru/threads/2221-LZFSE-New-Apple-Data-Compressi...
- talideon 10y agoI don't mind pkg-config that much: if anything, it's one of the more sensible portability mechanisms out there.
- grewil2 10y agoKind of weak licence, what are you actually allowed to do with this code? Change it? Distribute your changes? https://github.com/lzfse/lzfse/blob/master/LICENSE https://github.com/lzfse/lzfse/blob/master/LICENSE
- Thev00d00 10y agoThat is the BSD 3-Clause License?
- dalbin 10y agoIt's the BSD 3-Clause : https://opensource.org/licenses/BSD-3-Clause https://opensource.org/licenses/BSD-3-Clause
- DasIch 10y agoThe very first paragraph answers the question: > Redistribution and use in source and binary forms, with or without modification, are permitted[...]
- nicky0 10y agoClicked the link expecting to see some obscure license and wryly think "ah, crazy Apple logic again". Turns out it's the BSD license, probably the most well-known and widely used permissive open source license.
- finchisko 10y agoWaiting for first guy who take this implementation and run it through emscripten so we can actually use it in client -> server communication, eg sending compressed json payloads to the server.
- panic 10y agoIs running (not to mention downloading/parsing/compiling) emscriptened decompression code really that much faster than just transferring the data? I think a better strategy would be to add support for LZFSE to the browsers themselves.
- finchisko 10y agoNative support in browser would be appreciated. But I was also thinking about nodejs server side decompressing via native or emscripten transpiled module.
- ascagnel_ 10y agoA quick reading of the license[0] shows that there's no legal stumbling blocks to the code showing up in browsers, but the license doesn't mention anything about patents. [0] https://github.com/lzfse/lzfse/blob/master/LICENSE https://github.com/lzfse/lzfse/blob/master/LICENSE
- finchisko 10y agoIt would be slower, but point is to reduce bits when sending large json over cellular network.
- madeofpalk 10y agoYou mean... like gzip?
- finchisko 10y agoyeah, but also the opposite direction client -> server. client will send compressed data to server use LZFSE. Kind of nice extension to HTTP protocol, which only supports compression from server to client.
- shmerl 10y ago> LZFSE is only present in iOS and OS X, so it can’t be used when the compressed payload has to be shared to other platforms (Linux, Windows). So now it will be cross platform?
- hollander 10y agoYou can bet that there is a Linux version soon, and if it's good enough, it will end up in the default repo. For Windows, it's a different story, but maybe because of the iPhone and iPad, and many MS employees using them, will it be supported somewhere in the not so near future. Anyways, 7zip and Winzip will probably support it soon enough.
- coldcode 10y agoIt compiles in Linux as is. There is a generic makefile.
- jibsen 10y agoIt compiles fine with mingw-w64 on Windows. MSVC is a bit more involved due to the GCC extensions used. When LZFSE first came out I made a fork with the changes to compile with MSVC [1], but there wasn't any interest in it. [1]: https://github.com/jibsen/lzfse/tree/msvc-compatibility https://github.com/jibsen/lzfse/tree/msvc-compatibility
- pilif 10y agoIt's 2016. How can you launch a reasonably high profile open source project with code that looks like this? This fulfills all the TODO list for unreadable code. One character variable names, one character parameter names, full of magic numbers... Yes. This is very performance critical code and I completely see the need to write very optimized code. That's fine. But optimizing code for speed shouldn't imply also optimizing it to use as few characters as possible. Compression code is code that often runs at boundaries to the external world and thus is a very significant attack surface. To release compression code in a non-safe language is risky enough but then using what amounts to practically write-only code is, IMHO, irresponsible.
- johncolanduoni 10y ago> To release compression code in a non-safe language is risky enough At the moment, what's their real alternative? Rust is the only memory-safe language I can think of that could hope to meet their performance requirements, but even the Rust runtime would be a lot of overhead for this application. That said, I agree this isn't acceptable C code for something that runs on untrusted data while using tons of pointer arithmetic.
- pilif 10y agoYou're right about C. C in general, I would find acceptable, because, yes, there aren't that many good alternatives around for this kind of code. But there's nothing stopping you from writing readable C code. That's where my concerns come from.
- deleted 10y ago[deleted]
- msvalkon 10y agoI don't really understand where the downvotes come from? I find the readability concerns legitimate, and would like to understand why compression algorithm developers feel like this is OK? Is it just the math heavy background? Can't think of any real benefits to this style.
- panic 10y agoThe article is essentially a link to https://www.infoq.com/news/2016/07/apple-lzfse-lossless-opensource https://www.infoq.com/news/2016/07/apple-lzfse-lossless-open... with a bunch of ads on top. Maybe someone could update it to point there instead?
- dang 10y agoOk, we changed to that from http://www.appleworld.today/blog/2016/7/6/apples-lzfse-compression-algorithm-goes-open-source http://www.appleworld.today/blog/2016/7/6/apples-lzfse-compr....
- tlrobinson 10y agoWell, what's the Weissman score?
- dietrichepp 10y agoThe Weissman score is the most moronic compression "metric" ever devised. I put "metric" in quotes because from a mathematical perspective, it is practically gibberish. I'm tired of seeing it mentioned in every HN post on compression.
- deleted 10y ago[deleted]
- indolering 10y agoSilicon Valley gets rave reviews, but a story plot based on a patented compression algorithm....
- legodt 10y agoI also see this kind of response a lot in situations the score is brought up. I don't have a background in compression, what is the current method for measuring compression efficiency? Is it a balance between size reduction and speed to unpack or is measuring compression efficacy far more nuanced?
- dietrichepp 10y agoUsually you compare on a 2D graph, with one axis being decompression speed and the other axis being compression ratio. Sometimes decompression speed is replaced by decompression + compression speed, for round-trip data. Very rarely you only consider compression speed, for "write-many read-seldom" data (like backups). Normally, any sensible 1D metric would be visualized as isolines in that 2D plane. But the "Weissman score" doesn't even make that much sense, it's a discontinuous, non-monotonic function with singularities right in the middle! It doesn't even make sense from a dimensional analysis perspective… the score will fluctuate wildly based on the units you choose for time and size (minutes? seconds? octets? bits?). There is no conceivable real-world application of the Weissman score. It is just a bit of bad math that appeared on TV once.
- kirkdouglas 10y agoHuh, I hope macOS code looks better.
- deleted 10y ago[deleted]
- cooper12 10y agoOh wow dude you watch Silicon Valley also? Great reference! It sure added a lot to the conversation. Please continue making useful comments like this in the future, you really got us thinking with your pop culture reference. (And I sure patted myself on the back for recognizing such witticism)
- klausa 10y agoThere's a way to make this point without being an asshole about it.
- deleted 10y ago[deleted]
- Mao_Zedang 10y agoI thought it was funny, dont be so joyless.
- deleted 10y ago[deleted]
- dang 10y agoPlease don't do this here. We detached this subthread from https://news.ycombinator.com/item?id=12048265 https://news.ycombinator.com/item?id=12048265 and marked it off-topic.
- espadrine 10y agoI feel like LZFSE is too little, too late. It would be great to have a proper comparison, but Zstd is stable, and offers a superior compression ratio with compression and decompression speeds that seem on par with LZFSE. And Zstd is not proprietary. (This issue is relevant in this regard: https://github.com/lzfse/lzfse/issues/21 https://github.com/lzfse/lzfse/issues/21) https://github.com/Cyan4973/zstd https://github.com/Cyan4973/zstd Edit: here is a quick comparison I did on Linux with Project Gutemberg's webster (http://sun.aei.polsl.pl/~sdeor/corpus/webster.bz2 http://sun.aei.polsl.pl/~sdeor/corpus/webster.bz2). $ time ./lzfse-master/build/bin/lzfse -encode -i webster -o webster.lzfse real 0m1.885s user 0m1.860s sys 0m0.024s $ time ./zstd-master/programs/zstd webster -8 -f -o webster.zstd webster : 25.98% (41458703 =>10772836 bytes, webster.zstd) real 0m1.700s user 0m1.660s sys 0m0.036s $ ls -l -rw-r--r-- 1 tyl tyl 12209496 Jul 7 16:26 webster.lzfse -rw-rw-r-- 1 tyl tyl 10772836 Jul 7 16:31 webster.zstd $ time ./lzfse-master/build/bin/lzfse -decode -i webster.lzfse -o /dev/null real 0m0.127s user 0m0.112s sys 0m0.012s $ time ./zstd-master/programs/zstd -d webster.zstd -o /dev/null webster.zstd : 41458703 bytes real 0m0.116s user 0m0.112s sys 0m0.000s LZFSE's -h option doesn't show a flag to tweak compression. Zstd's default -1 compression is super-fast, but obviously not optimal. Its -8 is the closest I got to LZFSE's compression speed; its -4 was the closest to LZFSE's compression ratio, with a speed of 0m0.527s real compression, 0m0.101s real decompression.
- tmd83 10y agoThanks for this. Down the thread I was asking exactly for this. And it seems Zstd is significantly better. We would of course need a wider range of data to really judge this. One thing could be that apple's work started before or in parallel with Zstd and didn't know that this was going to be better. But the problem remains we might end up with a compression algorithm widely used (by virtue of being pushed by apple) while another very similar and better algorithm waiting to come to mainstream. Now if there isn't something special about LZFSE in terms of power usage (beyond faster operation reduces power usage) it would be best if once Zstd is really proved to be solid they phase out LZFSE and start pushing this. Don't really think this would happen. It also seems that Zstd has some dictionary support and so an ever bigger question is whether Zstd can actually replace brotil which probably has a much bigger impact. I really like the idea of Zstd being available everywhere if all the numbers are as good as they seem to be.
- skreuzer 10y agoIf anyone on FreeBSD wants to try this I just added a port under archivers/lzfse http://www.freshports.org/archivers/lzfse/ http://www.freshports.org/archivers/lzfse/
- ausjke 10y agoA quick test resutl(zip a 1.5GB file): lzfse: real 1m44.481s user 1m17.956s sys 0m2.852s lz4: real 0m28.136s user 0m1.200s sys 0m2.240s lz4 is much faster somehow. The final size are very close.
- klodolph 10y agoIt's not terribly useful for most applications to test compression speed. The only applications I can think of where this is relevant is data backup and archiving. There are two typical speed benchmarks you want to do. For the "compress once, decompress many times" situation, benchmark the time it takes to decompress and ignore compression time. For the "compress once, decompress once" situation, add the compression and decompression times. The first situation is common for distributing packages and static assets, the second situation is common for distributing dynamic assets.
- eye2sky 10y agoFor the second situation, I prefer the compress/transmit/decompress metric (as a function of transmit pipe speed), as described here: http://fastcompression.blogspot.com/p/compression-benchmark.html http://fastcompression.blogspot.com/p/compression-benchmark....
- microcolonel 10y agoIt's nice to see that we will be able to at least decode these archives. Though I think for new software people are better off using zstd if they're looking for this set of performance characteristics.
- deleted 10y ago[deleted]
- Negative1 10y agoI'm not fully up on the latest and greatest in compression technologies but my go to format these days is usually 7zip which I believe is just a container that uses LZMA. For whatever reason *nix people seem to hate it even though I get much better compression with it than tarballs, zlib/zips. Is there a similar container format that will or does use LZFSE? And how much better is it than 7zip/LZMA?
- wmf 10y agoThe Unixy version of LZMA is called XZ. Unix people prefer tar over zip, probably for historical/tribal reasons. There are really three different compression "markets"; LZMA/XZ provides strong compression while LZFSE provides moderate or light compression so they don't really compete.
- macintux 10y ago> Unix people prefer tar over zip, probably for historical/tribal reasons. To this day I refuse to use the z argument to tar. Packaging and compressing are two different operations, and this is why the UNIX gods created pipes. And also I'm a stubborn old fart.
- tracker1 10y agoJust a side-comment, it would be really nice if we could get the browser vendors to support a newer compression algorithm beyond gzip and deflate. I know there have been a couple others implemented, but nothing that has been implemented by multiple browsers that has stuck. Really need to get MS, Google, Apple and Mozilla to come together on this. Should be patent free.
- j_s 10y agoI think Brotli is getting there, with support in Firefox and Chrome so far. https://samsaffron.com/archive/2016/06/15/the-current-state-of-brotli-compression https://samsaffron.com/archive/2016/06/15/the-current-state-...
- tracker1 10y agoThanks for this... the last I checked was a few months ago, as I coulldn't believe we were still limited to deflate/gzip... I'm somewhat surprised lzma didn't get broader support earlier on though. mental note, setup a new dokku box, and try getting this setup...
- kazinator 10y agoOpen source; but is it patent-free?
- technion 10y agoFor anyone wondering, I've tried throwing afl-fuzz at this. It's only been a few hours, but as yet, nothing has turned up.
- 0x54MUR41 10y agoSorry, I think this comment is out of topic. I don't know why Apple put this separated with their open source projects on https://github.com/apple https://github.com/apple.