Re: [boost] [metagraph]

Subject: Re: [boost] [metagraph]
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2012-02-03 01:21:21

Hi Nick,

On Feb 2, 2012, at 1:20 PM, Kitten, Nicholas wrote:
> On Fri, Jan 27, 2012 at 11:39 AM, Gordon Woodhull <gordon_at_[hidden]> wrote:
>> As you can see, the sandbox version now has an iterator-based design rather than using recursion.  
> Wait, now I'm confused; the sandbox/metagraph/
> <https://svn.boost.org/svn/boost/sandbox/metagraph/> (from what I can
> tell, anyway) uses the original recursion-based design (but includes
> the angly parser),

Sorry; I thought I had checked in the iterator versions.  They are there now.

> while sandbox/mgl/ (which I hadn't seen before) has
> iterator-based design, but no angly parser.  What am I missing here?
> Does metagraph now consist of both folders?  

No, MGL is a competing library by Franz Alt that I've learned a lot from.  The story is that Christophe Henry badly needed a graph metaprogramming library for verifying MSMs, so he encouraged Franz to write that one.  I had already written MPL.Graph but hadn't publicized it much.

I think my design is better (more closely parallels BGL; tighter metafunctions) but Franz's is somewhat faster and more memory-efficient.  Part of that was the iterators, which I've now adopted.

> As a side note, I can't
> tell whether "angly expression" refers to the profusion of angle
> brackets, or to some theoretician named "Angly" who works with DFAs :)

Yep, just my made-up name for these sorts of EDSLs.  :)

> Compile-time exception propagation is certainly an interesting
> concept, especially considering how poorly compilers do reporting
> errors for metaprogramming.  I actually stumbled across the metatest
> suite from the same group of libraries not long ago, and it's good
> stuff.  However, I think if we did incorporate it, we'd need a way to
> make it optional, since there will likely always be people who don't
> want to pay the extra cost for using exceptions.  To enable errors, I
> don't see how we could get around requiring the do / let notation for
> propagating monads, but perhaps a little preprocessor magic could
> disable them?  I'll have to think on that.

Yes, I think it may be too expensive for everyday use until compilers catch up, though I haven't tried it yet.  

Note you don't need exceptions to interrupt search with an iterator-based design.

> For topological sort in particular, what I have simply returns partial
> results for everything that _can_ be sorted, leaving cycles and
> components lower in the ordering behind.  That makes it so you can try
> to sort without doing any checks, and if all nodes are returned,
> you're done.  

This design makes more sense to me than just dying if there are cycles.  

> If not, you break cycles on the remaining subgraph, then
> continue sorting (this is exactly what I do in my own use case).

I presume you mean you build a new graph with the cycles broken, since MPL.Graph doesn't (yet?) support mutable graphs.

>> If you see how to write a patch for that, I'd be glad to have a co-author.  (The iterator design is based on Franz Alt's feedback and his alternative MGL. [2])
> 
> I will write a patch, once I'm sure where the definitive home for this
> library is at the moment.  My impression was that iterators and
> recursion each had their pros and cons, so I'd be interested to hear
> the rationale for switching.

Do you know any resources comparing iterators and recursion in TMP?

The reason I switched is that MPL.Graph was *dramatically* slower on my old machine, because template recursion seems to use a lot more memory and so it ran out of physical memory.  I know the Abrahams/Gurtovoy book strongly advises against deep recursion - but compilers may have changed.

The new design, with an explicit stack, is more complex but I think more powerful.  It's probably worthwhile to measure the performance difference.  On a new machine with more RAM, I didn't really see much difference between MGL and either version of MPL.Graph, so I kind of stopped worrying about it.

> Here, I see mgl already has a simple dfs-based solution, which is
> probably fine as long as find_cycles is also provided - which again
> begs the question, where is the merging happening?

So far there has only been conceptual merging - his coding style is way different.  

I think once MPL.Graph has topo sort, strong components and/or biconnected components, and maybe something fancy like Dijkstra's shortest paths (requires a heap metadata structure), it'll be ready for review.  Any help would be appreciated!

Cheers,
Gordon