1429609 - Pre- or runtime-optimized data structures for given situations?

Status: NEW

(Core :: MFBT, enhancement)

Description

[Gerald Squelart (he/him) (not at Mozilla since 2022-09-15)]

While working on bug 1426044, I've tried to select a combination of data structures that (hopefully) should give the best performance for different loads.

(In this particular case, we have a non-growing sequence of items, searches that mostly happen in order, and occasional removals; Some benchmarking on Try lead me to use a non-sorted array for "small" lists, and a hashtable otherwise, "small" depending on the platform.)

It would be great if we had a handful of data structures that could adapt to these situations, by internally using the most appropriate structure in each case (either through predetermined selection, or through a runtime benchmarking mechanism).

If not practical, then maybe some documented guidance about how to properly benchmark such data structures for the most common platforms that Firefox uses -- Is Try representative?