You may feel this one deeply if you ever play around with something like a brainfuck interpreter in a program search context.
Even for relatively long programs with high cycle counts, linearly scanning for matching jump instructions tends to be faster than precomputing a jump table. The cost of building the optimized data structure is massively outweighed by the ephemeral nature of its use in this context.
There is a point where the lookup table is faster (even for single use programs), but at this point the entire experiment is probably iterating so slowly as to be useless on timescales the experimenter cares about. We find other tricks to keep the linear scan effective. E.g., subdivide one large program into modules. You'd be amazed at the emergence you get from modules as small as 16 instructions, assuming some kind of shared memory. Using a dictionary to jump across 15 bytes is pretty comical.
bob1029•25m ago
Even for relatively long programs with high cycle counts, linearly scanning for matching jump instructions tends to be faster than precomputing a jump table. The cost of building the optimized data structure is massively outweighed by the ephemeral nature of its use in this context.
There is a point where the lookup table is faster (even for single use programs), but at this point the entire experiment is probably iterating so slowly as to be useless on timescales the experimenter cares about. We find other tricks to keep the linear scan effective. E.g., subdivide one large program into modules. You'd be amazed at the emergence you get from modules as small as 16 instructions, assuming some kind of shared memory. Using a dictionary to jump across 15 bytes is pretty comical.