https://gcc.gnu.org/g:e73194188cea9c4b41eccadb74bfbd3f0c52b8bd
commit r17-1347-ge73194188cea9c4b41eccadb74bfbd3f0c52b8bd Author: Richard Sandiford <[email protected]> Date: Thu Jun 4 16:40:44 2026 +0100 bitmap: Speed up bitmap_tree_link_element bitmap_tree_link_element first splays the tree to ensure that the root is a neighbour of the element that we want to insert. But the callers have already done the same kind of splay operation in order to prove that no existing element has the required index. Repeating the operation isn't free. For example, if the first splay operation leaves the left neighbour N in the root, the second splay operation would need to search N->right->left (N->next->prev), and similarly in reverse for a right neighbour. This gives a reproducible 20% improvement in an artificial test that inserted 2,000,000 pseudo-random elements (keeping the same sequence for all tests). gcc/ * bitmap.cc (bitmap_tree_link_element): Require callers to have done a splay operation. Avoid doing another one here. Diff: --- gcc/bitmap.cc | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/gcc/bitmap.cc b/gcc/bitmap.cc index 91c1019cb34c..fdea7200f1da 100644 --- a/gcc/bitmap.cc +++ b/gcc/bitmap.cc @@ -503,16 +503,18 @@ bitmap_tree_splay (bitmap head, bitmap_element *t, unsigned int indx) return t; } -/* Link bitmap element E into the current bitmap splay tree. */ +/* Link bitmap element E into the current bitmap splay tree. The caller + must have called bitmap_tree_find_element first, which guarantees that + the current root should become a neighbor of E. */ static inline void bitmap_tree_link_element (bitmap head, bitmap_element *e) { - if (head->first == NULL) + bitmap_element *t = head->first; + if (t == NULL) e->prev = e->next = NULL; else { - bitmap_element *t = bitmap_tree_splay (head, head->first, e->indx); if (e->indx < t->indx) { e->prev = t->prev;
