Apple Open-Sources its Compression Algorithm LZFSE • Hacker News Board

Re: Apple Open-Sources its Compression Algorithm LZFSE

#201

Post by catwell » Fri, Jul 08, 2016, 6:47 AM UTC

nabla9 wrote: post #103

willvarfar wrote: post #37

Earlier quoted context omitted.

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…

When implementing complex algorithm, this kind of code is usually easiest to understand. When you look at the code, you use the paper that describes the algorithm as documentation. Using same short one letter variable names in the code and paper makes understanding much easier. The thing I hate most is when the the paper uses 1-based numbering and the programming language uses 0-based numbering. We should settle for…

Or use 1-based programming languages :) I have implemented several algorithms from papers in Lua and that played in my favor more than once.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#202

Post by xxs » Fri, Jul 08, 2016, 7:18 AM UTC

valarauca1 wrote: post #115

xxs wrote: post #90

Earlier quoted context omitted.

the compilers are free to optimize. Creating a stack frame for each function is trivially avoided by inlining (esp. trivial for non-polymorph call sites)

It depends. In GCC/MSVC will only (attempt to) inline what you mark as inline. Then MSVC has a keyword which forces inlining. Unless you set a flag which tells the compiler to inline what ever it wants . But that being said Microsoft has a non-POSIX x64 ABI designed to allow better in-lining. How inlining works starts to dive pretty deep into the compiler rabbit hole.

Exported functions are entirely different than vast majority of the code, the exported ones do need call conventions, so they can be linked. But it's entirely not true that ONLY functions marked as 'inline' would be inlined. You can also direct GCC to try to integrate all “simple enough” functions into their callers with the option -finline-functions (includeded in -O3).[0]. O2 includes inline small functions [1]:

[0]: https://gcc.gnu.org/onlinedocs/gcc/Inline.html [1]: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html

Re: Apple Open-Sources its Compression Algorithm LZFSE

#203

Post by espadrine » Fri, Jul 08, 2016, 7:48 AM UTC

Someone wrote: post #190

espadrine wrote: post #136

I 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…

I’m not that comfortable with Xcode, but I just built two versions of this tool, one direct from GitHub, one (called lzfse2) that calls the Compression library on Mac OS X. Typical timings on my system are: > time ./lzfse -encode -i webster -o webster.lzfse real 0m0.945s user 0m0.864s sys 0m0.062s > time ./lzfse2 -encode -i webster -o webster.lzfse2 real 0m0.803s user 0m0.715s sys 0m0.072s > time ./lzfse -decode -i w…

> Worryingly, the two versions also produce different files

That is actually pretty common. I would guess the version you have in macOS is an older version. They may have tweaked the algorithm to deliver slightly better compression at the expense of speed, which is always the tradeoff in this field.

On the other hand, I would not be surprised if they prepared special tweaks in their internal version to better support arm64. Strategically, Apple seems to believe that people will stick with building for their App Store if they are pushed to write non-cross-platform code.

(Oddly enough, LZFSE/LZVN seems well-suited for file system compression on hard drives, but here again, Yann Collet wins with its LZ4's superior compression speeds, which impact write speeds.)

Re: Apple Open-Sources its Compression Algorithm LZFSE

#204

Post by astrange » Fri, Jul 08, 2016, 7:58 AM UTC

gsnedders wrote: post #89

svckr wrote: post #17

With 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.

> 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…

This 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".

Re: Apple Open-Sources its Compression Algorithm LZFSE

#205

Post by astrange » Fri, Jul 08, 2016, 8:04 AM UTC

valarauca1 wrote: post #115

xxs wrote: post #90

Earlier quoted context omitted.

the compilers are free to optimize. Creating a stack frame for each function is trivially avoided by inlining (esp. trivial for non-polymorph call sites)

It depends. In GCC/MSVC will only (attempt to) inline what you mark as inline. Then MSVC has a keyword which forces inlining. Unless you set a flag which tells the compiler to inline what ever it wants . But that being said Microsoft has a non-POSIX x64 ABI designed to allow better in-lining. How inlining works starts to dive pretty deep into the compiler rabbit hole.

Functions don't need to follow the ABI unless they're externally visible. If you use -fvisibility=hidden GCC will do whatever it wants for each function as it sees fit.

Interprocedural register allocation can work better than inlining too, because it keeps the code size smaller, and direct calls have almost no speed penalty.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#206

Post by espadrine » Fri, Jul 08, 2016, 8:34 AM UTC

eridius wrote: post #192

wmf wrote: post #168

Earlier quoted context omitted.

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.ycomb…

Surely LZ4 is not in fact more energy efficient, otherwise Apple would be pushing LZ4 as the algorithm to use on mobile devices instead of recommending LZFSE. If you see in that previous discussion, I was asking the same questions there and got no real answer. It looks to me like nobody (outside of Apple) has actually tested the energy efficiency.

LZ4 is a format. All you can say about how energy efficient a format is, is by looking at the average speeds of its implementations. However, zlib for instance (a DEFLATE library) is more energy efficient than zopfli (another DEFLATE library), just by virtue of taking less CPU cycles to crunch data.

There is in fact a very high correlation between CPU cycles and energy efficiency, since compression algorithms don't sit idle and use roughly the same instructions. In fact, Yann Collet's Zstd uses the same principles as LZFSE, as both were sprouted from Jarek Duda's research: http://arxiv.org/abs/1311.2540.

The reference LZ4 implementation is absolutely more energy efficient than LZFSE, and in fact Apple does push for its use by offering it in its compression library. However, it tends not to compress as well as both LZFSE and Zstd. For 4G or WiFi (or even broadband), the time lost by transferring more data is not compensated by the time won by decompressing it faster, resulting in much slower downloads than even zlib. LZ4 is still relevant for higher speeds, such as those offered by magnetic hard drives. (Beyond a certain speed, such as for SSDs, compression no longer offers a benefit, but you might be ok with the slowdown given that you win drive space.)

There is a separate discussion to be had about the fact that the open-sourced LZFSE reference implementation is not the one they use (which explains how little they touched it since), as it does not even have ARM-specific code. Also, LZFSE does not claim to be patent-unencumbered. LZ4 and Zstd do have optimized code for ARM.

All in all, it is not a stretch to assume that Apple benefits from this FUD, which explains why there is no comparative benchmark anywhere to be found on their GitHub or in their documentation. It really looks like Zstd is better all around.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#207

Post by a_imho » Fri, Jul 08, 2016, 11:18 AM UTC

Someone wrote: post #160

a_imho wrote: post #43

Earlier quoted context omitted.

Could 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.

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 chan…

Do you mean by extrapolating from executed instructions? It would be very much dependent on the architecture then. It would be nice to read some independent studies and experiments, after the recent events I take any manufacturer claim on consumption with a pinch of salt.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#208

Post by 0x54MUR41 » Fri, Jul 08, 2016, 2:00 PM UTC

Sorry, 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.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#209

Post by jamessb » Fri, Jul 08, 2016, 3:41 PM UTC

athenot wrote: post #123

douche wrote: post #100

Earlier quoted context omitted.

It's not like you have to pay a dime for every character in your source code. With halfway-decent autocomplete, longer identifiers are easier to use than shorter ones, I've found. I'd hope you'd at least put a comment header to explain what the parameters actually are for anyone who doesn't have the paper handy, or god forbid, used a paper implementing the same thing using different nomenclature.

For math it's the other way around: long identifiers make things harder to read. When reading the code, the pattern of operators is what really matters; variables happen to be plugged into them. For example, any person with a modicum of physics background will recognize the following as a kinetic energy calculation, even if I use random letters for the variables. X = (a * b^2)/2 But if I throw that in a codebase for…

For example, any person with a modicum of physics background will recognize the following as a kinetic energy calculation, even if I use random letters for the variables.

Someone with a physics background might assume that X is the kinetic energy of an object with mass a and velocity b. Or they might assume that X is the displacement of object after having acceleration a for a time b, having initially been at rest. The latter is perhaps more reasonable, since then the choice of two of three three variable names (x and a) is conventional.

A reason why single-letter variable names are practical is that there are strong conventions about what particular variables might represent: eg. start of the roman alphabet is constants, end of the roman alphabet is variables, capital letters are matrices, many letters in the roman and Greek alphabets have one (or a few) common meanings.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#210

Post by legodt » Fri, Jul 08, 2016, 4:44 PM UTC

dietrichepp wrote: post #130

tlrobinson wrote: post #60

Well, what's the Weissman score?

The 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.

I 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?