This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] libstdc++/22102 (Re: Hunting for performance...)
Hi Howard,
and thanks again for your extremely helpful feedback.
> The current standard has "after" semantics which costs 2 comparisons
> assuming a good hint.
Indeed, this is what you find in current GCC.
> The current resolution to lwg 233:
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#233
>
> proposes "adjacent" semantics which would cost 2 to 3 comparisons
> assuming a good hint (i.e. you must check before and after).
Agreed.
> N1780 proposes "before" semantics which would cost 2 comparisons
> assuming a good hint.
Agreed, again.
> With either "before" or "after" semantics, the vendor is free to spend
> 1 more comparison to implement "adjacent" semantics. This may or may
> not be more expensive for the client. That 1 more comparison might
> save an additional Log N comparisons (or it might not). It is a
> gamble. The current resolution to lwg 233 mandates that gamble.
Ok. Fine. Then the below probably would be an improvement wrt the
current GCC situation. If nobody (myseld included ;) finds major flaws
in it during the next days, I'd like to have it in mainline first, and
then in 4_0-branch too, since it fixes a (performance) regression (in
some cases). Then, for mainline only, I'd like to also implement in
RB-tree code the additional insert at the lower bound, for the full
glory of Howard, LWG, and, well, GCC! ;)
(already passes tests on x86-linux)
Paolo.
//////////////////
2005-06-XX Paolo Carlini <pcarlini@suse.de>
PR libstdc++/22102
* include/bits/stl_tree.h (insert_unique(iterator, const _Val&),
insert_equal((iterator, const _Val&)): Reimplement to check both
before and after, as per the algorithm "ignore hint if wrong" of
ISO paper N1780.
Index: stl_tree.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_tree.h,v
retrieving revision 1.45
diff -p -r1.45 stl_tree.h
*** stl_tree.h 26 Feb 2005 23:33:44 -0000 1.45
--- stl_tree.h 17 Jun 2005 19:33:37 -0000
*************** namespace std
*** 893,926 ****
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(iterator __position, const _Val& __v)
{
! if (__position._M_node == _M_end()
! || __position._M_node == _M_rightmost())
{
! if (size() > 0
! && _M_impl._M_key_compare(_S_key(_M_rightmost()),
! _KeyOfValue()(__v)))
! return _M_insert(0, _M_rightmost(), __v);
! else
! return insert_unique(__v).first;
! }
! else
! {
! iterator __after = __position;
! ++__after;
! if (_M_impl._M_key_compare(_S_key(__position._M_node),
! _KeyOfValue()(__v))
! && _M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key(__after._M_node)))
{
! if (_S_right(__position._M_node) == 0)
! return _M_insert(0, __position._M_node, __v);
else
! return _M_insert(__after._M_node, __after._M_node, __v);
! // First argument just needs to be non-null.
}
else
! return insert_unique(__v).first;
}
}
template<typename _Key, typename _Val, typename _KeyOfValue,
--- 893,951 ----
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(iterator __position, const _Val& __v)
{
! if (size() > 0)
{
! // end()
! if (__position._M_node == _M_end())
! {
! if (_M_impl._M_key_compare(_S_key(_M_rightmost()),
! _KeyOfValue()(__v)))
! return _M_insert(0, _M_rightmost(), __v);
! else
! return insert_unique(__v).first;
! }
! else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key(__position._M_node)))
! {
! // First, try before...
! iterator __before = __position;
! if (__position._M_node == _M_leftmost()) // begin()
! return _M_insert(_M_leftmost(), _M_leftmost(), __v);
! else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
! _KeyOfValue()(__v)))
! {
! if (_S_right(__before._M_node) == 0)
! return _M_insert(0, __before._M_node, __v);
! else
! return _M_insert(__position._M_node,
! __position._M_node, __v);
! }
! else
! return insert_unique(__v).first;
! }
! else if (_M_impl._M_key_compare(_S_key(__position._M_node),
! _KeyOfValue()(__v)))
{
! // ... then try after.
! iterator __after = __position;
! if (__position._M_node == _M_rightmost())
! return _M_insert(0, _M_rightmost(), __v);
! else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key((++__after)._M_node)))
! {
! if (_S_right(__position._M_node) == 0)
! return _M_insert(0, __position._M_node, __v);
! else
! return _M_insert(__after._M_node, __after._M_node, __v);
! }
else
! return insert_unique(__v).first;
}
else
! return __position; // Equivalent keys.
}
+ else
+ return insert_unique(__v).first;
}
template<typename _Key, typename _Val, typename _KeyOfValue,
*************** namespace std
*** 929,962 ****
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_equal(iterator __position, const _Val& __v)
{
! if (__position._M_node == _M_end()
! || __position._M_node == _M_rightmost())
{
! if (size() > 0
! && !_M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key(_M_rightmost())))
! return _M_insert(0, _M_rightmost(), __v);
! else
! return insert_equal(__v);
! }
! else
! {
! iterator __after = __position;
! ++__after;
! if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key(__position._M_node))
! && !_M_impl._M_key_compare(_S_key(__after._M_node),
! _KeyOfValue()(__v)))
{
! if (_S_right(__position._M_node) == 0)
! return _M_insert(0, __position._M_node, __v);
else
! return _M_insert(__after._M_node, __after._M_node, __v);
! // First argument just needs to be non-null.
}
else
! return insert_equal(__v);
}
}
template<typename _Key, typename _Val, typename _KoV,
--- 954,1009 ----
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_equal(iterator __position, const _Val& __v)
{
! if (size() > 0)
{
! // end()
! if (__position._M_node == _M_end())
! {
! if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key(_M_rightmost())))
! return _M_insert(0, _M_rightmost(), __v);
! else
! return insert_equal(__v);
! }
! else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
! _KeyOfValue()(__v)))
{
! // First, try before...
! iterator __before = __position;
! if (__position._M_node == _M_leftmost()) // begin()
! return _M_insert(_M_leftmost(), _M_leftmost(), __v);
! else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
! _S_key((--__before)._M_node)))
! {
! if (_S_right(__before._M_node) == 0)
! return _M_insert(0, __before._M_node, __v);
! else
! return _M_insert(__position._M_node,
! __position._M_node, __v);
! }
else
! return insert_equal(__v);
}
else
! {
! // ... then try after.
! iterator __after = __position;
! if (__position._M_node == _M_rightmost())
! return _M_insert(0, _M_rightmost(), __v);
! else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
! _KeyOfValue()(__v)))
! {
! if (_S_right(__position._M_node) == 0)
! return _M_insert(0, __position._M_node, __v);
! else
! return _M_insert(__after._M_node, __after._M_node, __v);
! }
! else
! return insert_equal(__v);
! }
}
+ else
+ return insert_equal(__v);
}
template<typename _Key, typename _Val, typename _KoV,