atime: Asymptotic Timing
atime()references_best()atime_versions()atime_pkg()## Install last released version from CRAN:
install.packages("atime")
## Install latest version from GitHub:
if(!require("remotes"))install.packages("remotes")
remotes::install_github("tdhock/atime")
The main function is atime for which you can specify these arguments:
N is numeric vector of data sizes to vary.setup is an expression to evaluate for every data size, before timings.times is the number of times each expression is timed (so we can take the median and ignore outliers).seconds.limit is the max number of seconds. If an expression takes more time, then it will not be timed for larger N values.## When studying asymptotic complexity, always provide sizes on a log
## scale (10^sequence) as below:
(subject.size.vec <- unique(as.integer(10^seq(0,3.5,l=100))))
## Compute asymptotic time and memory measurement:
atime.list <- atime::atime(
N=subject.size.vec,#vector of sizes.
setup={#Run for each size, before timings:
subject <- paste(rep("a", N), collapse="")
pattern <- paste(rep(c("a?", "a"), each=N), collapse="")
},
times=10,#number of timings to compute for each expression.
seconds.limit=0.1,#max seconds per expression.
## Different expressions which will be evaluated for each size N:
PCRE.match=regexpr(pattern, subject, perl=TRUE),
TRE.match=regexpr(pattern, subject, perl=FALSE),
constant.replacement=gsub("a","constant size replacement",subject),
linear.replacement=gsub("a",subject,subject))
atime.list
plot(atime.list)
## Compute and plot asymptotic reference lines:
(best.list <- atime::references_best(atime.list))
plot(best.list)
## Compute and plot data size N for given time/memory.
pred.list <- predict(best.list, seconds=1e-2, kilobytes=10)
plot(pred.list) Time/memory comparison overview
On my machine I got the following results:
> (subject.size.vec <- unique(as.integer(10^seq(0,3.5,l=100)))) [1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [16] 17 18 20 22 23 25 28 30 33 35 38 42 45 49 53 [31] 58 63 68 74 81 87 95 103 112 121 132 143 155 168 183 [46] 198 215 233 253 275 298 323 351 380 413 448 486 527 572 620 [61] 673 730 792 859 932 1011 1097 1190 1291 1401 1519 1648 1788 1940 2104 [76] 2283 2477 2687 2915 3162
The vector above is the sequence of sizes N, used with each expression, to measure time and memory. When studying asymptotic complexity, always provide sizes on a log scale as above.
> atime.list atime list with 228 measurements for PCRE.match(N=1 to 20) TRE.match(N=1 to 275) constant.replacement(N=1 to 3162) linear.replacement(N=1 to 3162)
The output above shows the min and max N values that were run for each of the expressions. In this case constant.replacement and linear.replacement were run all the way up to the max size (3162), but PCRE.match only went up to 20, and TRE.match only went up to 275, because no larger N values are considered after the median time for a given N has has exceeded seconds.limit which is 0.1 above. This behavior ensures that total time taken by atime will be about seconds.limit * times * number of expressions (times is the number of times each expression is evaluated at each data size). The output of the plot method for this atime result list is shown below,
The plot above facilitates comparing the time and memory of the different expressions, and makes it easy to see the ranking of different algorithms, but it does not show the asymptotic complexity class.
Asymptotic complexity class estimationTo estimate the asymptotic complexity class, use the code below:
> (best.list <- atime::references_best(atime.list)) references_best list with 456 measurements, best fit complexity: constant.replacement (N kilobytes, N seconds) linear.replacement (N^2 kilobytes, N^2 seconds) PCRE.match (2^N seconds) TRE.match (N^3 seconds)
The output above shows the best fit asymptotic time complexity for each expression. To visualize the results you can do:
The plot above shows the timings of each expression as a function of data size N (black), as well as the two closest asymptotic reference lines (violet, one smaller, one larger). If you have chosen N and seconds.limit appropriately for your problem (as we have in this case) then you should be able to observe the following:
seconds.limit and the max value in N until you start to see linear trends, and clearly overlapping reference lines (as is the case here).When comparing algorithms in terms of computational resources, we can show
We can do both using the code below,
> atime.list[["measurements"]][N==323, .(expr.name, seconds=median, kilobytes)]
expr.name seconds kilobytes
<char> <num> <num>
1: TRE.match 0.0678032 0.0000
2: constant.replacement 0.0000667 7.9375
3: linear.replacement 0.0002435 101.9375
> pred.list <- predict(best.list, seconds=1e-2, kilobytes=10)
> pred.list[["prediction"]]
unit expr.name unit.value N
<char> <char> <num> <num>
1: seconds PCRE.match 0.01 17.82348
2: seconds TRE.match 0.01 168.46338
3: seconds linear.replacement 0.01 2069.38604
4: kilobytes constant.replacement 10.00 407.55220
5: kilobytes linear.replacement 10.00 100.92007
> plot(pred.list)
Comparing different git versions of an R package
atime_versions() runs different versions of your R package code, for varying data sizes N, so you can see if there are any asymptotic differences in performance, between git versions of your package. See ?atime::atime_versions for documentation and examples (grates example and output).
If you want to run atime_versions() to check R package performance in every Pull Request, autocomment-atime-results is a GitHub action which can plot results in a PR comment, so you can see if the PR affects performance (example output: binsegRcpp, data.table). First, you should define a .ci/atime/tests.R code file that creates an R object called test.list which should be a list of performance tests, each one is a list of arguments that will be passed to atime_versions. See ?atime_pkg for documentation, and see these repos for code examples:
bench::press (multi-dimensional search including N) does something similar to atime (runs different N) and atime_grid (search over parameters other than N). However it can not store results if check=FALSE, results must be equal if check=TRUE, and there is no way to easily specify a time limit which stops for larger sizes (like seconds.limit argument in atime).
testComplexity::asymptoticTimings does something similar, but only for one expression (not several), and there is no special setup argument like atime (which means that the timing must include data setup code which may be irrelevant).
See Bencher prior art for even more related work, and see continuous benchmarking for a plot that shows how false positives can show up if you use a database of historical timings (perhaps run on different computers, see Dirk’s real timings to see the typical variability of R CI on GitHub Actions). In contrast, atime_pkg uses a database of historical commits (known Fast and Slow), and runs them alongside commits which are relevant to the current PR (HEAD, merge-base, etc), in the same R session, so we can be confident that any differences that we see are real. In the Bencher framework, a similar idea is presented in Relative Continuous Benchmarking, which shows how to compare two branches, feature-branch and main.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4
