Profiling graph library

[Joseph Rushton Wakeling]

On 07/31/2013 01:02 AM, bearophile wrote:
> There are many ways to design a graph data structure. All of them have
> tradeoffs, they can't be very good for everything.

Sure, it's just that in this case the reference code (igraph) is _much_ more
performant.  I'm keen to try and identify the major issues that are holding the
D code back.

I _could_ just copy the C algorithms from igraph into my own code, but nothing
would be learned from that, and it would seem to defeat the purpose of using a
more elegant language like D.

> For your benchmarks are you using the ldc2 compiler with correct compilation
> switches?

No, gdmd -O -release -inline -g -profile, and then gprof to generate the profile.

> map() should not allocate memory.
> 
> Sometimes lazy code is faster and sometimes it's slower. A good compiler (like
> Haskell GHC) should be able to optimize map well.

That's what I'd assumed, which was why I was so disappointed that in this case
performance was _very_ bad.  I particularly don't understand the major GC hit.

Or rather, I should say, I don't see why that GC hit should be there, unless
it's that there is a fault in the implementation of iota, map and/or chain.

> Also try to use a bitvector from Phobos instead of bool[].

I did consider that, I haven't tried yet.  Obviously it's superior from a
storage point of view, I wasn't sure if it would be worse or equivalent
performance-wise (I seem to recall reading that it's slightly slower than a
bool[]).  I'll try it. :-)

> Sometimes you can keep memory allocation low, performance almost acceptable, and
> code easy to read using a pre-allocated scratch space plus using map() and
> copy() from std.algorithm.

Could you expand a little on that point?

I don't mean to ask you to write my code for me, it's just that (like most
non-computer-science researchers) my knowledge of programming is somewhat
specialized, and there are blank spots on the map.  So when in your reply to
John you say, "Allocate a buffer somewhere, on the stack or heap", I'm still not
sure exactly what you mean or how you'd use it.  It'd really help to see a
concrete example (it doesn't need to be tailored to the use-case here).

In any case, thanks as ever for all the useful remarks and advice. :-)