Platform: Performance of ofType?

[bryanrideshark]

I'm submitting a...

[ ] Regression (a behavior that used to work and stopped working in a new release)
[ ] Bug report  
[x] Feature request
[ ] Documentation issue or request

What is the current behavior?

Right now, ofType is implemented via filter. As I understand it, this creates O(n) performance when you have multiple effects.

As an application grows, the performance is going to continually degrade, unless we re-write "ofType" to work without filter, and instead use something that has a performance closer to O(1).

Possible options:

I think that the best option would be doing a dictionary lookup on a Map or Set. We can always fall back to a POJO in the case that Map or Set are not supported.

The tricky bit is, when you have multiple ofTypes being called, each creating its own observable, how do you make that work in a performant fashion?

I can work on a PR for this, I just need to know whether or not it's a direction the project wants to go in.

[bryanrideshark]

Came up with an implementation. Could likely be skinnier, but it proves the basic concept.

[dummdidumm]

Effects are (normally) created from the stream of actions. Since it's a stream of actions and not an array, only one action at a time is processed. So filter does not have O(n) but O(1). The number of effects does not have an impact on the performance of one single effect.
https://www.learnrxjs.io/operators/filtering/filter.html

[brandonroberts]

Thanks @dummdidumm!

[bryanrideshark]

@dummdidumm , I think perhaps I misspoke. I was not referring to the performance of Effects once they begin, but rather, the performance of the ofType operator. I conflated the two, in the future I'll be more specific.

The performance of OfType definitely is O(n), where n is the number of times you have used actions.ofType in your application. Looking at the source code, I can't see any other explanation for what the O number would be, as there is one invocation of the filter predicate, for each time ofType is used in an active subscription. The more active subscriptions you have - the more times you're going to be invoking the predicate. Unless I fundamentally misunderstand rxjs, which is possible, I am convinced that it's O(n).

(edit)
After I wrote my rationale up, I decided I'd better measure the real world performance. I was blown away. Even with 187 things using ofType, it took under 1ms to perform the action. 1ms is really overstating it... It's really too small to measure.

I'm majorly impressed with the performance of V8, and rxjs. Even though almost everything I wrote below is irrelevant, I'm going to post it anyway for reference. Based on what I'm measuring, I'd say that unless you're using 10k ofType operators in a single application, don't worry about the performance of the current @Effect system. If you do start to notice a _measurable_ slowdown and you can trace it back to ofType - Feel free to use my PR, it will likely speed things up for your very unique use case.

(original post)

Why is the performance O(n)?

Let's look at a code sample, with 5 usages of ofType:

````

function logAction(action: Action) {
console.log(action);
}

@Injectable()
class TheEffects {

@Effect({dispatch: false})
as$ = this._actions$.ofType('A').pipe(tap(logAction));

@Effect({dispatch: false})
bs$ = this._actions$.ofType('B').pipe(tap(logAction));

@Effect({dispatch: false})
cs$ = this._actions$.ofType('C').pipe(tap(logAction));

@Effect({dispatch: false})
ds$ = this._actions$.ofType('D').pipe(tap(logAction));

@Effect({dispatch: false})
es$ = this._actions$.ofType('E').pipe(tap(logAction));

constructor(private _actions$: Actions) { }
}

````

Should I run store.dispatch({type: 'A'}), each observable will run the ofType operator on the source (Actions). There are 5 times it is being used, once for as$, once for bs$, once for cs$, ds$, and es$. Even though there's only one action being dispatched, the O is 5 (each ofType operator asks "Are you the thing I'm looking for")

If I add more usages of ofType (this is usually synonymous with more @Effect) usage - the efficiency will degrade. Each ofType operator instance is going to essentially be asked "Hey, do you care about this", even though there's a single Actions instance in the entire application. 99% of the time, the answer is going to be "No" for this question, so there's a lot of useless flops going around.

Real World Evidence

I just now dove into the enterprise Angular app I'm working on which uses ngrx. This is the Action Subject when an action is actually being dispatched.

Note the 187 observers.

Each observer is running Array.prototype.some() over the dispatched action. As I said before, for 99% of
the actions, this is always going to return false.

The performance is undoubtedly O(n).

My (over engineered) solution

I'm sure there is more than one way to solve this problem, but I'll just take the time to explain how my solution works. Instead of each ofType operator adding a subscription to the Actions singleton, instead, a single subscription is made. Each invocation of ofType adds a new Subject only for actions of the given type, so in the example above, you'd have 5 individual Subject's. There is only one Subject per action type which is observed, so even if I had 5 more @Effects which listened to the same actions, there would still be only one Subject per type of action.

When a new Action comes in, it is simply passed through via next to the appropriate Subject, so A's go directly to Subject A, B's go directly to Subject B, etc. Instead of using the filter operator to pass the actions to the downstream observables, we instead use merge.

Think of it this way - Imagine that the current implementation has a bunch of inspectors all standing around a conveyor belt. Each is looking for a particular color box, which they will then inform their interested parties about. The conveyor belt has to get longer and longer, the more inspectors that you add to the system. With the proposed implementation, we add a smart sorting machine at the front of the conveyor belt, which divides up the boxes to color-dedicated conveyor belts. We still have the same number of inspectors, but the horizontal space they take up in the factory is brought to a constant size.

[dummdidumm]

The performance of ofType is O(n) where n is the number of actions you filter for. Most of the time you use ofType with one action, so one could say its O(1).
The O(n) you speak about does not come from the use of ofType but the number of effects in general.

I don't know rxjs and the effects internals in and out, but I think to achieve what you want, you would have to change the way the effects are merged and subscribed to by the EffectsModule, just changing the implementation of ofType would not change much. As far as I know, the EffectsModule merges all effects into one big observable which it subscribes to. So on each action, all effects are triggered, therefore each effect's ofType is triggered.

So to do the optimization you want, you would have to implement an ofType-method which acts BEFORE each effect is called. To do this, you would have to do some processing outside of rxjs which the EffectsModule internally can use to intelligently call the right effects instead of just merging all into one. Because of this, ofType would no longer be a rxjs-operator which you use on the actions$-stream in a pipe-able fashion.

Something like this:

@Effect() 
noLongerAnActionStream = ofType(
   'SOME_ACTION',
   action$ => action$.pipe(
     ... // everything in here is only invoked for SOME_ACTION-actions
   )
);

The EffectsModule could then use noLongerAnActionStream to somehow process the effect intelligently.

This would then be a breaking change and you also have to find solutions for cases where users maybe don't want to dispatch an action in reaction to another action but f.e. just in some regular interval. The API is also less ergonomic (but maybe there are better ways).