Het versnellen van (kleine) Ruby Hashes

Niet dat ik niet trots ben op het resultaat; dat ben ik absoluut. Maar het proces van het schrijven ervan is zeer pijnlijk voor me. Dit geldt met name voor de allereerste zin; naarmate het bericht vordert, wordt het iets makkelijker.

Toch dwing ik mezelf om het te doen, omdat het me helpt om over problemen na te denken en kennis in mijn hoofd te "compileren". Ik ben zo bang om iets fouts of onnauwkeurigs te plaatsen, dat ik de neiging heb om langgekoesterde aannames dubbel te checken, dieper in de details van implementaties te duiken, enzovoort. Vaak denk ik kort na publicatie aan nieuwe ideeën die ik eerder had gemist.

Dit bericht gaat over zo'n idee dat ik kreeg vlak na het publiceren van het vorige artikel over het verkleinen van Ruby hashes. Als je die nog niet hebt gelezen, doe dat dan a.u.b., want dit is een direct vervolg.

AR-tabellen zijn geen hashtabellen

Een van de belangrijkste conclusies uit het vorige bericht is dat Ruby's Hash-klasse, tot een maximum van 8 items, niet echt een hashtabel is, zoals de naam doet vermoeden. In plaats daarvan is het letterlijk een array van paren.

Laten we kijken naar de datastructuur:

#define RHASH_AR_TABLE_MAX_SIZE SIZEOF_VALUE
typedef unsigned char ar_hint_t;

typedef struct ar_table_pair_struct {
    VALUE key;
    VALUE val;
} ar_table_pair;

typedef struct ar_table_struct {
    union {
        ar_hint_t ary[RHASH_AR_TABLE_MAX_SIZE];
        VALUE word;
    } ar_hint;
    /* 64bit CPU: 8B * 2 * 8 = 128B */
    ar_table_pair pairs[RHASH_AR_TABLE_MAX_SIZE];
} ar_table;

C kan wat cryptisch zijn voor niet-ingewijden, dus laat me dit uitleggen:

• VALUE is de referentie naar het Ruby-object, in feite een pointer van 8 bytes [^1].
• ar_hint is 8 bytes lang en kan worden geïnterpreteerd als een array van 8 bytes, of als een enkel 8-byte (64-bit) integer.
• pairs is de array die onze sleutel-waarde paren bevat.

Zoals ik in het vorige bericht noemde, is een hint in essentie een hash-code van één byte. In Ruby zijn hash-codes 8 bytes lang. Wanneer deze worden ondersteund door een st_table (de echte hashtabel-implementatie), wordt de volledige hash-code opgeslagen en vergeleken.

Om geheugen te besparen, slaat ar_table echter alleen de onderste byte van de hash-code op. In principe verandert dat niets, behalve dat hash-collisions waarschijnlijker worden, maar dat is een acceptabele afweging wanneer we weten dat we nooit meer dan 8 sleutels hebben.

Als we ar_table in Ruby zouden implementeren, zou de structuur voor {a: 1, b: 2, c: 3} er zo uit kunnen zien:

class ARTable
  def initialize
    @ar_hint = [0x34, 0x65, 0x72]
    @pairs = [:a, 1, :b, 2, :c, 3]
  end
end

Laten we nu kijken naar de kern van de ar_table lookup-routine:

// Retourneert de bin-index als deze is gevonden, RHASH_AR_TABLE_MAX_BOUND als deze niet is gevonden,
// of RHASH_AR_TABLE_CONVERTED_TO_ST_TABLE als #eql? of een Thread de hash heeft omgezet naar st_table.
static unsigned
ar_find_entry_hint(VALUE hash, ar_hint_t hint, st_data_t key)
{
    for (unsigned i = 0; i < RHASH_AR_TABLE_BOUND(hash); i++) {
        const ar_hint_t *hints = RHASH_AR_TABLE(hash)->ar_hint.ary;
        if (hints[i] == hint) {
            ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
            int eq = ar_equal(key, pair->key);
            if (UNLIKELY(!RHASH_AR_TABLE_P(hash))) {
                return RHASH_AR_TABLE_CONVERTED_TO_ST_TABLE;
            }
            if (eq) {
                return i;
            }
        }
    }
    return RHASH_AR_TABLE_MAX_BOUND;
}

Zoals je kunt zien, is dit in feite een lineaire zoekopdracht, oftewel $O(n)$. We ontvangen de hint van de sleutel waarnaar we zoeken en zoeken lineair naar een overeenkomst in de tabel. Wanneer er een match is gevonden, moeten we rekening houden met collisions; we roepen dan Object#eql? (ar_equal) aan. Als dit false retourneert, gaat de zoektocht verder tot het einde van de array is bereikt.

Deze $O(n)$ prestatie kan experimenteel worden geverifieerd:

require 'benchmark/ips'
ar = {a:1, b:2, c:3, d:4, e:5, f:6, g:7, h:8}.freeze
Benchmark.ips do |x|
  x.report("ar-hit-0") { ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a]; ar[:a] }
  x.report("ar-hit-1") { ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b]; ar[:b] }
  x.report("ar-hit-2") { ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c]; ar[:c] }
  x.report("ar-hit-3") { ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d]; ar[:d] }
  x.report("ar-hit-4") { ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e]; ar[:e] }
  x.report("ar-hit-5") { ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f]; ar[:f] }
  x.report("ar-hit-6") { ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g]; ar[:g] }
  x.report("ar-hit-7") { ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h] }
  x.report("ar-miss ") { ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X]; ar[:X] }
  x.compare!(order: :baseline)
end

Resultaten:

• ar-hit-0: 14.188M i/s
• ar-hit-7: 8.983M i/s (1.58x langzamer)
• ar-miss: 9.163M i/s (1.55x langzamer)

Zoals verwacht is het opzoeken van de achtste sleutel merkbaar langzamer dan de eerste. Gemeten vanaf de Ruby-kant is het verschil slechts ~1.5x vanwege de vaste overhead in de virtuele machine, maar dat is nog steeds significant.

Gezien we het maximaal over 8 items hebben, is een $O(n)$ algoritme prima. In dit specifieke geval ligt de prestatie van het lineair zoeken niet ver af van wat het zou zijn als de Hash werd ondersteund door een st_table:

require 'benchmark/ips'
ar = {a:1, b:2, c:3, d:4, e:5, f:6, g:7, h:8}.freeze
# Een hash maken met een capaciteit > 8 geeft ons een `st_table`
st = Hash.new(capacity: 9).merge(ar).freeze
Benchmark.ips do |x|
  x.report("ar-hit-7") { ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h]; ar[:h] }
  x.report("st-hit-7") { st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h]; st[:h] }
  x.compare!(order: :baseline)
end

Resultaten:

• ar-hit-7: 8.967M i/s
• st-hit-7: 10.574M i/s (1.18x sneller)

Het gebruik van artable versus sttable is dus de klassieke afweging tussen ruimte en tijd. Toch voelt het een beetje fout, omdat mensen bij hashtabellen vaak denken aan $O(1)$ toegang. Maar wat als lookups in ar_table ook $O(1)$ zouden kunnen zijn?

SWAR-zoeken

De kern van arfindentry_hint is een loop die zoekt naar een specifiek integer in een array van 8 integers. Vanuit een andere hoek bekeken, zoekt het naar een specifieke byte (een karakter) binnen een array van bytes (een string) van lengte 8.

Efficiënt zoeken naar karakters in strings is iets wat ik veel heb gedaan in de json gem. Byte voor byte zoeken in een string is vrij verspillend, omdat de kosten van het itereren over elke byte vaak groter zijn dan de kosten van het vergelijken van die bytes.

In ons geval kijken we naar 8 bytes, precies de grootte van onze CPU-registers. Dit maakt het perfect geschikt voor SWAR, wat staat voor SIMD within a register.

De kern van het idee is dat we ar_hint niet interpreteren als een lijst van acht 1-byte getallen, maar als één enkel 8-byte getal. Zolang we ervoor zorgen dat we niet overstromen (overflow), kunnen we dezelfde operaties op al deze bytes tegelijk uitvoeren.

Wikipedia laat bijvoorbeeld zien hoe je een NULL-byte vindt in een 8-byte getal:

#include <stdio.h>
#include <stdint.h>

static void has_null_byte(uint64_t word)
{
    uint64_t x7 = (word & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;
    uint64_t x8 = x7 | word;
    uint64_t matches = x8 | 0x7f7f7f7f7f7f7f7f;
    if (~matches) {
        printf("0x%llx has a NULL byte\n", word);
    }
    else {
        printf("0x%0llx does not have a NULL byte\n", word);
    }
}

int main(int argc, char **argv)
{
    has_null_byte(0x1020304050607080); // Geen NULL byte
    has_null_byte(0x1020304000607080); // Heeft NULL byte
    return 0;
}

Laten we dit ontleden:

1. word & 0x7f7f7f7f7f7f7f7f: We verwijderen het meest significante bit van elke byte om overflow te voorkomen bij de volgende stap.
2. We tellen 0x7f (0b01111111) op bij elke byte. Als de byte iets anders was dan 0, zal de carry ervoor zorgen dat het meest significante bit op 1 wordt gezet.
3. Omdat we de byte 0x80 (0b10000000) specifiek moeten behandelen (die werd in stap 1 verwijderd), doen we een bitwise OR met de oorspronkelijke waarde (x7 | word).
4. Nu hebben alle bytes, behalve degene die volledig nul waren, hun meest significante bit op 1 staan.
5. Door alleen dat bit te behouden (x8 | 0x7f7f7f7f7f7f7f7f) en vervolgens alle bits om te keren (~matches), worden de 0x00 bytes 0x80 en alle andere bytes 0x00. Als het resultaat 0 is, was er geen NULL-byte aanwezig.

Nullen tellen

Aangezien bitmaps veel voorkomen, hebben CPU's specifieke instructies hiervoor, zoals ffs (Find First Set), ctz (Count Trailing Zeros) of ntz (Number of Trailing Zeros).

Hier moeten we echter rekening houden met endianness. Op de meeste moderne computers (little-endian) worden getallen van rechts naar links gelezen. Daarom moet de index beginnen bij de minst significante byte.

Afhankelijk van de CPU-architectuur moeten we dus een andere functie gebruiken. Op de meeste architecturen gebruiken we ntz (trailing zeros), terwijl we op de weinige big-endian architecturen die Ruby ondersteunt, nlz (leading zeros) gebruiken.

Voor 32-bit en 64-bit architecturen resulteert dit in een macro zoals deze:

#if SIZEOF_VALUE == 8
#ifdef WORDS_BIGENDIAN
#define AR_HINT_FIND_FIRST_ZERO_BYTE(x) (nlz_int64(x) / CHAR_BIT)
#else
#define AR_HINT_FIND_FIRST_ZERO_BYTE(x) (ntz_int64(x) / CHAR_BIT)
#endif
#else
#ifdef WORDS_BIGENDIAN
#define AR_HINT_FIND_FIRST_ZERO_BYTE(x) (nlz_int32(x) / CHAR_BIT)
#else
#define AR_HINT_FIND_FIRST_ZERO_BYTE(x) (ntz_int32(x) / CHAR_BIT)
#endif
#endif

Integer-divisie is over het algemeen traag [^2], maar omdat we hier altijd delen door de constante 8, zal elke fatsoenlijke C-compiler dit optimaliseren naar een right-shift operatie (x >> 3), wat zeer snel is.

We kunnen nu niet alleen zien of er een NULL-byte is, maar ook waar deze staat:

static void first_null_byte(uint64_t word)
{
    uint64_t x7 = (word & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;
    uint64_t x8 = x7 | word;
    uint64_t matches = x8 | 0x7f7f7f7f7f7f7f7f;
    uint64_t indexes = ~matches;
    if (indexes) {
        printf("0x%llx has a NULL byte at index %u\n", word, __builtin_ctzll(indexes) / CHAR_BIT);
    }
    else {
        printf("0x%0llx does not have a NULL byte\n", word);
    }
}

Bovendien bevat de variabele indexes de positie van alle NULL-bytes. Om de volgende positie te vinden, kunnen we het minst significante bit wissen met de truc x & (x - 1).

static void find_null_bytes(uint64_t word)
{
    uint64_t x7 = (word & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;
    uint64_t x8 = x7 | word;
    uint64_t matches = x8 | 0x7f7f7f7f7f7f7f7f;
    uint64_t indexes = ~matches;
    if (!indexes) {
        printf("does not have a NULL byte\n");
        return;
    }
    while (indexes) {
        printf("NULL byte at index %u\n", __builtin_ctzll(indexes) / CHAR_BIT);
        indexes &= indexes - 1;
    }
}

Maskers maken

Het is geweldig dat we NULL-bytes snel kunnen vinden, maar een ar_table hint is een willekeurig getal, geen 0. We moeten de bytes die we zoeken dus eerst omzetten naar nul.

Dit doen we met een XOR operatie. Als we zoeken naar 0x42, dan is 0x42 ^ 0x42 = 0. Om dit voor alle 8 bytes tegelijk te doen, maken we eerst een masker via vermenigvuldiging:

# In Ruby:
puts (0x0101010101010101 * 0x42).to_s(16)
# Resultaat: 4242424242424242

Hier is de complete C-functie om willekeurige bytes te vinden:

static void find_bytes(uint8_t needle, uint64_t haystack)
{
    uint64_t search_mask = 0x0101010101010101 * needle;
    uint64_t word = haystack ^ search_mask;
    uint64_t x7 = (word & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f;
    uint64_t x8 = x7 | word;
    uint64_t matches = x8 | 0x7f7f7f7f7f7f7f7f;
    uint64_t indexes = ~matches;
    if (!indexes) {
        printf("miss\n");
        return;
    }
    while (indexes) {
        printf("hit at index %u\n", __builtin_ctzll(indexes) / CHAR_BIT);
        indexes &= indexes - 1;
    }
}

Integratie in Ruby

Mijn eerste poging was om de for-loop in arfindentry_hint volledig te vervangen door deze SWAR-logica. Dit werkte echter niet. Erger nog: Ruby wilde niet eens compileren. Ruby bootstrapt zichzelf namelijk door eerst een minimale versie (miniruby) te compileren; omdat ik de Hash-implementatie had gebroken, faalden de build-scripts.

Wat ik over het hoofd had gezien, is dat arequal de Hash#eql? methode aanroept op willekeurige objecten. Omdat objecten hun eigen eql? methode kunnen definiëren, roepen we willekeurige code aan die de Hash kan muteren terwijl we erin zoeken. Hierdoor kunnen we na elke aanroep van arequal de resultaten van matches niet meer vertrouwen.

Uiteindelijk besloot ik dat de volledige complexiteit niet nodig was. ar_table is klein genoeg dat collisions zelden voorkomen en de kosten van een lineaire zoekopdracht beperkt zijn. Ik heb de implementatie daarom aangepast om alleen naar de eerste match te springen:

static unsigned
ar_find_entry_hint(VALUE hash, ar_hint_t hint, st_data_t key)
{
    for (unsigned i = ar_hint_first_match(hint, RHASH_AR_TABLE(hash)->ar_hint.word); i < RHASH_AR_TABLE_BOUND(hash); i++) {
        const ar_hint_t *hints = RHASH_AR_TABLE(hash)->ar_hint.ary;
        if (hints[i] == hint) {
            ar_table_pair *pair = RHASH_AR_TABLE_REF(hash, i);
            int eq = ar_equal(key, pair->key);
            if (UNLIKELY(!RHASH_AR_TABLE_P(hash))) {
                return RHASH_AR_TABLE_CONVERTED_TO_ST_TABLE;
            }
            if (eq) {
                return i;
            }
        }
    }
    return RHASH_AR_TABLE_MAX_BOUND;
}

De resultaten waren不错: de prestaties waren nu identiek, ongeacht of we de eerste of de laatste sleutel raakten, en het was merkbaar sneller bij een miss.

Om de "happy-path" (het ideale scenario) verder te optimaliseren, heb ik de eerste match gespecialiseerd. In de eerste iteratie is de check if (hints[i] == hint) namelijk redundant en verstoort het de branch predictor.

De uiteindelijke implementatie ziet er zo uit:

static unsigned
ar_find_entry_hint(VALUE hash, ar_hint_t hint, st_data_t key)
{
    unsigned first_match = ar_hint_first_match(hint, RHASH_AR_TABLE(hash)->ar_hint.word);
    if (LIKELY(first_match >= RHASH_AR_TABLE_BOUND(hash))) {
        return RHASH_AR_TABLE_MAX_BOUND;
    }
    RUBY_ASSERT(RHASH_AR_TABLE(hash)->ar_hint.ary[first_match] == hint);
    int eq = ar_equal(key, RHASH_AR_TABLE_REF(hash, first_match)->key);
    if (UNLIKELY(!RHASH_AR_TABLE_P(hash))) {
        return RHASH_AR_TABLE_CONVERTED_TO_ST_TABLE;
    }
    if (LIKELY(eq)) {
        return first_match;
    }
    else {
        for (unsigned i = first_match + 1; i < RHASH_AR_TABLE_BOUND(hash); i++) {
            const ar_hint_t *hints = RHASH_AR_TABLE(hash)->ar_hint.ary;
            if (UNLIKELY(hints[i] == hint)) {
                eq = ar_equal(key, RHASH_AR_TABLE_REF(hash, i)->key);
                if (UNLIKELY(!RHASH_AR_TABLE_P(hash))) {
                    return RHASH_AR_TABLE_CONVERTED_TO_ST_TABLE;
                }
                if (eq) {
                    return i;
                }
            }
        }
    }
    return RHASH_AR_TABLE_MAX_BOUND;
}

Met deze patch is de prestatie constant geworden:

• ar-hit-0: 13.973M i/s
• ar-hit-7: 13.998M i/s
• ar-miss: 16.053M i/s

Het mooiste is dat artable nu altijd sneller is dan sttable:

• ar-hit-7: 13.975M i/s
• st-hit-7: 10.884M i/s (1.28x langzamer)

Ik heb de patch nog niet gemerged, maar ik zie geen reden om dat niet te doen na een laatste schoonmaakbeurt.

***

[^1]: Ik ga in dit hele bericht uit van een 64-bit architectuur om het eenvoudiger te maken. [^2]: Als je Turing Complete hebt gespeeld, heb je hier waarschijnlijk een gevoel voor.