source: doc/theses/mike_brooks_MMath/benchmarks/list/driver.c@ b9d1242

Last change on this file since b9d1242 was f449d1e, checked in by Michael Brooks <mlbrooks@…>, 2 months ago

Remove stray print from interleave-disabled mode

  • Property mode set to 100644
File size: 14.5 KB
Line 
1#include <time.h>
2#include <stdio.h>
3#include <stdlib.h>
4#include <string.h>
5
6#include "observation.h"
7
8#ifdef TINY_USER_ITEMS
9 #define UDATA_T char
10 #define UDATA_LEN 1
11 #define UDATA_USE_POS 0
12#else
13 #define UDATA_T int
14 #define UDATA_LEN 64
15 #define UDATA_USE_POS 17
16#endif
17
18typedef struct B_UserItem
19 BFX_EXTRUSION_DECL(B_UserItem)
20{
21 BFX_INTRUSION(B_UserItem)
22 UDATA_T userdata[ UDATA_LEN ];
23}
24B_UserItem;
25
26BFX_EXTRUSION_FOLLOWUP(B_UserItem)
27
28#if defined(NDEBUG) || (defined(__cforall) && !defined(__CFA_DEBUG__))
29 enum { DefaultNumNodes = 1000, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 1000, DefaultExperimentDurOpCount = -1, DefaultSeed = 5 };
30 const double DefaultInterleaveFrac = 0.0;
31 #define TRACE(tp)
32#else
33 enum { DefaultNumNodes = 10, DefaultExperimentDurSec = 1, DefaultCheckDonePeriod = 2, DefaultExperimentDurOpCount = 20, DefaultSeed = 5 };
34 const double DefaultInterleaveFrac = 0.5;
35 static const char * tp_filter
36 // = "";
37 // = "+ea";
38 = "*";
39 #define TRACE(tp) \
40 if (strcmp("*", tp_filter) == 0 || strchr(tp_filter, tp)) { \
41 printf("%c", tp); \
42 bobs_report(); \
43 }
44#endif
45
46static B_UserItem *ui = NULL;
47
48static BFX_LISTED_ELEM_T(B_UserItem) *listedItems = NULL;
49static BFX_LISTED_ELEM_T(B_UserItem) observedItem;
50
51static BFX_LIST_HEAD_T(B_UserItem) lst;
52
53MAYBE_EXTERN_C (
54
55 volatile size_t bobs_ops_completed = 0;
56 volatile unsigned int bobs_prog_inserting = 0;
57 volatile unsigned int bobs_prog_removing = 0;
58 volatile unsigned int bobs_prog_removing_end = 0;
59 volatile unsigned int bobs_prog_rollover_flag = 0;
60 // bobs_prog_rem_pos (defined after BOP_REMPROGEND_IS_REMNO_BASED)
61
62 void bobs_seek(unsigned int i) {
63 observedItem = listedItems[i];
64 }
65
66 void bobs_moveNext() {
67 observedItem = BFX_GET_AFTER(B_UserItem, lst, observedItem);
68 }
69
70 void bobs_movePrev() {
71 observedItem = BFX_GET_BEFORE(B_UserItem, lst, observedItem);
72 }
73
74 int bobs_hasCurrent() {
75 return BFX_IS_VALID_POS(B_UserItem, lst, observedItem);
76 }
77
78 void * bobs_getCurrentLoc() {
79 return BFX_DEREF_POS(B_UserItem, lst, observedItem);
80 }
81 int bobs_getCurrentVal() {
82 B_UserItem * curUI = BFX_DEREF_POS(B_UserItem, lst, observedItem);
83 return curUI->userdata[ UDATA_USE_POS ];
84 }
85
86 enum bobs_op_movement_t bobs_op_movement = OP_MOVEMENT;
87 enum bobs_op_polarity_t bobs_op_polarity = OP_POLARITY;
88)
89
90
91// Remove progress end (number) is based (upon) remove-number
92// True when an OP's REMELEM used remNo to choose which element to remove
93// False otherwise; notably including when REMELEM just bases upon first/last
94// Default to false.
95#ifndef BOP_REMPROGEND_IS_REMNO_BASED
96#define BOP_REMPROGEND_IS_REMNO_BASED false
97#endif
98MAYBE_EXTERN_C (
99 volatile unsigned int const * bobs_prog_rem_pos
100 = BOP_REMPROGEND_IS_REMNO_BASED ? & bobs_prog_removing_end : & bobs_prog_removing;
101)
102
103unsigned int uDefaultPreemption() {
104 return 0;
105}
106
107int main(int argc, const char *argv[]) {
108
109 const char * usage_args = "[ExperimentDurSec [CheckDonePeriod [NumNodes [ExperimentDurOpCount [Seed [InterleaveFrac]]]]]]";
110 const int static_arg_posns = 6;
111
112 unsigned int ExperimentDurSec = DefaultExperimentDurSec;
113 unsigned int CheckDonePeriod = DefaultCheckDonePeriod;
114 unsigned int NumNodes = DefaultNumNodes;
115 size_t ExperimentDurOpCount = DefaultExperimentDurOpCount;
116 unsigned int Seed = DefaultSeed;
117 double InterleaveFrac = DefaultInterleaveFrac;
118
119 switch (((argc - 1) < static_arg_posns) ? (argc - 1) : static_arg_posns) {
120 case 6: InterleaveFrac = atof(argv[6]);
121 case 5: Seed = atoi(argv[5]);
122 case 4: ExperimentDurOpCount = atol(argv[4]);
123 case 3: NumNodes = atoi(argv[3]);
124 case 2: CheckDonePeriod = atoi(argv[2]);
125 case 1: ExperimentDurSec = atoi(argv[1]);
126 }
127
128 // printf("ExperimentDurSec=%d, CheckDonePeriod=%d, NumNodes=%d, ExperimentDurOpCount=%zd, Seed=%d,\n",
129 // ExperimentDurSec, CheckDonePeriod, NumNodes, ExperimentDurOpCount, Seed );
130
131 if (ExperimentDurSec == 0 || CheckDonePeriod == 0 || NumNodes == 0 || ExperimentDurOpCount == 0 || Seed == 0 ) {
132 printf("usage: %s %s\n", argv[0], usage_args);
133 return -1;
134 }
135
136 #ifdef DISABLE_CLOCK_RECHECK
137 if (ExperimentDurSec != -1) {
138 printf("Error: experiment compiled as fixed-work only. ExperimentDurSec (currently %d) must be set to -1.\nUsage: %s %s\n", ExperimentDurSec, argv[0], usage_args);
139 return -1;
140 }
141 #endif
142
143 // Shuffling makes listed items' physical order in memory different from their order within to the list.
144 // Affects insertion: next item to insert picked through insertOrdShuf.
145 #ifdef DISABLE_SHUFFLING_INDIRECTION
146 #define INSERTPOS(insertNum) insertNum
147 #else
148 // To ensure random memory order of nodes being inserted, do so according to a shuffled ordering of them.
149 unsigned int * insertOrdShuf = (unsigned int *) malloc( (size_t)NumNodes * sizeof(unsigned int) );
150 if (!insertOrdShuf) {
151 printf("malloc request for %zd bytes for insertOrdShuf refused\n", (size_t)NumNodes * (size_t)sizeof(unsigned int));
152 return 1;
153 }
154 // Fill with the ordinals (iota)
155 for (int i = 0; i < NumNodes; i++) {
156 insertOrdShuf[i] = i;
157 }
158 // Dummy "Seed" of -1 means skip the shuffle: measure overhead of insertOrdShuf indirection
159 if (Seed != -1) {
160 // Shuffle
161 srand(Seed);
162 for (unsigned int i = 0; i < NumNodes; i++) {
163 unsigned int nodesRemaining = NumNodes - i;
164 unsigned int swapWith = i + rand() % nodesRemaining;
165 unsigned int tempValue = insertOrdShuf[swapWith];
166 insertOrdShuf[swapWith] = insertOrdShuf[i];
167 insertOrdShuf[i] = tempValue;
168 }
169 }
170 #define INSERTPOS(insertNum) insertOrdShuf[insertNum]
171 #endif
172
173 // Interleaving affects the list position where an element-oriented operation occurs: at an end vs. in the middle.
174 // Perterbs the sequence of logical insert/remove numbers presented to the OP cartridge, e.g. from [0 1 2 3 4 5 6]
175 // to [3 0 4 1 5 2 6], which is [mid end mid end mid end solo], for a perfect-alternation interleave; except that the
176 // end/mid interleave is atually selected randomly.
177 #ifdef DISABLE_INTERLEAVING
178 #define nextInterleave 0
179 #else
180 const unsigned int INTRL_KEYLEN = 64;
181 unsigned char interleaveKey[INTRL_KEYLEN];
182 unsigned char nextInterleavePos = 0;
183 {
184 unsigned int numOnes = INTRL_KEYLEN * InterleaveFrac;
185 unsigned int numZeros = INTRL_KEYLEN - numOnes;
186 // generate randomly drawn 0/1
187 memset( interleaveKey , 0, numZeros ); // zeros then ones
188 memset( interleaveKey+numZeros, 1, numOnes );
189 for (unsigned int i = 0; i < 64; i++) { // shuffle it
190 unsigned int nodesRemaining = 64 - i;
191 unsigned int swapWith = i + rand() % nodesRemaining;
192 unsigned char tempValue = interleaveKey[swapWith];
193 interleaveKey[swapWith] = interleaveKey[i];
194 interleaveKey[i] = tempValue;
195 }
196 #define nextInterleave (interleaveKey[nextInterleavePos = (nextInterleavePos + 1) % 64])
197 }
198 {
199 unsigned int z = 0, o = 0;
200 for ( int i = 0; i < INTRL_KEYLEN; i++ ) {
201 if (interleaveKey[i]) o++;
202 else z++;
203 }
204 // printf("Interleaving with %u in middle and %u at end\n", o, z);
205 }
206 // printf("interleave key begins %016llx\n", *(unsigned long long*)interleaveKey);
207 // printf("interleave key begins %016llx\n", *(unsigned long long*)(interleaveKey+8));
208 // printf("sample interleave value %d\n", nextInterleave);
209 // printf("sample interleave value %d\n", nextInterleave);
210 // printf("sample interleave value %d\n", nextInterleave);
211 // printf("sample interleave value %d\n", nextInterleave);
212 // printf("sample interleave value %d\n", nextInterleave);
213 // printf("sample interleave value %d\n", nextInterleave);
214 // printf("sample interleave value %d\n", nextInterleave);
215 // printf("sample interleave value %d\n", nextInterleave);
216 // printf("sample interleave value %d\n", nextInterleave);
217 // printf("sample interleave value %d\n", nextInterleave);
218 // printf("sample interleave value %d\n", nextInterleave);
219 // printf("sample interleave value %d\n", nextInterleave);
220 #endif
221
222 ui = (B_UserItem*) malloc( (size_t)NumNodes * (size_t)sizeof(B_UserItem) );
223 if (!ui) {
224 printf("malloc request for %zd bytes for ui refused\n", (size_t)NumNodes * (size_t)sizeof(B_UserItem));
225 return 1;
226 }
227 memset(ui, 0, (size_t)NumNodes * (size_t)sizeof(B_UserItem));
228
229 listedItems = (BFX_LISTED_ELEM_T(B_UserItem)*)malloc( (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)) );
230 if (!listedItems) {
231 printf("malloc request for %zd bytes for listedItems refused\n", (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
232 return 1;
233 }
234 memset(listedItems, 0, (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
235
236 // Construct and fill with demo data
237 for (unsigned int i = 0; i < NumNodes; i++) {
238 B_UserItem * curUI = & ui[INSERTPOS(i)];
239 #ifdef __cforall
240 (*curUI){};
241 #endif
242 curUI->userdata[ UDATA_USE_POS ] = i;
243 }
244
245 BFX_INIT(B_UserItem, lst);
246
247 bobs_init(NumNodes);
248
249 // BOP_ADDFOO(lst, iters, insNo, item)
250 // BOP_REMFOO(lst, iters, remNo)
251 // lst lvalue of the list head being added to / removed from
252 // iters array of ADD return values, in logical-insert order; on ADD, is valid at [0..insNo)
253 // insNo interleave-perterbed counter of the ADD calls (logical insert number)
254 // remNo interleave-perterbed counter of the REM calls (logical remove number)
255 // item lvalue of the item being added
256 // Logical insert number 0 and remove number n-1 are given with a distinguished hook.
257 // Logical insert numbers [1,n) and remove numbers [0,n-1) are pumped by the basic SUT hooks.
258 // This pattern lets BOP cartridges that measure element-level operations know statically when there is a reference element in the list.
259 // The driver owns the relationship between a logical insert number and the location of the `item` argument within `ui`. (Scattered for randomness.)
260 // The BOP cartridge owns the relationship between logical remove number and any choice of an item in iters. (Defines stack vs queue.)
261
262 // Default init/teardown is insert/remove
263 // Cartridges whose SUT insert/remove actions work on empty lists need not provide special-case ones.
264 #ifndef BOP_INIT
265 #define BOP_INIT(lst, iters, insNo, item) BOP_INSERT(lst, iters, insNo, item)
266 #endif
267 #ifndef BOP_TEARDOWN
268 #define BOP_TEARDOWN(lst, iters, remNo) BOP_REMOVE(lst, iters, remNo)
269 #endif
270
271 double elapsed_sec = 0;
272 clock_t start = clock();
273
274 const unsigned int numMiddleNodes = (NumNodes-1) * InterleaveFrac;
275 const unsigned int numEndNodes = NumNodes - numMiddleNodes - 1;
276
277 // printf("Running with %u in the middle and %u at end\n", numMiddleNodes, numEndNodes);
278
279 const unsigned int removeBase[] = {0, numEndNodes};
280 const unsigned int removeLimit[] = {numEndNodes, numMiddleNodes};
281
282 size_t privateOpsCompleted = 0;
283
284 while (elapsed_sec <= (double) ExperimentDurSec && privateOpsCompleted < ExperimentDurOpCount) {
285 for ( int t = 0; t < CheckDonePeriod; t += 1 ) {
286 TRACE('a') // insert special first
287 listedItems[0] =
288 BOP_INIT(lst, listedItems, 0, ui[INSERTPOS(0)]);
289 TRACE('b') // insert general
290 for ( int privateCurInsert = 1;
291 (bobs_prog_inserting = privateCurInsert, privateCurInsert < NumNodes);
292 privateCurInsert += 1
293 ) {
294 TRACE('-')
295 listedItems[privateCurInsert] =
296 BOP_INSERT( lst, listedItems, privateCurInsert, ui[INSERTPOS(privateCurInsert)] );
297 TRACE('+')
298 }
299 TRACE('c') // remove general
300 int removeProgress[] = { 0, 0 };
301 for ( int flip = 0;
302 (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
303 bobs_prog_removing_end = removeProgress[0] + 1,
304 flip = nextInterleave,
305 removeProgress[0] < removeLimit[0] && removeProgress[1] < removeLimit[1] );
306 removeProgress[flip] += 1
307 ) {
308 TRACE('-')
309 BOP_REMOVE( lst, listedItems, removeBase[flip]+removeProgress[flip] );
310 TRACE('+')
311 }
312 TRACE('X') // remove imbalanced
313 // most work done under general; it stops when either flip-side's work finishes
314 // now drain any any stragglers so both flip-sides' work finishes
315 for ( int flip = 0; flip < 2; flip ++ ) {
316 for ( ; (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
317 bobs_prog_removing_end = removeProgress[0] + 1,
318 removeProgress[flip] < removeLimit[flip] )
319 ; removeProgress[flip] += 1
320 ) {
321 TRACE('-')
322 BOP_REMOVE( lst, listedItems, removeBase[flip]+removeProgress[flip] );
323 TRACE('+')
324 }
325 }
326 TRACE('D') // remove special last
327 BOP_TEARDOWN(lst, listedItems, NumNodes-1);
328 TRACE('d')
329
330 privateOpsCompleted += NumNodes;
331
332 bobs_prog_rollover_flag = 1;
333 TRACE('e')
334 bobs_prog_inserting = 0;
335 bobs_prog_removing = 0;
336 bobs_prog_removing_end = 0;
337 bobs_ops_completed = privateOpsCompleted;
338 TRACE('f')
339 bobs_prog_rollover_flag = 0;
340 TRACE('g')
341 }
342 #ifndef DISABLE_CLOCK_RECHECK
343 clock_t end = clock();
344 elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
345 #endif
346 }
347 #ifdef DISABLE_CLOCK_RECHECK
348 {
349 clock_t end = clock();
350 elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
351 }
352 #endif
353
354 double mean_op_dur_ns = elapsed_sec / ((double)bobs_ops_completed) * 1000 * 1000 * 1000;
355 printf("%s,%zd,%f,%f\n", argv[0], bobs_ops_completed, elapsed_sec, mean_op_dur_ns);
356
357 free(ui);
358 free(listedItems);
359 #ifndef DISABLE_SHUFFLING_INDIRECTION
360 free(insertOrdShuf);
361 #endif
362}
Note: See TracBrowser for help on using the repository browser.