1 static char help[] = "A benchmark for testing PetscSortInt(), PetscSortIntSemiOrdered(), PetscSortIntWithArrayPair(), PetscIntSortSemiOrderedWithArray(), and PetscSortIntWithArray()\n\
2 The array is filled with random numbers, but one can control average duplicates for each unique integer with the -d option.\n\
3 Usage:\n\
4 mpiexec -n 1 ./ex32 -n <length of the array to sort>, default=100 \n\
5 -r <repeat times for each sort>, default=10 \n\
6 -d <average duplicates for each unique integer>, default=1, i.e., no duplicates \n\n";
7
8 #include <petscsys.h>
9 #include <petsctime.h>
10 #include <petscviewer.h>
11 #include <petscvec.h>
main(int argc,char ** argv)12 int main(int argc, char **argv)
13 {
14 PetscInt i, l, n = 100, r = 10, d = 1, vsize = 1;
15 PetscInt *X, *X1, *XR, *XSO, *W, *Y, *Z, *XP, *X1P;
16 PetscReal val, norm1, nreal;
17 PetscRandom rdm, rdm2;
18 PetscLogDouble time, time1, time2;
19 PetscMPIInt size;
20 PetscViewer vwr;
21 Vec x;
22 PetscInt64 seedr, seedo;
23 PetscBool order = PETSC_FALSE;
24
25 PetscFunctionBeginUser;
26 PetscCall(PetscInitialize(&argc, &argv, NULL, help));
27 PetscCallMPI(MPI_Comm_size(PETSC_COMM_WORLD, &size));
28 PetscCheck(size == 1, PETSC_COMM_WORLD, PETSC_ERR_WRONG_MPI_SIZE, "This is a uniprocessor example only!");
29
30 PetscCall(PetscOptionsGetInt(NULL, NULL, "-n", &n, NULL));
31 PetscCall(PetscOptionsGetInt(NULL, NULL, "-r", &r, NULL));
32 PetscCall(PetscOptionsGetInt(NULL, NULL, "-d", &d, NULL));
33 PetscCall(PetscOptionsGetInt(NULL, NULL, "-vsize", &vsize, NULL));
34 PetscCall(PetscOptionsGetBool(NULL, NULL, "-order", NULL, &order));
35 PetscCall(PetscOptionsCreateViewer(PETSC_COMM_WORLD, NULL, NULL, "-array_view", &vwr, NULL, NULL));
36 PetscCheck(n >= 1 && r >= 1 && d >= 1 && d <= n, PETSC_COMM_WORLD, PETSC_ERR_SUP, "Wrong input n=%" PetscInt_FMT ",r=%" PetscInt_FMT ",d=%" PetscInt_FMT ". They must be >=1 and n>=d", n, r, d);
37
38 PetscCall(PetscCalloc6(n, &X, n, &X1, n, &XR, n, &XSO, n, &Y, n, &Z));
39 PetscCall(PetscRandomCreate(PETSC_COMM_SELF, &rdm));
40 PetscCall(PetscRandomSetFromOptions(rdm));
41 PetscCall(PetscRandomGetSeed(rdm, &seedr));
42
43 for (i = 0; i < n; ++i) {
44 PetscCall(PetscRandomGetValueReal(rdm, &val));
45 XR[i] = val * ((PetscReal)PETSC_INT_MAX);
46 if (d > 1) XR[i] = XR[i] % (n / d);
47 XSO[i] = i;
48 if (d > 1) XSO[i] = XSO[i] % (n / d);
49 }
50
51 nreal = (PetscReal)n;
52 PetscCall(PetscRandomCreate(PETSC_COMM_SELF, &rdm2));
53 PetscCall(PetscRandomGetSeed(rdm, &seedo));
54 PetscCall(PetscRandomSetInterval(rdm2, 0, nreal));
55 for (i = 0; i < n / 10; ++i) {
56 PetscInt swapi, t;
57 PetscCall(PetscRandomGetValueReal(rdm2, &val));
58 swapi = (PetscInt)val;
59 t = XSO[swapi - 1];
60 XSO[swapi - 1] = XSO[swapi];
61 XSO[swapi] = t;
62 }
63 PetscCall(PetscRandomDestroy(&rdm2));
64
65 if (vwr) PetscCall(PetscIntView(n, order ? XSO : XR, vwr));
66 PetscCall(PetscViewerDestroy(&vwr));
67 PetscCall(VecCreate(PETSC_COMM_WORLD, &x));
68 PetscCall(VecSetSizes(x, PETSC_DECIDE, vsize));
69 PetscCall(VecSetFromOptions(x));
70 PetscCall(VecSetRandom(x, rdm));
71 time = 0.0;
72 time1 = 0.0;
73 for (l = 0; l < r; l++) { /* r loops */
74 PetscCall(PetscArraycpy(X, order ? XSO : XR, n));
75 PetscCall(PetscArraycpy(X1, order ? XSO : XR, n));
76
77 PetscCall(VecNorm(x, NORM_1, &norm1));
78 PetscCall(PetscTimeSubtract(&time1));
79 PetscCall(PetscIntSortSemiOrdered(n, X1));
80 PetscCall(PetscTimeAdd(&time1));
81
82 PetscCall(VecNorm(x, NORM_1, &norm1));
83 PetscCall(PetscTimeSubtract(&time));
84 PetscCall(PetscSortInt(n, X));
85 PetscCall(PetscTimeAdd(&time));
86
87 for (i = 0; i < n - 1; i++) PetscCheck(X[i] <= X[i + 1], PETSC_COMM_SELF, PETSC_ERR_PLIB, "PetscSortInt() produced wrong results!");
88 for (i = 0; i < n; i++) {
89 PetscCheck(X[i] == X1[i], PETSC_COMM_SELF, PETSC_ERR_PLIB, "PetscIntSortSemiOrdered() rep %" PetscInt_FMT " X1[%" PetscInt_FMT "]:%" PetscInt_FMT " does not match PetscSortInt() X[%" PetscInt_FMT "]:%" PetscInt_FMT "! randomSeed %" PetscInt64_FMT ", orderedSeed %" PetscInt64_FMT, l, i, X1[i], i, X[i], seedr, seedo);
90 }
91 for (i = 0; i < n - 1; i++) PetscCheck(X1[i] <= X1[i + 1], PETSC_COMM_SELF, PETSC_ERR_PLIB, "PetscIntSortSemiOrdered() produced wrong results! randomSeed %" PetscInt64_FMT "orderedSeed %" PetscInt64_FMT, seedr, seedo);
92 PetscCall(PetscArrayzero(X, n));
93 PetscCall(PetscArrayzero(X1, n));
94 }
95 PetscCall(PetscPrintf(PETSC_COMM_SELF, "PetscSortInt() with %" PetscInt_FMT " integers, %" PetscInt_FMT " duplicate(s) per unique value took %g seconds\n", n, d, time / r));
96 PetscCall(PetscPrintf(PETSC_COMM_SELF, "PetscIntSortSemiOrdered() with %" PetscInt_FMT " integers, %" PetscInt_FMT " duplicate(s) per unique value took %g seconds\n", n, d, time1 / r));
97 PetscCall(PetscPrintf(PETSC_COMM_SELF, "Speedup of PetscIntSortSemiOrdered() was %g (0:1 = slower, >1 means faster)\n", time / time1));
98
99 for (i = 0; i < n; i++) { /* Init X[] */
100 PetscCall(PetscRandomGetValueReal(rdm, &val));
101 X[i] = val * ((PetscReal)PETSC_INT_MAX);
102 if (d > 1) X[i] = X[i] % (n / d);
103 }
104 PetscCall(PetscCalloc3(n, &XP, n, &X1P, n, &W));
105
106 time = 0.0;
107 time1 = 0.0;
108 time2 = 0.0;
109 for (l = 0; l < r; l++) { /* r loops */
110 PetscCall(PetscArraycpy(X1, order ? XSO : XR, n));
111 PetscCall(PetscArraycpy(X1P, order ? XSO : XR, n));
112 PetscCall(PetscArraycpy(X, order ? XSO : XR, n));
113 PetscCall(PetscArraycpy(XP, order ? XSO : XR, n));
114 PetscCall(PetscArraycpy(W, order ? XSO : XR, n));
115
116 PetscCall(VecNorm(x, NORM_1, &norm1));
117 PetscCall(PetscTimeSubtract(&time1));
118 PetscCall(PetscIntSortSemiOrderedWithArray(n, X1, X1P));
119 PetscCall(PetscTimeAdd(&time1));
120
121 PetscCall(VecNorm(x, NORM_1, &norm1));
122 PetscCall(PetscTimeSubtract(&time2));
123 PetscCall(PetscSortIntWithArray(n, X, XP));
124 PetscCall(PetscTimeAdd(&time2));
125
126 PetscCall(PetscTimeSubtract(&time));
127 PetscCall(PetscSortIntWithArrayPair(n, W, Y, Z));
128 PetscCall(PetscTimeAdd(&time));
129
130 for (i = 0; i < n - 1; i++) {
131 if (Y[i] > Y[i + 1]) {
132 PetscCall(PetscIntView(n, Y, 0));
133 SETERRQ(PETSC_COMM_SELF, PETSC_ERR_PLIB, "PetscSortIntWithArray() produced wrong results!");
134 }
135 }
136 for (i = 0; i < n - 1; i++) PetscCheck(W[i] <= W[i + 1], PETSC_COMM_SELF, PETSC_ERR_PLIB, "PetscSortIntWithArrayPair() produced wrong results!");
137 for (i = 0; i < n; i++) {
138 PetscCheck(X1P[i] == X[i], PETSC_COMM_SELF, PETSC_ERR_PLIB, "PetscIntSortSemiOrdered() rep %" PetscInt_FMT " X1[%" PetscInt_FMT "]:%" PetscInt_FMT " does not match PetscSortIntWithArray() X[%" PetscInt_FMT "]:%" PetscInt_FMT "! randomSeed %" PetscInt64_FMT " orderedSeed %" PetscInt64_FMT, l, i, X1[i], i, X[i], seedr, seedo);
139 }
140 for (i = 0; i < n - 1; i++) PetscCheck(X1[i] <= X1[i + 1], PETSC_COMM_SELF, PETSC_ERR_PLIB, "PetscIntSortSemiOrdered() produced wrong results! randomSeed %" PetscInt64_FMT "orderedSeed %" PetscInt64_FMT, seedr, seedo);
141 PetscCall(PetscArrayzero(X1, n));
142 PetscCall(PetscArrayzero(X1P, n));
143 PetscCall(PetscArrayzero(X, n));
144 PetscCall(PetscArrayzero(XP, n));
145 PetscCall(PetscArrayzero(W, n));
146 }
147 PetscCall(PetscPrintf(PETSC_COMM_SELF, "PetscSortIntWithArrayPair() with %" PetscInt_FMT " integers, %" PetscInt_FMT " duplicate(s) per unique value took %g seconds\n", n, d, time / r));
148 PetscCall(PetscPrintf(PETSC_COMM_SELF, "PetscSortIntWithArray() with %" PetscInt_FMT " integers, %" PetscInt_FMT " duplicate(s) per unique value took %g seconds\n", n, d, time2 / r));
149 PetscCall(PetscPrintf(PETSC_COMM_SELF, "PetscIntSortSemiOrderedWithArray() with %" PetscInt_FMT " integers, %" PetscInt_FMT " duplicate(s) per unique value took %g seconds\n", n, d, time1 / r));
150 PetscCall(PetscPrintf(PETSC_COMM_SELF, "Speedup of PetscIntSortSemiOrderedWithArray() was %g (0:1 = slower, >1 means faster)\n", time2 / time1));
151 PetscCall(PetscPrintf(PETSC_COMM_SELF, "SUCCEEDED\n"));
152
153 PetscCall(VecDestroy(&x));
154 PetscCall(PetscRandomDestroy(&rdm));
155 PetscCall(PetscFree3(XP, X1P, W));
156 PetscCall(PetscFree6(X, X1, XR, XSO, Y, Z));
157 PetscCall(PetscFinalize());
158 return 0;
159 }
160
161 /*TEST
162
163 testset:
164 filter: grep -vE "per unique value took|Speedup of "
165 output_file: output/ex32.out
166
167 test:
168 suffix: small
169 args: -n 9 -r 1
170
171 test:
172 suffix: large
173 args: -n 1000 -r 10 -d 1
174 # Do not need to output timing results for test
175
176 TEST*/
177