Как сериализовать массив из двойников в байт

Это становится намного интереснее, когда мы исследуем размеры получаемых сообщений (как функцию длины массива): 

На этом этапе преимущества применения дельта-кодирования должны стать очевидными (эта синяя кривая в равной степени относится к сериализации байтового буфера и Kryo). Здесь происходит следующее: с некоторыми знаниями о специфике обрабатываемых данных можно с уверенностью сделать предположения, которые приведут к тому, что сериализация будет более ресурсоемкой, но смехотворно намного более эффективной с точки зрения пространства. Идея дельта-сжатия очень проста. Начнем с произвольного массива целых чисел:

Если бы это были целые числа, без какого-либо сжатия нам пришлось бы использовать 4 * 9 = 36 байт для хранения данных. Что особенно интересно в этом наборе чисел, так это то, что они сгруппированы относительно близко друг к другу. Мы могли бы легко уменьшить количество байтов, необходимых для хранения данных, ссылаясь на первое значение, а затем создать массив соответствующих дельт:

Ссылка: 85103, [8, 19, 26, 39, 41, 47, 62, 74].

Вау! Теперь мы можем уменьшить массив байтов. Давайте сделаем расчеты снова. Нам нужно 4 байта для ссылочного значения (которое по-прежнему int) и 8 * 1 байт на дельту = 12 байтов.

Это довольно значительное улучшение по сравнению с первоначальными 36 байтами, но есть место для некоторой оптимизации. Вместо того, чтобы вычислять дельты по эталонному значению, давайте последовательно хранить различия для каждого предшественника:

Ссылка: 85103, [8, 11, 7, 13, 2, 6, 15, 12]

В результате получается немонотонный набор чисел, характеризующийся низкой дисперсией и стандартным отклонением. Я надеюсь, что уже стало ясно, к чему это ведет. Тем не менее, стоит немного поработать. 

На этом мы, по сути, и остановились на этом этапе — это набор, который является идеальным кандидатом для двоичного кодирования. Для нашего примера это просто означает, что можно разместить 2 дельты в одном байте. Нам нужен только клочок (4 бита) для размещения значений в диапазоне от 0 до 15, поэтому мы можем легко сойтись с конечным сжатием исходного массива в 4 (для справки) + 8 * 1/2 = 8 байтов.

Поскольку цены выражаются десятичными числами, применение дельта-сжатия с двоичным кодированием будет включать установление максимальной поддерживаемой точности и обработку десятичных чисел как интегралов (умножение их на точность 10 ^), что делает 1.12345678 с точностью 6 целым числом 1123456. Пока что все это было чисто теоретическим предположением с некоторыми сюжетами в начале этой статьи. Я думаю, что сейчас подходящий момент, чтобы продемонстрировать, как эти идеи могут быть реализованы в Java с помощью двух очень простых классов. 

Начнем со стороны кодирования:

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);
    }
}

 

  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);
    }
 
}

Исходный код с некоторыми тестовыми классами можно найти  здесь . Пожалуйста, имейте в виду, несмотря на то, что доказано, что этот код, безусловно, не готов к работе. Вы определенно можете заставить его работать, не требуя временного массива, заменив полное сканирование массива при вычислении максимального размера дельты чем-то умным, или уйдите без этого тяжелого деления, выполнив деление по обратной аппроксимации.

Не стесняйтесь подбирать эти подсказки или применять различные микрооптимизации и создавать собственный проприетарный протокол дельта-кодирования. Это имеет огромное значение для чувствительных к латентности торговых приложений, уменьшая размер сообщений рыночных данных для ликвидных инструментов в 20-30 раз. Конечно, вы должны выяснить сами, если переключение на двоичное кодирование с дельта-сжатием приносит какую-то пользу вашей экосистеме приложения. Не стесняйтесь оставлять комментарии со своими результатами!