optimization: Reduce overhead of SimpleTransformIterator

[jeswr]

For basic methods like .map and .filter, on AsyncIterator, using the SimpleTransformIterator introduces uneccessary overhead via the readAndTransformSimple operator. To improve performance in applications like Comunica it may be worth creating custom iterators with simpler read methods; for instance a synchronous MapIterator could skip buffering entirely and just be implemented as something like

export class MapIterator<T, S> extends AsyncIterator<S> {
    ...
    read() {
       if ((item = source.read()) !== null)
          return this.map(item);
    }
}

@jacoscaz I suspect this is the cause of the potential slowdown you were encountering when doing a large amount of chaining.

[jacoscaz]

Indeed, chained buffering steps might explain the slowdowns I’ve seen. Normally I would expect performance to slow down linearly with the number of chained transforms but often I see slowdowns that seem somewhat exponential. I had been under the impression that methods such as map() and filter() behaved as you described but, given this issue, I was either plain wrong or possibly remembering a previous version. This would be a great addition to asynciterator itself but we could do it separately if better for backward compat.

However, I do not have hard numbers at hand. @jeswr have you done some profiling on this?

[rubensworks]

@jeswr Do you think think the slowdown is caused by the complexity of the code in readAndTransformSimple, or the fact that it fills an internal buffer? If the latter, just disabling the buffer on intermediary iterators might also improve overall performance.

[jeswr]

@rubensworks I'd suspect you're correct in that the intermediary buffers are the main overhead.

I was thinking that one way around this is to have a 'chained transform' which applies multiple map/filter/transform operations in one go, so long as each part of that chain is synchronous - is this equivalent to what you mean by disabling internal buffers?

[jeswr]

@jacoscaz - no I have not done profiling, it was just an observation I made when digging through the code when working on a PR I made earlier

[jacoscaz]

I was thinking that one way around this is to have a 'chained transform' which applies multiple map/filter/transform operations in one go

Would this not require knowing what those transformations look like ahead of time? Unless, perhaps, one were to have all intermediate actors return a transform function and have the final actor concatenate these.

However, if all intermediate steps were to be implemented as iterators without internal buffering as you suggested, provided an initial buffered iterator for I/O queries (i.e. reading from a file), the resulting performance should not be too far from that of a pure concatenation of functions while allowing to keep the current internal structure.

We should come up with a couple of examples that clearly demonstrate whether there’s a real issue here or not. One possible way of doing this would be to manually implement a no-buffering map iterator and profile it against the current map(). I’d be up for that if nobody has time to do so, there’s potential for a great return of investment.

[jeswr]

Would this not require knowing what those transformations look like ahead of time?

I was thinking that methods like map, filter and transform would add to the internal set of operations that need to be done and then return the same iterator. The major caveat of this being that this would affect upstream reads of the iterator if there are any

I’d be up for that if nobody has time to do so

That sounds great but I'd wait for #43 to be merged as there may introduce some small performance changes

[jacoscaz]

I was thinking that methods like map, filter and transform would add to the internal set of operations that need to be done and then return the same iterator.

I suspect that the concatenation mechanism might be a non-trivial one, and it would have to be instantiated even for single-op iterators unless we were to make it a lazy one, which would make it more complicated. Nonetheless, I think there’s definitely something to be said for combining operations. For example, could Comunica benefit from a mapFilter() iterator?

In any case, we should probably look at these as orthogonal issues:

1. on one side we have buffering, and the possibility that disabling buffering in intermediate iterators might result in gains when dealing with long-ish chains;

2. on a different side we have combining N transformations into M < N iterators, and the possibility that doing so might reduce avg chain length.

Both definitely sound worth investigating IMHO.

I'd wait for #43 to be merged as there may introduce some small performance changes

Seems reasonable! I may start setting up a simple benchmark and then pause and wait for that PR to be merged.

[RubenVerborgh]

Is the SimpleTransformIterator being used in performance-sensitive code?

My goal for it was to be used for simple cases—and definitely not for chaining.
I guess I should have been more explicit about that.

For chaining, you want to define your own sync or async transform iterator.

[jeswr]

Because of this the use of .map, .filter, .transform etc. all create a new SimpleTransformIterator and hence there are many places in Comunica that create new SimpleTransformIterators for instance

Mapping:

• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/bus-rdf-update-quads/lib/ActorRdfUpdateQuadsDestination.ts#L13
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-rdf-resolve-hypermedia-qpf/lib/RdfSourceQpf.ts#L196-L199
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-rdf-resolve-quad-pattern-federated/lib/FederatedQuadSource.ts#L270
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-rdf-join-inner-multi-bind/lib/ActorRdfJoinMultiBind.ts#L60
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-rdf-join-inner-multi-bind/lib/ActorRdfJoinMultiBind.ts#L72
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-query-operation-project/lib/ActorQueryOperationProject.ts#L52-L60
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-query-operation-project/lib/ActorQueryOperationProject.ts#L67-L83
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-query-operation-values/lib/ActorQueryOperationValues.ts#L31-L32

(and thats only going up to page 3/10 in searching for .map in https://github.com/comunica/comunica/search?p=3&q=.map)

Filtering:

• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-query-operation-reduced-hash/lib/ActorQueryOperationReducedHash.ts#L29
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-rdf-join-minus-hash/lib/ActorRdfJoinMinusHash.ts#L43
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-rdf-join-minus-hash-undef/lib/ActorRdfJoinMinusHashUndef.ts#L43
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-rdf-resolve-hypermedia-qpf/lib/RdfSourceQpf.ts#L163-L173 (not sure why this one is using .transform over .filter @rubensworks )
• https://github.com/comunica/comunica/blob/4c66bfaa44f73786bc7403504e5fe571181430c7/packages/actor-rdf-resolve-quad-pattern-federated/lib/FederatedQuadSource.ts#L273

Given how commonly this is used I think it is worth making the change upstream here in this package

[RubenVerborgh]

Absolutely, thanks for finding this. We probably want:

• Dedicated MapIterator, FilterIterator, …
• A check within the SimpleTransformIterator that, if only map or filter are requested, one of the dedicated iterators is instantiated instead.

[jacoscaz]

@jeswr could you have a look at this gist of mine? https://gist.github.com/jacoscaz/e20812991714092dbb20cfd432d1bf00

Either I got something wrong or there's virtually no performance difference between .map() and a dedicated mapping iterator.

[jeswr]

To summarize the results I have in the following comments

1. ArrayIterator causes about a 5x speed degradation compared to range iterator on 20000 elements (because as I raised here the V8 implementation of Array.shift is still very suboptimal).
2. Using the range iterator on 20000 elements and using custom MapIterator / FilterIterators we see approx. an 8x improvement.
3. Using my PR which avoids scheduling a few unnecessary tasks (ie just calling the end event straight away where possible creates a further 10% improvement.)
4. Using a CompositeTransform that reduces over all of the maps and filters causes a further 10-15% performance improvement when compared to simply creating 50 new Map and Filter iterators
5. Pre-compile the transformation pipeline on the CompositeTransform and observe a 50%-100% performance gain

Combining all of these factors can result in a speed-up of 100x or greater when doing 50 map/filters on 20000 elements; and similar results when we do smaller numbers of map/filters (e.g. 5).

This gist includes some experiments and results that are discussed in the following comments.

---

@jacoscaz - The vast majority of your time is spent on the array iterator because of #38; I believe node does not implement similar optimizations to firefox. (@RubenVerborgh for reference; my machine took about 5x times longer to run the implementation @jacoscaz had using the array iterator).

I get the following results for the code I have attached below

ArrayIterator#map(): 145
MappingIterator: 19

if you do 50 mappings the results become

ArrayIterator#map(): 1005
MappingIterator: 143

now here is where it gets more interesting - if we use the array iterator for 50 mappings we get

ArrayIterator#map(): 5321
MappingIterator: 4698

So this means that with a combination of optimizing the ArrayIterator and using the MappingIterator there is a 35-40x performance increase to be had for 50 chaining operations (and for 5 chaining operations the problems of the ArrayIterator become even more pronounced; observing a 200x difference in results).

import {AsyncIterator, range} from 'asynciterator';

class MappingIterator<I, O> extends AsyncIterator<O> {
  constructor(source: AsyncIterator<I>, map: (item: I) => O) {
    super();
    source.on('end', () => {
      this.close();
    });
    source.on('readable', () => {
      this.emit('readable');
    });
    let item: I | null;
    this.read = (): O | null => {
      return ((item = source.read()) !== null)
        ? map(item)
        : null;
    };
  }
}

const time = (createStream: (max: number) => AsyncIterator<number>): Promise<number> => {
  const max = 200000
  const str = createStream(max);
  let count = 0;
  return new Promise((resolve, reject) => {
    const now = Date.now();
    str.on('data', () => {
      count += 1;
    })
      .on('end', () => {
        const then = Date.now();
        if (count != max + 1) {
          reject(new Error('Bad count'));
          return;
        }
        resolve(then - now);
      });
  })
}

const main = async () => {
  const mapMethodTime = await time((max) => {
    let iterator: AsyncIterator<number> = range(0, max);
    for (let i = 0; i < 5; i++) {
      iterator = iterator.map(item => item);
    }
    return iterator;
  });
  const mappingIteratorTime = await time((max) => {
    let iterator: AsyncIterator<number> = range(0, max);
    for (let i = 0; i < 5; i++) {
      iterator = new MappingIterator(iterator, item => item);
    }
    return iterator;
  });
  console.log(`ArrayIterator#map(): ${mapMethodTime}`);
  console.log(`MappingIterator: ${mappingIteratorTime}`);
};

main().catch((err) => {
  console.error(err);
  process.exit(1);
});

Environment:

npm v8.4.1
node v17.4.0

Run on Dell XPS15 with 32G RAM

[jeswr]

With the PR (#45) I have made I get; for the ArrayIterator method

ArrayIterator#map(): 5532
MappingIterator: 4770

and for the range method I get

ArrayIterator#map(): 944
MappingIterator: 126

As a summary, using the range iterator and doing 50 transformations we get

	Current Version	New PR
ArrayIterator#map()	1005	944
MappingIterator	143	126

To do this I used the following MapIterator

class MappingIterator<I, O> extends AsyncIterator<O> {
  constructor(source: AsyncIterator<I>, map: (item: I) => O) {
    super();
    source.on('end', () => {
      this.close();
    });
    source.on('readable', () => {
      this.emit('readable');
    });
    let item: I | null;
    this.read = (): O | null => {
      const item = source.read();
      if (item === null) {
        // @ts-ignore
        if (this._state === CLOSED)
          this._end();
        return null
      }
      return map(item);
    };
  }
}