Debian Codegraph @

scripts/probe_perf/bench.c

raw
1 # include <sys/types.h>
2 # include <sys/time.h>
3 # include <sys/times.h>
4 # include <memory.h>
5 # include <stdio.h>
6 # include <stdlib.h>
7 # include "bench_.h"
8
9 #define nil 0
10 #define false 0
11 #define true 1
12 #define bubblebase 1.61
13 #define dnfbase 3.5
14 #define permbase 1.75
15 #define queensbase 1.83
16 #define towersbase 2.39
17 #define quickbase 1.92
18 #define intmmbase 1.46
19 #define treebase 2.5
20 #define mmbase 0.0
21 #define fpmmbase 2.92
22 #define puzzlebase 0.5
23 #define fftbase 0.0
24 #define fpfftbase 4.44
25
26 /* Towers */
27 #define maxcells 18
28
29 /* Intmm, Mm */
30 #define rowsize 40
31
32 /* Puzzle */
33 #define SIZE 511
34 #define classmax 3
35 #define typemax 12
36 #define d 8
37
38 /* Bubble, Quick */
39 #define sortelements 5000
40 #define srtelements 500
41
42 /* fft */
43 #define fftsize 256
44 #define fftsize2 129
45
46 /* Perm */
47 #define permrange 10
48
49 /* tree */
50 struct node
51 {
52 struct node *left, *right;
53 int val;
54 };
55
56 /* Towers */
57 #define stackrange 3
58
59 struct element
60 {
61 int discsize;
62 int next;
63 };
64
65 /* FFT */
66 struct complex
67 {
68 float rp, ip;
69 };
70
71 float value;
72 float fixed, floated;
73
74 /* global */
75 int seed;
76
77 #define CYCLES_HBOUND 1000
78 long cycles_start;
79 long permute_cycles_idx;
80 long permute_cycles_avg;
81 long (*permute_cycles) [CYCLES_HBOUND];
82 long tower_cycles_idx;
83 long tower_cycles_avg;
84 long (*tower_cycles) [CYCLES_HBOUND];
85 long try_cycles_idx;
86 long try_cycles_avg;
87 long (*try_cycles) [CYCLES_HBOUND];
88 long innerproduct_cycles_idx;
89 long innerproduct_cycles_avg;
90 long (*innerproduct_cycles) [CYCLES_HBOUND];
91 long trial_cycles_idx;
92 long trial_cycles_avg;
93 long (*trial_cycles) [CYCLES_HBOUND];
94 long quicksort_cycles_idx;
95 long quicksort_cycles_avg;
96 long (*quicksort_cycles) [CYCLES_HBOUND];
97 long insert_cycles_idx;
98 long insert_cycles_avg;
99 long (*insert_cycles) [CYCLES_HBOUND];
100 long bubble_cycles_idx;
101 long bubble_cycles_avg;
102 long (*bubble_cycles) [CYCLES_HBOUND];
103 long fft_cycles_idx;
104 long fft_cycles_avg;
105 long (*fft_cycles) [CYCLES_HBOUND];
106
107 /* Perm */
108 int permarray[permrange + 1];
109 int pctr;
110
111 /* tree */
112 struct node *tree;
113
114 /* Towers */
115 int stack[stackrange + 1];
116 struct element cellspace[maxcells + 1];
117 int freelist, movesdone;
118
119 /* Intmm, Mm */
120 int ima[rowsize + 1][rowsize + 1], imb[rowsize + 1][rowsize + 1],
121 imr[rowsize + 1][rowsize + 1];
122 float rma[rowsize + 1][rowsize + 1], rmb[rowsize + 1][rowsize + 1],
123 rmr[rowsize + 1][rowsize + 1];
124
125 /* Puzzle */
126 int piececount[classmax + 1],
127 class[typemax + 1],
128 piecemax[typemax + 1], puzzl[SIZE + 1], p[typemax + 1][SIZE + 1], n, kount;
129
130 /* Bubble, Quick */
131 int sortlist[sortelements + 1], biggest, littlest, top;
132
133 /* FFT */
134 struct complex z[fftsize + 1], w[fftsize + 1], e[fftsize2 + 1];
135 float zr, zi;
136
137 /* global procedures */
138
139 long rdtsc(void) __attribute__ ((__noinline__));
140 long rdtsc(void)
141 {
142 // XXX this only works on x86_64
143 // -- not i386 because the long result is only 32-bit
144 // -- not other archs because they need other asm
145 #if defined __x86_64__
146 int res[2];
147
148 __asm__ __volatile__ ("xorl %%eax,%%eax \n push %%rbx \n cpuid \n"
149 ::: "%rax", "%rcx", "%rdx");
150 // read TSC, store edx:eax in res
151 __asm__ __volatile__ ("rdtsc\n"
152 : "=a" (res[0]), "=d" (res[1]) );
153 __asm__ __volatile__ ("xorl %%eax,%%eax \n cpuid \n pop %%rbx \n"
154 ::: "%rax", "%rcx", "%rdx");
155
156 return *(long*)res;
157 #else
158 return 0;
159 #endif
160 }
161
162 Initrand ()
163 {
164 seed = 74755;
165 }
166
167 int
168 Rand ()
169 {
170 seed = (seed * 1309 + 13849) & 65535;
171 return (seed);
172 }
173
174 /* Permutation program, heavily recursive, written by Denny Brown. */
175
176 Swap (a, b)
177 int *a, *b;
178 {
179 int t;
180 t = *a;
181 *a = *b;
182 *b = t;
183 }
184
185 Initialize ()
186 {
187 int i;
188 for (i = 1; i <= 7; i++)
189 {
190 permarray[i] = i - 1;
191 };
192 }
193
194 Permute (n)
195 int n;
196 {
197 int k;
198 pctr = pctr + 1;
199 if (n != 1)
200 {
201 Permute (n - 1);
202 for (k = n - 1; k >= 1; k--)
203 {
204 cycles_start = rdtsc();
205 #ifndef NO_STAP_SDT
206 BENCH_PERMUTE (cycles_start,k);
207 #else
208 BENCH_PERMUTE:
209 #endif
210 if (__builtin_expect(permute_cycles_idx != CYCLES_HBOUND,0))
211 {
212 permute_cycles_idx++;
213 (*permute_cycles)[permute_cycles_idx] = rdtsc() - cycles_start;
214 }
215 Swap (&permarray[n], &permarray[k]);
216 Permute (n - 1);
217 Swap (&permarray[n], &permarray[k]);
218 };
219 };
220 }
221
222 Perm ()
223 {
224 int i;
225 pctr = 0;
226 for (i = 1; i <= 5; i++)
227 {
228 Initialize ();
229 Permute (7);
230 };
231 if (pctr != 43300)
232 printf (" Error in Perm.\n");
233 }
234
235
236 /* Program to Solve the Towers of Hanoi */
237
238 Error (emsg)
239 char *emsg;
240 {
241 printf (" Error in Towers: %s\n", emsg);
242 }
243
244 Makenull (s)
245 {
246 stack[s] = 0;
247 }
248
249 int
250 Getelement ()
251 {
252 int temp;
253 if (freelist > 0)
254 {
255 temp = freelist;
256 freelist = cellspace[freelist].next;
257 }
258 else
259 Error ("out of space ");
260 return (temp);
261 }
262
263 Push (i, s)
264 int i, s;
265 {
266 int errorfound, localel;
267 errorfound = false;
268 if (stack[s] > 0)
269 if (cellspace[stack[s]].discsize <= i)
270 {
271 errorfound = true;
272 Error ("disc size error");
273 };
274 if (!errorfound)
275 {
276 localel = Getelement ();
277 cellspace[localel].next = stack[s];
278 stack[s] = localel;
279 cellspace[localel].discsize = i;
280 }
281 }
282
283 Init (s, n)
284 int s, n;
285 {
286 int discctr;
287 Makenull (s);
288 for (discctr = n; discctr >= 1; discctr--)
289 Push (discctr, s);
290 }
291
292 int
293 Pop (s)
294 int s;
295 {
296 int temp, temp1;
297 if (stack[s] > 0)
298 {
299 temp1 = cellspace[stack[s]].discsize;
300 temp = cellspace[stack[s]].next;
301 cellspace[stack[s]].next = freelist;
302 freelist = stack[s];
303 stack[s] = temp;
304 return (temp1);
305 }
306 else
307 Error ("nothing to pop ");
308 }
309
310 Move (s1, s2)
311 int s1, s2;
312 {
313 Push (Pop (s1), s2);
314 movesdone = movesdone + 1;
315 }
316
317 tower (i, j, k)
318 int i, j, k;
319 {
320 int other;
321 cycles_start = rdtsc();
322 #ifndef NO_STAP_SDT
323 BENCH_TOWER (cycles_start,i, j, k);
324 #else
325 BENCH_TOWER:
326 #endif
327 if (__builtin_expect(tower_cycles_idx != CYCLES_HBOUND,0))
328 {
329 tower_cycles_idx++;
330 (*tower_cycles)[tower_cycles_idx] = rdtsc() - cycles_start;
331 }
332 if (k == 1)
333 Move (i, j);
334 else
335 {
336 other = 6 - i - j;
337 tower (i, other, k - 1);
338 Move (i, j);
339 tower (other, j, k - 1);
340 }
341 }
342
343
344 Towers ()
345 {
346 int i;
347 for (i = 1; i <= maxcells; i++)
348 cellspace[i].next = i - 1;
349 freelist = maxcells;
350 Init (1, 14);
351 Makenull (2);
352 Makenull (3);
353 movesdone = 0;
354 tower (1, 2, 14);
355 if (movesdone != 16383)
356 printf (" Error in Towers.\n");
357 }
358
359
360 /* The eight queens problem, solved 50 times. */
361 /*
362 type
363 doubleboard = 2..16;
364 doublenorm = -7..7;
365 boardrange = 1..8;
366 aarray = array [boardrange] of boolean;
367 barray = array [doubleboard] of boolean;
368 carray = array [doublenorm] of boolean;
369 xarray = array [boardrange] of boardrange;
370 */
371
372 Try (i, q, a, b, c, x)
373 int i, *q, a[], b[], c[], x[];
374 {
375 int j;
376 j = 0;
377 *q = false;
378 while ((!*q) && (j != 8))
379 {
380 j = j + 1;
381 cycles_start = rdtsc();
382 #ifndef NO_STAP_SDT
383 BENCH_TRY (cycles_start,i, q, a, b, c, x);
384 #else
385 BENCH_TRY:
386 #endif
387 if (__builtin_expect(try_cycles_idx != CYCLES_HBOUND,0))
388 {
389 try_cycles_idx++;
390 (*try_cycles)[try_cycles_idx] = rdtsc() - cycles_start;
391 }
392 *q = false;
393 if (b[j] && a[i + j] && c[i - j + 7])
394 {
395 x[i] = j;
396 b[j] = false;
397 a[i + j] = false;
398 c[i - j + 7] = false;
399 if (i < 8)
400 {
401 Try (i + 1, q, a, b, c, x);
402 if (!*q)
403 {
404 b[j] = true;
405 a[i + j] = true;
406 c[i - j + 7] = true;
407 }
408 }
409 else
410 *q = true;
411 }
412 }
413 }
414
415 Doit ()
416 {
417 int i, q;
418 int a[9], b[17], c[15], x[9];
419 i = 0 - 7;
420 while (i <= 16)
421 {
422 if ((i >= 1) && (i <= 8))
423 a[i] = true;
424 if (i >= 2)
425 b[i] = true;
426 if (i <= 7)
427 c[i + 7] = true;
428 i = i + 1;
429 }
430
431 Try (1, &q, b, a, c, x);
432 if (!q)
433 printf (" Error in Queens.\n");
434 }
435
436 Queens ()
437 {
438 int i;
439 for (i = 1; i <= 50; i++)
440 Doit ();
441 }
442
443 /* Multiplies two integer matrices. */
444
445 Initmatrix (m)
446 int m[rowsize + 1][rowsize + 1];
447 {
448 int temp, i, j;
449 for (i = 1; i <= rowsize; i++)
450 for (j = 1; j <= rowsize; j++)
451 temp = Rand ();
452 m[i][j] = temp - (temp / 120) * 120 - 60;
453 }
454
455 Innerproduct (result, a, b, row, column)
456 int *result, a[rowsize + 1][rowsize + 1], b[rowsize + 1][rowsize + 1],
457 row, column;
458 {
459 int i;
460 *result = 0;
461 for (i = 1; i <= rowsize; i++)
462 {
463 cycles_start = rdtsc();
464 #ifndef NO_STAP_SDT
465 BENCH_INNERPRODUCT (cycles_start,a, b, row, column);
466 #else
467 BENCH_INNERPRODUCT:
468 #endif
469 if (__builtin_expect(innerproduct_cycles_idx != CYCLES_HBOUND,0))
470 {
471 innerproduct_cycles_idx++;
472 (*innerproduct_cycles)[innerproduct_cycles_idx] = rdtsc() - cycles_start;
473 }
474 *result = *result + a[row][i] * b[i][column];
475 }
476
477 }
478
479 Intmm ()
480 {
481 int i, j;
482 Initrand ();
483 Initmatrix (ima);
484 Initmatrix (imb);
485 for (i = 1; i <= rowsize; i++)
486 for (j = 1; j <= rowsize; j++)
487 Innerproduct (&imr[i][j], ima, imb, i, j);
488 }
489
490
491 /* Multiplies two real matrices. */
492
493 rInitmatrix (m)
494 float m[rowsize + 1][rowsize + 1];
495 {
496 int temp, i, j;
497 for (i = 1; i <= rowsize; i++)
498 for (j = 1; j <= rowsize; j++)
499 temp = Rand ();
500 m[i][j] = (temp - (temp / 120) * 120 - 60) / 3;
501 }
502
503 rInnerproduct (result, a, b, row, column)
504 float *result, a[rowsize + 1][rowsize + 1], b[rowsize + 1][rowsize + 1];
505 int row, column;
506 {
507 int i;
508 *result = 0.0;
509 for (i = 1; i <= rowsize; i++)
510 *result = *result + a[row][i] * b[i][column];
511 }
512
513 Mm ()
514 {
515 int i, j;
516 Initrand ();
517 rInitmatrix (rma);
518 rInitmatrix (rmb);
519 for (i = 1; i <= rowsize; i++)
520 for (j = 1; j <= rowsize; j++)
521 rInnerproduct (&rmr[i][j], rma, rmb, i, j);
522 }
523
524
525 int
526 Fit (i, j)
527 int i, j;
528 {
529 int k;
530 for (k = 0; k <= piecemax[i]; k++)
531 if (p[i][k])
532 if (puzzl[j + k])
533 return (false);
534 return (true);
535 }
536
537 int
538 Place (i, j)
539 int i, j;
540 {
541 int k;
542 for (k = 0; k <= piecemax[i]; k++)
543 if (p[i][k])
544 puzzl[j + k] = true;
545 piececount[class[i]] = piececount[class[i]] - 1;
546 for (k = j; k <= SIZE; k++)
547 if (!puzzl[k])
548 {
549 return (k);
550 }
551 return (0);
552 }
553
554 Remove (i, j)
555 int i, j;
556 {
557 int k;
558 for (k = 0; k <= piecemax[i]; k++)
559 if (p[i][k])
560 puzzl[j + k] = false;
561 piececount[class[i]] = piececount[class[i]] + 1;
562 }
563
564 int
565 Trial (j)
566 int j;
567 {
568 int i, k;
569 kount = kount + 1;
570 for (i = 0; i <= typemax; i++)
571 {
572 if (piececount[class[i]] != 0)
573 if (Fit (i, j))
574 {
575 k = Place (i, j);
576 cycles_start = rdtsc();
577 #ifndef NO_STAP_SDT
578 BENCH_TRIAL (cycles_start,i, j, k);
579 #else
580 BENCH_TRIAL:
581 #endif
582 if (__builtin_expect(trial_cycles_idx != CYCLES_HBOUND,0))
583 {
584 trial_cycles_idx++;
585 (*trial_cycles)[trial_cycles_idx] = rdtsc() - cycles_start;
586 }
587 if (Trial (k) || (k == 0))
588 {
589 return (true);
590 }
591 else
592 Remove (i, j);
593 }
594 }
595 return (false);
596 }
597
598 Puzzle ()
599 {
600 int i, j, k, m;
601 for (m = 0; m <= SIZE; m++)
602 puzzl[m] = true;
603 for (i = 1; i <= 5; i++)
604 for (j = 1; j <= 5; j++)
605 for (k = 1; k <= 5; k++)
606 puzzl[i + d * (j + d * k)] = false;
607 for (i = 0; i <= typemax; i++)
608 for (m = 0; m <= SIZE; m++)
609 p[i][m] = false;
610 for (i = 0; i <= 3; i++)
611 for (j = 0; j <= 1; j++)
612 for (k = 0; k <= 0; k++)
613 p[0][i + d * (j + d * k)] = true;
614 class[0] = 0;
615 piecemax[0] = 3 + d * 1 + d * d * 0;
616 for (i = 0; i <= 1; i++)
617 for (j = 0; j <= 0; j++)
618 for (k = 0; k <= 3; k++)
619 p[1][i + d * (j + d * k)] = true;
620 class[1] = 0;
621 piecemax[1] = 1 + d * 0 + d * d * 3;
622 for (i = 0; i <= 0; i++)
623 for (j = 0; j <= 3; j++)
624 for (k = 0; k <= 1; k++)
625 p[2][i + d * (j + d * k)] = true;
626 class[2] = 0;
627 piecemax[2] = 0 + d * 3 + d * d * 1;
628 for (i = 0; i <= 1; i++)
629 for (j = 0; j <= 3; j++)
630 for (k = 0; k <= 0; k++)
631 p[3][i + d * (j + d * k)] = true;
632 class[3] = 0;
633 piecemax[3] = 1 + d * 3 + d * d * 0;
634 for (i = 0; i <= 3; i++)
635 for (j = 0; j <= 0; j++)
636 for (k = 0; k <= 1; k++)
637 p[4][i + d * (j + d * k)] = true;
638 class[4] = 0;
639 piecemax[4] = 3 + d * 0 + d * d * 1;
640 for (i = 0; i <= 0; i++)
641 for (j = 0; j <= 1; j++)
642 for (k = 0; k <= 3; k++)
643 p[5][i + d * (j + d * k)] = true;
644 class[5] = 0;
645 piecemax[5] = 0 + d * 1 + d * d * 3;
646 for (i = 0; i <= 2; i++)
647 for (j = 0; j <= 0; j++)
648 for (k = 0; k <= 0; k++)
649 p[6][i + d * (j + d * k)] = true;
650 class[6] = 1;
651 piecemax[6] = 2 + d * 0 + d * d * 0;
652 for (i = 0; i <= 0; i++)
653 for (j = 0; j <= 2; j++)
654 for (k = 0; k <= 0; k++)
655 p[7][i + d * (j + d * k)] = true;
656 class[7] = 1;
657 piecemax[7] = 0 + d * 2 + d * d * 0;
658 for (i = 0; i <= 0; i++)
659 for (j = 0; j <= 0; j++)
660 for (k = 0; k <= 2; k++)
661 p[8][i + d * (j + d * k)] = true;
662 class[8] = 1;
663 piecemax[8] = 0 + d * 0 + d * d * 2;
664 for (i = 0; i <= 1; i++)
665 for (j = 0; j <= 1; j++)
666 for (k = 0; k <= 0; k++)
667 p[9][i + d * (j + d * k)] = true;
668 class[9] = 2;
669 piecemax[9] = 1 + d * 1 + d * d * 0;
670 for (i = 0; i <= 1; i++)
671 for (j = 0; j <= 0; j++)
672 for (k = 0; k <= 1; k++)
673 p[10][i + d * (j + d * k)] = true;
674 class[10] = 2;
675 piecemax[10] = 1 + d * 0 + d * d * 1;
676 for (i = 0; i <= 0; i++)
677 for (j = 0; j <= 1; j++)
678 for (k = 0; k <= 1; k++)
679 p[11][i + d * (j + d * k)] = true;
680 class[11] = 2;
681 piecemax[11] = 0 + d * 1 + d * d * 1;
682 for (i = 0; i <= 1; i++)
683 for (j = 0; j <= 1; j++)
684 for (k = 0; k <= 1; k++)
685 p[12][i + d * (j + d * k)] = true;
686 class[12] = 3;
687 piecemax[12] = 1 + d * 1 + d * d * 1;
688 piececount[0] = 13;
689 piececount[1] = 3;
690 piececount[2] = 1;
691 piececount[3] = 1;
692 m = 1 + d * (1 + d * 1);
693 kount = 0;
694 if (Fit (0, m))
695 n = Place (0, m);
696 else
697 printf ("Error1 in Puzzle\n");
698 if (!Trial (n))
699 printf ("Error2 in Puzzle.\n");
700 else if (kount != 2005)
701 printf ("Error3 in Puzzle.\n");
702 }
703
704 /* Sorts an array using quicksort */
705
706 Initarr ()
707 {
708 int i, temp;
709 Initrand ();
710 biggest = 0;
711 littlest = 0;
712 for (i = 1; i <= sortelements; i++)
713 {
714 temp = Rand ();
715 sortlist[i] = temp - (temp / 100000) * 100000 - 50000;
716 if (sortlist[i] > biggest)
717 biggest = sortlist[i];
718 else if (sortlist[i] < littlest)
719 littlest = sortlist[i];
720 }
721 }
722
723 Quicksort (a, l, r)
724 int a[], l, r;
725 {
726 int i, j, x, w;
727
728 i = l;
729 j = r;
730 x = a[(l + r) / 2];
731 do
732 {
733 while (a[i] < x)
734 i = i + 1;
735 while (x < a[j])
736 j = j - 1;
737 cycles_start = rdtsc();
738 #ifndef NO_STAP_SDT
739 BENCH_QUICKSORT (cycles_start,i, j, x);
740 #else
741 BENCH_QUICKSORT:
742 #endif
743 if (__builtin_expect(quicksort_cycles_idx != CYCLES_HBOUND,0))
744 {
745 quicksort_cycles_idx++;
746 (*quicksort_cycles)[quicksort_cycles_idx] = rdtsc() - cycles_start;
747 }
748 if (i <= j)
749 {
750 w = a[i];
751 a[i] = a[j];
752 a[j] = w;
753 i = i + 1;
754 j = j - 1;
755 }
756 }
757 while (i <= j);
758 if (l < j)
759 Quicksort (a, l, j);
760 if (i < r)
761 Quicksort (a, i, r);
762 }
763
764
765 Quick ()
766 {
767 Initarr ();
768 Quicksort (sortlist, 1, sortelements);
769 if ((sortlist[1] != littlest) || (sortlist[sortelements] != biggest))
770 printf (" Error in Quick.\n");
771 }
772
773
774 tInitarr ()
775 {
776 int i, temp;
777 Initrand ();
778 biggest = 0;
779 littlest = 0;
780 for (i = 1; i <= sortelements; i++)
781 {
782 temp = Rand ();
783 sortlist[i] = temp - (temp / 100000) * 100000 - 50000;
784 if (sortlist[i] > biggest)
785 biggest = sortlist[i];
786 else if (sortlist[i] < littlest)
787 littlest = sortlist[i];
788 }
789 }
790
791 CreateNode (t, n)
792 struct node **t;
793 int n;
794 {
795 *t = (struct node *) malloc (sizeof (struct node));
796 (*t)->left = nil;
797 (*t)->right = nil;
798 (*t)->val = n;
799 }
800
801 Insert (n, t)
802 int n;
803 struct node *t;
804 {
805 cycles_start = rdtsc();
806 #ifndef NO_STAP_SDT
807 BENCH_INSERT (cycles_start,n, t);
808 #else
809 BENCH_INSERT:
810 #endif
811 if (__builtin_expect(insert_cycles_idx != CYCLES_HBOUND,0))
812 {
813 insert_cycles_idx++;
814 (*insert_cycles)[insert_cycles_idx] = rdtsc() - cycles_start;
815 }
816 if (n > t->val)
817 if (t->left == nil)
818 CreateNode (&t->left, n);
819 else
820 Insert (n, t->left);
821 else if (n < t->val)
822 if (t->right == nil)
823 CreateNode (&t->right, n);
824 else
825 Insert (n, t->right);
826 }
827
828 int
829 Checktree (p)
830 struct node *p;
831 {
832 int result;
833 result = true;
834 if (p->left != nil)
835 if (p->left->val <= p->val)
836 result = false;
837 else
838 result = Checktree (p->left) && result;
839 if (p->right != nil)
840 if (p->right->val >= p->val)
841 result = false;
842 else
843 result = Checktree (p->right) && result;
844 return (result);
845 }
846
847 Trees ()
848 {
849 int i;
850 tInitarr ();
851 tree = (struct node *) malloc (sizeof (struct node));
852 tree->left = nil;
853 tree->right = nil;
854 tree->val = sortlist[1];
855 for (i = 2; i <= sortelements; i++)
856 Insert (sortlist[i], tree);
857 if (!Checktree (tree))
858 printf (" Error in Tree.\n");
859 }
860
861
862 /* Sorts an array using bubblesort */
863
864 bInitarr ()
865 {
866 int i, temp;
867 Initrand ();
868 biggest = 0;
869 littlest = 0;
870 for (i = 1; i <= srtelements; i++)
871 {
872 temp = Rand ();
873 sortlist[i] = temp - (temp / 100000) * 100000 - 50000;
874 if (sortlist[i] > biggest)
875 biggest = sortlist[i];
876 else if (sortlist[i] < littlest)
877 littlest = sortlist[i];
878 }
879 }
880
881 Bubble ()
882 {
883 int i, j;
884 bInitarr ();
885 top = srtelements;
886
887 while (top > 1)
888 {
889
890 i = 1;
891 while (i < top)
892 {
893 cycles_start = rdtsc();
894 #ifndef NO_STAP_SDT
895 BENCH_BUBBLE (cycles_start,i, top);
896 #else
897 BENCH_BUBBLE:
898 #endif
899 if (__builtin_expect(bubble_cycles_idx != CYCLES_HBOUND,0))
900 {
901 bubble_cycles_idx++;
902 (*bubble_cycles)[bubble_cycles_idx] = rdtsc() - cycles_start;
903 }
904 if (sortlist[i] > sortlist[i + 1])
905 {
906 j = sortlist[i];
907 sortlist[i] = sortlist[i + 1];
908 sortlist[i + 1] = j;
909 }
910 i = i + 1;
911 }
912
913 top = top - 1;
914 }
915 if ((sortlist[1] != littlest) || (sortlist[srtelements] != biggest))
916 printf ("Error3 in Bubble.\n");
917 }
918
919
920 float
921 Cos (x)
922 float x;
923 {
924 int i, factor;
925 float result, power;
926
927 result = 1.0;
928 factor = 1;
929 power = x;
930 for (i = 2; i <= 10; i++)
931 {
932 factor = factor * i;
933 power = power * x;
934 if ((i & 1) == 0)
935 {
936 if ((i & 3) == 0)
937 result = result + power / factor;
938 else
939 result = result - power / factor;
940 }
941 }
942 return (result);
943 }
944
945 int
946 Min0 (arg1, arg2)
947 int arg1, arg2;
948 {
949 if (arg1 < arg2)
950 return (arg1);
951 else
952 return (arg2);
953 }
954
955 Printcomplex (arg1, arg2, zarray, start, finish, increment)
956 int arg1, arg2, start, finish, increment;
957 struct complex zarray[];
958 {
959 int i;
960 printf ("\n");
961
962 i = start;
963 do
964 {
965 printf (" %15.3e%15.3e", zarray[i].rp, zarray[i].ip);
966 i = i + increment;
967 printf (" %15.3e%15.3e", zarray[i].rp, zarray[i].ip);
968 printf ("\n");
969 i = i + increment;
970 }
971 while (i <= finish);
972
973 }
974
975 Uniform11 (iy, yfl)
976 int iy;
977 float yfl;
978 {
979 iy = (4855 * iy + 1731) & 8191;
980 yfl = iy / 8192.0;
981 }
982
983 Exptab (n, e)
984 int n;
985 struct complex e[];
986
987 {
988 float theta, divisor, h[26];
989 int i, j, k, l, m;
990
991 theta = 3.1415926536;
992 divisor = 4.0;
993 for (i = 1; i <= 25; i++)
994 {
995 h[i] = 1 / (2 * Cos (theta / divisor));
996 divisor = divisor + divisor;
997 }
998
999 m = n / 2;
1000 l = m / 2;
1001 j = 1;
1002 e[1].rp = 1.0;
1003 e[1].ip = 0.0;
1004 e[l + 1].rp = 0.0;
1005 e[l + 1].ip = 1.0;
1006 e[m + 1].rp = -1.0;
1007 e[m + 1].ip = 0.0;
1008
1009 do
1010 {
1011 i = l / 2;
1012 k = i;
1013
1014 do
1015 {
1016 e[k + 1].rp = h[j] * (e[k + i + 1].rp + e[k - i + 1].rp);
1017 e[k + 1].ip = h[j] * (e[k + i + 1].ip + e[k - i + 1].ip);
1018 k = k + l;
1019 }
1020 while (k <= m);
1021
1022 j = Min0 (j + 1, 25);
1023 l = i;
1024 }
1025 while (l > 1);
1026
1027 }
1028
1029 Fft (n, z, w, e, sqrinv)
1030 int n;
1031 struct complex z[], w[];
1032 struct complex e[];
1033 float sqrinv;
1034 {
1035 int i, j, k, l, m, index;
1036 m = n / 2;
1037 l = 1;
1038
1039 do
1040 {
1041 k = 0;
1042 j = l;
1043 i = 1;
1044
1045 do
1046 {
1047
1048 do
1049 {
1050 cycles_start = rdtsc();
1051 #ifndef NO_STAP_SDT
1052 BENCH_FFT (cycles_start,n, z, w, e);
1053 #else
1054 BENCH_FFT:
1055 #endif
1056 if (__builtin_expect(fft_cycles_idx != CYCLES_HBOUND,0))
1057 {
1058 fft_cycles_idx++;
1059 (*fft_cycles)[fft_cycles_idx] = rdtsc() - cycles_start;
1060 }
1061 w[i + k].rp = z[i].rp + z[m + i].rp;
1062 w[i + k].ip = z[i].ip + z[m + i].ip;
1063 w[i + j].rp = e[k + 1].rp * (z[i].rp - z[i + m].rp)
1064 - e[k + 1].ip * (z[i].ip - z[i + m].ip);
1065 w[i + j].ip = e[k + 1].rp * (z[i].ip - z[i + m].ip)
1066 + e[k + 1].ip * (z[i].rp - z[i + m].rp);
1067 i = i + 1;
1068 }
1069 while (i <= j);
1070
1071 k = j;
1072 j = k + l;
1073 }
1074 while (j <= m);
1075
1076 index = 1;
1077 do
1078 {
1079 z[index] = w[index];
1080 index = index + 1;
1081 }
1082 while (index <= n);
1083 l = l + l;
1084 }
1085 while (l <= m);
1086
1087 for (i = 1; i <= n; i++)
1088 {
1089 z[i].rp = sqrinv * z[i].rp;
1090 z[i].ip = -sqrinv * z[i].ip;
1091 };
1092
1093 }
1094
1095 Oscar ()
1096 {
1097 int i;
1098 Exptab (fftsize, e);
1099 seed = 5767;
1100 for (i = 1; i <= fftsize; i++)
1101 {
1102 Uniform11 (seed, zr);
1103 Uniform11 (seed, zi);
1104 z[i].rp = 20.0 * zr - 10.0;
1105 z[i].ip = 20.0 * zi - 10.0;
1106 };
1107
1108
1109 for (i = 1; i <= 20; i++)
1110 {
1111 Fft (fftsize, z, w, e, 0.0625);
1112 }
1113 }
1114
1115 #define Start()
1116 #define Stop(a,b)
1117
1118 #ifndef LOOP
1119 #define LOOP 500
1120 #endif
1121
1122 int
1123 main ()
1124 {
1125 int i,j;
1126
1127 permute_cycles = calloc(CYCLES_HBOUND,sizeof(long));
1128 tower_cycles = calloc(CYCLES_HBOUND,sizeof(long));
1129 try_cycles = calloc(CYCLES_HBOUND,sizeof(long));
1130 innerproduct_cycles = calloc(CYCLES_HBOUND,sizeof(long));
1131 trial_cycles = calloc(CYCLES_HBOUND,sizeof(long));
1132 quicksort_cycles = calloc(CYCLES_HBOUND,sizeof(long));
1133 insert_cycles = calloc(CYCLES_HBOUND,sizeof(long));
1134 bubble_cycles = calloc(CYCLES_HBOUND,sizeof(long));
1135 fft_cycles = calloc(CYCLES_HBOUND,sizeof(long));
1136
1137 Start ();
1138 for (i = 0; i < LOOP; i++)
1139 Perm ();
1140 Stop ("Perm", LOOP);
1141 Start ();
1142 for (i = 0; i < LOOP; i++)
1143 Towers ();
1144 Stop ("Towers", LOOP);
1145 Start ();
1146 for (i = 0; i < LOOP; i++)
1147 Queens ();
1148 Stop ("Queens", LOOP);
1149 Start ();
1150 for (i = 0; i < LOOP; i++)
1151 Intmm ();
1152 Stop ("Intmm", LOOP);
1153 Start ();
1154 for (i = 0; i < LOOP; i++)
1155 Mm ();
1156 Stop ("Mm", LOOP);
1157 Start ();
1158 for (i = 0; i < LOOP; i++)
1159 Puzzle ();
1160 Stop ("Puzzle", LOOP);
1161 Start ();
1162 for (i = 0; i < LOOP; i++)
1163 Quick ();
1164 Stop ("Quick", LOOP);
1165 Start ();
1166 for (i = 0; i < LOOP; i++)
1167 Bubble ();
1168 Stop ("Bubble", LOOP);
1169 Start ();
1170 for (i = 0; i < LOOP; i++)
1171 Trees ();
1172 Stop ("Trees", LOOP);
1173 Start ();
1174 for (i = 0; i < LOOP; i++)
1175 Oscar ();
1176 Stop ("Oscar", LOOP);
1177
1178 for (j = 1; j <= permute_cycles_idx; j++)
1179 permute_cycles_avg += (*permute_cycles)[j];
1180 printf ("permute_cycles %#lx\n", permute_cycles_avg / permute_cycles_idx);
1181 for (j = 1; j <= tower_cycles_idx; j++)
1182 tower_cycles_avg += (*tower_cycles)[j];
1183 printf ("tower_cycles %#lx\n", tower_cycles_avg / tower_cycles_idx);
1184 for (j = 1; j <= try_cycles_idx; j++)
1185 try_cycles_avg += (*try_cycles)[j];
1186 printf ("try_cycles %#lx\n", try_cycles_avg / try_cycles_idx);
1187 for (j = 1; j <= innerproduct_cycles_idx; j++)
1188 innerproduct_cycles_avg += (*innerproduct_cycles)[j];
1189 printf ("innerproduct_cycles %#lx\n", innerproduct_cycles_avg / innerproduct_cycles_idx);
1190 for (j = 1; j <= trial_cycles_idx; j++)
1191 trial_cycles_avg += (*trial_cycles)[j];
1192 printf ("trial_cycles %#lx\n", trial_cycles_avg / trial_cycles_idx);
1193 for (j = 1; j <= quicksort_cycles_idx; j++)
1194 quicksort_cycles_avg += (*quicksort_cycles)[j];
1195 printf ("quicksort_cycles %#lx\n", quicksort_cycles_avg / quicksort_cycles_idx);
1196 for (j = 1; j <= insert_cycles_idx; j++)
1197 insert_cycles_avg += (*insert_cycles)[j];
1198 printf ("insert_cycles %#lx\n", insert_cycles_avg / insert_cycles_idx);
1199 for (j = 1; j <= bubble_cycles_idx; j++)
1200 bubble_cycles_avg += (*bubble_cycles)[j];
1201 printf ("bubble_cycles %#lx\n", bubble_cycles_avg / bubble_cycles_idx);
1202 for (j = 1; j <= fft_cycles_idx; j++)
1203 fft_cycles_avg += (*fft_cycles)[j];
1204 printf ("fft_cycles %#lx\n", fft_cycles_avg / fft_cycles_idx);
1205 return 0;
1206 }