Performance: Improved performance for async iterables

[jeswr]

What is the problem this feature will solve?

I have recently been working on optimizations for this implementation of Asynchronous iterators. I did a quick benchmark between that implementation; and the Readable API for Node v17.4.0 and found that some of the latest of our optimizations (yet to be released) we have are orders of magnitude faster than the Readable API. As an example, we can apply 10 maps to 200_000 elements in 20ms, whilst it takes the Readable API ~2s (tested on DELL XPS 15, 32 GB RAM).

import { ArrayIterator } from './dist/asynciterator.js'
import { Readable } from 'stream';

async function test(fn) {
  let j = 0;
  const arr = new Array(200_000).fill(true).map(() => j++);
  let iterator = fn(arr)

  for (let i = 0; i < 10; i++) {
    iterator = iterator.map(x => x + 1)
  }

  const now = performance.now();
  return await new Promise((res) => iterator.on('data', () => {}).on('end', () => {
    res(performance.now() - now);
  }))
}

console.log('ArrayIterator', await test(arr => new ArrayIterator(arr)));
console.log('Readable.from', await test(arr => Readable.from(arr)))

Implementation	Time (ms)
ArrayIterator	20.243778005242348
Readable.from	2403.212348997593

The recent optimizations we have done include:

• Truncating arrays, and using linkedlists for internal buffers to get around performance issues with Array.shift in the V8 engine (Performance: make Array.shift an O(1) operation. #42449)
• 'Pre-compiling' chained operations

This (somewhat long) issue is where we have had most of the discussion around the recent improvements we have been working on.

What is the feature you are proposing to solve the problem?

Use some of the optimizations already implemented in https://github.com/RubenVerborgh/AsyncIterator, RubenVerborgh/AsyncIterator#59

What alternatives have you considered?

No response

[mscdex]

Are the suggested changes passing all of node's tests?

[jeswr]

It wouldn't because this library is missing a few elements that the Readable API has (for instance it doesn't expose a few read-only properties such as readableFlowing etc.) - though there is a PR to add some more of those properties in (RubenVerborgh/AsyncIterator#45), which also improved the perf. of the AsyncIterator library by ~5-10% in cases like the one given above.

[mscdex]

If it passes all tests, then feel free to submit a PR.

[benjamingr]

@nodejs/streams

[benjamingr]

Hey, thanks for asking. I don't think we spent a lot of time optimizing this area in the past and were mostly waiting for people to ask.

Is the ask specifically to make async iterators for Readable.from(largeArray) fast?

[ronag]

I don't think we can just replace the current implementation. Would break too much stuff.

[benjamingr]

I don't think we can just replace the current implementation. Would break too much stuff.

The current implementation doesn't refer to the whole of Readable (The AsyncIterator package doesn't contain 10% of the functionality of streams or stuff like watermarks).

I think the ask is to improve our performance for the async iterator API for Readable?

[ronag]

I think the ask is to improve our performance for the async iterator API for Readable?

I'm not sure what the ask here is. 😕

[ronag]

Use some of the optimizations already implemented in https://github.com/RubenVerborgh/AsyncIterator, RubenVerborgh/AsyncIterator#59

I think this needs to be a bit more specific... I'm not sure what optimisations we should apply.

[benjamingr]

For from, probably just adding a special case for arrays to avoid all the iteration objects should be fine?

diff --git a/lib/internal/streams/from.js b/lib/internal/streams/from.js
index d3d43f7dfb..ad2afa578c 100644
--- a/lib/internal/streams/from.js
+++ b/lib/internal/streams/from.js
@@ -25,10 +25,28 @@ function from(Readable, iterable, opts) {
     });
   }
 
+  if (Array.isArray(iterable)) {
+    let i = 0;
+    return new Readable({
+      objectMode: true,
+      ...opts,
+      read() {
+        if (i < iterable.length) {
+          this.push(iterable[i++]);
+        } else {
+          iterable.push(null);
+        }
+      }
+    });
+  }
+
+
   let isAsync;
   if (iterable && iterable[SymbolAsyncIterator]) {
     isAsync = true;
     iterator = iterable[SymbolAsyncIterator]();
   } else if (iterable && iterable[SymbolIterator]) {
     isAsync = false;
     iterator = iterable[SymbolIterator]();

I'm not sure it's worth it though? Statically creating readables with .from is probably not a hot path? (is it for your use case @jeswr ?)

[ronag]

We could probably make that even faster by just injecting the array as the readable's buffer. But again this seems like a quite unusual use case.

[mcollina]

I don't really understand what's the use case for this. I'm totally ok to have the perf improvement in, but what are we optimizing for in this case? I would not recommend anyone to process an Array using an AsyncIterator, it'll definitely be slower than just processing the Array.

[jeswr]

Apologies for the lack of clarity in my original issue. The main point was to highlight that there is room to make pull-based/Asynchronous streams a lot faster which has the potential to speed up downstream applications; I see where the choice to benchmark using Readable.from may have caused confusion. @jacoscaz reported to me that he has applications (not using Readable.from or its equivalent) that are now 600-900x as a result porting from using Readable to using the current release of the Asynciterator package.

I also note that I'm not intimately familiar with he nodejs codebase - and all comments are based on the observed performance comparison between Readable, and the Asynciterator package.

The ask is more specifically to optimize (in order of importance) the speed of:
(1) Internal buffers by using linked lists
(2) Transformations of pull-based/asynchronous iterators. Specifically the case of applying several synchronous transformations such as synchronous map/filter/skip etc. can be made a lot faster; we have done this optimization in RubenVerborgh/AsyncIterator#59 with more discussions around its performance gains in RubenVerborgh/AsyncIterator#58. The overarching idea is to apply all the transforms in a single read and skip any intermediary buffers.
(3) The speed of Readable.from by truncating the array on load

Once/if these have been applied then there are potentially some further optimisations that can be looked into based on the thread I linked to in my original message.

[mcollina]

@jeswr I'm not sure I follow. Readable.from() is primarily an utility to convert to a node stream.Readable, which allow plenty of things - including piping. There are plenty of way to make it faster, however it would deeply break backward compatibility for all things that depends on Stream.