[Haskell-cafe] Large graphs

tomberek tomberek at gmail.com
Tue May 22 01:13:42 CEST 2012


> - Immutable structure, mutable labels.  After initially reading in the graphs, their shape doesn't change, but information "flows" around the graph, changing the labels on nodes and edges.

I have been working on a similar problem for a while now, hence my
interest and dissatisfaction with FGL. I'm not sure if this is exactly
what you are looking for, but I've been playing around with mutable
graphs (both structure and labels) and found issues with GC, so I set
about the goal of creating an unboxed in-place mutable graph that has
O(1) neighbor retrieval. The graph has to live in ST or IO (i've been
using ST, and it works fine, though I'd like to try STM and try a
multiple-spider traversal). So far, it can do very fast traversal and
label mutation with no allocation or GC after the initial build.

> I wrote some code that reads in graphs and some some basic flow computations on them ... When I tried some larger graphs (~100k), the memory consumption spiked into multiple GB, ...

I can try to use the nodes/specs you provide to give you an estimate
of what my framework can handle. If that works for you, I'll clean up
my code and you can give it a shot. Send me whatever other details you
think are relevant.

I am also curious what would happen if I take out the mutable
structure feature and just stick with mutable labels and how it
affects performance.


More information about the Haskell-Cafe mailing list