Repository navigation
Brevi v0.22.0
A bug hunt and a head-to-head with Codon and Nuitka. Four rounds of bug hunting fixed the silent wrong answers they turned up (slices with negative steps, list aliasing on the first build attempt, catchable errors, copy.copy, and more), and the comparison found six more bugs, which are also fixed. On the same unchanged Python files, Brevi builds all 591 saved agent programs and all 18 large programs, and every one prints exactly what CPython prints; Codon builds 206 of the 591 and gets 36 of those wrong. Builds are faster by default: brevi run and brevi build without --release beat CPython on all 12 speed programs (1.7x to 40x). With --release, Brevi is level with Codon where Codon builds, and it also runs the object-heavy programs Codon refuses. Sets and deques in typed builds now give constant-time lookups and popleft(). Ints that grow past 64 bits, including values returned from functions (factorials, Fibonacci, recursion), become big ints as in Python. A growing value captured by a closure or nonlocal still stops with an overflow error.
-
Bug hunt, part 1: silent wrong answers fixed (each printed something other than CPython, with no error). Typed build: negative-step slices (
xs[::-2],xs[-1:-3:-1],s[4:0:-1]gave the wrong items or none; anyxs[a:b:k]now picks as Python does, also on text);zs = xsfollowed byxs.sort(),xs.extend(...),xs += [...]ordel xs[a:b]left zs unchanged (now built over dynamic values, where both names share the list); format specs with a fill character or theb,o,g,e,#,_,=and nested{x:{w}.2f}forms ('{:-^5}'.format('a')printeda); f-strings{x!r},{x=},{ x }and{1e16:g}; a plain (not f-) string such as"{x}"was filled in from a variable named x; a list mixing ints and floats printed1000.0as1000. Python files that print or walk a set (the typed build keeps a set in sorted order, CPython walks its hash table:{-1, 5}prints{5, -1}, and a set inside a dict printed as a list), or that change a value inside the print call showing it (print(q, q.popleft())), are now built over dynamic values. Dynamic build:raise ValueError("msg")(any built-in exception) lost its message and args;str.centerpadded odd widths on the wrong side; a set literal of 3 or more constants printed in a different order than CPython. 11 new parity probes cover these. -
Bug hunt, part 2. Silent wrong answers: the checks that make Python names share a list (
zs = xs; xs.sort(); print(zs)) were skipped on the first build attempt of every Python file, so most such programs printed an unchanged copy (they now build over dynamic values, where both names share the list); a change through one name followed by setting it anew (xs.sort(); xs = [...]; print(zs)) was also missed.'-'.join("xyz")printed-(nowx-y-z).-0.0 % 5.0printed-0.0(Python's zero remainder takes the divisor's sign), and float or JSON-number%and//by zero gave nan instead of ZeroDivisionError. In a Python file, an unknown method was silently renamed to a near one (s.rpartitionran ass.partition); Python files are never auto-fixed now. Printing arematch showed its groups (['12'],[]) instead of<re.Match object; ...>or None (such files now build over dynamic values). Speed: in dynamic builds everys.add(x),len(s)ands |= tcopied the whole set, so a 40,000-item BFS took 34 seconds; it now takes 0.09 s, as CPython does, and-=,&=and issuperset no longer slow down with the set's size. -
Bug hunt, part 3 (exceptions, input, numbers). Python files with
except ZeroDivisionError,IndexError,KeyError,LookupError,ArithmeticError,AssertionError,EOFError,OverflowErrororRecursionErrorbuild over dynamic values; the typed build stopped at those errors instead of letting the except catch them. Silent wrong answers fixed: a dict or set changed in a loop over it went on (CPython raises RuntimeError; such files build over dynamic values);2.0 ** 5000printed inf (OverflowError),0.0 ** -1and(-8) ** 0.5printed inf/nan (ZeroDivisionError, and a refusal since Python gives a complex number); a huge int power wrapped its exponent.input()at the end of the input raises EOFError (it returned "").int("1_000")andfloat("1_0.5")read as in Python.copy.copy(rows)shares the inner lists, as in Python (such files build over dynamic values; the typed build copied them). Dynamic builds: unbounded recursion raises RecursionError (it crashed with a stack overflow), andsys.setrecursionlimitstill allows deep recursion. -
Fast sets in typed builds. Typed builds kept a Python set as a plain list, so every
x in sscanned it: a 40,000-node BFS took several seconds and a 400x400 grid BFS with a walls set ran for over two minutes (CPython: 0.03 s and 0.4 s). A list or set that is searched withinand otherwise only added to, popped, counted, sorted or walked (a function's ownseen, or a parameter used that way) is now kept with a hash index, sointakes constant time; the items stay in the same order, so output does not change. The grid BFS now takes 0.8 s and the 40,000-node BFS 0.2 s (what remains isdeque.popleft(), still a list shift in typed builds). Set&and-sort one side once instead of scanning it for every item (15,000-item sets: 2.8 s to under 0.1 s), andwhile q:no longer copies the whole list on every test. tests/typed checks these against CPython with a time limit. -
Fast deques and object sets in typed builds. A
deque(or a list taken from the front withpop(0)) that is otherwise only added to, popped, read by index or walked is kept as a ring buffer, sopopleft()takes constant time instead of moving every item (40,000-node BFS: 0.20 s to 0.13 s; the 400x400 grid BFS takes 0.21 s with--release, CPython 0.43 s). Sets stored on objects (self.seen = set(), thenx in self.seen) get the same hash index as local sets when every use of that field is a set use. -
Big ints returned from functions. A function whose result outgrows 64 bits returns a big integer, as in Python. This covers a loop that multiplies (
f *= i ... return f), Fibonacci and Tribonacci sums, and recursion such asreturn n * fact(n - 1)orfib(n - 1) + fib(n - 2). These calls stopped with an overflow error before. Where such a call meets other big values or is printed, it stays big. Where an int is needed (an index, a count,//or%), it becomes an int, and raises OverflowError only if it does not fit. A function's locals no longer have to stay small ints just because another function uses the same name. -
Still open: a growing value captured by a nested function (a closure or
nonlocal) stops with an overflow error. -
Fast by default, and the Codon/Nuitka gaps closed.
brevi runandbrevi buildwithout--releasenow compile the program at opt-level 1 against a fully optimised runtime, so the default build beats CPython on all 12 speed programs inbench/compare(it was slower on 5): trees 9.8 s to 0.71 s (CPython 5.2 s), strings 5.6 s to 1.13 s (2.4 s), records 2.5 s to 0.38 s (0.71 s), nbody 1.4 s to 0.12 s; a cold build takes about 0.3 s longer. Typed programs get a small-object allocator (per-thread free lists for blocks up to 256 bytes, as CPython's pymalloc does), about 25% faster on string and dict work, plus quicker one-charactersplitand{i:06d}formatting. List slice assignment (xs[a:b] = ys,perm[:k+1] = perm[k::-1]) builds typed, so fannkuch runs at 3.5x CPython instead of 0.4x. Ints that grow past 64 bits in Python (a factorialf *= i, a rolling hashh = h * 31 + ord(c), Fibonaccia, b = b, a + b, big literals) become big ints,3 ** 200 % mis worked out exactly, and a literal power past 64 bits builds over dynamic values; these stopped with an overflow error before (a value returned from a function still does). Generators work in dynamic builds and run lazily, step by step with their caller as in CPython (endless generators,send(),yield fromwith a return value,StopIteration.value, generators in classes and closures); the typed build, which runs a generator to the end at its first use, keeps only generators where that cannot show (no prints, no reads of outside state, no while loops), and a yield inside try/finally or with is refused at build time.csv.DictReaderis native (rows are dicts of str, sod[r["dept"]]no longer guesses int keys),__file__is the file's absolute path, and thesys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))line needs no CPython.csv.reader(f, delimiter=";")is no longer read with commas. The chess huge-set program with generators and both__file__programs now build natively and match CPython. -
Brevi vs Codon vs Nuitka (
bench/compare/): the same unchanged Python files built by Brevi, Codon 0.20.6 and Nuitka 4.3.4, checked against CPython's exact output and exit status, with build and run times. Of 591 saved agent solutions, Brevi builds 589 and matches CPython on 588, Nuitka 591 and 591, Codon 206 and 170 (16 of its builds print a different answer with no error). On typed code Brevi--releaseruns 2.7x to 47x faster than CPython on 9 of 12 speed programs, level with Codon; Nuitka stays near CPython. It found four silent wrong answers in Brevi, now fixed:book = asks if buy else bidsfollowed bybook.remove(o)changed a copy (such files now build over dynamic values);m.group(3) is Nonewas False for a group that did not match (likewise); an f-string value starting with a number (f"{1/3:.3f}",f"{2*n}") printed as literal text;raise SystemExit(3)exited with 0 (dynamic build) or 1 (typed build) instead of 3. Also fixed two wrong refusals:d.setdefault(k, set()).add(x)stopped with KeyError, and10 ** -2stopped with an error instead of giving 0.01.
Prebuilt brevi compiler for Linux, macOS and Windows. brevi still needs rustc on the PATH to build programs; sh install.sh fetches it and picks the right download.