Cache Behaviour and Node Layout in Disjoint-Set Arrays

The analysis behind The Inverse Ackermann Bound and Why It Is Effectively Constant counts pointer hops, and a pointer hop in a flat array is not a unit-cost operation. It is a load whose address depends on the value just loaded, so the memory system cannot overlap it with anything else. The latency of that chain, not the number of iterations, is what determines the wall-clock cost of a find, and the two layout decisions that change it most are the width of each entry and whether the parent and auxiliary arrays are interleaved or split.

A find is a chain of dependent loads

Each step of the loop reads parent[x] and uses the value as the next address. Modern out-of-order cores can issue several independent loads per cycle, but a dependent chain defeats that: load n+1 cannot begin until load n has returned its value. If every load misses to DRAM, the chain costs the full memory latency per hop rather than the much smaller cost of a streamed, overlapping access. On current server hardware the latency is on the order of a hundred nanoseconds and the line size is 64 bytes.

The number of hops is bounded by the rank, at most ⌊log₂ n⌋, and compression usually reduces it to one or two. So the interesting regime is the one where the tree is freshly built and the array is larger than the last-level cache. At n = 10⁸, one 32-bit index per element is 400 MB; at 8 bytes per element it is 800 MB. Neither fits in cache, and a find that walks even four hops can touch four distinct lines in four distinct pages.

Two mitigations follow directly. Reducing entry width reduces both the footprint and the number of entries per line, and since a chain hop touches one entry, the line’s other seven entries are wasted unless the traversal happens to revisit them. Improving locality within a tree, by allocating nodes in the order they are unioned rather than by key, changes which lines the chain touches, not how many.

Four bytes or eight, and when four is wrong

The obvious encoding uses size_t for the parent index, because indices are compared against n and used as subscripts. That is 8 bytes per element on every 64-bit platform. A 32-bit index halves the footprint and doubles the entries per line, from 8 to 16.

A plain 32-bit index covers n up to 2³² - 1, and the self-parenting root marker parent[x] == x reserves no value, because an element’s own index is always a legal index. The negative-size encoding does reserve range: with int32_t the storable size is bounded by 2³¹ - 1, so a block larger than that cannot be represented. The array itself is already 8 GiB at n = 2³¹, which is why the bound is rarely the binding constraint in practice — but a block that outgrows it overflows the stored size and the structure starts treating a root as a child. The arithmetic that overflows is signed, so the language does not define the result; in practice the symptom is a wrong answer rather than a diagnostic.

#include <stdint.h>
#include <stddef.h>

/* 32-bit index, 32-bit negative size at roots. n must be < 2^31. */
static uint32_t find32(int32_t *parent, uint32_t x) {
    while (parent[x] >= 0)
        x = (uint32_t)parent[x];
    return x;
}

static void unite32(int32_t *parent, uint32_t a, uint32_t b) {
    uint32_t ra = find32(parent, a), rb = find32(parent, b);
    if (ra == rb) return;
    if (parent[ra] > parent[rb]) { uint32_t t = ra; ra = rb; rb = t; }
    parent[ra] += parent[rb];
    parent[rb] = (int32_t)ra;
}

Note the cast in the union: parent[rb] = (int32_t)ra requires ra < 2³¹, which the size bound guarantees. Without the guarantee the cast is implementation-defined at best.

A narrower index is possible when n is known to be small. At n ≤ 2¹⁶, a 16-bit index halves the array again, and at n ≤ 2⁸ a byte suffices; the access then costs a single zero-extending load, as on x86-64. The pattern is the same one used for adjacency arrays and sparse matrices: choose the index width from the largest index, not from the platform word size.

One array of structs or two parallel arrays

Union by rank needs a second field per root: the rank, or the size. The natural encoding packs both into one array of 8-byte structs, which puts a node’s parent and its rank in the same line. The alternative keeps two arrays, parent and rank, each indexed the same way.

The packed layout wins on the common case: a find that ends at a root needs the parent link, and a unite that compares two roots needs both ranks, so one line fetch serves the whole step. At 8 bytes per node, eight nodes share a line. The alternative that stores a negative size at roots, described in Union by Rank and Path Compression, needs no separate rank array at all, which is why it is the usual choice when space matters more than clarity.

The split layout wins when the rank array is only read at roots, which is a small fraction of nodes, and when the parent array benefits from being narrower. A structure with 4-byte parents and a separate 1-byte rank array is 5 bytes per element instead of 8, at the cost of two loads instead of one at a root. Whether that trade is favourable depends on the ratio of root visits to path steps, which is a property of the workload and not of the algorithm.

A third layout keeps the parent array but replaces the rank with a per-root size stored outside the node array, in a hash table keyed by root index. That saves the rank field for all non-root nodes — the vast majority — but adds a hash lookup at every union. The hash lookup is a dependent load of its own, so the saving in footprint is paid for in latency.

Keys are not indices

The array is addressed by dense integers. Application keys are frequently not dense: file paths, interned strings, 64-bit node identifiers, or coordinates. Two mechanisms bridge the gap.

Coordinate compression sorts the distinct keys, assigns each its rank, and stores the mapping in a sorted array. The mapping costs O(k log k) to build for k distinct keys and O(log k) per lookup, or O(1) with a perfect hash. The disjoint-set array then indexes by position. This is the right choice when the key set is known before any union, which is the common case for graph algorithms where the vertex set comes from a parsed input file.

A hash map from key to index handles keys discovered incrementally, at the cost of one lookup per operation plus the array hops after it. The map lookup happens once per find, not once per hop, so its cost does not multiply with the path length — but it does add one dependent load ahead of every chain, and that load is on the critical path.

#include <stdint.h>
#include <stddef.h>

struct keymap { uint64_t *keys; uint32_t *vals; unsigned char *occupied; size_t cap, count; };

/* Insert-on-first-use map over a table whose cap is a power of two. `count` is
   also the next dense index to hand out, so indices are assigned densely by
   first appearance. The caller rehashes before the table is more than half full. */
static uint32_t intern(struct keymap *m, uint64_t key) {
    size_t mask = m->cap - 1;
    size_t i = (size_t)(key * 0x9E3779B97F4A7C15ULL) & mask;   /* Fibonacci hashing */
    while (m->occupied[i]) {
        if (m->keys[i] == key) return m->vals[i];              /* key already interned */
        i = (i + 1) & mask;                                    /* linear probing */
    }
    m->keys[i] = key;
    m->vals[i] = (uint32_t)m->count;
    m->occupied[i] = 1;
    return (uint32_t)m->count++;
}

The failure mode here is a key set with a bad hash, which collapses the probe sequence into a linear scan and makes the map, not the forest, the bottleneck. With a fully compressed forest the paths are one hop, so the map is a large share of the total; with an uncompressed one the chains dominate and the map is noise.

Prefetching a chain that cannot be prefetched

Hardware prefetchers detect strides, not pointer chains, so a find gets no help from them. Software prefetching can help in one specific pattern: when the caller knows several independent elements to resolve, it can issue the first load of each chain before walking any of them. That converts one chain of latency into k parallel chains, and the win is proportional to k up to the number of outstanding misses the core supports.

/* Resolve k independent elements, overlapping their first loads. */
for (size_t i = 0; i < k; i++)
    __builtin_prefetch(&parent[elem[i]], 0, 1);
for (size_t i = 0; i < k; i++)
    roots[i] = find32(parent, elem[i]);

The same trick applies inside a single find only if the path can be discovered without walking it, which it cannot. This is the structural reason why compression helps more than the hop count suggests: it does not make the chain faster, it makes the chain shorter, and the chain’s cost is latency times length.

A related optimization is to store the parent array in huge pages when n is large. A 400 MB array spans about 100,000 4 KiB pages, or 200 2 MiB pages. Each find hop that misses in the TLB pays a page-walk in addition to the data access, and the page-walk structures themselves (the upper levels of the table, cached) are more likely to stay resident when there are fewer pages. Explicit huge-page allocation is platform-specific and often unavailable to library code above the operating system’s allocator, so the effect is usually reached through an allocator or a mmap of a reserved region rather than through a portable call.

The choice between these options interacts with the amortized structure. A compressed forest with a 4-byte parent array is the fastest configuration for cache-resident workloads; a wider, unpacked representation with an external rank array is easier to serialize and to reason about, and the difference disappears once the structure is dominated by I/O. The remaining performance work in this cluster is not on the forest at all but on the bit-parallel structures that replace it, beginning with Bitset Representation and Word-Level Rank and Select.