[Boost-commit] svn:boost r78412 - in sandbox/pool: boost/pool libs/pool/test

Subject: [Boost-commit] svn:boost r78412 - in sandbox/pool: boost/pool libs/pool/test
From: svart.riddare_at_[hidden]
Date: 2012-05-10 17:10:55

Author: edupuis
Date: 2012-05-10 17:10:54 EDT (Thu, 10 May 2012)
New Revision: 78412
URL: http://svn.boost.org/trac/boost/changeset/78412

Log:
Added a pool.order() function, which transforms an unordered pool into an ordered one. Call this function in object_pool::~object_pool() if suitable, which allows to use pool.malloc() and pool.free() instead of pool.ordered_malloc() and pool.ordered_free(). 

This changes the complexity of object_pool.destroy(), going from O(n) to O(1), while the complexity of the destructor goes from O(n) to O(n log n) if the pool user has not released all pool objects, otherwise the destructor is O(1).

This fixes #3789 and makes it possible to have pools holding millions of objects.
Added:
   sandbox/pool/libs/pool/test/test_bug_3789.cpp   (contents, props changed)
Text files modified: 
   sandbox/pool/boost/pool/object_pool.hpp               |    23 ++++++++++-                             
   sandbox/pool/boost/pool/pool.hpp                      |    80 ++++++++++++++++++++++++++++++++++++++- 
   sandbox/pool/boost/pool/simple_segregated_storage.hpp |    70 +++++++++++++++++++++++++++++++++++     
   3 files changed, 168 insertions(+), 5 deletions(-)

Modified: sandbox/pool/boost/pool/object_pool.hpp
==============================================================================
--- sandbox/pool/boost/pool/object_pool.hpp	(original)
+++ sandbox/pool/boost/pool/object_pool.hpp	2012-05-10 17:10:54 EDT (Thu, 10 May 2012)
@@ -69,6 +69,9 @@
     typedef typename Pool::size_type size_type; //!<   pool<UserAllocator>::size_type
     typedef typename Pool::difference_type difference_type; //!< pool<UserAllocator>::difference_type
 
+  private:
+    size_type allocated;
+
   protected:
     //! \return The underlying boost:: \ref pool storage used by *this.
     Pool & store()
@@ -93,6 +96,7 @@
     Pool(sizeof(T), arg_requested_objects)
     { //! Constructs a new (empty by default) ObjectPoolBase.
       //! \param arg_requested_objects Number of memory chunks to allocate at initialization.
+      allocated = 0;
     }
 
     ~object_pool_base();
@@ -104,16 +108,24 @@
       //! If out of memory, returns 0. 
       //!
       //! Amortized O(1).
-      return static_cast<element_type *>(store().ordered_malloc());
+      element_type *element = static_cast<element_type *>(store().malloc());
+      if (element)
+        allocated += 1;
+
+      return element;
     }
+
     void free BOOST_PREVENT_MACRO_SUBSTITUTION(element_type * const chunk)
     { //! De-Allocates memory that holds a chunk of type ElementType.
       //!
       //!  Note that p may not be 0.\n
       //!
       //! Note that the destructor for p is not called. O(N).
-      store().ordered_free(chunk);
+      store().free(chunk);
+      if (chunk)
+        allocated -= 1;
     }
+
     bool is_from(element_type * const chunk) const
     { /*! \returns true  if chunk was allocated from *this or
       may be returned as the result of a future allocation from *this.
@@ -205,6 +217,13 @@
   if (!this->list.valid())
     return;
 
+  // do not do useless work
+  if (!allocated)
+    return;
+
+  // sort store
+  store().order();
+
   details::PODptr<size_type> iter = this->list;
   details::PODptr<size_type> next = iter;
 

Modified: sandbox/pool/boost/pool/pool.hpp
==============================================================================
--- sandbox/pool/boost/pool/pool.hpp	(original)
+++ sandbox/pool/boost/pool/pool.hpp	2012-05-10 17:10:54 EDT (Thu, 10 May 2012)
@@ -234,6 +234,63 @@
       next_ptr() = arg.begin();
       next_size() = arg.total_size();
     }
+
+    static PODptr sort(PODptr list)
+    {
+      if (!list.valid() || !list.next().valid())
+        return list;
+
+      PODptr listA, listB;
+      split(list, &listA, &listB);
+
+      return merge(sort(listA), sort(listB));
+    }
+
+    static PODptr merge(PODptr listA, PODptr listB)
+    {
+      if (!listA.valid()) return listB;
+      if (!listB.valid()) return listA;
+
+      if (std::less<char *>()(listB.ptr, listA.ptr))
+        std::swap(listA, listB);
+
+      PODptr list = listA; listA = listA.next();
+      PODptr last = list;
+
+      while (listA.valid())
+      {
+        if (std::less<char *>()(listB.ptr, listA.ptr))
+          std::swap(listA, listB);
+
+        last.next(listA);
+        last = last.next();
+        listA = listA.next();
+      }
+
+      last.next(listB);
+      return list;
+    }
+  
+    static void split(PODptr list, PODptr *listA, PODptr *listB)
+    {
+      PODptr half = list;
+      PODptr full = list.next();
+
+      while (full.valid())
+      {
+        full = full.next();
+        if (full.valid())
+        {
+          half = half.next();
+          full = full.next();
+        }
+      }
+
+      *listA = list;
+      *listB = half.next();
+
+      half.next(PODptr());
+    }
 }; // class PODptr
 } // namespace details
 
@@ -308,6 +365,7 @@
     size_type next_size;
     size_type start_size;
     size_type max_size;
+    bool ordered;
 
     //! finds which POD in the list 'chunk' was allocated from.
     details::PODptr<size_type> find_POD(void * const chunk) const;
@@ -383,7 +441,8 @@
       //!   the first time that object needs to allocate system memory.
       //!   The default is 32. This parameter may not be 0.
       //! \param nmax_size is the maximum number of chunks to allocate in one block.			
-      set_max_size(nmax_size);			
+      set_max_size(nmax_size);	
+      ordered = true;
     }
 
     ~pool()
@@ -449,6 +508,7 @@
       //! \returns a free chunk from that block.
       //! If a new memory block cannot be allocated, returns 0. Amortized O(1).
       // Look for a non-empty storage
+      ordered = false;
       if (!store().empty())
         return (store().malloc)();
       return malloc_need_resize();
@@ -480,6 +540,7 @@
       //! Assumes that chunk actually refers to a block of chunks
       //! spanning n * partition_sz bytes.
       //! deallocates each chunk in that block.
+      ordered = false;
       if (chunk)
         (store().free)(chunk);
     }
@@ -540,6 +601,17 @@
       //! Note that this function may not be used to reliably test random pointer values.
       return (find_POD(chunk).valid());
     }
+
+    void order()
+    { //! Orders a pool
+      //! O(1) if the pool is already ordered, O(n log n) otherwise.
+      if (!ordered)
+      {
+        list = details::PODptr<size_type>::sort(list);
+        store().order();
+        ordered = true;
+      }
+    }
 };
 
 #ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION
@@ -557,6 +629,7 @@
   // ret is the return value: it will be set to true when we actually call
   //  UserAllocator::free(..)
   bool ret = false;
+  order();
 
   // This is a current & previous iterator pair over the memory block list
   details::PODptr<size_type> ptr = list;
@@ -672,7 +745,7 @@
 
   set_next_size(start_size);
   return ret;
-}
+}	
 
 template <typename UserAllocator>
 bool pool<UserAllocator>::purge_memory()
@@ -702,7 +775,8 @@
 
   list.invalidate();
   this->first = 0;
-  
+  ordered = true;
+
   set_next_size(start_size);
   return true;
 }

Modified: sandbox/pool/boost/pool/simple_segregated_storage.hpp
==============================================================================
--- sandbox/pool/boost/pool/simple_segregated_storage.hpp	(original)
+++ sandbox/pool/boost/pool/simple_segregated_storage.hpp	2012-05-10 17:10:54 EDT (Thu, 10 May 2012)
@@ -71,6 +71,10 @@
     static void * try_malloc_n(void * & start, size_type n,
         size_type partition_size);
 
+    static void *sort(void *list);
+    static void *merge(void *listA, void *listB);
+    static void split(void *list, void **listA, void **listB);
+
   protected:
     void * first; /*!< This data member is the free list.
       It points to the first chunk in the free list,
@@ -219,6 +223,12 @@
         add_ordered_block(chunks, n * partition_size, partition_size);
        BOOST_POOL_VALIDATE_INTERNALS
     }
+
+    void order()
+    { //! Orders the storageby sorting the list of free chunks
+      first = sort(first);
+    }
+
 #ifdef BOOST_POOL_VALIDATE
     void validate()
     {
@@ -368,6 +378,66 @@
   return ret;
 }
 
+//! Performs a recursive merge sort on given list
+template <typename SizeType>
+void *simple_segregated_storage<SizeType>::sort(void *list)
+{
+  if (!list || !nextof(list))
+    return list;
+
+  void *listA, *listB;
+  split(list, &listA, &listB);
+
+  return merge(sort(listA), sort(listB));
+}
+
+//! Merges two list in ascending order of memory addresses
+template <typename SizeType>
+void *simple_segregated_storage<SizeType>::merge(void *listA, void *listB)
+{
+  void *list = 0;
+  void **last = &list;
+
+  if (!listB)
+    return listA;
+
+  while (listA)
+  {
+    if (std::less<void *>()(listB, listA))
+      std::swap(listA, listB);
+
+    *last = listA;
+    last = &nextof(*last);
+    listA = nextof(listA);		
+  }
+
+  *last = listB;
+  return list;
+}
+
+//! Splits a list into two halves
+template <typename SizeType>
+void simple_segregated_storage<SizeType>::split(void *list, void **listA, void **listB)
+{
+  void *half = list;
+  void *full = nextof(list);
+
+  while (full)
+  {
+    full = nextof(full);
+    if (full)
+    {
+      half = nextof(half);
+      full = nextof(full);
+    }
+  }
+
+  *listA = list;
+  *listB = nextof(half);
+
+  nextof(half) = NULL;
+}
+
 } // namespace boost
 
 #ifdef BOOST_MSVC

Added: sandbox/pool/libs/pool/test/test_bug_3789.cpp
==============================================================================
--- (empty file)
+++ sandbox/pool/libs/pool/test/test_bug_3789.cpp	2012-05-10 17:10:54 EDT (Thu, 10 May 2012)
@@ -0,0 +1,48 @@
+/* Copyright (C) 2012 Étienne Dupuis
+* 
+* Use, modification and distribution is subject to the 
+* Boost Software License, Version 1.0. (See accompanying
+* file LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+*/
+
+// Test of ticket #3789 (https://svn.boost.org/trac/boost/ticket/3789)
+
+#include <boost/pool/object_pool.hpp>
+
+class object
+{
+  public :
+    static int instances;
+
+    char padding[31];
+    bool initialized;
+
+  public :
+    object() { initialized = true; instances += 1; }
+    ~object() { assert(initialized); initialized = false; instances -= 1; assert(instances >= 0); }
+};
+
+int object::instances;
+
+int main()
+{
+  object::instances = 0;
+  {
+    static const int size = 1000000;
+    boost::object_pool<object> pool(1);		
+  
+    object **objects = new object *[size];
+
+    for (int k = 0; k < size; k++)
+      objects[k] = pool.construct();
+
+    for (int k = 0; k < size; k += (k % 10) ? 1 : 2)
+      pool.destroy(objects[k]);
+
+    assert(object::instances == size / 10);
+    delete[] objects;
+  }
+
+  assert(object::instances == 0);
+  return object::instances;
+}