CODEWITHSUNDEEP
javascriptperformance
Joppy
Joppy

Reputation: 403

Allocation-free abstractions in Javascript

I have a general question which is about whether it is possible to make zero-allocation iterators in Javascript. Note that by "iterator" I am not married to the current definition of iterator in ECMAScript, but just a general pattern for iterating over user-defined ranges.

To make the problem concrete, say I have a list like [5, 5, 5, 2, 2, 1, 1, 1, 1] and I want to group adjacent repetitions together, and process it into a form which is more like [5, 3], [2, 2], [1, 4]. I then want to access each of these pairs inside a loop, something like "for each pair in grouped(array), do something with pair". Furthermore, I want to reuse this grouping algorithm in many places, and crucially, in some really hot inner loops (think millions of loops per second).

Question: Is there an iteration pattern to accomplish this which has zero overhead, as if I hand-wrote the loop myself?

Here are the things I've tried so far. Let's suppose for concreteness that I am trying to compute the sum of all pairs. (To be clear I am not looking for alternative ways of writing this code, I am looking for an abstraction pattern: the code is just here to provide a concrete example.)

Inlining the grouping code by hand. This method performs the best, but obscures the intent of the computation. Furthermore, inlining by hand is error-prone and annoying.

function sumPairs(array) {
  let sum = 0

  for (let i = 0; i != array.length; ) {
    let elem = array[i++], count = 1
    while (i < array.length && array[i] == elem) { i++; count++; }
    
    // Here we can actually use the pair (elem, count)
    sum += elem + count
  }

  return sum
}

Using a visitor pattern. We can write a reduceGroups function which will call a given visitor(acc, elem, count) for each pair (elem, count), similar to the usual Array.reduce method. With that our computation becomes somewhat clearer to read.

function sumPairsVisitor(array) {
  return reduceGroups(array, (sofar, elem, count) => sofar + elem + count, 0)
}

Unfortunately, Firefox in particular still allocates when running this function, unless the closure definition is manually moved outside the function. Furthermore, we lose the ability to use control structures like break unless we complicate the interface a lot.

Writing a custom iterator. We can make a custom "iterator" (not an ES6 iterator) which exposes elem and count properties, an empty property indicating that there are no more pairs remaining, and a next() method which updates elem and count to the next pair. The consuming code looks like this:

function sumPairsIterator(array) {
  let sum = 0
  for (let iter = new GroupIter(array); !iter.empty; iter.next())
    sum += iter.elem + iter.count
  return sum
}

I find this code the easiest to read, and it seems to me that it should be the fastest method of abstraction. (In the best possible case, scalar replacement could completely collapse the iterator definition into the function. In the second best case, it should be clear that the iterator does not escape the for loop, so it can be stack-allocated). Unfortunately, both Chrome and Firefox seem to allocate here.

Of the approaches above, the custom-defined iterator performs quite well in most cases, except when you really need to put the pedal to the metal in a hot inner loop, at which point the GC pressure becomes apparent.

I would also be ok with a Javascript post-processor (the Google Closure Compiler perhaps?) which is able to accomplish this.

Upvotes: 1

Views: 115

Answers (1)

Thomas
Thomas

Reputation: 12657

Check this out. I've not tested its performance but it should be good.

(+) (mostly) compatible to ES6 iterators.
(-) sacrificed ...GroupingIterator.from(arr) in order to not create a (imo. garbage) value-object. That's the mostly in the point above.
afaik, the primary use case for this is a for..of loop anyways.
(+) no objects created (GC)
(+) object pooling for the iterators; (again GC)
(+) compatible with controll-structures like break

class GroupingIterator {
  /* object pooling */
  static from(array) {
    const instance = GroupingIterator._pool || new GroupingIterator();
    GroupingIterator._pool = instance._pool;
    instance._pool = null;

    instance.array = array;
    instance.done = false;

    return instance;
  }

  static _pool = null;
  _pool = null;

  /* state and value / payload */

  array = null;
  element = null;
  index = 0;
  count = 0;

  /* IteratorResult interface */

  value = this;
  done = true;

  /* Iterator interface */

  next() {
    const array = this.array;
    let index = this.index += this.count;

    if (!array || index >= array.length) {
      return this.return();
    }

    const element = this.element = array[index];
    while (++index < array.length) {
      if (array[index] !== element) break;
    }
    this.count = index - this.index;
    return this;
  }

  return() {
    this.done = true;
    // cleanup
    this.element = this.array = null;
    this.count = this.index = 0;

    // return iterator to pool
    this._pool = GroupingIterator._pool;
    return GroupingIterator._pool = this;
  }
  
  /* Iterable interface */

  [Symbol.iterator]() {
    return this;
  }
}


var arr = [5, 5, 5, 2, 2, 1, 1, 1, 1];

for (const item of GroupingIterator.from(arr)) {
  console.log("element", item.element, "index", item.index, "count", item.count);
}

Upvotes: 1

Related Questions