node
node copied to clipboard
nodejs
lib: performance improvement on readline async iterator
Using a direct approach to create the readline async iterator allowed an iteration over 20 to 58% faster.
BREAKING CHANGE: With that change, the async iteterator obtained from the readline interface doesn't have the property "stream" any longer. This happened because it's no longer created through a Readable, instead, the async iterator is created directly from the events of the readline interface instance, so, if anyone is using that property, this change will break their code. Also, the Readable added a backpressure control that is fairly compensated by the use of FixedQueue + monitoring its size. This control wasn't really precise with readline before, though, because it only pauses the reading of the original stream, but the lines generated from the last message received from it was still emitted. For example: if the readable was paused at 1000 messages but the last one received generated 10k lines, but no further messages were emitted again until the queue was lower than the readable highWaterMark. A similar behavior still happens with the new implementation, but the highWaterMark used is fixed: 1024, and the original stream is resumed again only after the queue is cleared.
Before making this change, I created a package implementing the same concept used here to validate it. You can find it here if this helps anyhow.
@benjamingr during our little discussion about the setImmediate, I took a look in the EventEmtter class just before you pointed out that the listeners are called in inclusion order in most of the cases, and notice that the _events property is an array when there's more than one listener, which means that prependListener and addListener operations take O(N) to complete. Those could be improved to O(1) using a Map + a Linked list to preserve the execution order, without causing any breaking change. Do you think it's worth it to do it? I could do another PR with that.
@benjamingr during our little discussion about the setImmediate, I took a look in the EventEmtter class just before you pointed out that the listeners are called in inclusion order in most of the cases, and notice that the _events property is an array when there's more than one listener, which means that prependListener and addListener operations take O(N) to complete. Those could be improved to O(1) using a Map + a Linked list to preserve the execution order, without causing any breaking change. Do you think it's worth it to do it? I could do another PR with that.
Do it on a separate PR: we'll benchmark! Historically we could not change that because modules in the ecosystem relied on _events.
@Farenheith may I ask you to avoid force pushing the PR? It makes it harder to follow what's happening for reviewers. Don't worry, our tooling will squash all subsequent commits into the first one when landing, you don't have to do it yourself (except if there's a git conflict, in that case, sure rebasing and force pushing is still the best option).
@aduh95
Oh sure! I got the guidelines wrong then, sorry. I thought I need to keep just one commit. I'll not do that again
I got the guidelines wrong then, sorry.
That's not on you, it demonstrates that our docs could use some clarification. Would you be interested in sending a PR that updates those guidelines? (or if you prefer not to do it yourself, you can point me to where you saw those misguiding guidelines and I can work on a PR on my end)
I got the guidelines wrong then, sorry.
That's not on you, it demonstrates that our docs could use some clarification. Would you be interested in sending a PR that updates those guidelines? (or if you prefer not to do it yourself, you can point me to where you saw those misguiding guidelines and I can work on a PR on my end)
Yeah, I can do that.
Edit: Here it is, https://github.com/nodejs/node/pull/41287
Do it on a separate PR: we'll benchmark! Historically we could not change that because modules in the ecosystem relied on
_events.
@mcollina I just did it here https://github.com/nodejs/node/pull/41309 :). I opened it so you guys can have a look at the idea, but I'm still thinking about how can I benchmark it, and if it really makes sense, as, generally, the number of listeners that are added to each event is quite limited.
@Farenheith happy to help running the benchmarks it can be a bit tricky. They run code before/after a change and then perform a statistical significance test to verify the changes are indeed better/worse.
There are instructions here: https://github.com/nodejs/node/tree/master/benchmark#nodejs-core-benchmarks
For events, you would find the benchmarks here https://github.com/nodejs/node/tree/master/benchmark/events - there is a guide on running/authoring them here https://github.com/nodejs/node/blob/master/doc/guides/writing-and-running-benchmarks.md
I'd like to apologize for my (our?) lack of responsiveness I've been sick (worse than I've been since I was a kid) for about a month and am recovering now (not covid, just a stomach thing).
Wanted to emphasize you are welcome to reach out to discuss in a less asynchronous matter (email/facebook/slack/whatsapp whatever)
@benjamingr you are all actually quite responsive, you don't have to apologize for anything. I'm very happy with the attention I got here, It really invites me to contribute more. Thank you for the guidance about benchmarking, I'll look into it next week. I also think that your answer was meant to be sent in my other PR (https://github.com/nodejs/node/pull/41309), but that's all good, I'll use it to benchmark both of them!
Good night, folks.
@benjamingr @mcollina @aduh95 I just finished creating a benchmark for the readline iterable and ran it. The generated csv is here: compare-pr-41309.csv And the statistical results are here:
confidence improvement accuracy (*) (**) (***)
readline/readline-iterable.js n=10 *** 31.16 % ±6.56% ±8.75% ±11.44%
readline/readline-iterable.js n=100 *** 56.14 % ±5.35% ±7.15% ±9.35%
readline/readline-iterable.js n=1000 *** 82.18 % ±7.10% ±9.47% ±12.39%
readline/readline-iterable.js n=10000 *** 88.41 % ±5.65% ±7.52% ±9.78%
readline/readline-iterable.js n=100000 *** 78.56 % ±3.94% ±5.26% ±6.88%
readline/readline-iterable.js n=1000000 *** 83.11 % ±2.95% ±3.92% ±5.11%
Be aware that when doing many comparisons the risk of a false-positive result increases.
In this case, there are 6 comparisons, you can thus expect the following amount of false-positive results:
0.30 false positives, when considering a 5% risk acceptance (*, **, ***),
0.06 false positives, when considering a 1% risk acceptance (**, ***),
0.01 false positives, when considering a 0.1% risk acceptance (***)
Please take some time when you can to check if everything is alright with the new benchmark and a happy new year for all of you!
Edit: I notice that I had a lint problem and, fixing the lint, a minor problem in the benchmark, so after I fixed it I ran it again! The generated CSV is here: compare-pr-41309-2.csv The statistical results are here:
confidence improvement accuracy (*) (**) (***)
readline/readline-iterable.js n=10 *** 29.91 % ±4.82% ±6.46% ±8.50%
readline/readline-iterable.js n=100 *** 52.56 % ±4.76% ±6.36% ±8.34%
readline/readline-iterable.js n=1000 *** 84.24 % ±5.21% ±6.94% ±9.03%
readline/readline-iterable.js n=10000 *** 83.50 % ±3.87% ±5.17% ±6.78%
readline/readline-iterable.js n=100000 *** 77.76 % ±3.31% ±4.42% ±5.80%
readline/readline-iterable.js n=1000000 *** 78.52 % ±2.16% ±2.89% ±3.78%
Be aware that when doing many comparisons the risk of a false-positive result increases.
In this case, there are 6 comparisons, you can thus expect the following amount of false-positive results:
0.30 false positives, when considering a 5% risk acceptance (*, **, ***),
0.06 false positives, when considering a 1% risk acceptance (**, ***),
0.01 false positives, when considering a 0.1% risk acceptance (***)
Benchmark CI: https://ci.nodejs.org/view/Node.js%20benchmark/job/benchmark-node-micro-benchmarks/1078/
error: patch failed: lib/events.js:27
Falling back to three-way merge...
Applied patch to 'lib/events.js' with conflicts.
error: patch failed: lib/events.js:27
Falling back to three-way merge...
Applied patch to 'lib/events.js' with conflicts.
Can you rebase to fix those conflicts? (yes now I'm asking for a force push 🙈)
error: patch failed: lib/events.js:27 Falling back to three-way merge... Applied patch to 'lib/events.js' with conflicts. error: patch failed: lib/events.js:27 Falling back to three-way merge... Applied patch to 'lib/events.js' with conflicts.Can you rebase to fix those conflicts? (yes now I'm asking for a force push see_no_evil)
Lol, sure. It's necessary now and also in the guide
@aduh95 I did the rebase :)
I just ask that, even if it's everything ok, for you folks to wait a little bit before merging it. After some of the @benjamingr questions, I thought that I need one more test case: In the waitNext function I'm creating a Promise in a way to prevent an event leaking scenario that can occur if I have a slow stream, so it's fair to have a code testing it
@aduh95 also, after rebasing I ran the benchmark again just to be sure, here are the results:
confidence improvement accuracy (*) (**) (***)
readline/readline-iterable.js n=10 *** 37.15 % ±11.20% ±14.90% ±19.41%
readline/readline-iterable.js n=100 *** 53.09 % ±9.49% ±12.67% ±16.58%
readline/readline-iterable.js n=1000 *** 76.99 % ±10.65% ±14.23% ±18.66%
readline/readline-iterable.js n=10000 *** 81.81 % ±6.85% ±9.13% ±11.92%
readline/readline-iterable.js n=100000 *** 73.74 % ±4.98% ±6.64% ±8.66%
readline/readline-iterable.js n=1000000 *** 86.69 % ±3.66% ±4.88% ±6.35%
Be aware that when doing many comparisons the risk of a false-positive result increases.
In this case, there are 6 comparisons, you can thus expect the following amount of false-positive results:
0.30 false positives, when considering a 5% risk acceptance (*, **, ***),
0.06 false positives, when considering a 1% risk acceptance (**, ***),
0.01 false positives, when considering a 0.1% risk acceptance (***)
Benchmark CI: https://ci.nodejs.org/view/Node.js%20benchmark/job/benchmark-node-micro-benchmarks/1079/
confidence improvement accuracy (*) (**) (***)
readline/readline-iterable.js n=10 *** 30.56 % ±7.71% ±10.26% ±13.38%
readline/readline-iterable.js n=100 *** 51.98 % ±7.84% ±10.44% ±13.60%
readline/readline-iterable.js n=1000 *** 66.41 % ±7.88% ±10.51% ±13.72%
readline/readline-iterable.js n=10000 *** 64.99 % ±5.51% ±7.37% ±9.69%
readline/readline-iterable.js n=100000 *** 42.94 % ±3.99% ±5.34% ±7.03%
readline/readline-iterable.js n=1000000 *** 68.63 % ±2.07% ±2.78% ±3.66%
Benchmark CI: https://ci.nodejs.org/view/Node.js%20benchmark/job/benchmark-node-micro-benchmarks/1079/
@aduh95 nice! I just sent the new test case I talked about. But I found a situation that I need some guidance: When I create a Promise like this:
new Promise((resolve) => emitter.on('event', resolve));
This promise is not enough to keep the node process running if there's nothing else holding it. For example, this code will end immediately:
const events = require('events');
const emitter = new events.EventEmitter();
new Promise((resolve) => emitter.on('event', resolve)).then(msg => console.log(msg));
This code, though, will end in 5 seconds:
const events = require('events');
const emitter = new events.EventEmitter();
new Promise((resolve) => emitter.on('event', resolve)).then(msg => console.log(msg));
setTimeout(() => emitter.emit('event', 'some value'), 5000);
That said, if for any reason, the stream object used to obtain the readline interface has nothing holding up the node process (for example if it's a mock or something like that), the process will just end, no matter waitNext has created a Promise or not. I think this is an expected behavior. Do you folks think this is ok too?
@benjamingr I took a look at the async iterator version of on and it's pretty similar to the code I wrote on eventsToAsyncIteratorFactory.js. I realized that I need to do some adjustments to my code after I have analyzed it, like implementing the error and return methods of the resulting async iterator. I think it's important to do it before merging it.
In a future PR, maybe I can unify the on and eventsToAsyncIteratorFactory somehow, or I can make the "function on" use the eventsToAsyncIteratorFactory, because I really believe there are some performance improvements opportunities there.
Edit: @benjamingr I just just did it
@aduh95 hello! I fixed what you pointed out but I think I may have messed up doing the rebase :S
Everything looks fine in the final code, but the commit history in the PR contains duplicated commits now that I can't find in the commit history of my branch. Is this normal? I'm really not used to work with rebase, so I can't tell.
If there's something wrong, could you help me fix that?
Looks good, left a few nits that should be fixed before landing :)
Good job!
@benjamingr one thing I was thinking about is that the close parameter could have a default value of ['close', 'end']. That's because the previous implementation if I'm not mistaken, was only useful for emitters that never end, but with a finite stream, I couldn't use it without doing some trick with the abort signal.
If I do that I could be introducing a new breaking change, though, so I'm not really sure about it
If I do that I could be introducing a new breaking change, though, so I'm not really sure about it
Yes, let's not introduce any breaking changes (and I would prefer it if closeOn is private right now with a symbol and follow up with documenting and testing it in the public API)
Can't we implement on in a simpler way? e.g.
async function * on(emitter, event, options) {
// TODO: 'error' handler & options
const queue = []
let resume = null
emitter.on(event, (...args) => {
if (resume) {
resume(args)
resume = null
} else {
queue.push(args)
}
})
while (true) {
yield* queue.splice(0)
yield await new Promise(resolve => ({
resume = resolve
}))
}
@ronag
Regarding on() I would prefer if we have a batched iterator helper.
the changes here do not prevent that sort of extension?
Note this mostly improves the performance in on through a FixedQueue instead of an array since circular buffers require less allocation.
The readline iterator also needs support for closing the interface - so it adds a parameter for it.
In addition a readline interface's async iterable already has (some) support for backpressure - so this preserves it in on but does not expose it elsewhere.
@benjamingr the on implementation
Can't we implement
onin a simpler way? e.g.async function * on(emitter, event, options) { // TODO: 'error' handler & options const queue = [] let resume = null emitter.on(event, (...args) => { if (resume) { resume(args) resume = null } else { queue.push(args) } }) while (true) { yield* queue.splice(0) yield await new Promise(resolve => ({ resume = resolve })) }
That's similar to the implementation used on the Readable class, which was used previously to generate the readline async iterator. I could open another PR and try to use FixedQueue to improve the Readable iterator. Maybe it'd be enough to get a similar performance benefit I got here and it'd be less invasive. I'll test it and see.
Edit: actually never mind... it's not the case. Still the original logic for the on function was maintained, changing it is out of my scope
Possible alternative PR #41853
That's indeed a simpler alternative, but I ran it against the current implementation and got these results (old being the version of this PR and new being your suggestion):
[00:04:36|% 100| 1/1 files | 60/60 runs | 6/6 configs]: Done
confidence improvement accuracy (*) (**) (***)
readline/readline-iterable.js n=10 *** 13.08 % ±5.77% ±7.69% ±10.02%
readline/readline-iterable.js n=100 *** -8.54 % ±3.90% ±5.19% ±6.75%
readline/readline-iterable.js n=1000 *** -10.92 % ±4.42% ±5.92% ±7.76%
readline/readline-iterable.js n=10000 *** -39.76 % ±2.56% ±3.41% ±4.45%
readline/readline-iterable.js n=100000 *** -33.65 % ±2.00% ±2.66% ±3.48%
readline/readline-iterable.js n=1000000 *** -32.75 % ±0.90% ±1.20% ±1.58%
So, the current implementation is still faster in most cases. I didn't intend to change the function "events.on" on the first try, though, but I agreed with @benjamingr that it'd be beneficial. Changing it can bring even more valuable performance improvements than changing just the readline iterator, and also it increases its usability, as this way it can be used even with finite streams. I kindly ask you to take a look when you have some time to see that the PR didn't change the previous behavior of the function nor introduced a breaking change. The complexity of the implementation was already there, though, mainly because the function deals with some other scenarios that particularly I didn't worry about before, but maybe are relevant for some edge cases. It introduced some new parameters, though, so maybe it's a problem if you think about product design, as these new options aren't part of the currently proposed interface for the function and aren't deeply analyzed to see if it's worth it to have it on future versions of node.