Re: [RFC] optional fast iterators for set/map in libstdc++

[Paolo Bonzini <paolo dot bonzini at gmail dot com>]

Paolo Carlini wrote:
> Paolo Carlini wrote:
>>> implemented using only 2 bits rather than 16 bytes of overhead (and then
>>> you can in principle get rid of the parent pointer, and end up actually
>>> saving memory).
>> Thanks Paolo. Then I also suggest exploring other ways to implement
>> the same basic idea.
> Note that the _Rb_tree_color enum can certainly host the two bits
> without changing the memory layout of _Rb_tree_node_base. I wonder if we
> could even implement some of this (not optimally, maybe) without
> breaking binary compatibility... Paolo, any idea?

I don't think so, unfortunately.  You can do it without breaking memory
layout, because there is padding after _M_color, or you can emulate
bitfields within the enum. but from inspecting stl_tree.h, it looks like
there is code doing "_M_left != NULL" that is included in every
instantiation, then no, you'd break binary compatibility.

With thread trees, instead of checking _M_left and _M_right you have to
check the two bits ("is left link a thread to the predecessor?" and "is
right link a thread to the successor?") I mentioned.

The speedup possible could be half of what you have with Janis's patch,
expecting the improved (optimal) cache utilization of Janis's patch to
offset the benefits of the memory savings.  That's because you have,
compared to Janis's patch:

- 1 extra dereference per item with threaded trees (you visit each node
once going down to the left, and once going up through the threads)

- 2 extra dereferences per item with current code (you visit
left->parent->right->parent, and threading saves the visit of parent
pointers made when going up from the right---thus it must be 1 extra
dereference compared to threaded trees).

BTW, I looked up libavl, and removing parent pointers is feasible but
slows down the rebalancing.

Paolo