-
Notifications
You must be signed in to change notification settings - Fork 177
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
A more efficient Graph representation #936
Comments
IF we change the implementation, I'd argue that It might be possible to optimize the layout even more by using the unboxed array directly instead of a nested array, but that would require a second array to store the indices where the vertex lists start. It seems like a massive oversight to make |
@konsumlamm, I fear the amount of breakage is likely not small, though the number of programs affected likely is. I don't think the (few) users of the module have ever shied away from using what they know about the representation. |
I doubt we can use @treeowl so do you think this is not practical to do, given the amount of breakage? |
@meooow25 You could attempt an impact assessment, but I'm not terribly optimistic. You might be better off exploring those ideas in another package, and try to see if you get good performance using that for, e.g., GHC. |
Bodigrim's comment about improved allocations #909 (comment) and #928 makes me wonder if it would be good to represent graphs as
Array Int (UArray Int Int)
or something similar, instead ofArray Int [Int]
. We all know that[Int]
is not a great way to storeInt
s.Downsides: Breaking change, and construction would be very complicated. For example we can't just use
accumArray
to construct from edges inbuildG
.But memory used should be a lot better, 3 words out of 4 saved per edge if I understand correctly. And dfs algorithms should not suffer in any way.
The text was updated successfully, but these errors were encountered: