search

dominikbraun / graph

A library for creating generic graph data structures and modifying, analyzing, and visualizing them.
https://graph.dominikbraun.io
Apache License 2.0
1.77k stars 95 forks source link

Speed up StableTopologicalSort #131

Closed jonjohnsonjr closed 1 year ago

jonjohnsonjr commented 1 year ago

Fixes https://github.com/dominikbraun/graph/issues/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:

Before: 230.00s
After:    0.03s

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.

deitch commented 1 year ago

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 😄 ).

deitch commented 1 year ago

Hooray! I will run it as well. Will this be v0.22.2 or in v0.23.0?

dominikbraun commented 1 year ago

@deitch v0.22.2, I'm going to release it in a few minutes.

deitch commented 1 year ago

My use case collapsed from 4-6 mins down to 37 seconds. @jonjohnsonjr is 🧙‍♂️

Thanks to both of you.

dominikbraun commented 1 year ago

This change has been released in v0.22.2.