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

121–130 of 219 posts

Re: Apple Open-Sources its Compression Algorithm LZFSE

#121

Post by mschuster91 »

vog wrote: post #111
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 pr…

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

Re: Apple Open-Sources its Compression Algorithm LZFSE

#123

Post by athenot »

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 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 some web project, I would use fully explicit variable names.

This falls under the category of "know the audience for whom you are writing code".

Re: Apple Open-Sources its Compression Algorithm LZFSE

#124

Post by josephg »

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…

Hey, someone found those noise functions I ported to JS a few years ago!

Sorry for not referencing the original code. The java version I translated from is here: http://webstaff.itn.liu.se/~stegu/simplexnoise/SimplexNoise....

And the paper describing the algorithm is here: http://webstaff.itn.liu.se/~stegu/simplexnoise/simplexnoise....

Glad it was useful to you!

Re: Apple Open-Sources its Compression Algorithm LZFSE

#125

Post by cmiller1 »

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

In some of these lines I feel like I'd prefer to see more parenthesis. Sure, I can figure out what is happening here:

    } else if (D
but if it were grouped with a few more parenthesis it would take a little less time for me to grok it.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#126

Post by vog »

mschuster91 wrote: post #121
vog wrote: post #111

Earlier quoted context omitted.

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

> 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 uninstalling, upgrading and related operations are the task of a package manager, not a build script.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#127

Post by dietrichepp »

randlet wrote: post #97
nicky0 wrote: 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.

The more verbose name is infinitely more preferable to me. If I am tasked one day with doing some maintenance on this code and have never encountered it then at least I have a hint that I should be researching the aquatic properties of mariachi bands.

I would have a hard time with that, the long names hide the structure. Know your audience. Do you expect future maintainers for your compression algorithm to be people with knowledge of compression algorithms? Or do you expect them to be random programmers off the street?

Re: Apple Open-Sources its Compression Algorithm LZFSE

#128

Post by tmd83 »

awalton wrote: post #8
DiabloD3 wrote: post #6

So... basically a clone of LZ4?

Basically an Apple-specific reimplementation of Zstd: https://github.com/Cyan4973/zstd

Thats kind of what I thought when it came out. Zstd is closest to it both in terms of characteristic and concept. It would be nice to have a head to head comparison between the two.

Zstd & LZ4 being the work of single developer is amazing though.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#129

Post by josephg »

goldenkey wrote: post #55
lokedhs wrote: post #33

Earlier quoted context omitted.

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…

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.

Re: Apple Open-Sources its Compression Algorithm LZFSE

#130

Post by dietrichepp »

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.
Post reply on HN