jonnifyfsharp

Dive C4.01.3

Complexity on .NET

Read the cost from the shape: how many cells must an operation touch? That one question decides what a queue keeps its backlog in.

The cost of a list operation is the number of cells it touches. Work at the head is O(1) — List.head and :: read or write one cell. Work at the far end is O(n) — List.length, @ (append), List.last, and List.item all walk the chain. There is no random access. That asymmetry has a consequence beyond style: a queue that must take its oldest id on every claim and test membership on every admission cannot use a list, where both are O(n). It uses an immutable sorted Set, a balanced tree where the minimum, contains, and add are each O(log n). Every cost below was confirmed with dotnet fsi.

Compare the structures Module hub
C4.01.3 · part 1

The list cost table

Each operation below was run in dotnet fsi; the cost class is read from how far into the chain it reaches. The pattern is simple: the head is free, the far end is a walk.

let xs = [ 1 .. 5 ]
List.head xs       // O(1)  -> 1
List.length xs     // O(n)  -> 5   (walk every cell to count)
xs @ [ 6 ]         // O(n)  -> [1; 2; 3; 4; 5; 6]   (copy the left list)
List.last xs       // O(n)  -> 5
List.item 3 xs      // O(n)  -> 4   (no random access)
Without JavaScript: the F# list cost model
operationcostwhy
x :: xs (prepend)O(1)one new cell, tail shared
List.headO(1)reads the first cell
List.lengthO(n)walks every cell
xs @ ys (append)O(n)copies the left list
List.last, List.itemO(n)reaches the far end

The list is a one-way chain. Cheap at the head, linear at the end — and never random-access. Build at the head; if you need the far end often, you have the wrong structure.

List versus Set: where the oldest id lives

A queue's hot operations are: take the oldest id (the minimum), and test whether an id is already present (dedup). Pick an operation below; the chart shows the cost as the structure grows from 16 to 4096 ids, for a plain list (O(n), the linear bars) against an immutable sorted Set (O(log n), the flat bars). The readout names the cost class and the F# call. The numbers are the cost model, not a benchmark — the point is the shape of growth.

cost vs size · list (O(n)) versus Set (O(log n))

cost number of pending ids (n) list · O(n) Set · O(log n) 16 256 1024 4096
take the oldest · list = O(n) — scan every cell for the minimum · Set = O(log n) — Set.minElement
let pendingSet = Set.ofList [ "JOB07"; "JOB05"; "JOB02" ]
Set.minElement pendingSet         // O(log n) -> "JOB02"
Set.contains "JOB05" pendingSet   // O(log n) -> true
Set.toList pendingSet             // sorted ascending -> ["JOB02"; "JOB05"; "JOB07"]

On a list, the oldest id and a membership test are both O(n). On a sorted Set they are O(log n). For a queue that does both on every job, that is the difference between linear and logarithmic work per operation.

C4.01.3 · part 2

Byte order is mint order — so the Set needs no second index

There is a second reason the Set fits. A branded job id is time-ordered, and its Base62 text sorts exactly as the underlying integer does. So the Set's natural ordering is the order the jobs were minted — the oldest id is the minimum. A queue gets first-in-first-out for free from the sort, with no separate order index to maintain.

// branded ids are time-ordered; Base62 sorts as the integers do
let pending = Set.ofList [ "JOB07"; "JOB05"; "JOB02" ]
Set.minElement pending    // "JOB02" — the oldest, in O(log n)
Set.toList pending        // ["JOB02"; "JOB05"; "JOB07"]  // ascending = mint order
This is the property the Elixir bus calls "no second index", re-derived in F#. The Elixir course's E4.01 reads cost from the cons cell; here the same reasoning chooses a balanced tree for the pending set, because the queue's access pattern is the minimum, not the head.

EchoMQ in F#

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

This cost model is exactly why the F# EchoMQ port keeps pending ids in a Set, not a list. The store's hot path is the claim — take the oldest id — and admission's dedup test. Both are O(log n) on the set. The list appears only in browse, which materializes one for display and is never on the hot path.

EchoMQ in F#

The queue state keeps Pending as a Set<string>, quoted verbatim from echo_fs/EchoMQ/Store.fs:

/// One queue's state.
type QueueState =
    { Rows: Map<string, Job>
      Pending: Set<string>
      // ... Schedule, Active, Dead, Paused, Completed, Failed
    }

claim pops the minimum in O(log n); pendingSize is Set.count; and browse builds a list only to present the backlog — quoted verbatim from the same file:

/// Newest-first browse over the pending ids themselves (no second index).
let browse (n: int) (st: QueueState) : string list =
    st.Pending |> Set.toList |> List.rev |> List.truncate n

/// Pending depth.
let pendingSize (st: QueueState) : int = Set.count st.Pending

The F# EchoMQ keeps pending as an O(log n) sorted set today, and materializes a list only for display (echo_fs/EchoMQ/Store.fs, Jobs.fs — built and tested). The Valkey transport (EchoMQ.Connector) lands next; until then Connector.eval raises "EchoMQ Valkey connector: coming soon".

The cost

A list is O(n) at the far end; a sorted Set is O(log n) for the minimum, contains, and add.

The chapter ahead

That balanced tree is the start of C4's structures — trees, maps, the HAMT and CHAMP that back the registry.

Where this leads

That completes the list: its shape, the recursion and tail recursion that walk it, and the cost model that chooses the right structure for a queue. The next module turns the tail into two branches and a walk into a traversal — C4.02, Trees & traversals — where the balanced tree behind a Set gets its own chapter.

↑ C4.01 · Lists, recursion & complexity ← C4.01.2 · Tail recursion C4 · Algorithms overview →

References

Sources

Related in this course