JuliaDynamics / Agents.jl

Agent-based modeling framework in Julia
https://juliadynamics.github.io/Agents.jl/stable/
MIT License
736 stars 119 forks source link

Use Heap instead of PriorityQueue in EventQueueABM #1016

Closed Tortar closed 6 months ago

Tortar commented 6 months ago

This makes RPS more than 2x faster! in general a Heap is more suitable than a PriorityQueue for this task, also it actually makes everything better because a PriorityQueue denied the use of duplicate times, which is actually something which could happen

Datseris commented 6 months ago

I am having trouble understanding how this works. How can a binary heap be faster here? Do you have any idea why?

Tortar commented 6 months ago

the motivation is that with a priority queue you can change the priority of a given key while here you can't, this is not something needed in our case, so that is why it is faster I think

Tortar commented 6 months ago

And I think it is a lot faster if the all time is cut in half

Datseris commented 6 months ago

fantastic, thanks for the great work. But how did you think of this? of changing the data structurte?

Tortar commented 6 months ago

I was actually doing something else, and I needed something like a PriorityQueue but it was too slow and would make the algorithm unusable, so I looked for alternatives, then I remembered that in Agents we had a PriorityQueue and I also remembered it had a bad impact on overall performance when I benchmarked it :-)