Thanks @mschauer for this clarification, strange choice.
Here is the test code with DataStructures/PriorityQueue:
using DataStructures
Pqueue() = PriorityQueue{Any, Float16}()
function testm(m, n)
pq = Pqueue();
for i = 1:n
if randn() > 0
#enqueue!(pq, i + m*rand(), Tuple(rand()));
enqueue!(pq, Tuple(rand()), i + m*rand());
else
#enqueue!(pq, i + m*rand(), (rand(), 2));
enqueue!(pq, (rand(), 2), i + m*rand());
end
if i > m
d = dequeue!(pq);
end
end
println(m)
end
# run tests varying number of pending events
for m = Int.([5, 5e1, 5e2, 5e3, 5e4])
@time testm(m, Int(1e6))
end
and timing
5
0.970011 seconds (10.47 M allocations: 306.696 MiB, 6.56% gc time)
50
0.990156 seconds (11.09 M allocations: 314.963 MiB, 5.22% gc time)
500
1.149040 seconds (12.87 M allocations: 350.281 MiB, 5.04% gc time)
5000
1.163019 seconds (13.78 M allocations: 355.716 MiB, 5.32% gc time)
50000
1.340612 seconds (14.23 M allocations: 367.543 MiB, 9.16% gc time)
vs. timing of my code above
5
0.298179 seconds (3.51 M allocations: 107.208 MiB, 8.42% gc time, 4.43% compilation time)
50
0.338175 seconds (3.51 M allocations: 107.003 MiB, 9.77% gc time)
500
0.319229 seconds (3.50 M allocations: 106.807 MiB, 5.75% gc time)
5000
0.377245 seconds (3.50 M allocations: 107.121 MiB, 7.56% gc time)
50000
0.794678 seconds (3.50 M allocations: 109.315 MiB, 3.33% gc time)
Interesting. Looks like my sorted list method has (for tcalc = a*m^b) a lower factor a but a higher exponent b, with a break-even point perhaps at m = 1e6 pending events for the hash-based DataStruct pq.