Sorting benchmarks.

1 files changed, 106 insertions, 28 deletions

diff --git a/benchmarks/benchmarks/bench_function_base.py b/benchmarks/benchmarks/bench_function_base.py
index 64e578680..2f5808b1a 100644
--- a/benchmarks/benchmarks/bench_function_base.py
+++ b/benchmarks/benchmarks/bench_function_base.py
@@ -98,44 +98,122 @@ class Select(Benchmark):
 class Sort(Benchmark):
     params = [
         ['quick', 'merge', 'heap'],
-        ['float32', 'int32', 'uint32']
+        ['float32', 'int32', 'uint32'],
+        [
+            'ordered',
+            'reversed',
+            'uniform',
+            'sorted_block_10',
+            'sorted_block_100',
+            'sorted_block_1000',
+            'swapped_pair_1_percent',
+            'swapped_pair_10_percent',
+            'swapped_pair_50_percent',
+            'random_unsorted_area_50_percent',
+            'random_unsorted_area_10_percent',
+            'random_unsorted_area_1_percent',
+            'random_bubble_1_fold',
+            'random_bubble_5_fold',
+            'random_bubble_10_fold',
+        ],
     ]
-    param_names = ['kind', 'dtype']
+    param_names = ['kind', 'dtype', 'array_type']
 
-    def setup(self, kind, dtype):
-        self.e = np.arange(10000, dtype=dtype)
-        self.o = np.arange(10001, dtype=dtype)
-        np.random.seed(25)
-        np.random.shuffle(self.o)
-        # quicksort implementations can have issues with equal elements
-        self.equal = np.ones(10000, dtype=dtype)
-        self.many_equal = np.sort(np.arange(10000) % 10).astype(dtype)
+    ARRAY_SIZE = 10000
 
-        try:
-            np.sort(self.e, kind=kind)
-        except TypeError:
-            raise NotImplementedError()
+    def setup(self, kind, dtype, array_type):
+        np.random.seed(1234)
+        self.arr = getattr(self, 'array_' + array_type)(self.ARRAY_SIZE, dtype)
 
-    def time_sort(self, kind, dtype):
-        np.sort(self.e, kind=kind)
+    def time_sort_inplace(self, kind, dtype, array_type):
+        self.arr.sort(kind=kind)
 
-    def time_sort_random(self, kind, dtype):
-        np.sort(self.o, kind=kind)
+    def time_sort(self, kind, dtype, array_type):
+        np.sort(self.arr, kind=kind)
 
-    def time_sort_inplace(self, kind, dtype):
-        self.e.sort(kind=kind)
+    def time_argsort(self, kind, dtype, array_type):
+        np.argsort(self.arr, kind=kind)
 
-    def time_sort_equal(self, kind, dtype):
-        self.equal.sort(kind=kind)
+    def array_random(self, size, dtype):
+        arr = np.arange(size, dtype=dtype)
+        np.random.shuffle(arr)
+        return arr
+    
+    def array_ordered(self, size, dtype):
+        return np.arange(size, dtype=dtype)
 
-    def time_sort_many_equal(self, kind, dtype):
-        self.many_equal.sort(kind=kind)
+    def array_reversed(self, size, dtype):
+        return np.arange(size-1, -1, -1, dtype=dtype)
 
-    def time_argsort(self, kind, dtype):
-        self.e.argsort(kind=kind)
+    def array_uniform(self, size, dtype):
+        return np.ones(size, dtype=dtype)
 
-    def time_argsort_random(self, kind, dtype):
-        self.o.argsort(kind=kind)
+    def array_sorted_block_10(self, size, dtype):
+        return self.sorted_block(size, dtype, 10)
+
+    def array_sorted_block_100(self, size, dtype):
+        return self.sorted_block(size, dtype, 100)
+
+    def array_sorted_block_1000(self, size, dtype):
+        return self.sorted_block(size, dtype, 1000)
+
+    def array_swapped_pair_1_percent(self, size, dtype):
+        return self.swapped_pair(size, dtype, 0.01)
+
+    def array_swapped_pair_10_percent(self, size, dtype):
+        return self.swapped_pair(size, dtype, 0.1)
+
+    def array_swapped_pair_50_percent(self, size, dtype):
+        return self.swapped_pair(size, dtype, 0.5)
+
+    AREA_SIZE = 10
+
+    def array_random_unsorted_area_50_percent(self, size, dtype):
+        return self.random_unsorted_area(size, dtype, 0.5, self.AREA_SIZE)
+
+    def array_random_unsorted_area_10_percent(self, size, dtype):
+        return self.random_unsorted_area(size, dtype, 0.1, self.AREA_SIZE)
+
+    def array_random_unsorted_area_1_percent(self, size, dtype):
+        return self.random_unsorted_area(size, dtype, 0.01, self.AREA_SIZE)
+
+    BUBBLE_SIZE = 10
+
+    def array_random_bubble_1_fold(self, size, dtype):
+        return self.random_unsorted_area(size, dtype, 1, size / self.BUBBLE_SIZE)
+
+    def array_random_bubble_5_fold(self, size, dtype):
+        return self.random_unsorted_area(size, dtype, 5, size / self.BUBBLE_SIZE)
+
+    def array_random_bubble_10_fold(self, size, dtype):
+        return self.random_unsorted_area(size, dtype, 10, size / self.BUBBLE_SIZE)
+
+    def swapped_pair(self, size, dtype, swap_frac):
+        a = np.arange(size, dtype=dtype)
+        for _ in range(int(size * swap_frac)):
+            x, y = np.random.randint(0, size, 2)
+            a[x], a[y] = a[y], a[x]
+        return a
+
+    def sorted_block(self, size, dtype, block_size):
+        a = np.arange(size, dtype=dtype)
+        b = []
+        if size < block_size:
+            return a
+        block_num = size // block_size
+        for i in range(block_num):
+            b.extend(a[i::block_num])
+        return np.array(b)
+
+    def random_unsorted_area(self, size, dtype, frac, area_num):
+        area_num = int(area_num)
+        a = np.arange(size, dtype=dtype)
+        unsorted_len = int(size * frac / area_num)
+        for _ in range(area_num):
+            start = np.random.randint(size-unsorted_len)
+            end = start + unsorted_len
+            np.random.shuffle(a[start:end])
+        return a
 
 
 class SortWorst(Benchmark):