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

111–120 of 219 posts

Re: Apple Open-Sources its Compression Algorithm LZFSE

#111

Post by vog »

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.

> I really appreciate the presence of a no-nonsense Makefile.

Indeed, the current version of their Makefile is a great example of how to write a simple yet portable Makefile:

https://github.com/lzfse/lzfse/blob/33629bc65f4b356072c9a7d5...

> No autoconf, no pkgconfig, just plain and simple make.

While I agree with your sentiment, I believe that your statement about pkg-config goes a bit over the top.

Yes, the LZFSE project doesn't use pkg-config, but it also doesn't have any library dependencies. There's not a single "-l" argument in the linker flags.

If it had, I would prefer pkg-config over any other mechanism, as that is right now the best "simple yet portable" method of defining library dependencies.

Pkg-config is especially handy when it comes to cross-compiling, or when you have a special need for a static build instead of shared libraries.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#112

Post by Mao_Zedang »

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)

I thought it was funny, dont be so joyless.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#113

Post by satysin »

barsonme wrote: post #28
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

Blows my mind that people can come up with this stuff. I'm assuming they came up with the mathematical proofs first and translated that into code, so that has something to do with it, correct? It looks a lot like some crypto algorithms which are a nearly direct translation of the mathematical formulas. It's not that it's incredibly difficult to follow, but it's just very "math like".

Compression, encoding, encryption, etc. is more maths and computer science than "programming".

Of course it technically is programming don't get me wrong but it isn't "make a CRUD app with a simple UI" kind of programming.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#114

Post by satysin »

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…

I would agree if this were a "normal" project but it isn't. It is a compression algorithm which is essentially an implementation of a mathematical proof wrapped in some I/O functions.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#115

Post by valarauca1 »

xxs wrote: post #90
valarauca1 wrote: post #74

Earlier quoted context omitted.

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.

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.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#117

Post by finchisko »

madeofpalk wrote: post #116
finchisko wrote: post #22

Waiting for first guy who take this implementation and run it through emscripten so we can actually use it in client -> server communication, eg sending compressed json payloads to the server.

You mean... like gzip?

yeah, but also the opposite direction client -> server. client will send compressed data to server use LZFSE. Kind of nice extension to HTTP protocol, which only supports compression from server to client.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#118

Post by ascagnel_ »

finchisko wrote: post #85
panic wrote: post #26

Earlier quoted context omitted.

Is running (not to mention downloading/parsing/compiling) emscriptened decompression code really that much faster than just transferring the data? I think a better strategy would be to add support for LZFSE to the browsers themselves.

Native support in browser would be appreciated. But I was also thinking about nodejs server side decompressing via native or emscripten transpiled module.

A quick reading of the license[0] shows that there's no legal stumbling blocks to the code showing up in browsers, but the license doesn't mention anything about patents.

[0] https://github.com/lzfse/lzfse/blob/master/LICENSE

Re: Apple Open-Sources its Compression Algorithm LZFSE

#119

Post by gutnor »

douche wrote: post #100
userbinator wrote: post #95

Earlier quoted context omitted.

"It's 2016." So what ? Have people lost the ability to use abbreviations? One letter is perfectly fine because they are abbreviations, the purpose of which you should recognise immediately if you understand the tiniest bit of what LZ algorithms do and the concepts surrounding them. D = distance, L = long-distance, M = medium-distance. You may ask, "Why and what is q"? By only looking at the fragment posted, where q i…

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 anyone who doesn't have the paper handy

You are supposed to have the paper handy. Either you know the paper by heart, or you are actually learning the paper and look at the implementation. Otherwise you really have nothing to do in this piece of code.

Even more mundane codebase are like that. Variable are named in the context of the project. If you have no familiarity with the project variable "user" or "u" means exactly the same to you: nothing.

The difference is that generally regular project are huge in size but simple, while filesystem, compression/encryption algorightm, trading algorithm are tiny but extremely complex. In the former, you use more descriptive naming because people will only have a high level knowledge of the spec. In the later, there is no difference between spec and code, extreme familiarity is necessary to touch the code and naming convention crutches are simply unnecessary.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#120

Post by athenot »

lokedhs wrote: post #33
barsonme wrote: post #28

Earlier quoted context omitted.

Blows my mind that people can come up with this stuff. I'm assuming they came up with the mathematical proofs first and translated that into code, so that has something to do with it, correct? It looks a lot like some crypto algorithms which are a nearly direct translation of the mathematical formulas. It's not that it's incredibly difficult to follow, but it's just very "math like".

That is my experience. Maths people are not renowned for their ability to write readable or maintainable code. I recently needed an implementation of the Simplex Noise algorithm (that I could port to Common Lisp). I ended up using this one, which works but the code certainly does nothing to help understanding: https://github.com/josephg/noisejs/blob/master/perlin.js Note that the Javscript implementation is also a po…

> Maths people are not renowned for their ability to write readable or maintainable code.

I think it's because in that circle of heavy math coding, there are a different set of well-understood abstractions and shortcuts.

It's no different than saying front-end web developers are not writing readable code because they use $(...) instead of elementMatchingSelector(...) or use functions like xhr() instead of xmlHTTPrequest(). Node.js developers don't think twice about the mechanics of callbacks nor to Erlang developers have any mental block about async message semantics.

Each field has a lingo that has evolved over time, and those who have been in a field for longer tend to make more shortcuts because they are manipulating a concept for the 100th time and are well versed in it.

Post reply on HN