[deleted]
Apple Open-Sources its Compression Algorithm LZFSE
161–170 of 219 posts
Re: Apple Open-Sources its Compression Algorithm LZFSE
#162Earlier quoted context omitted.
Excerpt from the link : if (D == D_prev) { if (L == 0) { *q++ = 0xF0 + (x + 3); // XM! } else { *q++ = (L >8 in 0..5 *q++ = (D >> 8) + (L = (1 34) { // Long dist *q++ = (L > 2) + (L
I've never seen this code base before, but this makes straightforward sense to me as I do keep my hand in with compression software, and I don't anticipate others who works with compression algorithms in general would have any trouble. It looks just like the style of code in all the other fast LZ codebases. They are all in this style. The "non-aligned access OK" comment litter is presumably to silence an LLVM perform…
I agree. The only questionable part is the stuff like
*(uint16_t *)q = D;
q += 2; // non-aligned access OK
*(uint32_t *)q = literal;
memcpy(q, &D, sizeof(uint16_t));
q += 2; // non-aligned access OK
memcpy(q, &literal, sizeof(uint32_t));
Re: Apple Open-Sources its Compression Algorithm LZFSE
#163Earlier quoted context omitted.
This 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://developer.apple.com/library/ios/documentation/Perfor...
Well, 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 ), to prove that it could be transformed into something…
Thanks for the insight!
Re: Apple Open-Sources its Compression Algorithm LZFSE
#164It'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 optim…
We detached this subthread from https://news.ycombinator.com/item?id=12047902 and marked it off-topic.
Re: Apple Open-Sources its Compression Algorithm LZFSE
#165Earlier quoted context omitted.
You'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.
I 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.
I suspect the downvotes are because code readability is a complex, subtle topic that often gets reduced to flamewars by people who are sure they know ‘the’ right way to do things.
Code readability is relative to the reader, the programming language, and the conventions of a codebase. That's a lot of things to be relative to! Knowing that ought to put speed bumps on the way to dismissing code one isn't familiar with.
I remember having a reaction years ago on seeing some of P.J. Plauger's C++ standard library code. I think I burst out laughing and said I'd fire anyone who wrote code like that for me. Years of subsequent experience have brought multiple layers of understanding how wrong I was.
Re: Apple Open-Sources its Compression Algorithm LZFSE
#166Earlier quoted context omitted.
Excerpt from the link : if (D == D_prev) { if (L == 0) { *q++ = 0xF0 + (x + 3); // XM! } else { *q++ = (L >8 in 0..5 *q++ = (D >> 8) + (L = (1 34) { // Long dist *q++ = (L > 2) + (L
I've never seen this code base before, but this makes straightforward sense to me as I do keep my hand in with compression software, and I don't anticipate others who works with compression algorithms in general would have any trouble. It looks just like the style of code in all the other fast LZ codebases. They are all in this style. The "non-aligned access OK" comment litter is presumably to silence an LLVM perform…
I've also never seen that code but it's very readable for me, just based on the snippet. It's supposed to encode the information tuple and store it as the next entry of variable length on the position pointed by q. Every tuple ends with the 32-bit literal, but what comes before depends on the size of the displacement, and of course, smaller displacements need less bytes.
Re: Apple Open-Sources its Compression Algorithm LZFSE
#167I 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/Cyan4973/zstd Edit: here is a quick comparison I did on Linux with P…
Can you measure energy impact? Apple has specifically said that LZFSE is the right choice when you want lower energy impact, so doing benchmarks of LZFSE against other algorithms is kind of meaningless when you don't measure one of the key metrics. Of course, I'm not sure offhand how to measure energy impact, but Activity Monitor displays energy impact numbers so there must be some way to measure it.
Re: Apple Open-Sources its Compression Algorithm LZFSE
#168I 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/Cyan4973/zstd Edit: here is a quick comparison I did on Linux with P…
Can you measure energy impact? Apple has specifically said that LZFSE is the right choice when you want lower energy impact, so doing benchmarks of LZFSE against other algorithms is kind of meaningless when you don't measure one of the key metrics. Of course, I'm not sure offhand how to measure energy impact, but Activity Monitor displays energy impact numbers so there must be some way to measure it.
Based on Apple's own presentation it looks like energy efficiency is pretty proportional to performance, so it's very likely that a faster algorithm (e.g. LZ4) would also be more efficient. In modern "braniac" processors, 90% of the energy is spent on overhead and doesn't vary based on instruction mix. Memory accesses consume both energy and time, so fewer are better.
(From the previous discussion: https://news.ycombinator.com/item?id=11944975 )
Re: Apple Open-Sources its Compression Algorithm LZFSE
#169I'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?
Re: Apple Open-Sources its Compression Algorithm LZFSE
#170Earlier quoted context omitted.
> Indeed, the current version of their Makefile is a great example of how to write a simple yet portable Makefile: Yet it forgets the MOST important thing: make uninstall. Nothing worse than software where I have to reverse engineer a makefile in order to uninstall!
I don't trust "make uninstall" anyway. Instead, I usually put self-compiled packages into separate directories, such as: make install INSTALL_PREFIX=/opt/lzfse or make install INSTALL_PREFIX=$HOME/.../lzfse Uninstalling is then as simple as: rm -r /opt/lzfse For convenience, I either add /opt/lzfse/bin to $PATH , or create a symlink from /opt/lzfse/bin/lzfse to /usr/bin/lzfse . More generally, I believe that uninstal…
Good luck with getting pkg-config to recognize your include files automatically, for example. Or the good old "man" utility.
Alternative: maintain a HUUUUUGE list of xPATH env variables, and update them every time you recompile something and change the directory in the process. Oh, and hope that other people's Makefiles are intelligent enough to not mess up shit (e.g. use headers from system, and library .so files from your own compile)...