Is graphFromEdges too lazy?
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 30/100
Research direction
Start in containers/src/Data/Graph.hs at the linked graphFromEdges construction and compare its evaluation behavior with buildG. Review the existing discussion and benchmark results before deciding whether strict construction preserves useful laziness; done means a maintainer-approved decision, with any resulting change validated by measurements.
Written by the indexing model from the issue text.
Description
graphFromEdges is one way to construct a Graph in Data.Graph, and the line in it which actually constructs the graph looks like
This is very lazy. The elements of the array (lists of vertices) are lazy, and the lists themselves would be lazily generated when required. I doubt building up all these thunks is good for us. So I checked out if construction times improve if we are strict, and it does, from 371 ms ± 18 ms, 107 MB allocated to 323 ms ± 30 ms, 77 MB allocated on the largest graph.
Now I've tried to think of situations where lazily constructing a graph is useful.
The only case I can think of is if the user constructs a large graph through graphFromEdges, then runs dfs on a subset of the graph the user already knows is not connected to the rest of the graph. Then they avoid paying the cost of constructing the full graph. But this seems far-fetched.
All other functions like dff, topSort, scc, bcc will always evaluate the full graph.
So, is there any other scenario where lazily constructing a graph is useful?
And if not, should we make it strict?
This would improve the times and also make it consistent with buildG, the other way in Data.Graph to build a graph. The second reason alone might be good reason to do this.
- 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