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*/