Re: Opcode handler dispatch in an interpreter: Implementing switch on OpCode.

George Neuner <gneuner2@comcast.net> writes:
>Unfortunately, on modern CPUs, *all* branches are predicted. An
>indirect jump through the table will mispredict virtually every time.
>The same will be true of an indirect jump via register based address.


No. Since the Pentium, we have had indirect branch predictors. For
the early BTB-based indirect branch predictors, you get about 50%-60%
mispredictions in a virtual machine (VM) interpreter if you have a
separate dispatch per VM instructions (and approximately 100%
mispredictions if you have a shared dispatch routine). See
<https://www.jilp.org/vol5/v5paper12.pdf>.


In the meantime at least Intel (and probably others) have improved
indirect branch prediction, giving much better results. The paper
"Branch Prediction and the Performance of Interpreters - Don't Trust
Folklore" even concluded that branch mispredictions are no longer a
performance issue for interpreters; my own tests
<2015Aug11.090812@mips.complang.tuwien.ac.at>
<2015Sep7.142507@mips.complang.tuwien.ac.at> did not confirm this
conclusion, but still, the branch prediction has been improved by a
lot.


>The best you can do with an interpreter is to have all the code in L1
>code cache. As soon as you have to go to L2 (which typically is
>shared between code and data) or deeper, you risk taking large hits if
>the code is not resident.


That's the case for any code and any data. And yet we found that an
optimization that expands code size by a lot (far out of L1 size)
<http://www.complang.tuwien.ac.at/papers/ertl%26gregg03.ps.gz> gives a
very good speedup by reducing the number of mispredictions. The
postings referenced above show that this optimization is still useful
even with Haswell's indirect branch predictor (I have not repeated the
measurements on Skylake or Zen, but what I have seen on these
processors indicates that the optimization still provides a speedup).
So, no, the best you can do is not to have all the code in the L1
cache; other considerations also play a role, and caches usually also
work if the code/data is larger than the cache. A simple heuristic
like you propose enough is not good enough. You have to try it out
and measure.


David Gregg and I once tried out whether it would be beneficial to
have smaller dynamic superinstructions (by splitting long dynamic
superinstructions in several parts) that could be shared between more
uses, resulting in lower code size while still giving most of the
indirect branch prediction benefit. We found that the code was
smaller, but the result had more I-cache misses then dynamic
superinstructions; we explained that by having worse spatial locality:
If a long dynamic superinstruction occupies one cache line, and is
split in two parts that reside in different parts of the code space,
now at least 2 cache lines need to be resident to execute the same
code. We did not publish that work.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

Return to the comp.compilers page.
Search the comp.compilers archives again.