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

Last change on this file since 81e1984b was d7a2de1, checked in by Michael Brooks <mlbrooks@…>, 8 weeks ago

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