Debian Codegraph @

Tools/scripts/sortperf.py

raw
1 """
2 List sort performance test.
3
4 To install `pyperf` you would need to:
5
6 python3 -m pip install pyperf
7
8 To run:
9
10 python3 Tools/scripts/sortperf
11
12 Options:
13
14 * `benchmark` name to run
15 * `--rnd-seed` to set random seed
16 * `--size` to set the sorted list size
17
18 Based on https://github.com/python/cpython/blob/963904335e579bfe39101adf3fd6a0cf705975ff/Lib/test/sortperf.py
19 """
20
21 from __future__ import annotations
22
23 import argparse
24 import time
25 import random
26
27
28 # ===============
29 # Data generation
30 # ===============
31
32 def _random_data(size: int, rand: random.Random) -> list[float]:
33 result = [rand.random() for _ in range(size)]
34 # Shuffle it a bit...
35 for i in range(10):
36 i = rand.randrange(size)
37 temp = result[:i]
38 del result[:i]
39 temp.reverse()
40 result.extend(temp)
41 del temp
42 assert len(result) == size
43 return result
44
45
46 def list_sort(size: int, rand: random.Random) -> list[float]:
47 return _random_data(size, rand)
48
49
50 def list_sort_descending(size: int, rand: random.Random) -> list[float]:
51 return list(reversed(list_sort_ascending(size, rand)))
52
53
54 def list_sort_ascending(size: int, rand: random.Random) -> list[float]:
55 return sorted(_random_data(size, rand))
56
57
58 def list_sort_ascending_exchanged(size: int, rand: random.Random) -> list[float]:
59 result = list_sort_ascending(size, rand)
60 # Do 3 random exchanges.
61 for _ in range(3):
62 i1 = rand.randrange(size)
63 i2 = rand.randrange(size)
64 result[i1], result[i2] = result[i2], result[i1]
65 return result
66
67
68 def list_sort_ascending_random(size: int, rand: random.Random) -> list[float]:
69 assert size >= 10, "This benchmark requires size to be >= 10"
70 result = list_sort_ascending(size, rand)
71 # Replace the last 10 with random floats.
72 result[-10:] = [rand.random() for _ in range(10)]
73 return result
74
75
76 def list_sort_ascending_one_percent(size: int, rand: random.Random) -> list[float]:
77 result = list_sort_ascending(size, rand)
78 # Replace 1% of the elements at random.
79 for _ in range(size // 100):
80 result[rand.randrange(size)] = rand.random()
81 return result
82
83
84 def list_sort_duplicates(size: int, rand: random.Random) -> list[float]:
85 assert size >= 4
86 result = list_sort_ascending(4, rand)
87 # Arrange for lots of duplicates.
88 result = result * (size // 4)
89 # Force the elements to be distinct objects, else timings can be
90 # artificially low.
91 return list(map(abs, result))
92
93
94 def list_sort_equal(size: int, rand: random.Random) -> list[float]:
95 # All equal. Again, force the elements to be distinct objects.
96 return list(map(abs, [-0.519012] * size))
97
98
99 def list_sort_worst_case(size: int, rand: random.Random) -> list[float]:
100 # This one looks like [3, 2, 1, 0, 0, 1, 2, 3]. It was a bad case
101 # for an older implementation of quicksort, which used the median
102 # of the first, last and middle elements as the pivot.
103 half = size // 2
104 result = list(range(half - 1, -1, -1))
105 result.extend(range(half))
106 # Force to float, so that the timings are comparable. This is
107 # significantly faster if we leave them as ints.
108 return list(map(float, result))
109
110
111 # =========
112 # Benchmark
113 # =========
114
115 class Benchmark:
116 def __init__(self, name: str, size: int, seed: int) -> None:
117 self._name = name
118 self._size = size
119 self._seed = seed
120 self._random = random.Random(self._seed)
121
122 def run(self, loops: int) -> float:
123 all_data = self._prepare_data(loops)
124 start = time.perf_counter()
125
126 for data in all_data:
127 data.sort() # Benching this method!
128
129 return time.perf_counter() - start
130
131 def _prepare_data(self, loops: int) -> list[float]:
132 bench = BENCHMARKS[self._name]
133 data = bench(self._size, self._random)
134 return [data.copy() for _ in range(loops)]
135
136
137 def add_cmdline_args(cmd: list[str], args) -> None:
138 if args.benchmark:
139 cmd.append(args.benchmark)
140 cmd.append(f"--size={args.size}")
141 cmd.append(f"--rng-seed={args.rng_seed}")
142
143
144 def add_parser_args(parser: argparse.ArgumentParser) -> None:
145 parser.add_argument(
146 "benchmark",
147 choices=BENCHMARKS,
148 nargs="?",
149 help="Can be any of: {0}".format(", ".join(BENCHMARKS)),
150 )
151 parser.add_argument(
152 "--size",
153 type=int,
154 default=DEFAULT_SIZE,
155 help=f"Size of the lists to sort (default: {DEFAULT_SIZE})",
156 )
157 parser.add_argument(
158 "--rng-seed",
159 type=int,
160 default=DEFAULT_RANDOM_SEED,
161 help=f"Random number generator seed (default: {DEFAULT_RANDOM_SEED})",
162 )
163
164
165 DEFAULT_SIZE = 1 << 14
166 DEFAULT_RANDOM_SEED = 0
167 BENCHMARKS = {
168 "list_sort": list_sort,
169 "list_sort_descending": list_sort_descending,
170 "list_sort_ascending": list_sort_ascending,
171 "list_sort_ascending_exchanged": list_sort_ascending_exchanged,
172 "list_sort_ascending_random": list_sort_ascending_random,
173 "list_sort_ascending_one_percent": list_sort_ascending_one_percent,
174 "list_sort_duplicates": list_sort_duplicates,
175 "list_sort_equal": list_sort_equal,
176 "list_sort_worst_case": list_sort_worst_case,
177 }
178
179 if __name__ == "__main__":
180 # This needs `pyperf` 3rd party library:
181 import pyperf
182
183 runner = pyperf.Runner(add_cmdline_args=add_cmdline_args)
184 add_parser_args(runner.argparser)
185 args = runner.parse_args()
186
187 runner.metadata["description"] = "Test `list.sort()` with different data"
188 runner.metadata["list_sort_size"] = args.size
189 runner.metadata["list_sort_random_seed"] = args.rng_seed
190
191 if args.benchmark:
192 benchmarks = (args.benchmark,)
193 else:
194 benchmarks = sorted(BENCHMARKS)
195 for bench in benchmarks:
196 benchmark = Benchmark(bench, args.size, args.rng_seed)
197 runner.bench_time_func(bench, benchmark.run)