codekingpro/portable-devtools

1"""2List sort performance test.3 4To install `pyperf` you would need to:5 6    python3 -m pip install pyperf7 8To run:9 10    python3 Tools/scripts/sortperf11 12Options:13 14    * `benchmark` name to run15    * `--rnd-seed` to set random seed16    * `--size` to set the sorted list size17 18Based on https://github.com/python/cpython/blob/963904335e579bfe39101adf3fd6a0cf705975ff/Lib/test/sortperf.py19"""20 21from __future__ import annotations22 23import argparse24import time25import random26 27 28# ===============29# Data generation30# ===============31 32def _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 temp42    assert len(result) == size43    return result44 45 46def list_sort(size: int, rand: random.Random) -> list[float]:47    return _random_data(size, rand)48 49 50def list_sort_descending(size: int, rand: random.Random) -> list[float]:51    return list(reversed(list_sort_ascending(size, rand)))52 53 54def list_sort_ascending(size: int, rand: random.Random) -> list[float]:55    return sorted(_random_data(size, rand))56 57 58def 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 result66 67 68def 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 result74 75 76def 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 result82 83 84def list_sort_duplicates(size: int, rand: random.Random) -> list[float]:85    assert size >= 486    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 be90    # artificially low.91    return list(map(abs, result))92 93 94def 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 99def 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 case101    # for an older implementation of quicksort, which used the median102    # of the first, last and middle elements as the pivot.103    half = size // 2104    result = list(range(half - 1, -1, -1))105    result.extend(range(half))106    # Force to float, so that the timings are comparable.  This is107    # significantly faster if we leave them as ints.108    return list(map(float, result))109 110 111# =========112# Benchmark113# =========114 115class Benchmark:116    def __init__(self, name: str, size: int, seed: int) -> None:117        self._name = name118        self._size = size119        self._seed = seed120        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() - start130 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 137def 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 144def 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 165DEFAULT_SIZE = 1 << 14166DEFAULT_RANDOM_SEED = 0167BENCHMARKS = {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 179if __name__ == "__main__":180    # This needs `pyperf` 3rd party library:181    import pyperf182 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.size189    runner.metadata["list_sort_random_seed"] = args.rng_seed190 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)198