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

151–160 of 219 posts

Re: Apple Open-Sources its Compression Algorithm LZFSE

#151

Post by developer2 »

dozzie wrote: post #133
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!

> Yet it forgets the MOST important thing: make uninstall. Why it forgets that? It's not the job of a library build system to install or uninstall things in your system . It's a job for your system's package manager. Makefile that has a target (historically called "install") that puts things in appropriate places in a chroot-like manner is just good enough.

This disregards a common use of the Makefile: compiling software from source, bypassing the use of a package manager in the first place. Yes, software devs should be providing a Makefile that is friendly for package managers to wrap. But the best software provides a Makefile usable on all platforms it supports, without the expectation that a package manager will be involved.

Sure, you can install each compiled package to its own subdirectory under /usr/local/, but then their binaries are not located in a default PATH. Whether performed accidentally or intentionally, installing to /usr/local/ prefix (/usr/local/bin/, etc.), should not result in having no way of automating an uninstall of those files.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#152

Post by muizelaar »

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…

https://quixdb.github.io/squash-benchmark/unstable/ also seems to confirm this.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#153

Post by 72deluxe »

johncolanduoni wrote: post #32
pilif wrote: post #29

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

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

May I ask what is not memory safe about C++ in this situation? I am talking C++11, not the widespread C++98 stuff we find everywhere.

Or why not use local variables that are guaranteed to be cleaned up?

I suspect Apple would have an alternative to write this in Swift, but that would probably have speed implications (I am guessing).

Re: Apple Open-Sources its Compression Algorithm LZFSE

#154

Post by klodolph »

ausjke wrote: post #139

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

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

Re: Apple Open-Sources its Compression Algorithm LZFSE

#155

Post by etatoby »

drinchev wrote: post #15
nodesocket wrote: post #9

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

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

That looks like a host of buffer overflow vulnerabilities waiting to happen.

I think I'll stick with zlib.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#156

Post by PeCaN »

joeblau wrote: post #79
drinchev wrote: post #15

Earlier 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 feel like the main thing that makes this look crazy is the variable naming and bit shifting. If someone saw this program with descriptive variable names and array operations, it would probably look less daunting.

Eh. I feel like long variable names would obscure the algorithm. And bit shifting and array operations aren't interchangeable….

C just tends to look like line noise for numerical algorithms sometimes.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#157

Post by dozzie »

developer2 wrote: post #151
dozzie wrote: post #133

Earlier quoted context omitted.

> Yet it forgets the MOST important thing: make uninstall. Why it forgets that? It's not the job of a library build system to install or uninstall things in your system . It's a job for your system's package manager. Makefile that has a target (historically called "install") that puts things in appropriate places in a chroot-like manner is just good enough.

This disregards a common use of the Makefile: compiling software from source, bypassing the use of a package manager in the first place. Yes, software devs should be providing a Makefile that is friendly for package managers to wrap. But the best software provides a Makefile usable on all platforms it supports, without the expectation that a package manager will be involved. Sure, you can install each compiled packag…

> This disregards a common use of the Makefile: compiling software from source, bypassing the use of a package manager in the first place.

Most of the executions (those actually used in the wild) of this strategy are quite stupid. Add to that the fact that building packages with distribution's tools is quite easy, and now on top of that add fpm, which produces terrible packages and should be banned for upstream maintainers, but for a desktop installation they're perfectly usable, and checkinstall, which is more than fifteen years old.

> Yes, software devs should be providing a Makefile that is friendly for package managers to wrap.

After what I said to steveklabnik (https://news.ycombinator.com/item?id=12014815): build script (whatever it is, it doesn't need to be makefile) should never touch network when building the project and should not expect libraries in any particular place (especially not the directory with the sources nor $HOME/.whatever). This is enough for build script to be friendly towards package managers and none of the package managers expect anything more from the source tarball.

> But the best software provides a Makefile usable on all platforms it supports, without the expectation that a package manager will be involved.

Yes, of course. But package managers really don't expect anything more than a good build script should provide: no network, no hardcoded library paths, only building the artifacts from the locally accessible sources. And maybe a target that puts the artifacts in appropriate places under $DESTDIR, but this is often optional. There's nothing more than one could do by hand, installing stuff into /opt/$someproject directory, so it can be safely removed altogether, and add symlinks to /usr/local/bin, so they're in typical $PATH.

Package managers actually springed from automating what people did manually just before.

> Whether performed accidentally or intentionally, installing to /usr/local/ prefix (/usr/local/bin/, etc.), should not result in having no way of automating an uninstall of those files.

Let's not make the users mentally disabled people. Do we really need to protect them from all their mistakes? What would be next, adding a recycle bin for files removed with `rm'?

OK, I'm somewhat exaggregating here. But where's the line of that protection?

Re: Apple Open-Sources its Compression Algorithm LZFSE

#158

Post by jacobolus »

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’d love to see Charles Bloom add LZFSE and ZSTD to his “pareto frontier” charts: http://cbloomrants.blogspot.com (read down a few posts)

Re: Apple Open-Sources its Compression Algorithm LZFSE

#159

Post by PeCaN »

johncolanduoni wrote: post #32
pilif wrote: post #29

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

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

> At the moment, what's their real alternative?

Ada? Chapel? ATS? D if you avoid the GC?

> That said, I agree this isn't acceptable C code for something that runs on untrusted data while using tons of pointer arithmetic.

Why not? It's not the prettiest code ever, but it gets the point across of what's going on.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#160

Post by Someone »

a_imho wrote: post #43
Someone wrote: post #16

Earlier quoted context omitted.

That'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)

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 changes in power usage.

Post reply on HN