Open addressed hash containers, hand rolled for the Nim VM.

Everything Necsus does with a hash table happens while compiling, and std/tables and std/sets are surprisingly expensive there. Every lookup goes through the generic hashcommon.rawGet machinery, and std/hashes runs Wang Yi's mixer over each word of each key. Between them they account for a few million VM instructions when building the archetype graph for a large app.

These are deliberately plainer:

Entries live in flat, parallel seqs. The bucket array holds nothing but integers, so probing only reaches for a key once a hash code has already matched.
A bucket holds one plus an index into those seqs, which lets zero mean "empty" without having to prefill anything.
There is no del. Nothing here needs it, and leaving it out means a probe can stop at the first empty bucket rather than walking past tombstones.

Insertion order is preserved, so iteration is stable across compiles -- which matters when the output feeds code generation.

As with std/tables, a bucket is picked from the low bits of hash, and probing is linear. A key type whose hash leaves its low bits poorly mixed will cluster, and that shows up as a slow compile rather than as a wrong answer.

Types

OpenSet[K] = object: An open addressed hash set. Laid out like OpenTable, minus the values
OpenTable[K; V] = object: An open addressed hash table

Procs

proc `[]`[K, V](table: OpenTable[K, V]; key: K): V: The value stored against key, which has to be present
proc `[]=`[K, V](table: var OpenTable[K, V]; key: K; value: sink V): Stores value against key, replacing anything already there
proc card[K](openSet: OpenSet[K]): int
proc contains[K, V](table: OpenTable[K, V]; key: K): bool
proc contains[K](openSet: OpenSet[K]; key: K): bool
proc containsOrIncl[K](openSet: var OpenSet[K]; key: K): bool: Adds key and returns whether it was already there. This is the primitive worth reaching for -- a contains followed by an incl probes twice
proc getOrDefault[K, V](table: OpenTable[K, V]; key: K): V: The value stored against key, or a default value when it is missing
proc incl[K](openSet: var OpenSet[K]; key: K): Adds key, doing nothing if it is already there
proc initOpenSet[K](expected: int = 32): OpenSet[K]: Creates a set sized to hold expected entries without rehashing
proc initOpenTable[K, V](expected: int = 32): OpenTable[K, V]: Creates a table sized to hold expected entries without rehashing
proc key[K, V](table: OpenTable[K, V]; slot: int): K: The key held in a slot handed back by slotFor
proc len[K, V](table: OpenTable[K, V]): int
proc len[K](openSet: OpenSet[K]): int
proc setValue[K, V](table: var OpenTable[K, V]; slot: int; value: sink V): Replaces the value held in a slot handed back by slotFor
proc slotFor[K, V](table: var OpenTable[K, V]; key: K): int: The slot holding key, adding one that holds a default value if the key isn't in the table yet. Slots stay valid for the life of the table
proc value[K, V](table: OpenTable[K, V]; slot: int): V: The value held in a slot handed back by slotFor

Iterators

iterator items[K](openSet: OpenSet[K]): K: Yields every key, in the order they were added
iterator keys[K, V](table: OpenTable[K, V]): K: Yields every key, in the order they were added
iterator pairs[K, V](table: OpenTable[K, V]): (K, V): Yields every key and value, in the order they were added
iterator values[K, V](table: OpenTable[K, V]): V: Yields every value, in the order its key was added

src/necsus/util/openAddr

Types

Procs

Iterators