The container module

Every declaration in sysl.container, with its signature: the generated API page. This page is the argument — what the module is for, and how its pieces fit; that one is the list.

One module, sysl.container, holding five types. A program names the ones it wants and gets nothing else — what a program does not import, it does not link.

None of them is a type the compiler knows. Each is ordinary sysl over a []T or a Buf[T], in files a program could have written — which is the same thing worth saying about Buf itself, and it stays true as the containers get more interesting.

There is a sixth thing in this namespace and it is a module rather than a type: sysl.container.ring, holding Ring[T] — the queue of a fixed capacity, laid over storage the caller supplies. It sits below this module rather than inside it because it declares @no_alloc and a capability is a property of the whole module, which the five types here could not claim: every one of them grows. So a program that has given the allocator up imports that module and not this one.

One flat table, and why that is the whole design

Map and Set are open-addressed: entries live in the table, and a key is found by probing forward from where it hashes until it turns up or an empty slot proves it is not there.

The alternative is chaining — a bucket per hash, holding its entries through references. In a reference-counted language that costs more than it looks: a heap cell per entry, an allocation on every insert, a release on every removal, and a walk that touches every count when the table doubles. A flat table allocates once.

What makes it expressible is a variant that carries no payload. A generic container cannot make [K; n] storage, because a bound may promise no value to repeat — but Slot.Empty needs nothing of K or V, so [Slot.Empty; n] fills a table of any key and any value:

enum Slot[K, V]
    Empty
    Dead
    Live(hash: u64, key: K, value: V)

Three variants rather than two, and the third is what deletion needs. A removed key becomes Dead rather than Empty, because emptying it would end every probe that had run past it on the way to something else. Tombstones then count against the table’s load exactly as live entries do, and rehash sizes from the live count — so a map inserted into and removed from in equal measure settles at the size its contents deserve instead of doubling forever.

The u64 beside each key is the hash it mixed down to. It earns its eight bytes twice: a probe rejects a wrong slot on an integer comparison without touching either key, and a rehash re-places every entry without hashing anything.

A map of eight entries or fewer is not a table yet: it is a list. Its entries sit packed at the front of the same eight slots, in the order they were put, and a key is found by comparing it with each in turn — nothing is hashed. Hashing a key and then comparing it anyway costs more than comparing it with a handful of others: building a small map and looking keys up in it is faster as a list below eight entries for integer, struct and string keys alike, and no slower at eight — most so for long strings, whose hash reads every byte while an unequal comparison mostly stops at the length, where a map of eight is twice as fast as a list. The ninth distinct key builds the table, once, sized so that it does not grow again until it is three times as full. A table never turns back into a list however much is removed from it; clear starts over with a list. Nothing about this shows in what a map answers — capacity() says which form it is in (eight for a list), and a walk of a list happens to follow the order the keys were put, which is no more promised than the table’s order is.

The map

K: Hash + Eq is the whole requirement, and both are core traits — so every built-in key type already qualifies, and a program’s own type joins by writing the two impl blocks it would write anyway.

import sysl.container.{Map, map}

main()
    var ages: Map[string, int] = map()

    ages.put("ada", 36)
    ages.put("alan", 41)
    ages.put("ada", 37)

    print(ages.len())
    print(ages.get("ada"))
    print(ages.get("grace"))
    print(ages.get_or("grace", 0))
    print(ages.remove("alan"), ages.remove("alan"))

2
Some(37)
None
0
true false

get answers an Option because a missing key is an ordinary question rather than a mistake, and remove answers whether the key was there — so the second call reports false without failing.

The annotation on var ages is required. map() is a nullary generic, so its type arguments come from what receives it, and there is nothing else in that line to take them from.

A Map is a reference to one map, like Scala’s mutable.HashMap. Assigning it, passing it to a function, capturing it in a closure or reading it out of another container gives a second name for the same map, so what is put through one name is there through every other:

import sysl.container.{Map, map}

note(m: Map[string, int]) = m.put("seen", 1)

val counts: Map[string, int] = map()
val alias = counts

alias.put("a", 1)
note(counts)

print(counts.len(), counts.get("a"), counts.get("seen"))

2 Some(1) Some(1)

Every member that changes a map — put, remove, clear — takes it by value, so a val map is put into like any other: val says the name always refers to the same map. copy() is the way to a second map, holding the same entries and sized to them; a Deque has one too, and the same rule holds for Deque, Set and Heap.

So a map has no zero value: a declaration says where its map comes from, = map(), and a struct holding one is built with one.

A container in storage the program zeroed itself is empty until it is assigned. A calloced block or a collector’s arena holds a handle naming nothing, and every container reads that as empty — len() 0, get and first None, has false, for visiting nothing — while assigning map(), deque() or set() into it gives it storage. Growing one in place (put, push_back, push_front, add) panics, saying to assign it first. To empty one in a finalizer without allocating, call release(): it gives back this name’s share and leaves the handle naming nothing, where assigning a fresh map() would make a table nobody will free.

import sysl.container.{Map, map, Deque, deque}

extern "calloc" c_calloc(n: usize, size: usize) -> *u8

struct Scope
    names: Map[string, int]
    pending: Deque[int]

val s: *Scope = ptr_cast(c_calloc(1, sizeof(Scope)))

print(s.names.len(), s.names.get("x"), s.pending.pop_front())

s.names = map()
s.names.put("x", 1)
print(s.names.get("x"))

s.names.release()
print(s.names.len())

0 None None
Some(1)
0

An empty map holds no table at all. map() allocates only the small cell every name for the map shares — three words, whatever the key and value — and the first put makes its eight slots. That matters far more than it looks, because no caller can see that they are paying: a map built inside a loop, held in a struct that is usually empty, or made on a branch that turns out not to be taken would otherwise be a table of slots and the free behind it, every time. A profile of an interpreter that gave every block its own scope — two maps per scope, one entry each — put 27% of its running time in constructing and destroying maps nothing was ever read out of.

capacity() is how that is visible from outside, and it is the one number here that might surprise:

import sysl.container.{Map, map}

var m: Map[string, int] = map()

print(m.capacity(), m.len())

m.put("k", 1)

print(m.capacity(), m.get("k"))

m.clear()

print(m.capacity())

0 0
8 Some(1)
0

clear lets the table go entirely for the same reason, so a map used as scratch across a loop keeps nothing between passes and one that is cleared and never used again costs no table at all.

map_with_capacity(n) still allocates up front, which is the point of writing it: a caller who names a size is saying entries are coming. Eight or fewer get the list’s eight slots; past that it starts as a table sized for n entries, and the table is grown at three quarters full, so the storage is twice n rounded up to a power of two.

A Set is a Map and inherits all of this, including the empty table and being a reference.

A for walks a map directly, a pair per entry, in no particular order. Every container here except the heap implements Walk, so for x in c walks the cursor c.walk() answers — asked once, before the first turn:

for (name, age) in ages
    print(name, age)

Nothing hands out a reference into the table, and that is deliberate rather than an omission: a &V pointing into storage that a rehash replaces would be a pointer at freed memory the moment the map grew. The cost is that a value is updated by putting it back. The matching rule is that a map must not be modified while a cursor over it is live — doing so is memory-safe and nothing more, since what the cursor yields in that case is unspecified.

The set

The same table with nothing in the value column. add answers whether the key was new, which is what makes a set the “have I seen this before” test rather than something you ask twice:

import sysl.container.{Set, set, set_of, intersection}

main()
    var seen: Set[int] = set()

    for n in [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
        if seen.add(n)
            print("first time:", n)

    print("distinct:", seen.len())
    print("shared:", intersection(seen, set_of([1, 2, 7])).len())

first time: 3
first time: 1
first time: 4
first time: 5
first time: 9
first time: 2
first time: 6
distinct: 7
shared: 2

set_of collapses a slice’s duplicates in one line. Beside it are union, intersection, difference and is_subset — intersection walks the smaller side, since the answer cannot be bigger than that and walking the larger would ask more questions to reach it.

The queue at both ends

This is the module with a performance argument rather than an expressiveness one. A queue written over a Buf takes from the front with remove(0), which shifts every remaining element down one — so a loop that pushes n things and pops them all is quadratic while reading as though it were linear.

A Deque holds its elements in a ring: a head index says where the first one is, and both ends wrap rather than move. Taking from the front advances the head and touches nothing else.

import sysl.container.{Deque, deque}

main()
    var work: Deque[int] = deque()

    work.push_back(1)
    work.push_back(2)
    work.push_front(0)

    loop
        work.pop_front() match
            None -> break
            Some(job) ->
                print("doing", job)

                if job < 2 then work.push_back(job + 10)

doing 0
doing 1
doing 2
doing 10
doing 11

That is the shape of every work list and every breadth-first walk. d[i] counts from the front whatever the ring is doing underneath, and first/last answer an Option at either end.

The priority queue

A binary heap over a Buf, and a min-heap: the three things a priority queue is actually reached for — a scheduler ordered by deadline, a shortest path ordered by distance, an event loop ordered by time — all want the smallest first.

A tuple is ordered when its parts are, so a (priority, payload) queue needs no wrapper type:

import sysl.container.{Heap, heap_of}

main()
    var due = heap_of([(30, "sweep"), (10, "tick"), (20, "poll")])

    loop
        due.pop() match
            None -> break
            Some(job) -> print(job.0, job.1)

10 tick
20 poll
30 sweep

heap_of is linear where pushing the same elements one at a time is O(n log n): it lays them down unordered and establishes the heap property afterwards, sifting from the last parent to the root.

A heap cannot be walked, on purpose. Its storage order is not its priority order — only the first element is guaranteed to be anything in particular — so a cursor would hand back elements in an order that looks meaningful and is not. Draining with pop is the only reading that answers truthfully, which is why Heap implements no Walk and for x in h is refused.

The immutable list

Every operation answers a new list and the old one is still there. Putting an element on the front makes one cell holding it and a reference to the list that was there, so two lists differing by one element share every cell but one:

import sysl.container.{List, list_of}

main()
    val outer = list_of(["x"])
    val f = outer.prepend("y")
    val g = outer.prepend("z")

    print(outer.len(), f.len(), g.len())

    for name in f
        print("f:", name)

    for name in g
        print("g:", name)

1 2 2
f: y
f: x
g: z
g: x

This is the container that earns its place from reference counting specifically. prepend is one allocation whatever the length, and the count is what makes the sharing safe without either list knowing the other exists — a cell goes when the last list holding it does. A language without it would need a collector, or an ownership rule saying which of f and g owns outer, and there is no good answer to that.

It also cannot form a cycle, which is what makes counting sufficient here rather than merely convenient: a cell’s tail always existed before the cell did.

uncons is the member to write loops with — it answers the head and the rest together, so a walk asks one question instead of two:

at.uncons() match
    None -> break
    Some(pair) ->
        val head, rest = pair

len is constant time. Immutability is what makes that free: a cell’s tail never changes, so a length worked out when the list was built stays true forever.

Do not reach for this to hold a sequence and walk it. There is no index, getting to the ith element walks i cells, and those cells are wherever the allocator put them. Buf is what a sequence wants; this is what a shared history wants — a scope chain, an undo stack, a search path that is its parent’s path plus a step. All three share almost everything and would copy almost everything in a Buf.