libgomp/testsuite/libgomp.c/sort-1.c

   1 /* Test and benchmark of a couple of parallel sorting algorithms.
   2    Copyright (C) 2008-2023 Free Software Foundation, Inc.
   3
   4    GCC is free software; you can redistribute it and/or modify it under
   5    the terms of the GNU General Public License as published by the Free
   6    Software Foundation; either version 3, or (at your option) any later
   7    version.
   8
   9    GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  10    WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11    FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12    for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with GCC; see the file COPYING3.  If not see
  16    <http://www.gnu.org/licenses/>.  */
  17
  18 /* { dg-additional-options "-Wno-deprecated-declarations" } */
  19
  20 #include <limits.h>
  21 #include <omp.h>
  22 #include <stdbool.h>
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 int failures;
  28
  29 #define THRESHOLD 100
  30
  31 static void
  32 verify (const char *name, double stime, int *array, int count)
  33 {
  34   int i;
  35   double etime = omp_get_wtime ();
  36
  37   printf ("%s: %g\n", name, etime - stime);
  38   for (i = 1; i < count; i++)
  39     if (array[i] < array[i - 1])
  40       {
  41         printf ("%s: incorrectly sorted\n", name);
  42         failures = 1;
  43       }
  44 }
  45
  46 static void
  47 insertsort (int *array, int s, int e)
  48 {
  49   int i, j, val;
  50   for (i = s + 1; i <= e; i++)
  51     {
  52       val = array[i];
  53       j = i;
  54       while (j-- > s && val < array[j])
  55         array[j + 1] = array[j];
  56       array[j + 1] = val;
  57     }
  58 }
  59
  60 struct int_pair
  61 {
  62   int lo;
  63   int hi;
  64 };
  65
  66 struct int_pair_stack
  67 {
  68   struct int_pair *top;
  69 #define STACK_SIZE 4 * CHAR_BIT * sizeof (int)
  70   struct int_pair arr[STACK_SIZE];
  71 };
  72
  73 static inline void
  74 init_int_pair_stack (struct int_pair_stack *stack)
  75 {
  76   stack->top = &stack->arr[0];
  77 }
  78
  79 static inline void
  80 push_int_pair_stack (struct int_pair_stack *stack, int lo, int hi)
  81 {
  82   stack->top->lo = lo;
  83   stack->top->hi = hi;
  84   stack->top++;
  85 }
  86
  87 static inline void
  88 pop_int_pair_stack (struct int_pair_stack *stack, int *lo, int *hi)
  89 {
  90   stack->top--;
  91   *lo = stack->top->lo;
  92   *hi = stack->top->hi;
  93 }
  94
  95 static inline int
  96 size_int_pair_stack (struct int_pair_stack *stack)
  97 {
  98   return stack->top - &stack->arr[0];
  99 }
 100
 101 static inline void
 102 busy_wait (void)
 103 {
 104 #if defined __i386__ || defined __x86_64__
 105   __builtin_ia32_pause ();
 106 #elif defined __ia64__
 107   __asm volatile ("hint @pause" : : : "memory");
 108 #elif defined __sparc__ && (defined __arch64__ || defined __sparc_v9__)
 109   __asm volatile ("membar #LoadLoad" : : : "memory");
 110 #else
 111   __asm volatile ("" : : : "memory");
 112 #endif
 113 }
 114
 115 static inline void
 116 swap (int *array, int a, int b)
 117 {
 118   int val = array[a];
 119   array[a] = array[b];
 120   array[b] = val;
 121 }
 122
 123 static inline int
 124 choose_pivot (int *array, int lo, int hi)
 125 {
 126   int mid = (lo + hi) / 2;
 127
 128   if (array[mid] < array[lo])
 129     swap (array, lo, mid);
 130   if (array[hi] < array[mid])
 131     {
 132       swap (array, mid, hi);
 133       if (array[mid] < array[lo])
 134         swap (array, lo, mid);
 135     }
 136   return array[mid];
 137 }
 138
 139 static inline int
 140 partition (int *array, int lo, int hi)
 141 {
 142   int pivot = choose_pivot (array, lo, hi);
 143   int left = lo;
 144   int right = hi;
 145
 146   for (;;)
 147     {
 148       while (array[++left] < pivot);
 149       while (array[--right] > pivot);
 150       if (left >= right)
 151         break;
 152       swap (array, left, right);
 153     }
 154   return left;
 155 }
 156
 157 static void
 158 sort1 (int *array, int count)
 159 {
 160   omp_lock_t lock;
 161   struct int_pair_stack global_stack;
 162   int busy = 1;
 163   int num_threads;
 164
 165   omp_init_lock (&lock);
 166   init_int_pair_stack (&global_stack);
 167   #pragma omp parallel firstprivate (array, count)
 168   {
 169     int lo = 0, hi = 0, mid, next_lo, next_hi;
 170     bool idle = true;
 171     struct int_pair_stack local_stack;
 172
 173     init_int_pair_stack (&local_stack);
 174     if (omp_get_thread_num () == 0)
 175       {
 176         num_threads = omp_get_num_threads ();
 177         hi = count - 1;
 178         idle = false;
 179       }
 180
 181     for (;;)
 182       {
 183         if (hi - lo < THRESHOLD)
 184           {
 185             insertsort (array, lo, hi);
 186             lo = hi;
 187           }
 188         if (lo >= hi)
 189           {
 190             if (size_int_pair_stack (&local_stack) == 0)
 191               {
 192               again:
 193                 omp_set_lock (&lock);
 194                 if (size_int_pair_stack (&global_stack) == 0)
 195                   {
 196                     if (!idle)
 197                       busy--;
 198                     if (busy == 0)
 199                       {
 200                         omp_unset_lock (&lock);
 201                         break;
 202                       }
 203                     omp_unset_lock (&lock);
 204                     idle = true;
 205                     while (size_int_pair_stack (&global_stack) == 0
 206                            && busy)
 207                       busy_wait ();
 208                     goto again;
 209                   }
 210                 if (idle)
 211                   busy++;
 212                 pop_int_pair_stack (&global_stack, &lo, &hi);
 213                 omp_unset_lock (&lock);
 214                 idle = false;
 215               }
 216             else
 217               pop_int_pair_stack (&local_stack, &lo, &hi);
 218           }
 219
 220         mid = partition (array, lo, hi);
 221         if (mid - lo < hi - mid)
 222           {
 223             next_lo = mid;
 224             next_hi = hi;
 225             hi = mid - 1;
 226           }
 227         else
 228           {
 229             next_lo = lo;
 230             next_hi = mid - 1;
 231             lo = mid;
 232           }
 233
 234         if (next_hi - next_lo < THRESHOLD)
 235           insertsort (array, next_lo, next_hi);
 236         else
 237           {
 238             if (size_int_pair_stack (&global_stack) < num_threads - 1)
 239               {
 240                 int size;
 241
 242                 omp_set_lock (&lock);
 243                 size = size_int_pair_stack (&global_stack);
 244                 if (size < num_threads - 1 && size < STACK_SIZE)
 245                   push_int_pair_stack (&global_stack, next_lo, next_hi);
 246                 else
 247                   push_int_pair_stack (&local_stack, next_lo, next_hi);
 248                 omp_unset_lock (&lock);
 249               }
 250             else
 251               push_int_pair_stack (&local_stack, next_lo, next_hi);
 252           }
 253       }
 254     }
 255   omp_destroy_lock (&lock);
 256 }
 257
 258 static void
 259 sort2_1 (int *array, int lo, int hi, int num_threads, int *busy)
 260 {
 261   int mid;
 262
 263   if (hi - lo < THRESHOLD)
 264     {
 265       insertsort (array, lo, hi);
 266       return;
 267     }
 268
 269   mid = partition (array, lo, hi);
 270
 271   if (*busy >= num_threads)
 272     {
 273       sort2_1 (array, lo, mid - 1, num_threads, busy);
 274       sort2_1 (array, mid, hi, num_threads, busy);
 275       return;
 276     }
 277
 278   #pragma omp atomic
 279     *busy += 1;
 280
 281   #pragma omp parallel num_threads (2) \
 282                        firstprivate (array, lo, hi, mid, num_threads, busy)
 283   {
 284     if (omp_get_thread_num () == 0)
 285       sort2_1 (array, lo, mid - 1, num_threads, busy);
 286     else
 287       {
 288         sort2_1 (array, mid, hi, num_threads, busy);
 289         #pragma omp atomic
 290           *busy -= 1;
 291       }
 292   }
 293 }
 294
 295 static void
 296 sort2 (int *array, int count)
 297 {
 298   int num_threads;
 299   int busy = 1;
 300
 301   #pragma omp parallel
 302     #pragma omp single nowait
 303       num_threads = omp_get_num_threads ();
 304
 305   sort2_1 (array, 0, count - 1, num_threads, &busy);
 306 }
 307
 308 #if _OPENMP >= 200805
 309 static void
 310 sort3_1 (int *array, int lo, int hi)
 311 {
 312   int mid;
 313
 314   if (hi - lo < THRESHOLD)
 315     {
 316       insertsort (array, lo, hi);
 317       return;
 318     }
 319
 320   mid = partition (array, lo, hi);
 321   #pragma omp task
 322     sort3_1 (array, lo, mid - 1);
 323   sort3_1 (array, mid, hi);
 324 }
 325
 326 static void
 327 sort3 (int *array, int count)
 328 {
 329   #pragma omp parallel
 330     #pragma omp single
 331       sort3_1 (array, 0, count - 1);
 332 }
 333 #endif
 334
 335 int
 336 main (int argc, char **argv)
 337 {
 338   int i, count = 1000000;
 339   double stime;
 340   int *unsorted, *sorted, num_threads;
 341   if (argc >= 2)
 342     count = strtoul (argv[1], NULL, 0);
 343
 344   unsorted = malloc (count * sizeof (int));
 345   sorted = malloc (count * sizeof (int));
 346   if (unsorted == NULL || sorted == NULL)
 347     {
 348       puts ("allocation failure");
 349       exit (1);
 350     }
 351
 352   srand (0xdeadbeef);
 353   for (i = 0; i < count; i++)
 354     unsorted[i] = rand ();
 355
 356   omp_set_nested (1);
 357   omp_set_dynamic (0);
 358   #pragma omp parallel
 359     #pragma omp single nowait
 360       num_threads = omp_get_num_threads ();
 361   printf ("Threads: %d\n", num_threads);
 362
 363   memcpy (sorted, unsorted, count * sizeof (int));
 364   stime = omp_get_wtime ();
 365   sort1 (sorted, count);
 366   verify ("sort1", stime, sorted, count);
 367
 368   memcpy (sorted, unsorted, count * sizeof (int));
 369   stime = omp_get_wtime ();
 370   sort2 (sorted, count);
 371   verify ("sort2", stime, sorted, count);
 372
 373 #if _OPENMP >= 200805
 374   memcpy (sorted, unsorted, count * sizeof (int));
 375   stime = omp_get_wtime ();
 376   sort3 (sorted, count);
 377   verify ("sort3", stime, sorted, count);
 378 #endif
 379
 380   return 0;
 381 }