optimize array tracking (fix #4318)

[jods4]

This PR implements the optimisations proposed in #4318. Shortly:

• It adds a special tracking key: ARRAY_ITERATE_KEY, which represents a full dependency on an array (not including extra keys when handling an array as an object).
• It works simply by being automatically triggered whenever length or an integer key is triggered on an array.
• Almost all array functions have been instrumented for speed using ARRAY_ITERATE_KEY.
• With that, there's a single track record (vs O(N)) and no proxy overhead when manipulating the array.
• Should lead to big gains in memory and speed, especially with large arrays.
• Tests for all newly instrumented functions are included

Unrelated changes included in this PR

• I made the arrayInstrumentations object use a null prototype -> no need to check for ownKeys when accessing, should be ever so slightly faster on misses.
• For indexOf and co. I optimized the existing instrumentation slightly: when the needle is not found and is not a proxy, there's no reason to do a 2nd pass.

New public APIs

@vue/reactivity exposes readArray(source, deep = false).

This is an advanced reactivity function that returns the underlying raw array and tracks it entirely.
As this is a performance oriented API, an extra parameter indicates if deep reactive arrays return proxified array items (false by default). Of course, deep: true comes at the cost of one array copy (vs zero).
When source is not reactive, it's returned as-is and no tracking occurs.

Why expose this? Because it's still useful for performance-conscious users when they want to perform an operation not well covered by built-in array functions. Examples:

Example 1: v-for uses it :)
Example 2: consider writing matrix multiplication with reactive matrices (arrays). I tested a computed that performs 10x10 reactive matrices multiplication. Using readArray gave me more than 3x boost and those are pretty small matrices!
Example 3: Object.groupBy is a new API that could become quite popular. For compat. concern it is not an array method, so can't be instrumented. Unless we patch the browser APIs, readArray is the only way to optimize it in user-land.

Open points

1. Instrumented functions are only returned for non-readonly proxies. This is detrimental to this PR and I'm not sure why it was done. Current instrumentations fall in 2 categories:

• Avoid nested triggering in some mutations. Mutations fail on readonly proxies anyway, so does not really matter.
• Searching for un-proxified values in indexOf and co. This seems useful on readonly arrays too?

2. I have kept v-for very close to its current source code, sticking to the for (i = 0..) loop. Using readArray(source, true) implies a full array copy on deeply reactive arrays. I think it'd be better to use map or an iterator (also instrumented for perf, requires no O(N) allocation) or maybe readArray(source, false) and call toReactive inside the loop if required (more code).
3. I mentioned the new Object.groupBy API above. It's unfortunate it's not an array instance method. Do we want to patch Object? It feels really bad to patch native objects, but this is an API I can imagine being used inside computed a lot in the future... so it'd be nice to have the best perf by default. Maybe let users opt into that?

Noteworthy implementation details

• There's a comment in iterator() about the timing of tracking that is worth reading.
• Some method can early exit, such as find, some or every. After this PR they will track the full array and may trigger when not strictly necessary.
  This is not totally new, the existing instrumentations of indexOf and co. did exactly this already.
  Might be "fixed" if we introduce range dependencies (see below).

Further ideas

If this PR is merged, some ideas:

• A similar optimization could be made for mutations/triggers.
• Might be a big change because the reactivity structures may not support it as is: introduce tracked ranges? That could solve the imprecise tracking of indexOf, lastIndexOf, find, findLast, findIndex, findLastIndex, some, every, includes, slice (not instrumented in this PR).

[github-actions]

Size Report

Bundles

File	Size	Gzip	Brotli
runtime-dom.global.prod.js	89 kB (+2.52 kB)	33.6 kB (+701 B)	30.3 kB (+610 B)
vue.global.prod.js	135 kB (+2.52 kB)	50.3 kB (+698 B)	45.2 kB (+709 B)

Usages

Name	Size	Gzip	Brotli
createApp	50.3 kB (+2.4 kB)	19.5 kB (+616 B)	17.8 kB (+577 B)
createSSRApp	53.6 kB (+2.4 kB)	20.8 kB (+607 B)	19 kB (+570 B)
defineCustomElement	52.7 kB (+2.4 kB)	20.3 kB (+615 B)	18.5 kB (+587 B)
overall	63.7 kB (+2.41 kB)	24.4 kB (+650 B)	22.2 kB (+656 B)

[johnsoncodehk]

This PR is meant to be against v3.4.0-alpha.1 but as it is only a tag and not a branch, I had to go against main

Thanks for following up! You can go against the minor branch, and I will help review the changes.

[jods4]

@johnsoncodehk Thanks, I based the PR on minor. Only my commit shows up now, it's reviewable ;)

[dsonet]

Hope this can be landed into the 3.4.

[yyx990803]

/ecosystem-ci run

[vue-bot]

📝 Ran ecosystem CI: Open

suite	result	latest scheduled
language-tools	❌ failure	❌ failure
nuxt	✅ success	✅ success
pinia	✅ success	✅ success
quasar	✅ success	✅ success
radix-vue	✅ success	✅ success
router	✅ success	✅ success
test-utils	✅ success	✅ success
vant	❌ failure	✅ success
vite-plugin-vue	✅ success	✅ success
vitepress	✅ success	✅ success
vue-i18n	✅ success	✅ success
vue-macros	✅ success	✅ success
vuetify	✅ success	✅ success
vueuse	✅ success	✅ success
vue-simple-compiler	✅ success	✅ success

[yyx990803]

Great job! I've merged it with the latest reactivity system refactors on minor and everything is working. Ecosystem CI failures are expected and match current fails on minor.

Regarding the open points:

1. The reason readonly did not use instrumentations is because readonly proxies themselves don't and shouldn't need to be tracked (tracking will happen if it wraps another mutable reactive source). With these changes, we can consider enabling instrumentations for readonly arrays, but it will cause additional complexity in the methods as they now need to check whether the source is readonly in order to use toReactive vs toReadonly - and worse, if a readonly array wraps a reactive one... so I think it's best to still skip them. It should be rare for users to iterate on huge readonly arrays.

2. I've changed renderList to use the shallow readArray as suggested in 13d31d5

3. For Object.groupBy, we can consider it in a future PR.

[dev-zuo]

👍 awesome