self_validating_handles.c

struct Object {
    Key key; // The key is any piece of data that uniquely identifies the object.
    // ...
};

struct Handle {
    Key key;
    Index index; // This caches a speculative table index for an object with the corresponding key.
};

Object *deref(Handle *h) {
    Index i = h->index; // This doesn't have to be atomic because we will validate whatever we read.
    if (i < num_objects) {
        Object *o = objects + i;
        if (o->key == h->key) return o; // Fast: Well-predicted path, object key is only a control dependency, acts as prefetch.
    }
    i = find(h->key); // Slow: One or more branch mispredicts, must perform hash table lookup.
    h->index = i; // As with the read, this write also doesn't have to be atomic.
    // Next time this handle gets dereferenced, it will hit the fast path unless the object has since been relocated.
    return objects + i;
}