Re: [boost] Re: review request: container_traits

From: Brian McNamara (lorgon_at_[hidden])
Date: 2003-10-04 15:54:56

Note: a potentially good idea appears later in this message.

On Sat, Oct 04, 2003 at 03:47:03PM -0400, David Abrahams wrote:
> What I see there makes a perfect case for what I've been talking
> about: each of these container_traits<T> instantiations contains a lot
> of declarations and I can easily imagine only wanting one or two.  I
> see no reason at all to have begin et. al as member functions instead
> of using separate overloaded free functions.  And even if you don't
> buy the efficiency argument (you should), reserving an

Just to throw in a comment about efficiency...

In FC++, I recently added type information to full functoids (instances
of class fullN<F>) to read monomorphic type information about argument
types (don't worry if that makes little sense; the details don't
matter).  I originally did it using "traits blob"; that is, I just added
extra typedefs to the fullN classes to compute the information.  I was
astonished and horrified to find my compile-times slowed down by a
factor of about 1.5 (a 5-minute compile became a 7.5-minute compile).

Fortunately, I have been reading this thread, so I re-implemented the
same information using a traits class, and partially specialized that
class on the fullNs so that the information was extrinsic to those
classes.  As a result, the monomorphic type information was only
computed when it was demanded (that is, when someone asked for, e.g.
   monomorphic_traits<F>::first_argument_type
) rather than every time someone instantiated the fullN class.  And this
info is rarely demanded throughout the library.  As a result, this sped
the compile-time back up to what it was originally (before I added this
capability at all).

This was an extreme case, because
 - every functoid in FC++ relies on the fullN classes (they are a
   compile-time bottleneck), and
 - computing the monomorphic type info is somewhat "expensive" to do
But the point is, avoiding traits blob and defining each trait-of-
interest separately really can be a big win for compile-time efficiency.

I should point out that, in fact, I did not implement each
trait-of-interest separately; for a ternary function F, you can say
   monomorphic_traits<F>::first_argument_type
   monomorphic_traits<F>::second_argument_type
   monomorphic_traits<F>::third_argument_type
   monomorphic_traits<F>::result_argument_type
for example.  However, in practice, you do want all of these traits
together (typically if you need one, you need them all).  The point is,
I separated this set of tightly-related traits from the other traits
already associated with the fullN classes.  And this was a big
efficiency win.

It is not clear to me what the general design principle ought to be.  
On the one hand, it makes "conceptual sense" to group together related
traits into one traits class.  On the other hand, doing so often means
you get traits-blob compile-time inefficiencies, which in the worst
case can be horrible (as I described above).

Actually, duh, a middle-of-the-road trade-off just occurred to me.

Right now, when I say monomorphic_traits<F>, it computes all the
associated typedefs.  In order to do the computations individually, all
I have to do is change it to, e.g.

   monomorphic_traits<F>::first_argument_type<>::type
   monomorphic_traits<F>::second_argument_type<>::type
   ...

The nested templates are named as the individual traits of interest, and
they each have a default (dummy) parameter.  As a result, each
individual trait is only computed on demand (and is also individually 
MPL-able).  But all the related traits are grouped into a common
"supertraits" class, which groups related traits conceptually and also
helps prevent namespace pollution.  I think this may be a
nearly-perfect overall solution which gives the best of both worlds.

That looks really clever to me, and I'd appreciate comments on the idea
(especially from David).  I'm not sure if I've explained it well enough
to make it obvious how it's superior to either of the previous
alternatives; if not, ask again and I'll try to explain it again with a
better example.

-- 
-Brian McNamara (lorgon_at_[hidden])