Skip to content

Build1 publisher3 min readPublished Updated

countfn fits complexity classes to operation counts that match across Python and JavaScript

Megapixel99's countfn counts reads, writes and calls instead of timing code, and insertion sort on seed 17 logs 3,812 reads in Python and JavaScript alike. Counts are exact, so the tool can decline to name a class when the fit does not settle; its author says the timing tools on PyPI and npm cannot.

The Engineer · Build desk

Illustration accompanying countfn fits complexity classes to operation counts that match across Python and JavaScript

What happened

  • Megapixel99's countfn estimates how a function's cost grows by counting operations on an instrumented input across a ladder of sizes, and it can refuse to name a class.
  • Its author says the empirical complexity tools on PyPI and npm, including big-O and big-o-calculator, all time execution and neither can refuse to answer.
  • Out-of-place algorithms work on copies the counter never sees, so a naive merge sort run reports only n reads.

Compiled by The EngineerSomething wrong?How this is made

Why it matters

  • capability Complexity evidence becomes an integer table that someone on another machine, or in the other language, can reproduce exactly and assert in a test.
  • constraint Any algorithm that allocates its own buffers has to be edited to accept and wrap a probe before its read counts describe its real cost.
  • decision Deterministic functions come back UNDETERMINED by default, so a user who wants a named class must choose a tolerance and accept a report that labels those error bars as declared.

A stopwatch on a shared machine returns a mean over noise. countfn runs on a fitting library called undetermined, and that library's central precondition refuses exactly that kind of observable [7]. According to the author, a timing still has a standard error, still forms a ladder of sizes and can still plateau [7]. Noisy input therefore passes the fitter's checks and comes out as a confident answer [7]. "A count gives the ladder, the error bars and the three-rung plateau something real to be computed from," the author wrote [8].

The channel choice is the part I would defend at review. Reads, writes and wrapped calls are counted because they mean the same thing in both languages [9]. Comparisons are left out on purpose. `a < b` on two objects is two protocol events in JavaScript and one dunder method in Python, so the user wraps the comparator and each side counts one call per call [10]. The author reports insertion sort's comparisons fitting 0.2559 +/- 0.003006 times n^2 and calls it the textbook n^2/4 [11]. That coefficient sits 0.0059 above a quarter, about two of its own standard errors [12].

Parity comes from pinning three things: one seeded generator (mulberry32, specified in 32-bit arithmetic), one subscript rule and one iteration rule [13]. The iteration rule is the constraint nobody would guess. Iterating costs n reads, never n+1, because Python's fallback protocol would otherwise keep calling `__getitem__` until it raised [13]. With those fixed, insertion sort on seed 17 at n=64 records 3,812 reads and 1,848 writes in both languages [14]. A parity suite compares count tables for four algorithms [14].

The refusals are good engineering. A count that depends only on n has a standard error of exactly zero, so the verdict is `UNDETERMINED [exact]`, printed next to the mean counts [15]. Passing a `tolerance` produces error bars, and the report says they were declared, not measured [15]. Merge sort's reads over n log n move from 2.755 to 2.861 across a 32-times ladder [16]. That is a drift of about 3.8 percent [17], and the report says the constant is still moving [16]. Two classes that both settle also get a refusal. The post puts the gap between n and n log n at only 1.3x on its ladder, and at 1.8x with a top rung of 2048 [18]. One committed test asserts that three functions return n^2, log n and a refusal together [19].

The sharp edge is scope. The instrument sees only the object it wrapped [20]. Merge sort copies its input and works on buffers nothing is counting, so a naive run reports n reads [20]. The fix is an opt-in `probe` parameter, visible in the signature, that wraps the function's own working structures on the same counter [21]. A test checks both sides: far more than n reads with the probe, exactly n without [21].

A count repeats across machines because it records how many operations ran [1]. For it to predict wall-clock time as well, each counted read would have to cost about the same at every input size, and a count cannot show whether it does. The post does not include a side-by-side run showing big-O or big-o-calculator naming a wrong class [2]. In my context, checking that a change did not turn a log n lookup into a linear one, I would take the integer over the stopwatch. The library installs from either registry [3].

What to watch

  • Whether the two dependency findings the author filed in the README change how undetermined handles a zero-error rung.
  • Whether the parity suite grows past four algorithms to cover out-of-place ones that need a probe.
  • A side-by-side run of countfn against big-O and big-o-calculator on the same functions, which the post does not include.
Loading claim ledger
Loading source directory links
Loading share composer
Loading topic controls
Loading related stories