RB Tree performance aspects in a map
Sat Jan 5 17:20:00 GMT 2008
This is more of analytical question. Perhaps someone can discern me when
an _Rb_Tree::find becomes expensive.
Going into details, I have a map<long, TestVec>. TestVec is a vector of
trees(once can think of a forest). So, I kind of insert this TestVec
rather heavily. This can be thought similar to inserting a single TestVec
for each instruction execution in a simulator of a cross compiler tool chain.
A profiling version shows that _Rb_Tree::find() is taking about 15% of the
time. As such this is a not a serious concern but it would be nice to know
more on factors that would affect balancing these Red Black trees.
One thought particularly influencing is operator<. When the key is a user
defined class object, obviously operator< impacts. My question is to what
extent can we expect inlining of operator< (if it gets inlined at all).
Probably, I have not asked right point about operator<. Various views on
this will be truly helpful.
@S A N K H Y A
More information about the Gcc-help