Bitmap avoids a redundant splay operation to speed up tree linking.
A redundant tree splay operation in `bitmap_tree_link_element` is removed, improving performance by 20% in an artificial test case.
This commit optimizes the bitmap_tree_link_element function by removing a redundant splay operation. Previously, the function would splay the tree a second time to ensure the root was a neighbor of the element to be inserted, even though callers had already performed a similar splay. Eliminating this unnecessary work yields a 20% performance improvement in a controlled test.
In Details
The bitmap_tree_link_element function, found in bitmap.cc, is part of GCC's internal bitmap data structure implementation. It now relies on its callers to have already performed a splay operation, avoiding duplicating effort within the function itself. This optimization targets the overhead of tree manipulation during element insertion.
For Context
GCC, the GNU Compiler Collection, uses various internal data structures to manage information during compilation. One such structure is a bitmap, which efficiently stores sets of bits. This commit optimizes a specific operation within the bitmap's tree-based implementation, called bitmap_tree_link_element. This function is responsible for linking new elements into the bitmap's internal tree. The optimization avoids performing the same reorganizational step (a 'splay' operation) twice, which makes the compiler slightly faster when dealing with these data structures.