[Haskell-cafe] Inductive graphs memory usage

Don Stewart dons at galois.com
Thu Jul 10 19:52:44 EDT 2008

> On Thu, 2008-07-10 at 18:32 -0400, Ronald Guida wrote:
> > Your ratios are about 1 : 3 : 8.
> > That pretty close to quadratic growth, 1 : 4 : 9, so I think all is well.
> Maybe, but 96MB of resident memory for a 1000-node graph looks bad,
> especially considering p is low. Is the internal representation of
> inductive graphs perhaps not very memory-efficient? I still haven't read
> Erwig's paper...
> I know this is probably not fair, but I'm comparing these numbers with a
> C implementation which uses Ruby's C API for its complex data
> structures, and a 10,000 nodes graph uses around 6MB of memory.

Well, they're radically different graph representations, and fgl
hasn't been designed for large graphs.

What C library is Ruby's binding to? It might be quite cheap to bind
to that. I've been on the look out for a good C graph lib to use for
Haskell bindings for a while..

-- Don

More information about the Haskell-Cafe mailing list