SortBench.cpp 4.3 KB

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