v0.8.12

Built against Mojo 1.0.0 (ed45d567).

A patch release that is mostly one thread: the regular expression engine learning to remember what it did, which is the third of the three costs in issue #830 and the largest single change to the engine since it was written.

It arrives in three pieces. A compiled program can now say which characters it cannot tell apart, which turns an alphabet of a million code points into a handful of classes and is what makes a table of transitions small enough to keep. On top of that there is a cache of the sets of positions the machine holds, built as they are reached and bounded at two hundred and fifty six of them, which answers in one step what the machine answers by walking every instruction it is holding. And the matching kernel now runs that cache for contains, match and fullmatch over a column tall enough to pay for building it, with the machine kept underneath for every pattern the cache refuses and every row it gives up on.

On a million URLs that is about seven times the run on an anchored pattern of the shape ClickBench q28 uses and about fifteen on an unanchored one the first character set cannot help with. It does not move q28 itself, which replaces rather than matches and waits on the piece that finds where each match ended. count, replace and extract are all still the machine for the same reason.

Beside it, one wrong answer is gone. \z is RE2's spelling for the end of the string and Python read it as a bad escape until 3.14, so a flagged call carrying one was answered here and raised upstream on every interpreter but the newest. The compiler refuses it below 3.14 now, reading the same version number as the new rule that fails the build when the interpreter is newer than the versions those rules were measured against.

The other thread is a route that was taken back out. The streaming join's byte key packing was wired into whole frame joins behind a threshold, and the measurement said the concatenating route it was meant to replace is faster on every shape that was tried, because its copy is parallel and the packing route's is not. The threshold is gone and the measurement is written into the file in its place, so the next person to have the idea reads the numbers before writing the code.

Changed: the join's two compound key packings now have the measurement that says which one a whole frame join uses

The streaming join packs a key tuple into one byte string per row, because it holds the build side whole and the probe side a chunk at a time and cannot make a plan that both sides agree on. A whole frame join has both sides, so it uses _pair_plan to pack the tuple into a single integer, and when that declines it concatenates every key column with its opposite number and factorizes the lot. The obvious follow-up to the streaming work was to give the whole frame join the byte packing as well, for the tuples the integer packing declines. That is the thing this entry is about not doing.

The byte packing was wired into align_keys behind a build side share threshold, the way the text key route is, and then measured on an i9-13900K at ten million probe rows, three sessions a side in ABBA order, against the concatenating route. It lost on every lopsided shape and by a lot: on a pair of int64 keys shifted too far apart to share a uint32, 322.7 ms against 63.7 at a build side of eight thousand rows and 335.6 against 77.1 at a hundred thousand. On a pair with the first key written as text, which was expected to be the byte packing's best case, 482.2 ms against 55.6 and 507.3 against 65.1. Every run of one side sits outside the range of the other. The two rows with a build side as tall as the probe side are the only ones that are close, 960.2 against 951.4 and 1.342 s against 1.430, and their runs interleave.

The reason is that the concatenating route is not the naive thing its name suggests. Its copy is a parallel memcpy and costs almost nothing, and what it hands the copy to is group_ordinals, which has its own tuple handling: an integer pair no table can be laid over still gets one fused hash of the whole tuple in a single parallel pass, and a tuple with a string in it gets a factorize a key and a parallel fold. Packing to bytes writes a byte string a row on each side in a serial pass and then hashes and compares those strings, which is more bytes touched and less of it spread across cores.

So the route was taken back out and the measurement written into firepanda/join/keys.mojo in its place, with the reason it loses and the one condition under which it would be worth asking again. Six benchmark rows stay behind: join/two_keys_far_apart_100k and join/two_keys_far_apart_equal_sides complete the far apart pair's ladder, and join/two_keys_text, join/two_keys_text_100k and join/two_keys_text_equal_sides are the same three rungs with the first key written as text, which is the other way a tuple leaves the integer packing and had no row at all. Issue #372.

Two tests came out of it that are worth keeping on the route that ships. A compound key with a text part had no test in tests/test_join_keys.mojo, and the null and two dtype cases now say which route answers them rather than only that the answer is right.

Added: the next release of Python is a red light on purpose

The regular expression compiler copies CPython's re, and re is not the same module in every version of Python this project supports. Two of its rules have already moved inside that range, and each one is written down in the compiler as a version number the compiler compares the interpreter against. A number like that fails quietly. When the next release moves a third rule nothing raises, the library goes on answering with the rules of whatever version was current when somebody last measured, and the wrong answers are ordinary looking columns.

So tools/python_version.py reads the constants out of the compiler and the supported floor out of pixi.toml and fails when the interpreter it is standing in is newer than the newest one anybody has measured. The message says what to do about it, which is to run the corpus sweep across versions, write down what moved, add a constant for each rule that did, and raise the number.

It also refuses a constant above the newest measured version, which is a rule nobody could have measured and so a typo or a guess, and a constant at or below the floor, which is how these are meant to leave. When the floor rises past a threshold every supported interpreter is already above it, the branch behind it can never run, and the constant and its branch and its tests and its paragraphs are all dead with nothing anywhere to say so.

It runs twice, as a pixi task in CI and again inside the accessor test suite, because those two stand in different interpreters and either can be upgraded without the other. That gap is the one that produced the first of these two rules. Document 92.

Changed: contains, match and fullmatch read a column through the state cache

The matching kernel builds a cache beside the machine and asks the cache for every row. A pattern the cache refuses never reaches it and the whole column runs on the machine as before, and a row the cache gives up on runs on the machine on its own, so the column comes back the same either way and the fall back costs one branch per row. That is the shape the cache was written for: it is an accelerator with an engine underneath it rather than a second engine callers have to pick between.

On a million URLs, contains with an anchored pattern of the shape ClickBench q28 uses goes from about 870 ms to about 120 ms, and [a-z]+[0-9]+[a-z]+, which the character set skip cannot help at all because almost every row starts with a letter, goes from about 2.7 s to about 180 ms. A pattern matching most rows goes from about 330 ms to about 160 ms and one matching none from about 275 ms to about 200 ms, both of those being rows the skip added in 0.8.11 was already stepping over quickly.

The alphabet is not free and the compiler is not the one who knows whether it is worth it. Working it out costs a few microseconds on an RE2 compile and up to about three hundred on a Python engine compile with Unicode classes in it, against something between seventy nanoseconds and a microsecond of work per row, so the accessor asks for it when the column has at least four thousand rows and not below that. The number is a named constant next to the call, since the only thing that could move it is a measurement.

Only the three methods that answer whether a row matched are wired up. count still runs the machine for every row because it needs where each match ended rather than whether the row matched at all, and a state here is a set of positions with no record of which of them were ever the end of anything. replace and extract need the same thing and more of it, and are named in #863 as a different piece of work.

The test that ran the kernel against a scalar loop over the same rows was a narrow check before this, since both sides ran the machine. It compiles with the alphabet now, so the two sides are two engines and the comparison is worth what it looks like. The match differential does the same: thirty thousand generated patterns over sixteen texts for each of the three methods now go through both engines, with a disagreement between the two reported on its own line because pandas has no view on which of them is wrong. Five seeds of that report full agreement with pandas and between the engines.

Added: a cache of the sets of positions the regular expression machine holds

The machine holds every position a pattern could be in at once and walks the whole set for every character it reads, and it works that set out again at every position of every row. A column of a million rows over a program of forty instructions asks the same question about the same set an enormous number of times, so there is now a cache that answers it once. A state is one of those sets, a transition is a state and one character giving the next state, and both are built the first time they are reached rather than up front, which is the only way to have them at all for a pattern with more states than anyone would want to enumerate.

The alphabet added last release is what makes a row of transitions small enough to hold. It is one number per class of characters the program cannot tell apart rather than one per code point, so a state for abc is four numbers wide rather than a million, and finding which one a character is in is an array index for ASCII and the same kind of search the range tables already use above it.

The cache stops at two hundred and fifty six states and says so. A caller that gets that answer runs the machine for that row and gets the same answer more slowly, which is the whole of the fall back and is why this can never be the only engine. Two shapes of pattern are refused before any row is read rather than part way through one. A program compiled without an alphabet is refused because there is nothing to lay the transitions out on, and a program holding a word boundary, a multiline ^ or $, or Python's $ that also matches in front of a newline ending the row is refused because all of those read the character on the other side of a position and a state here knows only whether it is at the start of the row or the end of it. RE2 answers those by folding the neighbouring character into the state, which is a real design and a larger one than this.

The end of the row is a flag on a state rather than a column in the table. Each state is built twice, once asking what it reaches with the end of the row asserted and once without, and the first answer is kept as a bool. That is a second walk per state, which happens once per state ever rather than once per row.

Over two hundred thousand URLs read three times, with the decode taken off both sides, the cache is worth about eleven times the run on an anchored pattern of the shape ClickBench q28 uses and about twenty two times on an unanchored one whose first character set stops nothing. On a pattern that matches most rows it is a bit over twice, and on one that matches none it is about one and a half, since the character set added in 0.8.11 already steps over most of those rows. The machine and the cache now share one definition of what an instruction accepts, because two functions that looked alike would be two engines answering two different patterns the first time one of them was edited.

The scan that runs it for three of the accessor methods is the entry above, and issue #863 has the order the rest go in.

Fixed: \z is refused beside an interpreter that has no such escape

Series.str.contains("a\\z", flags=re.MULTILINE) answered a column whatever Python was running. RE2 spells the end of the string \z, Python spells the same position \Z and read \z as a bad escape \z until 3.14, which added it, so a flagged call goes to Python's engine and upstream raises there on every interpreter this project supports except the newest. The parse now records whether the caller wrote one and the compiler refuses it below 3.14, beside the version rule added above and reading the same number. Issue #8 M6.

The same pattern with no flags beside it still answers, on every interpreter, because the call goes to Arrow and RE2 has always had the spelling. That is upstream's answer as well, and it means a keyword argument that says nothing about escapes decides whether a pattern is an error.

\Z is unchanged and legal everywhere, and [\z] is a bad escape in every version including 3.14, since 3.14 added an anchor and a character class holds characters.

Found on the way: this library was writing \A( and )\z around a pattern it builds for Python's engine, which is RE2's spelling in a Python dialect. It never gave a wrong answer, because this library's own parser reads both spellings and the pattern is never handed to a real interpreter, and it was still wrong. The anchoring writes \Z now, which is the same position and is legal in every version, so the only \z in a pattern reaching the compiler by that route is one the caller wrote.

Added: a compiled pattern can say which characters it cannot tell apart

The alphabet a regular expression runs over is a million code points and a machine that remembers what it did needs a table as wide as the alphabet, so something has to make the alphabet small first. A class is a set of characters one program answers identically about: abc has four of them, the a, the b, the c and everything else, wherever in the code points that everything else happens to be. compile_program works them out when it is asked to and writes them on the program, as one entry per ASCII character and a searched table for the rest, which is the shape a column of text wants.

The questions a program asks are the character instructions, with a negated class asking the same question as the class it negates, since what the alphabet needs is which characters are told apart rather than what is done with the answer. A full stop asks about the newline and so does a ^ or a $ that reads a line ending. A word boundary asks about the word class, which is the one that would be easy to leave out: a boundary reads the characters around a position rather than the one at it, and a table built from the character instructions alone would put a letter and a space in one class and answer \bfoo wrongly. RE2 asks it against ASCII and Python against every letter there is, so the same pattern has a different alphabet on the two engines.

Nothing reads the table yet, so nothing builds one. It is off unless a caller asks, because building it costs several times what compiling a short pattern costs and a millisecond or two for a pattern holding a Unicode class, and a table nobody reads is not worth that. What will read it is the lazy DFA in issue #863, which is what this is the first piece of.

The test that matters is the property the whole thing rests on, asked of every pair of a hundred and thirty two characters against five patterns: two characters in one class answer every instruction of the program alike, and two in different classes are told apart by at least one of them. The second half is what makes the count as small as it can be rather than merely small.