Skip to content

Build1 publisher3 min readPublished

nondet re-runs each probe in a fresh worker because Python randomises hashing per interpreter

The obvious determinism check calls a function twice in one process, where the hash seed never changes. nondet re-runs each function against a fixed input ladder in fresh workers, and refuses to probe I/O.

The Engineer · Build desk

Illustration accompanying nondet re-runs each probe in a fresh worker because Python randomises hashing per interpreter

What happened

  • Three fresh python3 -c invocations of the same three-element set expression printed three different orderings in the transcript recorded in nondet's README.
  • nondet takes a directory or a single FILE::NAME target and re-runs each function against a fixed ladder of probe inputs in fresh worker processes, covering signatures of one to three positional arguments.
  • On a 19-function fixture set, the tool caught 9 of 9 nondeterministic functions and falsely flagged none of the 10 deterministic ones.
  • Pointed at a real 283-function tree with its safety gate on, it probed 127 functions and found 2 nondeterministic ones: one returns a set, and one's value moves between runs.

Compiled by The EngineerSomething wrong?How this is made

Why it matters

  • constraint Because a clean verdict is only the absence of a counterexample across the ladder, CI can fail a build on a finding but cannot treat a pass as evidence the function is deterministic.
  • cost Refusing to let the probe write left 156 of the 283 functions in the real tree unprobed, and one real finding, a function returning a path under a fresh temp directory, only appears under --unsafe.
  • decision Teams choosing between a static grep for random and a runtime probe now have a concrete data point: random.Random(42) is deterministic and the grep flags it.
  • exposure Anyone pointing this at a tree they did not write is executing that tree, and the gate stops only at writing and communicating, so other impure code runs.

String hashing is randomised per interpreter, so every set and dict inside one process shares one ordering and the next process gets a different one [1]. A function returning `list({'alpha','beta','gamma'})` answers identically twenty times out of twenty in a single interpreter [2]. Twenty calls are one draw, counted twenty times. The post says of the two-call check: "I wrote that check, and it is blind to the commonest source of nondeterminism in the language" [33]. nondet's workers run with `PYTHONHASHSEED` cleared, so a seed pinned in your environment cannot blind the check [6].

Process count is the sample size. A hash-order defect in a three-key dict admits 3! = 6 orderings, and the package puts the miss rate for three fresh processes at about 2.8 percent [13]. Three draws from six agree when the second and third match the first, which is (1/6)^2, or one in 36 [16]. An eight-key dict admits 40,320 orderings and is missed about once in a billion [14]; squaring the same fraction gives one in 1.63 billion [17]. Both shapes sit on the ladder, and the eight-key rung is the one that catches the defect [15].

The `nondeterministic` verdict comes with a witness: the input, and the two different answers it produced [11]. `deterministic` means only that no run disagreed across the ladder, and the output is worded as the absence of a counterexample [12]. The project also ships its own falsification test, committed as `test_in_process_repetition_would_have_missed_it`, asserting that the in-process check finds no variation over 20 calls on a hash-order function and that nondet finds it anyway [9]. If in-process repetition ever catches it, the test says, fresh processes are "expensive theatre" [10].

The probe executes the code it is asked about [26]. An early run reported a function raising `TypeError` once and `FileExistsError` the next time; the difference between runs was real, and it was also proof that the first run had created a file on disk [27]. `open()`, `subprocess` and sockets are refused, while `time`, `random`, `uuid` and set ordering stay in scope, because they are read-only and they are the target [28]. `--unsafe` lifts probing on the 283-function tree to 169 functions and the findings to 4 [29]: 42 more functions, two more findings [32].

The scores come from the tool's own fixtures, with the labels written down separately from the function names so the checker is not graded against its naming convention [18]. For 9 of 9 to mean anything on your tree, your nondeterminism has to look like the fixtures' (set order, clock, uuid), and your functions have to take one to three positional arguments, since variadics, keyword-only signatures and zero-arity functions are refused with a reason [4][5][19].

One deterministic fixture comes back as a refusal on purpose: every rung of its ladder raised, and a ladder that only reached a function's type errors has not measured its behaviour [20]. `dedup_unsorted` and `dedup_sorted` are one `sorted()` apart [21]. `seeded` uses `random.Random(42)` and is deterministic; `duration_arithmetic` imports `time` and never reads the clock [22][23].

What to watch

  • Whether the committed in-process control test ever starts catching the hash-order fixture, which would retire the fresh-worker design by the project's own rule.
  • A re-run of the 283-function census under the newer rule that files an all-raising function as a refusal, which the README says probes slightly fewer functions.
  • Whether coverage extends past one to three positional arguments to the variadic, keyword-only and zero-arity signatures refused today.
Loading claim ledger
Loading source directory links
Loading share composer
Loading topic controls
Loading related stories