5 ms·

This is one of those gotcha that trap senior devs way more than junior devs. Growing up with C being my first language, I intuitively associate switch with a jm

by KMnO4 4y ago

This is one of those gotcha that trap senior devs way more than junior devs. Growing up with C being my first language, I intuitively associate switch with a jmp table (ie extremely fast). Even though I knew it’s unlikely to be as performant in JS, it never occurred to me that it would actually be slow, until I did a deep dive into low level JS optimization. Related: Matt Godbolt’s talk on emulating 6502 in JS. He also mentions the poor performance of switch for opcodes: https://youtu.be/7WuRq-Wmw5o https://youtu.be/7WuRq-Wmw5o

syntheweave 4y ago
I don't know. Maybe it's because I've spent too long thinking about such things, but interpreter dispatch routines are one of those areas of code where micro-optimizations are very pernicious and one should expect to review the landscape each time to rediscover best practice. See all the ways of compiling and executing Forth words for examples.
teruakohatu 4y ago
> would actually be slow, until I did a deep dive into low level JS optimization Can you explain why this is? Intuitively it would seem like optimizing a switch statement would be really low-hanging fruit. I would have thought it would be optimized into something almost exactly like what the author hand rolled.
- TAForObvReasons 4y ago
  You can switch on arbitrary types in JS and you can add expressions: switch(3) { case true: break; case "ab" + "c": break; case Math.random() >= 0.5 ? "heads" : new Error("tails") : break; } The optimizer will have to be persuaded that the switch and each case is integral before optimizing with a jump table. On the other hand, Arrays typically have a fast path for integer indices.
  - teruakohatu 4y ago
    That explains it, but shouldn't a switch with string or numerical constants (or an expression made up of constants) just be optimized away anyway?
    - jcfields 4y ago
      The article quotes a Stack Overflow post with the conditions under which V8 will optimize the switch statement: > @LGB actually in V8 (JS engine used by google chrome) you need to jump through a lot of hoops to get switch case optimized: All the cases must be of same type. All the cases must either be string literals or 31-bit signed integer literals. And there must be less than 128 cases. And even after all those hoops, all you get is what you would have gotten with if-elses anyway (I.E. no jump tables or sth like that). True story. In the case of this emulator, it wasn’t being optimized because it had more than 128 cases.
      - teruakohatu 4y ago
        > In the case of this emulator, it wasn’t being optimized because it had more than 128 cases. Now that makes sense. Thank you.
  - shultays 4y ago
    But in js you can have maps of arbitrary types as keys right? So jump table could just use that
    - mattashii 4y ago
      that's not quite true, because arbitrary expressions can change meaning due to e.g. overloading of functions. E.g. Random.random() will have to be called each time that case branch is evaluated, because that function could be overloaded or change its returned value.
fenomas 4y ago
> the poor performance of switch for opcodes I think you've slightly misunderstood TFA. The issue there wasn't that the switch statement was slow, per se - it was that V8's optimizing compiler didn't yet support such statements, so V8 was bailing out of its JIT step and executing the function via a (dog-slow) interpreter. In other words the function would have run painfully slow even if it returned before reaching the switch statement. It's also maybe worth adding that gotchas like this were super common way back in the early days TFA describes, but AFAIK they are no longer a concern now. Back when V8's optimizer was primitive it used to bail out for all kinds of reasons - because it saw a "try()" statement, because a function was too long, or even just because it got confused. Nowadays it's a different world - I do a lot of JS perf work, but it's probably been two years since I've seen V8 deopt anything for any reason.
- ncmncm 4y ago
  I think you also misread the article. It clearly said that an optimized switch would still run as a series of "if" tests, and that when he got the compiler to generate that code, it wasn't faster.
  - fenomas 4y ago
    TFA doesn't cover any cases where switch statements got optimized. It starts with the relevant code getting deopted, then the author tries a fix but the code is still deopted, then he removes the switch statements. (Mind you I'm not saying switch statements are fast - they may well be slower than the alternatives even after being optimized. I'm just pointing out that TFA isn't about the performance of switch statements, it's about avoiding deopts.)
    - fps_doug 4y ago
      TFA references a post that states that optimized switch statements in V8 are still just if-elseif-else and not jump tables, at least back when it was written. They might be faster than unoptimized JS, but certainly not as fast as jump tables. The author didn't even bother to split up the functions/switch blocks further when they learned about the requirements to get V8 to actually optimize a switch, as it seemed not worth it.
dehrmann 4y ago
In my first job out of school, I was writing driver code in C. In one of my projects, I had a code block that wasn't working, but all it did was a switch on ints. On a hunch, I tried ifs, and it worked. Turns out I found a bug in the in-house GCC fork. I'm sure my manager thought I was an idiot--I was a new grad saying my project isn't working, and I think it's a compiler bug.
- carlmr 4y ago
  We always assume compilers to be infallible, and for the most part this is right. But special compilers for special targets or certified compilers for special uses, I've found to often have compiler issues. Why did you have a GCC-fork?
  - dehrmann 4y ago
    I wish I could remember. It wasn't a secret sauce thing, so all I can think of is you get improved support and faster bugfixes.
- georgecmu 4y ago
  What processor was that for? I remember (1999-2000) we found out the hard way that GCC for Hitachi H8s had that exact bug.
  - dehrmann 4y ago
    I think it was a generic mips CPU.
- throwawaysleep 4y ago
  Did you stick to it? I admittedly would have conceded I was wrong in that situation.
  - dehrmann 4y ago
    I did! The compiler team agreed that it was broken and gave me a flag to disable jump tables. Surprisingly, that didn't cause any noticeable performance regressions.
ChrisRR 4y ago
I'm the same. I've always worked in C and would've naturally assumed it would've executed as a jump table.
phkahler 4y ago
>> I intuitively associate switch with a jmp table Me too, but I try to keep the set of values dense and use a mask (op & 0xff) to help the compiler know it doesn't need to do bounds checking. Verify these changes help of course.

by KMnO4 4y ago

syntheweave 4y ago

I don't know. Maybe it's because I've spent too long thinking about such things, but interpreter dispatch routines are one of those areas of code where micro-optimizations are very pernicious and one should expect to review the landscape each time to rediscover best practice. See all the ways of compiling and executing Forth words for examples.

teruakohatu 4y ago

> would actually be slow, until I did a deep dive into low level JS optimization Can you explain why this is? Intuitively it would seem like optimizing a switch statement would be really low-hanging fruit. I would have thought it would be optimized into something almost exactly like what the author hand rolled.

TAForObvReasons 4y ago
You can switch on arbitrary types in JS and you can add expressions: switch(3) { case true: break; case "ab" + "c": break; case Math.random() >= 0.5 ? "heads" : new Error("tails") : break; } The optimizer will have to be persuaded that the switch and each case is integral before optimizing with a jump table. On the other hand, Arrays typically have a fast path for integer indices.
- teruakohatu 4y ago
  That explains it, but shouldn't a switch with string or numerical constants (or an expression made up of constants) just be optimized away anyway?
  - jcfields 4y ago
    The article quotes a Stack Overflow post with the conditions under which V8 will optimize the switch statement: > @LGB actually in V8 (JS engine used by google chrome) you need to jump through a lot of hoops to get switch case optimized: All the cases must be of same type. All the cases must either be string literals or 31-bit signed integer literals. And there must be less than 128 cases. And even after all those hoops, all you get is what you would have gotten with if-elses anyway (I.E. no jump tables or sth like that). True story. In the case of this emulator, it wasn’t being optimized because it had more than 128 cases.
    - teruakohatu 4y ago
      > In the case of this emulator, it wasn’t being optimized because it had more than 128 cases. Now that makes sense. Thank you.
- shultays 4y ago
  But in js you can have maps of arbitrary types as keys right? So jump table could just use that
  - mattashii 4y ago
    that's not quite true, because arbitrary expressions can change meaning due to e.g. overloading of functions. E.g. Random.random() will have to be called each time that case branch is evaluated, because that function could be overloaded or change its returned value.

fenomas 4y ago

> the poor performance of switch for opcodes I think you've slightly misunderstood TFA. The issue there wasn't that the switch statement was slow, per se - it was that V8's optimizing compiler didn't yet support such statements, so V8 was bailing out of its JIT step and executing the function via a (dog-slow) interpreter. In other words the function would have run painfully slow even if it returned before reaching the switch statement. It's also maybe worth adding that gotchas like this were super common way back in the early days TFA describes, but AFAIK they are no longer a concern now. Back when V8's optimizer was primitive it used to bail out for all kinds of reasons - because it saw a "try()" statement, because a function was too long, or even just because it got confused. Nowadays it's a different world - I do a lot of JS perf work, but it's probably been two years since I've seen V8 deopt anything for any reason.

ncmncm 4y ago
I think you also misread the article. It clearly said that an optimized switch would still run as a series of "if" tests, and that when he got the compiler to generate that code, it wasn't faster.
- fenomas 4y ago
  TFA doesn't cover any cases where switch statements got optimized. It starts with the relevant code getting deopted, then the author tries a fix but the code is still deopted, then he removes the switch statements. (Mind you I'm not saying switch statements are fast - they may well be slower than the alternatives even after being optimized. I'm just pointing out that TFA isn't about the performance of switch statements, it's about avoiding deopts.)
  - fps_doug 4y ago
    TFA references a post that states that optimized switch statements in V8 are still just if-elseif-else and not jump tables, at least back when it was written. They might be faster than unoptimized JS, but certainly not as fast as jump tables. The author didn't even bother to split up the functions/switch blocks further when they learned about the requirements to get V8 to actually optimize a switch, as it seemed not worth it.

dehrmann 4y ago

In my first job out of school, I was writing driver code in C. In one of my projects, I had a code block that wasn't working, but all it did was a switch on ints. On a hunch, I tried ifs, and it worked. Turns out I found a bug in the in-house GCC fork. I'm sure my manager thought I was an idiot--I was a new grad saying my project isn't working, and I think it's a compiler bug.

carlmr 4y ago
We always assume compilers to be infallible, and for the most part this is right. But special compilers for special targets or certified compilers for special uses, I've found to often have compiler issues. Why did you have a GCC-fork?
- dehrmann 4y ago
  I wish I could remember. It wasn't a secret sauce thing, so all I can think of is you get improved support and faster bugfixes.
georgecmu 4y ago
What processor was that for? I remember (1999-2000) we found out the hard way that GCC for Hitachi H8s had that exact bug.
- dehrmann 4y ago
  I think it was a generic mips CPU.
throwawaysleep 4y ago
Did you stick to it? I admittedly would have conceded I was wrong in that situation.
- dehrmann 4y ago
  I did! The compiler team agreed that it was broken and gave me a flag to disable jump tables. Surprisingly, that didn't cause any noticeable performance regressions.

ChrisRR 4y ago

I'm the same. I've always worked in C and would've naturally assumed it would've executed as a jump table.

phkahler 4y ago

>> I intuitively associate switch with a jmp table Me too, but I try to keep the set of values dense and use a mask (op & 0xff) to help the compiler know it doesn't need to do bounds checking. Verify these changes help of course.