tests/ampi/isomalloc/test.C

   1 #ifndef __STDC_FORMAT_MACROS
   2 # define __STDC_FORMAT_MACROS
   3 #endif
   4 #ifndef __STDC_LIMIT_MACROS
   5 # define __STDC_LIMIT_MACROS
   6 #endif
   7
   8 #include <cstdint>
   9 #include <cstdlib>
  10 #include <cstdio>
  11 #include <random>
  12 #include <chrono>
  13 #include <algorithm>
  14 #include <type_traits>
  15
  16 // for getrusage
  17 #include <sys/time.h>
  18 #include <sys/resource.h>
  19
  20 #include "mpi.h"
  21
  22 #define STRINGIZE(x) #x
  23 #define STRINGIZE_VALUE_OF(x) STRINGIZE(x)
  24 #define isomalloc_method_str STRINGIZE_VALUE_OF(isomalloc_method)
  25
  26 static const uint32_t primes[] =
  27 {
  28   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
  29   73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
  30   157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,
  31   239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
  32   331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
  33   421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503,
  34   509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607,
  35   613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
  36   709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811,
  37   821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911,
  38   919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019,
  39   1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
  40   1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201,
  41   1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291,
  42   1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409,
  43   1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487,
  44   1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579,
  45   1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667,
  46   1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777,
  47   1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
  48   1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993,
  49   1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083,
  50   2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179,
  51   2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
  52   2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381,
  53   2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473,
  54   2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609,
  55   2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693,
  56   2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789,
  57   2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887,
  58   2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001,
  59   3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119,
  60   3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229,
  61   3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331,
  62   3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457,
  63   3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541,
  64   3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637,
  65   3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739,
  66   3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853,
  67   3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947,
  68   3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073,
  69   4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177,
  70   4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273,
  71   4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
  72   4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517,
  73   4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639,
  74   4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733,
  75   4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871,
  76   4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969,
  77   4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077,
  78   5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189,
  79   5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309,
  80   5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431,
  81   5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521,
  82   5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651,
  83   5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743,
  84   5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851,
  85   5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981,
  86   5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091,
  87   6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211,
  88   6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311,
  89   6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397,
  90   6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553,
  91   6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673,
  92   6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781,
  93   6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883,
  94   6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991,
  95   6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121,
  96   7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237,
  97   7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369,
  98   7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507,
  99   7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589,
 100   7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699,
 101   7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829,
 102   7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937,
 103   7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087,
 104   8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209,
 105   8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297,
 106   8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431,
 107   8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573,
 108   8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681,
 109   8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779,
 110   8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887,
 111   8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011,
 112   9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137,
 113   9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241,
 114   9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371,
 115   9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463,
 116   9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601,
 117   9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719,
 118   9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817,
 119   9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929,
 120   9931, 9941, 9949, 9967, 9973,
 121 };
 122
 123 static const uint32_t largeprimes[] =
 124 {
 125   143687, 266083, 393073, 523417, 656683, 791447, 927853, 1066909, 1205653,
 126   1346567, 1488133, 1630987, 1774937, 1918439, 2063573, 2209499, 2356573,
 127   2503597, 2650931, 2799451, 2948161, 3097141, 3246119, 3396661, 3548471,
 128   3698881, 3849943, 4002547, 4154791, 4307453, 4459951, 4613237, 4766999,
 129   4920613, 5074633, 5229331, 5383601, 5539363, 5695831, 5851717, 6007247,
 130   6163567, 6319483, 6477301, 6633877, 6791437, 6947753, 7104341, 7263143,
 131   7421383, 7580459, 7738559, 7896949, 8056423, 8215633, 8375273, 8534489,
 132   8693653, 8853359, 9014101, 9174793, 9334487, 9495601, 9655759, 9817057,
 133   9979111, 10140307,
 134 };
 135
 136 template <typename T, size_t N>
 137 static inline constexpr size_t countof(T const (&)[N]) noexcept
 138 {
 139   return N;
 140 }
 141
 142 static inline void request_migration()
 143 {
 144   AMPI_Migrate(AMPI_INFO_LB_SYNC);
 145 }
 146
 147 class malloc_stress
 148 {
 149   // This class avoids heap allocations other than the test itself.
 150
 151   const int rank, p;
 152
 153   static constexpr size_t maxallocs = 2048;
 154   static constexpr size_t maxsegments = 8;
 155   static constexpr size_t maxtests = 32;
 156
 157   struct alloc_type
 158   {
 159     unsigned char *ptr;
 160     unsigned int size;
 161   };
 162   alloc_type allocations[maxallocs]{};
 163   alloc_type * allocation_queue[maxallocs*2]{};
 164
 165   unsigned int segments[maxsegments]{}; // segment boundaries
 166
 167   struct test_type
 168   {
 169     const char *description1, *description2;
 170     unsigned long long duration_count;
 171   };
 172   test_type tests[maxtests]{};
 173
 174   unsigned long long overall_duration_count = 0;
 175
 176   // ideally these variables could be marked const after a certain point in execution
 177   size_t numallocs = 0;
 178   size_t numsegments = 1;
 179   size_t queuesize;
 180 #ifdef MIGRATION_OVERKILL
 181   size_t migrationinterval;
 182 #endif
 183
 184 public:
 185
 186   using clock_type = typename std::conditional<
 187     std::chrono::high_resolution_clock::is_steady,
 188     std::chrono::high_resolution_clock, std::chrono::steady_clock>::type;
 189   using time_point = typename std::chrono::time_point<clock_type>;
 190   using duration_type = typename std::chrono::duration<unsigned long long, std::nano>;
 191
 192   malloc_stress(int rank_, int p_)
 193     : rank{rank_}, p{p_}
 194   {
 195     // this assertion needs to match the way the structures are populated below
 196     static_assert(countof(primes) + 3*countof(largeprimes) <= maxallocs, "increase maxallocs");
 197
 198     segments[0] = 0;
 199
 200     for (size_t i = rank; i < countof(primes); i += p)
 201     {
 202       allocations[numallocs++].size = primes[i];
 203     }
 204     segments[numsegments++] = numallocs;
 205
 206     for (size_t i = rank; i < countof(largeprimes); i += p)
 207     {
 208       allocations[numallocs++].size = largeprimes[i];
 209     }
 210     segments[numsegments++] = numallocs;
 211
 212     for (size_t i = rank; i < countof(largeprimes); i += p)
 213     {
 214       allocations[numallocs++].size = primes[countof(primes)-1-i];
 215       allocations[numallocs++].size = largeprimes[i];
 216     }
 217     segments[numsegments++] = numallocs;
 218
 219     queuesize = numallocs * 2;
 220 #ifdef MIGRATION_OVERKILL
 221     migrationinterval = numallocs / 31; // prime number divisor
 222 #endif
 223   }
 224
 225 private:
 226
 227   void alloc_loop(const size_t a_begin, const size_t a_end)
 228   {
 229     for (size_t a = a_begin; a < a_end; ++a)
 230     {
 231       alloc_type & allocation = *(allocation_queue[a]);
 232       const size_t size = allocation.size;
 233       const unsigned char rankbyte = rank & 0xFF;
 234
 235       const auto ptr = allocation.ptr = (unsigned char*)malloc(size);
 236       if (ptr == nullptr)
 237       {
 238         printf("Error: malloc() failure in rank %d, test %zu, allocation %zu\n", rank, testnum, a);
 239         MPI_Abort(MPI_COMM_WORLD, 1);
 240       }
 241       ptr[0] = ptr[size-1] = rankbyte;
 242
 243 #ifdef MIGRATION_OVERKILL
 244       ++eventnum;
 245       if (eventnum == migrationinterval)
 246       {
 247         eventnum = 0;
 248         request_migration();
 249       }
 250 #endif
 251     }
 252   }
 253
 254   void free_loop(const size_t a_begin, const size_t a_end)
 255   {
 256     for (size_t a = a_begin; a < a_end; ++a)
 257     {
 258       alloc_type & allocation = *(allocation_queue[a]);
 259       const size_t size = allocation.size;
 260       const unsigned char rankbyte = rank & 0xFF;
 261
 262       const auto ptr = allocation.ptr;
 263       if (ptr[0] != rankbyte || ptr[size-1] != rankbyte)
 264       {
 265         printf("Error: Correctness failure in rank %d, test %zu, allocation %zu\n", rank, testnum, a);
 266         MPI_Abort(MPI_COMM_WORLD, 2);
 267       }
 268       free(ptr);
 269       allocation.ptr = nullptr;
 270
 271 #ifdef MIGRATION_OVERKILL
 272       ++eventnum;
 273       if (eventnum == migrationinterval)
 274       {
 275         eventnum = 0;
 276         request_migration();
 277       }
 278 #endif
 279     }
 280   }
 281
 282   void undetermined_loop(const size_t a_begin, const size_t a_end)
 283   {
 284     for (size_t a = a_begin; a < a_end; ++a)
 285     {
 286       alloc_type & allocation = *(allocation_queue[a]);
 287       const size_t size = allocation.size;
 288       const unsigned char rankbyte = rank & 0xFF;
 289
 290       auto ptr = allocation.ptr;
 291       if (ptr == nullptr)
 292       {
 293         ptr = allocation.ptr = (unsigned char*)malloc(size);
 294         if (ptr == nullptr)
 295         {
 296           printf("Error: malloc() failure in rank %d, test %zu, allocation %zu\n", rank, testnum, a);
 297           MPI_Abort(MPI_COMM_WORLD, 1);
 298         }
 299         ptr[0] = ptr[size-1] = rankbyte;
 300       }
 301       else
 302       {
 303         if (ptr[0] != rankbyte || ptr[size-1] != rankbyte)
 304         {
 305           printf("Error: Correctness failure in rank %d, test %zu, allocation %zu\n", rank, testnum, a);
 306           MPI_Abort(MPI_COMM_WORLD, 2);
 307         }
 308         allocation.ptr = nullptr;
 309         free(ptr);
 310       }
 311
 312 #ifdef MIGRATION_OVERKILL
 313       ++eventnum;
 314       if (eventnum == migrationinterval)
 315       {
 316         eventnum = 0;
 317         request_migration();
 318       }
 319 #endif
 320     }
 321   }
 322
 323   void reset_queue()
 324   {
 325     alloc_type ** q = allocation_queue;
 326     for (alloc_type * al = allocations, * al_end = al + numallocs; al < al_end; ++al)
 327       *(q++) = al;
 328   }
 329
 330   // tests freeing after every segment
 331   using operate_segment = void (malloc_stress::*)(size_t);
 332
 333   void test_by_segment(operate_segment between = &malloc_stress::identity_segment, operate_segment after = &malloc_stress::identity_segment)
 334   {
 335 #ifdef MIGRATION_OVERKILL
 336     eventnum = 0;
 337 #endif
 338
 339     if (testnum == maxtests)
 340     {
 341       printf("Error: Increase maxtests.\n");
 342       MPI_Abort(MPI_COMM_WORLD, 10);
 343     }
 344
 345     unsigned long long test_duration_count = 0;
 346
 347     MPI_Barrier(MPI_COMM_WORLD);
 348
 349     for (size_t s = 1; s < numsegments; ++s)
 350     {
 351       const time_point t_0 = clock_type::now();
 352       alloc_loop(segments[s-1], segments[s]);
 353       const time_point t_1 = clock_type::now();
 354
 355       request_migration();
 356       (this->*between)(s);
 357
 358       const time_point t_2 = clock_type::now();
 359       free_loop(segments[s-1], segments[s]);
 360       const time_point t_3 = clock_type::now();
 361
 362       request_migration();
 363       (this->*after)(s);
 364
 365       const duration_type test_duration = (t_3 - t_2) + (t_1 - t_0);
 366       test_duration_count += test_duration.count();
 367     }
 368
 369     unsigned long long duration_count = 0;
 370     MPI_Reduce(&test_duration_count, &duration_count, 1, MPI_UNSIGNED_LONG_LONG, MPI_MAX, 0, MPI_COMM_WORLD);
 371     tests[testnum].duration_count += duration_count;
 372
 373     ++testnum;
 374   }
 375
 376   // tests freeing at the end
 377   using operate_all = void (malloc_stress::*)();
 378
 379   void test_all(operate_all between = &malloc_stress::identity_all, operate_all after = &malloc_stress::identity_all)
 380   {
 381 #ifdef MIGRATION_OVERKILL
 382     eventnum = 0;
 383 #endif
 384
 385     if (testnum == maxtests)
 386     {
 387       printf("Error: Increase maxtests.\n");
 388       MPI_Abort(MPI_COMM_WORLD, 10);
 389     }
 390
 391     MPI_Barrier(MPI_COMM_WORLD);
 392
 393     const time_point t_0 = clock_type::now();
 394     alloc_loop(0, numallocs);
 395     const time_point t_1 = clock_type::now();
 396
 397     request_migration();
 398     (this->*between)();
 399
 400     const time_point t_2 = clock_type::now();
 401     free_loop(0, numallocs);
 402     const time_point t_3 = clock_type::now();
 403
 404     request_migration();
 405     (this->*after)();
 406
 407     const duration_type test_duration = (t_3 - t_2) + (t_1 - t_0);
 408     unsigned long long test_duration_count = test_duration.count();
 409
 410     unsigned long long duration_count = 0;
 411     MPI_Reduce(&test_duration_count, &duration_count, 1, MPI_UNSIGNED_LONG_LONG, MPI_MAX, 0, MPI_COMM_WORLD);
 412     tests[testnum].duration_count += duration_count;
 413
 414     ++testnum;
 415   }
 416
 417   // tests with alloc and free interspersed
 418   void test_mixed()
 419   {
 420 #ifdef MIGRATION_OVERKILL
 421     eventnum = 0;
 422 #endif
 423
 424     if (testnum == maxtests)
 425     {
 426       printf("Error: Increase maxtests.\n");
 427       MPI_Abort(MPI_COMM_WORLD, 10);
 428     }
 429
 430     MPI_Barrier(MPI_COMM_WORLD);
 431
 432     const time_point t_0 = clock_type::now();
 433     undetermined_loop(0, numallocs*2);
 434     const time_point t_1 = clock_type::now();
 435
 436     request_migration();
 437
 438     const duration_type test_duration = t_1 - t_0;
 439     unsigned long long test_duration_count = test_duration.count();
 440
 441     unsigned long long duration_count = 0;
 442     MPI_Reduce(&test_duration_count, &duration_count, 1, MPI_UNSIGNED_LONG_LONG, MPI_MAX, 0, MPI_COMM_WORLD);
 443     tests[testnum].duration_count += duration_count;
 444
 445     ++testnum;
 446   }
 447
 448   void identity_segment(size_t) { }
 449   void identity_all() { }
 450
 451   void shuffle_segment(size_t s)
 452   {
 453     std::shuffle(allocation_queue + segments[s-1], allocation_queue + segments[s], generator);
 454   }
 455   void shuffle_segments()
 456   {
 457     for (size_t s = 1; s < numsegments; ++s)
 458       shuffle_segment(s);
 459   }
 460   void shuffle_all()
 461   {
 462     std::shuffle(allocation_queue, allocation_queue + numallocs, generator);
 463   }
 464
 465   void reverse_segment(size_t s)
 466   {
 467     std::reverse(allocation_queue + segments[s-1], allocation_queue + segments[s]);
 468   }
 469   void reverse_segments()
 470   {
 471     for (size_t s = 1; s < numsegments; ++s)
 472       reverse_segment(s);
 473   }
 474   void reverse_all()
 475   {
 476     std::reverse(allocation_queue, allocation_queue + numallocs);
 477   }
 478
 479   void shuffle_segments_and_reverse_all()
 480   {
 481     shuffle_segments();
 482     reverse_all();
 483   }
 484
 485   void tests_static(const char *desc1)
 486   {
 487     // allocate and free in the original order
 488
 489     tests[testnum].description1 = desc1;
 490     tests[testnum].description2 = "FIFO free, batched by segment";
 491     test_by_segment();
 492
 493     tests[testnum].description1 = desc1;
 494     tests[testnum].description2 = "FIFO free, one batch";
 495     test_all();
 496
 497
 498     // allocate in the original order, free in the reverse order
 499
 500     tests[testnum].description1 = desc1;
 501     tests[testnum].description2 = "LIFO free, batched by segment";
 502     test_by_segment(&malloc_stress::reverse_segment, &malloc_stress::reverse_segment);
 503
 504     tests[testnum].description1 = desc1;
 505     tests[testnum].description2 = "LIFO free within segments, one batch";
 506     test_all(&malloc_stress::reverse_segments, &malloc_stress::reverse_segments);
 507
 508     tests[testnum].description1 = desc1;
 509     tests[testnum].description2 = "LIFO free overall, one batch";
 510     test_all(&malloc_stress::reverse_all, &malloc_stress::reverse_all);
 511   }
 512
 513   void tests_dynamic(const char *desc1)
 514   {
 515     tests[testnum].description1 = desc1;
 516     tests[testnum].description2 = "within segments, batched by segment";
 517     test_by_segment(&malloc_stress::shuffle_segment);
 518
 519     tests[testnum].description1 = desc1;
 520     tests[testnum].description2 = "within segments, FIFO segment order, one batch";
 521     test_all(&malloc_stress::shuffle_segments);
 522
 523     tests[testnum].description1 = desc1;
 524     tests[testnum].description2 = "within segments, LIFO segment order, one batch";
 525     test_all(&malloc_stress::shuffle_segments_and_reverse_all); // reverse the segment order
 526
 527     tests[testnum].description1 = desc1;
 528     tests[testnum].description2 = "overall, one batch";
 529     test_all(&malloc_stress::shuffle_all);
 530   }
 531
 532   void tests_mixed(const char *desc1)
 533   {
 534     {
 535       alloc_type ** q = allocation_queue;
 536       for (size_t s = 1; s < numsegments; ++s)
 537       {
 538         const size_t a_begin = segments[s-1], a_end = segments[s];
 539
 540         alloc_type ** const q_begin = q;
 541
 542         alloc_type * const al_begin = allocations + a_begin, * const al_end = allocations + a_end;
 543         for (alloc_type * al = al_begin; al < al_end; ++al)
 544           *(q++) = al;
 545         for (alloc_type * al = al_begin; al < al_end; ++al)
 546           *(q++) = al;
 547
 548         std::shuffle(q_begin, q, generator);
 549       }
 550     }
 551     tests[testnum].description1 = desc1;
 552     tests[testnum].description2 = "within segments, batched by segment";
 553     test_mixed();
 554
 555     {
 556       alloc_type ** q = allocation_queue;
 557       for (alloc_type * al = allocations, * al_end = al + numallocs; al < al_end; ++al)
 558         *(q++) = al;
 559       for (alloc_type * al = allocations, * al_end = al + numallocs; al < al_end; ++al)
 560         *(q++) = al;
 561     }
 562     std::shuffle(allocation_queue, allocation_queue + queuesize, generator);
 563     tests[testnum].description1 = desc1;
 564     tests[testnum].description2 = "overall, one batch";
 565     test_mixed();
 566   }
 567
 568   // these variables should be reset for each run
 569   std::mt19937 generator;
 570 #ifdef MIGRATION_OVERKILL
 571   size_t eventnum;
 572 #endif
 573   size_t testnum;
 574
 575 public:
 576
 577   unsigned long long run(uint32_t randomseed)
 578   {
 579     generator.seed(randomseed);
 580 #ifdef MIGRATION_OVERKILL
 581     eventnum = 0;
 582 #endif
 583     testnum = 0;
 584
 585     MPI_Barrier(MPI_COMM_WORLD);
 586     const time_point t_0 = clock_type::now();
 587
 588     reset_queue();
 589
 590     tests_static("distinct phases, without shuffling, ");
 591
 592     shuffle_segments();
 593     tests_static("distinct phases, static shuffle within segments, ");
 594
 595     shuffle_all();
 596     tests_static("distinct phases, static shuffle overall, ");
 597
 598     shuffle_all();
 599     tests_dynamic("distinct phases, shuffling between phases ");
 600
 601     tests_mixed("one phase, shuffled ");
 602
 603     MPI_Barrier(MPI_COMM_WORLD);
 604     const time_point t_1 = clock_type::now();
 605
 606
 607     const duration_type my_overall_duration = t_1 - t_0;
 608     const unsigned long long my_overall_duration_count = my_overall_duration.count();
 609     overall_duration_count += my_overall_duration_count;
 610
 611     return my_overall_duration_count;
 612   }
 613
 614   void average(size_t iterations)
 615   {
 616     for (size_t t = 0; t < testnum; ++t)
 617     {
 618       test_type & test = tests[t];
 619       test.duration_count /= iterations;
 620     }
 621
 622     overall_duration_count /= iterations;
 623   }
 624
 625   void print(size_t iterations) const
 626   {
 627     unsigned long long total_duration_count = 0;
 628
 629     printf("detailed results:\n");
 630     printf("              test # -  total duration (ns) -   avg. duration (ns) - description\n");
 631     for (size_t t = 0; t < testnum; ++t)
 632     {
 633       const test_type & test = tests[t];
 634
 635       total_duration_count += test.duration_count;
 636
 637       printf("%20zu - %20llu - %20llu - %s%s\n", t+1,
 638              test.duration_count, test.duration_count / iterations,
 639              test.description1, test.description2);
 640     }
 641     printf("                 all - %20llu - %20llu - total\n",
 642            total_duration_count, total_duration_count / iterations);
 643
 644     printf("overall test duration (ns) including migration, shuffling, barriers, etc: { total: %llu, average: %llu }\n",
 645            overall_duration_count, overall_duration_count / iterations);
 646
 647     struct rusage usage;
 648     getrusage(RUSAGE_SELF, &usage);
 649
 650     printf("memory usage high water mark ("
 651 #ifdef __APPLE__
 652       "bytes"
 653 #else
 654       "kilobytes"
 655 #endif
 656       "): %lu\n", usage.ru_maxrss);
 657   }
 658 };
 659
 660 static uint32_t generate_randomseed(int rank)
 661 {
 662   uint32_t randomseed;
 663
 664   if (rank == 0)
 665     randomseed = std::chrono::system_clock::now().time_since_epoch().count();
 666
 667   MPI_Bcast(&randomseed, 1, MPI_UINT32_T, 0, MPI_COMM_WORLD);
 668
 669   return randomseed;
 670 }
 671
 672 int main(int argc, char** argv)
 673 {
 674   MPI_Init(&argc, &argv);
 675
 676   int rank;
 677   int p;
 678   MPI_Comm_rank(MPI_COMM_WORLD, &rank);
 679   MPI_Comm_size(MPI_COMM_WORLD, &p);
 680
 681   malloc_stress test{rank, p};
 682
 683   bool doIterations = false;
 684   size_t iterations = 1;
 685   uint32_t randomseed = generate_randomseed(rank);
 686
 687   if (argc > 2)
 688   {
 689     if (strcmp(argv[1], "iterations") == 0)
 690     {
 691       doIterations = true;
 692       iterations = (size_t)atoll(argv[2]);
 693       if (iterations == 0)
 694         iterations = 1;
 695     }
 696     else if (strcmp(argv[1], "randomseed") == 0)
 697     {
 698       randomseed = (uint32_t)atol(argv[2]);
 699     }
 700   }
 701
 702   if (doIterations)
 703   {
 704     if (rank == 0)
 705     {
 706       printf("malloc stress test: ./" isomalloc_method_str " (...) +vp%i iterations %zu\n", p, iterations);
 707       printf("             round # -        duration (ns) - command\n");
 708     }
 709
 710     for (size_t i = 0; i < iterations; ++i)
 711     {
 712       randomseed = generate_randomseed(rank);
 713
 714       const unsigned long long duration = test.run(randomseed);
 715
 716       if (rank == 0)
 717         printf("%20zu - %20llu - ./" isomalloc_method_str " (...) +vp%i randomseed %" PRIu32 "\n",
 718                i+1, duration, p, randomseed);
 719     }
 720   }
 721   else
 722   {
 723     if (rank == 0)
 724       printf("malloc stress test: ./" isomalloc_method_str " (...) +vp%i randomseed %" PRIu32 "\n",
 725              p, randomseed);
 726
 727     test.run(randomseed);
 728   }
 729
 730   if (rank == 0)
 731     test.print(iterations);
 732
 733   MPI_Finalize();
 734
 735   return 0;
 736 }