haskell / haskell/containers

Is graphFromEdges too lazy?

Open
#917 5 comments 0 reactions 0 assignees View on GitHub
Graph major-release performance
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

`graphFromEdges` is one way to construct a `Graph` in `Data.Graph`, and the line in it which actually constructs the graph looks like

https://github.com/haskell/containers/blob/d8d163a8baa43a7c8ba9b6f4198ee1e398e730d6/containers/src/Data/Graph.hs#L450

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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.