Delete unused junction/Averager.h
[junction.git] / 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