dispatch-1.0/testing/bench.mm

   1 /*
   2  * Copyright (c) 2008-2009 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_APACHE_LICENSE_HEADER_START@
   5  *
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  *
  18  * @APPLE_APACHE_LICENSE_HEADER_END@
  19  */
  20
  21 #include <Foundation/Foundation.h>
  22 #include <libkern/OSAtomic.h>
  23 #include <sys/sysctl.h>
  24 #include <mach/mach.h>
  25 #include <mach/mach_time.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <stdint.h>
  29 #include <stdbool.h>
  30 #include <unistd.h>
  31 #include <assert.h>
  32 #include <errno.h>
  33 #include <pthread.h>
  34 #include <math.h>
  35 #ifdef __BLOCKS__
  36 #include <Block.h>
  37 #endif
  38 #include <dispatch/dispatch.h>
  39 #include <dispatch/private.h>
  40
  41 extern "C" {
  42 __private_extern__ void func(void);
  43 #ifdef __BLOCKS__
  44 __private_extern__ void (^block)(void);
  45 #endif
  46 static void backflip(void *ctxt);
  47 static void backflip_done(void);
  48 }
  49
  50 @interface BasicObject : NSObject
  51 {
  52 }
  53 - (void) method;
  54 @end
  55
  56 @implementation BasicObject
  57 - (void) method
  58 {
  59 }
  60 @end
  61
  62 class BasicClass {
  63 public:
  64         virtual void virtfunc(void) {
  65         };
  66 };
  67
  68 static void *
  69 force_a_thread(void *arg)
  70 {
  71         pause();
  72         abort();
  73         return arg;
  74 }
  75
  76 static volatile int32_t global;
  77
  78 static const size_t cnt = 10000000;
  79 static const size_t cnt2 = 100000;
  80
  81 static uint64_t bfs;
  82 static long double loop_cost;
  83 static long double cycles_per_nanosecond;
  84 static mach_timebase_info_data_t tbi;
  85
  86 //static void func2(void *, dispatch_item_t di);
  87
  88 static void __attribute__((noinline))
  89 print_result(uint64_t s, const char *str)
  90 {
  91         uint64_t d, e = mach_absolute_time();
  92         long double dd;
  93
  94         d = e - s;
  95
  96         if (tbi.numer != tbi.denom) {
  97                 d *= tbi.numer;
  98                 d /= tbi.denom;
  99         }
 100
 101         dd = (typeof(dd))d / (typeof(dd))cnt;
 102
 103         dd -= loop_cost;
 104
 105         if (loop_cost == 0.0) {
 106                 loop_cost = dd;
 107         }
 108
 109         dd *= cycles_per_nanosecond;
 110
 111         printf("%-45s%15.3Lf cycles\n", str, dd);
 112 }
 113
 114 static void __attribute__((noinline))
 115 print_result2(uint64_t s, const char *str)
 116 {
 117         uint64_t d, e = mach_absolute_time();
 118         long double dd;
 119
 120         d = e - s;
 121
 122         if (tbi.numer != tbi.denom) {
 123                 d *= tbi.numer;
 124                 d /= tbi.denom;
 125         }
 126
 127         dd = (typeof(dd))d / (typeof(dd))cnt2;
 128
 129         dd -= loop_cost;
 130         dd *= cycles_per_nanosecond;
 131
 132         printf("%-45s%15.3Lf cycles\n", str, dd);
 133 }
 134
 135 #if defined(__i386__) || defined(__x86_64__)
 136 static inline uint64_t
 137 rdtsc(void)
 138 {
 139         uint32_t lo, hi;
 140
 141         asm volatile("rdtsc" : "=a" (lo), "=d" (hi));
 142
 143         return (uint64_t)hi << 32 | lo;
 144 }
 145 #endif
 146
 147 static struct fml {
 148         struct fml *fml_next;
 149 } *fixed_malloc_lifo_head;
 150
 151 struct fml *fixed_malloc_lifo(void);// __attribute__((noinline));
 152 void fixed_free_lifo(struct fml *fml);// __attribute__((noinline));
 153
 154 struct fml *
 155 fixed_malloc_lifo(void)
 156 {
 157         struct fml *fml_r = fixed_malloc_lifo_head;
 158
 159         if (fml_r) {
 160                 fixed_malloc_lifo_head = fml_r->fml_next;
 161                 return fml_r;
 162         } else {
 163                 return (struct fml *)malloc(32);
 164         }
 165 }
 166
 167 void
 168 fixed_free_lifo(struct fml *fml)
 169 {
 170         fml->fml_next = fixed_malloc_lifo_head;
 171         fixed_malloc_lifo_head = fml;
 172 }
 173
 174 int
 175 main(void)
 176 {
 177         NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
 178         pthread_mutex_t plock = PTHREAD_MUTEX_INITIALIZER;
 179         OSSpinLock slock = OS_SPINLOCK_INIT;
 180         BasicObject *bo;
 181         BasicClass *bc;
 182         pthread_t pthr_pause;
 183         dispatch_queue_t q, mq;
 184         kern_return_t kr;
 185         semaphore_t sem;
 186         uint64_t freq;
 187         uint64_t s;
 188         size_t freq_len = sizeof(freq);
 189         size_t bf_cnt = cnt;
 190         unsigned i;
 191         int r;
 192
 193         r = sysctlbyname("hw.cpufrequency", &freq, &freq_len, NULL, 0);
 194         assert(r != -1);
 195         assert(freq_len == sizeof(freq));
 196
 197         cycles_per_nanosecond = (long double)freq / (long double)NSEC_PER_SEC;
 198
 199         assert(pool);
 200
 201         /* Malloc has different logic for threaded apps. */
 202         r = pthread_create(&pthr_pause, NULL, force_a_thread, NULL);
 203         assert(r == 0);
 204
 205         kr = mach_timebase_info(&tbi);
 206         assert(kr == 0);
 207 #if defined(__i386__) || defined(__x86_64__)
 208         assert(tbi.numer == tbi.denom); /* This will fail on PowerPC. */
 209 #endif
 210
 211         bo = [[BasicObject alloc] init];
 212         assert(bo);
 213
 214         bc = new BasicClass();
 215         assert(bc);
 216
 217         q = dispatch_queue_create("com.apple.bench-dispatch", NULL);
 218         assert(q);
 219
 220         mq = dispatch_get_main_queue();
 221         assert(mq);
 222
 223         printf("%-45s%15Lf\n\n", "Cycles per nanosecond:", cycles_per_nanosecond);
 224
 225         s = mach_absolute_time();
 226         for (i = cnt; i; i--) {
 227                 asm volatile("");
 228         }
 229         print_result(s, "Empty loop:");
 230
 231         printf("\nLoop cost subtracted from the following:\n\n");
 232
 233         s = mach_absolute_time();
 234         for (i = cnt; i; i--) {
 235                 mach_absolute_time();
 236         }
 237         print_result(s, "mach_absolute_time():");
 238
 239 #if defined(__i386__) || defined(__x86_64__)
 240         s = mach_absolute_time();
 241         for (i = cnt; i; i--) {
 242                 rdtsc();
 243         }
 244         print_result(s, "rdtsc():");
 245 #endif
 246
 247         s = mach_absolute_time();
 248         for (i = cnt2; i; i--) {
 249                 pthread_t pthr;
 250                 void *pr;
 251
 252                 r = pthread_create(&pthr, NULL, (void *(*)(void *))func, NULL);
 253                 assert(r == 0);
 254                 r = pthread_join(pthr, &pr);
 255                 assert(r == 0);
 256         }
 257         print_result2(s, "pthread create+join:");
 258
 259         s = mach_absolute_time();
 260         for (i = cnt2; i; i--) {
 261                 kr = semaphore_create(mach_task_self(), &sem, SYNC_POLICY_FIFO, 0);
 262                 assert(kr == 0);
 263                 kr = semaphore_destroy(mach_task_self(), sem);
 264                 assert(kr == 0);
 265         }
 266         print_result2(s, "Mach semaphore create/destroy:");
 267
 268         kr = semaphore_create(mach_task_self(), &sem, SYNC_POLICY_FIFO, 0);
 269         assert(kr == 0);
 270         s = mach_absolute_time();
 271         for (i = cnt2; i; i--) {
 272                 kr = semaphore_signal(sem);
 273                 assert(kr == 0);
 274         }
 275         print_result2(s, "Mach semaphore signal:");
 276         kr = semaphore_destroy(mach_task_self(), sem);
 277         assert(kr == 0);
 278
 279         s = mach_absolute_time();
 280         for (i = cnt; i; i--) {
 281                 pthread_yield_np();
 282         }
 283         print_result(s, "pthread_yield_np():");
 284
 285         s = mach_absolute_time();
 286         for (i = cnt; i; i--) {
 287                 free(malloc(32));
 288         }
 289         print_result(s, "free(malloc(32)):");
 290
 291         s = mach_absolute_time();
 292         for (i = cnt / 2; i; i--) {
 293                 void *m1 = malloc(32);
 294                 void *m2 = malloc(32);
 295                 free(m1);
 296                 free(m2);
 297         }
 298         print_result(s, "Avoiding the MRU cache of free(malloc(32)):");
 299
 300         s = mach_absolute_time();
 301         for (i = cnt; i; i--) {
 302                 fixed_free_lifo(fixed_malloc_lifo());
 303         }
 304         print_result(s, "per-thread/fixed free(malloc(32)):");
 305
 306         s = mach_absolute_time();
 307         for (i = cnt; i; i--) {
 308                 assert(strtoull("18446744073709551615", NULL, 0) == ~0ull);
 309         }
 310         print_result(s, "strtoull(\"18446744073709551615\") == ~0ull:");
 311
 312         s = mach_absolute_time();
 313         for (i = cnt; i; i--) {
 314                 func();
 315         }
 316         print_result(s, "Empty function call:");
 317
 318 #ifdef __BLOCKS__
 319         s = mach_absolute_time();
 320         for (i = cnt; i; i--) {
 321                 block();
 322         }
 323         print_result(s, "Empty block call:");
 324 #endif
 325
 326         s = mach_absolute_time();
 327         for (i = cnt; i; i--) {
 328                 [bo method];
 329         }
 330         print_result(s, "Empty ObjC call:");
 331
 332         s = mach_absolute_time();
 333         for (i = cnt; i; i--) {
 334                 bc->virtfunc();
 335         }
 336         print_result(s, "Empty C++ virtual call:");
 337
 338         s = mach_absolute_time();
 339         for (i = cnt2; i; i--) {
 340                 [bo description];
 341         }
 342         print_result2(s, "\"description\" ObjC call:");
 343
 344         [pool release];
 345
 346         pool = NULL;
 347
 348 #if defined(__i386__) || defined(__x86_64__)
 349         s = mach_absolute_time();
 350         for (i = cnt; i; i--) {
 351                 asm("nop");
 352         }
 353         print_result(s, "raw 'nop':");
 354
 355         s = mach_absolute_time();
 356         for (i = cnt; i; i--) {
 357                 asm("pause");
 358         }
 359         print_result(s, "raw 'pause':");
 360
 361         s = mach_absolute_time();
 362         for (i = cnt; i; i--) {
 363                 asm("mfence");
 364         }
 365         print_result(s, "Atomic mfence:");
 366
 367         s = mach_absolute_time();
 368         for (i = cnt; i; i--) {
 369                 asm("lfence");
 370         }
 371         print_result(s, "Atomic lfence:");
 372
 373         s = mach_absolute_time();
 374         for (i = cnt; i; i--) {
 375                 asm("sfence");
 376         }
 377         print_result(s, "Atomic sfence:");
 378
 379         s = mach_absolute_time();
 380         for (i = cnt; i; i--) {
 381                 uint64_t sidt_rval;
 382                 asm("sidt %0" : "=m" (sidt_rval));
 383         }
 384         print_result(s, "'sidt' instruction:");
 385
 386         s = mach_absolute_time();
 387         for (i = cnt; i; i--) {
 388                 int prev;
 389                 asm volatile("cmpxchg %1,%2" : "=a" (prev) : "r" (0l), "m" (global), "0" (1l));
 390         }
 391         print_result(s, "'cmpxchg' without the 'lock' prefix:");
 392 #endif
 393
 394         s = mach_absolute_time();
 395         for (i = cnt; i; i--) {
 396                 __sync_lock_test_and_set(&global, 0);
 397         }
 398         print_result(s, "Atomic xchg:");
 399
 400         s = mach_absolute_time();
 401         for (i = cnt; i; i--) {
 402                 __sync_val_compare_and_swap(&global, 1, 0);
 403         }
 404         print_result(s, "Atomic cmpxchg:");
 405
 406         s = mach_absolute_time();
 407         for (i = cnt; i; i--) {
 408                 __sync_fetch_and_add(&global, 1);
 409         }
 410         print_result(s, "Atomic increment:");
 411
 412         global = 0;
 413
 414         s = mach_absolute_time();
 415         for (i = cnt; i; i--) {
 416                 OSAtomicIncrement32Barrier(&global);
 417         }
 418         print_result(s, "OSAtomic increment:");
 419
 420         global = 0;
 421
 422         s = mach_absolute_time();
 423         for (i = cnt; i; i--) {
 424                 while (!__sync_bool_compare_and_swap(&global, 0, 1)) {
 425                         do {
 426 #if defined(__i386__) || defined(__x86_64__)
 427                                 asm("pause");
 428 #endif
 429                         } while (global);
 430                 }
 431                 global = 0;
 432         }
 433         print_result(s, "Inlined spin lock/unlock:");
 434
 435         s = mach_absolute_time();
 436         for (i = cnt; i; i--) {
 437                 OSSpinLockLock(&slock);
 438                 OSSpinLockUnlock(&slock);
 439         }
 440         print_result(s, "OS spin lock/unlock:");
 441
 442         s = mach_absolute_time();
 443         for (i = cnt; i; i--) {
 444                 r = pthread_mutex_lock(&plock);
 445                 assert(r == 0);
 446                 r = pthread_mutex_unlock(&plock);
 447                 assert(r == 0);
 448         }
 449         print_result(s, "pthread lock/unlock:");
 450
 451 #ifdef __BLOCKS__
 452         s = mach_absolute_time();
 453         for (i = cnt; i; i--) {
 454                 dispatch_sync(q, ^{ });
 455         }
 456         print_result(s, "dispatch_sync:");
 457 #endif
 458
 459         s = mach_absolute_time();
 460         for (i = cnt; i; i--) {
 461                 dispatch_sync_f(q, NULL, (void (*)(void *))func);
 462         }
 463         print_result(s, "dispatch_sync_f:");
 464
 465 #ifdef __BLOCKS__
 466         s = mach_absolute_time();
 467         for (i = cnt; i; i--) {
 468                 dispatch_barrier_sync(q, ^{ });
 469         }
 470         print_result(s, "dispatch_barrier_sync:");
 471 #endif
 472
 473         s = mach_absolute_time();
 474         for (i = cnt; i; i--) {
 475                 dispatch_barrier_sync_f(q, NULL, (void (*)(void *))func);
 476         }
 477         print_result(s, "dispatch_barrier_sync_f:");
 478
 479         s = mach_absolute_time();
 480         dispatch_apply_f(cnt, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), NULL, (void (*)(void *, size_t))func);
 481         s += loop_cost; /* cancel out the implicit subtraction done by the next line */
 482         print_result(s, "dispatch_apply_f():");
 483
 484         // we do a "double backflip" to hit the fast-path of the enqueue/dequeue logic
 485         bfs = mach_absolute_time();
 486         dispatch_async_f(dispatch_get_main_queue(), &bf_cnt, backflip);
 487         dispatch_async_f(dispatch_get_main_queue(), &bf_cnt, backflip);
 488
 489         dispatch_main();
 490 }
 491
 492 __attribute__((noinline))
 493 void
 494 backflip_done(void)
 495 {
 496         print_result(bfs, "dispatch_async_f():");
 497         exit(EXIT_SUCCESS);
 498 }
 499
 500 void
 501 backflip(void *ctxt)
 502 {
 503         size_t *bf_cnt = (size_t *)ctxt;
 504         if (--(*bf_cnt)) {
 505                 return dispatch_async_f(dispatch_get_main_queue(), ctxt, backflip);
 506         }
 507         backflip_done();
 508 }