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) : m_env(env), m_map(MapAdapter::getInitialCapacity(KeysInBlock * BlocksToMaintain * env.numThreads)) {
  54         m_threads.resize(m_env.numThreads);
  55         m_rangePerThread = u32(-3) / m_env.numThreads;      // from 2 to 0xffffffff inclusive
  56         TURF_ASSERT(KeysInBlock * (BlocksToMaintain + BlocksToLookup + 1) < m_rangePerThread);
  57         u32 startIndex = 2;
  58         for (ureg i = 0; i < m_env.numThreads; i++) {
  59             ThreadInfo& thread = m_threads[i];
  60             thread.rangeLo = startIndex;
  61             startIndex += m_rangePerThread;
  62             thread.rangeHi = startIndex;
  63             thread.insertIndex = thread.rangeLo + thread.random.next32() % m_rangePerThread;
  64             thread.eraseIndex = thread.insertIndex;
  65             thread.lookupIndex = 0;
  66             thread.phase = Phase_Insert;
  67             thread.keysToCheck = 0;
  68         }
  69         m_relativePrime = m_threads[0].random.next32() * 2 + 1;
  70         m_env.dispatcher.kick(&TestChurn::warmUp, *this);
  71     }
  72
  73     void warmUp(ureg threadIndex) {
  74         ThreadInfo& thread = m_threads[threadIndex];
  75         TURF_ASSERT(thread.phase == Phase_Insert);
  76         TURF_ASSERT(thread.insertIndex == thread.eraseIndex);
  77         for (sreg keysRemaining = KeysInBlock * BlocksToMaintain; keysRemaining > 0; keysRemaining--) {
  78             u32 key = thread.insertIndex * m_relativePrime;
  79             key = key ^ (key >> 16);
  80             if (key >= 2) {
  81                 m_map.insert(key, (void*) uptr(key));
  82             }
  83             if (++thread.insertIndex >= thread.rangeHi)
  84                 thread.insertIndex = thread.rangeLo;
  85         }
  86     }
  87
  88     void doChurn(ureg threadIndex) {
  89         ThreadInfo& thread = m_threads[threadIndex];
  90         TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
  91         for (sreg stepsRemaining = StepsPerIteration; stepsRemaining > 0; stepsRemaining--) {
  92             switch (thread.phase) {
  93                 case Phase_Insert: {
  94                     for (sreg keysRemaining = KeysInBlock; keysRemaining > 0; keysRemaining--) {
  95                         u32 key = thread.insertIndex * m_relativePrime;
  96                         key = key ^ (key >> 16);
  97                         if (key >= 2) {
  98                             m_map.insert(key, (void*) uptr(key));
  99                         }
 100                         if (++thread.insertIndex >= thread.rangeHi)
 101                             thread.insertIndex = thread.rangeLo;
 102                         TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
 103                     }
 104                     thread.phase = Phase_Lookup;
 105                     thread.lookupIndex = thread.insertIndex;
 106                     thread.keysToCheck = KeysInBlock + (thread.random.next32() % (KeysInBlock * (BlocksToLookup - 1)));
 107                     break;
 108                 }
 109                 case Phase_Lookup: {
 110                     sreg keysRemaining = turf::util::min(thread.keysToCheck, KeysInBlock);
 111                     thread.keysToCheck -= keysRemaining;
 112                     for (; keysRemaining > 0; keysRemaining--) {
 113                         if (thread.lookupIndex == thread.rangeLo)
 114                             thread.lookupIndex = thread.rangeHi;
 115                         thread.lookupIndex--;
 116                         u32 key = thread.lookupIndex * m_relativePrime;
 117                         key = key ^ (key >> 16);
 118                         if (key >= 2) {
 119                             if (m_map.get(key) != (void*) uptr(key))
 120                                 TURF_DEBUG_BREAK();
 121                         }
 122                     }
 123                     if (thread.keysToCheck == 0) {
 124                         thread.phase = Phase_Erase;
 125                     }
 126                     break;
 127                 }
 128                 case Phase_Erase: {
 129                     for (sreg keysRemaining = KeysInBlock; keysRemaining > 0; keysRemaining--) {
 130                         u32 key = thread.eraseIndex * m_relativePrime;
 131                         key = key ^ (key >> 16);
 132                         if (key >= 2) {
 133                             m_map.erase(key);
 134                         }
 135                         if (++thread.eraseIndex >= thread.rangeHi)
 136                             thread.eraseIndex = thread.rangeLo;
 137                         TURF_ASSERT(thread.insertIndex != thread.eraseIndex);
 138                     }
 139                     thread.phase = Phase_LookupDeleted;
 140                     thread.lookupIndex = thread.eraseIndex;
 141                     thread.keysToCheck = KeysInBlock + (thread.random.next32() % (KeysInBlock * (BlocksToLookup - 1)));
 142                     break;
 143                 }
 144                 case Phase_LookupDeleted: {
 145                     sreg keysRemaining = turf::util::min(thread.keysToCheck, KeysInBlock);
 146                     thread.keysToCheck -= keysRemaining;
 147                     for (; keysRemaining > 0; keysRemaining--) {
 148                         if (thread.lookupIndex == thread.rangeLo)
 149                             thread.lookupIndex = thread.rangeHi;
 150                         thread.lookupIndex--;
 151                         u32 key = thread.lookupIndex * m_relativePrime;
 152                         key = key ^ (key >> 16);
 153                         if (key >= 2) {
 154                             if (m_map.get(key))
 155                                 TURF_DEBUG_BREAK();
 156                         }
 157                     }
 158                     if (thread.keysToCheck == 0) {
 159                         thread.phase = Phase_Insert;
 160                     }
 161                     break;
 162                 }
 163             }
 164         }
 165         m_env.threads[threadIndex].update();
 166     }
 167
 168     void run() {
 169         m_env.dispatcher.kick(&TestChurn::doChurn, *this);
 170     }
 171 };
 172
 173 #endif // SAMPLES_MAPCORRECTNESSTESTS_TESTCHURN_H