bitabs

nimony/src/lib/bitabs.nim

A BiTable is a table that can be seen as an optimized pair of (Table[Id, Val], Table[Val, Id]).

type BiTable = object
  vals: seq[T]
  keys: seq[Id]

proc initBiTable(): BiTable[Id,T]
proc len(t: BiTable[Id,T]): int64
proc hasId(t: BiTable[Id,T]; x: Id): bool
proc isIndexed(t: BiTable[Id,T]): bool
Whether the reverse (value -> id) index exists. It does not, and only does not, between an addOrdered fill and the first thing that needs it.
proc ensureIndexed(t: var BiTable[Id,T])
Build the reverse index if addOrdered left it unbuilt. Idempotent, and free for a table that was interned into normally.
getOrIncl calls this itself. getKeyId cannot — it takes the table immutably and changing that would break every caller in the ecosystem for the sake of the rare one — so a caller that looks up BY VALUE in a table that might have been filled with addOrdered calls this first. Getting it wrong is an assertion in getKeyId, not a wrong answer.
proc addOrdered(t: var BiTable[Id,T]; v: sink T): Id
Append v under the next id WITHOUT hashing it.
For a table deserialized in id order, every entry's id is its position, so the reverse index costs a hash and an insert per entry to reproduce something the file already states. bif.load fills four pools that way, and on a 68-module --ic:on build of the Nim compiler that was 451ms of a 637ms load, nearly all of it the symbol pool.
The table is still a BiTable: getOrIncl builds the index on demand (and ensureIndexed does it explicitly for getKeyId), so a pool that does get interned into behaves exactly as before — it just pays for the index at the point something needs it rather than always. Callers that only ever map id -> value never pay at all.
proc getKeyId(t: BiTable[Id,T]; v: T): Id
proc getOrIncl(t: var BiTable[Id,T]; v: T): Id
proc getOrInclFromView(t: var BiTable[Id,T]; v: View): Id
Optimized version that only materializes from the view v if the value does not exist yet.
proc [](t: BiTable[Id,T]; strId: Id): var T
proc hash(t: BiTable[Id,T]): uint64
as the keys are hashes of the values, we simply use them instead
proc memSize(t: BiTable[Id,T]): int64
type BiTableFloat = distinct BiTable[Id,uint64]
proc getOrIncl(t: var BiTableFloat[Id]; v: float64): Id
proc [](t: BiTableFloat[Id]; strId: Id): float64