Columnar Data Structure in Java

What if we need traditional object-oriented API and extra high performance for field-wise operations in one place?

I designed my CPS exactly having this in mind. The article is for describing the idea behind the library.

Imagine you have 10 million product objects, which have the following structure:

class Product {
String name;
int quantity;
int price;
}

You need to calculate the grand total value by summing quantity * price for every product. You would create an ArrayList<Product>, iterate on them one way or another and calculate the sum. And you would be right. Or you need the product with max quantity or lowest price.

Now imagine you are the CPU doing those operations. You would pick the object references from the backing array, go through them one by one, capture field values and then do the computation. In the best case you will cache more of those references. But you still need to chase them to get the data inside. This is called pointer chasing: following object references to reach data stored at other memory locations. It is because Java arrays do not store object data inline. Object arrays store references, while primitive arrays store primitive values directly.

Now imagine you have this class:

class ProductColumnarStore {
String[] names;
int[] quantities;
int[] prices;
int offset;
}

Each offset position represents one logical Product. Now your data is a good candidate for efficient CPU cache utilization during sequential access. And for primitive columns, no pointer chasing in the loop. Just loading new chunks of data from the arrays inside productColumnarStore. You have a contiguous data layout, which is especially good for sequential field-wise operations and SIMD instructions.

Why would you choose this way? It is not convenient to create this structure every time you need. You need to fill it first, then you need to handle bookkeeping of the offset during the iteration and you will not have the product object.

This is where CPS helps you. You design a projection based on your class, it is doing the heavy lifting.

interface ProductProjection {
String name();
int quantity();
int price();
}

Later I will show how and when to use this library.