10 ms·

Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

97 points by nkurz 11y ago

bch 11y ago
Would an editor kindly put a note in the OP link that this is a pdf?
acqq 11y ago
If my coworker would come to me and show me his results where he measured that the "Labels as Values" implementation is not need while "on his Haswell CPU the speedup is only 3%" I'd just ask "can it be guaranteed that the code you propose to revert to the plain switch will run only on that CPU?" If not and the switch is in the performance sensitive place I'd keep the "Labels as Values" implementation. There are many more CPUs in the world than "the latest Intel x86 CPU." Kudos for the developers of Haswell, but don't blindly trust the Inria researchers that tell you "Don’t Trust Folklore." I also don't like that this research was "partially supported" by the European grant thus explained: "ERC Advanced Grants allow exceptional established research leaders of any nationality and any age to pursue ground-breaking, high-risk projects that open new directions in their respective research fields or other domains." (1) 1) http://erc.europa.eu/advanced-grants http://erc.europa.eu/advanced-grants Is ground-breaking, high-risk research discovering that the algorithm in the latest Intel processor matches the one other researchers (which I respect much more) discovered in 2006, and variant of which won more "branch prediction championships"? I'd say no. At least they honestly write about the fact that the given algorithm is already known as highly efficient.
- vardump 11y ago
  While I somewhat agree with you, the real answer is assume nothing and profile. Always. But there's a catch. Things are getting a bit out of hand, there are just too many architectures and configurations. I think modern consumer-oriented code should run at least well on Intel Nehalem - Skylake, AMD K10 - K12, ARM Cortex A7/A8/A9/A15/A53/A57/A72, Qualcomm Krait/Kryo. Focus on 64-bit, but some attention should still be paid to 32-bit performance. Number of actual targets is even worse, because cache and memory architecture vary so much. At least all those have 64-byte cache lines. In high performance code, there's often the choice between memory and compute load balancing. What memory access patterns and layouts you're going to use - where do you want your bottlenecks? You can often reduce bandwidth requirements by computing more and vice versa. Take Sandy Bridge for example: While L1 and L2 cache sizes are fixed on Sandy Bridge, L3 cache varies between 1 - 20 MB. Clock speeds vary between 1.0 to 3.6 GHz. There are 1-4 memory channels, I believe they're usually arranged 64 byte granularity round robin. Say your access pattern is access every second 64-byte cache line vs. access every line. On 1 and 3 channel systems, both perform about same. When skipping 64 byte cache line on 2 channel system, effective memory bandwidth is equal to just 1 channel system. 4 channel system will behave like 2 channel one. The code might be bandwidth bottlenecked on 1-2 channel system and compute bound on 3-4 channel system. Then you're going to hit DRAM page miss every... 1-8 kB? System dependant, of course. To make the best choice for Sandy Bridge based systems, among other things, you need to know number of memory channels + their arrangement, amount of L3 cache and clock speed. On some Sandy Bridge CPUs you have a lot of time to do complicated data packing and unpacking, trying to just keep memory bandwidth usage down. That was just one architecture. Now add all the other platforms in the mix. There are pretty many different instruction set extensions. If you don't use them properly, you can lose an order of magnitude of performance. I think we'll need runtime code generation in the future. On system JIT/AOT also for traditionally compiled languages, such as C and C++.
  - acqq 11y ago
    > the real answer is assume nothing and profile. They did profile, but what? Their "don't trust folklore" ("just 3% speedup") conclusion is valid only for one specific architecture and only for the most recent CPUs. As you say > modern consumer-oriented code should run at least well on Intel Nehalem - Skylake, AMD K10 - K12, ARM Cortex A7/A8/A9/A15/A53/A57/A72, Qualcomm Krait/Kryo. If I understand correctly, they themselves measure 30% speedup even only one generation before on Intel and they didn't measure any ARM or AMD. It looks to me that "don't trust folklore" claim was possible only by ignoring all the processors you name. And you are right, they also didn't show that they are aware of the differences inside of one generation (does the cheapest processor of the same generation behave the same?)
    - loup-vaillant 11y ago
      > Their "don't trust folklore" ("just 3% speedup") conclusion is valid only for one specific architecture and only for the most recent CPUs. For now. In 5 years from now, you can be sure most new architectures will have predictors that are as good. So, while it might be good to reach for the low hanging fruit (jump threading), heavier approaches such as super-instruction replication are probably no longer a good idea.
      - acqq 11y ago
        Writing the code in a way not to be dependent on the most advanced hardware solution in existence is better choice unless you target only the specific hardware or the solution is of the "use once then throw away" kind.
        loup-vaillant 11y ago
        That would be true, if we were speaking of using this optimization instead of that optimisation. We're not. Here, they're saying that in this particular architecture, a number of optimisations are effectively useless. They're saying that naive code is almost as fast. They're saying that some "optimizations" have even become counter-productive. The lesson I get from this? Unless I know a fair bit about the target platforms, the naive approach is better, because any performance model I have in mind might be invalidated anyway.
- shoo 11y ago
  > Is ground-breaking, high-risk research discovering that the algorithm in the latest Intel processor matches the one other researchers (which I respect much more) discovered in 2006, and variant of which won more "branch prediction championships"? I'd say no. That appears to be a pretty reasonable criticism of the process by which the grant was awarded. My somewhat unfair characterisation of this research from skim reading the abstract and conclusion is: "we point out that the understanding in the academic literature is lagging behind the understanding already built into systems that are sold commercially and are in operational use". edit: There's something slightly humorous in considering the grant-allocation process itself as some kind of optimisation problem: Problem (GA) : How do we best allocate resources to promote high-risk, ground-breaking research? ...and then observing that grant resources have been allocated to perform research on another piece of optimisation that already seems to have happened. I wonder if one could obtain an ERC Advanced Grant to study the effectiveness of the current process by which ERC Advanced Grants are awarded, and suggest improvements? It is plausible that such a study could be very valuable and yet not have much political support.
  - acqq 11y ago
    > understanding in the academic literature is lagging Even that were too much to claim as the "branch prediction championships" happened on an "academic" place: IEEE/ACM International Symposium on Microarchitecture http://www.jilp.org/cbp/ http://www.jilp.org/cbp/ http://www.microarch.org/micro37/ http://www.microarch.org/micro37/ also note the sponsors.
- paulfr 11y ago
  > the one other researchers (which I respect much more) discovered in 2006 You seem to be blissfully unaware that they're in fact the same researchers: André Seznec is a co-author of the paper. This paper is valuable in pointing out that ITTAGE branch prediction performance is a very good predictor of Haswell performance. Because the Haswell algorithm is secret, that should be very helpful to developers who still have to care about branch prediction. Interpreter developers shouldn't ignore pre-Haswell chips just yet, but if you were to, say, develop a new language your design decisions should be guided by where the puck will be rather than where it used to be.
  - acqq 11y ago
    > You seem to be blissfully unaware that they're in fact the same researchers: André Seznec is a co-author of the paper. He's the third signer of the current paper but the first of the 2006 one. It's the case of legitimizing the "research" which only confirms exactly what Intel recently implemented in a given CPU generation, even if the grant is for other goals ("ground-breaking, high-risk projects"). Or, to be clearer, I respect the deeds not the persons. I fully understand the need for Seznec to be able to claim that the algorithm is really used by Intel and that therefore he co-authored the last paper. But confirming that Intel used ITTAGE is "ground-breaking, high-risk"? No. And does that mean we should never use goto label in the tight loops? No.
    - paulfr 11y ago
      The grant is for the DAL project [1], which presumably fits the "ground-breaking, high-risk" label. In such a project, some tasks will be high-risk, some tasks will be low-risk. Quantifying the branch predictor of current processors may be a comparatively easy task, but that doesn't mean it's trivial, useless or outside the scope of the project, which is to improve sequential performance of microarchitectures. Knowing that real-world processors are performing just as well as previous academic research is helpful, because it suggests that there is no difficulty or unrealistic assumption that prevented manufacturers from doing so. Conveying that knowledge to the compiler and interpreter community is important too. [1] https://team.inria.fr/alf/members/andre-seznec/defying-amdahls-law-dal/ https://team.inria.fr/alf/members/andre-seznec/defying-amdah...
umanwizard 11y ago
tl;dr for those who don't want to read the paper in detail: * Interpreters are conceptually a big switch(bytecode) statement in an infinite loop. They use various tricks to make it easier for the processor to predict the target of the next indirect branch * This previously had a dramatic impact on performance, because branch mispredictions are very expensive and it was difficult for the processor to predict them accurately. * Recent Intel architectures have improved branch prediction, so the aforementioned tricks no longer have a very big impact (on Haswell x86 processors specifically)
- acqq 11y ago
  > various tricks They actually present (approximately) a very simple construct that is used to speed the interpreters up: void labels[] = { &&ADD, &&SUB . . . }; ... goto labels[ vpc++ ]; ADD: ... goto labels[ vpc++ ]; instead of ... switch ( *vpc++ ) { case ADD: .... break; case SUB: It's not really hard. The only problem is that the former is not a standard C and not present in MSVC. See http://stackoverflow.com/questions/6421433/address-of-labels-msvc http://stackoverflow.com/questions/6421433/address-of-labels... "Erlang does (that) for building on Windows. They use MSVC for most of the build, and then GCC for one file to make use of the labels-as-values extension. The resulting object code is then hacked to be made compatible with the MSVC linker." It obviously mattered enough for Erlang developers to use GCC even for just that critical piece of C code. It doesn't mean that it has to be regularly used in every code (not every switch is executed the way the main interpreter loop is).
- haberman 11y ago
  I'd be interested to see benchmark numbers for LuaJIT, which makes it extremely easy to compile with either replicated dispatch (each bytecode instruction footer has a separate dispatch "jmp" instruction) or common dispatch (each bytecode instruction jumps to a common dispatch "jmp" instruction): http://repo.or.cz/w/luajit-2.0.git/blob/a5b1c4d98eeb97a950774ae032f51f820dfbfc4c:/src/vm_x86.dasc#l299 http://repo.or.cz/w/luajit-2.0.git/blob/a5b1c4d98eeb97a95077... // Instruction footer. .if 1 // Replicated dispatch. Less unpredictable branches, but higher I-Cache use. .define ins_next, ins_NEXT .define ins_next_, ins_NEXT .else // Common dispatch. Lower I-Cache use, only one (very) unpredictable branch. // Affects only certain kinds of benchmarks (and only with -j off). // Around 10%-30% slower on Core2, a lot more slower on P4. .macro ins_next jmp ->ins_next .endmacro .macro ins_next_ ->ins_next: ins_NEXT .endmacro .endif
pg_is_a_butt 11y ago
why is the 1st page narrower than the others? oversight?
chrisdevereux 11y ago
Is there a reason that machine languages don't allow the programmer/compiler/runtime to explicitly control the CPU's cache & instruction pipeline? Presumably they have access to much better information about the code's intent and future behaviour than the cpu does.
- deleted 11y ago
  [deleted]
- sklogic 11y ago
  There are architectures that require manual pipeline control. MIPS, for example, or any VLIW architecture (including many of the modern GPUs). Cache is also often programmable (see scratch memory in Sparc, local memory in GPUs, etc.)
- Timmons 11y ago
  There are a number of reasons this is not openly available. Just a few: - It may lock the programmer into a specific CPU - The CPU cache/pipeline is less generic than you might think. Making setting a standard way to change it from within a program problematic. - Multiple programs may be running at the same time. Having the a program dictate cache behaviour would effect all running applications. - Arbitrary changes to behaviour would have performance implications when the change is made. In a multiple application situation that could mean flipflopping behaviour. Generally though the benefit of the manual control wouldn't be worth the cost/risk/loss of platform support for most applications as CPU behaviour is very good and it would probably be cheaper to just upgrade to a more expensive CPU than to spend the time on developing improvements to the algorithm. In the rare case where you do need specific behaviour and it is worth while it would be worth speaking to the vendors rather than doing it yourself.
- PythonicAlpha 11y ago
  Another reason might be security: There are already attacks known, that are using the CPU cache and/or instruction pipeline to break the boundaries of virtualization. With today's virtualizable processors, it becomes more and more important, that the users can not access to much of the processors implementation details.
sklogic 11y ago
The article is missing one important difference between a primitive Python use of jump threading and the OCaml bytecode interpreter which pre-compiles the bytecode into a threaded code. A difference in performance between these two is huge.
- loup-vaillant 11y ago
  > the OCaml bytecode interpreter […] pre-compiles the bytecode into a threaded code Wait a minute, how is that even possible? Or rather, what do you mean? Here's my layman's view of things: the bytecode is basically a string of opcodes. The interpreter has to look up the opcode before executing it somehow. And it can be threaded, or use an ordinary switch, or perform some other bizarre optimization I don't understand. But what does it mean for the bytecode itself to be compiled into a threaded form?
  - sklogic 11y ago
    > Wait a minute, how is that even possible? Or rather, what do you mean? It means that the stream of bytecodes (32-bit numbers in OCaml) is replaced with the corresponding label addresses (for 64-bit hosts - addresses minus a fixed offset) once. Then the execution is trivial. This is called "indirect threaded code" [1] and used a lot in Forth implementations, for example. See the definition of the "Next" macro in interp.c [2] for details. [1] https://en.wikipedia.org/wiki/Threaded_code#Indirect_threading https://en.wikipedia.org/wiki/Threaded_code#Indirect_threadi... [2] https://github.com/ocaml/ocaml/blob/trunk/byterun/interp.c https://github.com/ocaml/ocaml/blob/trunk/byterun/interp.c EDIT: if you wonder where the actual threading is done, see https://github.com/ocaml/ocaml/blob/trunk/byterun/fix_code.c https://github.com/ocaml/ocaml/blob/trunk/byterun/fix_code.c
    - loup-vaillant 11y ago
      OK, I'm rephrasing to make sure I understand. In the ordinary, C compliant switch code, you would do this: int instructions[] = { /* bytecode */ }; // main loop int* ip = instructions; while(1) { switch (*ip) { case 1: /* instruction 1 */ break; case 2: /* instruction 2 */ break; case 3: /* instruction 3 */ break; /* etc */ } ip++; /* goto next instruction. beware jumps */ } With a jump threaded implementation, you would do this instead: int instructions[] = { /* bytecode */ }; void jump_table[] = { &&lbl1, &&lbl2, &&lbl3, /* etc */ }; // main loop int* ip = instructions; goto *jump_table[*ip]; lbl1: /* instruction1 */ ip++; goto *jump_table[*ip]; lbl2: /* instruction2 */ ip++; goto *jump_table[*ip]; lbl3: /* instruction3 */ ip++; goto *jump_table[*ip]; /* etc */ Which means, instead of having the compiler constructing a jump table under the hood, I do this myself, and get the benefit of jumping from several locations instead of just one. But I still look up that table. Now the indirect threading you speak of: int instructions[] = { /* bytecode */ }; void jump_table[] = { &&lbl1, &&lbl2, &&lbl3, /* etc */ }; // translating bytecode into adresses void* labels[] = malloc(sizeof(void*) * nb_instructions); for (uint i = 0; i < nb_instructions; i++) labels[i] = jump_table[instructions[i]]; // main loop void** lp = labels; goto **lp; lbl1: /* instruction1 */ lp++; goto **lp; lbl2: /* instruction2 */ lp++; goto **lp; lbl3: /* instruction3 */ lp++; goto **lp; /* etc */ If I got that correctly, instead of accessing the jump table at some random place, I only access the label table in a much more linear fashion, saving one indirection and some memory access in the process —this should relieve some pressure off the L1 cache. Did I get that right?
nly 11y ago
I wonder if indirect calls have also improved in latest generations? Anything vtable based would benefit.
- loup-vaillant 11y ago
  Considering that Vtables are basically the same thing as a jump table in a switch… They have most probably improved in the same way.
rurban 11y ago
This research misses a few important points. First, the fastest interpreter is never switch or "jump threading" (i.e. computed goto) based. It is either based on passing the next pointer from one opcode to the next (e.g. perl5) or using an opcode array (lua). Those two cache much better and don't need the dispatch overhead with a jump table at all. Not talking about asm tuned interpreter dispatch yet, which count as best of the best. Second, the famous cited Ertl paper mostly suggested to use smaller opcodes to influence the icache. Lua and luajit do this with one-word ops and blow all other interpreters away. Using the computed goto extension only helps in bypassing the out of bounds check at the start of the switch dispatch, and gains the famous 2-3%, and less on more modern CPU's. When talking about the differences, the differences should be explained. Summary: This research result is not useful for state of the art interpreters, only for conventional slow interpreters. And for those the result should be ignored at all, as much better interpreter speedup techniques exist, not noted in this paper.
- loup-vaillant 11y ago
  > passing the next pointer from one opcode to the next (e.g. perl5) > using an opcode array (lua) Would you perchance have a couple links explaining what those are? A quick search on my end didn't turn up anything useful.
- mamcx 11y ago
  So, any example (easy to understand? well explained?, ie: apart to study a whole codebase as luajit) in what are the state of art interpreters?
- sanderjd 11y ago
  Since you seem to know a lot about this, which popular interpreters would you say are "state of the art" and which are "conventional slow"? It seems that lua and luajit (and perhaps perl5?) are in the former category. Is everything else in the latter?
deleted 11y ago
[deleted]
caf 11y ago
Is it really true that "Jump threading, though, can- not be implemented in standard C."? Surely, each computed goto: goto *labels[*vpc++]; can be replaced with a full copy of the switch: switch (*vpc++) { case OP_ADD: goto ADD; case OP_SUB: goto SUB; } ..and hopefully the compiler will replace the entries for the cases in the switch's jump table with the goto targets.

97 points by nkurz 11y ago

bch 11y ago

Would an editor kindly put a note in the OP link that this is a pdf?

acqq 11y ago

If my coworker would come to me and show me his results where he measured that the "Labels as Values" implementation is not need while "on his Haswell CPU the speedup is only 3%" I'd just ask "can it be guaranteed that the code you propose to revert to the plain switch will run only on that CPU?" If not and the switch is in the performance sensitive place I'd keep the "Labels as Values" implementation. There are many more CPUs in the world than "the latest Intel x86 CPU." Kudos for the developers of Haswell, but don't blindly trust the Inria researchers that tell you "Don’t Trust Folklore." I also don't like that this research was "partially supported" by the European grant thus explained: "ERC Advanced Grants allow exceptional established research leaders of any nationality and any age to pursue ground-breaking, high-risk projects that open new directions in their respective research fields or other domains." (1) 1) http://erc.europa.eu/advanced-grants http://erc.europa.eu/advanced-grants Is ground-breaking, high-risk research discovering that the algorithm in the latest Intel processor matches the one other researchers (which I respect much more) discovered in 2006, and variant of which won more "branch prediction championships"? I'd say no. At least they honestly write about the fact that the given algorithm is already known as highly efficient.

vardump 11y ago
While I somewhat agree with you, the real answer is assume nothing and profile. Always. But there's a catch. Things are getting a bit out of hand, there are just too many architectures and configurations. I think modern consumer-oriented code should run at least well on Intel Nehalem - Skylake, AMD K10 - K12, ARM Cortex A7/A8/A9/A15/A53/A57/A72, Qualcomm Krait/Kryo. Focus on 64-bit, but some attention should still be paid to 32-bit performance. Number of actual targets is even worse, because cache and memory architecture vary so much. At least all those have 64-byte cache lines. In high performance code, there's often the choice between memory and compute load balancing. What memory access patterns and layouts you're going to use - where do you want your bottlenecks? You can often reduce bandwidth requirements by computing more and vice versa. Take Sandy Bridge for example: While L1 and L2 cache sizes are fixed on Sandy Bridge, L3 cache varies between 1 - 20 MB. Clock speeds vary between 1.0 to 3.6 GHz. There are 1-4 memory channels, I believe they're usually arranged 64 byte granularity round robin. Say your access pattern is access every second 64-byte cache line vs. access every line. On 1 and 3 channel systems, both perform about same. When skipping 64 byte cache line on 2 channel system, effective memory bandwidth is equal to just 1 channel system. 4 channel system will behave like 2 channel one. The code might be bandwidth bottlenecked on 1-2 channel system and compute bound on 3-4 channel system. Then you're going to hit DRAM page miss every... 1-8 kB? System dependant, of course. To make the best choice for Sandy Bridge based systems, among other things, you need to know number of memory channels + their arrangement, amount of L3 cache and clock speed. On some Sandy Bridge CPUs you have a lot of time to do complicated data packing and unpacking, trying to just keep memory bandwidth usage down. That was just one architecture. Now add all the other platforms in the mix. There are pretty many different instruction set extensions. If you don't use them properly, you can lose an order of magnitude of performance. I think we'll need runtime code generation in the future. On system JIT/AOT also for traditionally compiled languages, such as C and C++.
- acqq 11y ago
  > the real answer is assume nothing and profile. They did profile, but what? Their "don't trust folklore" ("just 3% speedup") conclusion is valid only for one specific architecture and only for the most recent CPUs. As you say > modern consumer-oriented code should run at least well on Intel Nehalem - Skylake, AMD K10 - K12, ARM Cortex A7/A8/A9/A15/A53/A57/A72, Qualcomm Krait/Kryo. If I understand correctly, they themselves measure 30% speedup even only one generation before on Intel and they didn't measure any ARM or AMD. It looks to me that "don't trust folklore" claim was possible only by ignoring all the processors you name. And you are right, they also didn't show that they are aware of the differences inside of one generation (does the cheapest processor of the same generation behave the same?)
  - loup-vaillant 11y ago
    > Their "don't trust folklore" ("just 3% speedup") conclusion is valid only for one specific architecture and only for the most recent CPUs. For now. In 5 years from now, you can be sure most new architectures will have predictors that are as good. So, while it might be good to reach for the low hanging fruit (jump threading), heavier approaches such as super-instruction replication are probably no longer a good idea.
    - acqq 11y ago
      Writing the code in a way not to be dependent on the most advanced hardware solution in existence is better choice unless you target only the specific hardware or the solution is of the "use once then throw away" kind.
      - loup-vaillant 11y ago
        That would be true, if we were speaking of using this optimization instead of that optimisation. We're not. Here, they're saying that in this particular architecture, a number of optimisations are effectively useless. They're saying that naive code is almost as fast. They're saying that some "optimizations" have even become counter-productive. The lesson I get from this? Unless I know a fair bit about the target platforms, the naive approach is better, because any performance model I have in mind might be invalidated anyway.
shoo 11y ago
> Is ground-breaking, high-risk research discovering that the algorithm in the latest Intel processor matches the one other researchers (which I respect much more) discovered in 2006, and variant of which won more "branch prediction championships"? I'd say no. That appears to be a pretty reasonable criticism of the process by which the grant was awarded. My somewhat unfair characterisation of this research from skim reading the abstract and conclusion is: "we point out that the understanding in the academic literature is lagging behind the understanding already built into systems that are sold commercially and are in operational use". edit: There's something slightly humorous in considering the grant-allocation process itself as some kind of optimisation problem: Problem (GA) : How do we best allocate resources to promote high-risk, ground-breaking research? ...and then observing that grant resources have been allocated to perform research on another piece of optimisation that already seems to have happened. I wonder if one could obtain an ERC Advanced Grant to study the effectiveness of the current process by which ERC Advanced Grants are awarded, and suggest improvements? It is plausible that such a study could be very valuable and yet not have much political support.
- acqq 11y ago
  > understanding in the academic literature is lagging Even that were too much to claim as the "branch prediction championships" happened on an "academic" place: IEEE/ACM International Symposium on Microarchitecture http://www.jilp.org/cbp/ http://www.jilp.org/cbp/ http://www.microarch.org/micro37/ http://www.microarch.org/micro37/ also note the sponsors.
paulfr 11y ago
> the one other researchers (which I respect much more) discovered in 2006 You seem to be blissfully unaware that they're in fact the same researchers: André Seznec is a co-author of the paper. This paper is valuable in pointing out that ITTAGE branch prediction performance is a very good predictor of Haswell performance. Because the Haswell algorithm is secret, that should be very helpful to developers who still have to care about branch prediction. Interpreter developers shouldn't ignore pre-Haswell chips just yet, but if you were to, say, develop a new language your design decisions should be guided by where the puck will be rather than where it used to be.
- acqq 11y ago
  > You seem to be blissfully unaware that they're in fact the same researchers: André Seznec is a co-author of the paper. He's the third signer of the current paper but the first of the 2006 one. It's the case of legitimizing the "research" which only confirms exactly what Intel recently implemented in a given CPU generation, even if the grant is for other goals ("ground-breaking, high-risk projects"). Or, to be clearer, I respect the deeds not the persons. I fully understand the need for Seznec to be able to claim that the algorithm is really used by Intel and that therefore he co-authored the last paper. But confirming that Intel used ITTAGE is "ground-breaking, high-risk"? No. And does that mean we should never use goto label in the tight loops? No.
  - paulfr 11y ago
    The grant is for the DAL project [1], which presumably fits the "ground-breaking, high-risk" label. In such a project, some tasks will be high-risk, some tasks will be low-risk. Quantifying the branch predictor of current processors may be a comparatively easy task, but that doesn't mean it's trivial, useless or outside the scope of the project, which is to improve sequential performance of microarchitectures. Knowing that real-world processors are performing just as well as previous academic research is helpful, because it suggests that there is no difficulty or unrealistic assumption that prevented manufacturers from doing so. Conveying that knowledge to the compiler and interpreter community is important too. [1] https://team.inria.fr/alf/members/andre-seznec/defying-amdahls-law-dal/ https://team.inria.fr/alf/members/andre-seznec/defying-amdah...

umanwizard 11y ago

tl;dr for those who don't want to read the paper in detail: * Interpreters are conceptually a big switch(bytecode) statement in an infinite loop. They use various tricks to make it easier for the processor to predict the target of the next indirect branch * This previously had a dramatic impact on performance, because branch mispredictions are very expensive and it was difficult for the processor to predict them accurately. * Recent Intel architectures have improved branch prediction, so the aforementioned tricks no longer have a very big impact (on Haswell x86 processors specifically)

acqq 11y ago
> various tricks They actually present (approximately) a very simple construct that is used to speed the interpreters up: void labels[] = { &&ADD, &&SUB . . . }; ... goto labels[ vpc++ ]; ADD: ... goto labels[ vpc++ ]; instead of ... switch ( *vpc++ ) { case ADD: .... break; case SUB: It's not really hard. The only problem is that the former is not a standard C and not present in MSVC. See http://stackoverflow.com/questions/6421433/address-of-labels-msvc http://stackoverflow.com/questions/6421433/address-of-labels... "Erlang does (that) for building on Windows. They use MSVC for most of the build, and then GCC for one file to make use of the labels-as-values extension. The resulting object code is then hacked to be made compatible with the MSVC linker." It obviously mattered enough for Erlang developers to use GCC even for just that critical piece of C code. It doesn't mean that it has to be regularly used in every code (not every switch is executed the way the main interpreter loop is).
haberman 11y ago
I'd be interested to see benchmark numbers for LuaJIT, which makes it extremely easy to compile with either replicated dispatch (each bytecode instruction footer has a separate dispatch "jmp" instruction) or common dispatch (each bytecode instruction jumps to a common dispatch "jmp" instruction): http://repo.or.cz/w/luajit-2.0.git/blob/a5b1c4d98eeb97a950774ae032f51f820dfbfc4c:/src/vm_x86.dasc#l299 http://repo.or.cz/w/luajit-2.0.git/blob/a5b1c4d98eeb97a95077... // Instruction footer. .if 1 // Replicated dispatch. Less unpredictable branches, but higher I-Cache use. .define ins_next, ins_NEXT .define ins_next_, ins_NEXT .else // Common dispatch. Lower I-Cache use, only one (very) unpredictable branch. // Affects only certain kinds of benchmarks (and only with -j off). // Around 10%-30% slower on Core2, a lot more slower on P4. .macro ins_next jmp ->ins_next .endmacro .macro ins_next_ ->ins_next: ins_NEXT .endmacro .endif

pg_is_a_butt 11y ago

why is the 1st page narrower than the others? oversight?

chrisdevereux 11y ago

Is there a reason that machine languages don't allow the programmer/compiler/runtime to explicitly control the CPU's cache & instruction pipeline? Presumably they have access to much better information about the code's intent and future behaviour than the cpu does.

deleted 11y ago
[deleted]
sklogic 11y ago
There are architectures that require manual pipeline control. MIPS, for example, or any VLIW architecture (including many of the modern GPUs). Cache is also often programmable (see scratch memory in Sparc, local memory in GPUs, etc.)
Timmons 11y ago
There are a number of reasons this is not openly available. Just a few: - It may lock the programmer into a specific CPU - The CPU cache/pipeline is less generic than you might think. Making setting a standard way to change it from within a program problematic. - Multiple programs may be running at the same time. Having the a program dictate cache behaviour would effect all running applications. - Arbitrary changes to behaviour would have performance implications when the change is made. In a multiple application situation that could mean flipflopping behaviour. Generally though the benefit of the manual control wouldn't be worth the cost/risk/loss of platform support for most applications as CPU behaviour is very good and it would probably be cheaper to just upgrade to a more expensive CPU than to spend the time on developing improvements to the algorithm. In the rare case where you do need specific behaviour and it is worth while it would be worth speaking to the vendors rather than doing it yourself.
PythonicAlpha 11y ago
Another reason might be security: There are already attacks known, that are using the CPU cache and/or instruction pipeline to break the boundaries of virtualization. With today's virtualizable processors, it becomes more and more important, that the users can not access to much of the processors implementation details.

sklogic 11y ago

The article is missing one important difference between a primitive Python use of jump threading and the OCaml bytecode interpreter which pre-compiles the bytecode into a threaded code. A difference in performance between these two is huge.

loup-vaillant 11y ago
> the OCaml bytecode interpreter […] pre-compiles the bytecode into a threaded code Wait a minute, how is that even possible? Or rather, what do you mean? Here's my layman's view of things: the bytecode is basically a string of opcodes. The interpreter has to look up the opcode before executing it somehow. And it can be threaded, or use an ordinary switch, or perform some other bizarre optimization I don't understand. But what does it mean for the bytecode itself to be compiled into a threaded form?
- sklogic 11y ago
  > Wait a minute, how is that even possible? Or rather, what do you mean? It means that the stream of bytecodes (32-bit numbers in OCaml) is replaced with the corresponding label addresses (for 64-bit hosts - addresses minus a fixed offset) once. Then the execution is trivial. This is called "indirect threaded code" [1] and used a lot in Forth implementations, for example. See the definition of the "Next" macro in interp.c [2] for details. [1] https://en.wikipedia.org/wiki/Threaded_code#Indirect_threading https://en.wikipedia.org/wiki/Threaded_code#Indirect_threadi... [2] https://github.com/ocaml/ocaml/blob/trunk/byterun/interp.c https://github.com/ocaml/ocaml/blob/trunk/byterun/interp.c EDIT: if you wonder where the actual threading is done, see https://github.com/ocaml/ocaml/blob/trunk/byterun/fix_code.c https://github.com/ocaml/ocaml/blob/trunk/byterun/fix_code.c
  - loup-vaillant 11y ago
    OK, I'm rephrasing to make sure I understand. In the ordinary, C compliant switch code, you would do this: int instructions[] = { /* bytecode */ }; // main loop int* ip = instructions; while(1) { switch (*ip) { case 1: /* instruction 1 */ break; case 2: /* instruction 2 */ break; case 3: /* instruction 3 */ break; /* etc */ } ip++; /* goto next instruction. beware jumps */ } With a jump threaded implementation, you would do this instead: int instructions[] = { /* bytecode */ }; void jump_table[] = { &&lbl1, &&lbl2, &&lbl3, /* etc */ }; // main loop int* ip = instructions; goto *jump_table[*ip]; lbl1: /* instruction1 */ ip++; goto *jump_table[*ip]; lbl2: /* instruction2 */ ip++; goto *jump_table[*ip]; lbl3: /* instruction3 */ ip++; goto *jump_table[*ip]; /* etc */ Which means, instead of having the compiler constructing a jump table under the hood, I do this myself, and get the benefit of jumping from several locations instead of just one. But I still look up that table. Now the indirect threading you speak of: int instructions[] = { /* bytecode */ }; void jump_table[] = { &&lbl1, &&lbl2, &&lbl3, /* etc */ }; // translating bytecode into adresses void* labels[] = malloc(sizeof(void*) * nb_instructions); for (uint i = 0; i < nb_instructions; i++) labels[i] = jump_table[instructions[i]]; // main loop void** lp = labels; goto **lp; lbl1: /* instruction1 */ lp++; goto **lp; lbl2: /* instruction2 */ lp++; goto **lp; lbl3: /* instruction3 */ lp++; goto **lp; /* etc */ If I got that correctly, instead of accessing the jump table at some random place, I only access the label table in a much more linear fashion, saving one indirection and some memory access in the process —this should relieve some pressure off the L1 cache. Did I get that right?

nly 11y ago

I wonder if indirect calls have also improved in latest generations? Anything vtable based would benefit.

loup-vaillant 11y ago
Considering that Vtables are basically the same thing as a jump table in a switch… They have most probably improved in the same way.

rurban 11y ago

This research misses a few important points. First, the fastest interpreter is never switch or "jump threading" (i.e. computed goto) based. It is either based on passing the next pointer from one opcode to the next (e.g. perl5) or using an opcode array (lua). Those two cache much better and don't need the dispatch overhead with a jump table at all. Not talking about asm tuned interpreter dispatch yet, which count as best of the best. Second, the famous cited Ertl paper mostly suggested to use smaller opcodes to influence the icache. Lua and luajit do this with one-word ops and blow all other interpreters away. Using the computed goto extension only helps in bypassing the out of bounds check at the start of the switch dispatch, and gains the famous 2-3%, and less on more modern CPU's. When talking about the differences, the differences should be explained. Summary: This research result is not useful for state of the art interpreters, only for conventional slow interpreters. And for those the result should be ignored at all, as much better interpreter speedup techniques exist, not noted in this paper.

loup-vaillant 11y ago
> passing the next pointer from one opcode to the next (e.g. perl5) > using an opcode array (lua) Would you perchance have a couple links explaining what those are? A quick search on my end didn't turn up anything useful.
mamcx 11y ago
So, any example (easy to understand? well explained?, ie: apart to study a whole codebase as luajit) in what are the state of art interpreters?
sanderjd 11y ago
Since you seem to know a lot about this, which popular interpreters would you say are "state of the art" and which are "conventional slow"? It seems that lua and luajit (and perhaps perl5?) are in the former category. Is everything else in the latter?

deleted 11y ago

[deleted]

caf 11y ago

Is it really true that "Jump threading, though, can- not be implemented in standard C."? Surely, each computed goto: goto *labels[*vpc++]; can be replaced with a full copy of the switch: switch (*vpc++) { case OP_ADD: goto ADD; case OP_SUB: goto SUB; } ..and hopefully the compiler will replace the entries for the cases in the switch's jump table with the goto targets.