Variable-Length-Integer effizient in C/C++ kodieren

Die Verwendung fester Integer-Breiten ist in vielen Fällen platzineffizient, besonders wenn die Mehrheit der Werte niedrig ist und nur die niederwertigsten Bytes verwendet.

Dieser Leitfaden beschreibt die Grundlagen der Varint-Kodierung (Variable-Length Integer) mit Fokus auf C++ als Programmiersprache, aber die grundlegenden Konzepte gelten für jede Sprache.

Varint-Kodierungen verwenden nur die Bytes, die benötigt werden, um den Integer-Wert angemessen zu repräsentieren. Ein Varint-Algorithmus kann die Zahl 10 in nur einem Byte darstellen, während er 4 Bytes benötigt, um 800000000 (800 Millionen) zu kodieren. In vielen Anwendungen führt dies zu einer signifikanten Reduzierung des Overheads, da man größere Integer verwenden müsste, wenn es eine leichte Chance gibt, dass die Werte über die Grenze des Integer-Typs hinauswachsen, der für die Mehrheit der Werte geeignet ist. Zusätzlich kann man normalerweise nur 8-, 16-, 32- oder 64-Bit-Integer verwenden, während 48-Bit-Integer in den meisten Sprachen manuell kodiert werden müssen. Wenn beispielsweise die meisten Werte zwischen 0 und 100 liegen, aber einige wenige größer als 16384 sein könnten (für vorzeichenlose Integer), würde man normalerweise einen vollen 32-Bit-Integer verwenden, auch wenn die meisten Werte durch ein einziges Byte dargestellt werden könnten.

Wann (und wann nicht) Varint-Kodierung verwenden?

Nicht alle Anwendungen können von Varint-Kodierung profitieren, und einige benötigen spezielle Algorithmen zusätzlich zum Varint-Encoder (siehe Delta-Kodierung).

Wenn Leistung und/oder Platz in deiner Anwendung wirklich kritisch sind, stelle dir diese Fragen:

Reduziert der gewählte Varint-Algorithmus wirklich den Platzbedarf zur Darstellung der Daten?

• Der in diesem Beitrag beschriebene MSB-Algorithmus funktioniert nicht gut für große Zahlen und verwendet häufig mehr Platz als Integer fester Breite.
• Am meisten Platz wird gespart, wenn man eine große Menge sehr kleiner Zahlen hat, aber wenige Zahlen im Datensatz riesig im Vergleich zu den anderen sind.

Gibt es eine absolute Grenze für die Länge des Integers?

• Theoretisch existiert keine Grenze
• Spezifische Varint-Implementierungen können unter undefiniertem Verhalten aufgrund von Zählerüberläufen leiden
• Generell begrenzt der verfügbare Speicher die Ausgabegröße.

Überwiegt der durch die Reduzierung der IO-Bytes gewonnene Performancegewinn den Varint-Kodierungs-/Dekodierungs-Overhead?

• Wenn der Platz so stark begrenzt ist, dass man keine Integer fester Breite für die Aufgabe verwenden kann und den Performance-Overhead nicht in Kauf nehmen kann, ist das Systemdesign wahrscheinlich fehlerhaft.

Welches Massenspeichermedium wird beschrieben?

• Festplatten haben eine geringe Wahlfreiheit und moderate sequenzielle Lesegeschwindigkeit, daher ist Fragmentierung wichtig. Wenn man die Wahrscheinlichkeit verbessern kann, dass ein Lesezugriff gecached oder sequenziell ist, indem man Varints verwendet, profitiert man wahrscheinlich davon.
• USB-Sticks haben eine geringe bis moderate Lesegeschwindigkeit und normalerweise eine etwas geringere Wahlfreiheit. Fragmentierung ist nicht so wichtig, aber bei großen Datensätzen kann die gesamte Lesezeit einen spürbaren Unterschied machen.
• SSDs haben hohe Lesegeschwindigkeiten und fast genauso hohe Wahlfreiheit. Fragmentierung ist überhaupt nicht wichtig (außer in sehr speziellen Fällen). Da die Gesamtgeschwindigkeit so hoch ist, müssen Varints eine signifikante Reduzierung des Speicherverbrauchs bewirken, um den Overhead aufzuwiegen.
• RAM ist ein Sonderfall, da man fast immer in RAM schreibt, bevor man auf eines der anderen Massenspeichermedien schreibt. RAM ist extrem schnell sowohl im sequenziellen als auch im Wahlfrei-Modus, aber seine Größe ist stark begrenzt. Wenn in deiner Anwendung der Datensatz in RAM statt auf der Festplatte gespeichert werden kann, weil die Größe durch Varints reduziert wird, steigt die Performance normalerweise um mehrere Größenordnungen. Wenn der Datensatz so klein ist, dass er leicht in RAM passt, überwiegt der IO-Performancegewinn (hauptsächlich durch Reduzierung von Pagefaults) selten den Overhead, außer in einigen sehr speziellen Fällen wie RAM-Fragmentierung – aber diese sind ziemlich selten und unglaublich schwer zu profilieren.

Könnte das Neuberechnen der Daten schneller sein als das Lesen der varint-kodierten Daten vom Massenspeichermedium?

• Macht es wirklich einen Unterschied oder verschwendest du deine Zeit für 0,1% mehr Effizienz, wo es nicht wirklich notwendig ist? (Siehe Wikipedia zu Opportunitätskosten)
• Macht es deinen Code unlesbar oder verringert es deine Codequalität in irgendeiner anderen Weise?

MSB-Varint-Kodierung

MSB bedeutet most-significant bit (in einigen anderen Fällen könnte es most significant byte bedeuten, also aufpassen!). Der Algorithmus basiert auf der Annahme, dass die höchstwertigen Bytes seltener verwendet werden als die niederwertigsten Bytes (daher funktioniert er am besten für kleine Zahlen).

Für jedes Byte im Strom der vom MSB-Algorithmus erzeugten Bytes wird das höchstwertige Bit nur gesetzt, wenn es ein nächstes Byte im Strom gibt. Daher kann jedes Byte nur sieben Bits des Wertes repräsentieren, aber es muss kein Größenbyte extern gespeichert werden. Für Integer, die kleiner oder gleich 2^64 sind, ist die MSB-Kodierung genauso platzsparend (für 64-Bit-Integer) oder platzsparender (für 48-Bit-oder-kleiner-Integer) als das externe Speichern eines Größenbytes und das einfache Abschneiden der ungenutzten höchstwertigen Bytes.

Wenn wir beispielsweise den Integer 1 (00000001) kodieren, würde er einfach als 1 (00000001) kodiert werden, da 1 < 127 (2^7-1) und der Algorithmus daher nur ein Bit benötigt (daher ist das höchstwertige Bit nicht gesetzt).

Wenn wir jedoch 255 (11111111) kodieren, hat das erste Byte das Next-Byte-Flag gesetzt (d.h. das höchstwertige Bit). Das erste Varint-Byte wäre daher 11111111, da alle 7 Datenbits in 255 gesetzt sind, während das zweite Byte das Flag nicht gesetzt hat und nur das verbleibende Datenbit anzeigt (2. Varint-Byte: 00000001).

Ein komplexeres Beispiel wäre die Kodierung von 814 – das erste Byte hat das Next-Byte-Flag gesetzt, aber nicht alle Datenbits sind gesetzt (erstes Varint-Byte wäre 10101110), das zweite Byte hat das Next-Byte-Flag nicht gesetzt und enthält die verbleibenden Datenbits (das zweite Varint-Byte wäre 10000010).

Encoder/Decoder schreiben

Wenn man das Prinzip verstanden hat, ist das Schreiben des Encoders und Decoders ziemlich einfach.

Im Encoder weiß man, ob ein zusätzliches Byte benötigt wird, wenn der Wert > 127 ist. Daher weiß man, ob das Next-Byte-Flag gesetzt werden muss. Dann nimmt man einfach die 7 niederwertigsten Bits der Daten, erhöht den Array-Index (oder was auch immer man verwendet), auf den man schreibt, schiebt die Daten um 7 Bits nach rechts und startet die Schleife neu.

Der Decoder ist genauso einfach: Man nimmt die 7 niederwertigsten Bits des aktuellen Varint-Eingabebytes, multipliziert sie mit 2^7 multipliziert mit dem (0-basierten) Index des Eingabebytes und stoppt die Schleife, wenn man auf ein Byte trifft, das das Next-Byte-Flag nicht gesetzt hat.

Vorzeichenlose vs. vorzeichenbehaftete Integer

Im Allgemeinen müssen wir nur den Fall vorzeichenloser Integer behandeln, da jeder vorzeichenbehaftete Integer implizit oder explizit in einen vorzeichenlosen Integer umgewandelt werden kann. Dies kann jedoch zu einer extrem ineffizienten Varint-Kodierung führen, da das höchstwertige Bit der Eingabe normalerweise zur Darstellung des Vorzeichens verwendet wird (siehe Wikipedia zum Zweierkomplement). Der Algorithmus funktioniert daher so ineffizient wie möglich und verwendet 5 Bytes für 32-Bit-Integer und 10 Bytes für 64-Bit-Integer (25% mehr als die Größe des entsprechenden Integer fester Breite).

Byte-Reihenfolge

Beachte, dass es zwei verschiedene mögliche sequenzielle Anordnungen beim Speichern des Varint-Ergebnisses gibt: Der oben beschriebene Algorithmus ist Little-Endian (siehe Wikipedia zu Endianness). Man kann zwischen den Byte-Reihenfolgen konvertieren, indem man die Bytes der Ausgabe umkehrt – das sollte man im Kopf behalten, wenn man heterogene Systeme entwirft (Die Netzwerk-Byte-Reihenfolge ist als Big-Endian standardisiert.)

MSB-Kodierung für vorzeichenlose Integer in C++

In C++ kann man diese template-basierte Header-Datei für einfaches Kodieren und Dekodieren von Integers variabler Länge mit dem oben beschriebenen Algorithmus verwenden.

/**
 * C++ utilities for variable-length integer encoding
 * Compile with -std=c++11 or higher
 *
 * Version 1.1: Use size_t for size argument, improve function signatures
 *
 * License: CC0 1.0 Universal
 * Originally published on https://techoverflow.net
 * Copyright (c) 2015 Uli Koehler
 */
#ifndef __VARIABLE_LENGTH_INTEGER_H
#define __VARIABLE_LENGTH_INTEGER_H

#include <cstdint>

/**
 * Encodes an unsigned variable-length integer using the MSB algorithm.
 * This function assumes that the value is stored as little endian.
 * @param value The input value. Any standard integer type is allowed.
 * @param output A pointer to a piece of reserved memory. Must have a minimum size dependent on the input size (32 bit = 5 bytes, 64 bit = 10 bytes).
 * @return The number of bytes used in the output memory.
 */
template<typename int_t = uint64_t>
size_t encodeVarint(int_t value, uint8_t* output) {
    size_t outputSize = 0;
    //While more than 7 bits of data are left, occupy the last output byte
    // and set the next byte flag
    while (value > 127) {
        //|128: Set the next byte flag
        output[outputSize] = ((uint8_t)(value & 127)) | 128;
        //Remove the seven bits we just wrote
        value >>= 7;
        outputSize++;
    }
    output[outputSize++] = ((uint8_t)value) & 127;
    return outputSize;
}

/**
 * Decodes an unsigned variable-length integer using the MSB algorithm.
 * @param value A variable-length encoded integer of arbitrary size.
 * @param inputSize How many bytes are
 */
template<typename int_t = uint64_t>
int_t decodeVarint(uint8_t* input, size_t inputSize) {
    int_t ret = 0;
    for (size_t i = 0; i < inputSize; i++) {
        ret |= (input[i] & 127) << (7 * i);
        //If the next-byte flag is set
        if(!(input[i] & 128)) {
            break;
        }
    }
    return ret;
}

#endif //__VARIABLE_LENGTH_INTEGER_H

Hier ist ein einfaches Test- und Demoprogramm:

/**
 * Test program for varint.hpp
 *
 * Compile like this: g++ -std=c++11 -o varint-test varint-test.cpp
 *
 * License: CC0 1.0 Universal
 * Originally published on https://techoverflow.net
 * Copyright (c) 2015 Uli Koehler
 */
#include <iostream>
#include <string>

#include "varint.hpp"

using namespace std;

int main(int argc, char** argv) {
    uint8_t* buf;
    size_t outsize = encodeVarint<uint64_t>(0xCAFE, buf);
    //Should print 51966
    std::cout << decodeVarint(buf, outsize) << endl;
}