Text archives Help

---

Author: boulos
Date: Fri Jul 20 17:39:58 2007
New Revision: 1523

Added:
   trunk/Core/Util/MemoryPool.h
Modified:
   trunk/Core/CMakeLists.txt
   trunk/Core/Util/ApproximatePriorityQueue.h
   trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc
   trunk/Engine/ImageTraversers/DeadlineImageTraverser.h
Log:
Core/CMakeLists.txt
Core/Util/MemoryPool.h

  Adding a simple memory pool class that simply allocates blocks of
  data and keeps a list of them.  There's a lot left to do here, but
  an initial implementation with free lists was too expensive to
  maintain (the clear() method is then linear in the capacity of each
  block to rebuild the free list)

Core/Util/ApproximatePriorityQueue.h
  
  Seeding the random number generators to hopefully reduce contention.

Engine/ImageTraversers/DeadlineImageTraverser.cc
Engine/ImageTraversers/DeadlineImageTraverser.h

  Using the new MemoryPool interface instead of new and delete to
  avoid requiring a preallocated set of Tiles and to cleanup dangling
  pointers.


Modified: trunk/Core/CMakeLists.txt
==============================================================================
--- trunk/Core/CMakeLists.txt   (original)
+++ trunk/Core/CMakeLists.txt   Fri Jul 20 17:39:58 2007
@@ -68,6 +68,7 @@
      Util/Endian.h
      Util/LargeFile.h
      Util/LargeFile.cc
+     Util/MemoryPool.h
      Util/PriorityQueue.h
      Util/Stat.h
      Util/ThreadStorage.h

Modified: trunk/Core/Util/ApproximatePriorityQueue.h
==============================================================================
--- trunk/Core/Util/ApproximatePriorityQueue.h  (original)
+++ trunk/Core/Util/ApproximatePriorityQueue.h  Fri Jul 20 17:39:58 2007
@@ -29,6 +29,9 @@
     ApproximatePriorityQueue(size_t num_queues, size_t max_threads = 64) :
       num_queues(num_queues), max_threads(max_threads) {
       rngs = new CheapRNG[max_threads];
+      for (size_t i = 0; i < max_threads; i++) {
+        rngs[i].seed(i * 12345 + 62284);
+      }
       queues = new QueueType[num_queues];
       for (size_t i = 0; i < num_queues; i++) {
         // TODO(boulos): Number them using ostringstream? Seems pretty

Added: trunk/Core/Util/MemoryPool.h
==============================================================================
--- (empty file)
+++ trunk/Core/Util/MemoryPool.h        Fri Jul 20 17:39:58 2007
@@ -0,0 +1,91 @@
+#ifndef MANTA_CORE_UTIL_MEMORY_POOL_H_
+#define MANTA_CORE_UTIL_MEMORY_POOL_H_
+
+#include <list>
+#include <vector>
+
+namespace Manta {
+
+  // A MemoryPool for a single StorageType.  TODO(boulos): Extend this
+  // class to be a more generic MemoryPool that allows arbitrary
+  // requests, uses a set of free lists instead of one, etc.
+
+  template<class StorageType>
+  class MemoryPool {
+  private:
+    // A Block is a chunk of memory along with its own capacity and
+    // size (because lists don't have a constant time size operation).
+    // TODO(boulos): add free list?
+    struct Block {
+      StorageType* data;
+      size_t capacity;
+      size_t size;
+    };
+  public:
+    MemoryPool(size_t new_size = 8) : capacity(0), size(0) {
+      reserve(new_size);
+    }
+
+    void clear() {
+      // Consider coalescing all the blocks?
+      for (size_t i = 0; i < blocks.size(); i++) {
+        blocks[i].size = 0;
+      }
+    }
+
+    void reserve(size_t new_size) {
+      if (new_size < capacity)
+        return;
+      size_t new_block_size = new_size - capacity;
+
+      Block new_block;
+      new_block.size = 0;
+      new_block.capacity = new_block_size;
+      new_block.data = new StorageType[new_block_size];
+      blocks.push_back(new_block);
+
+      capacity = new_size;
+    }
+
+    StorageType* getItem() {
+      // If we're out of space, ask for more
+      if (size == capacity) {
+        reserve(2 * size);
+      }
+
+      for (size_t i = 0; i < blocks.size(); i++) {
+        // NOTE(boulos): The SGI docs imply that .empty() is constant
+        // time while .size() is linear (which is reasonable)
+        Block& block = blocks[i];
+        if (block.size == block.capacity) {
+          continue;
+        }
+
+        StorageType* result = &(block.data[block.size]);
+        if (result == 0) {
+          throw SCIRun::InternalError("Apparently we're holding a NULL 
pointer in our free list.", __FILE__, __LINE__);
+        }
+        block.size++;
+        size++;
+        return result;
+      }
+
+      // NOTE(boulos): This shouldn't happen, but not having it will
+      // generate compiler warnings.
+      throw SCIRun::InternalError("Unable to allocate a new item",
+                                  __FILE__, __LINE__);
+      return 0;
+    }
+
+    // TODO(boulos): Add the ability to return memory one-by-one.
+  private:
+    std::vector<Block> blocks;
+    // Maintain an aggregate capacity and size so we don't need to
+    // search when we need to allocate a new block.  TODO(boulos): Add
+    // a first free block list to avoid searching through full blocks.
+    size_t capacity;
+    size_t size;
+  };
+};
+
+#endif // MANTA_CORE_UTIL_MEMORY_POOL_H_

Modified: trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc
==============================================================================
--- trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc      (original)
+++ trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc      Fri Jul 20 
17:39:58 2007
@@ -131,8 +131,7 @@
   }
 }
 
-DeadlineImageTraverser::~DeadlineImageTraverser()
-{
+DeadlineImageTraverser::~DeadlineImageTraverser() {
 }
 
 void DeadlineImageTraverser::setupBegin(SetupContext& context, int 
numChannels)
@@ -144,7 +143,11 @@
   context.loadBalancer->setupBegin(context, numChannels);
   context.pixelSampler->setupBegin(context, numChannels);
 
-  queue.clear();
+  if (context.proc == 0)
+    queue.clear();
+
+  ASSERT(context.proc < DeadlineImageTraverser::kMaxThreads);
+  tile_pools[context.proc].clear();
 
   context.rtrt_int->addIdleMode(this);
 }
@@ -153,10 +156,9 @@
                                             bool changed,
                                             bool firstFrame,
                                             bool& pipelineNeedsSetup) {
-  if (firstFrame)
-    reset_every_frame = true;
-
   if (context.proc == 0) {
+    if (firstFrame)
+      reset_every_frame = true;
     // NOTE(boulos): Someone probably moved the camera or
     // something... Time to restart.  The setupFrame call for the next
     // frame will clean up the other data (queue and next_tile)
@@ -213,15 +215,20 @@
   //if (context.proc == 0)
   //  cerr << __func__ << endl;
   // TODO(boulos): What other stuff shouldn't get reset?
-  if (reset_every_frame) {
+  if (reset_every_frame && context.proc == 0) {
     //if (context.proc == 0) cerr << "We are resetting every frame"<< endl;
     finished_coarse = false;
   }
   if (!finished_coarse) {
     context.loadBalancer->setupFrame(context);
-    queue.clear();
-    converged = false;
-    StartFrameTime = CPUTime::currentSeconds();
+    if (context.proc == 0) {
+      queue.clear();
+      converged = false;
+      StartFrameTime = CPUTime::currentSeconds();
+    }
+
+    ASSERT(context.proc < DeadlineImageTraverser::kMaxThreads);
+    tile_pools[context.proc].clear();
   }
 
   context.pixelSampler->setupFrame(context);
@@ -239,7 +246,6 @@
       double total_time = EndTime - StartFrameTime;
       cerr << "Took " << total_time << " seconds to refine to 
"<<Fragment::MaxSize<<" spp" << endl;
     }
-    //cerr << "queue size = " << queue.size() << ", next_tile = " << 
next_tile << endl;
   }
 }
 
@@ -315,7 +321,11 @@
         frag.setSize(idx);
         if((xcoarsepixelsize | ycoarsepixelsize) > 1){
           singleSampler->renderFragment(context, frag);
-          Tile* tile = new Tile;
+
+          //Tile* tile = new Tile;
+          ASSERT(context.proc < DeadlineImageTraverser::kMaxThreads);
+          Tile* tile = tile_pools[context.proc].getItem();
+
           tile->xstart = xstart;
           tile->ystart = ystart;
           tile->xend = xend;
@@ -429,7 +439,10 @@
             }
           }
 
-          Tile* childtile = new Tile;
+
+          //Tile* childtile = new Tile;
+          ASSERT(context.proc < DeadlineImageTraverser::kMaxThreads);
+          Tile* childtile = tile_pools[context.proc].getItem();
           childtile->xstart = x;
           childtile->xend = xend;
           childtile->ystart = y;
@@ -474,7 +487,9 @@
           // NOTE(boulos): We know that we don't just stop anymore due
           // to super sampling
           singleSampler->renderFragment(context, frag);
-          Tile* childtile = new Tile;
+          //Tile* childtile = new Tile;
+          ASSERT(context.proc < DeadlineImageTraverser::kMaxThreads);
+          Tile* childtile = tile_pools[context.proc].getItem();
           childtile->xstart = x;
           childtile->xend = xend;
           childtile->ystart = y;
@@ -489,13 +504,6 @@
       }
     }
 
-    // Return the memory.  TODO(boulos): Use a memory pool
-    // implementation, so that each frame we can say that "I know I'm
-    // done with any pointers I asked for even if I don't ask to
-    // delete them." (because currently the priority queue might be
-    // the only class that is holding some pointers that need to be
-    // cleaned up)
-    delete tile;
     // Check size before inserting to avoid lock contention
     if(childtiles.size())
       insertIntoQueue(childtiles, static_cast<size_t>(context.proc));

Modified: trunk/Engine/ImageTraversers/DeadlineImageTraverser.h
==============================================================================
--- trunk/Engine/ImageTraversers/DeadlineImageTraverser.h       (original)
+++ trunk/Engine/ImageTraversers/DeadlineImageTraverser.h       Fri Jul 20 
17:39:58 2007
@@ -35,7 +35,7 @@
 #include <Interface/Fragment.h>
 #include <Core/Thread/Mutex.h>
 #include <Core/Util/ApproximatePriorityQueue.h>
-#include <Core/Util/PriorityQueue.h>
+#include <Core/Util/MemoryPool.h>
 
 #include <sgi_stl_warnings_off.h>
 #include <string>
@@ -94,6 +94,8 @@
     };
     SCIRun::Mutex qlock;
     ApproximatePriorityQueue<Tile*, float> queue;
+    static const int kMaxThreads = 32;
+    MemoryPool<Tile> tile_pools[kMaxThreads];
     bool reset_every_frame;
     bool finished_coarse;
     bool ShowTimeSupersample;

---

• [MANTA] r1523 - in trunk: Core Core/Util Engine/ImageTraversers, boulos, 07/20/2007

---

Archive powered by MHonArc 2.6.16.