5 ms·

Lua's dispatch wasn't chosen because it was the fastest. If you read their Lua5 paper, they discuss how they prioritized being portable ANSI C over speed. Indir

by pbiggar 14y ago

Lua's dispatch wasn't chosen because it was the fastest. If you read their Lua5 paper, they discuss how they prioritized being portable ANSI C over speed. Indirect threading is the fastest simple technique, but you can do even better. See section 3.3 of http://www.cs.tcd.ie/publications/tech-reports/reports.07/TCD-CS-2007-49.pdf http://www.cs.tcd.ie/publications/tech-reports/reports.07/TC... for a discussion.

haberman 14y ago
If you're giving up portability, you might as well go all the way and create a JIT. Techniques like what the paper calls "inline-threaded dispatch" seem of limited usefulness, since they give neither the speed of a JIT nor the portability of a bytecode VM. My main point was that switch()-based dispatch isn't that bad. I'm surprised that this recent literature distinguishes between switch dispatch and token-threaded dispatch, since as Mike Pall notes, "Tail-merging and CSE will happily join all these common tails of each instruction and generate a single dispatch point," so the goto-spaghetti of token-threaded dispatch is likely not even worth it. (http://article.gmane.org/gmane.comp.lang.lua.general/75426 http://article.gmane.org/gmane.comp.lang.lua.general/75426) > Indirect threading is the fastest simple technique I'm confused; the paper itself says: "However, because of a level of indirection, indirect-threaded dispatch is not be as efficient as direct-threaded dispatch." Even direct-threaded dispatch still results in an indirect branch for every VM instruction, it just tries to save a table lookup over token-threading. Ultimately the most common and practical dispatch techniques seem to boil down to either a single indirect branch or replicated indirect branches.
- sb 14y ago
  You're not really "giving up" portability, only with ANSI C. For all architectures where GCC is available, its labels-as-values support will happily compile and hence give you a fully portable instruction dispatch. Regarding the threaded code: the literature seems to be horribly inconsistent in this regard. Token threaded code might actually refer to indirect-threaded code depending on what the author has read. I was actually quite surprised to read what "indirect threaded code" originally meant when I read Debaere and van Campenhout's 1990 book "Interpretation and Instruction Path co-processing". Regarding the effect of CSE & tail-merging: I have only seen GCC to do this once, by disabling basic block reordering (-fno-reorder-blocks, due to a so-called "software trace cache"), otherwise this has never happened to me. Since I have nothing but the highest respect for Mike Pall, I guess that he might have experienced this for Lua, which has--to the best of my knowledge--less than 40 instructions. I will try to verify this on the weekend.
  - haberman 14y ago
    > You're not really "giving up" portability I should have been more clear; that comment was in reference to some of the techniques the paper discusses which do give up portability, namely "inline-threaded dispatch" and "context-threaded dispatch." My overall points are: switch() isn't that bad, and most practical dispatch techniques ultimately boil down to either a single indirect branch or replicated indirect branches. > Regarding the effect of CSE & tail-merging: I have only seen GCC to do this once I've never seen it happen with my own eyes, but it appears the Python guys experienced this also at one point and had to tweak the flags -fno-crossjumping and -fno-gcse. http://bugs.python.org/issue4753 http://bugs.python.org/issue4753 > I will try to verify this on the weekend. Do you have a blog? I'd love to hear what you discover.
    - pbiggar 14y ago
      > Do you have a blog? I'd love to hear what you discover. I second this. I'd be very interested to know who you (sb) are in real life.
- pbiggar 14y ago
  I'm not sure where you're going with this, but you seem to have an emotional attachment to switch statements, which is otherwise unsupported by reality :) > If you're giving up portability, you might as well go all the way and create a JIT. Well no. A JIT is a massive massive amount of work, an interpreter is not. Don't throw the baby out with the bathwater. Besides, you can make a damn portable token-threaded dispatch for supported platforms (which means anything using GCC, LLVM or Visual Studio, which means basically anything that exists today), falling back to switch statements for unsupported platforms. > Techniques like what the paper calls "inline-threaded dispatch" seem of limited usefulness, since they give neither the speed of a JIT nor the portability of a bytecode VM. I forget the numbers, but lets say its 20%. It gives a 20% speed boost, for a few dozen lines of code. Hardly "limited usefulnes". > My main point was that switch()-based dispatch isn't that bad. Its portable and easy to implement. It is not the fastest dispatch mechanism. It will generally be the bottleneck in an otherwise-efficient interpreter. It does not compare well to most other dispatch techniques, and is only useful if you demand that absolutely only ANSI C will do. > I'm surprised that this recent literature distinguishes between switch dispatch and token-threaded dispatch, since as Mike Pall notes, "Tail-merging and CSE will happily join all these common tails of each instruction and generate a single dispatch point," so the goto-spaghetti of token-threaded dispatch is likely not even worth it. (http://article.gmane.org/gmane.comp.lang.lua.general/75426 http://article.gmane.org/gmane.comp.lang.lua.general/75426) Firstly, the work on interpreters was done in the 80s and 90s. Really awesome optimizing compilers post-date that considerably. Secondly, Pall does not say those those dispatching techniques are equivalent. What he says is that interpreters in C are difficult, and you have to fight the optimizer. If you wrote them in assembly, as Pall did, you would not find that the techniques were equivalent. > Ultimately the most common and practical dispatch techniques seem to boil down to either a single indirect branch or replicated indirect branches. Its certainly common to use a single indirect branch. However, it is suboptimal. People like speed. Finally, note that my original point is the switch-based dispatch is slow, but that better techniques in PHP are not worth it, because the rest of the interpreter is so much slower.
  - haberman 14y ago
    Wow, you read a way more argumentative tone into my comment than I intended. It's all good, I'm trying to expand my understanding. :) Though I'm not sure I agree with your characterization of my points as "nonsense." > [Inline-threaded dispatch] gives a 20% speed boost, for a few dozen lines of code. Hardly "limited usefulness". Unless I'm missing something, I think you would be very hard-pressed to generate basic blocks of native code in only a few dozen lines of platform-dependent code. I'm not seeing how you could do it without implementing your own code generator (which would take far more than a dozen lines). Is there some clever way of leveraging the C compiler's output that I'm missing? Also, once you are generating basic blocks of native code, I would consider it a JIT at that point, even if it is not as sophisticated as a JIT that's doing register allocation and optimization. Writing this sort of JIT that uses a static register allocation and a fixed instruction sequence for each bytecode op doesn't seem that much more work than writing an interpreter in assembly language (especially if you use Mike Pall's excellent framework DynASM: http://luajit.org/dynasm.html http://luajit.org/dynasm.html). > Its certainly common to use a single indirect branch. However, it is suboptimal. I don't believe that a single indirect branch is a priori slower; while replicated dispatch makes better use of the branch predictor, it also results in less optimal i-cache usage (the LuaJIT code notes this trade-off, but observes that replicated dispatch is 20-30% faster in practice: http://repo.or.cz/w/luajit-2.0.git/blob/2ad9834df6fe47c7150d16a5d30782fb5696bec9:/src/vm_x86.dasc#l283 http://repo.or.cz/w/luajit-2.0.git/blob/2ad9834df6fe47c7150d...). I'm not saying switch is better, what I'm saying is that you can't reliably replicate dispatch in C (at least according to Mike's message that I cited earlier), which makes switch() a totally reasonable choice for interpreters written in C. By the way, I'm not just making stuff up, I have written a JIT of my own: https://github.com/haberman/upb/blob/master/upb/pb/decoder_x64.dasc https://github.com/haberman/upb/blob/master/upb/pb/decoder_x...

by pbiggar 14y ago

haberman 14y ago

If you're giving up portability, you might as well go all the way and create a JIT. Techniques like what the paper calls "inline-threaded dispatch" seem of limited usefulness, since they give neither the speed of a JIT nor the portability of a bytecode VM. My main point was that switch()-based dispatch isn't that bad. I'm surprised that this recent literature distinguishes between switch dispatch and token-threaded dispatch, since as Mike Pall notes, "Tail-merging and CSE will happily join all these common tails of each instruction and generate a single dispatch point," so the goto-spaghetti of token-threaded dispatch is likely not even worth it. (http://article.gmane.org/gmane.comp.lang.lua.general/75426 http://article.gmane.org/gmane.comp.lang.lua.general/75426) > Indirect threading is the fastest simple technique I'm confused; the paper itself says: "However, because of a level of indirection, indirect-threaded dispatch is not be as efficient as direct-threaded dispatch." Even direct-threaded dispatch still results in an indirect branch for every VM instruction, it just tries to save a table lookup over token-threading. Ultimately the most common and practical dispatch techniques seem to boil down to either a single indirect branch or replicated indirect branches.

sb 14y ago
You're not really "giving up" portability, only with ANSI C. For all architectures where GCC is available, its labels-as-values support will happily compile and hence give you a fully portable instruction dispatch. Regarding the threaded code: the literature seems to be horribly inconsistent in this regard. Token threaded code might actually refer to indirect-threaded code depending on what the author has read. I was actually quite surprised to read what "indirect threaded code" originally meant when I read Debaere and van Campenhout's 1990 book "Interpretation and Instruction Path co-processing". Regarding the effect of CSE & tail-merging: I have only seen GCC to do this once, by disabling basic block reordering (-fno-reorder-blocks, due to a so-called "software trace cache"), otherwise this has never happened to me. Since I have nothing but the highest respect for Mike Pall, I guess that he might have experienced this for Lua, which has--to the best of my knowledge--less than 40 instructions. I will try to verify this on the weekend.
- haberman 14y ago
  > You're not really "giving up" portability I should have been more clear; that comment was in reference to some of the techniques the paper discusses which do give up portability, namely "inline-threaded dispatch" and "context-threaded dispatch." My overall points are: switch() isn't that bad, and most practical dispatch techniques ultimately boil down to either a single indirect branch or replicated indirect branches. > Regarding the effect of CSE & tail-merging: I have only seen GCC to do this once I've never seen it happen with my own eyes, but it appears the Python guys experienced this also at one point and had to tweak the flags -fno-crossjumping and -fno-gcse. http://bugs.python.org/issue4753 http://bugs.python.org/issue4753 > I will try to verify this on the weekend. Do you have a blog? I'd love to hear what you discover.
  - pbiggar 14y ago
    > Do you have a blog? I'd love to hear what you discover. I second this. I'd be very interested to know who you (sb) are in real life.
pbiggar 14y ago
I'm not sure where you're going with this, but you seem to have an emotional attachment to switch statements, which is otherwise unsupported by reality :) > If you're giving up portability, you might as well go all the way and create a JIT. Well no. A JIT is a massive massive amount of work, an interpreter is not. Don't throw the baby out with the bathwater. Besides, you can make a damn portable token-threaded dispatch for supported platforms (which means anything using GCC, LLVM or Visual Studio, which means basically anything that exists today), falling back to switch statements for unsupported platforms. > Techniques like what the paper calls "inline-threaded dispatch" seem of limited usefulness, since they give neither the speed of a JIT nor the portability of a bytecode VM. I forget the numbers, but lets say its 20%. It gives a 20% speed boost, for a few dozen lines of code. Hardly "limited usefulnes". > My main point was that switch()-based dispatch isn't that bad. Its portable and easy to implement. It is not the fastest dispatch mechanism. It will generally be the bottleneck in an otherwise-efficient interpreter. It does not compare well to most other dispatch techniques, and is only useful if you demand that absolutely only ANSI C will do. > I'm surprised that this recent literature distinguishes between switch dispatch and token-threaded dispatch, since as Mike Pall notes, "Tail-merging and CSE will happily join all these common tails of each instruction and generate a single dispatch point," so the goto-spaghetti of token-threaded dispatch is likely not even worth it. (http://article.gmane.org/gmane.comp.lang.lua.general/75426 http://article.gmane.org/gmane.comp.lang.lua.general/75426) Firstly, the work on interpreters was done in the 80s and 90s. Really awesome optimizing compilers post-date that considerably. Secondly, Pall does not say those those dispatching techniques are equivalent. What he says is that interpreters in C are difficult, and you have to fight the optimizer. If you wrote them in assembly, as Pall did, you would not find that the techniques were equivalent. > Ultimately the most common and practical dispatch techniques seem to boil down to either a single indirect branch or replicated indirect branches. Its certainly common to use a single indirect branch. However, it is suboptimal. People like speed. Finally, note that my original point is the switch-based dispatch is slow, but that better techniques in PHP are not worth it, because the rest of the interpreter is so much slower.
- haberman 14y ago
  Wow, you read a way more argumentative tone into my comment than I intended. It's all good, I'm trying to expand my understanding. :) Though I'm not sure I agree with your characterization of my points as "nonsense." > [Inline-threaded dispatch] gives a 20% speed boost, for a few dozen lines of code. Hardly "limited usefulness". Unless I'm missing something, I think you would be very hard-pressed to generate basic blocks of native code in only a few dozen lines of platform-dependent code. I'm not seeing how you could do it without implementing your own code generator (which would take far more than a dozen lines). Is there some clever way of leveraging the C compiler's output that I'm missing? Also, once you are generating basic blocks of native code, I would consider it a JIT at that point, even if it is not as sophisticated as a JIT that's doing register allocation and optimization. Writing this sort of JIT that uses a static register allocation and a fixed instruction sequence for each bytecode op doesn't seem that much more work than writing an interpreter in assembly language (especially if you use Mike Pall's excellent framework DynASM: http://luajit.org/dynasm.html http://luajit.org/dynasm.html). > Its certainly common to use a single indirect branch. However, it is suboptimal. I don't believe that a single indirect branch is a priori slower; while replicated dispatch makes better use of the branch predictor, it also results in less optimal i-cache usage (the LuaJIT code notes this trade-off, but observes that replicated dispatch is 20-30% faster in practice: http://repo.or.cz/w/luajit-2.0.git/blob/2ad9834df6fe47c7150d16a5d30782fb5696bec9:/src/vm_x86.dasc#l283 http://repo.or.cz/w/luajit-2.0.git/blob/2ad9834df6fe47c7150d...). I'm not saying switch is better, what I'm saying is that you can't reliably replicate dispatch in C (at least according to Mike's message that I cited earlier), which makes switch() a totally reasonable choice for interpreters written in C. By the way, I'm not just making stuff up, I have written a JIT of my own: https://github.com/haberman/upb/blob/master/upb/pb/decoder_x64.dasc https://github.com/haberman/upb/blob/master/upb/pb/decoder_x...