[tree view] Should use maps not arrays for selected / expanded

[burtonator]

Right now selected/expanded are arrays and not maps/dictionaries.

Arrays are linear time lookup. Maps are constant time... O(N) vs O(1)...

For smaller maps it won't matter but for bigger maps performance will be impacted.

Search keywords:

[esseswann]

This line shows that there is indeed an array look up for finding if the item is expanded
https://github.com/mui-org/material-ui/blob/e04b4634f4b72f564c4e7532c1c91c15ab4fd5eb/packages/material-ui-lab/src/TreeView/TreeView.js#L39

But firstly Arrays in JavaScript are known to have faster lookup time when they have small length and secondly both in terms of performance and proper type usage you should go with Set

[eps1lon]

An array is easier to handle for the basic use case. IMO <TreeView expanded={[1, 2]} /> is easier to parse than <TreeView expanded={{1: true, 2: true}} />. We could switch to other data structures internally but this adds the cost of transforming these data types.

In the end it boils down to: Are there real-world use cases where dictionaries make a noticeable difference?

[oliviertassinari]

We could switch to other data structures internally but this adds the cost of transforming these data types.

I was interested in testing this approach out, it seems that it's a great approach.
Here is a quick and dirty benchmark, assuming somebody tries to render 100,000 items:

var expanded1 = Array.from(new Array(100000)).map((_, index) => String(index))

console.time('conversion')
var expanded2 = expanded1.reduce((acc, index) => {
    acc[index] = true;
    return acc;
}, {});
console.timeEnd('conversion')

console.time('array')
expanded1.indexOf('foo')
console.timeEnd('array')

console.time('object')
expanded['foo']
console.timeEnd('object')

conversion: 4.6630859375ms
array: 0.3330078125ms
object: 0.001953125ms

It looks like that if we hit a performance issue, we can handle the concern internally, 20 items are enough to convert the data structure to an object and observe an ROI > 1. So I don't think that performance should be a concern from the API standpoint.

---

This makes me think, virtualization support could be pretty neat!

[eps1lon]

1. Objects are likely the worst choice here. Set and Map should have better runtime. Adding this many properties to objects has likely some memory overhead.
2. .reduce is over-engineered. A simple forEach does the same.
3. Micro-benchmarks are not useful for this issue. We want to know the actual performance impact on render/user interactions.
4. console.time is inaccurate for micro benchmarks. Try performance.now or, better, jsperf.com

[joshwooding]

I had similar thoughts on this, I had previously discussed using a Set but decided against it since I did not have an example where I could measure the actual performance impact as @eps1lon suggested.

[rashdeva]

We also require virtualization for Tree View. Most of the time, Tree VIew has many items inside.

[oliviertassinari]

@rash2x Could you open a new issue for Virtualization? Thanks

[rashdeva]

@oliviertassinari done! #9685