ruby: get rid of PrioHeap and use STL

One big difference is that PrioHeap puts the smallest element at the
top of the heap, whereas stl puts the largest element on top, so I
changed all comparisons so they did the right thing.

Some usage of PrioHeap was simply changed to a std::vector, using sort
at the right time, other usage had me just use the various heap functions
in the stl.

22 files changed, 120 insertions, 119 deletions

diff --git a/src/mem/ruby/buffers/MessageBuffer.cc b/src/mem/ruby/buffers/MessageBuffer.cc
index 26d187305..9cd1dd47b 100644
--- a/src/mem/ruby/buffers/MessageBuffer.cc
+++ b/src/mem/ruby/buffers/MessageBuffer.cc
@@ -27,10 +27,12 @@
  */
 
 #include "base/cprintf.hh"
+#include "base/stl_helpers.hh"
 #include "mem/ruby/buffers/MessageBuffer.hh"
 #include "mem/ruby/system/System.hh"
 
 using namespace std;
+using m5::stl_helpers::operator<<;
 
 MessageBuffer::MessageBuffer(const string &name)
 {
@@ -111,7 +113,7 @@ MessageBuffer::getMsgPtrCopy() const
 {
     assert(isReady());
 
-    return m_prio_heap.peekMin().m_msgptr->clone();
+    return m_prio_heap.front().m_msgptr->clone();
 }
 
 const Message*
@@ -124,7 +126,7 @@ MessageBuffer::peekAtHeadOfQueue() const
                        m_name, g_eventQueue_ptr->getTime()));
     assert(isReady());
 
-    const Message* msg_ptr = m_prio_heap.peekMin().m_msgptr.get();
+    const Message* msg_ptr = m_prio_heap.front().m_msgptr.get();
     assert(msg_ptr);
 
     DEBUG_EXPR(QUEUE_COMP, MedPrio, *msg_ptr);
@@ -223,7 +225,9 @@ MessageBuffer::enqueue(MsgPtr message, Time delta)
 
     // Insert the message into the priority heap
     MessageBufferNode thisNode(arrival_time, m_msg_counter, message);
-    m_prio_heap.insert(thisNode);
+    m_prio_heap.push_back(thisNode);
+    push_heap(m_prio_heap.begin(), m_prio_heap.end(),
+        greater<MessageBufferNode>());
 
     DEBUG_NEWLINE(QUEUE_COMP, HighPrio);
     DEBUG_MSG(QUEUE_COMP, HighPrio,
@@ -260,7 +264,7 @@ void
 MessageBuffer::dequeue(MsgPtr& message)
 {
     DEBUG_MSG(QUEUE_COMP, MedPrio, "dequeue from " + m_name);
-    message = m_prio_heap.peekMin().m_msgptr;
+    message = m_prio_heap.front().m_msgptr;
 
     pop();
     DEBUG_EXPR(QUEUE_COMP, MedPrio, message);
@@ -272,7 +276,7 @@ MessageBuffer::dequeue_getDelayCycles()
     int delay_cycles = -1;  // null value
 
     // get MsgPtr of the message about to be dequeued
-    MsgPtr message = m_prio_heap.peekMin().m_msgptr;
+    MsgPtr message = m_prio_heap.front().m_msgptr;
 
     // get the delay cycles
     delay_cycles = setAndReturnDelayCycles(message);
@@ -288,7 +292,10 @@ MessageBuffer::pop()
 {
     DEBUG_MSG(QUEUE_COMP, MedPrio, "pop from " + m_name);
     assert(isReady());
-    m_prio_heap.extractMin();
+    pop_heap(m_prio_heap.begin(), m_prio_heap.end(),
+        greater<MessageBufferNode>());
+    m_prio_heap.pop_back();
+
     // record previous size and time so the current buffer size isn't
     // adjusted until next cycle
     if (m_time_last_time_pop < g_eventQueue_ptr->getTime()) {
@@ -301,11 +308,7 @@ MessageBuffer::pop()
 void
 MessageBuffer::clear()
 {
-    while(m_prio_heap.size() > 0){
-        m_prio_heap.extractMin();
-    }
-
-    ASSERT(m_prio_heap.size() == 0);
+    m_prio_heap.clear();
 
     m_msg_counter = 0;
     m_size = 0;
@@ -320,9 +323,13 @@ MessageBuffer::recycle()
 {
     DEBUG_MSG(QUEUE_COMP, MedPrio, "recycling " + m_name);
     assert(isReady());
-    MessageBufferNode node = m_prio_heap.extractMin();
+    MessageBufferNode node = m_prio_heap.front();
+    pop_heap(m_prio_heap.begin(), m_prio_heap.end(),
+        greater<MessageBufferNode>());
     node.m_time = g_eventQueue_ptr->getTime() + m_recycle_latency;
-    m_prio_heap.insert(node);
+    m_prio_heap.back() = node;
+    push_heap(m_prio_heap.begin(), m_prio_heap.end(),
+        greater<MessageBufferNode>());
     g_eventQueue_ptr->scheduleEventAbsolute(m_consumer_ptr,
         g_eventQueue_ptr->getTime() + m_recycle_latency);
 }
@@ -353,7 +360,10 @@ MessageBuffer::print(ostream& out) const
     if (m_consumer_ptr != NULL) {
         out << " consumer-yes ";
     }
-    out << m_prio_heap << "] " << m_name << endl;
+
+    vector<MessageBufferNode> copy(m_prio_heap);
+    sort_heap(copy.begin(), copy.end(), greater<MessageBufferNode>());
+    out << copy << "] " << m_name << endl;
 }
 
 void
diff --git a/src/mem/ruby/buffers/MessageBuffer.hh b/src/mem/ruby/buffers/MessageBuffer.hh
index 12799c871..9315eaec0 100644
--- a/src/mem/ruby/buffers/MessageBuffer.hh
+++ b/src/mem/ruby/buffers/MessageBuffer.hh
@@ -34,10 +34,12 @@
 #ifndef __MEM_RUBY_BUFFERS_MESSAGEBUFFER_HH__
 #define __MEM_RUBY_BUFFERS_MESSAGEBUFFER_HH__
 
+#include <algorithm>
+#include <functional>
 #include <iostream>
+#include <vector>
 #include <string>
 
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/ruby/buffers/MessageBufferNode.hh"
 #include "mem/ruby/common/Consumer.hh"
 #include "mem/ruby/common/Global.hh"
@@ -61,13 +63,16 @@ class MessageBuffer
     isReady() const
     {
         return ((m_prio_heap.size() > 0) &&
-                (m_prio_heap.peekMin().m_time <= g_eventQueue_ptr->getTime()));
+                (m_prio_heap.front().m_time <= g_eventQueue_ptr->getTime()));
     }
 
     void
     delayHead()
     {
-        MessageBufferNode node = m_prio_heap.extractMin();
+        MessageBufferNode node = m_prio_heap.front();
+        std::pop_heap(m_prio_heap.begin(), m_prio_heap.end(),
+                      std::greater<MessageBufferNode>());
+        m_prio_heap.pop_back();
         enqueue(node.m_msgptr, 1);
     }
 
@@ -93,13 +98,13 @@ class MessageBuffer
     peekMsgPtr() const
     {
         assert(isReady());
-        return m_prio_heap.peekMin().m_msgptr;
+        return m_prio_heap.front().m_msgptr;
     }
 
     const MsgPtr&
     peekMsgPtrEvenIfNotReady() const
     {
-        return m_prio_heap.peekMin().m_msgptr;
+        return m_prio_heap.front().m_msgptr;
     }
 
     void enqueue(MsgPtr message) { enqueue(message, 1); }
@@ -144,7 +149,7 @@ class MessageBuffer
 
     // Data Members (m_ prefix)
     Consumer* m_consumer_ptr;  // Consumer to signal a wakeup(), can be NULL
-    PrioHeap<MessageBufferNode> m_prio_heap;
+    std::vector<MessageBufferNode> m_prio_heap;
     std::string m_name;
 
     int m_max_size;
diff --git a/src/mem/ruby/buffers/MessageBufferNode.hh b/src/mem/ruby/buffers/MessageBufferNode.hh
index 9ead9b9aa..078da47c4 100644
--- a/src/mem/ruby/buffers/MessageBufferNode.hh
+++ b/src/mem/ruby/buffers/MessageBufferNode.hh
@@ -59,13 +59,13 @@ class MessageBufferNode
 };
 
 inline bool
-node_less_then_eq(const MessageBufferNode& n1, const MessageBufferNode& n2)
+operator>(const MessageBufferNode& n1, const MessageBufferNode& n2)
 {
     if (n1.m_time == n2.m_time) {
         assert(n1.m_msg_counter != n2.m_msg_counter);
-        return (n1.m_msg_counter <= n2.m_msg_counter);
+        return n1.m_msg_counter > n2.m_msg_counter;
     } else {
-        return (n1.m_time <= n2.m_time);
+        return n1.m_time > n2.m_time;
     }
 }
 
diff --git a/src/mem/ruby/eventqueue/RubyEventQueue.hh b/src/mem/ruby/eventqueue/RubyEventQueue.hh
index 4a0fb9ceb..6fa8b0ac3 100644
--- a/src/mem/ruby/eventqueue/RubyEventQueue.hh
+++ b/src/mem/ruby/eventqueue/RubyEventQueue.hh
@@ -63,7 +63,6 @@
 #include "sim/eventq.hh"
 
 class Consumer;
-template <class TYPE> class PrioHeap;
 class RubyEventQueueNode;
 
 class RubyEventQueue : public EventManager
diff --git a/src/mem/ruby/network/garnet/fixed-pipeline/NetworkLink_d.hh b/src/mem/ruby/network/garnet/fixed-pipeline/NetworkLink_d.hh
index 29699562d..39fdd3c6f 100644
--- a/src/mem/ruby/network/garnet/fixed-pipeline/NetworkLink_d.hh
+++ b/src/mem/ruby/network/garnet/fixed-pipeline/NetworkLink_d.hh
@@ -37,7 +37,6 @@
 #include "mem/ruby/network/garnet/NetworkHeader.hh"
 #include "mem/ruby/common/Consumer.hh"
 #include "mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh"
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/ruby/network/orion/power_bus.hh"
 
 class GarnetNetwork_d;
diff --git a/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.cc b/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.cc
index 38510c758..5387604d4 100644
--- a/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.cc
+++ b/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.cc
@@ -49,7 +49,7 @@ bool flitBuffer_d::isReady()
 {
         if(m_buffer.size() != 0 )
         {
-                flit_d *t_flit = m_buffer.peekMin();
+                flit_d *t_flit = peekTopFlit();
                 if(t_flit->get_time() <= g_eventQueue_ptr->getTime())
                         return true;
         }
@@ -60,7 +60,7 @@ bool flitBuffer_d::isReadyForNext()
 {
         if(m_buffer.size() != 0 )
         {
-                flit_d *t_flit = m_buffer.peekMin();
+                flit_d *t_flit = peekTopFlit();
                 if(t_flit->get_time() <= (g_eventQueue_ptr->getTime() + 1))
                         return true;
         }
diff --git a/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh b/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh
index 976fa4053..8aa869f82 100644
--- a/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh
+++ b/src/mem/ruby/network/garnet/fixed-pipeline/flitBuffer_d.hh
@@ -31,10 +31,11 @@
 #ifndef FLIT_BUFFER_D_H
 #define FLIT_BUFFER_D_H
 
+#include <algorithm>
 #include <iostream>
+#include <vector>
 
 #include "mem/ruby/network/garnet/NetworkHeader.hh"
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/ruby/network/garnet/fixed-pipeline/flit_d.hh"
 
 class flitBuffer_d {
@@ -51,19 +52,23 @@ public:
 
         inline flit_d* getTopFlit()
         {
-                return m_buffer.extractMin();
+            flit_d *f = m_buffer.front();
+            std::pop_heap(m_buffer.begin(), m_buffer.end(), flit_d::greater);
+            m_buffer.pop_back();
+            return f;
         }
         inline flit_d* peekTopFlit()
         {
-                return m_buffer.peekMin();
+            return m_buffer.front();
         }
         inline void insert(flit_d *flt)
         {
-                m_buffer.insert(flt);
+            m_buffer.push_back(flt);
+            std::push_heap(m_buffer.begin(), m_buffer.end(), flit_d::greater);
         }
         /**********Data Members*********/
 private:
-        PrioHeap <flit_d *> m_buffer;
+        std::vector<flit_d *> m_buffer;
         int size, max_size;
 };
 
diff --git a/src/mem/ruby/network/garnet/fixed-pipeline/flit_d.hh b/src/mem/ruby/network/garnet/fixed-pipeline/flit_d.hh
index 39bbe011d..ec2774a94 100644
--- a/src/mem/ruby/network/garnet/fixed-pipeline/flit_d.hh
+++ b/src/mem/ruby/network/garnet/fixed-pipeline/flit_d.hh
@@ -115,6 +115,16 @@ public:
                 return src_delay;
         }
 
+        static bool
+        greater(flit_d* n1, flit_d* n2)
+        {
+            if (n1->get_time() == n2->get_time()) {
+                //ASSERT(n1->flit_id != n2->flit_id);
+                return (n1->get_id() > n2->get_id());
+            } else {
+                return (n1->get_time() > n2->get_time());
+            }
+        }
 
 private:
         /************Data Members*************/
@@ -132,19 +142,6 @@ private:
 
 };
 
-inline extern bool node_less_then_eq(flit_d* n1, flit_d* n2);
-
-inline extern
-bool node_less_then_eq(flit_d* n1, flit_d* n2)
-{
-  if (n1->get_time() == n2->get_time()) {
-//    ASSERT(n1->flit_id != n2->flit_id);
-    return (n1->get_id() <= n2->get_id());
-  } else {
-    return (n1->get_time() <= n2->get_time());
-  }
-}
-
 inline std::ostream&
 operator<<(std::ostream& out, const flit_d& obj)
 {
diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh b/src/mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh
index c23d55b48..9f1311dce 100644
--- a/src/mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh
+++ b/src/mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh
@@ -37,7 +37,6 @@
 #include "mem/ruby/network/garnet/NetworkHeader.hh"
 #include "mem/ruby/network/garnet/flexible-pipeline/FlexibleConsumer.hh"
 #include "mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh"
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/ruby/common/NetDest.hh"
 
 class GarnetNetwork;
diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/Router.hh b/src/mem/ruby/network/garnet/flexible-pipeline/Router.hh
index b6ebb601f..16b19204a 100644
--- a/src/mem/ruby/network/garnet/flexible-pipeline/Router.hh
+++ b/src/mem/ruby/network/garnet/flexible-pipeline/Router.hh
@@ -37,7 +37,6 @@
 #include "mem/ruby/network/garnet/NetworkHeader.hh"
 #include "mem/ruby/network/garnet/flexible-pipeline/GarnetNetwork.hh"
 #include "mem/ruby/network/garnet/flexible-pipeline/FlexibleConsumer.hh"
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/ruby/network/garnet/flexible-pipeline/NetworkLink.hh"
 #include "mem/ruby/common/NetDest.hh"
 #include "mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh"
diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/flit.hh b/src/mem/ruby/network/garnet/flexible-pipeline/flit.hh
index 1cc8806e9..5aa01c5e7 100644
--- a/src/mem/ruby/network/garnet/flexible-pipeline/flit.hh
+++ b/src/mem/ruby/network/garnet/flexible-pipeline/flit.hh
@@ -52,6 +52,16 @@ public:
         flit_type get_type();
         void print(std::ostream& out) const;
 
+        static bool
+        greater(flit* n1, flit* n2)
+        {
+            if (n1->get_time() == n2->get_time())
+                //ASSERT(n1->flit_id != n2->flit_id);
+                return (n1->get_id() > n2->get_id());
+            else
+                return (n1->get_time() > n2->get_time());
+        }
+
 private:
 /************Data Members*************/
         int m_id;
@@ -64,19 +74,6 @@ private:
 
 };
 
-inline extern bool node_less_then_eq(flit* n1, flit* n2);
-
-inline extern
-bool node_less_then_eq(flit* n1, flit* n2)
-{
-  if (n1->get_time() == n2->get_time()) {
-//    ASSERT(n1->flit_id != n2->flit_id);
-    return (n1->get_id() <= n2->get_id());
-  } else {
-    return (n1->get_time() <= n2->get_time());
-  }
-}
-
 inline std::ostream&
 operator<<(std::ostream& out, const flit& obj)
 {
diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.cc b/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.cc
index 7f41d6f8c..82eb08902 100644
--- a/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.cc
+++ b/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.cc
@@ -28,8 +28,12 @@
  * Authors: Niket Agarwal
  */
 
+#include <algorithm>
+
 #include "mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh"
 
+using namespace std;
+
 flitBuffer::flitBuffer()
 {
         max_size = INFINITE_;
@@ -49,7 +53,7 @@ bool flitBuffer::isReady()
 {
         if(m_buffer.size() != 0 )
         {
-                flit *t_flit = m_buffer.peekMin();
+                flit *t_flit = m_buffer.front();
                 if(t_flit->get_time() <= g_eventQueue_ptr->getTime())
                         return true;
         }
@@ -60,7 +64,7 @@ bool flitBuffer::isReadyForNext()
 {
         if(m_buffer.size() != 0 )
         {
-                flit *t_flit = m_buffer.peekMin();
+                flit *t_flit = m_buffer.front();
                 if(t_flit->get_time() <= (g_eventQueue_ptr->getTime() + 1))
                         return true;
         }
@@ -79,17 +83,21 @@ void flitBuffer::setMaxSize(int maximum)
 
 flit* flitBuffer:: getTopFlit()
 {
-        return m_buffer.extractMin();
+        flit *f = m_buffer.front();
+        pop_heap(m_buffer.begin(), m_buffer.end(), flit::greater);
+        m_buffer.pop_back();
+        return f;
 }
 
 flit* flitBuffer::peekTopFlit()
 {
-        return m_buffer.peekMin();
+        return m_buffer.front();
 }
 
 void flitBuffer::insert(flit *flt)
 {
-        m_buffer.insert(flt);
+        m_buffer.push_back(flt);
+        push_heap(m_buffer.begin(), m_buffer.end(), flit::greater);
 }
 
 void flitBuffer::print(std::ostream& out) const
diff --git a/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh b/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh
index 646cd99c7..a5ec25590 100644
--- a/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh
+++ b/src/mem/ruby/network/garnet/flexible-pipeline/flitBuffer.hh
@@ -32,9 +32,9 @@
 #define FLIT_BUFFER_H
 
 #include <iostream>
+#include <vector>
 
 #include "mem/ruby/network/garnet/NetworkHeader.hh"
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/ruby/network/garnet/flexible-pipeline/flit.hh"
 
 class flitBuffer {
@@ -54,7 +54,7 @@ public:
 
 /**********Data Members*********/
 private:
-        PrioHeap <flit *> m_buffer;
+        std::vector<flit *> m_buffer;
         int size, max_size;
 };
 
diff --git a/src/mem/ruby/profiler/AccessTraceForAddress.hh b/src/mem/ruby/profiler/AccessTraceForAddress.hh
index a707cd4df..b950f2be2 100644
--- a/src/mem/ruby/profiler/AccessTraceForAddress.hh
+++ b/src/mem/ruby/profiler/AccessTraceForAddress.hh
@@ -60,6 +60,13 @@ class AccessTraceForAddress
 
     void print(std::ostream& out) const;
 
+    static inline bool
+    less_equal(const AccessTraceForAddress* n1,
+        const AccessTraceForAddress* n2)
+    {
+        return n1->getTotal() <= n2->getTotal();
+    }
+
   private:
     Address m_addr;
     uint64 m_loads;
@@ -72,13 +79,6 @@ class AccessTraceForAddress
     Histogram* m_histogram_ptr;
 };
 
-inline bool
-node_less_then_eq(const AccessTraceForAddress* n1,
-                  const AccessTraceForAddress* n2)
-{
-    return n1->getTotal() > n2->getTotal();
-}
-
 inline std::ostream&
 operator<<(std::ostream& out, const AccessTraceForAddress& obj)
 {
diff --git a/src/mem/ruby/profiler/AddressProfiler.cc b/src/mem/ruby/profiler/AddressProfiler.cc
index 4274569ad..5c1b7352c 100644
--- a/src/mem/ruby/profiler/AddressProfiler.cc
+++ b/src/mem/ruby/profiler/AddressProfiler.cc
@@ -29,7 +29,6 @@
 #include <vector>
 
 #include "base/stl_helpers.hh"
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/protocol/CacheMsg.hh"
 #include "mem/ruby/profiler/AddressProfiler.hh"
 #include "mem/ruby/profiler/Profiler.hh"
@@ -70,15 +69,16 @@ printSorted(ostream& out, int num_of_sequencers, const AddressMap &record_map,
     const int records_printed = 100;
 
     uint64 misses = 0;
-    PrioHeap<const AccessTraceForAddress*> heap;
+    std::vector<const AccessTraceForAddress *> sorted;
 
     AddressMap::const_iterator i = record_map.begin();
     AddressMap::const_iterator end = record_map.end();
     for (; i != end; ++i) {
         const AccessTraceForAddress* record = &i->second;
         misses += record->getTotal();
-        heap.insert(record);
+        sorted.push_back(record);
     }
+    sort(sorted.begin(), sorted.end(), AccessTraceForAddress::less_equal);
 
     out << "Total_entries_" << description << ": " << record_map.size()
         << endl;
@@ -106,8 +106,9 @@ printSorted(ostream& out, int num_of_sequencers, const AddressMap &record_map,
     }
 
     int counter = 0;
-    while (heap.size() > 0 && counter < records_printed) {
-        const AccessTraceForAddress* record = heap.extractMin();
+    int max = sorted.size();
+    while (counter < max && counter < records_printed) {
+        const AccessTraceForAddress* record = sorted[counter];
         double percent = 100.0 * (record->getTotal() / double(misses));
         out << description << " | " << percent << " % " << *record << endl;
         all_records.add(record->getTotal());
@@ -117,8 +118,8 @@ printSorted(ostream& out, int num_of_sequencers, const AddressMap &record_map,
         m_touched_weighted_vec[record->getTouchedBy()] += record->getTotal();
     }
 
-    while (heap.size() > 0) {
-        const AccessTraceForAddress* record = heap.extractMin();
+    while (counter < max) {
+        const AccessTraceForAddress* record = sorted[counter];
         all_records.add(record->getTotal());
         remaining_records.add(record->getTotal());
         all_records_log.add(record->getTotal());
diff --git a/src/mem/ruby/profiler/CacheProfiler.cc b/src/mem/ruby/profiler/CacheProfiler.cc
index 8ba64add9..006617190 100644
--- a/src/mem/ruby/profiler/CacheProfiler.cc
+++ b/src/mem/ruby/profiler/CacheProfiler.cc
@@ -26,7 +26,6 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/ruby/profiler/CacheProfiler.hh"
 #include "mem/ruby/profiler/Profiler.hh"
 #include "mem/ruby/system/System.hh"
diff --git a/src/mem/ruby/profiler/Profiler.cc b/src/mem/ruby/profiler/Profiler.cc
index 33d490a85..2b844ef9d 100644
--- a/src/mem/ruby/profiler/Profiler.cc
+++ b/src/mem/ruby/profiler/Profiler.cc
@@ -50,7 +50,6 @@
 
 #include "base/stl_helpers.hh"
 #include "base/str.hh"
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/protocol/CacheMsg.hh"
 #include "mem/protocol/MachineType.hh"
 #include "mem/protocol/Protocol.hh"
diff --git a/src/mem/ruby/recorder/CacheRecorder.cc b/src/mem/ruby/recorder/CacheRecorder.cc
index 32db211b6..1d08eef12 100644
--- a/src/mem/ruby/recorder/CacheRecorder.cc
+++ b/src/mem/ruby/recorder/CacheRecorder.cc
@@ -26,31 +26,21 @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
+#include <algorithm>
+
 #include "gzstream.hh"
 
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/ruby/eventqueue/RubyEventQueue.hh"
 #include "mem/ruby/recorder/CacheRecorder.hh"
-#include "mem/ruby/recorder/TraceRecord.hh"
 
 using namespace std;
 
-CacheRecorder::CacheRecorder()
-{
-    m_records_ptr = new PrioHeap<TraceRecord>;
-}
-
-CacheRecorder::~CacheRecorder()
-{
-    delete m_records_ptr;
-}
-
 void
 CacheRecorder::addRecord(Sequencer* sequencer, const Address& data_addr,
     const Address& pc_addr, RubyRequestType type, Time time)
 {
-    m_records_ptr->
-        insert(TraceRecord(sequencer, data_addr, pc_addr, type, time));
+    TraceRecord rec(sequencer, data_addr, pc_addr, type, time);
+    m_records.push_back(rec);
 }
 
 int
@@ -62,13 +52,15 @@ CacheRecorder::dumpRecords(string filename)
         return 0;
     }
 
-    int counter = 0;
-    while (m_records_ptr->size() != 0) {
-        TraceRecord record = m_records_ptr->extractMin();
-        record.output(out);
-        counter++;
-    }
-    return counter;
+    std::sort(m_records.begin(), m_records.end(), greater<TraceRecord>());
+
+    int size = m_records.size();
+    for (int i = 0; i < size; ++i)
+        m_records[i].output(out);
+
+    m_records.clear();
+
+    return size;
 }
 
 void
diff --git a/src/mem/ruby/recorder/CacheRecorder.hh b/src/mem/ruby/recorder/CacheRecorder.hh
index 18c246c9f..14066c387 100644
--- a/src/mem/ruby/recorder/CacheRecorder.hh
+++ b/src/mem/ruby/recorder/CacheRecorder.hh
@@ -36,13 +36,14 @@
 
 #include <iostream>
 #include <string>
+#include <vector>
 
 #include "mem/protocol/CacheRequestType.hh"
 #include "mem/ruby/common/Global.hh"
 #include "mem/ruby/libruby_internal.hh"
 #include "mem/ruby/system/NodeID.hh"
+#include "mem/ruby/recorder/TraceRecord.hh"
 
-template <class TYPE> class PrioHeap;
 class Address;
 class TraceRecord;
 class Sequencer;
@@ -50,9 +51,6 @@ class Sequencer;
 class CacheRecorder
 {
   public:
-    CacheRecorder();
-    ~CacheRecorder();
-
     void addRecord(Sequencer* sequencer, const Address& data_addr,
         const Address& pc_addr, RubyRequestType type, Time time);
     int dumpRecords(std::string filename);
@@ -64,7 +62,7 @@ class CacheRecorder
     CacheRecorder(const CacheRecorder& obj);
     CacheRecorder& operator=(const CacheRecorder& obj);
 
-    PrioHeap<TraceRecord>* m_records_ptr;
+    std::vector<TraceRecord> m_records;
 };
 
 inline std::ostream&
diff --git a/src/mem/ruby/recorder/TraceRecord.hh b/src/mem/ruby/recorder/TraceRecord.hh
index 98e78b20e..ed066debb 100644
--- a/src/mem/ruby/recorder/TraceRecord.hh
+++ b/src/mem/ruby/recorder/TraceRecord.hh
@@ -60,12 +60,6 @@ class TraceRecord
     TraceRecord(const TraceRecord& obj);
     TraceRecord& operator=(const TraceRecord& obj);
 
-    bool
-    node_less_then_eq(const TraceRecord& rec) const
-    {
-        return this->m_time <= rec.m_time;
-    }
-
     void issueRequest() const;
 
     void print(std::ostream& out) const;
@@ -73,6 +67,8 @@ class TraceRecord
     bool input(std::istream& in);
 
   private:
+    friend bool operator>(const TraceRecord& n1, const TraceRecord& n2);
+
     Sequencer* m_sequencer_ptr;
     Time m_time;
     Address m_data_address;
@@ -81,9 +77,9 @@ class TraceRecord
 };
 
 inline bool
-node_less_then_eq(const TraceRecord& n1, const TraceRecord& n2)
+operator>(const TraceRecord& n1, const TraceRecord& n2)
 {
-    return n1.node_less_then_eq(n2);
+    return n1.m_time > n2.m_time;
 }
 
 inline std::ostream&
diff --git a/src/mem/ruby/recorder/Tracer.cc b/src/mem/ruby/recorder/Tracer.cc
index 23dafdb6c..bff59a832 100644
--- a/src/mem/ruby/recorder/Tracer.cc
+++ b/src/mem/ruby/recorder/Tracer.cc
@@ -27,7 +27,6 @@
  */
 
 #include "base/cprintf.hh"
-#include "mem/gems_common/PrioHeap.hh"
 #include "mem/ruby/eventqueue/RubyEventQueue.hh"
 #include "mem/ruby/recorder/TraceRecord.hh"
 #include "mem/ruby/recorder/Tracer.hh"
diff --git a/src/mem/ruby/recorder/Tracer.hh b/src/mem/ruby/recorder/Tracer.hh
index d468b4920..4b81d6121 100644
--- a/src/mem/ruby/recorder/Tracer.hh
+++ b/src/mem/ruby/recorder/Tracer.hh
@@ -46,7 +46,6 @@
 #include "params/RubyTracer.hh"
 #include "sim/sim_object.hh"
 
-template <class TYPE> class PrioHeap;
 class Address;
 class TraceRecord;
 class Sequencer;