Speed up StableTopologicalSort #131
Conversation
The biggest savings come from just calling sort less often. Instead of in the inner-most loop, we call it after processing the whole map of predecessors. The other portion is just not appending duplicate items to the queue. I do this in a simple way by maintaining a set of queued things (similar to the visited set). I think the "proper" way to fix this would be to use a sorted list for queue instead of sorting after every pass, but I'm too lazy to implement that, and I don't think it's part of the go stdlib. For our use case, on my machine, StableTopologicalSort took: Before: 230.00s After: 0.03s Signed-off-by: Jon Johnson <jon.johnson@chainguard.dev>
jonjohnsonjr
changed the title
There was a problem hiding this comment.
Thanks! I didn't have the time to investigate the performance issue yet, so any help is really welcome. I've also thought about calling sort.Slice less often, and maintaining a map of already-added items makes sense as well.
I think the "proper" way to fix this would be to use a sorted list for queue instead of sorting after every pass, but I'm too lazy to implement that, and I don't think it's part of the go stdlib.
There even is a priority queue implementation in this library. It maintains a binary heap for sorting the items and is currently being used for Dijkstra's algorithm – maybe something like that would be a good fit.
Anyways, I guess an 8000x speed-up is worthy of a new patch release :-)
|
I am really glad @jonjohnsonjr hopped onto this, and I appreciate it as well. He is one superstar, especially in performance related areas (I think he enjoys it too 😄 ). |
|
Hooray! I will run it as well. Will this be v0.22.2 or in v0.23.0? |
|
@deitch v0.22.2, I'm going to release it in a few minutes. |
|
My use case collapsed from 4-6 mins down to 37 seconds. @jonjohnsonjr is 🧙♂️ Thanks to both of you. |
|
This change has been released in v0.22.2. |
Fixes #129
The biggest savings come from just calling sort less often. Instead of in the inner-most loop, we call it after processing the whole map of predecessors.
The other portion is just not appending duplicate items to the queue. I do this in a simple way by maintaining a set of queued things (similar to the visited set).
I think the "proper" way to fix this would be to use a sorted list for queue instead of sorting after every pass, but I'm too lazy to implement that, and I don't think it's part of the go stdlib.
For our use case, on my machine, StableTopologicalSort took:
So about 8000x faster.
We were doing ~50 billion string comparisons before, and we're doing 242642 now. I think that's still too high, but I'm willing to call that fine.