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

Last change on this file since 1eea589f was 7806f91, checked in by Mike Brooks <mlbrooks@…>, 2 months ago

Add code for reproducing performance numbers in thesis draft of 16a843

  • 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 printf("interleave key %x\n", 0);
180 #else
181 const unsigned int INTRL_KEYLEN = 64;
182 unsigned char interleaveKey[INTRL_KEYLEN];
183 unsigned char nextInterleavePos = 0;
184 {
185 unsigned int numOnes = INTRL_KEYLEN * InterleaveFrac;
186 unsigned int numZeros = INTRL_KEYLEN - numOnes;
187 // generate randomly drawn 0/1
188 memset( interleaveKey , 0, numZeros ); // zeros then ones
189 memset( interleaveKey+numZeros, 1, numOnes );
190 for (unsigned int i = 0; i < 64; i++) { // shuffle it
191 unsigned int nodesRemaining = 64 - i;
192 unsigned int swapWith = i + rand() % nodesRemaining;
193 unsigned char tempValue = interleaveKey[swapWith];
194 interleaveKey[swapWith] = interleaveKey[i];
195 interleaveKey[i] = tempValue;
196 }
197 #define nextInterleave (interleaveKey[nextInterleavePos = (nextInterleavePos + 1) % 64])
198 }
199 {
200 unsigned int z = 0, o = 0;
201 for ( int i = 0; i < INTRL_KEYLEN; i++ ) {
202 if (interleaveKey[i]) o++;
203 else z++;
204 }
205 // printf("Interleaving with %u in middle and %u at end\n", o, z);
206 }
207 // printf("interleave key begins %016llx\n", *(unsigned long long*)interleaveKey);
208 // printf("interleave key begins %016llx\n", *(unsigned long long*)(interleaveKey+8));
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 // printf("sample interleave value %d\n", nextInterleave);
221 #endif
222
223 ui = (B_UserItem*) malloc( (size_t)NumNodes * (size_t)sizeof(B_UserItem) );
224 if (!ui) {
225 printf("malloc request for %zd bytes for ui refused\n", (size_t)NumNodes * (size_t)sizeof(B_UserItem));
226 return 1;
227 }
228 memset(ui, 0, (size_t)NumNodes * (size_t)sizeof(B_UserItem));
229
230 listedItems = (BFX_LISTED_ELEM_T(B_UserItem)*)malloc( (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)) );
231 if (!listedItems) {
232 printf("malloc request for %zd bytes for listedItems refused\n", (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
233 return 1;
234 }
235 memset(listedItems, 0, (size_t)NumNodes * (size_t)sizeof(BFX_LISTED_ELEM_T(B_UserItem)));
236
237 // Construct and fill with demo data
238 for (unsigned int i = 0; i < NumNodes; i++) {
239 B_UserItem * curUI = & ui[INSERTPOS(i)];
240 #ifdef __cforall
241 (*curUI){};
242 #endif
243 curUI->userdata[ UDATA_USE_POS ] = i;
244 }
245
246 BFX_INIT(B_UserItem, lst);
247
248 bobs_init(NumNodes);
249
250 // BOP_ADDFOO(lst, iters, insNo, item)
251 // BOP_REMFOO(lst, iters, remNo)
252 // lst lvalue of the list head being added to / removed from
253 // iters array of ADD return values, in logical-insert order; on ADD, is valid at [0..insNo)
254 // insNo interleave-perterbed counter of the ADD calls (logical insert number)
255 // remNo interleave-perterbed counter of the REM calls (logical remove number)
256 // item lvalue of the item being added
257 // Logical insert number 0 and remove number n-1 are given with a distinguished hook.
258 // Logical insert numbers [1,n) and remove numbers [0,n-1) are pumped by the basic SUT hooks.
259 // This pattern lets BOP cartridges that measure element-level operations know statically when there is a reference element in the list.
260 // The driver owns the relationship between a logical insert number and the location of the `item` argument within `ui`. (Scattered for randomness.)
261 // The BOP cartridge owns the relationship between logical remove number and any choice of an item in iters. (Defines stack vs queue.)
262
263 // Default init/teardown is insert/remove
264 // Cartridges whose SUT insert/remove actions work on empty lists need not provide special-case ones.
265 #ifndef BOP_INIT
266 #define BOP_INIT(lst, iters, insNo, item) BOP_INSERT(lst, iters, insNo, item)
267 #endif
268 #ifndef BOP_TEARDOWN
269 #define BOP_TEARDOWN(lst, iters, remNo) BOP_REMOVE(lst, iters, remNo)
270 #endif
271
272 double elapsed_sec = 0;
273 clock_t start = clock();
274
275 const unsigned int numMiddleNodes = (NumNodes-1) * InterleaveFrac;
276 const unsigned int numEndNodes = NumNodes - numMiddleNodes - 1;
277
278 // printf("Running with %u in the middle and %u at end\n", numMiddleNodes, numEndNodes);
279
280 const unsigned int removeBase[] = {0, numEndNodes};
281 const unsigned int removeLimit[] = {numEndNodes, numMiddleNodes};
282
283 size_t privateOpsCompleted = 0;
284
285 while (elapsed_sec <= (double) ExperimentDurSec && privateOpsCompleted < ExperimentDurOpCount) {
286 for ( int t = 0; t < CheckDonePeriod; t += 1 ) {
287 TRACE('a') // insert special first
288 listedItems[0] =
289 BOP_INIT(lst, listedItems, 0, ui[INSERTPOS(0)]);
290 TRACE('b') // insert general
291 for ( int privateCurInsert = 1;
292 (bobs_prog_inserting = privateCurInsert, privateCurInsert < NumNodes);
293 privateCurInsert += 1
294 ) {
295 TRACE('-')
296 listedItems[privateCurInsert] =
297 BOP_INSERT( lst, listedItems, privateCurInsert, ui[INSERTPOS(privateCurInsert)] );
298 TRACE('+')
299 }
300 TRACE('c') // remove general
301 int removeProgress[] = { 0, 0 };
302 for ( int flip = 0;
303 (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
304 bobs_prog_removing_end = removeProgress[0] + 1,
305 flip = nextInterleave,
306 removeProgress[0] < removeLimit[0] && removeProgress[1] < removeLimit[1] );
307 removeProgress[flip] += 1
308 ) {
309 TRACE('-')
310 BOP_REMOVE( lst, listedItems, removeBase[flip]+removeProgress[flip] );
311 TRACE('+')
312 }
313 TRACE('X') // remove imbalanced
314 // most work done under general; it stops when either flip-side's work finishes
315 // now drain any any stragglers so both flip-sides' work finishes
316 for ( int flip = 0; flip < 2; flip ++ ) {
317 for ( ; (bobs_prog_removing = removeProgress[0] + removeProgress[1] + 1,
318 bobs_prog_removing_end = removeProgress[0] + 1,
319 removeProgress[flip] < removeLimit[flip] )
320 ; removeProgress[flip] += 1
321 ) {
322 TRACE('-')
323 BOP_REMOVE( lst, listedItems, removeBase[flip]+removeProgress[flip] );
324 TRACE('+')
325 }
326 }
327 TRACE('D') // remove special last
328 BOP_TEARDOWN(lst, listedItems, NumNodes-1);
329 TRACE('d')
330
331 privateOpsCompleted += NumNodes;
332
333 bobs_prog_rollover_flag = 1;
334 TRACE('e')
335 bobs_prog_inserting = 0;
336 bobs_prog_removing = 0;
337 bobs_prog_removing_end = 0;
338 bobs_ops_completed = privateOpsCompleted;
339 TRACE('f')
340 bobs_prog_rollover_flag = 0;
341 TRACE('g')
342 }
343 #ifndef DISABLE_CLOCK_RECHECK
344 clock_t end = clock();
345 elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
346 #endif
347 }
348 #ifdef DISABLE_CLOCK_RECHECK
349 {
350 clock_t end = clock();
351 elapsed_sec = ((double)(end - start)) / ((double)CLOCKS_PER_SEC);
352 }
353 #endif
354
355 double mean_op_dur_ns = elapsed_sec / ((double)bobs_ops_completed) * 1000 * 1000 * 1000;
356 printf("%s,%zd,%f,%f\n", argv[0], bobs_ops_completed, elapsed_sec, mean_op_dur_ns);
357
358 free(ui);
359 free(listedItems);
360 #ifndef DISABLE_SHUFFLING_INDIRECTION
361 free(insertOrdShuf);
362 #endif
363}
Note: See TracBrowser for help on using the repository browser.