34 Containers and sorting — sortlib, sortgen, hashmap, vecgen, spsc

34 Containers and sorting — `sortlib`, `sortgen`, `hashmap`, `vecgen`, `spsc`

What to know first

chapter 22, Generics · comparison is brought by the type, not a value

chapter 20, Allocators and fixed memory · allocators are handed over with using

chapter 32, A map of the standard library · buffers belong to the caller

Looking back

In chapter 22, C’s qsort takes a comparison function as a value. What did it say Lowent’s sortgen takes it by?

A. The type brings the comparison. If the type being sorted satisfies the ordered trait and provides less, sort_by is monomorphised for that type and the comparison is built in as a direct call. This chapter tours that sort together with the standard library’s containers.

The need for this chapter, and its context

Sorting, searching, hash maps and growing arrays go into almost every program. In other languages such containers usually allocate on the heap secretly and grow quietly when full. Lowent’s containers come in two kinds: fixed containers whose backing slice the caller hands over (hashmap, sortlib), and generic containers that receive an allocator with using and grow themselves (vecgen, mapgen). Either way, where memory comes from is visible in the head.

By the end of this chapter

You will learn to sort and search u64 slices with sortlib.sort and searchlib.bsearch, and to sort structs by a type-defined criterion with sortgen.sort_by. You will see how hashmap works over the caller’s slice (empty slots and tombstones). You will watch vecgen receive an allocator and grow, with its effects depending on the allocator’s type. You will also see spsc, which passes values between flows without locks, and where the other containers fit.

The questions this chapter answers

What happens if less a a is true?

34.1 Sorting and finding `u64`#

examples/ch34/sorted.low

module sorted .
rem run: main

use sortlib .
use searchlib .

proc main input al cap allocator . output u8 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 40 .
  guard is_some g . else return 255 .
  var xs mut slice u64 be view_array u64 (some_value g) .
  set (index xs 0) 42 .
  set (index xs 1) 7 .
  set (index xs 2) 19 .
  set (index xs 3) 3 .
  set (index xs 4) 25 .
  sortlib.sort xs .
  let at option u64 be searchlib.bsearch xs 19 .
  guard is_some at . else return 254 .
  let missing option u64 be searchlib.bsearch xs 20 .
  guard not (is_some missing) . else return 253 .
  return narrow u8 (add (mul (index xs 0) 10) (some_value at)) .
end

Output

$ lowentc --run main sorted.low
main() = 32

alloc_bytes al capacity 40 gets 40 bytes, and view_array u64 views them as a slice of five u64 elements. Allocation happens only here.
sortlib.sort xs sorts in place in ascending order. It is effects none.
searchlib.bsearch xs 19 gives the position of 19 in the sorted slice as an option, or none if absent. lower_bound gives the insertion position.

The smallest value 3 and 19′s position 2 give 32. bsearch trusts that its input is sorted. Given an unsorted slice it gives a wrong answer. That trust is a precondition written in the module document.

34.2 The type brings the criterion#

examples/ch34/rows.low

module rows .
rem run: main

use sortgen .

struct score do
  satisfies sortgen.ordered .
  points u64 .
  id u64 .
end

fn score.less input a score . input b score . output bool .
do
  return gt (field a points) (field b points) .
end

proc main input al cap allocator . output u8 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 48 .
  guard is_some g . else return 255 .
  var rs mut slice score be view_array score (some_value g) .
  set (index rs 0) (make score do points 70 . id 1 . end) .
  set (index rs 1) (make score do points 95 . id 2 . end) .
  set (index rs 2) (make score do points 80 . id 3 . end) .
  sortgen.sort_by score rs .
  return narrow u8 (add (mul (field (index rs 0) id) 100) (add (mul (field (index rs 1) id) 10) (field (index rs 2) id))) .
end

Output

$ lowentc --run main rows.low
main() = 231

score declares that it knows order with satisfies sortgen.ordered ., and score.less gives the criterion “higher score first”. sortgen.sort_by score rs sorts by that criterion. The ids for scores 95, 80 and 70 are 2, 3 and 1 in order.

To sort descending or by several keys, write less that way. Instead of adding a mode argument, the type brings the meaning. sort_by is insertion sort, so it is stable (the order of equal scores does not change) and fast on nearly sorted input. For large arrays there is sort_fast (a generic quicksort). Scalars like u64 cannot satisfy traits, so wrap them in a one-field struct. The layout stays 8 bytes.

Q. What happens if less a a is true?

A. Sorting may not stop or may give a wrong order. less must be a strict weak ordering — in particular nothing may come before itself. The mistake of writing lt where le belongs, or the reverse, happens here. A trait checks that an op exists, not that it keeps mathematical properties. Those properties are a contract written in the module document.

34.3 A hash map over the caller’s slice#

examples/ch34/table.low

module table .
rem run: main

use hashmap .

proc main input al cap allocator . output u8 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 128 .
  guard is_some g . else return 255 .
  var slots mut slice u64 be view_array u64 (some_value g) .
  let a bool be hashmap.put slots 7 700 .
  let b bool be hashmap.put slots 9 900 .
  let c bool be hashmap.put slots 7 777 .
  let v option u64 be hashmap.lookup slots 7 .
  guard is_some v . else return 254 .
  let gone bool be hashmap.del slots 9 .
  let w option u64 be hashmap.lookup slots 9 .
  guard not (is_some w) . else return 253 .
  return narrow u8 (add (mul (div (some_value v) 100) 10) (hashmap.size slots)) .
end

Output

$ lowentc --run main table.low
main() = 78

hashmap is a u64 → u64 open-addressing hash map. Its backing is a mut slice u64 held by the caller, laid out as [key0+1, value0, key1+1, value1, …]. size is the slot count (len / 2). Initially everything must be 0 (empty), and alloc_bytes gives zero-filled bytes, so they are used as is.

put slots 7 700 inserts, and put again with the same key changes the value. When full it is false.
lookup gives an option.
del does not return a slot to empty; it covers it with a tombstone. Returning it to empty would break the probe chain continuing behind it, and later keys could not be found.

The price of this design is written in the document too. The two largest keys cannot be used, because they mark empty (0) and tombstone, and it does not grow automatically. Byte-string keys are handled by strmap, and a growing generic hash map by mapgen.

34.4 A growing generic vector#

examples/ch34/growing.low

module growing .
rem run: main

use allocs .
use vecgen .

proc main input h cap heap . output u8 . effects heap state .
do
  var hb allocs.heap_bytes be spawn actor allocs.heap_bytes .
  let vo option (vecgen.vec u32 allocs.heap_bytes) using hb be vecgen.open u32 4 .
  guard is_some vo . else return 255 .
  var v vecgen.vec u32 allocs.heap_bytes be some_value vo .
  var i u32 be 0 .
  while lt i 100 . do
    let pushed bool be vecgen.append u32 allocs.heap_bytes v (mul i 2) .
    guard pushed . else return 254 .
    set i (add i 1) .
  end
  let x option u32 be vecgen.at u32 allocs.heap_bytes v 50 .
  guard is_some x . else return 253 .
  return narrow u8 (some_value x) .
end

Output

$ lowentc --run main growing.low
main() = 100

allocs.heap_bytes is spawned and used as an allocator. Only main, holding cap heap, can spawn it (chapter 20).
vecgen.open u32 4 opens a vector with element type u32 and initial capacity 4. The allocator is handed over with the binding’s using hb.
vecgen.append … v x asks the allocator for more and grows when out of room. On failure it is false. The vector already holds its own allocator, so append does not take using. Writing it is rejected with E-ALLOC-USING-UNUSED.
vecgen.at … v 50 gives element 50 as an option. 50 × 2 = 100.

The effect of vecgen.append is state via a. Here a is heap_bytes, so this instance’s effect is heap state, and heap shows in main’s head too. Opening the same code with a bump over borrowed bytes shows only state. The allocator’s type decides whether the container runs on a machine without an operating system.

A common misconception. A growing vector is hidden allocation after all

Allocation happens but is not hidden. append’s effects line carries the allocator’s effect as is, and heap or alloc shows in the calling op’s head. When the allocator runs short, append gives false — running out of memory is a value. Hidden allocation is allocation invisible in the head that stops the program when it fails.

34.5 A ring buffer passing values between flows#

spsc is a lock-free single-producer, single-consumer ring buffer. One flow puts and another takes. The caller hands over the control and backing slots, and the ops that put and take receive cap atomic and move the cursors with atomic operations (chapter 27). It is used where interrupt handlers and ordinary code exchange values (chapter 30).

Lock-free data structures are notorious for being wrong only in rare orderings. spsc’s correctness was confirmed by borrowing the proof of an algorithm already proven in a weak-memory model. Multi-producer multi-consumer queues and seqlocks have no proof to borrow, so they were left out (chapter 47).

34.6 Other containers#

Module	In one line
`strmap`	Byte string → `u64` hash map. Key bytes are kept in the caller’s slice too
`mapgen`	Generic hash map `table k v`. Rehashes itself
`vecs` · `growvec`	Growing byte vectors. `growvec` is a short name for `vecgen.vec u8`
`nodelist`	Fixed-size intrusive list
`soa`	An experiment laying out an array of structs as per-field arrays

Table 34.1 — Other container modules

34.7 Common mistakes#

Counter-example. Binary-searching a slice that was never sorted

examples/ch34/mistake_unsorted.low

module mistake_unsorted .
rem run: find42 0

use searchlib .

proc find42 input al cap allocator . output u64 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 40 .
  guard is_some g . else return 255 .
  var xs mut slice u64 be view_array u64 (some_value g) .
  set (index xs 0) 42 .
  set (index xs 1) 7 .
  set (index xs 2) 19 .
  set (index xs 3) 3 .
  set (index xs 4) 25 .
  rem ✘ binary search without sorting --- 42 is there, yet it is not found
  let at option u64 be searchlib.bsearch xs 42 .
  guard is_some at . else return 99 .
  return some_value at .
end

Output

$ lowentc --run find42 mistake_unsorted.low 0
find42(0) = 99

42 sits in slot 0, yet bsearch returns 99 (not found). Binary search compares with the middle value and discards half, and if the slice is not sorted the answer may be in the discarded half. It neither stops nor warns, which makes it the hardest kind of bug to find. With luck it even succeeds (in the same slice it finds 19). A binary search must always be preceded by sortlib.sort, and where code that keeps the order is scattered, use lower_bound to find the insertion point and keep the slice sorted.

Counter-example. Writing less non-strictly, like ge

examples/ch34/mistake_lessge.low

module mistake_lessge .
rem run: order_strict 0
rem run: order_loose 0

use sortgen .

struct strict_score do
  satisfies sortgen.ordered .
  points u64 .
  id u64 .
end

struct loose_score do
  satisfies sortgen.ordered .
  points u64 .
  id u64 .
end

fn strict_score.less input a strict_score . input b strict_score . output bool .
do
  return gt (field a points) (field b points) .
end

rem ✘ "comes first" written with `ge` --- equal scores each come before the other
fn loose_score.less input a loose_score . input b loose_score . output bool .
do
  return ge (field a points) (field b points) .
end

proc order_strict input al cap allocator . output u64 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 48 .
  guard is_some g . else return 255 .
  var rs mut slice strict_score be view_array strict_score (some_value g) .
  set (index rs 0) (make strict_score do points 70 . id 1 . end) .
  set (index rs 1) (make strict_score do points 70 . id 2 . end) .
  set (index rs 2) (make strict_score do points 70 . id 3 . end) .
  sortgen.sort_by strict_score rs .
  return add (mul (field (index rs 0) id) 100) (add (mul (field (index rs 1) id) 10) (field (index rs 2) id)) .
end

proc order_loose input al cap allocator . output u64 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 48 .
  guard is_some g . else return 255 .
  var rs mut slice loose_score be view_array loose_score (some_value g) .
  set (index rs 0) (make loose_score do points 70 . id 1 . end) .
  set (index rs 1) (make loose_score do points 70 . id 2 . end) .
  set (index rs 2) (make loose_score do points 70 . id 3 . end) .
  sortgen.sort_by loose_score rs .
  return add (mul (field (index rs 0) id) 100) (add (mul (field (index rs 1) id) 10) (field (index rs 2) id)) .
end

Output

$ lowentc --run order_strict mistake_lessge.low 0
order_strict(0) = 123
$ lowentc --run order_loose mistake_lessge.low 0
order_loose(0) = 321

All three scores are 70. strict_score, written with gt, keeps the insertion order 1, 2, 3 and returns 123. loose_score, written with ge, treats equal scores as “coming first” too, swaps them, and returns 321. The stable sort’s promise that “equal items keep their order” is broken. With another sorting algorithm it might even never finish or produce a wrong order. The trait checks only that less exists, so the property “nothing comes before itself” is for the writer to keep.

Counter-example. Writing using again for a container that already carries its allocator

examples/ch34/mistake_usingappend.low

module mistake_usingappend .
rem expect: E-ALLOC-USING-UNUSED

use allocs .
use vecgen .

proc main input h cap heap . output u8 . effects heap state .
do
  var hb allocs.heap_bytes be spawn actor allocs.heap_bytes .
  let vo option (vecgen.vec u32 allocs.heap_bytes) using hb be vecgen.open u32 4 .
  guard is_some vo . else return 255 .
  var v vecgen.vec u32 allocs.heap_bytes be some_value vo .
  var i u32 be 0 .
  while lt i 100 . do
    rem ✘ `using` is written again although the vector already carries its allocator
    let pushed bool using hb be vecgen.append u32 allocs.heap_bytes v (mul i 2) .
    guard pushed . else return 254 .
    set i (add i 1) .
  end
  let x option u32 be vecgen.at u32 allocs.heap_bytes v 50 .
  guard is_some x . else return 253 .
  return narrow u8 (some_value x) .
end

Output

$ lowentc --check mistake_usingappend.low
16:27 E-ALLOC-USING-UNUSED: this binding says which allocator to use, but the call it initialises does not draw from one (no `using` clause on that op). An object that already carries its allocator — like `vecgen.append` on a vector — does not take the caller's choice (RFC-0112 D8(5))

vecgen.open takes the allocator and stores it inside the vector. The later append uses the allocator the vector carries, so the binding’s using hb means nothing. A meaningless mark becomes false information — “this call carves from hb” — so it is rejected with E-ALLOC-USING-UNUSED. Write using only where the allocator is first received (open).

A common misconception. Any u64 can be a key in hashmap

examples/ch34/hashmap_topkeys.low

module hashmap_topkeys .
rem run: main

use hashmap .

proc main input al cap allocator . output u8 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 160 .
  guard is_some g . else return 255 .
  var slots mut slice u64 be view_array u64 (some_value g) .
  rem the two largest keys are used to mark empty slots and tombstones, so they cannot be stored
  let a bool be hashmap.put slots 18446744073709551615 40 .
  let b bool be hashmap.put slots 18446744073709551614 50 .
  let c bool be hashmap.put slots 18446744073709551613 60 .
  var r u8 be 0 .
  if a . do set r (add r 1) . end
  if b . do set r (add r 2) . end
  if c . do set r (add r 4) . end
  return r .
end

Output

$ lowentc --run main hashmap_topkeys.low
main() = 4

The result 4 means only the third put succeeded. The two largest keys (18446744073709551615·18446744073709551614) are used to mark empty slots and tombstones, so they cannot be stored and put returns false. This cost is stated at the top of the module’s documentation. If keys may use the full range, put them in a struct and use mapgen.

34.8 This chapter’s syntax at a glance#

Shape	Meaning	Why
`sortlib.sort xs` · `searchlib.bsearch xs k`	sort `u64` in place · search sorted input (`option`)	no allocation — search trusts the order
`struct score do satisfies sortgen.ordered . … end` + `fn score.less`	the type brings the sort order	a type instead of a mode argument — `less` must be strict
`sortgen.sort_by score rs` · `sort_fast`	stable insertion sort · quicksort for large arrays	the choice is in the name
`hashmap.put slots k v` · `lookup` · `del`	a `u64 → u64` map on the caller’s slice	`false` when full — deletion leaves a tombstone
`let vo … using hb be vecgen.open u32 4 .`	open a growing vector with an allocator	`using` only where it is first received
`vecgen.append u32 allocs.heap_bytes v x`	push while growing — `false` on failure	effects follow the allocator type (`state via a`)
`spsc`	lock-free single-producer single-consumer ring buffer	atomic operations — a borrowed proof

Table 34.2 — Shapes of containers and sorting — shape · meaning · why it looks this way

Recap

sortlib and searchlib sort and search u64 slices in place, and with sortgen a type satisfying ordered brings the criterion. hashmap and strmap are fixed containers over the caller’s slice that delete with tombstones. vecgen and mapgen receive an allocator with using and grow, their effects following the allocator type. spsc passes values between flows with atomic operations, and its correctness was confirmed with a borrowed proof.

← PrevContentsNext →