3 ms·
One surprising thing that I discovered recently is that after Haswell, Intel processors got much much better at predicting "interpreter loops", which are basica
by ufo 9y ago
One surprising thing that I discovered recently is that after Haswell, Intel processors got much much better at predicting "interpreter loops", which are basically a while true loop with a very large seemingly unpredictable switch statement. It lead to a dramatic improvement in micro benchmarks and made some traditional optimizations involving computed goto and " indirect threading" obsolete.
Does anyone know how it achieved this?
- fulafel 9y agoIt doesn't look like a series of comparisons from the CPU point of view. Normally switch statements are compiled like a series of "if" statements, but the interpreter loop style switch gets compiled into a table of jump targets that is indexed by bytecode. Same kind of indirect branch prediction features that were previously designed to help C++ "virtual" functions help here - a branch target buffer, etc. The VM interpreter loop is mostly a main bottleneck in languages that have rather low-level VM instructions and data types. In high level VMs the dispatch on operand type is the main bottleneck. This too benefits from indirect branch prediction.
- deepnotderp 9y agoLonger switches are usually compiled into binary search trees.
- fulafel 9y agoIt depends on whether the switched-on values are sparse. Contiguous ranges of bytecodes are more efficiently compiled to straight jump tables (and enable indirect branch prediction mechanisms in CPUs to work). For another boost to leveraging indirect branch prediction, threaded code is still a little better since each VM instruction has a unique jump call site: http://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables http://eli.thegreenplace.net/2012/07/12/computed-goto-for-ef...
- ufo 9y agoThat blog post is from 2012. What I observed is that with the more recent processors threaded code doesn't make much of a difference.
- deepnotderp 9y agoperhaps they have a dedicated loop length predictor? Iirc, loop exits account for a majority of branch mispredicts nowadays, so it makes sense.
- ufo 9y agoIt must have been something else. I was talking about VM loops, which never exit.
- deepnotderp 9y agoAh , maybe they have a dedicated inner predictor?
- to3m 9y agohttps://hal.inria.fr/hal-01100647 https://hal.inria.fr/hal-01100647 suggests it might use an improved version of the TAGE scheme referred to in the article.