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.

This used to be good advice, but I'm pretty sure that the modern engines all perform this optimization for you now.

Try this benchmark out: http://jsperf.com/fastest-array-loops-in-javascript/56

It looks like you're right, very right unless there's something else going on in the perf tests.

There's something going on with the perf tests - most of that code is being optimised away, in one case I got over a billion cycles per second. The trick to these things is writing code which cannot be optimised away, like returning Math.random() from a function and using the return value to increment another variable.

Yes. At present if you want a jsperf test to be remotely accurate:

1) It shouldn't exercise the GC. GC pressure totally skews jsperf results in a way it can't compensate for.

2) It should compute a result on every iteration that is checked at the end to make sure it is accurate. (This ensures that the compiler can't optimize out unused results from your benchmark loop)

3) The check should have actual control flow so it can't be ignored.

It's also worthwhile to warm all your test cases once in the setup portion of the page before the loop runs. Some performance issues only appear once you've passed multiple argument types into a function, so if you run a test case that passes in ints, and then run a test case that passes in floats, the second test case will be slower for no obvious reason. You can swap the test cases around and the second run will still be slower.

(There are actually a huge list of problems with javascript microbenchmarks, and jsperf only adds to them by being low quality software. Please use it sparingly.)

I can't say for arguments, but optimizing for a changing array.length in-loop must be difficult if not impossible.

for(var i=0;i<a.length;i++) if(check(a[i])) a.push('foo');

Compiler optimizations are never perfect. In this case, a compiler would just assume that push could be called and not hoist the length calculation.

JavaScript is complex enough that pretty much any code inside of the loop could end up doing an array push. Even `console.log(myCompletelyUnrelatedObject.x)` (given an evil property descriptor).

Not if the function is inlineable or an intrinsic (console.log will likely be either), which is the most basic trick of any JIT.

Unless you can specifically measure caching the length is faster, I wouldn't do it. Most of the time it doesn't matter anyway (won't cause a bump in performance), and even then most of the time the compiler will be able to figure it out for you.

Maybe my comment was misleading - the important part is the property read, not the `console.log`. The following code might be an infinite loop in JavaScript:

  function adder(arr, obj) {
    for (var i = 0; i < arr.length; ++i) {
      obj.x += i;
    }
  }

  var arr = [1];
  var obj = Object.defineProperties({}, {
    x: {
      get: function() { return 1; },
      set: function(v) { arr.push(v); }
    }
  };
  adder(arr, obj);

V8 can inline getters and setters like it can inline normal functios.

I don't know a whole lot about JIT compilers, but would it be possible to emit code with length optimized, and trap changes to it to fall back to a slow path in a way that wouldn't hurt the fast path? For example, you might mark the array so that when other code mutates it, that code also modifies the return address on the stack to point to some fixup code that puts you onto the slow path.

I don't know much about this, either, but I don't think that is a feasible approach.

- where are you going to 'mark the array'? Does that mean every array gets the overhead of having room for that mark or do these marks live elsewhere? If so, where, and how is code checking it going to be performant?

- in nested calls, are you going to allow multiple marks? (Solvable, I think, as you can get away with an integer mark count)

- that would mean that all code that modifies any array must check whether such a mark is present and then find the return address on the stack (and nested return addresses)

- even if you do all of the above, the simple checking for presence of such a mark can kill performance in tight loops, even if you do that with branch prediction hints.

- how do you know what mutating changes are important for the calling code? You can use a function pointer as the 'mark' and call that so that it can figure it out by itself, but that surely will kill performance in tight loops.

I think the normal way is for compiled functions to detect when their own assumptions (may) no longer hold, not for other code to signal any compiled code on the stack that its assumptions (may) no longer hold. In tight frequently run code, you may be able to inline calls and recompile, but that is costly, too.

EDIT: I just realize that it is possible to do something in the spirit of this without needing any marks. The really bad calls, such as those to eval, will have to tell the JIT compiler that the current game is over, and that they can start over. It is too costly to do that from any innocuous call, such as that which adds an item to an array, though.

As to that length optimization: it use to say that C doesn't have a for loop; because it evaluates the end condition through every iteration, its 'for' is a 'while' in disguise. Pascal, on the other hand, has a for loop.

JavaScript inherits that IMO bad decision.

Can you elaborate? "pretty sure" sounds like a hunch rather than actual data.

The article is "optimisation killers", you're right about caching the array length lookup check being faster, but it doesn't kill V8's ability to optimise functions like the rest of the examples do