1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <time.h>
#include "cleanbench.h"
#include "randnum.h"
/*********************
** NUMERIC HEAPSORT **
**********************
** This test implements a heapsort algorithm, performed on an
** array of longs.
*/
/*
** The following constant NUMARRAYSIZE determines the
** default # of elements in each numeric array
*/
#define ARRAY_SIZE 8111
static clock_t DoNumSortIteration(long *array, unsigned int num_arrays);
static void LoadNumArrayWithRand(long *array, unsigned int num_arrays);
static void NumHeapSort(long *array, unsigned long bottom, unsigned long top);
static void NumSift(long *array, unsigned long min, unsigned long max);
/**************
** DoNumSort **
***************
** This routine performs the CPU numeric sort test.
*/
double
DoNumSort (void)
{
long* array = NULL;
clock_t total_time = 0;
int iterations = 0;
static int num_arrays = 0;
static bool is_adjusted = false;
if (is_adjusted == false) {
is_adjusted = true;
/*
** Self-is_adjustedment code. The system begins by sorting 1
** array. If it does that in no time, then two arrays
** are built and sorted. This process continues until
** enough arrays are built to handle the tolerance.
*/
do {
++num_arrays;
array = realloc(array, num_arrays * ARRAY_SIZE * sizeof(long));
/*
** Do an iteration of the numeric sort. If the
** elapsed time is less than or equal to the permitted
** minimum, then allocate for more arrays and
** try again.
*/
} while (DoNumSortIteration(array, num_arrays) <= MINIMUM_TICKS);
} else {
array = malloc(num_arrays * ARRAY_SIZE * sizeof(long));
}
/*
** All's well if we get here. Repeatedly perform sorts until the
** accumulated elapsed time is greater than # of seconds requested.
*/
do {
total_time += DoNumSortIteration(array, num_arrays);
++iterations;
} while (total_time < MINIMUM_SECONDS * CLOCKS_PER_SEC);
free(array);
return (double)(iterations * num_arrays * CLOCKS_PER_SEC) / (double)total_time;
}
/***********************
** DoNumSortIteration **
************************
** This routine executes one iteration of the numeric
** sort benchmark. It returns the number of ticks
** elapsed for the iteration.
*/
static clock_t
DoNumSortIteration(long *array, unsigned int num_arrays)
{
clock_t start, stop;
unsigned long i;
/*
** Load up the array with random numbers
*/
LoadNumArrayWithRand(array, num_arrays);
start = clock();
for (i = 0; i < num_arrays; i++) {
NumHeapSort(&array[i], 0, ARRAY_SIZE - 1);
}
stop = clock();
return stop - start;
}
/*************************
** LoadNumArrayWithRand **
**************************
** Load up an array with random longs.
*/
static void
LoadNumArrayWithRand(long *array, unsigned int num_arrays)
{
long i; /* Used for index */
long *darray; /* Destination array pointer */
/* Initialize the random number generator */
randnum(13);
/* Load up first array with randoms */
for (i = 0; i < ARRAY_SIZE; i++) {
array[i] = randnum(0);
}
/*
** Now, if there's more than one array to load, copy the
** first into each of the others.
*/
darray = array;
while (--num_arrays) {
darray += ARRAY_SIZE;
memcpy(darray, array, ARRAY_SIZE * sizeof(long));
}
}
/****************
** NumHeapSort **
*****************
** Pass this routine a pointer to an array of long
** integers. Also pass in minimum and maximum offsets.
** This routine performs a heap sort on that array.
*/
static void
NumHeapSort(long *array, unsigned long bottom, unsigned long top)
{
unsigned long temp; /* Used to exchange elements */
unsigned long i; /* Loop index */
/*
** First, build a heap in the array
*/
for (i = (top / 2L); i > 0; i--) {
NumSift(array, i, top);
}
/*
** Repeatedly extract maximum from heap and place it at the
** end of the array. When we get done, we'll have a sorted
** array.
*/
for (i = top; i > 0; i--) {
NumSift(array, bottom, i);
temp = *array;
*array = *(array + i);
*(array + i) = temp;
}
}
/************
** NumSift **
*************
** Peforms the sift operation on a numeric array,
** constructing a heap in the array.
*/
static void
NumSift(long *array, unsigned long min, unsigned long max)
{
unsigned long k;
unsigned long temp; /* Used for exchange */
while ( ( min * 2 ) <= max ) {
k = min * 2;
if ( k < max ) {
if ( array[k] < array[k+1L] ) {
++k;
}
}
if ( array[min] < array[k] ) {
temp = array[k];
array[k] = array[min];
array[min] = temp;
min = k;
} else {
min = max + 1;
}
}
}
|
