Understanding btime

General Usage
1

I’ve implemented insertion sort and merge sort and I’m trying to run a benchmark between the two using @btime from BenchmarkTools

input = rand(1:1000, 1000000)
println("Insertion sort on random array of size ", length(input))
@time output = insertion_sort(input)

input = rand(1:1000, 1000000)
println("Merge sort on random array of size ", length(input))
@time output = merge_sort!(input, 1, length(input))

I got from @btime that insertion sort runs in 862.916 μs (0 allocations: 0 bytes) while merge sort 129.066 ms. And well, that’s impossibile. Running the two algorithms I can see (by the time i watch the terminal expecting for the output) that insertion sort is by far slower than merge sort (as expected since insertion sort is O(n^2) and merge_sort is O(nlogn)).

If I ran the same code using @time instead of @btime I got

Insertion sort on random array of size 1000000
161.143262 seconds (18.99 k allocations: 1.062 MiB, 0.01% compilation time)
Merge sort on random array of size 1000000
0.188673 seconds (4.02 M allocations: 670.534 MiB, 12.13% gc time, 4.99% compilation time)

Here’s the whole code: Insertion Sort vs Merge Sort · GitHub

Why is this happening?

2

@btime runs the code multiple times to obtain a good estimate of the time, and if the array is already sorted the second time, the benchmark is probably meaningless. To avoid that (if that is the problem, I didn’t look closely), you can reset the array at each run within @btime with:

input = rand(1:1000,1000000)
@btime merge_sort!(x, 1, length(x)) setup=(x=copy($input)) evals=1

(see Manual · BenchmarkTools.jl)

3 Likes