Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r80378 - trunk/boost/unordered/detail
From: dnljms_at_[hidden]
Date: 2012-09-03 16:01:51


Author: danieljames
Date: 2012-09-03 16:01:50 EDT (Mon, 03 Sep 2012)
New Revision: 80378
URL: http://svn.boost.org/trac/boost/changeset/80378

Log:
Unordered: Avoid unnecessary swapping in rehash and move.
Text files modified:
   trunk/boost/unordered/detail/buckets.hpp | 41 ++++++++++++++++++++++++++++++---------
   trunk/boost/unordered/detail/equivalent.hpp | 24 ++++------------------
   trunk/boost/unordered/detail/table.hpp | 7 ++---
   trunk/boost/unordered/detail/unique.hpp | 24 ++++------------------
   4 files changed, 44 insertions(+), 52 deletions(-)

Modified: trunk/boost/unordered/detail/buckets.hpp
==============================================================================
--- trunk/boost/unordered/detail/buckets.hpp (original)
+++ trunk/boost/unordered/detail/buckets.hpp 2012-09-03 16:01:50 EDT (Mon, 03 Sep 2012)
@@ -684,38 +684,59 @@
         }
 
         buckets(buckets& b, boost::unordered::detail::move_tag m) :
- buckets_(),
+ buckets_(b.buckets_),
             bucket_count_(b.bucket_count_),
- size_(),
+ size_(b.size_),
             allocators_(b.allocators_, m)
         {
- swap(b);
+ b.buckets_ = bucket_pointer();
+ b.size_ = 0;
         }
 
         template <typename Types>
         buckets(boost::unordered::detail::table<Types>& x,
                 boost::unordered::detail::move_tag m) :
- buckets_(),
+ buckets_(x.buckets_),
             bucket_count_(x.bucket_count_),
- size_(),
+ size_(x.size_),
             allocators_(x.allocators_, m)
         {
- swap(x);
+ x.buckets_ = bucket_pointer();
+ x.size_ = 0;
         }
 
         ////////////////////////////////////////////////////////////////////////
         // Create buckets
         // (never called in constructor to avoid exception issues)
 
- void create_buckets()
+ void create_buckets(std::size_t new_count)
         {
             boost::unordered::detail::array_constructor<bucket_allocator>
                 constructor(bucket_alloc());
     
             // Creates an extra bucket to act as the start node.
- constructor.construct(bucket(), this->bucket_count_ + 1);
+ constructor.construct(bucket(), new_count + 1);
     
- if (bucket::extra_node)
+ if (buckets_)
+ {
+ // Copy the nodes to the new buckets, including the dummy
+ // node if there is one.
+ (constructor.get() +
+ static_cast<std::ptrdiff_t>(new_count))->next_ =
+ (buckets_ + static_cast<std::ptrdiff_t>(
+ bucket_count_))->next_;
+
+ bucket_pointer end = this->get_bucket(this->bucket_count_ + 1);
+ for(bucket_pointer it = this->buckets_; it != end; ++it)
+ {
+ bucket_allocator_traits::destroy(bucket_alloc(),
+ boost::addressof(*it));
+ }
+
+ bucket_allocator_traits::deallocate(bucket_alloc(),
+ this->buckets_, this->bucket_count_ + 1);
+ }
+ else if (bucket::extra_node)
             {
                 node_constructor a(this->node_alloc());
                 a.construct_node();
@@ -725,6 +746,7 @@
                         a.release();
             }
 
+ this->bucket_count_ = new_count;
             this->buckets_ = constructor.release();
         }
 
@@ -755,7 +777,6 @@
             this->bucket_count_ = other.bucket_count_;
             this->size_ = other.size_;
             other.buckets_ = bucket_pointer();
- other.bucket_count_ = 0;
             other.size_ = 0;
         }
 

Modified: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- trunk/boost/unordered/detail/equivalent.hpp (original)
+++ trunk/boost/unordered/detail/equivalent.hpp 2012-09-03 16:01:50 EDT (Mon, 03 Sep 2012)
@@ -719,7 +719,7 @@
         {
             BOOST_ASSERT(!dst.buckets_);
 
- dst.create_buckets();
+ dst.create_buckets(dst.bucket_count_);
 
             node_constructor a(dst.node_alloc());
 
@@ -766,7 +766,7 @@
         {
             BOOST_ASSERT(!dst.buckets_);
 
- dst.create_buckets();
+ dst.create_buckets(dst.bucket_count_);
 
             node_constructor a(dst.node_alloc());
 
@@ -808,26 +808,12 @@
         {
             BOOST_ASSERT(this->size_);
 
- buckets dst(this->node_alloc(), num_buckets);
- dst.create_buckets();
-
- previous_pointer src_start = this->get_previous_start();
- previous_pointer dst_start = dst.get_previous_start();
-
- dst_start->next_ = src_start->next_;
- src_start->next_ = link_pointer();
- dst.size_ = this->size_;
- this->size_ = 0;
-
- previous_pointer prev = dst_start;
+ this->create_buckets(num_buckets);
+ previous_pointer prev = this->get_previous_start();
             while (prev->next_)
- prev = place_in_bucket(dst, prev,
+ prev = place_in_bucket(*this, prev,
                     static_cast<node_pointer>(
                         static_cast<node_pointer>(prev->next_)->group_prev_));
-
- // Swap the new nodes back into the container and setup the
- // variables.
- dst.swap(*this); // no throw
         }
 
         // Iterate through the nodes placing them in the correct buckets.

Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp (original)
+++ trunk/boost/unordered/detail/table.hpp 2012-09-03 16:01:50 EDT (Mon, 03 Sep 2012)
@@ -196,7 +196,7 @@
             max_load_(x.max_load_)
         {
             if(a == x.node_alloc()) {
- this->buckets::swap(x, false_type());
+ this->move_buckets_from(x);
             }
             else if(x.size_) {
                 // Use a temporary table because move_buckets_to leaves the
@@ -403,9 +403,8 @@
     inline void table<Types>::reserve_for_insert(std::size_t size)
     {
         if (!this->buckets_) {
- this->bucket_count_ = (std::max)(this->bucket_count_,
- this->min_buckets_for_size(size));
- this->create_buckets();
+ this->create_buckets((std::max)(this->bucket_count_,
+ this->min_buckets_for_size(size)));
             this->max_load_ = this->calculate_max_load();
         }
         // According to the standard this should be 'size >= max_load_',

Modified: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp (original)
+++ trunk/boost/unordered/detail/unique.hpp 2012-09-03 16:01:50 EDT (Mon, 03 Sep 2012)
@@ -626,7 +626,7 @@
         {
             BOOST_ASSERT(!dst.buckets_);
 
- dst.create_buckets();
+ dst.create_buckets(dst.bucket_count_);
 
             node_constructor a(dst.node_alloc());
 
@@ -657,7 +657,7 @@
         {
             BOOST_ASSERT(!dst.buckets_);
 
- dst.create_buckets();
+ dst.create_buckets(dst.bucket_count_);
 
             node_constructor a(dst.node_alloc());
 
@@ -683,24 +683,10 @@
         {
             BOOST_ASSERT(this->size_);
 
- buckets dst(this->node_alloc(), num_buckets);
- dst.create_buckets();
-
- previous_pointer src_start = this->get_previous_start();
- previous_pointer dst_start = dst.get_previous_start();
-
- dst_start->next_ = src_start->next_;
- src_start->next_ = link_pointer();
- dst.size_ = this->size_;
- this->size_ = 0;
-
- previous_pointer prev = dst.get_previous_start();
+ this->create_buckets(num_buckets);
+ previous_pointer prev = this->get_previous_start();
             while (prev->next_)
- prev = place_in_bucket(dst, prev);
-
- // Swap the new nodes back into the container and setup the
- // variables.
- dst.swap(*this); // no throw
+ prev = place_in_bucket(*this, prev);
         }
 
         // Iterate through the nodes placing them in the correct buckets.


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk