Wojciech Kudla

About Wojciech Kudla

Wojciech is a low latency Java developer with 10 years of professional experience. His interests revolve around high performance computing, JVM internals and Linux kernel tuning. Recently focusing also on ultra-low latency networking and high precision time protocols. He gained most of his experience working for LMAX and few other high frequency trading shops.

How to serialize an array of doubles with a byte (binary delta encoding for low-varianced monotonic sets of floating point data)

Low latency systems require high performance message processing and passing. As in most cases data has to be transfered over the wire or serialised for persistence, encoding and decoding messages become a crucial part of the processing pipeline. The best results in high performance data encoding usually involve applying knowledge of application data specifics. The technique presented in this article is a good example of how leveraging some aspects of the data benefits encoding in both latency and space complexity.

Usually the largest messages passed around high frequency trading systems represent some state of an exchange in a form of an excerpt from the order book. That is, a typical market data (tick) message contains information identifying an instrument and a set of values representing the top of the order book. A mandatory member of the data set is price/exchange rate information expressed in real numbers (for buy and sell sides).

What makes that data set very interesting from optimization perspective is that it is:

  1. monotonic
  2. low varianced
  3. non-negative*

So in practice we deal with sets of floating point numbers which are not only sorted (ascending for bid and descending for ask) but also having neighbouring values relatively “close” to each other. Keeping in mind that message processing latency is crucial for most trading systems, market ticks as one of key entities need to be passed as efficiently as possible.

Let me demonstrate how all these features can be exploited to encode numeric data to a very compact binary form. First, two teaser plots demonstrating the difference between different serialization approaches:

image1

So far we can see that delta encoding yields better results for encoding times as compared to standard ByteBuffer based serialization but becomes worse than Kryo (one of the most popular high-performance serialization libraries) as soon as we reach array lengths above 40. What is important here though, is a typical use-case scenario which for high frequency trading market messages happen to fit into the 10-40 range of array lengths

It gets much more interesting when we examine the resulting message sizes (as a function of array length):

image2

The benefits of applying delta encoding should become obvious at this point (that blue curve applies equally to bytebuffer and Kryo serialization). What happens here is, with some knowledge on the specifics of data being processed it is safe to make assumptions that result in serialization being more CPU-intensive but ridiculously much more efficient space-wise. The idea behind delta compression is very simple. Let’s start with an arbitrary array of integral numbers:

  • [85103, 85111, 85122, 85129, 85142, 85144, 85150, 85165, 85177]

If these were ints, without any compression we would have to use 4 * 9 = 36 bytes to store the data. What is particularly interesting in this set of numbers is that they are clustered relatively close to each other. We could easily reduce the number of bytes required to store the data by referencing the first value and then produce an array of corresponding deltas:

  • Reference: 85103, [8, 19, 26, 39, 41, 47, 62, 74]

Wow! Now we can downsize to array of bytes. Let’s do the calculations again. We need 4 bytes for the reference value (which is still int) and 8 * 1 byte per delta = 12 bytes.

That’s quite an improvement from the original 36 bytes but there is still room for some optimisation. Instead of calculating deltas from the reference value let’s store differences for each predecessor successively:

  • Reference: 85103, [8, 11, 7, 13, 2, 6, 15, 12]

The result is a non-monotonic set of numbers characterised by low variance and standard deviation. I hope it has already became clear where this is heading to. Still, it’s worth elaborating a little.

What we essentially ended up with at this point is a set that’s a perfect candidate for binary encoding. For our example that just means it is possible to accommodate 2 deltas in a single byte. We only need a nibble (4 bits) to accommodate values from 0-15 range so we can easily get away with ultimately squeezing the original array into 4 (for reference) + 8 * 1/2 = 8 bytes.

Since prices are expressed with decimal numbers, applying delta compression with binary encoding would involve establishing a maximum supported precision and treating decimals as integrals (multiplying them by 10 ^ precision), making 1.12345678 with precision of 6 a 1123456 integer. So far all of this has been a purely theoretical speculation with some teaser plots at the beginning of this article. I guess this is the right moment to demonstrate how these ideas may be implemented in Java with 2 very simple classes.

We’ll start with the encoding side:

package eu.codearte.encoder;

import java.nio.ByteBuffer;

import static eu.codearte.encoder.Constants.*;

public class BinaryDeltaEncoder {

    public static final int MAX_LENGTH_MASK = ~(1 << (LENGTH_BITS - 1));

    public ByteBuffer buffer;
    public double[] doubles;
    public int[] deltas;
    public int deltaSize, multiplier, idx;

    public void encode(final double[] values, final int[] temp, final int precision, final ByteBuffer buf) {
        if (precision >= 1 << PRECISION_BITS) throw new IllegalArgumentException();
        if ((values.length & MAX_LENGTH_MASK) != values.length) throw new IllegalArgumentException();
        doubles = values; deltas = temp; buffer = buf;
        multiplier =  Utils.pow(10, precision);

        calculateDeltaVector();
        if (deltaSize > DELTA_SIZE_BITS) throw new IllegalArgumentException();
        buffer.putLong((long) precision << (LENGTH_BITS + DELTA_SIZE_BITS) | (long) deltaSize << LENGTH_BITS | values.length);
        buffer.putLong(roundAndPromote(values[0]));
        idx = 1;
        encodeDeltas();
    }

    private void calculateDeltaVector() {
        long maxDelta = 0, currentValue = roundAndPromote(doubles[0]);
        for (int i = 1; i < doubles.length; i++) {
            deltas[i] = (int) (-currentValue + (currentValue = roundAndPromote(doubles[i])));
            if (deltas[i] > maxDelta) maxDelta = deltas[i];
        }
        deltaSize = Long.SIZE - Long.numberOfLeadingZeros(maxDelta);
    }

    private void encodeDeltas() {
        if (idx >= doubles.length) return;
        final int remainingBits = (doubles.length - idx) * deltaSize;

        if (remainingBits >= Long.SIZE || deltaSize > Integer.SIZE) buffer.putLong(encodeBits(Long.SIZE));
        else if (remainingBits >= Integer.SIZE || deltaSize > Short.SIZE) buffer.putInt((int) encodeBits(Integer.SIZE));
        else if (remainingBits >= Short.SIZE || deltaSize > Byte.SIZE) buffer.putShort((short) encodeBits(Short.SIZE));
        else buffer.put((byte) encodeBits(Byte.SIZE));
        encodeDeltas();
    }

    private long encodeBits(final int typeSize) {
        long bits = 0L;
        for (int pos = typeSize - deltaSize; pos >= 0 && idx < deltas.length; pos -= deltaSize)
            bits |= (long) deltas[idx++] << pos;
        return bits;
    }

    private long roundAndPromote(final double value) {
        return (long) (value * multiplier + .5d);
    }
}

A few words of introductory explanation before I go into details. This code is not a complete, fully-blown solution; it’s sole purpose is to demonstrate how easily it is to improve some bits of application’s serialization protocol. Since it is subjected to microbenchmarking it also does not induce gc-pressure just because the impact of even the quickest minor gc could severily skew the final results, hence the ugly api. The implementation is also highly sub-optimal, especially CPU-wise but demonstrating micro-optimizations is not the goal of this article. Having said that let’s see what it does (line numbers in curly brackets).

Encode method first does some fundamental sanity checks {17,18}, calculates the multiplier used in transforming decimals to integrals {20} and the delegates to calculateDeltaVector(). This in turn has two effects.

  1. Calculates rolling delta for the whole set by transforming decimals to integrals, subtracting from predecessors and finally storing the results in a temporary array {33}
  2. As a side effect works out the maximum number of bits required to represent a delta {34,36}

The encode() method then stores some metadata required for correct deserialization. It packs precision, delta size in bits and the array length in the first 64 bits {24}. It then stores the reference value {25} and initiates binary encoding {27}.

Encoding deltas does the following:

  1. Checks if it already processed all array entries and exit if so {40}
  2. Calculates the number of remaining bits to encode {41}
  3. Chooses the most appropriate type (given its size in bits), encodes the remaining bits, and writes the bits to the buffer {43-46}
  4. Recurses {47}

One last bit probably requiring some elaboration is the encodeBits() method itself. Based on type size (in bits) passed in the argument it loops over a temporary long which sole purpose is to serve as a bitset and writes the bits representing consecutive deltas moving from the most to the least significant part of the long value (scoped by the type size).

Decoding is, as expected, a pure opposite of encoding and is mostly about using the meta data to reconstruct the original array of doubles up to the specified precision:

package eu.codearte.encoder;

import java.nio.ByteBuffer;

import static eu.codearte.encoder.Constants.DELTA_SIZE_BITS;
import static eu.codearte.encoder.Constants.LENGTH_BITS;

public class BinaryDeltaDecoder {

    private ByteBuffer buffer;
    private double[] doubles;
    private long current;
    private double divisor;
    private int deltaSize, length, mask;

    public void decode(final ByteBuffer buffer, final double[] doubles) {
        this.buffer = buffer; this.doubles = doubles;
        final long bits = this.buffer.getLong();
        divisor = Math.pow(10, bits >>> (LENGTH_BITS + DELTA_SIZE_BITS));
        deltaSize = (int) (bits >>> LENGTH_BITS) & 0x3FFFFFF;
        length = (int) (bits & 0xFFFFFFFF);
        doubles[0] = (current = this.buffer.getLong()) / divisor;
        mask = (1 << deltaSize) - 1;
        decodeDeltas(1);
    }

    private void decodeDeltas(final int idx) {
        if (idx == length) return;
        final int remainingBits = (length - idx) * deltaSize;

        if (remainingBits >= Long.SIZE) decodeBits(idx, buffer.getLong(), Long.SIZE);
        else if (remainingBits >= Integer.SIZE) decodeBits(idx, buffer.getInt(), Integer.SIZE);
        else if (remainingBits >= Short.SIZE) decodeBits(idx, buffer.getShort(), Short.SIZE);
        else decodeBits(idx, buffer.get(), Byte.SIZE);
    }

    private void decodeBits(int idx, final long bits, final int typeSize) {
        for (int offset = typeSize - deltaSize; offset >= 0 && idx < length; offset -= deltaSize)
            doubles[idx++] = (current += ((bits >>> offset) & mask)) / divisor;
        decodeDeltas(idx);
    }

}

The source code with some test classes can be found here. Please bear in mind even though it’s proven to work this code is certainly not production-ready. You can definitely make it work without requiring the temporary array, replacing full array scan when calculating max delta size with something clever or get away without that heavyweight division by doing division by reciprocal approximation. Feel free to pick those hints up or apply different micro-optimizations and build your own proprietary delta encoding protocol. It makes a vast difference for latency-sensitive trading applications reducing market data message size for liquid instruments by 20-30x. Of course you have to figure out yourself if switching to delta-compression binary encoding brings any value to your application ecosystem. Feel free to post comments with your findings!
 

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.

Leave a Reply


+ 5 = seven



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close