The bytecode optimiser works on individual instructions. I'm trying something a little more greedy now. What if Pipit recognises a whole loop and hands its work to a compiled function?
I'd like to keep writing this ordinary Go:
sum := 0.0
for i := 0; i < len(values); i++ {
sum += values[i]
}
The ordinary route repeatedly dispatches instructions for the index, comparison, load and addition. A recogniser can spot the sum during compilation and replace that loop with a specialised bytecode operation. Its handler gives the work to a kernel, a compiled routine for that numerical job.
It feels a bit like cheating.
I'm building an interpreter and now I'm trying to arrange for it not to interpret the loop. (Possibly some benchmarkmaxxing, but it looks like a fun exercise.)
There are two things to gain here. One kernel dispatch can replace many trips round the interpreter and SIMD can let one machine instruction operate on several values inside the kernel. Fewer interpreter steps, more parallel arithmetic. Those are separate savings and both interest me.
Four patterns to start with
I'm keeping this to float64 sums, dot products, elementwise addition and scaling. Pipit still lives inside Piko and anything outside those patterns keeps the ordinary bytecode route. I'd like to write the ordinary Go loop, sum these values, multiply those pairs, and leave Pipit to choose a kernel without putting its name in my program.
A dot product multiplies corresponding elements of two arrays and adds the products. It is another small loop to recognise. Multiply a pair, add the product, move on.
Follow what each iteration reads
Recognising those few patterns seems manageable. Keeping the program's behaviour is the part that needs more attention. I'll start with the memory the loop reads.
Here is an addition loop whose source and destination share an array:
values := []float64{1, 2, 3, 4}
src, dst := values[:3], values[1:]
other := []float64{10, 10, 10}
for i := 0; i < len(src); i++ {
dst[i] = src[i] + other[i]
}
The first iteration reads 1 and writes 11 into the next position, so the second reads that newly written 11 and writes 21. The third reads 21 and writes 31.
Forward execution leaves [1, 11, 21, 31]. If a replacement reads the original source values before doing the writes, it gets [1, 11, 12, 13] instead:
| Iteration | Forward loop reads | Reading the original input gives |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 11 | 2 |
| 2 | 21 | 3 |
Each addition still works. What changed? The values reaching it. I can recognise the addition perfectly and still hand it the wrong numbers because the source loop reads its earlier writes while the replacement reads the old input. Different names don't help me here. src and dst share an array and a write lands exactly where the next read will look. I need the actual storage ranges before choosing how to process them.
The overlapping slices give me a dependency through memory. A sum has another one, even when nobody writes to its input. Each iteration needs the previous accumulator. Combining many values into one is a reduction, and I have to preserve that running history too.
Start the accumulator at a nonzero value:
values := []float64{-1e16, 1}
sum := 1e16
for i := 0; i < len(values); i++ {
sum += values[i]
}
The source cancels 1e16 with -1e16, leaving zero. Adding the final unit produces 1.
Sum the slice, then add the starting value, or seed. It's a tempting shortcut at the interface, because the kernel wouldn't need to take that seed at all.
Suppose the specialised path does that. At the magnitude of -1e16, a float64 can't retain that extra unit in this addition. The separate reduction rounds back to -1e16. Adding the seed produces 0:
| Route | First useful addition | Final result |
|---|---|---|
| Source accumulator | 1e16 + -1e16 becomes zero | 1 |
| Reduce, then add seed | -1e16 + 1 rounds to -1e16 | 0 |
The seed has moved in the calculation. That alone breaks agreement with the source loop before I choose how many values each vector instruction handles. A sum has acquired a different answer without acquiring any different numbers. Floating-point arithmetic is very economical with its surprises.
Starting at zero doesn't settle the order
I could make the recogniser accept only a zero seed and feel much happier about it, but after removing the seed movement I'd still have to ask how the replacement groups its additions.
Three familiar decimal fractions are enough:
values := []float64{0.1, 0.2, 0.3}
Accumulating from zero in source order produces these successive values:
0.1 → 0.30000000000000004 → 0.6000000000000001
Now add the last two values before adding the first:
0.1 + (0.2 + 0.3)
0.1 + 0.5 = 0.6
Go's float64 is a 64-bit float and these decimal fractions don't fit exactly, so each addition rounds its result. One order finishes at 0.6000000000000001 while the other gives the value printed as 0.6. Close enough? That would be a different contract from preserving the result of the loop I'm replacing.
This is reassociation, changing how the operations are grouped. Whatever the seed, I still have to follow how the kernel combines its intermediate totals at the other end, and saying SIMD just hands that question straight back to me.
These examples change what I'm asking the recogniser to do. A familiar loop body gets me a candidate, but before calling a kernel I have to check the memory relationships and the sequence of arithmetic that its replacement will use.
A runtime overlap check can select forward, one-element-at-a-time execution when needed, giving the fast path a way to decline this particular input after compilation. LLVM's vectoriser documentation describes checking memory overlap at runtime and falling back to a scalar loop. I can inspect the storage ranges when they exist rather than rule out the loop because I can't establish them earlier.
The bounds and updates belong to that decision too. A short second slice must still produce the required bounds failure. An index declared outside the loop can be read afterwards, so its final value belongs to the behaviour being replaced.
That overlap check can select forward execution for one input, but changing the addition order needs its own decision about what the language permits, and a read-only slice doesn't settle it. Restricting the recognised patterns helps me follow those decisions, even if four short loops turn out to hide a surprising number of them.
The loop I still need to measure
A dense layer in a neural network multiplies the input values by each output's weights and sums the products, so its dot products give me a useful comparison with inner loops that match one of these patterns. I can run it with recognition on and off, check the results and record whether the kernel actually ran before putting a time beside the change.
The SIMD library began with float32 embedding and similarity work. Adding float64 kernels gave this experiment somewhere to send the loops. Another sum syntax? No thanks. I like being able to bring that work into the interpreter without inventing another way to write one.
For now, the part that keeps me interested is how much work can disappear behind an ordinary Go loop. Does handing over the whole job buy more than improving its individual instructions? These four patterns give me something small enough to try that with, and enough memory relationships, bounds checks and arithmetic choices to keep me occupied before I get near the stopwatch.