Ivan Kazmenko:
Thank you all for assistance, I've finally pinned it down!
This is great. The first step to solve a problem is to find it. The second step is to formalize it. So I suggest you to create a small benchmark that shows what you mean (it should not include RedBlackTree) and put it in Bugzilla, with some timings.
Bye, bearophile