Fast integer compression in Java | Hacker News Reader

Fast integer compression in Java

lemire.me

54 pointsdangoldin47 comments

In what way is compressing an array of integers "less general" than a general compression algorithm? Is that not exactly what a normal compression algorithm does, or at least can be construed as doing, with, say, 8-bit integers?

See: http://lemire.me/blog/archives/2012/02/08/effective-compress...

You can use it for text but it won't work as well. It's designed for numbers that are created by some kind of real process.

It compresses by looking for the largest and smallest number and only storing the difference from the smallest number, and only as many bits as needed for the largest. (Good for situations where most of your data lies inside a range.)

It stores the difference between successive numbers. (Good for measuring a process that varies slowly.)

Also see: http://en.wikipedia.org/wiki/Golomb_coding which works on the principle that small numbers show up more than large.

None of that makes sense for text which doesn't have those patterns.

Thanks for the explanation, definitely an interesting routine and the performance numbers he touts in the blog post make it something I'd definitely look to test on my own

One difference is API e.g. for compressing an array of integers in Java, you say int[] compress(int[] toCompress) i.e. it natively works or Java's int[]. While it's true that the layout of data in memory could be re-interpreted as a byte array, you avoid cumbersome casting (which, by itself, might incur cost in languages like Java where you can't just party on memory via pointers).

Another difference is that a custom algorithm for compressing integers might gain speed/compression efficiency from exploiting statistical properties of integers e.g. it's a safe bet that in most cases the highest byte of an int is 0 (i.e. integers are are small).

Or in many cases a delta encoding is very effective (i.e. {5, 10, 15} => {5, 5, 5} which is easily encoded with run-length encoding).

Of course if integers are randomly and uniformly distributed they are just as un-compressible as random, uniform distribution of bytes, but in many real-life uses of integer arrays that is not true.

You should probably read the original research paper if you're curious: http://arxiv.org/abs/1209.2137

I was thinking the same myself - couldn't it work just as well on a random byte stream by just passing in every 4 bytes as a 32-bit integer?

No, because everything would be an outlier, so it would save nothing. Here is a basic explanation (there are niggly little details i'm not going to go over, since the papers do a better job)

The way FOR (i'll get to PFORDELTA in a sec) codecs work is by taking numbers say 128 at a time, finding the max number of bits necessary (so if all numbers are between 0 and 32, it would be 5), and then encoding them as 5 bit numbers

FOR has the problem that if you have a list of numbers like 1 2 2 2 3 728 3 2 1, the 728 screws you.

PFORDELTA instead finds the number of bits it takes to represent, say, 90% percent of the numbers (IE it finds the b such that 90% of numbers are < 2^b), encodes those numbers in fixed size blocks of b bits, and along the way, "patches" out the 10% of outliers, and encodes them at the end.

It is normally used on posting lists.

In a sufficiently large random byte stream, for random 4 byte streams, either b == 32 all the time, or over time, the outliers will take more space than you save elsewhere. (where the amount of "more space" will be whatever the control overhead of the outlier encoding is).

So you will either save nothing, or grow in size. This is guaranteed by the pigeonhole principle.

From what you're writing it seems like this might work for bytes when you treat them as such and not group four of them together as integers. Especially text probably has pretty much the same patterns (lots of code points in a range [lower-case letters] with a few outliers [upper-case letters and spaces]).

But then again, for text there probably are much better-suited alforithms.

For text, you would probably want an encoding hard coded into the algorithm. Because (in a given language) the distribution of characters is relativly consistent, you do not loose much by deciding which characters only need 2 bits and which ones need 10; and you save on having to put this information in the compressed data.

But you are right that their are far better algorithms for text compression (although if doing this character re-encoding makes sense, I would imagine most implementations include it along with the main algorithm, and several other bonus compression algorithms).

Thanks for the explanation

No. There is no general purpose compression that works on random byte streams.

FTA:

> Though you cannot reach the same kind of speed in Java as you can in C++, there are many good reasons to use Java instead of C++. How good is Java at this task? Direct comparisons between Java and C++ are difficult. I would estimate that the difference is a factor of 3 and more. But Java can still be more than fast enough.

That has also been my experience, but there's always an army of people that claims "Java can be just as fast or faster than C++". Anyone care to prove Mr.Lemire wrong? (My experience was more like twice as slow for memory intensive code, but thrice as slow still sounds like a reasonable estimate to me)

The answer is that if you're prepared to off piste, mainly by using sun.misc.Unsafe, you can get within a gnat's whisker of C++. For example:

http://mechanical-sympathy.blogspot.co.uk/2012/07/native-cc-...

and

http://mechanical-sympathy.blogspot.co.uk/2012/10/compact-of...

It's interesting to look at what Java lacks to achieve this level of performance with less pain. The main issue, I believe, is control over memory layout. For example, avoiding boxing in arrays of objects. Avoiding GC is also an issue.

I think Rust is interesting as it allows the programmer to talk about these things without going "outside" the language like one must in Java, while still retaining a modern programming style.

That's a good answer, but it isn't really Java - it's assembly in disguise. You lose basically everything Java can give you when you do that. And I don't know since when it actually works well - as of 2011 with Java 1.6, I had similar code that used memory mapped buffers, and crawled like a snail because (apparently, I couldn't directly verify) the optimizer would not inline the memory mapped access, meaning that every array access cost ~10 times as much as it should.

You can say that about every technique that goes 1 level lower in abstraction. Personally, these techniques allow me to write the vast majority of my code in a high level JVM language (Scala in my case) and optimize the very small percentage of my code that needs to be this latency sensitive.

Because I can get so close to native performance in that highly specific case, the idea of using C++ hardly ever comes up. If I need faster than this, C++ is probably not fast enough either and I need to look at "closer to iron" solutions. I for one appreciate that. But then again, I'd much rather program in C than C++.

As far as claims like Java is 3x slower than C++, it is nearly impossible to quantify these things directly. For any given benchmark you will be able to find people who complain about the code in the benchmark not being optimized enough.

Suffice it to say that there are some things Java is faster at and some C++ is and their are techniques in both that allow them to achieve near parity.

I agree it isn't great, but it works, and if you need that extra performance in a small part of your application it can allow you to stay on the JVM. I'd rather do that than write everything in C (YMMV.)

The blog posts I linked compare performance to nio ByteBuffers, and show improvement for Unsafe over ByteBuffer. That might be relevant to your case.

I rewrote in C, and got 10x speedup and x4 less memory. So, it's no longer relevant :)

If you're prepared to do all that, why not write the hot code in C and use JNI?

If you go C/JNI you:

1. Have added an extra step to your build process

2. Pay the cost of doing JNI calls, which I believe is quite high.

Look, I'm not saying doing this Unsafe stuff is rainbows and unicorns. It's a hack, but it's a hack that is extremely useful in a few niche applications.

JNI calls carry a very significant latency overhead. If the code you are trying to optimize would have to call the JNI methods repeatedly you very quickly lose any speed advantage you had from writing it in C. If on the other hand you only need to call the JNI a few times it probably does make sense to go the JNI route.

Another common option (especially in server style programs) is to have 2 daemons, one in C (or C++) doing a very specialized role and communicating with a JVM daemon via memory mapped files.

Have look at my project: MapDB. It provides java collections on top of raw byte buffers or files.

Nice work! Never heard of this before. Looks like it might be a useful replacement for Redis in some cases.

I'd like to say something that may sound a bit controversial, but bear with me: for most practical programs, Java's performance beats C++; in fact, it beats C. And assembly. There, I've said it, and now let me try to back this up.

Proving my claim is very hard, but I'll try to persuade you. The task is made harder by the fact that for every possible Java program, there exists a C++ program that performs the exact same task at least as fast as Java (proof by example: the JVM).

And yet, Java is the best performing programming environment in existence (well, in widespread use; there may be runtimes I'm not aware of). How is that possible? When we say that one language or environment is faster than another, do we mean that there exists a string of characters in that language that would produce a faster executable? If that is what we mean, then yes, C++ is faster than Java. But I think the question is not whether that desired program exists, but whether you can write it. To that question, I think the answer is no in most circumstances, especially when it comes to large programs.

Why? because when you write a large, hopefully maintainable, C++ program, you must make use of language features that are hard for the compiler to optimize, most notably -- virtual methods. The JVM JIT does runtime compilation, so it inlines virtual calls, and de-optimizes them if its assumptions are shown to be false. Method inlining is the most important compiler optimization because it opens to door to all kinds of other optimizations like lock elision, scalarization of objects and more.

And there's another issue. What do we mean by performance nowadays? It's not too hard for a single-threaded C++ program to beat a similar Java program (provided that the program is not large, and does not make use of virtual methods). But modern hardware is multi- and many-core, and most scalable lock-free algorithms absolutely require a good GC in order to function well. Java probably has (several of) the most advanced GC(s) in wide use.

To sum up: C++ can beat Java in small benchmarks, but Java will beat C/C++ in most large, real-world programs; and if the program is heavily multi-threaded, Java has even more of an edge.

No, you don't need a GC to implement lock-free data-structures. RCU allows you to generically defer work on a piece of data until it is no longer accessible. I personally find the idea behind it to be very elegant and I'd recommend reading up on it. While it isn't as simple as a full-blown GC, once you have a working implementation that suits your needs (eg. urcu), it's usually pretty straightforward to introduce in a lock-free data-structure and has far less overhead. In fact, when it comes to real-time systems (eg. games), the GC is usually something you want to avoid at all costs.

Note that there are various other tricks (eg. hazard pointers, reference counters, etc.) to get around the same problem but they're mostly specialized to various situations. As an example, last time I checked gcc's std::shared_ptr implementation on x86, it used some lock-free magic to implement its thread-safe reference counter. In fact, I think it could even be used to build entire lock-free data-structures and never have to worry about deleting anything.

Several things:

First, various techniques for avoiding GC in lock-free data structures are not in wide use and for good reason: they are far more complicated to implement in a general fashion than you think. Sometimes they're very specific, sometimes they require cooperation by the kernel, and sometimes you end up writing a buggy and inefficient garbage collector just to get around implementation problems. Java's lock-free data structures are used everywhere today and with great results.

Second, regarding real-time. There are hard real-time GCs for Java, and they work great, only they tend to cost a lot of money. But hard real time systems often sacrifice performance for the sake of worst-case guarantees -- that's a whole other set of tradeoffs. In general, and certainly when it comes to throughput, a good GC is both the easiest and the most efficient way to manage memory.

Finally, because, as I've shown, for every Java program there exists a C++ program that performs as efficiently or better, you could, given enough effort, always surpass Java. In practice, doing that is extremely hard (unless it's a very specific, well understood problem), and the returns are hardly worth the effort. What you gain in integer compression you lose in method invocation. What you gain with SIMD you lose on malloc. What you gain in cache-friendliness you lose in multi-threading. And the gap is only narrowing in Java's favor so that there are fewer and fewer things you gain when using C++.

This is not to say that C++ doesn't have it's place. First, you need it to write the JVM :) You need it in a resource constrained environment where memory is limited, and you may not want to spare a thread for concurrent GC. You need it when startup time is crucial. You need it (or Fortran) for some well-understood numeric computing problems. But for general, large, long-running server side applications - Java is king.

And BTW, games are years, if not a decade or more, behind advances in software engineering (I've had some experience in that). In the past decade they've literally progressed on one front only (though, an important one): graphics and GPGPU (for physics and AI). I know that some AAA studios literally forbid any multithreaded code on the CPU (beyond a simple and predefined division of labor among a few threads). MMO game engines, for examples, are practically primitive compared to advanced server-side systems in other markets.

RCU is in wide use today. In fact, you probably rely on it everyday: inside the Linux kernel.

The biggest problem holding back RCU is not how hard it is to use (if you're qualified to write lock-free data-structures then it should be cake) but that it's relatively unknown and there are not many user-land libraries. I know of 4 available user-land implementations: two that I've written, one that we use at work and only the fourth, liburcu, would I consider mature and stable enough for wide-use. There's a third reason but I'll let you figure that one out by reading the Wikipedia article.

Note that it's not a magic bullet either because there are various possible implementations and they offer various trade-offs. A bit like the various GC mechanisms really. Funny thing is that I usually introduce RCU as a GC mechanism; albeit one that's far more specialized and offers many advantages over a traditional GC when it comes to lock-free data-structures.

Final note, I've written various mechanism for cleaning up lock-free data-structures and I'm fully aware of how difficult they can be to implement correctly. If nothing else, it's more complicated then using a GC where there's nothing for you to do. The point of my previous post was not to say that one approach or language is better then another but merely to point out that a full-blown GC is not required to build a scalable lock-free data-structure. Good thing for me since that's exactly what I do for fun :)

I see that while RCU doesn't rely on GC, it does rely on safepoints (or a specific kind of safepoint - a task switch). A little unrelated, but internally, the JVM makes use of safepoints, not only for GC but for other purposes as well (I think JIT-ing and maybe other things). There are some "phase changes" that can only occur when all, or some, threads are at a safepoint. JVM data structure gurus like Doug Lea sometimes structure their code with that knowledge. For example, if I'm not mistaken (and I may very well be mistaken on this point), there's a safepoint at every back jump, and this somehow makes Doug use a while loop and a do-while loop for different occasions.

While the Linux kernel may rely on task-switch safe-points, user-land implementations can't which means they require an entirely different grace-period mechanism to work. This is what makes user-land implementations tricky to get right. I won't go into the details here since it's somewhat involved and I need a white board to explain it properly. That being said, if you feel brave, head over to my github repo[1] and look for src/rcu.h and src/grcu.* .

[1]: https://github.com/RAttab/lockless

I think your logic is flawed. I will agree with it if you will replace "for most practical programs" by "for most in-house or agency-coded enterprise applications".

Another point is that Java bytecode doesn't have SIMD primitives, so unless JIT can do SIMD-optimizations, any SIMD-aware C/C++ compiler will beat Java.

This is especially relevant for the kind of task this article discusses: PFOR Delta integer compression.

SIMD for Java is a long time coming. It doesn't change my statement though, because obviously, you can write small snippets of code, or benchmarks, where C beats Java. I was saying that for a large program (and there are few large programs whose performance depends on SIMD), Java usually beats C.

Actually, there are other changes that would improve Java performance more than SIMD, like value types. The lack of value types causes many unnecessary cache faults in Java programs.

> I was saying that for a large program (and there are few large programs whose performance depends on SIMD), Java usually beats C.

That goes counter to my experience. Care to share your anecdata here?

I thought I did. I've been involved with porting large C++ programs to Java (mostly soft real-time defense applications). We've always seen a significant performance increase (not due to newer hardware).

Like I said, this happens for two reasons: large maintainable programs require virtual methods that are hard for the C++ compiler to optimize, and Java opens a whole new realm of possibilities with scalable non-blocking data structures.

I would say this is true for most large applications, but untrue in particular circumstances: Java does not excel in many cases of numeric computation (where value types, and, yes, SIMD, would be of assistance). Also, Java is the wrong choice if startup time is important.

Taking your logic a little further, Python+PyPy beats Java hands down. Every single argument applies to Python vs. Java or Python vs. C/C++ more than it does to Java vs. C/C++

Which, incidentally, is my tool of choice...

Personally, I've never met nice readable Java code. I'm sure it exists somewhere, but I've actually gone looking for it in the past (including posting a question on HN, out of 10 responses only one was concrete -- Play Framework -- and they've abandoned Java since).

Every piece of Java I've met is an overengineered piece of AbstractAbstractFactoryFactoryBeanSingleton class. I'm sure Notch writes better code. But as far as I can tell he's the only one.

> Python+PyPy beats Java hands down. . Every single argument applies to Python vs. Java or Python vs. C/C++ more than it does to Java vs. C/C++

Not at all. Python does not even begin to apply a minuscule portion of the optimizations the JVM performs. Also, I wasn't talking theory, I was talking practice: I've worked on porting two multi-million LOC soft real-time applications from C++ to Java, and a few smaller programs; big performance improvements in all cases. I was simply explaining why Java performs better in practice, not speculating why it would. But if you haven't seen that with your own eyes, all that's left for me is to explain why this is so.

> Personally, I've never met nice readable Java code.

This has no relevance to the discussion, though there's plenty of nice, readable Java code. Anyway, I was talking about the JVM, not specifically Java the language.

> I'm sure Notch writes better code. But as far as I can tell he's the only one.

Right... and as far as I can tell, you're not really into Java :) That's okay. Millions of developers are.

> Not at all. Python does not even begin to apply a minuscule portion of the optimizations the JVM performs

Are you familiar with PyPy? It doesn't go as far as the JVM, but "minuscule" is definitely wrong.

> I was talking practice: I've worked on porting two multi-million LOC soft real-time applications from C++ to Java, and a few smaller programs; big performance improvements in all cases.

My experience is the opposite. Not two million lines - just a few tens of thousands, but still.

> This has no relevance to the discussion, though there's plenty of nice, readable Java code. Anyway, I was talking about the JVM, not specifically Java the language.

One of the previous posts (to which I was replying) claimed that Java is faster in practice because (paraphrasing) it is nicer to read and write, and that was a response to that.

> Right... and as far as I can tell, you're not really into Java :) That's okay. Millions of developers are.

That's good, that guarantees I'll always be in demand :)

> My experience is the opposite. Not two million lines - just a few tens of thousands, but still.

But that's the whole point. I could probably write a C++ program of that size that beats a Java program of that size, provided that they're single threaded. But programs of that size are usually written by a single developer or a very small team. Many programs aren't that small.

But even at this size, unless the problem is embarrassingly parallel, a multi-threaded Java program would often perform better, mostly due to concurrent data structures that require (or greatly benefit from) GC.

Python, and PyPy AFAIK, doesn't provide true concurrent threads or lock-free primitives like CAS. This means there are a class of high performance and high concurrency applications you simply can't write in Python.

I'm no fan of Java, but I am a fan of the JVM. The two don't necessarily go together, as I'm sure you know. I also recognise the JVM has limitations. There will (hopefully) be better things in the future. This is one reason that Rust is interesting to me, but it has a long way to go before I'd use it in production.

While Python beats Java at a lot of things, that wasn't the point.

The point was, a badly written Java program can beat a badly written C++ program, because the Java optimiser is more robust against stupid decisions by the programmer.

PyPy might make your point correct though. While PyPy will never beat well-written C++ (at least, not in the foreseeable future), it might start beating badly written C++.

I work on java db engine. C/C++ and Java developers have completely different mind set. Where C guy is doing bite-wise operations Java guy will implement separate object for each pixel. It is rare to see tightly optimized java code.

I see main Java advantage in concurrency and advanced programming. My code has fine-grained locking, robust, correct and very quickly written. And hand optimized code in bottlenecks usually has comparable speed.

> That has also been my experience, but there's always an army of people that claims "Java can be just as fast or faster than C++". Anyone care to prove Mr.Lemire wrong?

They are not necessarily in contradiction. Java can be as fast or faster than C++ - if you choose a workload whose active set (including Java overheads) fits into the CPU cache. Of course there are very few realistic and useful workloads where that is the case.

Still, most things don't have code execution as a bottleneck and/or aren't so performance critical that a factor of 3 is a big problem.

I can afford twice as powerful kit when I write in Java as it takes less time :)

Try Python or K, you'll be able to afford 5 to 100 times as much :)

Is there lossless compression encoding like PForDelta but for floats/doubles?

Yes. Floats/doubles can be strictly ordered. Now, instead of storing a value as a float, store the distance (in your strictly ordered list) from the previous value. This is effectivly mapping your floats/doubles to ints; but it works because the mapping maintains the ordering that is central to PForDelta.

I doubt it will be lossless, unless using the same ordering and same compute device. My primary use encoding on CPU, decoding on GPU.

I have not worked heavily with floats, but I think numerical comparison (IE, greater than/less than) produce a non-ambigous ordering. Assuming that both ends have the same set of numbers representable as floats, it should be lossless. If they do have a different set of floats, then you need to solve lossless conversions before talking about lossless compressions.

How do you decide how many bits distance should be encoded in? How many bits for mantissas, sign bits?

I worked with half floats (FP16) and other weird partial word float formats ... I don't think it's trivial.

I guess the most straightforward way is to convert to fixed point real numbers first, then it's essentially the same as integers.

Or maybe just do it per block of each 128 floats?

Reply on news.ycombinator.com