Speeding Up (Small) Ruby Hashes

Speeding Up (small) Ruby Hashes | byroot’s blog

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 bytes1

ar_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 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;

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...

Speeding Up (Small) Ruby Hashes

Related Articles

(no title)

Scientists reverse brain aging, with a nasal spray

NHS apologises and admits Palantir have access to identifiable patient data

AI has torched the market for junior programmers

Al Vigier: Canada's AI strategy shouldn't include secret Palantir bills