Faster Integer Reading and Printing in SBCL

The first thing is of course to profile:

Reading an 18-digit integer with read-from-string takes ~190 ns, while parse-integer turns the same 18 digits into a number in 40 ns. So obviously, building an integer is already fast and takes just a fifth of the overal time. Most of the time seem to go to finding the token: for every character, a call through the stream, a readtable lookup, a copy into a buffer and a step of a state machine. So a faster digit conversion, with SWAR or SIMD, could gain at most that fifth. The scan itself had to get cheaper.

Implemented idea is a fast path at the start of read-token. When the reader reads from a string, which is what read-from-string and with-input-from-string do, it looks directly at the string for something of the form [sign] digits [. digits] [marker [sign] digits] followed by a delimiter. If it finds an integer of up to 18 digits, it returns it; if it finds a float, it converts it with Eisel-Lemire from the float work. For anything else it gives up and the reader does exactly what it did before.

This is safe due to two properties. For the first, if the fast path gives up, the stream has not moved: it never calls read-char, it only looks at the string and moves the stream's position once, on success. And it asks the current readtable about every character, so a modified readtable gives the same result as the normal reader. If you make 5 a whitespace character, "15" reads as 1 in both.

Reading an 18-digit integer went from 190 to 85 ns, 2.2 times faster, and short integers from 85 to 60 ns. Floats, which already had Eisel-Lemire, got another 1.5-2 times on top: the coordinates in canada.txt now read in 93 ns each, against 315 ns in plain SBCL. When the fast path gives up, for a symbol like 123abc, it costs at most 40-50 ns, and nothing for symbols that start with a letter.

Printing an 18-digit integer spent two thirds of its time in a loop that divides by the base once per digit. The base is a variable there, so every division is a real hardware divide, one of the slowest instructions a CPU has.

For base 10 the new code splits the number into top * 10^16 + hi * 10^8 + lo. Dividing by a constant compiles to a multiplication. Then it writes hi and lo as 16 digits at once with the SSE2 routine from zmij, which the float work already had, and uses its mask of nonzero digits to skip leading zeros.

Short integers print as fast as before, they only needed a few divisions anyway. I tried the same trick for bignums and dropped it: SBCL already compiles its bignum printing separately for base 10, with the divisions turned into multiplications. My version was slower :(.

Testing the printer found a bug in SBCL: (let ((*print-base* 2)) (prin1-to-string most-negative-fixnum)) signalled an internal error. The size estimate for the result string was one bit short for exactly that one number. The fix is now upstream.

parse-integer looked like an obvious target: it tests the string's type before reading every character, and it checks every character for digits of all scripts. Compiling its body once per string type helped sb-ext:parse-float a little, so I measured the same on parse-integer. It made nothing faster for the strings people actually parse, and some cases slower: parse-integer already compiles its digit check inline and reads 18 digits in 10-16 ns. So I dropped that idea too, and nothing is changed there.

That experiment also taught me something about measuring. I first compiled the old and new versions side by side at run time, in one image, and those copies did not behave like the code in the built SBCL. The first time they made the change look much better than it was (in my favour), because they were compiled without a declaim declaration the real file in SBCL has, so digit-char-p didn't get inlined properly in the un-patched versions. Only two real SBCL builds, one with the change and one without, built in separate worktrees and run alternately, gave more realistic numbers. The kind of string matters too: format nil and prin1-to-string return base strings for ASCII text, read-line returns character strings, and the two can perform quite differently.

Together with the float work, on everyday data:

The pattern is the same everywhere: where the number conversion itself is the bottleneck, as in printing floats, the gains are large; where the surrounding machinery dominates, the reader, streams, format's directive handling, they are smaller. What is left now is mostly that machinery.

As before, everything produces exactly the same output and reads exactly the same values as the old code, and the tests that check it are in the repository.

There is definitely room for improvements left:

The reader's fast path only works on strings, because it needs to look ahead in the buffer. A file stream has a buffer too, so reading numbers from files could get the same treatment.

Finding tokens with SIMD: The token scan could find delimiters 16 or 32 characters at a time, for symbols and strings as well as numbers.

The integer part of the reader's fast path does not need Eisel-Lemire, so it could go upstream on its own.

Hexadecimal floats in style of C99 could be useful; neither the reader nor parse-float supports.

Smaller things like writing prin1-to-string's integer result directly into its string, a few nanoseconds; format calls with more than one directive; 32-bit versions of zmij and Eisel-Lemire; and one shared table of powers of ten for the printer and the reader.