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 "Benchmark.h"
9#include "SkRandom.h"
10#include "SkString.h"
11#include "SkTSort.h"
12
13static const int N = 1000;
14
15static void rand_proc(int array[N]) {
16    SkRandom rand;
17    for (int i = 0; i < N; ++i) {
18        array[i] = rand.nextS();
19    }
20}
21
22static void randN_proc(int array[N]) {
23    SkRandom rand;
24    int mod = N / 10;
25    for (int i = 0; i < N; ++i) {
26        array[i] = rand.nextU() % mod;
27    }
28}
29
30static void forward_proc(int array[N]) {
31    for (int i = 0; i < N; ++i) {
32        array[i] = i;
33    }
34}
35
36static void backward_proc(int array[N]) {
37    for (int i = 0; i < N; ++i) {
38        array[i] = -i;
39    }
40}
41
42static void same_proc(int array[N]) {
43    for (int i = 0; i < N; ++i) {
44        array[i] = N;
45    }
46}
47
48typedef void (*SortProc)(int array[N]);
49
50enum Type {
51    kRand, kRandN, kFore, kBack, kSame
52};
53
54static const struct {
55    const char* fName;
56    SortProc    fProc;
57} gRec[] = {
58    { "rand", rand_proc },
59    { "rand10", randN_proc },
60    { "forward", forward_proc },
61    { "backward", backward_proc },
62    { "repeated", same_proc },
63};
64
65static void skqsort_sort(int array[N]) {
66    // End is inclusive for SkTQSort!
67    SkTQSort<int>(array, array + N - 1);
68}
69
70static void skheap_sort(int array[N]) {
71    SkTHeapSort<int>(array, N);
72}
73
74extern "C" {
75    static int int_compare(const void* a, const void* b) {
76        const int ai = *(const int*)a;
77        const int bi = *(const int*)b;
78        return ai < bi ? -1 : (ai > bi);
79    }
80}
81
82static void qsort_sort(int array[N]) {
83    qsort(array, N, sizeof(int), int_compare);
84}
85
86enum SortType {
87    kSKQSort, kSKHeap, kQSort
88};
89
90static const struct {
91    const char* fName;
92    SortProc    fProc;
93} gSorts[] = {
94    { "skqsort", skqsort_sort },
95    { "skheap", skheap_sort },
96    { "qsort", qsort_sort },
97};
98
99class SortBench : public Benchmark {
100    SkString           fName;
101    const Type         fType;
102    const SortProc     fSortProc;
103    SkAutoTMalloc<int> fUnsorted;
104
105public:
106    SortBench(Type t, SortType s) : fType(t), fSortProc(gSorts[s].fProc) {
107        fName.printf("sort_%s_%s", gSorts[s].fName, gRec[t].fName);
108    }
109
110    virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
111        return backend == kNonRendering_Backend;
112    }
113
114protected:
115    virtual const char* onGetName() SK_OVERRIDE {
116        return fName.c_str();
117    }
118
119    // Delayed initialization only done if onDraw will be called.
120    virtual void onPreDraw() SK_OVERRIDE {
121        fUnsorted.reset(N);
122        gRec[fType].fProc(fUnsorted.get());
123    }
124
125    virtual void onDraw(const int loops, SkCanvas*) SK_OVERRIDE {
126        SkAutoTMalloc<int> sorted(N);
127        for (int i = 0; i < loops; i++) {
128            memcpy(sorted.get(), fUnsorted.get(), N*sizeof(int));
129            fSortProc(sorted.get());
130#ifdef SK_DEBUG
131            for (int j = 1; j < N; ++j) {
132                SkASSERT(sorted[j - 1] <= sorted[j]);
133            }
134#endif
135        }
136    }
137
138private:
139    typedef Benchmark INHERITED;
140};
141
142///////////////////////////////////////////////////////////////////////////////
143
144static Benchmark* NewSkQSort(Type t) {
145    return new SortBench(t, kSKQSort);
146}
147static Benchmark* NewSkHeap(Type t) {
148    return new SortBench(t, kSKHeap);
149}
150static Benchmark* NewQSort(Type t) {
151    return new SortBench(t, kQSort);
152}
153
154DEF_BENCH( return NewSkQSort(kRand); )
155DEF_BENCH( return NewSkHeap(kRand); )
156DEF_BENCH( return NewQSort(kRand); )
157
158DEF_BENCH( return NewSkQSort(kRandN); )
159DEF_BENCH( return NewSkHeap(kRandN); )
160DEF_BENCH( return NewQSort(kRandN); )
161
162DEF_BENCH( return NewSkQSort(kFore); )
163DEF_BENCH( return NewSkHeap(kFore); )
164DEF_BENCH( return NewQSort(kFore); )
165
166DEF_BENCH( return NewSkQSort(kBack); )
167DEF_BENCH( return NewSkHeap(kBack); )
168DEF_BENCH( return NewQSort(kBack); )
169
170DEF_BENCH( return NewSkQSort(kSame); )
171DEF_BENCH( return NewSkHeap(kSame); )
172DEF_BENCH( return NewQSort(kSame); )
173