We are bank of hackers based in the UK, US, Canada we offer services such as school grades change, DDOS, database hack, credit, criminal records, bank transfer, social network hack, emails, password retrieval and all forms of hack, contact GURULEADS hackers today via email demonteco@outlook.com
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.
"Admittedly, LZFSE does not aim to be the best or fastest algorithm out there. In fact, Apple states that LZ4 is faster than LZFSE while LZMA provides a higher compression ratio, albeit at the cost of being an order of magnitude slower than other options available in Apple SDKs. LZFSE is Apple’s suggested option when compression and speed are more or less equally important and you want reduce energy consumption."
It's not worse than LZ4. LZ4 is just an LZ-based compression (find common strings, reference them), while LZFSE does both LZ compression and entropy coding (like ZIP's deflate). It's comparable to zstd, which uses LZ and finite state entropy coder. They achieve better compression at lower (than just LZ-based compressor) speed. You can say they replace zlib, achieving much higher performance at pretty much the same compression ratio.
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.
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 port from another language (whose implementation I have failed to find).
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 var style is harmless.
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
When I was doing numerical analysis and computational physics, this is also exactly what I did. Work out all the equations then port them straight into C or fortran.
And I was a comp sci major first and a physics major second. You spend over a decade doing math with single letter variables. Hard habit to break I guess.
> 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.
It's funny, but nothing helps you understand something better than porting it to a new language... Even if you aren't particularly skilled in the shortcuts a given language/platform offers, it does help you understand a given algorithm.
D clearly refers to some form of "distance". M is "Medium". L is defined before this snippet of code, but I'd imagine it maps to a concept of Long.
And you're left with the variable 'q'.
The real issue is that unless you are comfortable, code involving pointer math can get confusing (all the * and + can be confusing, especially since they are such overloaded symbols in C). The single character variable names (especially when we're talking about what is basically code representation of mathematical formulae) is hardly a huge issue.
I've never seen this code base before, but this makes straightforward sense to me as I do keep my hand in with compression software, and I don't anticipate others who works with compression algorithms in general would have any trouble.
It looks just like the style of code in all the other fast LZ codebases. They are all in this style.
The "non-aligned access OK" comment litter is presumably to silence an LLVM performance sanitizer.
When implementing complex algorithm, this kind of code is usually easiest to understand.
When you look at the code, you use the paper that describes the algorithm as documentation. Using same short one letter variable names in the code and paper makes understanding much easier.
The thing I hate most is when the the paper uses 1-based numbering and the programming language uses 0-based numbering. We should settle for 0-based numbering when describing algorithms.
I've also never seen that code but it's very readable for me, just based on the snippet. It's supposed to encode the information tuple and store it as the next entry of variable length on the position pointed by q. Every tuple ends with the 32-bit literal, but what comes before depends on the size of the displacement, and of course, smaller displacements need less bytes.
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.
Yeah that's true; they aren't interchangeable but you can create functions that perform all of the bit shifting operations on arrays; Performance just suffers.
There is a lot to be said for really knowing the order of operations. I write a lot of C code and this looks very clear to me. More parenthesis would just add noise from my perspective.
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.
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)
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.
This is not true. Gcc will inline everything it damn well wants to. It will definitely inline any function that is smaller than a function call, like small C++ accessors, and any other small function available at compile time like trivial constructors and the like. The "inline" keyword mainly serves to avoid ODR violations, not to inform the optimizer.
Exported functions are entirely different than vast majority of the code, the exported ones do need call conventions, so they can be linked.
But it's entirely not true that ONLY functions marked as 'inline' would be inlined. You can also direct GCC to try to integrate all “simple enough” functions into their callers with the option -finline-functions (includeded in -O3).[0].
O2 includes inline small functions [1]:
Functions don't need to follow the ABI unless they're externally visible. If you use -fvisibility=hidden GCC will do whatever it wants for each function as it sees fit.
Interprocedural register allocation can work better than inlining too, because it keeps the code size smaller, and direct calls have almost no speed penalty.
But might be something related, eg like they are talking about a state machine in the description somewhere, and give at most one return per state, or something like that?
I think that there's a scientific paper accompanying that code somewhere. So in order to understand that code one should read the paper and all those names probably just came from paper's algorithms.
That's not a useful comparison. LZFSE is meant to be very fast and energy efficient while xz is meant for high compression while using lots of CPU and memory.
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.
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.
Do you mean by extrapolating from executed instructions? It would be very much dependent on the architecture then. It would be nice to read some independent studies and experiments, after the recent events I take any manufacturer claim on consumption with a pinch of salt.
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.
It's entirely possible that Apple have a SIMD-optimised version targeting their in-house CPUs but have chosen only to open source their reference implementation.
> With energy efficiency as a primary goal I was expecting way more use of explicit SIMD instructions.
I remember reading one paper whose conclusion was running SIMD instructions can be bad for power consumption: while you need the processor in a higher power state for longer without, you can keep the SIMD unit powered off.
[Edit: That said, I have no idea how true this is for the modern Intel CPUs yet alone Apple's custom SoCs.]
This can be true if it's the only time it's used, but when memcpy and everything use the SIMD operations, it's a lost cause. Instead you just want to go as fast as possible, so you can go back to sleep. They call it "race to idle".
> 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.
Good luck with getting pkg-config to recognize your include files automatically, for example. Or the good old "man" utility.
Alternative: maintain a HUUUUUGE list of xPATH env variables, and update them every time you recompile something and change the directory in the process. Oh, and hope that other people's Makefiles are intelligent enough to not mess up shit (e.g. use headers from system, and library .so files from your own compile)...
If you are alluding to cross-compiling, rest assured that I wrote my comment being fully aware of the plenty of pitfalls, which is why I started the MXE (mingw-cross-env) project some time ago:
Cross-compiling is yet another pile of dungheap in addition to the dungheap I mentioned.
I usually set up a Debian chroot with qemu and compile "natively" (e.g. for RPi). It's dog slow, yes, but at least it works reliably in contrast to cross compilation.
The only way I ever got CC to work is with the buildroot toolchain, which has the downside that it isn't Debian.
> 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.
Moreover, I tend to see "make install" not as actual installation command (that's indeed the task of a package manager), but more of an "extract the relevant build results".
With that in mind, I prefer packages that have a clear "build destination" folder which is filled (and updated) by a plain "make", so that "make install" isn't even needed anymore, because installation then boils down to a trivial "cp -R" command.
This, of course, requires a disciplined separation of intermediate build results from the final build results. But that shouldn't be too hard. In fact, this may be simpler than writing down a good "make install" in the first place.
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.
> 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?
More importantly, who tests it? Most developers using e.g. automake or some other generator don't test this, ever. If you package it, you delegate uninstallation to the package manager.
I'd be very leery of actually running this on my system in case it blew away unrelated bits, or versioned bits shared with other packages or package versions, like shared library symlinks or similar.
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.
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.
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.
You can bet that there is a Linux version soon, and if it's good enough, it will end up in the default repo. For Windows, it's a different story, but maybe because of the iPhone and iPad, and many MS employees using them, will it be supported somewhere in the not so near future. Anyways, 7zip and Winzip will probably support it soon enough.
It compiles fine with mingw-w64 on Windows. MSVC is a bit more involved due to the GCC extensions used. When LZFSE first came out I made a fork with the changes to compile with MSVC [1], but there wasn't any interest in it.
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 optimizing it to use as few characters as possible.
Compression code is code that often runs at boundaries to the external world and thus is a very significant attack surface. To release compression code in a non-safe language is risky enough but then using what amounts to practically write-only code is, IMHO, irresponsible.
> 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 arithmetic.
I don't really understand where the downvotes come from? I find the readability concerns legitimate, and would like to understand why compression algorithm developers feel like this is OK? Is it just the math heavy background? Can't think of any real benefits to this style.
If you don't understand the underlying mathematical algorithms its using, no amount of explicit varible names are going to help you. If you do, the concise structure makes things straightforward. The code is not meant to be read alone and understood, the papers published along with it need to be understood first.
I suspect the downvotes are because code readability is a complex, subtle topic that often gets reduced to flamewars by people who are sure they know ‘the’ right way to do things.
Code readability is relative to the reader, the programming language, and the conventions of a codebase. That's a lot of things to be relative to! Knowing that ought to put speed bumps on the way to dismissing code one isn't familiar with.
I remember having a reaction years ago on seeing some of P.J. Plauger's C++ standard library code. I think I burst out laughing and said I'd fire anyone who wrote code like that for me. Years of subsequent experience have brought multiple layers of understanding how wrong I was.
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.
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.
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 runtime when a program doesn't use it (something like GCC's gc-sections), it's not going to be feasible for small libraries to be written in it.
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.
> 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
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.
> 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.
Unless I'm mistaken, no_std means no built-in non-manual dynamic allocation (Box, Rc, etc.), unless you use "extern crate alloc", once again requiring the nightly. Some fundamentals one expects from a modern language like Vec are also missing in either case.
This is fine if you're using no_std for something where these are anathema anyway (writing bare-metal OSes comes to mind) but a huge limitation for a humble user-space library. As it stands if you want to take advantage of Rust's safety you're going to need to reimplement at least Box, probably Vec, and Rc if your program requires that kind of thing. This isn't a huge time suck, but if I were feeling out C-compatible languages before writing a library it would be a major turnoff.
I really like Rust for low-overhead binaries but it is missing a lot when it comes to writing non-rlib libraries.
Ah I see. There's two things here: first off, I'm using it in an OSdev context, so I don't expect any allocation to exist, since I haven't actually implemented that yet. And second, I took your comment to mean the language itself, which doesn't lose anything with no_std, but you mean the convenience of the libraries, which makes sense.
By the way, you _can_ reintroduce just those things if you want to. no_std means "don't include std", but you can then require them:
#![feature(alloc)]
#![feature(collections)]
#![no_std]
extern crate alloc;
extern crate collections;
use alloc::boxed::Box;
use alloc::rc::Rc;
use collections::vec::Vec;
pub fn foo() -> Box<i32> {
Box::new(5)
}
pub fn bar() -> Rc<i32> {
Rc::new(5)
}
pub fn baz() -> Vec<i32> {
let mut v = Vec::new();
v.push(5);
v
}
Of course, as you can see, the facade crates are largely not stable, so doing this on _stable_ rust isn't quite there yet, which is a thing that matters, as you originally pointed out. I expect as Rust grows for this stuff to stabilize, after all, the std versions are re-exported, so this example is de-facto stable, other than maybe the 'use' lines, which is an easy fix in the future.
Yes, my issue is just that creating a small library with a C API requires a lot of machinations that are going to turn off anyone who isn't really set on going with Rust. For OS development, standalone binaries, or Rust libraries, I think Rust is in excellent shape as it is.
It's an implementation of a mathematical algorithm. It doesn't need allTheVariables toBeNamed likeThis. Single letters map to meaningful concepts in the mathematical algorithm.
I don't see how giving the variables longer names would make it more readable. Indeed I think long variable names would obscure the structure.
Code like this has to be looked at in the concept of the algorithm design (which I hope exists...)
"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 is the output pointer, I can already guess there is an input pointer named p, and glancing at the full file shows that is indeed the case. x is also a temporary. This is a very common convention.
Sadly, I'm increasingly finding that code these days is some bloated monstrosity with variable names that barely fit into 80 columns and plenty of ridiculous indirection that turns what really needs only a single line into a deep function-call-chain spanning dozens of lines (not all in the same place) and maybe even across multiple files. Reading "modern" C# and Java code makes my head hurt with all the verbiage --- there is so much code, but very little actual substance.
This code is essentially all substance and little verbiage, and I can comprehend it quite easily. Thus I find the style complaints entirely unfounded.
To borrow a sentiment from Linus Torvalds: the code is "unreadable" to you, because you are not (yet) qualified to read it.
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.
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.
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".
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.
Someone with a physics background might assume that X is the kinetic energy of an object with mass a and velocity b. Or they might assume that X is the displacement of object after having acceleration a for a time b, having initially been at rest. The latter is perhaps more reasonable, since then the choice of two of three three variable names (x and a) is conventional.
A reason why single-letter variable names are practical is that there are strong conventions about what particular variables might represent: eg. start of the roman alphabet is constants, end of the roman alphabet is variables, capital letters are matrices, many letters in the roman and Greek alphabets have one (or a few) common meanings.
I agree on the C-bashing. But the single-letter variable names are fine---they correspond to the paper, and are probably very mathematical entities that don't even have real longer names.
(Longer names are for book keeping, not so much for calculation.)
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.
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?
As someone who's written and maintained code like this, in my experience the heavy algorithmic parts themselves usually requires almost no maintenance. Its the surrounding code - the API endpoints, makefiles and test suites that need to be modernized every few years. Algorithms like this are written, then used, then better algorithms are written from scratch.
Code like this also usually can't be edited piecemeal. Any change requires reloading the entire algorithm into your head before a single line is changed. And as others have mentioned, the normal way to do that is to read the paper. .. And if you do that, the paper's naming convention becomes the natural way to express the algorithm.
I'd like the one where this whole thing is put in a function with a name describing what it does, no matter whether the math-like one or the one with long names is used. that I'd consider readable. And any sane compiler inlines it anyway.
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.
I also see this kind of response a lot in situations the score is brought up. I don't have a background in compression, what is the current method for measuring compression efficiency? Is it a balance between size reduction and speed to unpack or is measuring compression efficacy far more nuanced?
Usually you compare on a 2D graph, with one axis being decompression speed and the other axis being compression ratio. Sometimes decompression speed is replaced by decompression + compression speed, for round-trip data. Very rarely you only consider compression speed, for "write-many read-seldom" data (like backups).
Normally, any sensible 1D metric would be visualized as isolines in that 2D plane. But the "Weissman score" doesn't even make that much sense, it's a discontinuous, non-monotonic function with singularities right in the middle! It doesn't even make sense from a dimensional analysis perspective… the score will fluctuate wildly based on the units you choose for time and size (minutes? seconds? octets? bits?). There is no conceivable real-world application of the Weissman score. It is just a bit of bad math that appeared on TV once.
271 is the longest length possible (the code is writing out some kind of literal data). The count, -16, follows each 0xE0 byte (see emit_literal - recall Apple only use little-endian CPUs). 255+16=271.
When the byte is 0xE1...0xEF (inclusive), the bottom 4 bits alone are the count - so after a run of 0xE0 sections this is how you write out any stragglers.
The decoder has comments, but I managed to figure the above out without them, so I doubt it can be that hard - I've just had a fair amount of practice at this bit twiddling C stuff. At some point when writing code you have to assume that the reader will be speaking your language.
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)
213 comments
[ 2.7 ms ] story [ 256 ms ] threadBut 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.
"Admittedly, LZFSE does not aim to be the best or fastest algorithm out there. In fact, Apple states that LZ4 is faster than LZFSE while LZMA provides a higher compression ratio, albeit at the cost of being an order of magnitude slower than other options available in Apple SDKs. LZFSE is Apple’s suggested option when compression and speed are more or less equally important and you want reduce energy consumption."
https://developer.apple.com/library/ios/documentation/Perfor... has a section titled "Choice of Compression Algorithm"
Apple's libcompression also provides LZ4 if you need it: https://developer.apple.com/library/ios/documentation/Perfor...
Zstd & LZ4 being the work of single developer is amazing though.
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".
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 port from another language (whose implementation I have failed to find).
Performance was totally unchanged either way. Looks like V8's optimizer eats those vars for breakfast.
And I was a comp sci major first and a physics major second. You spend over a decade doing math with single letter variables. Hard habit to break I guess.
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.
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!
I used it as a base for a map generator for a strategy game. Thanks a lot for the code, it worked perfectly.
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.
D clearly refers to some form of "distance". M is "Medium". L is defined before this snippet of code, but I'd imagine it maps to a concept of Long.
And you're left with the variable 'q'.
The real issue is that unless you are comfortable, code involving pointer math can get confusing (all the * and + can be confusing, especially since they are such overloaded symbols in C). The single character variable names (especially when we're talking about what is basically code representation of mathematical formulae) is hardly a huge issue.
It looks just like the style of code in all the other fast LZ codebases. They are all in this style.
The "non-aligned access OK" comment litter is presumably to silence an LLVM performance sanitizer.
When you look at the code, you use the paper that describes the algorithm as documentation. Using same short one letter variable names in the code and paper makes understanding much easier.
The thing I hate most is when the the paper uses 1-based numbering and the programming language uses 0-based numbering. We should settle for 0-based numbering when describing algorithms.
Look at eg https://www.cs.ox.ac.uk/jeremy.gibbons/publications/arith.pd... to see a cleaner alternative.
(This is about describing algorithms in papers. Optimizing for performance after the big-O has been taken care of is a different matter.)
But I could also say that I'm lazy and it's not a big deal anyway.
C just tends to look like line noise for numerical algorithms sometimes.
I think I'll stick with zlib.
What am I missing?
This doesn't take many cycles, but it does take some. While a GOTO is just a jump.
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.
[0]: https://gcc.gnu.org/onlinedocs/gcc/Inline.html [1]: https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
Interprocedural register allocation can work better than inlining too, because it keeps the code size smaller, and direct calls have almost no speed penalty.
(If you want to be glib, complain about misplaced FP perhaps?)
Not sure why.
But might be something related, eg like they are talking about a state machine in the description somewhere, and give at most one return per state, or something like that?
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)
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.
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 remember reading one paper whose conclusion was running SIMD instructions can be bad for power consumption: while you need the processor in a higher power state for longer without, you can keep the SIMD unit powered off.
[Edit: That said, I have no idea how true this is for the modern Intel CPUs yet alone Apple's custom SoCs.]
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.
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!
More generally, I believe that uninstalling, upgrading and related operations are the task of a package manager, not a build script.
Alternative: maintain a HUUUUUGE list of xPATH env variables, and update them every time you recompile something and change the directory in the process. Oh, and hope that other people's Makefiles are intelligent enough to not mess up shit (e.g. use headers from system, and library .so files from your own compile)...
http://mxe.cc/
I usually set up a Debian chroot with qemu and compile "natively" (e.g. for RPi). It's dog slow, yes, but at least it works reliably in contrast to cross compilation.
The only way I ever got CC to work is with the buildroot toolchain, which has the downside that it isn't Debian.
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.
Moreover, I tend to see "make install" not as actual installation command (that's indeed the task of a package manager), but more of an "extract the relevant build results".
With that in mind, I prefer packages that have a clear "build destination" folder which is filled (and updated) by a plain "make", so that "make install" isn't even needed anymore, because installation then boils down to a trivial "cp -R" command.
This, of course, requires a disciplined separation of intermediate build results from the final build results. But that shouldn't be too hard. In fact, this may be simpler than writing down a good "make install" in the first place.
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.
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?
this could make for a cool portmanteau.
More importantly, who tests it? Most developers using e.g. automake or some other generator don't test this, ever. If you package it, you delegate uninstallation to the package manager.
I'd be very leery of actually running this on my system in case it blew away unrelated bits, or versioned bits shared with other packages or package versions, like shared library symlinks or similar.
Granted, pkgconfig is often a good solution for a hairy problem. I was just so very delighted to see such a simple Makefile :)
As expected whenever a project does this, there's already a PR from someone trying to change that.[0]
[0] https://github.com/lzfse/lzfse/pull/15
https://github.com/lzfse/lzfse/blob/master/LICENSE
https://opensource.org/licenses/BSD-3-Clause
> Redistribution and use in source and binary forms, with or without modification, are permitted[...]
I think a better strategy would be to add support for LZFSE to the browsers themselves.
[0] https://github.com/lzfse/lzfse/blob/master/LICENSE
So now it will be cross platform?
[1]: https://github.com/jibsen/lzfse/tree/msvc-compatibility
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 optimizing it to use as few characters as possible.
Compression code is code that often runs at boundaries to the external world and thus is a very significant attack surface. To release compression code in a non-safe language is risky enough but then using what amounts to practically write-only code is, IMHO, irresponsible.
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 arithmetic.
But there's nothing stopping you from writing readable C code. That's where my concerns come from.
Code readability is relative to the reader, the programming language, and the conventions of a codebase. That's a lot of things to be relative to! Knowing that ought to put speed bumps on the way to dismissing code one isn't familiar with.
I remember having a reaction years ago on seeing some of P.J. Plauger's C++ standard library code. I think I burst out laughing and said I'd fire anyone who wrote code like that for me. Years of subsequent experience have brought multiple layers of understanding how wrong I was.
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.
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 runtime when a program doesn't use it (something like GCC's gc-sections), it's not going to be feasible for small libraries to be written in it.
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 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.
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.
This is fine if you're using no_std for something where these are anathema anyway (writing bare-metal OSes comes to mind) but a huge limitation for a humble user-space library. As it stands if you want to take advantage of Rust's safety you're going to need to reimplement at least Box, probably Vec, and Rc if your program requires that kind of thing. This isn't a huge time suck, but if I were feeling out C-compatible languages before writing a library it would be a major turnoff.
I really like Rust for low-overhead binaries but it is missing a lot when it comes to writing non-rlib libraries.
By the way, you _can_ reintroduce just those things if you want to. no_std means "don't include std", but you can then require them:
Of course, as you can see, the facade crates are largely not stable, so doing this on _stable_ rust isn't quite there yet, which is a thing that matters, as you originally pointed out. I expect as Rust grows for this stuff to stabilize, after all, the std versions are re-exported, so this example is de-facto stable, other than maybe the 'use' lines, which is an easy fix in the future.Thanks for elaborating :)
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).
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.
It's an implementation of a mathematical algorithm. It doesn't need allTheVariables toBeNamed likeThis. Single letters map to meaningful concepts in the mathematical algorithm.
I don't see how giving the variables longer names would make it more readable. Indeed I think long variable names would obscure the structure.
Code like this has to be looked at in the concept of the algorithm design (which I hope exists...)
You may ask, "Why and what is q"? By only looking at the fragment posted, where q is the output pointer, I can already guess there is an input pointer named p, and glancing at the full file shows that is indeed the case. x is also a temporary. This is a very common convention.
Sadly, I'm increasingly finding that code these days is some bloated monstrosity with variable names that barely fit into 80 columns and plenty of ridiculous indirection that turns what really needs only a single line into a deep function-call-chain spanning dozens of lines (not all in the same place) and maybe even across multiple files. Reading "modern" C# and Java code makes my head hurt with all the verbiage --- there is so much code, but very little actual substance.
This code is essentially all substance and little verbiage, and I can comprehend it quite easily. Thus I find the style complaints entirely unfounded.
To borrow a sentiment from Linus Torvalds: the code is "unreadable" to you, because you are not (yet) qualified to read it.
/rant
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.
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.
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.
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".
Someone with a physics background might assume that X is the kinetic energy of an object with mass a and velocity b. Or they might assume that X is the displacement of object after having acceleration a for a time b, having initially been at rest. The latter is perhaps more reasonable, since then the choice of two of three three variable names (x and a) is conventional.
A reason why single-letter variable names are practical is that there are strong conventions about what particular variables might represent: eg. start of the roman alphabet is constants, end of the roman alphabet is variables, capital letters are matrices, many letters in the roman and Greek alphabets have one (or a few) common meanings.
(Longer names are for book keeping, not so much for calculation.)
} else if (D >= (1 << 14) || M == 0 || (x + 3) + M > 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.
} else if (D >= HUYGENS_LIMIT || M == 0 || (x+3)+M > SWIM_RATE_B)
Code like this also usually can't be edited piecemeal. Any change requires reloading the entire algorithm into your head before a single line is changed. And as others have mentioned, the normal way to do that is to read the paper. .. And if you do that, the paper's naming convention becomes the natural way to express the algorithm.
Normally, any sensible 1D metric would be visualized as isolines in that 2D plane. But the "Weissman score" doesn't even make that much sense, it's a discontinuous, non-monotonic function with singularities right in the middle! It doesn't even make sense from a dimensional analysis perspective… the score will fluctuate wildly based on the units you choose for time and size (minutes? seconds? octets? bits?). There is no conceivable real-world application of the Weissman score. It is just a bit of bad math that appeared on TV once.
It's a Cuban Prime. Everybody knows that. Geez!
When the byte is 0xE1...0xEF (inclusive), the bottom 4 bits alone are the count - so after a run of 0xE0 sections this is how you write out any stragglers.
The decoder has comments, but I managed to figure the above out without them, so I doubt it can be that hard - I've just had a fair amount of practice at this bit twiddling C stuff. At some point when writing code you have to assume that the reader will be speaking your language.
https://github.com/lzfse/lzfse/blob/master/src/lzvn_decode_b...
We detached this subthread from https://news.ycombinator.com/item?id=12048265 and marked it off-topic.