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