Last year, we published a fast C++ library to quickly compress and decompress arrays of integers. To get good compression, we use differential coding: the arrays of integers are sorted and instead of storing the integers themselves, we store the difference between successive integers. The differences are typically small integers that can be compressed efficiently. Out of habit, I ported our code to Java and published it under the name JavaFastPFOR library.

Unlike generic compression techniques like gzip or Google Snappy, we only wish to compress and uncompress integers. We provide a less general solution, but we can also get much more impressive speeds in some cases (e.g., an order of magnitude faster).

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.

I decided to compare our results with the popular Kamikaze PForDelta library. I used a fast core i7 processor with synthetic data. We vary the compressibility of the data. For each test, I report the speed in millions of integers per second as well as the storage cost in bits per integer (in parenthesis).

 Binary Packing   Kamikaze PForDelta 
1200 (3.1) 300 (3.3)
1100 (7.4) 300 (7.7)
1000 (13) 300 (14)

The numbers show that the Binary Packing technique implemented in the JavaFastPFOR library can easily exceed 1 billion of integers per second in decompression speed. This is likely fast enough for most applications.

I posted the raw results if you wish the examine them more closely.

The library is available under the Apache license and is part of the Maven repository. It includes many more schemes.

Warning: These results may not be representative of what you get in an actual application. They will vary depending on the machine you use and your data. I am only providing these numbers as a ballpark indication.

Credit: This work is the result of a fruitful collaboration with many super smart people including L. Boytsov, O. Kaser, N. Kurz. All mistakes are my fault.

6 Comments

  1. “The assumption is that most (but not all) values in your array use less than 32 bits.”
    I think this statement belongs in this post, otherwise nothing makes sense.

    Comment by Anonymous — 9/7/2013 @ 5:48

  2. I was recently contemplating on whether I should use Java for algorithmic programming and I came to a conclusion. Java is not good. I mean it is great if you consider the number of libraries available. The performance is generally good. Yet, if you need top-notch performance, it is quite hard to get in Java. You would need to use awful things like manual memory management and parallel arrays…. This is awful and counterproductive. You can do much better in C++. But, if you don’t mind 2-3x loss in performance Java (Scala, or, say, OCaml) can be a nice choice.

    Comment by Itman — 9/7/2013 @ 6:19

  3. @Anonymous

    Thanks for pointing out a shortcoming in my post. However, we do not make this assumption. Instead, we just assume that the integers have been sorted. I have edited the post accordingly.

    Comment by Daniel Lemire — 9/7/2013 @ 8:25

  4. @Itman

    What is true is that there is a whole range of optimizations that are simply not possible in Java (by design).

    Comment by Daniel Lemire — 9/7/2013 @ 8:30

  5. Does it support streaming compression as integers keep appearing in the stream?

    Comment by Ishan — 9/7/2013 @ 14:17

  6. @Ishan

    You can compress and uncompress data in blocks… See the “advanced” example in the example.java file:

    https://github.com/lemire/JavaFastPFOR/blob/master/example.java

    So, yes, I would say that you can building streaming applications using this library.

    Comment by Daniel Lemire — 9/7/2013 @ 15:41

Sorry, the comment form is closed at this time.

« Blog's main page

Powered by WordPress