NAME
Bencher::Scenario::SortingByKey - Benchmark various techniques to sort array by some computed key
VERSION
This document describes version 0.001 of Bencher::Scenario::SortingByKey (from Perl distribution Bencher-Scenario-SortingByKey), released on 2019-12-25.
SYNOPSIS
To run benchmark with default option:
% bencher -m SortingByKeyTo run module startup overhead benchmark:
% bencher --module-startup -m SortingByKeyFor more options (dump scenario, list/include/exclude/add participants, list/include/exclude/add datasets, etc), see bencher or run bencher --help.
DESCRIPTION
Packaging a benchmark script as a Bencher scenario makes it convenient to include/exclude/add participants/datasets (either via CLI or Perl code), send the result to a central repository, among others . See Bencher and bencher (CLI) for more details.
BENCHMARKED MODULES
Version numbers shown below are the versions used when running the sample benchmark.
Sort::Key 1.33
BENCHMARK PARTICIPANTS
uncached (perl_code)
Code template:
state $array=<array>; sort { -$a <=> -$b } @$arrayST (perl_code)
Code template:
state $array=<array>; map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [$_, -$_] } @$arrayGRT (perl_code)
Code template:
state $array=<array>; map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [$_, -$_] } @$array2array (perl_code)
Code template:
state $array=<array>; my @keys = map { -$_ } @$array; my @indexes = 0..$#{$array}; map { $array->[$_] } sort { $keys[$a] <=> $keys[$b] } @indexesSort::Key::nkeysort (perl_code)
Code template:
state $array=<array>; Sort::Key::nkeysort(sub { -$_ }, @$array)
BENCHMARK DATASETS
10
100
1000
10000
SAMPLE BENCHMARK RESULTS
Run on: perl: v5.30.0, CPU: Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz (2 cores), OS: GNU/Linux Ubuntu version 19.04, OS kernel: Linux version 5.0.0-37-generic.
Benchmark with default options (bencher -m SortingByKey):
#table1#
+---------------------+---------+-----------+------------+------------+---------+---------+
| participant | dataset | rate (/s) | time (ms) | vs_slowest | errors | samples |
+---------------------+---------+-----------+------------+------------+---------+---------+
| ST | 10000 | 63 | 16 | 1 | 4.6e-05 | 21 |
| GRT | 10000 | 63 | 16 | 1 | 5e-05 | 20 |
| 2array | 10000 | 110 | 9.1 | 1.7 | 1.5e-05 | 20 |
| Sort::Key::nkeysort | 10000 | 326 | 3.07 | 5.19 | 2.9e-06 | 20 |
| GRT | 1000 | 867 | 1.15 | 13.8 | 6.9e-07 | 20 |
| ST | 1000 | 888 | 1.13 | 14.1 | 6.9e-07 | 20 |
| 2array | 1000 | 1560 | 0.64 | 24.8 | 2.7e-07 | 20 |
| Sort::Key::nkeysort | 1000 | 3820 | 0.262 | 60.8 | 2.1e-07 | 20 |
| ST | 100 | 12533 | 0.0797893 | 199.268 | 6.4e-11 | 20 |
| GRT | 100 | 13000 | 0.079 | 200 | 1.1e-07 | 20 |
| 2array | 100 | 21800 | 0.0459 | 346 | 1.3e-08 | 21 |
| Sort::Key::nkeysort | 100 | 51420 | 0.01945 | 817.5 | 2.2e-10 | 20 |
| uncached | 10000 | 150000 | 0.00667 | 2380 | 3.1e-09 | 23 |
| ST | 10 | 200000 | 0.005 | 3180 | 1.7e-09 | 20 |
| GRT | 10 | 201000 | 0.00497 | 3200 | 1.6e-09 | 22 |
| 2array | 10 | 318710 | 0.0031376 | 5067.4 | 2.3e-11 | 23 |
| Sort::Key::nkeysort | 10 | 505400 | 0.001979 | 8035 | 1.5e-10 | 20 |
| uncached | 1000 | 1464000 | 0.0006831 | 23270 | 3.7e-11 | 20 |
| uncached | 100 | 9900000 | 0.0001 | 160000 | 2.1e-10 | 20 |
| uncached | 10 | 25000000 | 0.00004 | 390000 | 7.5e-11 | 20 |
+---------------------+---------+-----------+------------+------------+---------+---------+Benchmark module startup overhead (bencher -m SortingByKey --module-startup):
#table2#
+---------------------+-----------+------------------------+------------+---------+---------+
| participant | time (ms) | mod_overhead_time (ms) | vs_slowest | errors | samples |
+---------------------+-----------+------------------------+------------+---------+---------+
| Sort::Key | 14 | 7.1 | 1 | 1.7e-05 | 20 |
| perl -e1 (baseline) | 6.9 | 0 | 2 | 1.9e-05 | 20 |
+---------------------+-----------+------------------------+------------+---------+---------+To display as an interactive HTML table on a browser, you can add option --format html+datatables.
HOMEPAGE
Please visit the project's homepage at https://metacpan.org/release/Bencher-Scenario-SortingByKey.
SOURCE
Source repository is at https://github.com/perlancar/perl-Bencher-Scenario-SortingByKey.
BUGS
Please report any bugs or feature requests on the bugtracker website https://rt.cpan.org/Public/Dist/Display.html?Name=Bencher-Scenario-SortingByKey
When submitting a bug or request, please include a test-file or a patch to an existing test-file that illustrates the bug or desired feature.
SEE ALSO
Guttman, U., & Rosler, L. (2003). A fresh look at efficient perl sorting. http://www.sysarch.com/Perl/sort_paper.html. This is the original paper that mentions GRT.
https://www.perlmonks.org/?node_id=145659
https://www.perlmonks.org/?node_id=287149
Sort::Maker, also by Uri Guttman, describes the various sort techniques (ST, GRT, etc).
Sort::Key by Salvador Fandiño García.
AUTHOR
perlancar <perlancar@cpan.org>
COPYRIGHT AND LICENSE
This software is copyright (c) 2019 by perlancar@cpan.org.
This is free software; you can redistribute it and/or modify it under the same terms as the Perl 5 programming language system itself.