Speeding Up (Small) Ruby Hashes

Speeding Up (small) Ruby Hashes Something I must confess is that I absolutely hate writing these blog posts. It’s not quite as bad as having to give a conference talk, but it’s up there on the list of activities that feel like pulling teeth to me. Not that I’m not proud of the result. I absolutely am. But the process of writing them is very painful for me. It’s particularly true of the very first sentence, as the post progresses, it gets a bit easier Yet, I force myself to do it, because it helps me think about problems, and “compile” knowledge in my head. I’m so terrified of posting something wrong or inaccurate that I tend to double-check some long-held assumptions, dig into more details about how some things are implemented, etc. And very often, quickly after publishing the post, I think of new ideas I previously missed. This post is about one such idea I had right after publishing the previous one on shrinking Ruby hashes. If you haven’t read it yet, please do, as this one is a direct continuation. AR Tables Aren’t Hash Tables One of the main takeaways from the previous post is that, up to 8 entries, Ruby’s Hash class isn’t truly a Hash Table as its name would make you think. Instead, it’s literally an array of pairs. Let’s look at its data structure: #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 can be a little cryptic to the uninitiated, so let me unpack it: VALUE is the Ruby object reference, basically a pointer, so 8 bytes1ar_hint is 8 bytes long, and can be interpreted as either an array of 8 bytes, or as a single 8-byte (64-bit) integer.pairs is the array containing our key-value pairs. As I mentioned in the previous post, a hint is essentially a single-byte hash-code. In Ruby, hash-codes are 8 bytes long, and when backed by an st_table (the real hash-table implementation), the entire hash-code is stored and compared. But to save memory, ar_table only stores the lower byte of the hash-code. Fundamentally, that doesn’t change anything, except make hash collisions more likely, but that’s an acceptable tradeoff when we know we never have any more than 8 keys. If we were to implement ar_table in Ruby, the structure for {a: 1, b: 2, c: 3} could look like this: class ARTable def initialize @ar_hint = [0x34, 0x65, 0x72] @pairs = [:a, 1, :b, 2, :c, 3] end end Now let’s look at the core of the ar_table lookup routine, the one I looked at closely while writing the previous post, but that I never really thought of deeply before then: // Returns the bin index if found, RHASH_AR_TABLE_MAX_BOUND if not found, // or RHASH_AR_TABLE_CONVERTED_TO_ST_TABLE if #eql? or a Thread converted the hash to st_table. static unsigned ar_find_entry_hint(VALUE hash, ar_hint_t hint, st_data_t key) { for (unsigned i = 0; i 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; } As you may be able to see, it’s essentially a linear, AKA O(n) , search. We receive the hint of the key we’re searching for, and linearly search for a match in the table list. When a match is found, since we have to worry about collisions, we invoke Object#eql? (ar_equal ), and if it returns false, we continue our search until we reach the end of the array. This O(n) performance can be verified experimentally: 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 ruby 4.1.0dev (2026-08-11T14:41:10Z c-api-shareable-co.. ab6b8ceaac) +YJIT +PRISM [arm64-darwin25] ar-hit-0 14.188M (± 0.8%) i/s (70.48 ns/i) - 71.928M in 5.069797s ar-hit-1 13.247M (± 0.3%) i/s (75.49 ns/i) - 67.139M in 5.068423s ar-hit-2 11.890M (± 0.4%) i/s (84.11 ns/i) - 60.027M in 5.048655s ar-hit-3 11.119M (± 1.7%) i/s (89.94 ns/i) - 56.290M in 5.062484s ar-hit-4 10.456M (± 1.5%) i/s (95.64 ns/i) - 53.056M in 5.074381s ar-hit-5 10.018M (± 0.4%) i/s (99.82 ns/i) - 50.464M in 5.037463s ar-hit-6 9.380M (± 2.9%) i/s (106.61 ns/i) - 47.215M in 5.033578s ar-hit-7 8.983M (± 0.6%) i/s (111.32 ns/i) - 45.158M in 5.026746s ar-miss 9.163M (± 1.9%) i/s (109.14 ns/i) - 46.161M in 5.037831s Comparison: ar-hit-0: 14187571.6 i/s ar-hit-1: 13246581.8 i/s - 1.07x slower ar-hit-2: 11889678.7 i/s - 1.19x slower ar-hit-3: 11118989.8 i/s - 1.28x slower ar-hit-4: 10455642.8 i/s - 1.36x slower ar-hit-5: 10017678.5 i/s - 1.42x slower ar-hit-6: 9379948.0 i/s - 1.51x slower ar-miss : 9162845.7 i/s - 1.55x slower ar-hit-7: 8983492.7 i/s - 1.58x slower As expected, looking up the 8th key is noticeably slower than looking up the first one. When measured from the Ruby side, since there is a fixed cost overhead in the virtual machine dispatch, etc, so the measured difference is only ~1.5x , but that’s still significant. Again, given we’re only ever dealing with at most 8 entries, an O(n) algorithm is fine. In this specific case, the linear search performance isn’t that far from what it would be if the Hash was backed by an st_table : require 'benchmark/ips' ar = {a:1, b:2, c:3, d:4, e:5, f:6, g:7, h:8}.freeze # Creating a hash with a capacity > 8 gives us an 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 ruby 4.1.0dev (2026-08-11T14:41:10Z c-api-shareable-co.. ab6b8ceaac) +YJIT +PRISM [arm64-darwin25] ar-hit-7 8.967M (± 1.9%) i/s (111.52 ns/i) - 45.030M in 5.021777s st-hit-7 10.574M (± 0.1%) i/s (94.57 ns/i) - 53.527M in 5.061952s Comparison: ar-hit-7: 8966929.4 i/s st-hit-7: 10574312.0 i/s - 1.18x faster So using ar_table versus st_table is your classic space vs time trade-off. Yet, when most people think about hash tables, they think about O(1) access, so it feels slightly wrong. But what if ar_table lookups could be made O(1) too? SWAR Search The core of ar_find_entry_hint is a loop that searches for a specific integer in an array of 8 such integers. But if you look at it from another angle, it’s searching for a specific byte, AKA character, inside an array of bytes, AKA string, of length 8. Efficiently searching for characters in strings is something I’ve done a lot in the json gem, and that I’ve touched on previously on this blog. Searching byte by byte in a string is quite wasteful, because the cost of iterating over each byte tends to dwarf the cost of comparing said bytes. And in our case, we’re looking at 8 bytes, so exactly the size of our CPU registers, which makes it a perfect fit for SWAR, which stands for SIMD within a register. I previously posted a quick explanation of what SIMD (and incidentally SWAR) is, so I’m not gonna repeat it here. But the crux of the idea is that instead of interpreting ar_hint as a list of 8 1-byte long numbers, we can interpret it as a single 8-byte number, then, as long as we make sure not to overflow, we can perform the same operations on all these bytes all at once. This is a common enough trick that the Wikipedia article directly showcases how to find a NULL byte inside an 8-byte number: #include #include 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); has_null_byte(0x1020304000607080); return 0; } 0x1020304050607080 does not have a NULL byte 0x1020304000607080 has a NULL byte The above example might sound a bit like magic, so let’s try to unpack it. The very first step is word & 0x7f7f7f7f7f7f7f7f , or scoped to a byte, byte & 0x7f (127 ), or in binary form byte & 0b01111111 . In other words, we get rid of the most significant bit of each byte, which is necessary to prevent the next operation from ever overflowing. Then for each byte we add that same 0x7f value. The idea is that since 0x7f is 0b01111111 if the byte contained anything but 0 , the addition carry will cause the most significant bit to be set to 1 . e.g. 0b00000000 + 0b01111111 = 0b01111111 0b00000001 + 0b01111111 = 0b10000000 0b00000010 + 0b01111111 = 0b10000001 - … So all the bytes that had any of their 7 lower bits set now have their 8th bit set too. However, we need to handle 0x80 / 0b10000000 specifically, as it got its most significant bit discarded by the first bitwise AND . To restore that most significant bit, we do a b