From: Peizhao Ou <peizhaoo@uci.edu>
Date: Thu, 8 Feb 2018 23:53:09 +0000 (-0800)
Subject: Adds parallel junction map test cases
X-Git-Url: http://plrg.eecs.uci.edu/git/?p=junction.git;a=commitdiff_plain;h=50f56cab28e918328fb7c2c2e327003c490261b6;ds=sidebyside

Adds parallel junction map test cases
---

diff --git a/test/junction_parallel_driver.cpp b/test/junction_parallel_driver.cpp
index d016438..4fe6d29 100644
--- a/test/junction_parallel_driver.cpp
+++ b/test/junction_parallel_driver.cpp
@@ -1,14 +1,17 @@
-#include <cassert>
-#include <chrono>
-#include <iostream>
 #include <junction/ConcurrentMap_Crude.h>
 #include <junction/ConcurrentMap_Grampa.h>
 #include <junction/ConcurrentMap_Leapfrog.h>
 #include <junction/ConcurrentMap_Linear.h>
-#include <memory>
 
 #include <gtest/gtest.h>
 
+#include <algorithm>
+#include <cassert>
+#include <chrono>
+#include <iostream>
+#include <memory>
+#include <random>
+
 namespace junction_test {
 
 class JunctionMapInsDelFindTest : public ::testing::Test {
@@ -18,107 +21,137 @@ protected:
   typedef junction::ConcurrentMap_Leapfrog<size_t, size_t> LeapfrogMap;
   typedef junction::ConcurrentMap_Crude<size_t, size_t> CrudeMap;
 
-  static const unsigned s_nInsertPercentage = 10;
-  // Run GC after "kGCFrequency" operations.
-  static const size_t kGCFrequency = 3000;
-  static const size_t kLeapfrogGCFrequency = 1500;
+  static const unsigned s_nInsertPercentage = 5;
+  static const unsigned s_nDeletePercentage = 5;
 
-  static const size_t kCrudeMapSize = 10000;
-  static const size_t kCrudePassCount = 400000;
+  // Run GC after "kGCFrequency" operations.
+  const size_t kGCFrequency = 1500;
+  const size_t kMapSize = 20000;
+
+  enum actions { do_find, do_insert, do_delete };
+  static const unsigned int kShuffleSize = 100;
+  static actions s_arrShuffle[kShuffleSize];
+
+  const size_t kCrudePassCount = 400000;
+  const size_t kGrampaPassCount = 60000;
+  const size_t kLinearPassCount = 70000;
+  const size_t kLeapfrogPassCount = 75000;
+
+  static void SetUpTestCase() {
+    // Build an array of shuffled actions.
+    EXPECT_LE(s_nInsertPercentage + s_nDeletePercentage, 100);
+    actions* pFirst = s_arrShuffle;
+    actions* pLast = s_arrShuffle + s_nInsertPercentage;
+    std::fill(pFirst, pLast, do_insert);
+    pFirst = pLast;
+    pLast += s_nDeletePercentage;
+    std::fill(pFirst, pLast, do_delete);
+    pFirst = pLast;
+    pLast = s_arrShuffle + sizeof(s_arrShuffle) / sizeof(s_arrShuffle[0]);
+    if (pFirst < pLast) {
+      std::fill(pFirst, pLast, do_find);
+    }
+    std::random_device rd;
+    std::mt19937 g(rd());
+    std::shuffle(s_arrShuffle, pLast, g);
+  }
 
-  static const size_t kGrampaMapSize = 20000;
-  static const size_t kGrampaPassCount = 60000;
+  template <typename Map, typename Key, typename Value>
+  static bool map_insert(Map* map, Key key, Value value) {
+    auto iter = map->insertOrFind(key);
+    if (!iter.getValue()) {
+      iter.assignValue(value);
+      return true;
+    } else {
+      return false;
+    }
+  }
 
-  static const size_t kLinearMapSize = 20000;
-  static const size_t kLinearPassCount = 70000;
+  template <typename Map, typename Key>
+  static bool map_delete(Map* map, Key key) {
+    auto iter = map->find(key);
+    if (iter.getValue()) {
+      iter.eraseValue();
+      return true;
+    } else {
+      return false;
+    }
+  }
 
-  static const size_t kLeapfrogMapSize = 20000;
-  static const size_t kLeapfrogPassCount = 75000;
+  template <typename Map, typename Key>
+  static bool map_find(Map* map, Key key) {
+    auto iter = map->find(key);
+    if (iter.getValue()) {
+      return true;
+    } else {
+      return false;
+    }
+  }
 
-  static void SetUpTestCase() {}
+  // Specialization for CrudeMap
+  template <typename Key, typename Value>
+  static bool map_insert(CrudeMap* map, Key key, Value value) {
+    if (!map->get(key)) {
+      map->assign(key, value);
+      return true;
+    } else {
+      return false;
+    }
+  }
 
-  template <typename Map>
-  static void run_test(size_t map_size, size_t pass_count,
-                       size_t gc_frequency) {
-    size_t nInsertedNum = 0;
-    size_t nFindSuccess = 0;
-    size_t nOperations = 0;
-    std::unique_ptr<Map> map(new Map());
-    auto qsbrContext = junction::DefaultQSBR.createContext();
-    for (size_t count = 0; count < pass_count; count++) {
-      for (size_t i = 0; i < map_size; ++i) {
-        // The number to operate on the map.
-        size_t n = map_size + i;
-        // Insert
-        if (i % s_nInsertPercentage == 1) {
-          auto iter = map->insertOrFind(i);
-          if (!iter.getValue()) {
-            iter.assignValue(n);
-            nInsertedNum++;
-            //                  std::cout << "Inserted" << i << "\n";
-          }
-        }
-        // Find
-        {
-          auto iter = map->find(i);
-          if (iter.getValue()) {
-            ++nFindSuccess;
-            //                    std::cout << "Found" << i << "\n";
-          }
-        }
-        // Delete
-        if (i % s_nInsertPercentage == 1) {
-          auto iter = map->find(i);
-          if (iter.getValue()) {
-            iter.eraseValue();
-            //                    std::cout << "Erased" << i << "\n";
-          }
-        }
-        if (++nOperations > gc_frequency) {
-          junction::DefaultQSBR.update(qsbrContext);
-          nOperations = 0;
-        }
-      }
+  template <typename Key> static bool map_delete(CrudeMap* map, Key key) {
+    if (!map->get(key)) {
+      map->assign(key, ((Key)0));
+      return true;
+    } else {
+      return false;
     }
-    junction::DefaultQSBR.update(qsbrContext);
-    junction::DefaultQSBR.destroyContext(qsbrContext);
-    EXPECT_EQ(nFindSuccess, nInsertedNum);
+  }
+
+  template <typename Key> static bool map_find(CrudeMap* map, Key key) {
+    return map->get(key) != ((Key)0);
   }
 
   template <typename Map>
-  void run_crude_map(size_t map_size, size_t pass_count, size_t gc_frequency) {
+  void run_test(Map* map, size_t pass_count) {
+    auto qsbrContext = junction::DefaultQSBR.createContext();
+
+    std::random_device rd;
+    std::mt19937 gen(rd());
+    std::uniform_int_distribution<size_t> dis(kMapSize, 2 * kMapSize);
+
+    unsigned action_index = 0;
     size_t nInsertedNum = 0;
     size_t nFindSuccess = 0;
     size_t nOperations = 0;
-    // Seems like the crude map won't resize, so better have a large enough
-    // capacity.
-    std::unique_ptr<Map> map(new Map(map_size * 32));
-    auto qsbrContext = junction::DefaultQSBR.createContext();
+
     for (size_t count = 0; count < pass_count; count++) {
-      for (size_t i = 0; i < map_size; ++i) {
+      for (size_t i = 0; i < kMapSize; ++i) {
         // The number to operate on the map.
-        size_t n = map_size + i;
-        // Insert
-        if (i % s_nInsertPercentage == 1) {
-          map->assign(i, n);
-          nInsertedNum++;
-          //                std::cout << "Inserted" << i << "\n";
-        }
-        // Find
-        {
-          if (map->get(i)) {
-            ++nFindSuccess;
-            //                    std::cout << "Found" << i << "\n";
+        size_t n = dis(gen);
+        switch (s_arrShuffle[action_index]) {
+          case do_insert: {
+            if (map_insert(map, n, n)) {
+              nInsertedNum++;
+            }
+            break;
           }
-        }
-        // Delete
-        if (i % s_nInsertPercentage == 1) {
-          if (map->get(i)) {
-            map->assign(n, 0);
-            //                    std::cout << "Erased" << i << "\n";
+          case do_delete: {
+            map_delete(map, n);
+            break;
+          }
+          case do_find: {
+            if (map_find(map, n)) {
+              ++nFindSuccess;
+            }
+            break;
           }
+          default: { break; }
         }
-        if (++nOperations > gc_frequency) {
+        if (++action_index >= kShuffleSize) {
+          action_index = 0;
+        }
+        if (++nOperations > kGCFrequency) {
           junction::DefaultQSBR.update(qsbrContext);
           nOperations = 0;
         }
@@ -126,26 +159,33 @@ protected:
     }
     junction::DefaultQSBR.update(qsbrContext);
     junction::DefaultQSBR.destroyContext(qsbrContext);
-
-    EXPECT_EQ(nFindSuccess, nInsertedNum);
   }
 };
 
+const unsigned JunctionMapInsDelFindTest::s_nInsertPercentage;
+const unsigned JunctionMapInsDelFindTest::s_nDeletePercentage;
+const unsigned int JunctionMapInsDelFindTest::kShuffleSize;
+JunctionMapInsDelFindTest::actions JunctionMapInsDelFindTest::s_arrShuffle
+    [JunctionMapInsDelFindTest::kShuffleSize];
+
 TEST_F(JunctionMapInsDelFindTest, JunctionMapCrude) {
-  run_crude_map<CrudeMap>(kCrudeMapSize, kCrudePassCount, kGCFrequency);
+  std::unique_ptr<CrudeMap> map(new CrudeMap(kMapSize * 32));
+  run_test(map.get(), kCrudePassCount);
 }
 
 TEST_F(JunctionMapInsDelFindTest, JunctionMapLeapfrog) {
-  run_test<LeapfrogMap>(kLeapfrogMapSize, kLeapfrogPassCount,
-                        kLeapfrogGCFrequency);
+  std::unique_ptr<LeapfrogMap> map(new LeapfrogMap());
+  run_test(map.get(), kLeapfrogPassCount);
 }
 
 TEST_F(JunctionMapInsDelFindTest, JunctionMapLinear) {
-  run_test<LinearMap>(kLinearMapSize, kLinearPassCount, kGCFrequency);
+  std::unique_ptr<LinearMap> map(new LinearMap());
+  run_test(map.get(), kLinearPassCount);
 }
 
 TEST_F(JunctionMapInsDelFindTest, JunctionMapGrampa) {
-  run_test<GrampaMap>(kGrampaMapSize, kGrampaPassCount, kGCFrequency);
+  std::unique_ptr<GrampaMap> map(new GrampaMap());
+  run_test(map.get(), kGrampaPassCount);
 }
 
 } // namespace junction_test