perf(orderBy): filters needlessly executed on every digest

[thorn0]

I'm submitting a ...

• bug report
• feature request
• other

Current behavior:

from the docs:

When filters are executed
In templates, filters are only executed when their inputs have changed... There are two exceptions to this rule: 1. In general, this applies only to filters that take primitive values as inputs. Filters that receive Objects as input are executed on each $digest, as it would be too costly to track if the inputs have changed...

This effectively means that in all the instances of ng-repeat that use orderBy, this filter is rerun on every digest. Instead of "costly" tracking the input array for changes, the framework first sorts this array and then still tracks it. The sorting part here is a pure performance loss which doesn't make any sense.

Expected / new behavior:
Similar to the $stateful flag, it'd be great to have another flag for filters like orderBy. This flag will make the filter be executed only if its inputs have changed even if the inputs are objects.

Minimal reproduction of the problem with instructions:
http://jsbin.com/nulonon/edit?html,js,output

AngularJS version: 1.6.x, 1.5.x

Browser: all

[petebacondarwin]

You are right that orderBy re-runs its sorting on every digest loop, this includes recomputing the predicates, applying those predicates to each item in the collection, running the sort against the predicate values, using the comparison function, and finally creating a new array of the sorted values. I can see that this can cause performance issues, if you have large collections, compounded if you also have complicated predicates and comparison functions.

The suggestion you make is to compare the inputs, i.e. array, sortPredicate, reverseOrder, compareFn, before running the filter. Given that the predicates can look "deeply" into the array, which could be a complex object, we would need to do a deep comparison of that array on each digest loop (this also involves storing a copy of the array for comparison), as well as doing (at least) a shallow comparison of the sortPredicate, which can be an array itself.

While in some cases, it might be true that doing this comparison upfront is faster, I believe that there are other scenarios where this would be slower: Since the output of the orderBy filter, when used in ngRepeat will be watched using $watchCollection the comparison will be simpler than a deep comparison. Consider a very deep complex object, with many levels of nesting, where we are only sorting on a top level simple property. In this case it may be faster to pull out these properties, do a sort and return the array, which will then be compared only via a shallow compare; rather than do a deep watch of the input array before triggering the orderBy filter.

Given that the input array and the predicates can be complex, I don't see how we could short circuit the deep watch (except possibly in the case where the array is a constant literal, @jbedard ??).

If you know that the orderBy behaviour is killing performance then a workaround would be to move the call to the filter into a separate watch on the controller instead: http://jsbin.com/yicolak/edit?html,js,output

[thorn0]

Given that the predicates can look "deeply" into the array, which could be a complex object, we would need to do a deep comparison of that array on each digest loop

It'd be enough to watch only array.map(sortPredicate) in this case, not the whole array. wouldn't it? Can we allow filters to specify custom watch expressions?

[thorn0]

Also, I hardly agree with the "frequency: low" label. Everyone uses orderBy. It's worth to be optimized.

[petebacondarwin]

Also, I hardly agree with the "frequency: low" label. Everyone uses orderBy. It's worth to be optimized.

In five years you are the first to mention this :-) It can't be killing performance on that many applications. Of course any optimisation is worth it if it works.

[petebacondarwin]

Can we allow filters to specify custom watch expressions?

I wonder if there is something using interceptors that would work here??

[jbedard]

Filters/interceptors only have the input-watching advantages when the inputs are also non-stateful which we (unfortunately) can't assume for anything other then primitive objects. Sometimes object/array literals will only have non-primitive inputs but that would probably be an edge case for any use of orderBy, for example... [{id: x}, {id: y}] | orderBy:'id' would only have x and y as inputs, so if those two inputs are primitives then orderBy will only be executed when those inputs change.

Filters/interceptors for arrays is where input-watching has always fallen short, and it has always bugged me. 97b00ca solved it for a few specific cases ($watchCollection of literals), maybe that can be extended somehow? For example if you had a filter that only accepts immutable data as input, then setting that flag on the filter would solve this...

[jbedard]

@thorn0 one other idea we thought of is the use of valueOf. As I mentioned above input-watching only works on primitive objects. However, input-watching does go one step further and invokes valueOf to attempt converting non-primitives to primitives. The main motivation here was originally Date objects and ensuring the date filters would get all the input-watching benefits, but it can (and will) be used for anything that implements valueOf.

You could implement valueOf on your data objects to return something such as a hash. As long as any two objects that return the same valueOf-value can be considered "equal", and that value must be primitive in order for input-watching to take advantage of it.

For orderBy... if you really wanted you could (I think, I'm making some assumptions/guesses here)... put a valueOf method on the array?

[jbedard]

Looks like what I was suggesting won't work for ng-repeat or anything using $watchCollection today because the $watchCollection interceptor is marked as $stateful. I think this was originally done just because the probability of $watchCollection watching a non-primitive (like a collection) was too high so we thought it wasn't worth using the input-watching, but maybe that can change. It has already changed a bit in master to allowing input-watching of collection literals.

[thorn0]

Individual situations can be easily solved like Pete described. But is there a chance to improve the performance of orderBy + ng-repeat in the general case? My idea was, at least when the comparator is default, to watch array.map(sortPredicate) (pseudo-code), which would typically be an array of primitives so it'd be cheap to deep-watch it, instead of re-sorting the array on every digest and watching the result. Mapping is O(n) whereas sorting is O(n log n). Does it make sense?

[petebacondarwin]

@thorn0 Do you have a suggestion for how we would implement that?

[thorn0]

No, unfortunately. That's what I'm asking. Is there infrastructure in place for doing something like this? Without deep diving into code I can't tell the answer from what @jbedard wrote, It seems to be no, but I thought I'd confirm.

[petebacondarwin]

There is no infrastructure for doing this. It would require some "refactoring" :-)

[raybellis]

I've also just found (somewhat belatedly) that I'm suffering from this too.

My application gets frequent updates over a WebSocket (sometimes as often as every 0.1s) which some pages need to listen to. The WebSocket is part of a Service which uses $scope.$emit within a $scope.$apply block to tell the listeners when a new message has arrived. However this subsequently then propagates all the way up to $rootScope which then forces a $digest on all descendent scopes, causing my sort function to get invoked repeatedly (for hundreds of rows in that collection) even though the underlying model data for that particular table hasn't changed at all.

[petebacondarwin]

@raybellis - I am sorry about this. We are now in LTS so this behaviour is not going to change. You could try limiting the impact by throttling the calls to $emit so you run $apply less frequently.

[raybellis]

Throttling the $emit calls would be a pain as I do want some of them to be actioned immediately.

I'm now working around it by using a separate member of $scope in which I store the sorted and filtered rows for my table per your suggestion above (#16348 (comment)) instead of using | orderBy:foo | filter:bar.

[raybellis]

p.s. the only reason this wasn't visible before was because I was using built-in sort predicates. It was only observed when I tried to implement a bespoke comparator function and then noticed how often that comparator was being called.