What we measured and what we found

This chapter is not about Oberon as such but about what can be learnt when a whole system fits on a desk: the sources, the compiler, the processor's description, and a way to run and measure all of it.

What an array bounds check costs

An old question, usually settled at the level of opinion. Here it can be closed with a number.

The Oberon code generator inserts two instructions before every index operation with a variable subscript: a comparison and a conditional branch. In ORG.Mod this is switched by a single constant, check. So three compilers can be built — without checks, with software checks, and with a hardware instruction — and the same workload run through each.

The subtlety that usually makes such measurements lie: a compiler without checks not only does not contain them, it also does not emit them. The difference then is not "the cost of executing checks" but a mixture of two different things. So at a second stage all three compilers are built from one and the same reference source — then the code they emit is bit-identical and only what is inside them differs.

The result, building five modules of the system:

Two conclusions. First: a bounds check costs about two per cent, not the tens of per cent commonly assumed. Second: hardware support removes only about a sixth of that cost (15.5%), because the check itself is two cheap instructions rather than work with memory.

The same 2.19% was obtained independently, by decomposing four builds in a two-by-two arrangement. Two different methods gave one number.

That number belongs to one workload. What a check costs in your loop depends on how much other work the loop does: the hardware saves exactly one instruction and one cycle per indexing, and the rest decides the share. In lab 12 you measure it on your own module: build it with the stock compiler, then with a compiler that knows the hardware instruction, and compare the time from Kernel.Time. The machine's timer counts cycles (25,000 per millisecond), so a repeat gives the same number to the millisecond.

The hardware check: where to fit it

Measuring the third row meant adding an instruction to the processor. That is instructive in itself.

RISC5 has no free opcodes — all sixteen operations are taken. A crack was found: format F0, v=1, op=1. That is an alias of left shift which the compiler never emits, because for shifts it always sets v=0. We did not assume those bits were free; we checked by sweeping every value of the field through the real decoder.

The limit had to be cut into two pieces — bits 27–24 and 15–8 — because no contiguous twelve-bit field exists. The decision was made from data: a dynamic profile showed that 68.3% of executed checks are on arrays of length 256…1023, which eight bits cannot cover. And the familiar figure "the median array length is 32" turned out to be an artefact: that is ARRAY 32 OF CHAR, the file-name type, which appears in declarations often and executes in hot code almost never.

The cost in silicon: from 46 to 123 square microns on the Nangate45 library, that is from 58 to 154 gate equivalents. The lower bound lies inside the noise of the synthesis route, which is to say indistinguishable from zero. On frequency the sign of the effect could not be determined honestly: different routes give it different signs.

Three parts of Project Oberon disagree with each other

The most unexpected finding. The width of the displacement field in a branch instruction:

Three parts of one system, written by one person, disagree about the width of one field. There are no practical consequences: the address space is one megabyte, eighteen bits in words, and nothing reaches the disputed bits. All three agree where it matters.

The condition table in the disassembler ORTool.Mod, on the other hand, is simply wrong: eleven of sixteen indices are filled in and two of them contradict the hardware — where the processor tests carry, the disassembler prints "lower or same". This is checked by execution: take the layout from ORTool and four of a hundred and twelve conditional-branch checks fail on the hardware.

The moral is the one from the previous chapter: the hardware is right, not the documentation and not the tools.

How exactly timing can be predicted

RISC5 has no cache, no branch prediction, no out-of-order execution. Execution time should therefore follow from a table.

We wrote such a table and checked it against twelve million real instructions during boot: not one divergence. This is a property modern processors do not have and will not have, and the reason machines like this are still used for real-time work.

What all of it is verified by

For the numbers to be believable, the instrumentation is verified separately:

• step for step against an independent emulator — 14.6 million instructions, comparing all registers, flags, the H register and the whole of memory;
• decoder equivalence — 20,480 encoding combinations run through two variants of the core, and exactly one diverges: the one we added;
• a round trip on the compiler's real output — 33,838 words of code are taken apart by the disassembler and put back together, requiring a bit-exact match;
• a semantic differential — 4,650 checks: an independently written model of the arithmetic is compared against the hardware on the result, all four flags and the H register.

And above all of it, a rule we arrived at the hard way: every check must be tried by breaking. We break the model, break the tables, break the encodings — and watch whether it turns red. Three times during this work a check proved green on a broken input, and each time that mattered more than the check itself.