[RFC] optional fast iterators for set/map in libstdc++
Janis Johnson
janis187@us.ibm.com
Fri May 8 00:59:00 GMT 2009
I'd like some advice about this speedup to iterators for red-black
trees. The idea comes from developers of IBM's proprietary C++
product who implemented it in the C++ library used on AIX. Their
users access the functionality with -Dsomething when compiling, but
it could be done by adding a g++ option that defines the macro, like:
-ffast-set-map-iterators
This option augments the base class for map<>, set<>, multimap<> and
multiset<> template classes to allow faster iterator operations.
Warning: -ffast-set-map-iterators causes GCC to generate code that
is not binary compatible with code generated without the option.
All code that operates on the same set or map objects must use the
same variant of this option.
The functional changes are all within include/bits/stl_tree.h and have
no effect on the compilation of src/tree.cc, which doesn't need to
know the size of the class. It uglifies the header with code
protected by #ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__.
Why do this? Because it speeds up 447.dealII from SPEC CPU2006. On
powerpc64-linux, the speedup over our usual peak options is 32% for
-m32, 26% for -m64. The two other CPU2006 benchmarks that use set
and/or map are omnetpp and xalancbmk, which speed up between 1% and
1.4%. Those speedups are based on the the middle result from 3 runs,
using mainline from a couple of months ago. I have not yet run
benchmarks and any other targets.
libstdc++ tests compiled with -D__GLIBCXX_USE_FAST_SET_MAP_ITERAOR__
all pass. I'm figuring out how to add tests for this option, possibly
by finding a set of tests that provide good test coverage and
including them in new tests files that define the macro.
Would a patch like this be acceptable? What changes might it need
before formal submission? Should there be a g++ option to enable it,
like -ffast-set-map-iterators, or can we tell users to turn it on
with -D?
Here are the changes to the library itself, without documentation or
new tests. Two existing tests are affected by line numbers within
the modified header file.
2009-05-07 Janis Johnson <janis187@us.ibm.com>
* include/bits/stl_tree.h: Add comment about effect of new macro
__GLIBCXX_USE_FAST_SET_MAP_ITERATOR__.
(_Rb_tree_node_base): Add next and prev pointers if macro is defined.
(operator++): Use next pointer if macro is defined.
(operator--): Use prev pointer if macro is defined.
(_Rb_tree_insert_into_sorted_list, _Rb_tree_remove_from_sorted_list,
_Rb_tree_recreate_sorted_list(_Rb_tree_node_base& __header): New.
(_Rb_tree_impl::_M_initialize): Initialize new pointers.
(_Rb_tree(const _Rb_tree &)): Recreate sorted list.
(_Rb_tree<>::operator==): Ditto.
(_Rb_tree<>::_M_insert): Insert into sorted list.
(_Rb_tree<>::_M_insert_lower): Ditto.
(_Rb_tree<>::swap): Adjust links for sorted list.
(_Rb_tree<>::erase): Remove from sorted list.
* testsuite/23_containers/set/operators/1_neg.cc: Adjust line numbers.
* testsuite/23_containers/map/operators/1_neg.cc: Ditto.
Index: libstdc++-v3/include/bits/stl_tree.h
===================================================================
--- libstdc++-v3/include/bits/stl_tree.h (revision 147259)
+++ libstdc++-v3/include/bits/stl_tree.h (working copy)
@@ -81,6 +81,13 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
// (2) when a node being deleted has two children its successor node
// is relinked into its place, rather than copied, so that the only
// iterators invalidated are those referring to the deleted node.
+ //
+ // (3) When __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__ is defined, in
+ // addition to the links for the red-black tree there is a second
+ // set of links maintaining a sorted doubly-linked list to allow a
+ // single link traversal for increment and decrement operations.
+ // The list is circular, with the header between the leftmost and
+ // rightmost nodes.
enum _Rb_tree_color { _S_red = false, _S_black = true };
@@ -93,6 +100,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_Base_ptr _M_parent;
_Base_ptr _M_left;
_Base_ptr _M_right;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _Base_ptr _M_next;
+ _Base_ptr _M_prev;
+#endif
static _Base_ptr
_S_minimum(_Base_ptr __x)
@@ -181,7 +192,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_Self&
operator++()
{
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_node = _M_node->_M_next;
+#else
_M_node = _Rb_tree_increment(_M_node);
+#endif
return *this;
}
@@ -189,14 +204,22 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
operator++(int)
{
_Self __tmp = *this;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_node = _M_node->_M_next;
+#else
_M_node = _Rb_tree_increment(_M_node);
+#endif
return __tmp;
}
_Self&
operator--()
{
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_node = _M_node->_M_prev;
+#else
_M_node = _Rb_tree_decrement(_M_node);
+#endif
return *this;
}
@@ -204,7 +227,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
operator--(int)
{
_Self __tmp = *this;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_node = _M_node->_M_prev;
+#else
_M_node = _Rb_tree_decrement(_M_node);
+#endif
return __tmp;
}
@@ -256,7 +283,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_Self&
operator++()
{
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_node = _M_node->_M_next;
+#else
_M_node = _Rb_tree_increment(_M_node);
+#endif
return *this;
}
@@ -264,14 +295,22 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
operator++(int)
{
_Self __tmp = *this;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_node = _M_node->_M_next;
+#else
_M_node = _Rb_tree_increment(_M_node);
+#endif
return __tmp;
}
_Self&
operator--()
{
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_node = _M_node->_M_prev;
+#else
_M_node = _Rb_tree_decrement(_M_node);
+#endif
return *this;
}
@@ -279,7 +318,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
operator--(int)
{
_Self __tmp = *this;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_node = _M_node->_M_prev;
+#else
_M_node = _Rb_tree_decrement(_M_node);
+#endif
return __tmp;
}
@@ -316,6 +359,19 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
_Rb_tree_node_base& __header) throw ();
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ void
+ _Rb_tree_insert_into_sorted_list(const bool __insert_left,
+ _Rb_tree_node_base* __x,
+ _Rb_tree_node_base* __p,
+ _Rb_tree_node_base& __header);
+
+ void
+ _Rb_tree_remove_from_sorted_list(_Rb_tree_node_base* __x);
+
+ void
+ _Rb_tree_recreate_sorted_list(_Rb_tree_node_base& __header);
+#endif
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc = allocator<_Val> >
@@ -447,6 +503,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
this->_M_header._M_parent = 0;
this->_M_header._M_left = &this->_M_header;
this->_M_header._M_right = &this->_M_header;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ this->_M_header._M_next = &this->_M_header;
+ this->_M_header._M_prev = &this->_M_header;
+#endif
}
};
@@ -603,6 +663,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
_M_impl._M_node_count = __x._M_impl._M_node_count;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _Rb_tree_recreate_sorted_list(this->_M_impl._M_header);
+#endif
}
}
@@ -863,6 +926,9 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
_M_impl._M_node_count = __x._M_impl._M_node_count;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _Rb_tree_recreate_sorted_list(this->_M_impl._M_header);
+#endif
}
}
return *this;
@@ -880,6 +946,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_Link_type __z = _M_create_node(__v);
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _Rb_tree_insert_into_sorted_list(__insert_left, __z,
+ const_cast<_Base_ptr>(__p),
+ this->_M_impl._M_header);
+#endif
_Rb_tree_insert_and_rebalance(__insert_left, __z,
const_cast<_Base_ptr>(__p),
this->_M_impl._M_header);
@@ -899,6 +970,10 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_Link_type __z = _M_create_node(__v);
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _Rb_tree_insert_into_sorted_list(__insert_left, __z, __p,
+ this->_M_impl._M_header);
+#endif
_Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
this->_M_impl._M_header);
++_M_impl._M_node_count;
@@ -1122,6 +1197,12 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
__t._M_root() = 0;
__t._M_leftmost() = __t._M_end();
__t._M_rightmost() = __t._M_end();
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_end()->_M_next = _M_leftmost();
+ _M_leftmost()->_M_prev = _M_end();
+ _M_end()->_M_prev = _M_rightmost();
+ _M_rightmost()->_M_next = _M_end();
+#endif
}
}
else if (__t._M_root() == 0)
@@ -1134,6 +1215,14 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_M_root() = 0;
_M_leftmost() = _M_end();
_M_rightmost() = _M_end();
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ __t._M_end()->_M_next = __t._M_leftmost();
+ __t._M_leftmost()->_M_prev = __t._M_end();
+ __t._M_end()->_M_prev = __t._M_rightmost();
+ __t._M_rightmost()->_M_next = __t._M_end();
+ _M_end()->_M_next = _M_end();
+ _M_end()->_M_prev = _M_end();
+#endif
}
else
{
@@ -1143,6 +1232,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_M_root()->_M_parent = _M_end();
__t._M_root()->_M_parent = __t._M_end();
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _M_end()->_M_next = _M_leftmost();
+ _M_leftmost()->_M_prev = _M_end();
+ _M_end()->_M_prev = _M_rightmost();
+ _M_rightmost()->_M_next = _M_end();
+ __t._M_end()->_M_next = __t._M_leftmost();
+ __t._M_leftmost()->_M_prev = __t._M_end();
+ __t._M_end()->_M_prev = __t._M_rightmost();
+ __t._M_rightmost()->_M_next = __t._M_end();
+#endif
}
// No need to swap header's color as it does not change.
std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
@@ -1341,7 +1440,11 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
erase(iterator __position)
{
- _Link_type __y =
+ _Link_type __y;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _Rb_tree_remove_from_sorted_list(__position._M_node);
+#endif
+ __y =
static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
(__position._M_node,
this->_M_impl._M_header));
@@ -1355,7 +1458,12 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
erase(const_iterator __position)
{
- _Link_type __y =
+ _Link_type __y;
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ _Rb_tree_remove_from_sorted_list(const_cast<_Base_ptr>
+ (__position._M_node));
+#endif
+ __y =
static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
(const_cast<_Base_ptr>(__position._M_node),
this->_M_impl._M_header));
@@ -1490,6 +1598,72 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
return true;
}
+#ifdef __GLIBCXX_USE_FAST_SET_MAP_ITERATOR__
+ inline void
+ _Rb_tree_insert_into_sorted_list(const bool __insert_left,
+ _Rb_tree_node_base* __x,
+ _Rb_tree_node_base* __p,
+ _Rb_tree_node_base& __header)
+ {
+ if (__insert_left)
+ {
+ if (__p == &__header)
+ {
+ // Set up the initial circular doubly-linked list.
+ __p->_M_next = __x;
+ __p->_M_prev = __x;
+ __x->_M_next = __p;
+ __x->_M_prev = __p;
+ }
+ else
+ {
+ // Include in the doubly-linked list prior to __p.
+ __x->_M_next = __p;
+ __x->_M_prev = __p->_M_prev;
+ __p->_M_prev->_M_next = __x;
+ __p->_M_prev = __x;
+ }
+ }
+ else
+ {
+ // Include in the doubly-linked list after __p.
+ __x->_M_prev = __p;
+ __x->_M_next = __p->_M_next;
+ __p->_M_next->_M_prev = __x;
+ __p->_M_next = __x;
+ }
+ }
+
+ inline void
+ _Rb_tree_remove_from_sorted_list(_Rb_tree_node_base* __x)
+ {
+ __x->_M_next->_M_prev = __x->_M_prev;
+ __x->_M_prev->_M_next = __x->_M_next;
+ }
+
+ inline void
+ _Rb_tree_recreate_sorted_list(_Rb_tree_node_base& __header)
+ {
+ _Rb_tree_node_base *__x, *__y, *__rightmost;
+
+ __rightmost = __header._M_right; // rightmost
+ __x = __header._M_left; // leftmost
+ __x->_M_prev = &__header; // leftmost links to header
+ __header._M_next = __x;
+
+ while (__x != __rightmost)
+ {
+ __y = _Rb_tree_increment(__x);
+ __x->_M_next = __y;
+ __y->_M_prev = __x;
+ __x = __y;
+ }
+
+ __rightmost->_M_next = &__header; // rightmost links to header
+ __header._M_prev = __rightmost;
+ }
+#endif
+
_GLIBCXX_END_NAMESPACE
#endif
Index: libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc
===================================================================
--- libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc (revision 147259)
+++ libstdc++-v3/testsuite/23_containers/set/operators/1_neg.cc (working copy)
@@ -39,5 +39,5 @@ void test01()
test &= itr == setByName.end(); // { dg-error "no" }
}
-// { dg-error "candidates are" "" { target *-*-* } 287 }
-// { dg-error "candidates are" "" { target *-*-* } 291 }
+// { dg-error "candidates are" "" { target *-*-* } 330 }
+// { dg-error "candidates are" "" { target *-*-* } 334 }
Index: libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc
===================================================================
--- libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc (revision 147259)
+++ libstdc++-v3/testsuite/23_containers/map/operators/1_neg.cc (working copy)
@@ -41,5 +41,5 @@ void test01()
test &= itr == mapByName.end(); // { dg-error "no" }
}
-// { dg-error "candidates are" "" { target *-*-* } 212 }
-// { dg-error "candidates are" "" { target *-*-* } 216 }
+// { dg-error "candidates are" "" { target *-*-* } 239 }
+// { dg-error "candidates are" "" { target *-*-* } 243 }
More information about the Gcc-patches
mailing list