search

haskell / fgl

A Functional Graph Library for Haskell
http://hackage.haskell.org/package/fgl
Other
185 stars 54 forks source link

Replace Lists with Data.Sequence in edge lists. #63

Closed wuerges closed 7 years ago

wuerges commented 7 years ago

Since it is not really possible to know before hand if a ++ b is faster than b ++ a, it might be better to use Data.Sequence.

This change can improve fgl's (&) performance from O(n) to potentially O(1), without loss of generality or ease of use.

I noticed this when the following change reduced my memory usage by half: https://github.com/wuerges/vlsi_verification/commit/45e7c30ee47194d57e70e7ca01b299d0d9438f90?diff=unified#diff-014d188201674e3d3062b5a764945832

This is due to fastInsEdge being implemented with addLists instead of (++)

I could evaluate this because my particular Graph has a huge amount of inn edges for each node and at most 2 out edges. The change above only made any difference in memory consumption when changing the input edge list, not the output.

ivan-m commented 7 years ago

Is this still the case with #62 merged in?

wuerges commented 7 years ago

Yes, #62 only fixes it if you are adding one edge at a time. If you add n edges at O(1), it gets O(n).

Consider the case where you are merging nodes in a Graph (which is very important in my project): Ideally, you would do something like this:

let (Just (is1, _, v, os1), g1) = match n1 g0
    (Just (is2, _, _, os2), g2) = match n2 g1
    g3 =  (is1 ++ is2, n1, v, os1 ++ os2)  & g2

Since the Adj use regular lists, currently, it will be O(n). Using Seq it would be O(log(n))

What I'm now wondering is if it is possible to change the inner workings of fgl to work with something like Monoid or Foldable, or some other type class instead of lists. This way, it would be possible to keep compatibility with the current API.

Anyway, I'll investigate it further in the next week, and provide some evidence if it is something really important.

wuerges commented 7 years ago

It seems #62 fixed my space leaks. After 120 seconds, my project was using 7GB of memory, and now it is using only 35 MB. Execution time is still an issue, however.

wuerges commented 7 years ago

Ok, I've been working on this problem in my project and my conclusion is that the problem is with my algorithm and lists are more than fine to represent edges.

Therefore, this issue should be closed.