Hacker News Reader

Comment by throwaway_yy2Di | Hacker News Reader

I think in most cases where you'd worry about JS array performance you should use actual numeric arrays [0] rather than the kitchen sink Array(). Also, I think those function abstractions have a pretty significant overhead?

[0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Type...

(edit): Yeah, the abstraction overhead is ridiculous. Here's the forEach() benchmark again, compared to an explicit for loop (no function calls):

    // new benchmark in bench/for-each.js    

    exports['explicit iteration'] = function() {
        acc = 0;
        for (var j=0; j<input.length; ++j) {
            acc += input[j];
        }
    }

  Native .forEach() vs fast.forEach() vs explicit iteration
    ✓  Array::forEach() x 2,101,860 ops/sec ±1.50% (79 runs sampled)
    ✓  fast.forEach() x 5,433,935 ops/sec ±1.12% (90 runs sampled)
    ✓  explicit iteration x 28,714,606 ops/sec ±1.44% (87 runs sampled)

    Winner is: explicit iteration (1266.15% faster)

(I ran this on Node "v0.11.14-pre", fresh from github).

View on HN

I used this in a Firefox OS app, inside an implementation of Dijkstra's algorithm and an accompanying binary heap, and while I haven't run any rigorous benchmarks, I can say the runtime felt way better on my test phone when I rewrote the algorithm to use the typed arrays.

This is very often overlooked but extremely useful for implementations of fast algorithms in JavaScript that should scale to a lot of input data.

One other micro optimization for you. Assuming the length of the array does not change in the operation, this is usually faster:

    for (var j=0, len=input.length; j < len; ++j) {

This prevents rechecking the array length on every iteration.

I actually didn't get any speedup with that one -- looks like V8 can optimize that already. But you're right, that's an important one on some browsers.

You can squeeze out another factor of 2 with typed arrays:

    var input_typed = new Uint32Array(input)
    
    exports['numeric typed array'] = function() {
        var acc = 0;
        for (var j=0; j<input_typed.length; ++j) {
            acc += input_typed[j];
        }
    }

    ✓  Array::forEach() x 1,999,244 ops/sec ±2.93% (84 runs sampled)
    ✓  fast.forEach() x 5,161,137 ops/sec ±2.05% (85 runs sampled)
    ✓  explicit iteration x 27,851,200 ops/sec ±1.32% (86 runs sampled)
    ✓  explicit iteration w/precomputed array limit x 28,567,527 ops/sec ±1.33% (86 runs sampled)
    ✓  numeric typed array x 42,951,837 ops/sec ±0.97% (88 runs sampled)

    Winner is: numeric typed array (2048.40% faster)

And probably more still if you can figure out the asm.js incantation that makes everything statically typed.

The optimisation mentioned by the grandparent is specific to looping overso-called "live" collections of the DOM. NodeList [0] is sometimes a live collection, and is the return type of querySelectorAll, so it's likely you've dealt with this type of collection.

The reason it incurs an overhead is because the DOM is traversed every single time the property is read, to ensure nothing has changed. You can see why caching the length is a reasonable optimisation, as you're unlikely to be modifying the collection while looping.

[0] https://developer.mozilla.org/en/docs/Web/API/NodeList

Exactly. Although, I am curious if there's a reason the JS engine (possibly working with the DOM implementation) can't optimize that to one look-up, if the JS in the loop doesn't change that part of the DOM or call anything that forces it to yield.

I suspect a lot of the optimization opportunity in browsers today is less about JS or DOM in isolation but more about ways they could work together to improve situations like this one.

(Note: I understand this one is solvable by a proficient/attentive developer, but not all developers are like that, and not all such DOM/JS transition problems are as easily solvable from your JS code)

The length is not recalculated on every pass. However it's slightly faster.

http://stackoverflow.com/questions/17989270/for-loop-perform...

regarding your edit, you're exactly right, of course a for loop will be faster. Sometimes you really do need a function call though, in which case fast forEach and map implementations become more useful.

The next step for fast.js are some sweet.js macros which will make writing for loops a bit nicer, because it's pretty painful to write this every time you want to iterate over an object:

    var keys = Object.keys(obj),
        length = keys.length,
        key, i;
    for (i = 0; i < length; i++) {
      key = keys[i];
      // ...
    }

I'd rather write:

   every key of obj {
     // ...
   }

and have that expanded at compile time.

Additionally there are some cases where you must use inline for loops (such as when slicing arguments objects, see https://github.com/petkaantonov/bluebird/wiki/Optimization-k...) and a function call is not possible. These can also be addressed with sweet.js macros.

To be fair, it's not obvious if you're not a JS expert: coming from some other language, you could naively assume that function call gets inlined, with no overhead.

A few months ago, I tried some image processing with JS and the canvas object (big Arrays).

They have a structure like image[pixel].color

What I found was, always traversing the object structure was much slower than putting every pixel color as an argument in a function, that gets called every iteration.

So I had the impression, reasonable simple function, like a greyscale filter, get inlined by engines like V8.

You probably would have been better off with typed arrays and fragment shaders, if you were going for performance.

Aren't the arrays produced by a canvas object typed?

Yep, but they only become performant when you treat them as such instead of doing naive e.g. multiplication. See: https://hacks.mozilla.org/2011/12/faster-canvas-pixel-manipu...

Like any other compiler, function calls sometimes get inlined. And sometimes not. Depending on compiler heuristics of various sorts.

Note that 'in'

    for (key in object)

is for getting keys, in Firefox, meanwhile 'of'

     for (value of iterator)

is for getting values out of an Iterator.

Most of the array methods are explicitly defined in terms of indexing rather that iterators, so for(of) is incorrect. On the other hand indexing is still faster than iteration in the major implementations.

My comment were intended as a direct reply to phpnode's code, 'ignoring' the rest of the thread.

How do you mean when you state that for(of) is incorrect?

Perhaps this 'example' clears something up?

  « for (value in {a:1,b:2,c:3,d:4,e:5}) console.log(value)
  » undefined
    "a"
    "b"
    "c"
    "d"
    "e"
  « for (value of {a:1,b:2,c:3,d:4,e:5}) console.log(value)
  × TypeError: ({a:1, b:2, c:3, d:4, e:5})['@@iterator'] is not a function

the only issue is i'd like to differentiate between iterating arrays and objects at the syntax level. Coffeescript uses `in` for arrays and `of` for objects, but I agree that becomes confusing. Open to other suggestions!

That's a though one. I know I can't think of any that aren't either verbose or nondescript.

But if Coffescript can walk away with its choice then I don't think you'll have anything to worry about.

I've been spending some time thinking about CoffeeScript's choice for `in` and `of` and I think I have the answer: they should be more regular. One (probably `of`) should be used for the keys/indexes and the other (probably `in`) should be used for contents.

These are legal CoffeeScript examples:

    for key, value of object
    if key of object

    for value in array
    if value in array

    for index, value of array
    if index of array

The one that's missing is:

    for value in object
    if value in object

The issue with coffeescript is that it uses the opposite syntax to JS - `in` for arrays instead of objects. ES6 introduces the `of` keyword for real iterators so i don't really want to use that for either of them. It's tricky. There are other options but they're verbose

    every element as key, value from arr {
      console.log(key, value);
    }

    every property as key, value from obj {
      console.log(key, value);
    }

Thoughts on this?

    every [key, value] from arr {
      console.log(key, value);
    }

    every {key, value} from obj {
      console.log(key, value);
    }

    every [key] from arr {
      console.log(key);
    }

    every {_, value} from obj {
      console.log(value);
    }

Looks a bit cramped to me but I get the impression that array comprehension is one of the major reasons that people use Coffeescript, so perhaps it's not too much trouble?

There's also the issue with some fonts making it hard to differentiate between { and [ but it's an idea that might be worth to think about at least.

I quite like this suggestion. If we flip the key, value around to make it inline with what forEach etc do, then we don't need the placeholder for iterating without the key:

    fast-each [value] from arr {

    }

    fast-each {value} from obj {

    }
 
    fast-each [value, key] from arr {

    }

    fast-each {value, key} from obj {

    }

The disadvantage is that this looks like array comprehension but isn't.

Alternative:

    fast-properties key, value from obj {

    }

    fast-elements index, value from arr {

    }

    fast-properties value from obj {

    }

    fast-elements value from arr {

    }

Reply on news.ycombinator.com