I believe the thing we are optimizing for here is the size of the output assembly code, not the execution speed.
By precomputing approximations and local adjustment offsets, you store the offsets as int8_t rather than the int16_t required for larger absolute offsets from the 0 position. With large enough lookup tables, it compounds to something that might be significant.
This also reminds me of a classic assembly programming trick. Suppose you have a byte i and each value needs a separate case handler. Suppose all but 10 of the cases can be implemented in at most 32 bytes of inline machine code. Instead of using a jump table you dispatch to the address case0 + i<<5. The 10 cases that need more than 32 bytes use their 32-byte allowance to include a branch to a basic block outside the dense 256 * 32 byte range. It's nice (but not necessary) if those out-of-line branch targets correspond to natural subcases you need to handle anyway. It's even nicer if you put the cold subcases out of line.
Yeah. You can do a reasonably portable version of this in C by putting the case handler functions in a custom linker section, e.g. __attribute__((section(".text.ops"), aligned(64), used, noinline, no_reorder)) with gcc. Even better if you can use musttail and preserve_none. At runtime init you verify the placement as a final safeguard.
vbernat | a day ago
A benchmark would be nice to understand how the last solution is better. But maybe the author wanted very large tables?
karlyeurl | a day ago
I believe the thing we are optimizing for here is the size of the output assembly code, not the execution speed.
By precomputing approximations and local adjustment offsets, you store the offsets as int8_t rather than the int16_t required for larger absolute offsets from the 0 position. With large enough lookup tables, it compounds to something that might be significant.
pervognsen | a day ago
This also reminds me of a classic assembly programming trick. Suppose you have a byte i and each value needs a separate case handler. Suppose all but 10 of the cases can be implemented in at most 32 bytes of inline machine code. Instead of using a jump table you dispatch to the address case0 + i<<5. The 10 cases that need more than 32 bytes use their 32-byte allowance to include a branch to a basic block outside the dense 256 * 32 byte range. It's nice (but not necessary) if those out-of-line branch targets correspond to natural subcases you need to handle anyway. It's even nicer if you put the cold subcases out of line.
wareya | a day ago
This trick is still alive in indirect threaded interpreters! It saves a memory read while keeping bytecode small.
pervognsen | a day ago
Yeah. You can do a reasonably portable version of this in C by putting the case handler functions in a custom linker section, e.g. __attribute__((section(".text.ops"), aligned(64), used, noinline, no_reorder)) with gcc. Even better if you can use musttail and preserve_none. At runtime init you verify the placement as a final safeguard.