This is the mail archive of the
gcc-help@gcc.gnu.org
mailing list for the GCC project.
RB Tree performance aspects in a map
- From: Anitha Boyapati <anithab at sankhya dot com>
- To: gcc-help at gcc dot gnu dot org
- Date: Fri, 4 Jan 2008 20:31:32 +0530 (IST)
- Subject: RB Tree performance aspects in a map
Hi,
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.
--
Regards,
Anitha B
@S A N K H Y A