Actual source code: ex52.c
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: mpirun -n 1 ./ex52 -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";
8: #include <petscsys.h>
9: #include <petsctime.h>
10: #include <petscviewer.h>
11: #include <petscvec.h>
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: unsigned long seedr, seedo;
23: PetscBool order = PETSC_FALSE;
25: PetscFunctionBeginUser;
26: PetscCall(PetscInitialize(&argc, &argv, (char *)0, 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!");
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(PetscOptionsGetViewer(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);
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));
43: for (i = 0; i < n; ++i) {
44: PetscCall(PetscRandomGetValueReal(rdm, &val));
45: XR[i] = val * ((PetscReal)PETSC_MAX_INT);
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: }
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));
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));
77: PetscCall(VecNorm(x, NORM_1, &norm1));
78: PetscCall(PetscTimeSubtract(&time1));
79: PetscCall(PetscIntSortSemiOrdered(n, X1));
80: PetscCall(PetscTimeAdd(&time1));
82: PetscCall(VecNorm(x, NORM_1, &norm1));
83: PetscCall(PetscTimeSubtract(&time));
84: PetscCall(PetscSortInt(n, X));
85: PetscCall(PetscTimeAdd(&time));
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 %lu, orderedSeed %lu", 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 %lu orderedSeed %lu", 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));
99: for (i = 0; i < n; i++) { /* Init X[] */
100: PetscCall(PetscRandomGetValueReal(rdm, &val));
101: X[i] = val * ((PetscReal)PETSC_MAX_INT);
102: if (d > 1) X[i] = X[i] % (n / d);
103: }
104: PetscCall(PetscCalloc3(n, &XP, n, &X1P, n, &W));
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));
116: PetscCall(VecNorm(x, NORM_1, &norm1));
117: PetscCall(PetscTimeSubtract(&time1));
118: PetscCall(PetscIntSortSemiOrderedWithArray(n, X1, X1P));
119: PetscCall(PetscTimeAdd(&time1));
121: PetscCall(VecNorm(x, NORM_1, &norm1));
122: PetscCall(PetscTimeSubtract(&time2));
123: PetscCall(PetscSortIntWithArray(n, X, XP));
124: PetscCall(PetscTimeAdd(&time2));
126: PetscCall(PetscTimeSubtract(&time));
127: PetscCall(PetscSortIntWithArrayPair(n, W, Y, Z));
128: PetscCall(PetscTimeAdd(&time));
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 %lu, orderedSeed %lu", 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 %lu orderedSeed %lu", 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"));
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: }
161: /*TEST
163: testset:
164: filter: grep -vE "per unique value took|Speedup of "
166: test:
167: suffix: small
168: args: -n 9 -r 1
170: test:
171: suffix: large
172: args: -n 1000 -r 10 -d 1
173: # Do not need to output timing results for test
175: TEST*/