It might not be possible to do it with an interpreter, but a well-designed JIT should be able to shift the cost of calculating instruction scheduling and cycle-costs from execution time to JIT time.
Since OoO CPUs spend long stretches of time between branch miss-predicts and L1 cache misses, you can get long sequence of instructions that executing with the exact same timings every time. A tracing JIT is perfect for this usecase. You just need to normalise the pipeline state on entry (and this since this normally happens after a miss-predict, the pipeline is often drained), and then exit on every branch miss-predict or L1 cache miss and start a new trace.
I suspect such a scheme might be fast enough for a Pentium III, I just need to find some time to actually try out my ideas at some point.
https://dl.acm.org/doi/10.1145/384265.291063
It’ll help, but still won’t get you down to the 10-20x cycle overhead range that you need to claim success.
You a right, they get a 190-360x overhead, and on today's CPUs, I think I need need to get it down to about 20-30x overhead to get realtime on current CPUs. It's only off by a single order of magnitude.
Though, it would be fast enough for some usecases. 10% of realtime would be bearable for some TAS usecases.
It might be possible for me to improve on what they have. For starters, they aren't using a trace-based approach and I think they are applying the memorisation on every single branch, correctly predicted or not, and every single memory access (even when they hit L1). But I would need a 10x improvement over what they had, and that's a big ask.
gem5 is a simulator that aims to do precisely all that, and yes it is extremely slow. Probably on the order of 100x slower, but I don't have timings to hand.
Similarly booting a small processor compiled into C++ with verilator is very taxing on the processor too.