samples/MapCorrectnessTests/TestChurn.h

   1 /*------------------------------------------------------------------------
   2   Junction: Concurrent data structures in C++
   3   Copyright (c) 2016 Jeff Preshing
   4
   5   Distributed under the Simplified BSD License.
   6   Original location: https://github.com/preshing/junction
   7
   8   This software is distributed WITHOUT ANY WARRANTY; without even the
   9   implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  10   See the LICENSE file for more information.
  11 ------------------------------------------------------------------------*/
  12
  13 #ifndef SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H
  14 #define SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H
  15
  16 #include <junction/Core.h>
  17 #include "TestEnvironment.h"
  18 #include <turf/extra/Random.h>
  19 #include <vector>
  20 #include <turf/Util.h>
  21
  22 class TestChurn {
  23 public:
  24     static const ureg KeysInBlock = 32;
  25     static const ureg BlocksToMaintain = 256;
  26     static const ureg BlocksToLookup = 4;
  27     static const ureg StepsPerIteration = 100;
  28
  29     enum Phase {
  30         Phase_Insert,
  31         Phase_Lookup,
  32         Phase_Erase,
  33         Phase_LookupDeleted,
  34     };
  35
  36     struct ThreadInfo {
  37         turf::extra::Random random;
  38         u32 rangeLo;
  39         u32 rangeHi;
  40         u32 insertIndex;
  41         u32 eraseIndex;
  42         u32 lookupIndex;
  43         Phase phase;
  44         ureg keysToCheck;
  45     };
  46
  47     TestEnvironment& m_env;
  48     MapAdapter::Map m_map;
  49     u32 m_rangePerThread;
  50     u32 m_relativePrime;
  51     std::vector<ThreadInfo> m_threads;
  52
  53     TestChurn(TestEnvironment& env)
  54         : m_env(env), m_map(MapAdapter::getInitialCapacity(KeysInBlock * BlocksToMaintain * env.numThreads)) {
  55         m_threads.resize(m_env.numThreads);
  56         m_rangePerThread = u32(-3) / m_env.numThreads; // from 2 to 0xffffffff inclusive
  57         TURF_ASSERT(KeysInBlock * (BlocksToMaintain + BlocksToLookup + 1) < m_rangePerThread);
  58         u32 startIndex = 2;
  59         for (ureg i = 0; i < m_env.numThreads; i++) {
  60             ThreadInfo& thread = m_threads[i];
  61             thread.rangeLo = startIndex;
  62             startIndex += m_rangePerThread;
  63             thread.rangeHi = startIndex;
  64             thread.insertIndex = thread.rangeLo + thread.random.next32() % m_rangePerThread;
  65             thread.eraseIndex = thread.insertIndex;
  66             thread.lookupIndex = 0;
  67             thread.phase = Phase_Insert;
  68             thread.keysToCheck = 0;
  69         }
  70         m_relativePrime = m_threads[0].random.next32() * 2 + 1;
  71         m_env.dispatcher.kick(&TestChurn::warmUp, *this);
  72     }
  73
  74     void warmUp(ureg threadIndex) {
  75         ThreadInfo& thread = m_threads[threadIndex];
  76         TURF_ASSERT(thread.phase == Phase_Insert);
  77         TURF_ASSERT(thread.insertIndex == thread.eraseIndex);
  78         for (sreg keysRemaining = KeysInBlock * BlocksToMaintain; keysRemaining > 0; keysRemaining--) {
  79             u32 key = thread.insertIndex * m_relativePrime;
  80             key = key ^ (key >> 16);
  81             if (key >= 2) {
  82                 m_map.insert(key, (void*) uptr(key));
  83             }
  84             if (++thread.insertIndex >= thread.rangeHi)
  85                 thread.insertIndex = thread.rangeLo;
  86         }
  87     }
  88
  89     void doChurn(ureg threadIndex) {
  90         ThreadInfo& thread = m_threads[threadIndex];
  91         TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
  92         for (sreg stepsRemaining = StepsPerIteration; stepsRemaining > 0; stepsRemaining--) {
  93             switch (thread.phase) {
  94             case Phase_Insert: {
  95                 for (sreg keysRemaining = KeysInBlock; keysRemaining > 0; keysRemaining--) {
  96                     u32 key = thread.insertIndex * m_relativePrime;
  97                     key = key ^ (key >> 16);
  98                     if (key >= 2) {
  99                         m_map.insert(key, (void*) uptr(key));
 100                     }
 101                     if (++thread.insertIndex >= thread.rangeHi)
 102                         thread.insertIndex = thread.rangeLo;
 103                     TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
 104                 }
 105                 thread.phase = Phase_Lookup;
 106                 thread.lookupIndex = thread.insertIndex;
 107                 thread.keysToCheck = KeysInBlock + (thread.random.next32() % (KeysInBlock * (BlocksToLookup - 1)));
 108                 break;
 109             }
 110             case Phase_Lookup: {
 111                 sreg keysRemaining = turf::util::min(thread.keysToCheck, KeysInBlock);
 112                 thread.keysToCheck -= keysRemaining;
 113                 for (; keysRemaining > 0; keysRemaining--) {
 114                     if (thread.lookupIndex == thread.rangeLo)
 115                         thread.lookupIndex = thread.rangeHi;
 116                     thread.lookupIndex--;
 117                     u32 key = thread.lookupIndex * m_relativePrime;
 118                     key = key ^ (key >> 16);
 119                     if (key >= 2) {
 120                         if (m_map.get(key) != (void*) uptr(key))
 121                             TURF_DEBUG_BREAK();
 122                     }
 123                 }
 124                 if (thread.keysToCheck == 0) {
 125                     thread.phase = Phase_Erase;
 126                 }
 127                 break;
 128             }
 129             case Phase_Erase: {
 130                 for (sreg keysRemaining = KeysInBlock; keysRemaining > 0; keysRemaining--) {
 131                     u32 key = thread.eraseIndex * m_relativePrime;
 132                     key = key ^ (key >> 16);
 133                     if (key >= 2) {
 134                         m_map.erase(key);
 135                     }
 136                     if (++thread.eraseIndex >= thread.rangeHi)
 137                         thread.eraseIndex = thread.rangeLo;
 138                     TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
 139                 }
 140                 thread.phase = Phase_LookupDeleted;
 141                 thread.lookupIndex = thread.eraseIndex;
 142                 thread.keysToCheck = KeysInBlock + (thread.random.next32() % (KeysInBlock * (BlocksToLookup - 1)));
 143                 break;
 144             }
 145             case Phase_LookupDeleted: {
 146                 sreg keysRemaining = turf::util::min(thread.keysToCheck, KeysInBlock);
 147                 thread.keysToCheck -= keysRemaining;
 148                 for (; keysRemaining > 0; keysRemaining--) {
 149                     if (thread.lookupIndex == thread.rangeLo)
 150                         thread.lookupIndex = thread.rangeHi;
 151                     thread.lookupIndex--;
 152                     u32 key = thread.lookupIndex * m_relativePrime;
 153                     key = key ^ (key >> 16);
 154                     if (key >= 2) {
 155                         if (m_map.get(key))
 156                             TURF_DEBUG_BREAK();
 157                     }
 158                 }
 159                 if (thread.keysToCheck == 0) {
 160                     thread.phase = Phase_Insert;
 161                 }
 162                 break;
 163             }
 164             }
 165         }
 166         m_env.threads[threadIndex].update();
 167     }
 168
 169     void run() {
 170         m_env.dispatcher.kick(&TestChurn::doChurn, *this);
 171     }
 172 };
 173
 174 #endif // SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H