6 ms·

Unless this is relying on the compiler optimizing this, the dispatch looks to be not good if(vm->pProgram->instr[instr_idx] == MOV) arg0 = arg1; else if(vm->

• palish 15y ago
  Yeah, I noticed the same thing. But this is a good starting point. From here, he could VirtualProtect() some memory and write the equivalent x86 instructions.
• haberman 15y ago
  That is surprisingly bad. It reminds me of when I first heard that you could get fast sine/cosine approximations with table lookups -- not fully understanding this idea I wrote a program that generated the following (I was in high school, young and naive): double sin(double x) { if (x >= 0.00 && x < 0.01) return 0; if (x >= 0.01 && x < 0.02) return 0.01; // ... }
  • gcr 15y ago
    At least you wrote the program to generate it rather than typing all that by hand. I think you got the gist of the idea. In any case, would all those branches be faster than the comparatively expensive floating-point arithmetic?
    • Retric 15y ago
      No, at best you could do a binary search using if's to simulate a lookup table, but you are going to trash the pipeline on a modern CPU if you want a reasonably complex lookup table you are much better off with something like: float lookup_Sine(x){ int I = 100 * (x mod 360); return sine_table(I); } Anyway, for a modern CPU hitting main memory takes a lot of cycles. So you need something a lot more complex than a simple trig function to make it worth it.
• teyc 15y ago
  For the benefit of those who don't understand this, have a look at http://en.wikipedia.org/wiki/Threaded_code http://en.wikipedia.org/wiki/Threaded_code where it explains the different ways one can process byte codes. The key issue here is that the efficiency of dispatch loop determines the performance of a VM.
  • anon_comenter9 15y ago
    Exactamundo!
• spitfire 15y ago
  That just makes the case for switch expressions even stronger. If you had those this would be a damn simple switch statement and it'd provide lots of hints to the compiler for speedups. (All but the modified jump instructions can go in a straight switch statement). I'm very tempted to add type tagging into this and write a burroughs b5000 emulator. That'd be a neat side project.
• windsurfer 15y ago
  Why can't the compiler optimize this?
  • to3m 15y ago
    Theoretically, it could do, at least in this case, I think? Very risky to rely on that though! I doubt compiler writers have people who haven't heard of the switch statement in mind when they decide which optimizations to put in. (The "fast" branch uses a switch statement - I guess the author is going for minimum number of lines in this one? I'm not sure saving 2-3 lines compared to a squeezed-together switch statement is a great tradeoff, though. You could get better results by just putting everything in one source file. Easier deployment, too. I bet it wouldn't affect readability significantly.)
  • ori_b 15y ago
    It can. However, this is a very uncommon pattern, so it's not worth trying very hard to detect. On top of that, I'd expect the compiler to bail after the pattern gets to a certain size.
• matthew-wegner 15y ago
  Perhaps that's why there is a FastVM fork?
• lobster_johnson 15y ago
  Yes, that's very odd. At least they could have used a case statement, which a C compiler will be able to optimize into an efficient jump table. I remember reading about a VM (I remember it as being Google's V8, but that one compiles directly to machine code so probably I'm misremembering; maybe it was Strongtalk?) which basically ditched the classic bytecode loop (grab next instruction, check what it is, evaluate it, repeat) and instead implemented each bytecode type as a function and somehow munged the instruction pointer or modified the VM's machine code itself so that the CPU would move directly to the next instruction's function without jumping. Damn, I wish I could remember the idea. Anyone know what I'm talking about?
  • anon_comenter9 15y ago
    You are probably talking about threaded code which is described in "The Structure and Performance of Efficient Interpreters" http://www.jilp.org/vol5/v5paper12.pdf http://www.jilp.org/vol5/v5paper12.pdf With real code examples
    • lobster_johnson 15y ago
      Thanks, that's an interesting paper. I have never heard of that paper, I'm thinking specifically of a VM that implemented the feature. Not sure if we are talking about the same algorithm, either, although it sounds similar.
      • anon_comenter9 15y ago
        Thinking about it, that sounds like inline threading http://blog.mozilla.com/dmandelin/2008/08/27/inline-threading-tracemonkey-etc/ http://blog.mozilla.com/dmandelin/2008/08/27/inline-threadin...
    • jws 15y ago
      The bodies of these opcodes are only single machine instruction or two themselves and are inlined. This changes the game.
• jws 15y ago
  Update: I changed it to a switch statement. The euler1 program went from 0.081s to 0.091s with gcc on a core i3. The cascading if statements are indeed faster than a switch. EOU - original comment follows… Without the benefit of profiling, I can suggest it may not be as bad as it looks. The relative frequency of the opcodes could make this faster than the switch. See MOV, PUSH, POP in the front? Theses likely have tiny, inline implementations and are also probably a large percentage of the opcodes implemented. They may all fit in the same cache line and give the pipelines on deep pipeline, branch predicting machines lots of good stuff to work on. Likewise, the infrequently occurring opcode comparisons in the back part of the statement, by definition, are almost always false, which should tell the branch predictors which way to go to again keep the pipelines full. A switch on the other hand is pretty much a guaranteed pipeline flush. But… if you asked me to code this control structure without being able to profile and to get it fast the first time… I'd use a switch. (well, maybe with a couple if statements out front if I knew I had a heavily lopsided distribution.) Then if I'd go reread that article that came by HN a couple weeks ago and turn the control structure inside out and see how much better it was.
  • palish 15y ago
    You're very wise. Thank you for sharing. It's satisfying that you were able to say "There's a good chance you're wrong, here's why" and then be confirmed by testing. You obviously have a great deal of experience with low-level programming; relatively rare, nowadays. Mine comes from graphics programming. Also, which article are you referring to? Any keywords I can search for?
    • jws 15y ago
      I think I am remembering this one: http://news.ycombinator.com/item?id=2593095 http://news.ycombinator.com/item?id=2593095 The Common CPU Interpreter Loop Revisited But after looking at tinyvm it may be a special animal. The native implementation of its virtual opcodes are only one or two instructions. Locality, cacheing, and pipelining are working at their finest here and it might be best to just let them do their thing.
  • iam 15y ago