Improve reactive collections performance · Issue #4318 · vuejs/core (original) (raw)

This some stuff I had on the back of my head for months, but just can't find any time to PR.
I thought maybe @basvanmeurs or @RobbinBaauw may be interested in having a go at it, as they did awesome work on ref performance before.

I'll write this issue focusing on arrays, but some of it could be applied unchanged to other collections (Maps, Sets).

Arrays are important

In vue, arrays are wrapped behind a reactive proxy that traps every read/write to every array indice.

Arrays can be big. In fact, as big as you can imagine.
Data viz is a prime example of applications that manipulate lots of large arrays.

Let's imagine a dashboard that monitors 100 VM. For each it displays metrics (maybe a sparkline) for CPU and memory, based on the last hour, 1 data point per minute.
That's 100 x (60 + 60) = 12'000 array elements.

A (raw) indexed array access is crazy fast in modern JS VM.
But each reactive array access incurs:

Key observations

Most applications use arrays as lists, not tuples.
By this I mean: they iterate through arrays completely, rather than access specific random indices.

For this usage, arrays are read entirely (e.g. using for-of, map, filter, sort, v-for) and everything in the array is a dependency.

It could all be tracked with a single dependency, no matter the size of array (aka O(1) vs O(n), if not O(n lg n) for sorts).
Instead a naive approach tracks every single indice access.

Notice that Vue actually already performs this optimization for keys, values, entries, @@Iterator and forEach, for collections -- which does not include arrays:
https://github.com/vuejs/vue-next/blob/7ffa225aa334f0fd7da6ba30bee9109de3597643/packages/reactivity/src/collectionHandlers.ts#L182-L224

Optimization idea

Much like collections above, arrays could often take a single ITERATE dependency and process the native array, bypassing proxies and tracking altogether.

shallowReactive is especially easy because it doesn't modify its contents.
Deep and readonly reactives are designed to modify their contents on read, which is probably not the best decision perf-wise but it's too late to change. This makes their optimization a bit more tricky.

Map, filter, reduce -- and the likes

Those methods take a callback and apply it to the complete array.
We must ensure the items in callback are wrapped.
Callbacks also take the entire array, I don't think we have a choice here but pass the reactive array and incur any tracking work if it is used. In my experience this parameter is rarely used in practice, though.

Here's a sketch of an implementation, using map as an example but the code can be shared:

// Assume we captured map on the target when returning the function below. // This is required in case user has its own map implementations and calls // the function on a different instance than the one it obtained it from. // In other words stuff like: // const aMap = reactive1.map; // aMap.call(unrelated, ...); const targetMap = target.map;

// This would be the map function returned by the proxy for reactiveArray.map, // with targetMap above captured. function map(cb, thisArg) { // Native arrays or whatever if (!isReactive(this)) return targetMap.call(this, cb, thisArg);

// Bail out to unoptimized for weird usage on non-array? // This is so that dependencies are properly tracked if (!isArray(this)) return targetMap.call(this, cb, thisArg);

// Register an ITERATE (i.e. whole array dependency) track(this, ITERATE); const raw = getRaw(this);

// shallow -> nothing to do, except ensure the array argument is the reactive one if (isShallow(this)) return targetMap.call(raw, (item, idx) => cb.call(thisArg ?? window, item, idx, this));

// readonly and deep: must wrap value const wrap = isReadonly(this) ? toReadonly : toReactive; return targetMap.call(raw, (item, idx) => cb.call(thisArg ?? window, wrap(item), idx, this)); }

entries, values, keys, Iterator

Same idea as map & co., but simpler because there's no callback.
Vue actually does it for Map and Sets, as indicated previously.

some, every, find, findIndex

These are basically the same as map & co.

They are special because iteration doesn't go to the end (notice: for-of on an iterator could break as well) but can stop early.
In a first approach, I wouldn't care about that. It's theoretically possible to create range dependencies if we really wanted to.

This mean an effect can run again although no impacting change was made, but it's already the case today, so I wouldn't call that a breaking change.
Today some has a dependency on length, and even if it stops at index 0, if you push a new value it would run again (although it doesn't have to).

sort

This one is a bit special because it reads values more than once, n lg n times on average.
I think it would be worth wrapping all items into a new native array, sort it natively, and apply the result to original array.
Maybe less efficient for small arrays, but small is fast anyway. The larger the array, the more efficient it should be.

A first approach could be like above and wrap every item on-demand.

readAll

I think for advanced uses it'd be nice to have a function readAll(reactiveArray) that performs a track(array, ITERATE) and returns the raw, non-reactive array. That would allow users to efficiently use this array in an index-based for loop for example, or perform any other kind of custom analytics with random access (think moving average, etc.).

For non-shallow arrays, instead of returning the raw array, we'd need to return a mapped copy with every element wrapped.

v-for

Let's not forget v-for, one of the main use cases!
Currently it iterates with an index-based loop.
https://github.com/vuejs/vue-next/blob/master/packages/runtime-core/src/helpers/renderList.ts#L62-L66

To benefit from work above, it should switch to a for-of (using iterator tracking) or map.

[...spread] and Array.from

I believe those are based on the iterator protocol, so they would also benefit from changes above?