cf9073a | plum | pyrossh

git clone https://git.pyrossh.dev/plum

A statically typed, imperative programming language inspired by rust, python

cf9073a — Peter John 2026-11-01T22:49:06+05:30

perf: Map is an insertion-ordered open-addressing hash table (dense entries + probe index), grows at 75%

Files changed (4) hide show

plum-std/Http.plum +6 -15
plum-std/Json.plum +2 -9
plum-std/Map.plum +265 -85
plum-std/Set.plum +3 -9

plum-std/Http.plum CHANGED Viewed

@@ -48,21 +48,12 @@ extern fun rawHttpRequest(method: Str, url: Str, headers: Str, body: Str) -> Str
 # expects for its own `headers` argument.
 fun encodeHeaders(headers: Map[Str, Str]) -> Str =
   buf := Buffer()
-  i := 0
-  while i < headers.buckets.length()
-    bucket := headers.buckets.get(i)
-    j := 0
-    while j < bucket.size
+  for k, v := range headers
-      pair := bucket.data.get(j)
-      k := pair.key
-      v := pair.val
-      if buf.length() > 0
+    if buf.length() > 0
-        buf.write("\n")
+      buf.write("\n")
-      buf.write(k)
+    buf.write(k)
-      buf.write(": ")
+    buf.write(": ")
-      buf.write(v)
+    buf.write(v)
-      j = j + 1
-    i = i + 1
   return buf.toStr()
 # The reverse of `encodeHeaders`, for the response headers `rawHttpRequest`

plum-std/Json.plum CHANGED Viewed

@@ -340,15 +340,8 @@ record JsonParser(src: Str, pos: Int, text: Str) =
 # reference (as `appendJsonPair` does to `buf`) does.
 fun jsonMapToStr(pairs: Map[Str, Json]) -> Str =
   buf := Buffer()
-  i := 0
-  while i < pairs.buckets.length()
-    bucket := pairs.buckets.get(i)
-    j := 0
-    while j < bucket.size
+  for k, v := range pairs
-      pair := bucket.data.get(j)
-      appendJsonPair(buf, pair.key, pair.val)
+    appendJsonPair(buf, k, v)
-      j = j + 1
-    i = i + 1
   return buf.toStr()
 fun appendJsonPair(buf: Buffer, k: Str, v: Json) -> Unit =

plum-std/Map.plum CHANGED Viewed

@@ -4,87 +4,153 @@ import std/Array
 import std/Int
 import std/Float
 import std/Str
+import std/Buffer
-# A Pair is a grouping of a key with a value.
+# A Pair is a grouping of a key with a value. `k => v` sugar builds Pairs for
-#
-# `toStr` exists because `List[T]` calls `toStr` on its elements (duck-typed)
+# `Map(...)`'s variadic init; a Map itself stores no Pairs.
-# and `Map` stores `List[Pair[K, V]]` buckets.
 record Pair[K, V](key: K, val: V) =
   fun toStr(self) -> Str =
     return "{self.key.toStr()}: {self.val.toStr()}"
-# A Map is a hash table: `BUCKET_COUNT` buckets, each an association-list
+# A Map is an open-addressing hash table with an insertion-ordered dense entry
+# store (the layout of Python's dict):
+#
+#   index   : Array[Int]  power-of-two sized probe table (capacity, starts at 16).
+#                         0 = empty, 1 = tombstone (deleted), e + 2 = entry e.
-# chain (`List[Pair[K, V]]`) of every key hashing into it — O(1) average
+#   hashes  : Array[Int]  per entry: the mixed hash, compared before `==` so
+#                         most mismatches never call `==`, and reused on rehash.
+#   keys    : Array[K]    per entry (parallel arrays; `Array[V]` of a struct V is
+#   vals    : Array[V]    stored field by field, so inserting allocates nothing).
+#   alive   : Array[Bool] per entry: false once deleted.
+#   used    : Int         entries appended so far, dead ones included.
+#   size    : Int         live entries.
+#
-# `get`/`set`/`remove` (versus the single, whole-map linear scan a plain
+# Entries are appended in insertion order; `index` is probed linearly. A delete
+# writes a tombstone into `index` and clears `alive`. The entry arrays hold
+# capacity * 3/4 slots, so `used == capacity * 3/4` is the 75% load limit counting
+# tombstones (every dead entry owns at most one tombstone): at that point the
+# table is rebuilt, doubling the capacity if at least half the slots are live,
+# or just compacting dead entries away otherwise. A tombstone met while
+# inserting a new key is reused.
-# association list costs), degrading to O(n) only if many keys collide into
+# Iteration order is insertion order (a re-`set` of an existing key keeps its
-# the same bucket.
+# original position; a removed-then-re-added key goes to the end).
-# `K` must have a `hash() -> Int` method (duck-typed, checked per instantiation).
+# `K` must have a `hash() -> Int` method (duck-typed) and `==`.
-record Map[K, V](buckets: Array[List[Pair[K, V]]], size: Int) =
+record Map[K, V](index: Array[Int], hashes: Array[Int], keys: Array[K], vals: Array[V], alive: Array[Bool], used: Int, size: Int) =
-  # Number of buckets every `Map` allocates at construction — fixed for the
-  # map's whole lifetime, no rehashing/resizing as it grows. A real hash table
-  # would grow this as `size` outpaces it (keeping average bucket length, and
-  # so average `get`/`set` cost, roughly constant); that's future work; for now
-  # a big-enough fixed count keeps small-to-medium maps fast in practice.
-  BUCKET_COUNT = 16
   # `Map[Str, Int]()` builds an empty map; `Map(Pair("a", 1), ...)` infers
   # `K`/`V` from its entries (a later duplicate key wins, as in `set`).
-  # Builds `BUCKET_COUNT` empty bucket lists up front via `Array`'s `push`-to-grow.
   fun init(entries: ...Pair[K, V]) -> Map[K, V] =
-    b := Array[List[Pair[K, V]]]()
+    m := Map(index: Array[Int](), hashes: Array[Int](), keys: Array[K](), vals: Array[V](), alive: Array[Bool](), used: 0, size: 0)
-    i := 0
-    while i < BUCKET_COUNT
-      b = b.push(List[Pair[K, V]]())
-      i = i + 1
-    m := Map(buckets: b, size: 0)
+    m.allocate(16)
     for e := range entries
       m.set(e.key, e.val)
     return m
+  # Installs empty storage for `cap` index slots (a power of two).
+  fun allocate(self, cap: Int) -> Unit =
+    n := cap - cap / 4
+    self.index = Array[Int]().resize(cap)
+    self.hashes = Array[Int]().resize(n)
+    self.keys = Array[K]().resize(n)
+    self.vals = Array[V]().resize(n)
+    self.alive = Array[Bool]().resize(n)
+    self.used = 0
+    self.size = 0
-  # `k`'s bucket index — `hash`'s sign is unconstrained (a plain `%` on a
+  # `k`'s hash, avalanched so identity hashes (`Int`) and sequential keys
-  # negative `Int` stays negative in Plum, matching wasm's signed
-  # `i64.rem_s`), so this folds a negative result back into `[0,
+  # spread across the low bits that pick the slot.
-  # BUCKET_COUNT)` rather than indexing `buckets` out of range.
-  fun bucketIndex(self, k: K) -> Int =
+  fun hashOf(self, k: K) -> Int =
-    m := k.hash() % BUCKET_COUNT
+    h := k.hash()
-    return if m < 0 then m + BUCKET_COUNT else m
+    h = {h ^ {h >> 32}} * 0x5851f42d4c957f2d
+    return h ^ {h >> 29}
+  # The `index` slot holding `k` (whose hash is `h`), or -1.
+  fun findSlot(self, k: K, h: Int) -> Int =
+    mask := self.index.length() - 1
+    slot := h & mask
+    while true
+      x := self.index.get(slot)
+      if x == 0
+        return -1
+      if x >= 2
+        e := x - 2
+        if self.hashes.get(e) == h && self.keys.get(e) == k
+          return slot
+      slot = {slot + 1} & mask
+    return -1
   # Gets the value for `k`, or fails with `KeyNotFound` if absent.
   fun get(self, k: K) -> error{KeyNotFound}!V =
-    bucket := self.buckets.get(self.bucketIndex(k))
+    slot := self.findSlot(k, self.hashOf(k))
-    i := 0
-    while i < bucket.size
-      pair := bucket.data.get(i)
-      if pair.key == k
+    if slot < 0
-        return pair.val
-      i = i + 1
-    return error.KeyNotFound
+      return error.KeyNotFound
+    return self.vals.get(self.index.get(slot) - 2)
   # Gets the value for `k`, or null if absent.
   fun getOrNull(self, k: K) -> V? =
     return self.get(k) catch return null
   fun has(self, k: K) -> Bool =
+    return self.findSlot(k, self.hashOf(k)) >= 0
+  # Rebuilds the table when the entry arrays are full: doubles the capacity if
+  # at least half the entries are live, else compacts at the same capacity.
+  fun rebuild(self) -> Unit =
+    cap := self.index.length()
+    oldHashes := self.hashes
+    oldKeys := self.keys
+    oldVals := self.vals
+    oldAlive := self.alive
+    oldUsed := self.used
+    n := cap - cap / 4
+    newCap := cap
+    if self.size * 2 >= n
+      newCap = cap * 2
+    self.allocate(newCap)
+    mask := newCap - 1
+    e := 0
+    while e < oldUsed
+      if oldAlive.get(e)
+        h := oldHashes.get(e)
+        slot := h & mask
+        while self.index.get(slot) != 0
+          slot = {slot + 1} & mask
+        j := self.used
+        self.index.set(slot, j + 2)
+        self.hashes.set(j, h)
+        self.keys.set(j, oldKeys.get(e))
+        self.vals.set(j, oldVals.get(e))
+        self.alive.set(j, true)
-    self.get(k) catch e
+        self.used = j + 1
-      return false
-    return true
+      e = e + 1
+    self.size = self.used
-  # Sets `k`'s value to `v` — replacing an existing entry for `k` in place
+  # Sets `k`'s value to `v`, replacing an existing entry for `k` in place.
-  # (mutating the stored `Pair`'s `val` field) rather than appending a
-  # duplicate, so a repeated `set` on the same key doesn't grow its bucket
-  # unboundedly or leave a stale value reachable by `get`.
   fun set(self, k: K, v: V) -> Unit =
-    bucket := self.buckets.get(self.bucketIndex(k))
-    i := 0
-    while i < bucket.size
+    h := self.hashOf(k)
-      pair := bucket.data.get(i)
+    slot := self.findSlot(k, h)
-      if pair.key == k
+    if slot >= 0
-        pair.val = v
+      self.vals.set(self.index.get(slot) - 2, v)
-        return
+      return
+    if self.used >= self.hashes.length()
+      self.rebuild()
+    mask := self.index.length() - 1
+    slot = h & mask
+    tomb := -1
+    while self.index.get(slot) != 0
+      if tomb < 0 && self.index.get(slot) == 1
+        tomb = slot
+      slot = {slot + 1} & mask
+    if tomb >= 0
+      slot = tomb
+    e := self.used
+    self.index.set(slot, e + 2)
+    self.hashes.set(e, h)
+    self.keys.set(e, k)
+    self.vals.set(e, v)
+    self.alive.set(e, true)
-      i = i + 1
+    self.used = e + 1
-    bucket.push(Pair(key: k, val: v))
     self.size = self.size + 1
   # Sets `k`'s value to `v` only if `k` isn't already present.
@@ -92,16 +158,13 @@ record Map[K, V](buckets: Array[List[Pair[K, V]]], size: Int) =
     if !self.has(k)
       self.set(k, v)
-  # Removes `k`'s entry, if present.
+  # Removes `k`'s entry, if present (leaves a tombstone).
   fun remove(self, k: K) -> Unit =
-    bucket := self.buckets.get(self.bucketIndex(k))
+    slot := self.findSlot(k, self.hashOf(k))
-    i := 0
+    if slot >= 0
-    while i < bucket.size
-      if bucket.data.get(i).key == k
+      self.alive.set(self.index.get(slot) - 2, false)
-        bucket.removeAt(i)
+      self.index.set(slot, 1)
-        self.size = self.size - 1
+      self.size = self.size - 1
-        return
-      i = i + 1
   fun length(self) -> Int =
     return self.size
@@ -110,28 +173,18 @@ record Map[K, V](buckets: Array[List[Pair[K, V]]], size: Int) =
     return self.size == 0
   fun clear(self) -> Unit =
-    i := 0
-    while i < self.buckets.length()
-      self.buckets.get(i).clear()
-      i = i + 1
-    self.size = 0
+    self.allocate(16)
-  # `for k, v := range m` (or `m.entries()`): every key with its value, in bucket
+  # `for k, v := range m` (or `m.entries()`): every key with its value, in
-  # order, then insertion order within a bucket. One loop, so `break` and
+  # insertion order. One loop, so `break` and `continue` in the body act on the
-  # `continue` in the body act on the whole walk; the cursor moves before the
+  # whole walk; the cursor moves before the `yield` for the same reason.
-  # `yield` for the same reason.
   fun* entries(self) *(K, V) =
     i := 0
+    while i < self.used
-    j := 0
+      e := i
-    while i < self.buckets.length()
-      bucket := self.buckets.get(i)
-      if j >= bucket.size
-        i = i + 1
+      i = i + 1
-        j = 0
-        continue
-      pair := bucket.data.get(j)
+      if self.alive.get(e)
-      j = j + 1
-      yield pair.key, pair.val
+        yield self.keys.get(e), self.vals.get(e)
   # `for k := range m.keys()`.
   fun* keys(self) *K =
@@ -143,6 +196,8 @@ record Map[K, V](buckets: Array[List[Pair[K, V]]], size: Int) =
     for k, v := range self
       yield v
+struct MapPoint(x: Float, y: Float)
 test "get/set/has round-trip and set replaces an existing key in place"
   m := Map[Str, Int]()
   assert m.has("a") == false
@@ -333,3 +388,128 @@ test "init_negative_int_keys_and_duplicates"
   assert m.length() == 2
   assert m.get(-5)! == "c"
   assert m.get(-17)! == "b"
+test "100k inserts, every key found, 100k missing keys absent"
+  m := Map[Int, Int]()
+  i := 0
+  while i < 100000
+    m.set(i, i * 2)
+    i = i + 1
+  assert m.length() == 100000
+  i = 0
+  bad := 0
+  while i < 100000
+    if m.get(i)! != i * 2
+      bad = bad + 1
+    i = i + 1
+  assert bad == 0
+  i = 100000
+  found := 0
+  while i < 200000
+    if m.has(i)
+      found = found + 1
+    i = i + 1
+  assert found == 0
+test "delete half, reinsert, tombstones are reused and lookups stay right"
+  m := Map[Int, Int]()
+  i := 0
+  while i < 20000
+    m.set(i, i)
+    i = i + 1
+  i = 0
+  while i < 20000
+    m.remove(i)
+    i = i + 2
+  assert m.length() == 10000
+  i = 0
+  bad := 0
+  while i < 20000
+    if m.has(i) != {i % 2 == 1}
+      bad = bad + 1
+    i = i + 1
+  assert bad == 0
+  i = 0
+  while i < 20000
+    m.set(i, i + 1)
+    i = i + 2
+  assert m.length() == 20000
+  i = 0
+  while i < 20000
+    if m.get(i)! != {if i % 2 == 0 then i + 1 else i}
+      bad = bad + 1
+    i = i + 1
+  assert bad == 0
+test "repeated set/remove of a few keys never grows the table without bound"
+  m := Map[Int, Int]()
+  i := 0
+  while i < 100000
+    m.set(i % 7, i)
+    m.remove(i % 7)
+    i = i + 1
+  assert m.length() == 0
+  m.set(3, 9)
+  assert m.get(3)! == 9
+  assert m.index.length() == 16
+test "growth past several doublings"
+  m := Map[Int, Int]()
+  assert m.index.length() == 16
+  i := 0
+  while i < 1000
+    m.set(i, i)
+    i = i + 1
+  assert m.index.length() == 2048
+  assert m.length() == 1000
+test "Map[Str, Int] with Buffer-built keys"
+  m := Map[Str, Int]()
+  i := 0
+  while i < 2000
+    b := Buffer()
+    b.write("k")
+    b.write(i.toStr())
+    m.set(b.toStr(), i)
+    i = i + 1
+  assert m.length() == 2000
+  assert m.get("k1999")! == 1999
+  assert m.has("k2000") == false
+test "Map[Int, MapPoint] struct values"
+  m := Map[Int, MapPoint]()
+  i := 0
+  while i < 500
+    m.set(i, MapPoint(x: Float(i), y: Float(i) * 2.0))
+    i = i + 1
+  v := m.get(499)!
+  assert v.x == 499.0
+  assert v.y == 998.0
+  m.set(499, MapPoint(x: 1.0, y: 2.0))
+  assert m.get(499)!.y == 2.0
+  assert m.length() == 500
+test "iteration is insertion order, skipping removed entries"
+  m := Map[Int, Int]()
+  m.set(30, 1)
+  m.set(10, 2)
+  m.set(20, 3)
+  m.set(10, 4)
+  m.remove(30)
+  m.set(30, 5)
+  order := ""
+  for k, v := range m
+    order = "{order}{k}={v} "
+  assert order == "10=4 20=3 30=5 "
+test "clear then reuse"
+  m := Map[Int, Int]()
+  i := 0
+  while i < 100
+    m.set(i, i)
+    i = i + 1
+  m.clear()
+  assert m.length() == 0
+  assert m.has(5) == false
+  m.set(5, 1)
+  assert m.get(5)! == 1

plum-std/Set.plum CHANGED Viewed

@@ -31,17 +31,11 @@ record Set[T](map: Map[T, Bool]) =
   fun clear(self) -> Unit =
     self.map.clear()
-  # Every member, in no particular order.
+  # Every member, in insertion order.
   fun toList(self) -> List[T] =
     result := List[T]()
-    i := 0
-    while i < self.map.buckets.length()
-      bucket := self.map.buckets.get(i)
+    for k := range self.map.keys()
-      j := 0
-      while j < bucket.size
-        result.push(bucket.data.get(j).key)
+      result.push(k)
-        j = j + 1
-      i = i + 1
     return result
 test "set_dedup: adding duplicates keeps one copy"