Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Huge switches are common in the inner loop of emulators and interpreters. They tend to end up with a 256-case switch to handle the next byte in the instruction stream.


I understand that use case, but in my opinion it would be much cleaner (and speculating faster) to have an 256-slot array...and routing with opcodes[byte.charCodeAt(0)](); or something similar.


Function calls are expensive if they are not optimized. However, the same is true for switch/case trees, and even for JIT'd code (dynamically created functions) ...

In the Javascript world, "Your Mileage May Vary" truly is a motto.


Would it make sense to use a bitwise test and two 128-part switch blocks?


Why would the use a switch instead of a hashtable?


Good compilers optimize a switch into a jump table, which is much, much faster than a hashtable.

Using a hashtable for instruction dispatch in an emulator would be utterly insane. You'd use an array (but the compiler can do a better job by generating raw asm for a jump table.)


Could you explain why it would be insane? I was under the impression that all you needed was fast lookup time.


A jump table is O(1). A hash table lookup is gonna be roughly O(N) for the hash + O(M) for the size of the hash bucket. Small hash tables can end up with very large buckets. Hash buckets are sometimes linked lists as well, so you pay the cost of that pointer indirection to walk the bucket. It's possible that a typical JS runtime can cache the hash value for a given string (especially literals), so that will help a bit for string keys. Integer keys might have a similar optimization.

People overestimate the performance of hash tables. It's true that they are quite fast on a modern CPU, so you get away with using them extensively in dynamic languages like JS, but they are still way way slower than a jump table or directly accessing fields at statically known offsets.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: