; sort.sol -- lines in order, and a file bigger than the memory to hold it. ; ; Run with: ./bin/solas programs/sort.sol && ./bin/solvm programs/sort.sob ; ; solvm sort.sob names.txt in byte order ; solvm sort.sob -n scores.txt by the number each line starts with ; solvm sort.sob -r -u names.txt descending, one of each ; solvm sort.sob -t: -k2,2n /etc/passwd by the second colon field, numerically ; solvm sort.sob -c names.txt say whether it is already sorted ; solvm sort.sob -m a.txt b.txt merge two files that already are ; solvm sort.sob -S 4096 huge.txt hold 4 KB at a time and spill the rest ; ... | solvm sort.sob from a pipe ; ; With no arguments it demonstrates itself on a file it writes, which is the ; house rule for these programs. ; ; **Byte order, always.** `LC_ALL=C` is what the tool on the machine has to be ; run under to agree with this, and that is not a limitation being apologised ; for: a string here is bytes ([2.13](../docs/ROADMAP.md#213-text-is-bytes-and-case-is-ascii-only)), ; `lessThan` compares them, and a collation table is a different program. ; ; --------------------------------------------------------------------------- ; The twenty-first program here, and the first that cannot hold its input ; ; **The prediction was written before the program**, in ; [ideas.md](../docs/ideas.md#which-unix-tool-next-and-what-each-would-press-on--surveyed-2026-08-31), ; and it is kept there rather than rewritten: ; ; > **`sort`.** `array:sorted(block)` at scale, and its stability, which nothing ; > has had to care about. **Its real finding is predicted to be a gap we ; > already know about and nothing has wanted**: an external merge sort writes ; > runs to temporary files and merges them, and there is no positioned write — ; > `writeFile` replaces and `appendFile` appends. That is the mirror of the ; > ranged read built this morning, and `sort` would be its first customer. ; ; **The predicted gap is not there, and the reason is worth more than the ; prediction was.** An external merge sort never writes into the middle of a ; file: it writes each run once, whole, and then reads the runs back. The ; account is at the bottom of this file, with what it found instead -- which ; came from the sweep over real files rather than from anything predicted, and ; with the one claim this program nearly published and had to take back. ; ; --------------------------------------------------------------------------- ; What is here, and what is not ; ; -r descending ; -n by the number a field begins with ; -u one line per distinct key ; -f fold case before comparing ; -b ignore the blanks a field begins with ; -s stable: no last-resort comparison, and ties keep their order ; -c check rather than sort; exit 1 and name the first line out of place ; -t SEP fields are separated by SEP rather than by blanks ; -k F[,F][nrbf] compare by fields, several times over, in the order given ; -o FILE write there rather than to standard output, `-o in.txt` included ; -m the inputs are sorted already; merge them ; -S BYTES hold at most this much in memory and spill the rest to runs ; ; Left out, and each for a reason: ; ; -k F.C a character offset inside a field. The field machinery is the ; interesting half and the offset is arithmetic on top of it; it ; is refused by name rather than misread, and there is a case in ; `differ/` saying so. ; -h -V -R human sizes, version numbers, a random hash. Three more ; comparison functions against the same key machinery. ; -z NUL-terminated records. `split` would do it in one line and ; nothing here produces them. ; collation see the note above. @include "text.sol". ; --------------------------------------------------------------------------- ; Options options := object:new. options:reverse := false. options:numeric := false. options:unique := false. options:foldCase := false. options:ignoreBlanks := false. options:stable := false. options:checkOnly := false. options:mergeOnly := false. options:separator := nil. ; nil means blanks options:keys := array:new. ; key specs; empty means the whole line options:output := nil. options:budget := #16777216. ; -S, in bytes; 16 MB before spilling options:files := nil. ; A key spec is `[fromField, toField, numeric, reverse, blanks, fold]`, with ; `toField` nil for *to the end of the line*. The four flags are the modifiers ; that may follow the fields, each of which turns its global option on for this ; key alone -- never off, which is what the tool does and is the only reading ; that makes `-n -k2,2` and `-k2,2n` agree. options:key := { text | | body, from, to, at, mods, spec, digits | body := text. mods := "". at := #1. ; The point is taken as part of the fields rather than as a modifier, so ; that `-k1.2` reaches the refusal below and is told what is wrong with it ; rather than being told `.2` is not a modifier. Found by the corpus case ; written to pin the refusal, which is the case earning its keep before the ; feature it refuses ever existed. digits := "0123456789,.". { at:lessOrEqual(body:size) :and({ digits:indexOf(body:at(at)):notNil }) }:whileTrue({ at := at:add(#1) }). at:lessOrEqual(body:size):ifTrue({ mods := body:copyFrom(at, body:size). body := body:copyFrom(#1, at:sub(#1)) }). body:indexOf("."):notNil:ifTrue({ error:raise("a character offset in `-k` is not supported: {}" :fill([text])) }). spec := body:split(","). spec:size:greaterThan(#2):ifTrue({ error:raise("`-k {}` names more than a start and an end":fill([text])) }). from := { spec:at(#1):asInteger }:onError({ e | error:raise("`-k {}` does not start with a field number":fill([text])) }). from:lessThan(#1):ifTrue({ error:raise("`-k {}` starts at field {}, and fields start at 1" :fill([text, from])) }). to := spec:size:equals(#2):ifElse( { { spec:at(#2):asInteger }:onError({ e | error:raise("`-k {}` does not end with a field number" :fill([text])) }) }, { nil }). ; Every modifier character, rather than the first: `-k2,2nr` is two of them ; and `-k2,2x` has to be refused rather than half-read. [#1, mods:size]:loop({ m | "nrbf":indexOf(mods:at(m)):isNil:ifTrue({ error:raise("`-k {}` has a modifier that is not one of n, r, b or f" :fill([text])) }) }). [from, to, mods:indexOf("n"):notNil, mods:indexOf("r"):notNil, mods:indexOf("b"):notNil, mods:indexOf("f"):notNil] }. options:read := { args | | i, a, j, c, done, value | self:files := array:new. self:keys := array:new. i := #1. { i:lessOrEqual(args:size) }:whileTrue({ a := args:at(i). a:equals("--"):ifElse( { i := i:add(#1). { i:lessOrEqual(args:size) }:whileTrue({ self:files:add(args:at(i)). i := i:add(#1) }) }, { a:size:greaterThan(#1):and({ a:copyFrom(#1, #1):equals("-") }) :ifElse( { j := #2. done := false. { done:not:and({ j:lessOrEqual(a:size) }) }:whileTrue({ c := a:at(j). c:equals("r"):ifTrue({ self:reverse := true. j := j:add(#1) }). c:equals("n"):ifTrue({ self:numeric := true. j := j:add(#1) }). c:equals("u"):ifTrue({ self:unique := true. j := j:add(#1) }). c:equals("f"):ifTrue({ self:foldCase := true. j := j:add(#1) }). c:equals("b"):ifTrue({ self:ignoreBlanks := true. j := j:add(#1) }). c:equals("s"):ifTrue({ self:stable := true. j := j:add(#1) }). c:equals("c"):ifTrue({ self:checkOnly := true. j := j:add(#1) }). c:equals("m"):ifTrue({ self:mergeOnly := true. j := j:add(#1) }). ; The four that take a value, which may be joined to the ; letter or be the next argument -- `-t:` and `-t :` both. "tkoS":indexOf(c):notNil:ifTrue({ j:lessThan(a:size):ifElse( { value := a:copyFrom(j:add(#1), a:size) }, { i := i:add(#1). i:greaterThan(args:size):ifTrue({ error:raise("-{} wants a value":fill([c])) }). value := args:at(i) }). c:equals("t"):ifTrue({ value:size:equals(#1):ifFalse({ error:raise("-t wants one character, got `{}`" :fill([value])) }). self:separator := value }). c:equals("k"):ifTrue({ self:keys:add(self:key(value)) }). c:equals("o"):ifTrue({ self:output := value }). c:equals("S"):ifTrue({ self:budget := { value:asInteger }:onError({ e | error:raise("-S wants a number of bytes, got `{}`" :fill([value])) }). self:budget:lessThan(#1):ifTrue({ error:raise("-S cannot hold {} bytes" :fill([self:budget])) }) }). done := true }). "rnufbscmtkoS":indexOf(c):isNil:ifTrue({ error:raise("unknown option -- {}":fill([c])) }) }). i := i:add(#1) }, { self:files:add(a). i := i:add(#1) }) }) }). self:files:size:equals(#0):ifTrue({ self:files:add("-") }) }. ; --------------------------------------------------------------------------- ; Fields, which is where the fiddliness lives ; ; **A field carries the blanks in front of it**, and that is not a quirk to be ; tidied away: `-k2,2` over `a z` and `a y` compares `" z"` against ; `" y"`, so the *wider* gap sorts first because a space is less than a letter. ; `-b` is what says to skip them, and the pair of cases in the corpus is the ; only reason this paragraph is right. ; ; With `-t` there are no blanks in it: the line is cut at each separator and the ; separator belongs to neither side, so `a::b` has three fields and the middle ; one is empty. fieldsOf := { line | options:separator:isNil:ifElse( { | out, i, size, start | ; Each field is the blanks before it and the non-blanks after, which ; is one pass with two inner walks rather than a split. out := array:new. size := line:size. i := #1. { i:lessOrEqual(size) }:whileTrue({ start := i. { i:lessOrEqual(size) :and({ line:at(i):equals(" "):or({ line:at(i):equals("\t") }) }) }:whileTrue({ i := i:add(#1) }). { i:lessOrEqual(size) :and({ line:at(i):equals(" "):or({ line:at(i):equals("\t") }) :not }) }:whileTrue({ i := i:add(#1) }). out:add(line:copyFrom(start, i:sub(#1))) }). out }, { line:split(options:separator) }) }. ; The text a key spec names: field `from` to field `to`, joined back together ; with what separated them -- which for the blank case is nothing, since the ; blanks are already inside the fields. ; ; **A field that is not there is the empty string** rather than an error, which ; is what the tool does with `-k3` on a two-field line and is what makes a key ; usable on ragged input at all. keyOf := { line, spec | | fields, from, to, out, i | fields := fieldsOf:value(line). from := spec:at(#1). to := spec:at(#2):isNil:ifElse({ fields:size }, { spec:at(#2) }). to:greaterThan(fields:size):ifTrue({ to := fields:size }). from:greaterThan(fields:size):or({ to:lessThan(from) }):ifElse( { "" }, { out := array:new. [from, to]:loop({ i | out:add(fields:at(i)) }). out:join(options:separator:isNil:ifElse({ "" }, { options:separator })) }) }. ; --------------------------------------------------------------------------- ; The number a line begins with ; ; **`asFloat` is strict and this cannot be**, which is the second time a program ; here has wanted a lenient numeric read -- `awk` predicted it first and was not ; written on it. What the tool reads is: blanks, then a sign, then digits, then ; a point and more digits. **No exponent and no hex**: `1e3` is one and `0x10` ; is zero, measured rather than assumed, and anything with no digits at all is ; zero as well. ; ; So the reading is written out here, and it is nine lines. That is the whole ; cost of the gap for this program, and it is worth stating because the entry it ; would open should not be opened on nine lines. numberOf := { text | | i, size, sign, digits, seenPoint, out | size := text:size. i := #1. { i:lessOrEqual(size) :and({ text:at(i):equals(" "):or({ text:at(i):equals("\t") }) }) }:whileTrue({ i := i:add(#1) }). ; **A minus and not a plus.** The tool reads `-1` as minus one and `+5` as ; *zero* -- so `+5` sorts with the unreadable lines and the last resort puts ; it before `3`, because `+` is less than `3` in bytes. Found by sorting this ; repository's own README, where a line begins `+0.2% to +3.4%`; the ; generated half of the sweep never produced a leading plus because nobody ; thought to put one in the alphabet. sign := 1.0. i:lessOrEqual(size):and({ text:at(i):equals("-") }):ifTrue({ sign := -1.0. i := i:add(#1) }). digits := "". seenPoint := false. { i:lessOrEqual(size) :and({ "0123456789":indexOf(text:at(i)):notNil :or({ text:at(i):equals("."):and({ seenPoint:not }) }) }) }:whileTrue({ text:at(i):equals("."):ifTrue({ seenPoint := true }). digits := digits:concat(text:at(i)). i := i:add(#1) }). out := (digits:equals(""):or({ digits:equals(".") })):ifElse( { 0.0 }, { { digits:asFloat }:onError({ e | ; A run of digits with a point at one end -- `3.` or `.5` -- which ; `asFloat` refuses and every sort reads. { digits:concat("0"):asFloat }:onError({ e2 | { "0":concat(digits):asFloat }:onError({ e3 | 0.0 }) }) }) }). sign:mul(out) }. ; --------------------------------------------------------------------------- ; Comparing ; ; One key at a time, in the order they were given, and the first that decides ; wins. **The last resort is the whole line, compared byte for byte** -- and it ; is switched off by `-s` and by `-u`, both measured against the tool: `-s` ; wants ties in input order, and `-u` wants keys rather than lines to be what ; is distinct. ; ; It answers `#-1`, `#0` or `#1` rather than a boolean, because a sort needs ; *less than* and a check and a uniqueness test need *equal*, and deriving one ; from two calls to the other costs a second pass over the keys. compareText := { a, b, useNumeric | useNumeric:ifElse( { | x, y | x := numberOf:value(a). y := numberOf:value(b). x:lessThan(y):ifElse({ #-1 }, { y:lessThan(x):ifElse({ #1 }, { #0 }) }) }, { a:lessThan(b):ifElse({ #-1 }, { b:lessThan(a):ifElse({ #1 }, { #0 }) }) }) }. ; `-b` and `-f` change what is compared rather than how, so they are applied to ; the text before it is handed on. prepare := { text, blanks, fold | | out, i | out := text. blanks:ifTrue({ i := #1. { i:lessOrEqual(out:size) :and({ out:at(i):equals(" "):or({ out:at(i):equals("\t") }) }) }:whileTrue({ i := i:add(#1) }). out := i:greaterThan(out:size):ifElse({ "" }, { out:copyFrom(i, out:size) }) }). ; **Upper, not lower**, and the difference is visible only next to ; punctuation: folding down puts `[` (91) below `a` (97) and folding up puts ; it above `Z` (90). Measured against the tool, which answers `ab Zb [a`. ; The generated half of the sweep never showed it because its alphabet is ; letters and digits; three of this repository's own README files did. fold:ifTrue({ out := out:asUppercase }). out }. compareLines := { a, b | | verdict | verdict := #0. options:keys:do({ spec | | ka, kb, useNumeric, useBlanks, useFold, r | verdict:equals(#0):ifTrue({ useNumeric := options:numeric:or({ spec:at(#3) }). useBlanks := options:ignoreBlanks:or({ spec:at(#5) }). useFold := options:foldCase:or({ spec:at(#6) }). ka := prepare:value(keyOf:value(a, spec), useBlanks, useFold). kb := prepare:value(keyOf:value(b, spec), useBlanks, useFold). r := compareText:value(ka, kb, useNumeric). (options:reverse:or({ spec:at(#4) })):ifTrue({ r := r:negated }). verdict := r }) }). ; No `-k` at all: the whole line is the key, and the last resort would be ; the same comparison a second time. options:keys:size:equals(#0):ifTrue({ verdict := compareText:value( prepare:value(a, options:ignoreBlanks, options:foldCase), prepare:value(b, options:ignoreBlanks, options:foldCase), options:numeric). options:reverse:ifTrue({ verdict := verdict:negated }) }). ; The last resort, on the whole line and in byte order, which `-r` reverses ; and `-s` and `-u` switch off. ; ; **It applies with no `-k` too**, which a first draft got wrong on the ; reasoning that the key is then the whole line already. It is not: `-f` ; folds it and `-b` strips it, so `Apple` and `apple` tie under `-f` and ; the byte comparison is what puts the capital first. Two of the fourteen ; smoke tests, and both of them options that change the key rather than ; the order. verdict:equals(#0) :and({ options:stable:not }) :and({ options:unique:not }):ifTrue({ verdict := compareText:value(a, b, false). options:reverse:ifTrue({ verdict := verdict:negated }) }). verdict }. ; What `-u` calls the same line: the keys, without the last resort. When there ; are no keys that is the whole line, which is what `sort -u` means on its own. sameKey := { a, b | options:keys:size:equals(#0):ifElse( { compareLines:value(a, b):equals(#0) }, { | verdict | verdict := #0. options:keys:do({ spec | | ka, kb | verdict:equals(#0):ifTrue({ ka := prepare:value(keyOf:value(a, spec), options:ignoreBlanks:or({ spec:at(#5) }), options:foldCase:or({ spec:at(#6) })). kb := prepare:value(keyOf:value(b, spec), options:ignoreBlanks:or({ spec:at(#5) }), options:foldCase:or({ spec:at(#6) })). verdict := compareText:value(ka, kb, options:numeric:or({ spec:at(#3) })) }) }). verdict:equals(#0) }) }. ; --------------------------------------------------------------------------- ; Reading lines without holding the file ; ; A reader answers one line at a time and nil at the end. Two sources, and the ; difference between them is the whole of what this program had to find out. ; ; **From a file: a ranged read with a buffer.** `readFile(path, from, count)` ; gives a window without a handle, so a reader is a path and an integer -- and ; several readers over several files need nothing shared, which is what the ; merge below depends on. ; ; **From a pipe: the same shape**, since ; [6.45](../docs/COMPLETED.md#645-a-pipe-cannot-be-taken-in-bounded-pieces--done) ; closed. `readUpTo(#n)` answers up to n bytes exactly as they were sent, so the ; two branches differ by which call fills the buffer and by nothing else. The ; program that raised that entry is this one -- see the bottom of this file for ; what it cost while the middle was missing. ; ; **The count is a ceiling and the window is a lower one.** `readUpTo` answers ; out of the four-kilobyte window every reader here shares, so asking for 65,536 ; gets 4,096 and the loop goes round again. That is the documented contract ; rather than a surprise -- *a short answer is normal* -- and it is written down ; because `readChunk` reads like a promise about the size of a read, and for the ; pipe it is not one. readChunk := #65536. reader := object:new. ; **A reader holds lines, not a buffer**, and that is the whole of why the size ; of a read stopped mattering. The first version kept one string and cut the ; front off it for each line, so every line copied the whole of what was behind ; it: `readChunk` at 65,536 cost 1.03 s on a 4.7 MB file where 8,192 cost 0.86, ; and a *large* read was the slow one. Splitting each piece once instead copies ; every byte once whatever the piece is. ; ; lines the fields of the piece last read, `head` to `limit` of them ; complete and not yet handed out ; parts the fragments of the line still being read, joined only when its ; newline arrives -- a line longer than a read is the case that ; makes this an array rather than a string, since concatenating ; into one copies the whole of it per piece ; pending how many bytes are in them, so that "is anything left?" can be ; asked without joining reader:onFile := { path | | r | r := object:new. r:path := path. r:at := #1. ; the next unread byte, one-based r:lines := array:new. r:head := #1. r:limit := #0. r:parts := array:new. r:pending := #0. r:done := false. r:kind := 'file. r }. reader:onStdin := { | r | r := object:new. r:lines := array:new. r:head := #1. r:limit := #0. r:parts := array:new. r:pending := #0. r:done := false. r:kind := 'stdin. r }. reader:open := { name | name:equals("-"):ifElse({ self:onStdin }, { self:onFile(name) }) }. ; Reads until a complete line is waiting or the source is spent. Answers ; whether anything is left to hand out. ; ; **A piece is split once and never looked at again.** The obvious loop asks ; `r:buffer:indexOf("\n"):isNil` as its condition and concatenates each piece ; onto a buffer, which searches and copies everything read so far on every ; read: on a line longer than one piece both are quadratic in the length of the ; line. Measured on one line and nothing else, through a pipe, `-g`, best of ; three: ; ; scan and concat scan fixed this ; 1,000,000 0.48 s 0.01 s 0.01 s ; 2,000,000 1.90 s 0.04 s 0.02 s ; 4,000,000 7.71 s 0.25 s 0.03 s ; 8,000,000 -- 1.10 s 0.07 s ; 16,000,000 -- 4.48 s 0.15 s ; ; The middle column is the scan fixed and the concatenation left, and it is ; still four times the time for twice the input. This column is twice for ; twice, which is what a reader owes. ; ; The fragments are joined **only when the newline arrives**. Joining on every ; piece would put the copy back exactly where it was taken from. reader:fill := { r | | more, fields | { r:head:greaterThan(r:limit):and({ r:done:not }) }:whileTrue({ more := r:kind:equals('file):ifElse( { | got | got := system:readFile(r:path, r:at, readChunk). r:at := r:at:add(got:size). got:size:equals(#0):ifTrue({ r:done := true }). got }, { | got | got := system:readUpTo(readChunk). got:isNil:ifElse({ r:done := true. "" }, { got }) }). more:size:greaterThan(#0):ifTrue({ fields := more:split("\n"). r:parts:add(fields:at(#1)). r:pending := r:pending:add(fields:at(#1):size). fields:size:greaterThan(#1):ifTrue({ fields:atPut(#1, r:parts:join("")). r:lines := fields. r:head := #1. r:limit := fields:size:sub(#1). r:parts := array:new. r:parts:add(fields:at(fields:size)). r:pending := fields:at(fields:size):size }) }) }). r:head:lessOrEqual(r:limit):or({ r:pending:greaterThan(#0) }) }. ; **A last line with no newline is a line**, which is what every sort does -- ; and the output always ends with one, so the difference never reaches the ; answer. That is the one place this program is allowed not to care about the ; distinction `diff` had to be exact about. reader:next := { r | | line | self:fill(r):ifElse( { r:head:lessOrEqual(r:limit):ifElse( { line := r:lines:at(r:head). r:head := r:head:inc. line }, { line := r:parts:join(""). r:parts := array:new. r:pending := #0. line }) }, { nil }) }. ; --------------------------------------------------------------------------- ; Where the runs go ; ; `TMPDIR` when there is one, the way the tool does, and `build/` when there is ; not. The directory is made, filled and taken away again -- a program that ; leaves runs behind after sorting a large file is worse than one that is slow. temporary := object:new. temporary:dir := nil. temporary:count := #0. temporary:directory := { | base | self:dir:isNil:ifTrue({ base := system:environment("TMPDIR"). base:isNil:ifTrue({ base := "build/" }). base:endsWith("/"):ifFalse({ base := base:concat("/") }). self:dir := base:concat("solveig-sort-") :concat(system:clock:mul(1000000.0):truncated:asString). system:makeDirectory(self:dir) }). self:dir }. temporary:path := { self:count := self:count:add(#1). self:directory:concat("/run-"):concat(self:count:asString) }. temporary:clean := { self:dir:isNil:ifFalse({ system:filesIn(self:dir):do({ name | system:remove(self:dir:concat("/"):concat(name)) }). system:remove(self:dir). self:dir := nil }) }. ; --------------------------------------------------------------------------- ; Sorting ; ; **`array:sorted(block)` is a stable merge sort**, which this program needs and ; which nothing said. See the bottom of the file: the guarantee is in a comment ; in `builtins.c` and was not in the reference until this program went looking ; for it. ; ; The comparison hands `sorted` a boolean and keeps the three-way answer for the ; merge and for `-u`, which both need *equal* rather than *before*. sortBatch := { lines | lines:sorted({ a, b | compareLines:value(a, b):lessThan(#0) }) }. ; --------------------------------------------------------------------------- ; The whole of it, in one pass over the inputs ; ; Read until the budget is spent, sort what is in hand, and either keep it (if ; that was all there was) or write it out as a run and carry on. **One run means ; the file fitted**, and the merge below is then a walk over a single sorted ; array rather than anything to do with files. runs := array:new. inMemory := nil. spill := { batch | | path | path := temporary:path. system:writeFile(path, sortBatch:value(batch):join("\n"):concat("\n")). runs:add(path) }. readEverything := { | batch, bytes, r, line | batch := array:new. bytes := #0. options:files:do({ name | r := reader:open(name). line := reader:next(r). { line:notNil }:whileTrue({ batch:add(line). bytes := bytes:add(line:size):add(#1). bytes:greaterOrEqual(options:budget):ifTrue({ spill:value(batch). batch := array:new. bytes := #0 }). line := reader:next(r) }) }). ; What is left over is a run like any other -- except when it is the only ; one, where writing it to a file and reading it back would be work done to ; make the code shorter rather than to make it right. runs:size:equals(#0):ifElse( { inMemory := sortBatch:value(batch) }, { batch:size:greaterThan(#0):ifTrue({ spill:value(batch) }) }) }. ; --------------------------------------------------------------------------- ; Merging ; ; **The k-way merge is where a positioned write was predicted and where the ; ranged read turned out to be the whole answer.** Every run has a reader, each ; reader is a path and an integer, and the smallest head wins. Nothing is ; opened, nothing is closed, and nothing has to be seeked to a place it was ; already at. ; ; **The winner comes off a heap, and the first draft used a linear scan.** That ; draft carried a comment saying a heap *would matter at a few hundred runs* and ; that the scan was the trade this repository keeps making until something ; measures otherwise. Something measured otherwise within the day, and the ; comment had named its own falsifying condition well enough to recognise it: ; ; | 400 lines, 23 KB | scan | heap | ; | --- | --- | --- | ; | `-S 100000` -- one run, no merge | 0.01 s | 0.01 s | ; | `-S 1024` -- 23 runs | 0.02 s | 0.02 s | ; | `-S 64` -- 366 runs | **0.24 s** | 0.09 s | ; ; Twenty-four times on four hundred lines, and the shape is `lines x runs`. ; `sweep.sh` runs `-S 16` over this repository's own files, where ; `docs/CHANGELOG.md` is **14,707 lines in 788,815 bytes** -- some forty-nine ; thousand runs, and a comparison per run per line. ; ; **It did not fail. It ran for two hours and fourteen minutes without ; finishing the generated half**, which is how this was found: a check too slow ; to finish is a defect report that nobody reads as one. The same file, same ; budget, on the heap: ; ; ```text ; sort -S 16 docs/CHANGELOG.md 3.88 s, and agrees with the tool ; ``` ; ; And the sweep that would not finish now takes 5 minutes 28 seconds for all ; 1,610 comparisons. ; ; **What the handle-free reader bought is worth naming here.** A merge over ; 43,750 runs is not unusual for an external sort at a small budget, and a ; program holding a file handle per run would have run out of descriptors long ; before it ran out of patience. A reader here is a path and an integer, so the ; only cost of a large `k` was the scan -- which is an algorithm to choose ; rather than a wall to hit. ; ; Ties go to the **earlier run**, which the scan got for free by taking the ; first strictly-smaller head and the heap has to be told: two runs holding ; equal lines must come out in the order they were written, or `-s` stops being ; stable the moment the input spills. emit := object:new. emit:parts := array:new. emit:held := #0. emit:path := nil. emit:started := false. emit:line := { line | self:parts:add(line). self:held := self:held:add(line:size):add(#1). self:held:greaterThan(#1048576):ifTrue({ self:flush }) }. emit:flush := { | text | self:parts:size:greaterThan(#0):ifTrue({ text := self:parts:join("\n"):concat("\n"). self:parts := array:new. self:held := #0. self:path:isNil:ifElse( { system:write(text) }, { self:started:ifElse( { system:appendFile(self:path, text) }, { system:writeFile(self:path, text). self:started := true }) }) }) }. emit:finish := { self:flush. ; A file that was written to must exist even when nothing was written to ; it: `sort -o out.txt` over an empty input leaves an empty file, not the ; file that was there before. self:path:isNil:or({ self:started }):ifFalse({ system:writeFile(self:path, "") }) }. ; A binary heap of run numbers, ordered by the line each run is holding. The ; array is one-based, so a node at `i` has its parent at `i/2` and its children ; at `2i` and `2i+1` with no offset anywhere -- which is the one place this ; language's indexing is simpler than C's rather than noisier. heads := array:new. ; Equal lines go to the earlier run, so that a spilled sort is as stable as one ; that fitted. heapBefore := { a, b | | r | r := compareLines:value(heads:at(a), heads:at(b)). r:equals(#0):ifElse({ a:lessThan(b) }, { r:lessThan(#0) }) }. siftUp := { heap, at | | i, parent, t | i := at. { i:greaterThan(#1) :and({ heapBefore:value(heap:at(i), heap:at(i:div(#2))) }) }:whileTrue({ parent := i:div(#2). t := heap:at(i). heap:atPut(i, heap:at(parent)). heap:atPut(parent, t). i := parent }) }. siftDown := { heap, size | | i, small, left, right, t, going | i := #1. going := true. { going }:whileTrue({ small := i. left := i:mul(#2). right := left:add(#1). left:lessOrEqual(size) :and({ heapBefore:value(heap:at(left), heap:at(small)) }):ifTrue({ small := left }). right:lessOrEqual(size) :and({ heapBefore:value(heap:at(right), heap:at(small)) }):ifTrue({ small := right }). small:equals(i):ifElse( { going := false }, { t := heap:at(i). heap:atPut(i, heap:at(small)). heap:atPut(small, t). i := small }) }) }. mergeReaders := { readers | | heap, size, best, last, haveLast | heads := readers:collect({ r | reader:next(r) }). heap := array:new. size := #0. [#1, heads:size]:loop({ n | heads:at(n):notNil:ifTrue({ heap:add(n). size := size:add(#1). siftUp:value(heap, size) }) }). last := nil. haveLast := false. { size:greaterThan(#0) }:whileTrue({ | line | best := heap:at(#1). line := heads:at(best). ; `-u` drops a line whose key matches the one before it, which is the ; only place the merge looks backwards. options:unique:and({ haveLast }) :and({ sameKey:value(last, line) }):ifFalse({ emit:line(line) }). last := line. haveLast := true. heads:atPut(best, reader:next(readers:at(best))). heads:at(best):isNil:ifElse( { heap:atPut(#1, heap:at(size)). heap:removeLast. size := size:sub(#1) }, { }). size:greaterThan(#0):ifTrue({ siftDown:value(heap, size) }) }) }. ; --------------------------------------------------------------------------- ; Checking rather than sorting ; ; `-c` says nothing when the file is in order and names the first line that is ; not: `sort: :: disorder: `, exit 1. The name of a pipe is ; `-`, which is what the tool prints and is why the corpus marks these cases ; `pipenames:` rather than waving the two routes through. check := { | r, name, previous, n, bad | name := options:files:at(#1). r := reader:open(name). previous := reader:next(r). n := #1. bad := nil. { bad:isNil:and({ previous:notNil }) }:whileTrue({ | line | line := reader:next(r). line:isNil:ifElse( { previous := nil }, { n := n:add(#1). ; `-c` with `-u` refuses an *equal* pair too, which is the one ; place the two options meet. (compareLines:value(line, previous):lessThan(#0) :or({ options:unique:and({ sameKey:value(line, previous) }) })) :ifElse( { bad := [n, line] }, { previous := line }) }) }). bad:isNil:ifElse( { #0 }, { system:writeError("sort: {}:{}: disorder: {}\n" :fill([name, bad:at(#1), bad:at(#2)])). #1 }) }. ; --------------------------------------------------------------------------- ; Running it sort := object:new. ; **Every run starts from nothing**, which the demonstration is what found: ; it sorts the same file three ways, and the second run merged the first run's ; spill files because `runs` and the emitter were still holding them. A program ; invoked once from a command line would never have shown it. sort:run := { | readers | runs := array:new. inMemory := nil. emit:parts := array:new. emit:held := #0. emit:started := false. emit:path := options:output. options:checkOnly:ifElse( { check:value }, { options:mergeOnly:ifElse( { ; The inputs are sorted already, so there is nothing to sort: ; the merge is the whole program, and this is the path a run of ; `sort` over already-sorted parts takes. readers := options:files:collect({ name | reader:open(name) }). mergeReaders:value(readers). emit:finish. #0 }, { readEverything:value. inMemory:isNil:ifElse( { readers := runs:collect({ path | reader:onFile(path) }). mergeReaders:value(readers) }, { | last, haveLast | last := nil. haveLast := false. inMemory:do({ line | options:unique:and({ haveLast }) :and({ sameKey:value(last, line) }):ifFalse({ emit:line(line) }). last := line. haveLast := true }) }). emit:finish. temporary:clean. #0 }) }) }. ; --------------------------------------------------------------------------- ; What it does with no arguments demonstrate := { | dir, path | dir := "build". system:makeDirectory(dir). path := "build/sort-demo.txt". system:writeFile(path, "pear:3\napple:10\nfig:1\nbanana:2\napple:7\n"). "-- in byte order":display. options:files := [path]. sort:run. "":display. "-- by the number after the colon, numerically":display. options:keys := [options:key("2,2n")]. options:separator := ":". sort:run. "":display. "-- one line per fruit, four bytes at a time so it spills to runs":display. options:keys := [options:key("1,1")]. options:unique := true. options:budget := #4. sort:run }. ; **No arguments means two different things here**, which is the second time a ; program in this directory has had that -- `tail` was the first, and the note ; in its file is where this one was copied from rather than rediscovered. ; Every program here runs with no arguments on input it carries; `... | sort` is ; also a real invocation, and it is how half of sort's uses are typed. The same ; empty command line, two meanings, and `system:isTerminal` is what tells them ; apart. ; ; It was found by the corpus rather than by thinking: the pipe route of every ; case with no options ran the demonstration and reported it as the answer. { system:arguments:size:equals(#0):and({ system:isTerminal('input) }):ifElse( { demonstrate:value }, { options:read(system:arguments). system:exit(sort:run) }) }:onError({ e | temporary:clean. system:writeError("sort: {}\n":fill([e:message])). system:exit(#2) }). ; --------------------------------------------------------------------------- ; The prediction was wrong about the gap, and the reason is the finding ; ; **Kept beside the prediction rather than in place of it.** ; [ideas.md](../docs/ideas.md#which-unix-tool-next-and-what-each-would-press-on--surveyed-2026-08-31) ; said `sort`'s real finding would be a missing **positioned write**, on the ; reasoning that an external merge sort writes runs to temporary files and ; `writeFile` replaces where `appendFile` appends. ; ; ### There is nothing to write into the middle of ; ; **An external merge sort never seeks in a file it is writing.** A run is ; produced whole -- read a budget's worth of lines, sort them, write them once ; -- and then it is only ever *read*. The output is produced in order, so it ; appends. `writeFile` and `appendFile` are exactly the two writes this needs ; and there is no third. ; ; The entry called this *the mirror of the ranged read*, and a mirror is the ; wrong figure: the ranged read exists because a program wants to look at part ; of a file it did not write. Nothing wants to write part of a file it is ; producing, because a producer knows what comes next. **A write is not the ; reverse of a read**, and the entry reasoned from the symmetry of the names. ; ; ### What the merge wanted was the ranged read, and it was already there ; ; The k-way merge needs `k` independent positions in `k` files at once, which is ; the thing a language with file *handles* has to think about -- how many are ; open, what closes them, what happens when one is used after closing. ; `readFile(path, from, count)` has none of that: **a reader here is a path and ; an integer.** So the half of the program the entry was worried about is the ; half that needed nothing. ; ; ### The claim this program nearly published, and had to take back ; ; The entry's first sentence was *`array:sorted(block)` at scale, and its ; stability, which nothing has had to care about.* `sort -s` has to care, and so ; does `-k`, so this was going to be the headline: **`sorted` is a stable merge ; sort, deliberately, and nothing says so** -- an implementation detail and a ; promise being the same line of code, which is the shape ; [6.42](../docs/COMPLETED.md#642-a-second-producer-of-sob-has-no-contract-to-build-against--done) ; closed for the bytecode format five days earlier. ; ; **It is not true.** [REFERENCE.md](../docs/REFERENCE.md#array) has said it all ; along, in prose under the sorting examples rather than in the message table: ; ; > The sort is **stable** -- equal elements keep the order they were in -- ; > which is what makes sorting twice a way to order by two keys. ; ; The paragraph was written and nearly shipped because a `grep` for `sorted` ; found the table row and the `filesIn` note and stopped there. **An absence was ; asserted from a search that did not cover the document**, which is the ; argument from absence ; [design.md](../docs/design.md#what-the-language-is-for) rules out for ; features and 2026-09-01 found nothing had ruled out for checks. It is kept ; here rather than deleted because the *good* version of this finding and the ; wrong one look identical until somebody reads the page. ; ; What is true is the smaller thing: **this program depends on that guarantee**, ; and it is the first here that does. `-s` is exactly *no last resort, and let ; the sort keep the order*, and the merge relies on the same promise across ; runs. Until now the sentence in the reference had no customer. ; ; ### `-n` is the second customer for a lenient numeric read ; ; `asFloat` is strict on purpose and the reference says so. Every sort reads a ; *prefix*: blanks, a sign, digits, a point. `1e3` is **one** and `0x10` is ; **zero**, measured against the tool rather than assumed. ; ; [awk](awk.sol) predicted this gap first and was written after `lib/re.sol` ; rather than on it, so the gap was named and never had a second customer. It ; has one now -- and the honest report is that it cost **nine lines**, which is ; why this is a paragraph rather than a roadmap entry. A message that saves nine ; lines in two programs is not one this language is short of. ; ; ### The second customer for 6.43, which is why 6.45 has a number ; ; [6.43](../docs/COMPLETED.md#643-a-program-cannot-read-standard-input-whole-and-the-call-that-looks-as-though-it-can-answers---done) ; said a program cannot read standard input whole, and `diff` raised it because ; `readLine` cannot see the newline at the end. That closed on 2026-09-03 and ; this half did not, so it is ; [6.45](../docs/COMPLETED.md#645-a-pipe-cannot-be-taken-in-bounded-pieces--done) now. ; ; **`sort` does not care about the newline** -- the output always ends with one, ; so the distinction never reaches the answer -- and it was the second customer ; anyway, for the other half: ; `readLine` folds `\r\n` into one terminator, so a file written on another ; system sorts as *different lines* through a pipe than through a name. ; ; **And it adds a reason the entry does not have.** `diff` wants a pipe read ; *whole*. A sort that spills to runs wants the opposite: a pipe read in bounded ; pieces, so that memory stays inside `-S` no matter how large the input is. ; `readKey` does that and costs 238 nanoseconds a byte; `readLine` does it at a ; twentieth of the price and changes the answer. **The entry is about the ; absence of a middle**, and the second customer is what shows that the middle ; is what is missing rather than the whole-file read. ; ; ### And the middle arrived, so this is what it was worth ; ; `readUpTo` shipped in 0.43.0 and the byte-at-a-time loop above is now four ; lines that read like the file branch beside them. Same machine, same input -- ; `docs/REFERENCE.md` and `docs/ideas.md` concatenated, 584,997 bytes in 11,350 ; lines -- and the counts are exact rather than sampled, by the `--steps=N` ; binary search `gzip.sol` describes. **An instruction count does not depend on ; how the machine was built**, and these were reproduced under both `-g` and ; `-O2` to the instruction; the seconds below are `-O2`, best of five, because ; `make` builds `-g` and those would be a different number: ; ; through a pipe, byte at a time 28,846,431 instructions ; through a pipe, `readUpTo` 15,402,663 1.87x fewer ; the same file named on the command line 15,398,455 ; ; **The pipe now costs what the name costs**, to within 4,208 instructions on ; thirteen and a half million saved -- 0.03%, and the file route did not change. ; That is the result worth having and it is not the speed: a program with two ; ways in had two performance stories, and the entry's whole argument was that ; one of them was missing a call. 4.7 MB through a pipe went from 1.50 s to ; 0.81 s. ; ; **What was spent was 23 instructions a byte**, which is what `readKey` costs ; in the loop that has to ask whether it answered nil. Nothing about the answer ; moved -- `oracle.sh` runs all thirty cases down both routes and reports the ; same two divergences it always has. ; ; ### What the conversion turned up, which was a question about `readChunk` ; ### and turned out to be two defects underneath it ; ; The conversion left the pipe route *faster than the named file* -- 20% in wall ; clock, on identical instruction counts -- which does not happen for any reason ; that is about pipes. The first reader drained its buffer with ; `copyFrom(at + 1, size)`, so **every line copied whatever was behind it**, and ; a larger read was therefore not a cheaper one: ; ; readChunk 4,096 0.88 s ; 8,192 0.86 s ; 16,384 0.87 s ; 65,536 1.03 s <- what this program used ; ; (`-O2`, best of five, 4.7 MB, named file.) The pipe was only faster because ; `readUpTo` answers out of a 4,096-byte window whatever is asked for, so it had ; been reading in 4 KB pieces by accident. ; ; **The answer was not to tune the constant.** Asking why a bigger read was ; slower found two quadratics -- the scan in `fill` and this copy in `next` -- ; and fixing both retires the table rather than improving a row of it. Same ; build, same file: ; ; readChunk 4,096 2.64 s ; 8,192 2.62 s ; 65,536 2.56 s <- and now the best of them ; 262,144 2.55 s ; ; A 17% spread with the largest read the worst became a 2% spread with the ; largest read the best, which is the shape a reader should have had all along. ; `readChunk` stays at 65,536 because it has stopped being a question. ; ; **And the win is in bytes copied rather than instructions run**, which is why ; `--steps` could not see any of it. On 584,997 bytes in 11,350 lines: ; ; pipe named file ; as converted 15,402,663 15,398,455 ; scan fixed 15,448,496 15,443,861 +0.3%, and no quadratic ; lines not buffer 15,288,867 15,274,324 -0.7% on where it started ; ; One percent of the instructions against 14% of the wall clock on the named ; route -- 2.97 s to 2.55 s, `-g`, best of three -- because a `copyFrom` is one ; send and a `memcpy` of everything behind the line. **An instruction count is ; not a cost model**, and this is the first measurement here where the two have ; disagreed by more than a rounding.