Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Apple Open-Sources its Compression Algorithm LZFSE

infoq.com

Post reply on HN
Print view View original

141–150 of 219 posts

Re: Apple Open-Sources its Compression Algorithm LZFSE

#141

Post by jcranmer »

josephg wrote: post #129
goldenkey wrote: post #55

Earlier quoted context omitted.

Seems pretty well commented. There are definitely worse examples. I think you are underestimating the amount of temporary calculations that most mathematical formulas or algorithms require. It's actually a good thing to see so many vars because the variable names combined with the comments make more sense. Any js packer will most certainly get rid of the redundancy of memory allocations, so I'd say the superfluous va…

When I wrote it I ran that JS code through several rounds of benchmarking to try and eke out some more performance. One of the tweaks I tried was collapsing all the calculations together to use fewer variables to see if that would make it faster. Performance was totally unchanged either way. Looks like V8's optimizer eats those vars for breakfast.

In general, at the optimization IR level of any decent compiler or JIT, most straight-line code gets reduced into some form of expression DAG for common subexpression elimination and other similar optimizations, meaning that

    var x = a + b;
    call(x + c);
and

    call(a + b + c);
would be literally indistinguishable.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#142

Post by michel-slm »

vog wrote: post #126
mschuster91 wrote: post #121

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

I do that, and then use GNU Stow to manage the symlinks. That way I only need to add a single directory to PATH and to library paths

Re: Apple Open-Sources its Compression Algorithm LZFSE

#143

Post by twitch_checksum »

dchest wrote: post #41
shmerl wrote: post #25

Earlier quoted context omitted.

They are very much into NIH, seemingly out of paranoid fear of patent attacks (though not sure how it can protect them).

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

Re: Apple Open-Sources its Compression Algorithm LZFSE

#144

Post by steveklabnik »

johncolanduoni wrote: post #80
nmjohn wrote: post #77

Earlier quoted context omitted.

> A static library is a whopping 2.4 MB. The comparable number for C are 4K and 800 bytes respectively. It is possible to significantly optimize that number [0]. Not that binary size is not an issue, but rather 2.4mb vs. 4kb is not an apples to apples comparison [0]: https://lifthrasiir.github.io/rustlog/why-is-a-rust-executab...

The article you linked is doing all of this with a binary. Last time I tried something like this with Rust, there were a lot more obstacles to cutting down this overhead with a library than a binary. Also note that towards the bottom he cuts out libstd, which loses any form of dynamic memory allocation, as well as a significant chunk of Rust's usability advantage. The biggest factor however is that you have to read t…

> as well as a significant chunk of Rust's usability advantage.

What bits are you thinking of here? Just curious, as I do a lot of no_std work, and don't feel that way, and am probably blind to it :)

Rust 1.10, coming out later today, has a new crate type that removes Rust-specific metadata for dynamic libraries, by the way, making them a bit smaller for this kind of case.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#145

Post by steveklabnik »

vertex-four wrote: post #75
johncolanduoni wrote: post #69

Earlier quoted context omitted.

Using rust 1.9.0, an empty (save for a function that adds two u32s) standalone dynamic library built in release mode on OS X is 1.6 MB. A static library is a whopping 2.4 MB. The comparable number for C are 4K and 800 bytes respectively. Asking every client of the compression library to pull in that much overhead would likely make it rather unpopular. Until Rust gets better at eliminating unnecessary parts of the run…

My understanding is that the majority of that is jemalloc, libbacktrace, and glibc. jemalloc can be replaced with system malloc easily, libbacktrace can be removed by setting the compiler to interpret panics as aborts (which you need to do in a library used by C anyway, really), and glibc can be replaced with musl. This can bring binary size down to about 160kb for a binary which just does printf!(). Still not quite…

  > (which you need to do in a library used by C anyway, really)
You can also use panic::catch_unwind at the boundary too, it depends on what you want to do.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#146

Post by rusanu »

eru wrote: post #109
gigatexal wrote: post #31

Earlier quoted context omitted.

I wonder why they use goto statements instead of just returning q1 like the statement evaluates to.

They seem to like a style that has rather constrained use of `return' (but uses deliberate amounts of goto instead). Not sure why.

I assume is "one return only per function" rule http://programmers.stackexchange.com/questions/118703/where-...

Re: Apple Open-Sources its Compression Algorithm LZFSE

#147

Post by tmd83 »

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…

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

Re: Apple Open-Sources its Compression Algorithm LZFSE

#148

Post by lorenzhs »

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.

Are you sure? This does not match my experience. Rather, compilers inline stuff if they think it's a good idea, and treat the "inline" keyword more like a hint.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#149

Post by [deleted] »

klausa wrote: post #105
cooper12 wrote: post #99

Oh 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)

There's a way to make this point without being an asshole about it.

[deleted]
Post reply on HN