This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: [Patch] Performance and memory usage improvements for stl_tree.h
- From: Gawain Bolton <gp dot bolton at computer dot org>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Cc: Nathan Myers <ncm-nospam at cantrip dot org>
- Date: Wed, 26 Feb 2003 18:05:13 +0100
- Subject: Re: [Patch] Performance and memory usage improvements for stl_tree.h
- References: <3E57882B.3050200@computer.org> <20030222162959.GC25068@tofu.dreamhost.com>
Nathan Myers wrote:
On Sat, Feb 22, 2003 at 03:24:43PM +0100, Gawain Bolton wrote:
This is an updated patch to improve stl_tree.h. It affects the
std::map, std::multimap, std::set and std::multiset container types.
This patch has been updated to show the differences with respect to
what ( I hope) is the latest version in CVS. I'm hoping that this will
help these changes get in.
This patch improves performance when creating and destroying containers,
as well as reducing the amount of memory required since the header no
longer allocates storage for the container's type.
I vote to put this one in immediately. The only think I'd fix along
the way is some of the comments that go beyond 80 columns.
Nathan Myers
ncm at cantrip dot org
Thanks for your comments Nathan. I have fixed the problem concerning
comments beyond 80 columns and removed the use of static_cast<> as this
increased the size of generated code bloat and is therefore probably
less efficient than a C style cast.
Please find attached the corresponding patch.
Cheers,
Gawain
Index: stl_tree.h
===================================================================
RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_tree.h,v
retrieving revision 1.19
diff -u -r1.19 stl_tree.h
--- stl_tree.h 16 Jan 2003 20:30:24 -0000 1.19
+++ stl_tree.h 26 Feb 2003 16:58:54 -0000
@@ -192,7 +192,7 @@
typedef _Rb_tree_node<_Val>* _Link_type;
_Rb_tree_iterator() {}
- _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
+ _Rb_tree_iterator(_Rb_tree_node_base * __x) { _M_node = __x; }
_Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }
reference
@@ -528,13 +528,13 @@
get_allocator() const { return _M_node_allocator; }
_Rb_tree_alloc_base(const allocator_type& __a)
- : _M_node_allocator(__a), _M_header(0) {}
+ : _M_node_allocator(__a) {}
protected:
typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type
_M_node_allocator;
- _Rb_tree_node<_Tp>* _M_header;
+ _Rb_tree_node_base _M_header;
_Rb_tree_node<_Tp>*
_M_get_node() { return _M_node_allocator.allocate(1); }
@@ -552,10 +552,10 @@
typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
- _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {}
+ _Rb_tree_alloc_base(const allocator_type&) {}
protected:
- _Rb_tree_node<_Tp>* _M_header;
+ _Rb_tree_node_base _M_header;
typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type
_Alloc_type;
@@ -576,8 +576,7 @@
typedef typename _Base::allocator_type allocator_type;
_Rb_tree_base(const allocator_type& __a)
- : _Base(__a) { this->_M_header = _M_get_node(); }
- ~_Rb_tree_base() { _M_put_node(this->_M_header); }
+ : _Base(__a) {}
};
@@ -645,14 +644,17 @@
_Compare _M_key_compare;
_Link_type&
- _M_root() const { return (_Link_type&) this->_M_header->_M_parent; }
+ _M_root() const { return (_Link_type&) this->_M_header._M_parent; }
_Link_type&
- _M_leftmost() const { return (_Link_type&) this->_M_header->_M_left; }
+ _M_leftmost() const { return (_Link_type&) this->_M_header._M_left; }
_Link_type&
- _M_rightmost() const { return (_Link_type&) this->_M_header->_M_right; }
+ _M_rightmost() const { return (_Link_type&) this->_M_header._M_right; }
+ _Link_type
+ _M_end() { return (_Link_type) &this->_M_header; }
+
static _Link_type&
_S_left(_Link_type __x) { return (_Link_type&)(__x->_M_left); }
@@ -668,9 +670,6 @@
static const _Key&
_S_key(_Link_type __x) { return _KeyOfValue()(_S_value(__x)); }
- static _Rb_tree_color&
- _S_color(_Link_type __x) { return __x->_M_color; }
-
static _Link_type&
_S_left(_Base_ptr __x) { return (_Link_type&)(__x->_M_left); }
@@ -737,8 +736,8 @@
_M_empty_initialize();
else
{
- _S_color(this->_M_header) = _M_red;
- _M_root() = _M_copy(__x._M_root(), this->_M_header);
+ _S_color(&this->_M_header) = _M_red;
+ _M_root() = _M_copy(__x._M_root(), &this->_M_header);
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
}
@@ -753,11 +752,11 @@
private:
void _M_empty_initialize()
{
- _S_color(this->_M_header) = _M_red; // used to distinguish header from
- // __root, in iterator.operator++
+ // Used to distinguish header from __root, in iterator.operator++
+ _S_color(&this->_M_header) = _M_red;
_M_root() = 0;
- _M_leftmost() = this->_M_header;
- _M_rightmost() = this->_M_header;
+ this->_M_header._M_left = &this->_M_header;
+ this->_M_header._M_right = &this->_M_header;
}
public:
@@ -772,10 +771,10 @@
begin() const { return _M_leftmost(); }
iterator
- end() { return this->_M_header; }
+ end() { return &this->_M_header; }
const_iterator
- end() const { return this->_M_header; }
+ end() const { return const_cast<_Rb_tree_node_base *>(&this->_M_header); }
reverse_iterator
rbegin() { return reverse_iterator(end()); }
@@ -801,9 +800,12 @@
void
swap(_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>& __t)
{
- std::swap(this->_M_header, __t._M_header);
- std::swap(_M_node_count, __t._M_node_count);
- std::swap(_M_key_compare, __t._M_key_compare);
+ std::swap(this->_M_header._M_parent, __t._M_header._M_parent);
+ std::swap(this->_M_header._M_left, __t._M_header._M_left);
+ std::swap(this->_M_header._M_right, __t._M_header._M_right);
+ // No need to swap header's color as it does not change.
+ std::swap(_M_node_count, __t._M_node_count);
+ std::swap(_M_key_compare, __t._M_key_compare);
}
// Insert/erase.
@@ -845,9 +847,9 @@
if (_M_node_count != 0)
{
_M_erase(_M_root());
- _M_leftmost() = this->_M_header;
+ this->_M_header._M_left = &this->_M_header;
_M_root() = 0;
- _M_rightmost() = this->_M_header;
+ this->_M_header._M_right = &this->_M_header;
_M_node_count = 0;
}
}
@@ -955,12 +957,12 @@
if (__x._M_root() == 0)
{
_M_root() = 0;
- _M_leftmost() = this->_M_header;
- _M_rightmost() = this->_M_header;
+ this->_M_header._M_left = &this->_M_header;
+ this->_M_header._M_right = &this->_M_header;
}
else
{
- _M_root() = _M_copy(__x._M_root(), this->_M_header);
+ _M_root() = _M_copy(__x._M_root(), &this->_M_header);
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
_M_node_count = __x._M_node_count;
@@ -979,13 +981,13 @@
_Link_type __y = (_Link_type) __y_;
_Link_type __z;
- if (__y == this->_M_header || __x != 0 ||
+ if (__y == &this->_M_header || __x != 0 ||
_M_key_compare(_KeyOfValue()(__v), _S_key(__y)))
{
__z = _M_create_node(__v);
_S_left(__y) = __z; // also makes _M_leftmost() = __z
- // when __y == _M_header
- if (__y == this->_M_header)
+ // when __y == &_M_header
+ if (__y == &this->_M_header)
{
_M_root() = __z;
_M_rightmost() = __z;
@@ -1004,7 +1006,7 @@
_S_parent(__z) = __y;
_S_left(__z) = 0;
_S_right(__z) = 0;
- _Rb_tree_rebalance(__z, this->_M_header->_M_parent);
+ _Rb_tree_rebalance(__z, this->_M_header._M_parent);
++_M_node_count;
return iterator(__z);
}
@@ -1015,7 +1017,7 @@
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_equal(const _Val& __v)
{
- _Link_type __y = this->_M_header;
+ _Link_type __y = _M_end();
_Link_type __x = _M_root();
while (__x != 0)
{
@@ -1033,7 +1035,7 @@
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_unique(const _Val& __v)
{
- _Link_type __y = this->_M_header;
+ _Link_type __y = _M_end();
_Link_type __x = _M_root();
bool __comp = true;
while (__x != 0)
@@ -1060,7 +1062,7 @@
_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
insert_unique(iterator __position, const _Val& __v)
{
- if (__position._M_node == this->_M_header->_M_left)
+ if (__position._M_node == this->_M_header._M_left)
{
// begin()
if (size() > 0 &&
@@ -1070,7 +1072,7 @@
else
return insert_unique(__v).first;
}
- else if (__position._M_node == this->_M_header)
+ else if (__position._M_node == &this->_M_header)
{
// end()
if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v)))
@@ -1102,7 +1104,7 @@
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
insert_equal(iterator __position, const _Val& __v)
{
- if (__position._M_node == this->_M_header->_M_left)
+ if (__position._M_node == this->_M_header._M_left)
{
// begin()
if (size() > 0 &&
@@ -1112,7 +1114,7 @@
else
return insert_equal(__v);
}
- else if (__position._M_node == this->_M_header)
+ else if (__position._M_node == &this->_M_header)
{
// end()
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost())))
@@ -1168,9 +1170,9 @@
{
_Link_type __y =
(_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node,
- this->_M_header->_M_parent,
- this->_M_header->_M_left,
- this->_M_header->_M_right);
+ this->_M_header._M_parent,
+ this->_M_header._M_left,
+ this->_M_header._M_right);
destroy_node(__y);
--_M_node_count;
}
@@ -1264,9 +1266,8 @@
typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
{
- _Link_type __y
- = this->_M_header; // Last node which is not less than __k.
- _Link_type __x = _M_root(); // Current node.
+ _Link_type __y = _M_end(); // Last node which is not less than __k.
+ _Link_type __x = _M_root(); // Current node.
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
@@ -1285,8 +1286,7 @@
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
find(const _Key& __k) const
{
- _Link_type __y
- = this->_M_header; // Last node which is not less than __k.
+ _Link_type __y = _M_end(); // Last node which is not less than __k.
_Link_type __x = _M_root(); // Current node.
while (__x != 0)
@@ -1318,9 +1318,8 @@
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
lower_bound(const _Key& __k)
{
- _Link_type __y
- = this->_M_header; /* Last node which is not less than __k. */
- _Link_type __x = _M_root(); /* Current node. */
+ _Link_type __y = _M_end(); // Last node which is not less than __k
+ _Link_type __x = _M_root(); // Current node.
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
@@ -1337,9 +1336,8 @@
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
lower_bound(const _Key& __k) const
{
- _Link_type __y
- = this->_M_header; /* Last node which is not less than __k. */
- _Link_type __x = _M_root(); /* Current node. */
+ _Link_type __y = _M_end(); // Last node which is not less than __k.
+ _Link_type __x = _M_root(); // Current node.
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k))
@@ -1356,9 +1354,8 @@
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
upper_bound(const _Key& __k)
{
- _Link_type __y
- = this->_M_header; /* Last node which is greater than __k. */
- _Link_type __x = _M_root(); /* Current node. */
+ _Link_type __y = _M_end(); // Last node which is greater than __k.
+ _Link_type __x = _M_root(); // Current node.
while (__x != 0)
if (_M_key_compare(__k, _S_key(__x)))
@@ -1375,9 +1372,8 @@
_Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
upper_bound(const _Key& __k) const
{
- _Link_type __y
- = this->_M_header; /* Last node which is greater than __k. */
- _Link_type __x = _M_root(); /* Current node. */
+ _Link_type __y = _M_end(); // Last node which is greater than __k.
+ _Link_type __x = _M_root(); // Current node.
while (__x != 0)
if (_M_key_compare(__k, _S_key(__x)))
@@ -1434,8 +1430,8 @@
{
if (_M_node_count == 0 || begin() == end())
return _M_node_count == 0 && begin() == end() &&
- this->_M_header->_M_left == this->_M_header
- && this->_M_header->_M_right == this->_M_header;
+ this->_M_header._M_left == &this->_M_header &&
+ this->_M_header._M_right == &this->_M_header;
int __len = __black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it)