Live data from Hacker News

Apple Open-Sources its Compression Algorithm LZFSE

infoq.com

71–80 of 219 posts

Re: Apple Open-Sources its Compression Algorithm LZFSE

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

They open sourced it for you to clean up!

Re: Apple Open-Sources its Compression Algorithm LZFSE

#72

Earlier quoted context omitted.

I suspect any runtime, at all, would be too much overhead.

There isn't a Rust runtime, though, in the sense that you seem to be implying. There's a standard library, which is what I assumed they meant.

Yes, I was using it to describe the standard library. C and C++ are both described as having a runtime, and Rust has one in the same sense. In any case I would consider the code needed for handling stack unwinding to be worthy of the name runtime (small though it may be).

I understand it doesn't have a runtime in the way a JIT'ed or GC'ed language has a runtime, but it's a runtime nonetheless.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#74

Earlier quoted context omitted.

No function call overhead. Makes sense as long as you stay in the same state-machine. This thing doesn't have to be pretty. It has to be fast. Who cares for any oo-written implementation that takes half a hour to do the same job?

But there is no function call overhead right? Replacing goto OUT_FULL; with return q1; would seem to be faster right? No need for a goto, just invoke return. What am I missing?

There is some. A few register need to be assigned, and everything else gets pushed/copied onto the stack. Then you jump to a location and copy everything back off the stack.

This doesn't take many cycles, but it does take some. While a GOTO is just a jump.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#75

Earlier quoted context omitted.

Which bits of the Rust runtime(?) do you think are too high overhead for this?

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 as good as C, but a lot better than default Rust with just a few tweaks.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#76
post #70

Earlier quoted context omitted.

I suspect any runtime, at all, would be too much overhead.

This C code doesn't use the C library. Code like this in Rust wouldn't engage with any part of the Rust standard library either. There's no runtime work to be done, in either language.

There is still an overhead in terms of executable size, unless you use #![no_std]. This environment is not easy to code in; it doesn't even have heap allocation.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#77

Earlier quoted context omitted.

Which bits of the Rust runtime(?) do you think are too high overhead for this?

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…

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

Re: Apple Open-Sources its Compression Algorithm LZFSE

#78
post #61
post #59

Earlier quoted context omitted.

OK but which is more readable ... (I know it's a bit silly, I juts made up names) } else if (D >= (1 34) { } else if (DirectWeightingFactor >= HUYGENS_LIMIT || MariachiBand == 0 || (xylemNonce + STANDARD_PZSH_INCREMENT) + MariachiBand > SWIM_RATE_B) { I guess your opinion differs to mine. I like the one that looks like math.

What about a middle ground? } else if (D >= HUYGENS_LIMIT || M == 0 || (x+3)+M > SWIM_RATE_B)

And then somebody else will write angry hackernews comment how code is abysmal because it mixes in single char names. ;)

Re: Apple Open-Sources its Compression Algorithm LZFSE

#79

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

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.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#80
post #77

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…

> 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 through that whole page, use unstable features (alloc_system) that condemn you to the nightly, and download and compile musl. This is a huge, brittle pain at the moment, and far from obvious to anyone who comes upon Rust and is thinking of building a C-compatible library using it.

Post reply on HN