Performant design decisions

[carloszimm]

Hello, guys!
I was wondering about the implementation design decisions taken by mostjs (either v.1 or v.2) that makes it faster than other libraries.
Is that detailed anywhere publicly accessible?
Do you guys still have a perf test to make sure that those performant decisions still hold?

[briancavalier]

Hey @carloszimm 👋

I don't think it's all been documented in one place, but here are a couple older issues that discuss some of the decisions of most. I think @most/core has followed the same path.

1. How comes it so much faster than LoDash? cujojs/most#137
2. thanks! (questions about performance) cujojs/most#458

Keep in mind that those are from 2015 and 2017, and JS performance is always a moving target. There are probably things in mostjs that don't help with performance anymore (it's possible some never did! Performance is tricky!). For example, mostjs's map/filter fusion was incredibly fun and interesting to implement, but I doubt matters much anymore, and I'll probably vote to drop it from any new versions.

Overall, I think I'd say it's probably best to approach performance from multiple angles, starting with your project's goals, then architecture, and finally implementation. Try to figure out where performance really matters for your specific project, and where it doesn't.

As for implementation, simple is king. Do less. Don't try to solve every problem for everyone. Implement things as directly and obviously as possible. Try not to be "clever" unless you can prove (with data) that "clever" is actually better. In my experience, focusing on simplicity almost always work out well.

Beyond that, reading about current generation VMs and their optimizations can be fun and interesting. You can use tooling to learn about how they optimize your code, and then look for ways to improve it.

I hope that's somewhat helpful.

[briancavalier]

I figured it might be interesting to try to list some specific implementation-level things mostjs has done. Again, some of these might still matter, some might not, so they're probably worth evaluating before applying them elsewhere. I hope they at least give you some ideas to explore 😄

VM friendliness

1. Avoid and/or isolate try/catch (at one time, VMs couldn't optimize it. I don't know if that's still true)
2. Keep functions small to improve chances of optimization and inlining
3. Keep functions monomorphic whenever possible to prevent them from being deoptimized
4. Use objects with a small, fixed set of properties, and don't add or delete properties after construction (at one time, VMs would optimize object property access)

Operator optimizations

1. Fuse adjacent map() operations, e.g. map(h, map(g, map(f, stream))) becomes map(pipe(f, g, h), stream)
2. Fuse adjacent filter() operations, similar to 1, but for filter
3. Fuse adjacent filter() and map(), e.g. map(f, filter(p, stream))` uses an internal FilterMap stream.
4. Fuse adjacent slice/take/skip, by fusing bounds
5. Commute map and slice/take/skip, e.g. take(5, map(f, stream)) becomes map(f, take(5, stream)). Moving slice/take/skip before map can result in fewer calls to mapping functions
6. Recognize when slice/take/drop would result in an empty stream and return the canonical empty stream instead.
7. Squash merge trees, e.g. merge(a, merge(b, c) becomes merge(a, b, c). Possible because merge is associative and commutative.
8. Remove canonical empty stream from merge trees, e.g. merge(a, empty()) becomes a, merge(a, b, empty()) becomes merge(a, b)

Scheduler optimizations

1. Use a single timeout
2. Use a bucketed binary tree for scheduling async tasks

Scheduler is especially complicated and probably not worth it. It was fun and challenging to implement, though.

That's what I can think of at the moment. If I think of more, I'll add them. @TylorS may have more to add.

[TylorS]

No you really hit all the points. I think just to add emphasis I'd highlight the scheduler enables the ability to enable a single try/catch for the majority of streams since the call stack always originates within the scheduler itself. This further enables most's "always async" guarantee, which also makes higher-order operators capable of interrupting "inner" streams that would otherwise run synchronously in many other libraries, further avoiding additional work.

In my recent micro-benchmarking of a stream library I've been working on, I'm near positive all of these things hold true today as well. Most is still pretty damn fast. I don't have many still hanging around, but here is one - https://github.com/TylorS/typed/blob/development/packages/fx/test/benchmarks.ts#L40

Here's the results of 1k, 10k, 100k lists of numbers using stream.filter(isEven).map(addOne).scan(add, 0)

I removed Fx from the above run because it's kind of an unfair advantage that it understands the source is an array and can safely cache the result.

There's 2 graphs per test, the first is just the raw values calculated, and the second is the relative values where the fastest is 1 to be able to tell relative differences. What I think you'll see, is that at 1k items, there's not a very big difference. Conveniently, these are not running long enough to be really optimized. At 10k and 100k, you start to see the benefits of optimizations

I don't have them hanging around anymore, but higher-order operators like switchMap were much more stark in contrast if I remember correctly.

[TylorS]

@briancavalier Just to comment on some of the parts in parentheses that seem like you're less sure of these things today, I do have some insights into some of them.

• try/catch is definitely still a de-optimization.

  • There's been some work in V8 to enable some optimization in some cases - https://codereview.chromium.org/1996373002
  • That said, this fairly recent PR is for Effect-TS (improve performance of fiber forking Effect-TS/effect#1743), but it increased fiber forking by removing try/catches in their fiber runtime improved the creation of its class by about 20x, and at runtime about 2x.

• Small, fixed-sized objects is still definitely an optimization around memory access using hidden classes in all of the VMs

• A single timeout really doesn't optimize much these days, at least not in node.js. I attempted to swap out the Effect scheduler , which uses an arbitrary number of setTimeouts for scheduling, with a version based on our Timeline, and it had 0 affect on the performance in my testing. This might bode well for ditching a fair amount of the scheduler as it is today

• I'm not really sure about fusion, it's had a tremendous affect on my Fx library, but often the fusion is allowing me to avoid the Effect runtime, which isn't free and will never be as fast as a native function call. It's probably worth investigation this a bit more to figure out how much it does or doesn't do at this point, but I suspect it still helps with memory usage by eliminating intermediate Stream objects and corresponding Sinks even if performance isn't as worthwhile these days.

[briancavalier]

Thanks @TylorS!

One more I remembered for VM friendliness:

Avoid allocating "lots" of closures. Executing closures after they've been created isn't a real problem, rather the problem is allocating them in the first place. Or at least it has been in the past.

The problem was they allocate large amounts of memory compared to, say, instantiating a class with a prototype method. So, allocating a "large" number of closures can consume huge amounts of memory, which, because memory is a shared resource, can lead to memory pressure and slow everything down drastically.

Using closures in application level code usually isn't a problem. They're powerful and convenient, so I wouldn't worry about it. In a library that is used pervasively within an application (like back in the day before Promises were native), closure allocation can be significant.

How many is "lots" or a "large" number? I have no idea these days, but if you're working on a library that could be used pervasively, preferring objects and prototype methods over closures could be a good option. As always, try to verify with data!

[briancavalier]

@carloszimm

Do you guys still have a perf test to make sure that those performant decisions still hold?

@TylorS has done more of this than me over recent years. Back in the early days of most, we maintained a suite of microbenchmarks. They were useful, and I ran them a lot while working on the original most 1.0 code. They were only a guide, and not a guarantee. We would occasionally add new benchmarks to the suite when working on a new optimization. Merge tree squashing comes to mind. See the "merge nested streams" benchmark at the link above.

Another thing to consider is performance scaling. When inputs and applications are small, almost any solution will be fine, and it's usually best just to do the most obvious thing. Need to map, filter, and reduce 10k items? Just put them in an Array and .map.filter.reduce. Need to map, filter, and reduce 1 billion items? An Array may not be the best solution depending on your time budget.

@TylorS pointed out performance scaling as well: mostjs's performance typically scales more linearly than other similar libs (I haven't kept track of other libs, so it's entirely possible some do scale more linearly now). You can see this in @TylorS's perf results, as well as in the "merge nested streams" microbenchmark results I mentioned previously.

I don't intend any of this as negative toward other projects in any way. Each of these projects has had different goals and priorities, and solves a slightly different set of problems.