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