Optimizing DFS in Data.Graph
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Refactor
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- haskell
- Domain
- performance
Research direction
Start by reviewing Data.Graph's dfs implementation and the generate, prune, and chop helpers described in the issue. Compare the proposed dfsGraph approach with dfs, topSort, scc, and bcc, using the listed benchmarks as a baseline. Done means removing unnecessary intermediate trees while preserving the affected graph algorithms.
Written by the indexing model from the issue text.
Description
dfs is the core function in Data.Graph that all other algorithms (topSort, scc, bcc, etc) are based on. It takes a Graph and generates a [Tree Vertex].
dfs makes use of generate, prune and chop to generate a [Tree Vertex] and chop it into the returned [Tree Vertex].
Other functions further transform this [Tree Vertex], for example topSort flattens the [Tree Vertex] into a [Vertex].
These intermediate trees are unnecessary.
- The trees generated by
generateare immediately chopped into other trees. - For
topSort, the trees returned bydfsare immediately turned into a list.
There is no reason we need to create these trees in memory.
I propose combining the existing generate, prune, and chop function into a new core function that eliminates the intermediate trees from generate and also allows us to choose what to build from the DFS.
dfsGraph :: (Vertex -> a -> b) -> (b -> a -> a) -> a -> Graph -> [Vertex] -> a
Then we can define, for example
dfs = dfsGraph Node (:) []
topSort = dfsGraph <build the list directly>
Benchmarks on a random graph with 10,000 vertices and 100,000 edges:
dfs: OK (0.90s)
3.51 ms ± 79 μs, 57% less than baseline
topSort: OK (0.47s)
3.60 ms ± 107 μs, 59% less than baseline
Other function such as scc and bcc should also benefit, I've not implemented them yet.
Thoughts? I can clean up my code into a PR if this sounds good.
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 2d 12h
- Merged PRs (30d)
- 6
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from haskell/containers
-
major-release strictness Tree
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
haskell/containers#1260 ·
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
haskell/containers#1261 · 9 comments ·
-
IntSet low-hanging-fruit performance
Difficulty 3/5 1-2 days Newbie friendliness 58/100
haskell/containers#1251 ·
-
maintainability major-release
Difficulty 3/5 1-2 days Newbie friendliness 70/100
haskell/containers#1250 ·
-
Difficulty 4/5 3-5 days Newbie friendliness 50/100
haskell/containers#1242 ·
All issues in haskell/containers
Similar issues
-
bug good-title pdd
Difficulty 2/5 Under an hour Newbie friendliness 82/100
objectionary/phino#1630 ·
Maintainers usually reply within 1 day
-
attention: pr-welcome documentation
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
haskell/cabal#12402 · 1 reaction ·
Maintainers usually reply within 1 day