Summary
PathTrie.advance() (Sources/EdgeHooks/PathTrie.swift) takes an NSLock on every first-hit edge during a test run, via PathTrieStrategy's onEdge observer. It's on the per-dispatch hot path and should be made lock-free, but unlike the other strategies it is not a mechanical swap — tracking separately so it isn't lost.
Context
A lock audit of the coverage-strategy hot path (scheduler-lab Finding 42) found that SyncBox (an NSLock-backed test utility) and a couple of os_unfair_locks had leaked onto the per-dispatch observer path. Measured per-strategy lock acquisitions (stlc/SinglePreserve, synchronous SUT, 6s):
| strategy |
acquisitions |
tests |
acq/test |
contended |
throughput |
| hitcountbuckets |
14,272,900 |
20,000 |
~714 |
0 |
3.3k/s |
| boundarystate |
1,386,368 |
1,385,000 |
1.0 |
0 |
231k/s |
| pathtrie |
(NSLock, uninstrumented) |
413,000 |
per-edge |
0 |
69k/s |
Contention was zero (our SUTs are synchronous), but the uncontended acquisition volume itself is the cost — an out-of-line libsystem call + atomic per acquisition. hitCountBuckets and comparisonCoverage have since been made lock-free (replacing their per-dispatch SyncBox with fixed-capacity per-slot-atomic accumulators, mirroring BoundarySiteAccumulator), with a measured ~28× throughput win on hitCountBuckets (20k → ~565k tests/6s).
Why PathTrie is different
The accumulator pattern (fixed-capacity flat atomic arrays, claimed-index drain) works for the other strategies because their per-dispatch state is an unordered map/set. PathTrie guards an ordered, mutable trie with parent/child links that it walks and extends per edge — the lock-free flat-array pattern does not transfer directly.
Proposed approaches (not yet evaluated)
- Per-thread tries merged at
decide. Cross-thread sharing of one trie only matters when the SUT spawns concurrent work (inherited coverage context); for the common synchronous case a per-thread trie has no contention and no lock. Merge/compare at decide.
- Lock-free trie (CAS-published child pointers). A genuine concurrent-data-structure effort; higher risk.
Either needs its own design pass + benchmark. Deferred from the Finding-42 lock-excision sweep.
Summary
PathTrie.advance()(Sources/EdgeHooks/PathTrie.swift) takes anNSLockon every first-hit edge during a test run, viaPathTrieStrategy'sonEdgeobserver. It's on the per-dispatch hot path and should be made lock-free, but unlike the other strategies it is not a mechanical swap — tracking separately so it isn't lost.Context
A lock audit of the coverage-strategy hot path (scheduler-lab Finding 42) found that
SyncBox(anNSLock-backed test utility) and a couple ofos_unfair_locks had leaked onto the per-dispatch observer path. Measured per-strategy lock acquisitions (stlc/SinglePreserve, synchronous SUT, 6s):Contention was zero (our SUTs are synchronous), but the uncontended acquisition volume itself is the cost — an out-of-line libsystem call + atomic per acquisition.
hitCountBucketsandcomparisonCoveragehave since been made lock-free (replacing their per-dispatchSyncBoxwith fixed-capacity per-slot-atomic accumulators, mirroringBoundarySiteAccumulator), with a measured ~28× throughput win onhitCountBuckets(20k → ~565k tests/6s).Why PathTrie is different
The accumulator pattern (fixed-capacity flat atomic arrays, claimed-index drain) works for the other strategies because their per-dispatch state is an unordered map/set.
PathTrieguards an ordered, mutable trie with parent/child links that it walks and extends per edge — the lock-free flat-array pattern does not transfer directly.Proposed approaches (not yet evaluated)
decide. Cross-thread sharing of one trie only matters when the SUT spawns concurrent work (inherited coverage context); for the common synchronous case a per-thread trie has no contention and no lock. Merge/compare atdecide.Either needs its own design pass + benchmark. Deferred from the Finding-42 lock-excision sweep.