msgQ test: Now also reports performance of STL-based variant of msg Q
authorRamprasad Venkataraman <ramv@illinois.edu>
Mon, 18 Jun 2012 21:45:53 +0000 (16:45 -0500)
committerRamprasad Venkataraman <ramv@illinois.edu>
Thu, 28 Jun 2012 16:00:32 +0000 (11:00 -0500)
Charm uses a custom message queue that handles arbitrary bitvector priorities.
Underneath, it implements three separate queues for -ve, +ve and zero priorities.

The test now includes a simple, STL-based implementation of similar functionality,
so that we can compare charm's msg q performance against a simple STL version.
Monitoring these numbers should help guide optimizations.

Capabilities of the reference STL msgQ
- Only integer / long / compile-time fixed length priorities are directly supported
- arbitrary bitvec prios can be supported using thin wrappers to the priority type
- std::less is assumed to be available for the priority type

The STL version is still quite naive and could use optimization, but is faster than
charm's custom implementation on g++ 4.4 on net-linux-x86_64.

tests/charm++/queue/msgq.h [new file with mode: 0644]
tests/charm++/queue/pgm.C

diff --git a/tests/charm++/queue/msgq.h b/tests/charm++/queue/msgq.h
new file mode 100644 (file)
index 0000000..50a351e
--- /dev/null
@@ -0,0 +1,112 @@
+#ifndef MSG_Q_H
+#define MSG_Q_H
+
+#include <deque>
+#include <queue>
+#include <map>
+#include <ostream>
+
+typedef void msg_t;
+
+template <typename P>
+inline P defaultprio(P *dummy_tag) { return 0; }
+
+
+template <typename P = int>
+class msgQ
+{
+    public:
+        typedef P prio_t;
+
+        ///
+        msgQ(): qSize(0) {}
+        ///
+        void enq(const msg_t *msg
+                ,const prio_t &prio = defaultprio<prio_t>(0)
+                ,const bool isFifo = true
+                );
+        ///
+        const msg_t* deq();
+        ///
+        const msg_t* front() const;
+        ///
+        inline size_t size() const { return qSize; }
+        ///
+        inline bool empty() const { return (0 == qSize); }
+        ///
+        inline prio_t top_priority() const { return prios.top(); }
+
+        ///
+        friend std::ostream& operator<< (std::ostream &out, const msgQ &q)
+        {
+            out <<"\nmsgQ[" << q.qSize << "]:";
+            out<<"\n";
+            return out;
+        }
+
+    private:
+        size_t qSize;
+        std::map<prio_t, std::deque<const msg_t*> > msgmap;
+        std::priority_queue<prio_t, std::vector<prio_t>, std::greater<prio_t> > prios;
+};
+
+
+
+template <typename P>
+void msgQ<P>::enq(const msg_t *msg
+                 ,const prio_t &prio
+                 ,const bool isFifo
+                 )
+{
+    // Create or access deq holding msgs of this priority
+    std::deque<const msg_t*> &q = msgmap[prio];
+    // If this deq is empty, insert corresponding priority into prioQ
+    if (q.empty())
+        prios.push(prio);
+    // Enq msg either at front or back of deq
+    if (isFifo)
+        q.push_back(msg);
+    else
+        q.push_front(msg);
+    // Increment the total number of msgs in this container
+    qSize++;
+
+}
+
+
+
+template <typename P>
+const msg_t* msgQ<P>::deq()
+{
+    if (prios.empty())
+        return NULL;
+
+    // Get the top priority in the priority queue
+    const prio_t &prio = prios.top();
+
+    std::deque<const msg_t*> &q = msgmap[prio];
+    // Assert that there is at least one msg corresponding to this priority, in the msgmap
+    if (q.empty()) throw;
+    const msg_t *msg = q.front();
+    q.pop_front();
+    // If all msgs of the highest priority have been consumed, pop that priority from the priority Q
+    if (q.empty())
+        prios.pop();
+    // Decrement the total number of msgs in this container
+    qSize--;
+    return msg;
+}
+
+
+
+template <typename P>
+const msg_t* msgQ<P>::front() const
+{
+    if (prios.empty())
+        return NULL;
+    prio_t &prio = prios.top();
+    return msgmap[prio].front();
+}
+
+#endif // MSG_Q_H
+
index 25368afc3523d7a6017efc8b4a69807ca914aa10..9ac2168aecc57cd5f6ecd1a050acdf8fbdab1edf 100644 (file)
@@ -8,6 +8,7 @@ using std::endl;
 using std::sprintf;
 
 #include "queueing.h"
 using std::sprintf;
 
 #include "queueing.h"
+#include "msgq.h"
 #include "main.decl.h"
 
 #define CmiFree free
 #include "main.decl.h"
 
 #define CmiFree free
@@ -205,16 +206,51 @@ double timePerOp_general_ififo(int qBaseSize = 256)
 }
 
 
 }
 
 
+double timePerOp_stlQ(int qBaseSize = 256)
+{
+  msgQ<int> q;
+  int qBatchSize = 1<<4;
+  int numIters   = 1<<16;
+
+  std::vector<char> msgs(qBaseSize + qBatchSize);
+  std::vector<unsigned int> prios(qBaseSize + qBatchSize);
+
+  for (int i = 0; i < qBaseSize + qBatchSize; i++)
+      prios[i] = std::rand();
+
+  for (int i = 0; i < qBaseSize; i++)
+      q.enq((msg_t*)&msgs[i], prios[i]);
+
+  double startTime = CmiWallTimer();
+  for (int i = 0; i < numIters; i++)
+  {
+      for (int j = qBaseSize; j < qBaseSize+qBatchSize; j++)
+          q.enq((msg_t*)&msgs[j], prios[j]);
+      void *m;
+      for (int j = qBaseSize; j < qBaseSize+qBatchSize; j++)
+        q.deq();
+  }
+
+  return 1000000 * (CmiWallTimer() - startTime) / (numIters * qBatchSize * 2);
+}
+
+
 bool perftest_general_ififo()
 {
   CkPrintf("Reporting time per enqueue / dequeue operation for charm's underlying mixed priority queue\n");
   CkPrintf("\n  Q length     time/op(us)\n");
 bool perftest_general_ififo()
 {
   CkPrintf("Reporting time per enqueue / dequeue operation for charm's underlying mixed priority queue\n");
   CkPrintf("\n  Q length     time/op(us)\n");
-  for (int i = 16; i <= 1024; i *= 2)
+  for (int i = 16; i <= 2048; i *= 2)
     CkPrintf("%10d %15f\n", i, timePerOp_general_ififo(i));
 
     CkPrintf("%10d %15f\n", i, timePerOp_general_ififo(i));
 
+  printf("Reporting time per enqueue / dequeue operation for an STL version of the same Q functionality\n");
+  printf("\n  Q length     time/op(us)\n");
+  for (int i = 16; i <= 2048; i *= 2)
+    printf("%10d %15f\n", i, timePerOp_stlQ(i));
+
   return true;
 }
 
   return true;
 }
 
+
 #if 0
 // Template for new harness-driven tests
 bool test_foo()
 #if 0
 // Template for new harness-driven tests
 bool test_foo()