Text archives Help

---

Author: boulos
Date: Thu Jul 19 15:36:23 2007
New Revision: 1514

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

 Adding a max heap PriorityQueue implementation.  Unlike the STL
 priority queue, it returns by value (so don't put big objects into
 it) which allows for easier pop() usage.  It also has nice features
 like reserve and clear.

Engine/ImageTraversers/DeadlineImageTraverser.cc
Engine/ImageTraversers/DeadlineImageTraverser.h
 
 Updating the DeadlineImageTraverser to use the new PriorityQueue.  It
 is no longer necessary to pre-allocate the queue as it will simply
 grow and realloc itself (which doesn't seem to have a perf hit).


Modified: trunk/Core/CMakeLists.txt
==============================================================================
--- trunk/Core/CMakeLists.txt   (original)
+++ trunk/Core/CMakeLists.txt   Thu Jul 19 15:36:23 2007
@@ -67,6 +67,7 @@
      Util/Endian.h
      Util/LargeFile.h
      Util/LargeFile.cc
+     Util/PriorityQueue.h
      Util/Stat.h
      Util/ThreadStorage.h
      Util/ThreadStorage.cc

Added: trunk/Core/Util/PriorityQueue.h
==============================================================================
--- (empty file)
+++ trunk/Core/Util/PriorityQueue.h     Thu Jul 19 15:36:23 2007
@@ -0,0 +1,135 @@
+#ifndef MANTA_CORE_UTIL_PRIORITY_QUEUE_H_
+#define MANTA_CORE_UTIL_PRIORITY_QUEUE_H_
+
+#include <Core/Util/Assert.h>
+
+namespace Manta {
+
+  // This class is a simple max heap that allows for push, pop,
+  // reserve, empty, size, and top (similar to the STL
+  // priority_queue). This class _differs_ from the STL implementation
+  // in that it returns by value instead of by reference. The STL
+  // avoids this due to the perceived efficiency hit of return by
+  // value (a copy constructor call); however, if your DataType is an
+  // integral type this is not an issue. Return by value also avoids
+  // any dangling pointer issues.
+  //
+  // This class is also not templated on a priority/comparison
+  // function. Users of this class are instead required to provide the
+  // priority upon insertion. Currently, it is not possible to see the
+  // priority of an item. TODO(boulos): Change this?
+  //
+  // In addition, this class allows for a simple clear method that
+  // simply causes the queue to appear empty. This makes it useful for
+  // avoiding reallocation of memory each frame.
+  template<class DataType, class PriorityType>
+  class PriorityQueue {
+  public:
+    struct PriorityQueueEntry {
+      DataType data;
+      PriorityType priority;
+    };
+
+    PriorityQueue(size_t default_size = 8) : qsize(0), 
capacity(default_size) {
+      queue_data = new PriorityQueueEntry[default_size];
+    }
+
+    ~PriorityQueue() {
+      delete[] queue_data;
+    }
+
+    bool empty() const {
+      return qsize == 0;
+    }
+    size_t size() const {
+      return qsize;
+    }
+
+    void reserve(size_t new_size) {
+      if (new_size > capacity) {
+        reallocate(new_size);
+      }
+    }
+
+    void clear() {
+      qsize = 0;
+    }
+
+    DataType top() const {
+      ASSERT(empty() == false);
+      return queue_data[0].data;
+    }
+
+    DataType pop() {
+      DataType result = queue_data[0].data;
+
+      // NOTE(boulos): This part looks for a new root node. So the part
+      // where you replace queue[p] with queue[c] is actually okay (since
+      // we're removing the root node).
+      size_t p = 0;
+      while((p<<1)+2 < qsize){
+        size_t c1 = (p<<1)+1;
+        size_t c2 = (p<<1)+2;
+        size_t c;
+        if(queue_data[c1].priority > queue_data[c2].priority)
+          c = c1;
+        else
+          c = c2;
+        queue_data[p] = queue_data[c];
+        p = c;
+      }
+
+      // NOTE(boulos): qsize >= 1, so this is legal and correct.
+      queue_data[p] = queue_data[qsize-1];
+      reheapify(p);
+
+      qsize--;
+      return result;
+    }
+
+    void push(const DataType& data, const PriorityType& priority) {
+      if (qsize >= capacity) {
+        // Grow by a factor of 2
+        reallocate(2 * qsize);
+      }
+      queue_data[qsize].data = data;
+      queue_data[qsize].priority = priority;
+      size_t p = qsize++;
+      reheapify(p);
+    }
+
+  private:
+    void reheapify(size_t p) {
+      while(p){
+        size_t parent = (p-1)>>1;
+        if(queue_data[p].priority > queue_data[parent].priority){
+          // Swap
+          PriorityQueueEntry tmp = queue_data[p];
+          queue_data[p] = queue_data[parent];
+          queue_data[parent] = tmp;
+        } else {
+          break;
+        }
+        p = parent;
+      }
+    }
+
+    void reallocate(size_t new_size) {
+      PriorityQueueEntry* new_data = new PriorityQueueEntry[new_size];
+      ASSERT(new_data);
+      for (size_t i = 0; i < qsize; i++) {
+        new_data[i] = queue_data[i];
+      }
+      delete[] queue_data;
+      queue_data = new_data;
+      capacity = new_size;
+    }
+
+    size_t qsize;
+    size_t capacity;
+    PriorityQueueEntry* queue_data;
+  };
+
+}; // end namespace Manta
+
+#endif // _MANTA_PRIORITY_QUEUE_H_

Modified: trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc
==============================================================================
--- trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc      (original)
+++ trunk/Engine/ImageTraversers/DeadlineImageTraverser.cc      Thu Jul 19 
15:36:23 2007
@@ -116,9 +116,7 @@
   }
   frameTime = 1./frameRate;
   tiles = 0;
-  queue = 0;
   total_tiles = 0;
-  qsize = 0;
   singleSampler = new SingleSampler(vector<string>());
 
   //cerr << "xpacketsize = " << xpacketsize << endl;
@@ -152,7 +150,7 @@
   context.pixelSampler->setupBegin(context, numChannels);
   if(total_tiles){
     delete[] tiles;
-    delete[] queue;
+    queue.clear();
   }
   total_tiles = 0;
   top_tiles = 0;
@@ -170,7 +168,7 @@
   if (context.proc == 0) {
     // 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 (qsize and next_tile)
+    // frame will clean up the other data (queue and next_tile)
     //cerr << "changeIdleMode called with changed = " << changed << endl;
     if (changed) {
       reset_every_frame = true;
@@ -236,14 +234,14 @@
   ntotal += cur;
   if(total_tiles){
     delete[] tiles;
-    delete[] queue;
+    queue.clear();
   }
   if(numAssignments > top_tiles)
     top_tiles = numAssignments;
   total_tiles = ntotal * xtiles * ytiles;
   //cerr << "Total tiles is now " << total_tiles << endl;
   tiles = new Tile[total_tiles];
-  queue = new Tile*[total_tiles];
+  //queue.reserve(total_tiles); // With the new queue, we don't even need to 
reserve ;)
 
   singleSampler->setupDisplayChannel(context);
   // NOTE(boulos): Having the sampler tell the renderer to setup is a
@@ -265,7 +263,7 @@
   }
   if (!finished_coarse) {
     context.loadBalancer->setupFrame(context);
-    qsize = 0;
+    queue.clear();
     next_tile = top_tiles;
     converged = false;
     StartFrameTime = CPUTime::currentSeconds();
@@ -281,13 +279,13 @@
   // Determine how long we should render this frame.
   frameEnd = CPUTime::currentSeconds() + frameTime;
   if (context.proc == 0) {
-    if (finished_coarse && qsize == 0 && !converged) {
+    if (finished_coarse && queue.empty() && !converged) {
       converged = true;
       double EndTime = CPUTime::currentSeconds();
       double total_time = EndTime - StartFrameTime;
       cerr << "Took " << total_time << " seconds to refine to 
"<<Fragment::MaxSize<<" spp" << endl;
     }
-    //cerr << "qsize = " << qsize << ", next_tile = " << next_tile << endl;
+    //cerr << "queue size = " << queue.size() << ", next_tile = " << 
next_tile << endl;
     //cerr << "totalTiles = " << total_tiles << endl;
   }
 }
@@ -295,62 +293,25 @@
 void DeadlineImageTraverser::insertIntoQueue(Tile* tiles, int numtiles)
 {
   qlock.lock();
-  if (qsize + numtiles >= total_tiles) {
+  if (queue.size() + numtiles >= total_tiles) {
     cerr << "Can't resize for insertion, but I'll just drop for now." << 
endl;
     qlock.unlock();
     return;
     throw SCIRun::InternalError("Can't currently resize during rendering", 
__FILE__, __LINE__);
-    resizeQueue(2*(qsize + numtiles));
   }
 
   for(int i=0;i<numtiles;i++){
     Tile* tile = &tiles[i];
-
-    // Heap insert
-    if (qsize >= total_tiles) {
-      cerr << "Uh oh, ran out of queue space\n";
-      return;
-    }
-    queue[qsize] = tile;
-    int p = qsize++;
-    while(p){
-      int parent = (p-1)>>1;
-      if(queue[p]->priority > queue[parent]->priority){
-        // Swap
-        Tile* tmp = queue[p];
-        queue[p] = queue[parent];
-        queue[parent] = tmp;
-      } else {
-        break;
-      }
-      p = parent;
-    }
+    queue.push(tile, tile->priority);
   }
   qlock.unlock();
 }
 
-// NOTE(boulos): This function assumes you own the lock for the queue
-void DeadlineImageTraverser::resizeQueue(int new_size) {
-  // Must allocate a new queue of size new_size and then copy all
-  // the elements from 0 to qsize-1 into the new array
-  Tile** new_queue = new Tile*[new_size];
-  Tile*  new_tiles = new Tile[new_size];
-  for (int i = 0; i < qsize; i++) {
-    new_queue[i] = queue[i];
-    new_tiles[i] = tiles[i];
-  }
-  delete[] queue;
-  delete[] tiles;
-  queue = new_queue;
-  tiles = new_tiles;
-  total_tiles = new_size;
-}
-
 DeadlineImageTraverser::Tile* DeadlineImageTraverser::popFromQueue(Tile*& 
childtiles)
 {
   int numtiles = xrefinementRatio * yrefinementRatio;
   qlock.lock();
-  if(qsize == 0){
+  if(queue.empty()) {
     qlock.unlock();
     return 0;
   }
@@ -363,47 +324,11 @@
     qlock.unlock();
     return NULL;
     throw SCIRun::InternalError("Can't currently resize during rendering", 
__FILE__, __LINE__);
-    resizeQueue(next_tile * 2);
-    //cerr << "Uh oh, ran out of tile space for kids\n";
-    //return 0;
-  }
-
-  // Get the next tile and update the queue
-  Tile* tile = queue[0];
-  tile->priority = -1;
-
-  // NOTE(boulos): This part looks for a new root node. So the part
-  // where you replace queue[p] with queue[c] is actually okay (since
-  // we're removing the root node).
-  int p = 0;
-  while((p<<1)+2 < qsize){
-    int c1 = (p<<1)+1;
-    int c2 = (p<<1)+2;
-    int c;
-    if(queue[c1]->priority > queue[c2]->priority)
-      c = c1;
-    else
-      c = c2;
-    queue[p] = queue[c];
-    p = c;
-  }
-
-  // NOTE(boulos): qsize >= 1, so this is legal and correct.
-  queue[p] = queue[qsize-1];
-  while(p){
-    int parent = (p-1)>>1;
-    if(queue[p]->priority > queue[parent]->priority){
-      // Swap
-      Tile* tmp = queue[p];
-      queue[p] = queue[parent];
-      queue[parent] = tmp;
-    } else {
-      break;
-    }
-    p = parent;
   }
 
-  qsize--;
+  // Get the next tile from the queue
+  Tile* tile = queue.pop();
+
   qlock.unlock();
   return tile;
 }

Modified: trunk/Engine/ImageTraversers/DeadlineImageTraverser.h
==============================================================================
--- trunk/Engine/ImageTraversers/DeadlineImageTraverser.h       (original)
+++ trunk/Engine/ImageTraversers/DeadlineImageTraverser.h       Thu Jul 19 
15:36:23 2007
@@ -34,6 +34,8 @@
 #include <Interface/ImageTraverser.h>
 #include <Interface/Fragment.h>
 #include <Core/Thread/Mutex.h>
+#include <Core/Util/PriorityQueue.h>
+
 #include <sgi_stl_warnings_off.h>
 #include <string>
 #include <vector>
@@ -91,9 +93,10 @@
     };
     SCIRun::Mutex qlock;
     Tile* tiles;
-    Tile** queue;
+    //Tile** queue;
+    PriorityQueue<Tile*, float> queue;
     int next_tile;
-    int qsize;
+    //int qsize;
     int total_tiles;
     int top_tiles;
     bool reset_every_frame;
@@ -108,7 +111,7 @@
 
     void insertIntoQueue(Tile* oldtile, int numtiles);
     Tile* popFromQueue(Tile*& childtiles);
-    void resizeQueue(int new_size);
+
     void computePriority(Tile* tile, const Fragment& frag) const;
   };
 }

---

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

---

Archive powered by MHonArc 2.6.16.