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