This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] tr1::hashtable::operator[] (final)
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Cc: Peter Doerfler <gcc at pdoerfler dot com>
- Date: Mon, 15 May 2006 17:58:19 +0200
- Subject: [Patch] tr1::hashtable::operator[] (final)
Hi,
eventually, I decided to go for something simpler (and performance-wise
more effective), leaving the insertion with hint alone (maybe I will
reconsider it soon): I'm just splitting out the second part of
insert(..., true_type) and calling it from operator[]. In this form
everything is pretty straightforward and is suitable for 4_1-branch too.
Tested x86-linux.
Paolo.
P.S. Peter, for your future contributions, do you have a Copyright
Assignment on file?!?
/////////////////
2006-05-15 Paolo Carlini <pcarlini@suse.de>
* include/tr1/hashtable (hashtable<>::m_find, m_insert_bucket): Add.
(hashtable<>::find, m_insert(const value_type&, std::tr1::true_type),
map_base<>::operator[]): Use the above.
* testsuite/performance/23_containers/insert/unordered_map_array.cc:
New.
* include/tr1/hashtable (hashtable<>::find_node,
insert(const value_type&, ...), erase_node): Rename to m_*, adjust
callers.
* include/tr1/hashtable: Minor cosmetic changes.
Index: include/tr1/hashtable
===================================================================
--- include/tr1/hashtable (revision 113737)
+++ include/tr1/hashtable (working copy)
@@ -680,8 +680,11 @@
operator[](const K& k)
{
Hashtable* h = static_cast<Hashtable*>(this);
- typename Hashtable::iterator it =
- h->insert(std::make_pair(k, mapped_type())).first;
+ typename Hashtable::hash_code_t code = h->m_hash_code(k);
+ typename Hashtable::iterator it = h->m_find(k, code);
+ if (!it.m_cur_node)
+ it = h->m_insert_bucket(std::make_pair(k, mapped_type()),
+ it.m_cur_bucket - h->m_buckets, code);
return it->second;
}
};
@@ -1032,6 +1035,9 @@
cache_hash_code>
const_iterator;
+ template<typename K, typename Pair, typename Hashtable>
+ friend struct Internal::map_base;
+
private:
typedef Internal::hash_node<Value, cache_hash_code> node;
typedef typename Allocator::template rebind<node>::other
@@ -1188,7 +1194,7 @@
public: // lookup
iterator
- find(const key_type&);
+ find(const key_type& k);
const_iterator
find(const key_type& k) const;
@@ -1202,7 +1208,7 @@
std::pair<const_iterator, const_iterator>
equal_range(const key_type& k) const;
- private: // Insert and erase helper functions
+ private: // Find, insert and erase helper functions
// ??? This dispatching is a workaround for the fact that we don't
// have partial specialization of member templates; it would be
// better to just specialize insert on unique_keys. There may be a
@@ -1217,31 +1223,35 @@
>::type
Insert_Conv_Type;
+ iterator
+ m_find(const key_type&, typename hashtable::hash_code_t) const;
+
node*
- find_node(node* p, const key_type& k,
- typename hashtable::hash_code_t c) const;
+ m_find_node(node*, const key_type&,
+ typename hashtable::hash_code_t) const;
+ iterator
+ m_insert_bucket(const value_type&, size_type,
+ typename hashtable::hash_code_t);
+
std::pair<iterator, bool>
- insert(const value_type&, std::tr1::true_type);
-
+ m_insert(const value_type&, std::tr1::true_type);
+
iterator
- insert(const value_type&, std::tr1::false_type);
+ m_insert(const value_type&, std::tr1::false_type);
void
- erase_node(node*, node**);
+ m_erase_node(node*, node**);
public: // Insert and erase
Insert_Return_Type
insert(const value_type& v)
- {
- return this->insert(v, std::tr1::integral_constant<bool,
- unique_keys>());
- }
+ { return m_insert(v, std::tr1::integral_constant<bool, unique_keys>()); }
iterator
insert(iterator, const value_type& v)
{ return iterator(Insert_Conv_Type()(this->insert(v))); }
-
+
const_iterator
insert(const_iterator, const value_type& v)
{ return const_iterator(Insert_Conv_Type()(this->insert(v))); }
@@ -1531,12 +1541,24 @@
bool c, bool ci, bool u>
typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
+ m_find(const key_type& k, typename hashtable::hash_code_t code) const
+ {
+ std::size_t n = this->bucket_index(k, code, this->bucket_count());
+ node* p = m_find_node(m_buckets[n], k, code);
+ return iterator(p, m_buckets + n);
+ }
+
+ template<typename K, typename V,
+ typename A, typename Ex, typename Eq,
+ typename H1, typename H2, typename H, typename RP,
+ bool c, bool ci, bool u>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
find(const key_type& k)
{
typename hashtable::hash_code_t code = this->m_hash_code(k);
- std::size_t n = this->bucket_index(k, code, this->bucket_count());
- node* p = find_node(m_buckets[n], k, code);
- return p ? iterator(p, m_buckets + n) : this->end();
+ iterator i = m_find(k, code);
+ return i.m_cur_node ? i : this->end();
}
template<typename K, typename V,
@@ -1548,11 +1570,10 @@
find(const key_type& k) const
{
typename hashtable::hash_code_t code = this->m_hash_code(k);
- std::size_t n = this->bucket_index(k, code, this->bucket_count());
- node* p = find_node(m_buckets[n], k, code);
- return p ? const_iterator(p, m_buckets + n) : this->end();
+ const_iterator i = const_iterator(m_find(k, code));
+ return i.m_cur_node ? i : this->end();
}
-
+
template<typename K, typename V,
typename A, typename Ex, typename Eq,
typename H1, typename H2, typename H, typename RP,
@@ -1584,7 +1605,7 @@
typename hashtable::hash_code_t code = this->m_hash_code(k);
std::size_t n = this->bucket_index(k, code, this->bucket_count());
node** head = m_buckets + n;
- node* p = find_node(*head, k, code);
+ node* p = m_find_node(*head, k, code);
if (p)
{
@@ -1617,7 +1638,7 @@
typename hashtable::hash_code_t code = this->m_hash_code(k);
std::size_t n = this->bucket_index(k, code, this->bucket_count());
node** head = m_buckets + n;
- node* p = find_node(*head, k, code);
+ node* p = m_find_node(*head, k, code);
if (p)
{
@@ -1644,8 +1665,8 @@
bool c, bool ci, bool u>
typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*
hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
- find_node(node* p, const key_type& k,
- typename hashtable::hash_code_t code) const
+ m_find_node(node* p, const key_type& k,
+ typename hashtable::hash_code_t code) const
{
for (; p; p = p->m_next)
if (this->compare(k, code, p))
@@ -1653,34 +1674,28 @@
return false;
}
- // Insert v if no element with its key is already present.
+ // Insert v in bucket n (assumes no element with its key already present).
template<typename K, typename V,
typename A, typename Ex, typename Eq,
typename H1, typename H2, typename H, typename RP,
bool c, bool ci, bool u>
- std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
- H2, H, RP, c, ci, u>::iterator, bool>
+ typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
- insert(const value_type& v, std::tr1::true_type)
+ m_insert_bucket(const value_type& v, size_type n,
+ typename hashtable::hash_code_t code)
{
- const key_type& k = this->m_extract(v);
- typename hashtable::hash_code_t code = this->m_hash_code(k);
- std::size_t n = this->bucket_index(k, code, m_bucket_count);
-
- if (node* p = find_node(m_buckets[n], k, code))
- return std::make_pair(iterator(p, m_buckets + n), false);
-
std::pair<bool, std::size_t> do_rehash
= m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
// Allocate the new node before doing the rehash so that we don't
// do a rehash if the allocation throws.
node* new_node = m_allocate_node(v);
-
+
try
{
if (do_rehash.first)
{
+ const key_type& k = this->m_extract(v);
n = this->bucket_index(k, code, do_rehash.second);
m_rehash(do_rehash.second);
}
@@ -1689,7 +1704,7 @@
this->store_code(new_node, code);
m_buckets[n] = new_node;
++m_element_count;
- return std::make_pair(iterator(new_node, m_buckets + n), true);
+ return iterator(new_node, m_buckets + n);
}
catch(...)
{
@@ -1697,6 +1712,25 @@
__throw_exception_again;
}
}
+
+ // Insert v if no element with its key is already present.
+ template<typename K, typename V,
+ typename A, typename Ex, typename Eq,
+ typename H1, typename H2, typename H, typename RP,
+ bool c, bool ci, bool u>
+ std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
+ H2, H, RP, c, ci, u>::iterator, bool>
+ hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
+ m_insert(const value_type& v, std::tr1::true_type)
+ {
+ const key_type& k = this->m_extract(v);
+ typename hashtable::hash_code_t code = this->m_hash_code(k);
+ size_type n = this->bucket_index(k, code, m_bucket_count);
+
+ if (node* p = m_find_node(m_buckets[n], k, code))
+ return std::make_pair(iterator(p, m_buckets + n), false);
+ return std::make_pair(m_insert_bucket(v, n, code), true);
+ }
// Insert v unconditionally.
template<typename K, typename V,
@@ -1705,19 +1739,19 @@
bool c, bool ci, bool u>
typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
- insert(const value_type& v, std::tr1::false_type)
+ m_insert(const value_type& v, std::tr1::false_type)
{
std::pair<bool, std::size_t> do_rehash
= m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
if (do_rehash.first)
m_rehash(do_rehash.second);
-
+
const key_type& k = this->m_extract(v);
typename hashtable::hash_code_t code = this->m_hash_code(k);
- std::size_t n = this->bucket_index(k, code, m_bucket_count);
-
+ size_type n = this->bucket_index(k, code, m_bucket_count);
+
node* new_node = m_allocate_node(v);
- node* prev = find_node(m_buckets[n], k, code);
+ node* prev = m_find_node(m_buckets[n], k, code);
if (prev)
{
new_node->m_next = prev->m_next;
@@ -1741,7 +1775,7 @@
bool c, bool ci, bool u>
void
hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
- erase_node(node* p, node** b)
+ m_erase_node(node* p, node** b)
{
node* cur = *b;
if (cur == p)
@@ -1786,25 +1820,25 @@
bool c, bool ci, bool u>
typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
- erase(iterator i)
+ erase(iterator it)
{
- iterator result = i;
+ iterator result = it;
++result;
- erase_node(i.m_cur_node, i.m_cur_bucket);
+ m_erase_node(it.m_cur_node, it.m_cur_bucket);
return result;
}
-
+
template<typename K, typename V,
typename A, typename Ex, typename Eq,
typename H1, typename H2, typename H, typename RP,
bool c, bool ci, bool u>
typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
- erase(const_iterator i)
+ erase(const_iterator it)
{
- const_iterator result = i;
+ const_iterator result = it;
++result;
- erase_node(i.m_cur_node, i.m_cur_bucket);
+ m_erase_node(it.m_cur_node, it.m_cur_bucket);
return result;
}
Index: testsuite/performance/23_containers/insert/unordered_map_array.cc
===================================================================
--- testsuite/performance/23_containers/insert/unordered_map_array.cc (revision 0)
+++ testsuite/performance/23_containers/insert/unordered_map_array.cc (revision 0)
@@ -0,0 +1,61 @@
+// Copyright (C) 2006 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING. If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction. Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License. This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <tr1/unordered_map>
+#include <testsuite_performance.h>
+
+typedef std::tr1::unordered_map<int, int> map_type;
+typedef std::tr1::unordered_map<int, map_type> matrix_type;
+
+int main()
+{
+ using namespace __gnu_test;
+
+ time_counter time;
+ resource_counter resource;
+
+ const int sz = 1000;
+
+ matrix_type matrix;
+
+ start_counters(time, resource);
+ for (int iter = 0; iter < 50; ++iter)
+ {
+ for (int i = 0; i < sz; ++i)
+ {
+ for (int j = 0; j < sz; ++j)
+ {
+ map_type& row = matrix[i / 4];
+ ++row[j / 4];
+ }
+ }
+ }
+ stop_counters(time, resource);
+ report_performance(__FILE__, "", time, resource);
+
+ return 0;
+}