1/* 2 * Copyright 2013 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#include "SkBenchmark.h" 9#include "SkRandom.h" 10#include "SkTSort.h" 11#include "SkString.h" 12 13#ifdef SK_DEBUG 14// Windows-debug builds (at least) don't implement tail-recursion, and we have 15// a bench that triggers a worst-case behavior in SkTQSort (w/ repeated keys) 16// which can overflow the stack if N is too big. So we reduce it for debug 17// builds (for which we don't care about sorting performance anyways). 18static const int N = 100; 19#else 20static const int N = 1000; 21#endif 22 23static void rand_proc(int array[], int count) { 24 SkRandom rand; 25 for (int i = 0; i < count; ++i) { 26 array[i] = rand.nextS(); 27 } 28} 29 30static void randN_proc(int array[], int count) { 31 SkRandom rand; 32 int mod = N / 10; 33 for (int i = 0; i < count; ++i) { 34 array[i] = rand.nextU() % mod; 35 } 36} 37 38static void forward_proc(int array[], int count) { 39 for (int i = 0; i < count; ++i) { 40 array[i] = i; 41 } 42} 43 44static void backward_proc(int array[], int count) { 45 for (int i = 0; i < count; ++i) { 46 array[i] = -i; 47 } 48} 49 50static void same_proc(int array[], int count) { 51 for (int i = 0; i < count; ++i) { 52 array[i] = count; 53 } 54} 55 56typedef void (*SortProc)(int array[], int count); 57 58enum Type { 59 kRand, kRandN, kFore, kBack, kSame 60}; 61 62static const struct { 63 const char* fName; 64 SortProc fProc; 65} gRec[] = { 66 { "rand", rand_proc }, 67 { "rand10", randN_proc }, 68 { "forward", forward_proc }, 69 { "backward", backward_proc }, 70 { "repeated", same_proc }, 71}; 72 73static void skqsort_sort(int array[], int count) { 74 SkTQSort<int>(array, array + count); 75} 76 77static void skheap_sort(int array[], int count) { 78 SkTHeapSort<int>(array, count); 79} 80 81extern "C" { 82 static int int_compare(const void* a, const void* b) { 83 const int ai = *(const int*)a; 84 const int bi = *(const int*)b; 85 return ai < bi ? -1 : (ai > bi); 86 } 87} 88 89static void qsort_sort(int array[], int count) { 90 qsort(array, count, sizeof(int), int_compare); 91} 92 93enum SortType { 94 kSKQSort, kSKHeap, kQSort 95}; 96 97static const struct { 98 const char* fName; 99 SortProc fProc; 100} gSorts[] = { 101 { "skqsort", skqsort_sort }, 102 { "skheap", skheap_sort }, 103 { "qsort", qsort_sort }, 104}; 105 106class SortBench : public SkBenchmark { 107 SkString fName; 108 enum { MAX = 100000 }; 109 int fUnsorted[MAX]; 110 int fSorted[MAX]; 111 int fCount; 112 SortProc fSortProc; 113 114public: 115 SortBench(void* param, Type t, int n, SortType s) : INHERITED(param) { 116 if (n > MAX) { 117 n = MAX; 118 } 119 fName.printf("sort_%s_%s", gSorts[s].fName, gRec[t].fName); 120 fCount = n; 121 gRec[t].fProc(fUnsorted, n); 122 fSortProc = gSorts[s].fProc; 123 fIsRendering = false; 124 } 125 126protected: 127 virtual const char* onGetName() SK_OVERRIDE { 128 return fName.c_str(); 129 } 130 131 virtual void onDraw(SkCanvas* canvas) { 132 int n = SkBENCHLOOP(200); 133 for (int i = 0; i < n; i++) { 134 memcpy(fSorted, fUnsorted, fCount * sizeof(int)); 135 fSortProc(fSorted, fCount); 136#ifdef SK_DEBUG 137 for (int j = 1; j < fCount; ++j) { 138 SkASSERT(fSorted[j - 1] <= fSorted[j]); 139 } 140#endif 141 } 142 } 143 144private: 145 typedef SkBenchmark INHERITED; 146}; 147 148/////////////////////////////////////////////////////////////////////////////// 149 150static SkBenchmark* NewSkQSort(void* param, Type t) { 151 return new SortBench(param, t, N, kSKQSort); 152} 153static SkBenchmark* NewSkHeap(void* param, Type t) { 154 return new SortBench(param, t, N, kSKHeap); 155} 156static SkBenchmark* NewQSort(void* param, Type t) { 157 return new SortBench(param, t, N, kQSort); 158} 159 160DEF_BENCH( return NewSkQSort(p, kRand); ) 161DEF_BENCH( return NewSkHeap(p, kRand); ) 162DEF_BENCH( return NewQSort(p, kRand); ) 163 164DEF_BENCH( return NewSkQSort(p, kRandN); ) 165DEF_BENCH( return NewSkHeap(p, kRandN); ) 166DEF_BENCH( return NewQSort(p, kRandN); ) 167 168DEF_BENCH( return NewSkQSort(p, kFore); ) 169DEF_BENCH( return NewSkHeap(p, kFore); ) 170DEF_BENCH( return NewQSort(p, kFore); ) 171 172DEF_BENCH( return NewSkQSort(p, kBack); ) 173DEF_BENCH( return NewSkHeap(p, kBack); ) 174DEF_BENCH( return NewQSort(p, kBack); ) 175 176DEF_BENCH( return NewSkQSort(p, kSame); ) 177DEF_BENCH( return NewSkHeap(p, kSame); ) 178DEF_BENCH( return NewQSort(p, kSame); ) 179