Bugzilla

Working on bug 1924444 showed that the current usage of memory position based comparators for `RedBlackTree`s might not always yield the best result, and together with that that the size of those trees might matter, too, as operations on them are O(log(n)) and can touch quite a lot of objects.

An example of this is [mRunsAvail](https://searchfox.org/mozilla-central/rev/e24f7f322960a39f9ef644a31b6026994db73850/memory/build/mozjemalloc.cpp#1172-1174) where we are [mixing a size based comparator with a position based one](https://searchfox.org/mozilla-central/rev/e24f7f322960a39f9ef644a31b6026994db73850/memory/build/mozjemalloc.cpp#956-967), and also chunk comparators use similar conditions.

Example:
`mRunsAvail`'s primary use seems to be "find a run of at least size X". That means the sort criteria size could be enough if then we had just a plain list of runs behind each size, getting us a potentially much smaller and much more stable tree. The difficulty here is that we cannot easily use hash maps or other standard implementations, as we must avoid normal allocations during these operations. We could probably use the already added `DoublyLinkedListElement<arena_run_t>` on runs and add a `DoublyLinkedList<arena_run_t> mAvailableSameSizeSiblings` list to `arena_run_t` itself, putting only ever 1 run of the same size into `mRunAvail` and handle the siblings inside that additional list. This would reduce the cost of adding, removing and finding those runs (under the assumption that we have many runs of the same size) and also get us for free a "most recently made available" policy for those runs on re-use.

But as a first step, we should look out for `RedBlackTree` operations in detailed enough profiles in order to see if this is worth it.

Working on bug 1924444 showed that the current usage of memory position based comparators for `RedBlackTree`s might not always yield the best result, and together with that that the size of those trees might matter, too, as operations on them are O(log(n)) and can touch quite a lot of objects.

An example of this is [mRunsAvail](https://searchfox.org/mozilla-central/rev/e24f7f322960a39f9ef644a31b6026994db73850/memory/build/mozjemalloc.cpp#1172-1174) where we are [mixing a size based comparator with a position based one](https://searchfox.org/mozilla-central/rev/e24f7f322960a39f9ef644a31b6026994db73850/memory/build/mozjemalloc.cpp#956-967), and also chunk comparators use similar conditions.

Example:
`mRunsAvail`'s primary use seems to be "find a run of at least size X". That means the sort criteria "size" could be enough if then we had just a plain list of runs behind each size, getting us a potentially much smaller and much more stable tree. The difficulty here is that we cannot easily use hash maps or other standard implementations, as we must avoid normal allocations during these operations. We could probably use the already added `DoublyLinkedListElement<arena_run_t>` on runs and add a `DoublyLinkedList<arena_run_t> mAvailableSameSizeSiblings` list to `arena_run_t` itself, putting only ever 1 run of the same size into `mRunAvail` and handle the siblings inside that additional list. This would reduce the cost of adding, removing and finding those runs (under the assumption that we have many runs of the same size) and also get us for free a "most recently made available" policy for those runs on re-use.

But as a first step, we should look out for `RedBlackTree` operations in detailed enough profiles in order to see if this is worth it.

Working on bug 1924444 showed that the current usage of memory position based comparators for `RedBlackTree`s might not always yield the best result, and together with that that the size of those trees might matter, too, as operations on them are O(log(n)) and can touch quite a lot of objects.

An example of this is [mRunsAvail](https://searchfox.org/mozilla-central/rev/e24f7f322960a39f9ef644a31b6026994db73850/memory/build/mozjemalloc.cpp#1172-1174) where we are [mixing a size based comparator with a position based one](https://searchfox.org/mozilla-central/rev/e24f7f322960a39f9ef644a31b6026994db73850/memory/build/mozjemalloc.cpp#956-967), and also chunk comparators use similar conditions.

Example:
`mRunsAvail`'s primary use seems to be "find a run of at least size X". That means the sort criteria "size" could be enough if then we had just a plain list of runs behind each size, getting us a potentially much smaller and much more stable tree. The difficulty here is that we cannot easily use hash maps or other standard implementations, as we must avoid normal allocations during these operations. We could probably use the already added `DoublyLinkedListElement<arena_run_t>` on runs and add a `DoublyLinkedList<arena_run_t> mAvailableSameSizeSiblings` list to `arena_run_t` itself, putting only ever 1 run of the same size into `mRunsAvail` and handle the siblings inside that additional list. This would reduce the cost of adding, removing and finding those runs (under the assumption that we have many runs of the same size) and also get us for free a "most recently made available" policy for those runs on re-use.

But as a first step, we should look out for `RedBlackTree` operations in detailed enough profiles in order to see if this is worth it.

Working on bug 1924444 showed that the current usage of memory position based comparators for `RedBlackTree`s might not always yield the best result, and together with that that the size of those trees might matter, too, as operations on them are O(log(n)) and can touch quite a lot of objects.

An example of this is [mRunsAvail](https://searchfox.org/mozilla-central/rev/e24f7f322960a39f9ef644a31b6026994db73850/memory/build/mozjemalloc.cpp#1172-1174) where we are [mixing a size based comparator with a position based one](https://searchfox.org/mozilla-central/rev/e24f7f322960a39f9ef644a31b6026994db73850/memory/build/mozjemalloc.cpp#956-967), and also chunk comparators use similar conditions.