| 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) |