Re: [boost] Formal Review: Indexed Set

From: Rob Stewart (stewart_at_[hidden])
Date: 2004-03-30 10:03:14

From: =?iso-8859-1?Q?Joaqu=EDn=20M=AA=20L=F3pez=20Mu=F1oz?= <joaquin_at_[hidden]>
> Rob Stewart ha escrito:
> 
> > The main page mentions "STL-like indices," but I don't think of
> > the Standard Library as providing indices, so this doesn't mean
> > anything to me.
> 
> Well the meaning is that indices (italicized as the term is first
> introduced) have STL-like characteristics. I'd be happy to rewrite this
> in a cleaner way if only you provided me with a different wording.

Rereading the text, I think that you're trying to say that the
various indices one can configure in an indexed_set have
interfaces like those of the container types provided in the STL,
making using them familiar.

> > While it will complicate matters somewhat, I'd prefer to see the
> > examples written as if "namespace is = boost::indexed_sets" (or
> > similar) were in effect.  That would highlight the functionality
> > not already in namespace boost.
> 
> I don't quite get it. The docs are written as if the library is
> already in Boost. Other tutorials in Boost also apply
> the implicit using policy.

Other documentation notwithstanding, I'm suggesting that all of
the pieces that come from your library be highlighted by an
"is::" prefix so they stand apart from the other components used
in the examples.  IOW, any lambda, mpl, tuples, etc. code would
be unqualified, through the use of "using namespace ..." and the
Indexed Set code would be distinct.

> > The initial discussion of "regular indices" in the tutorial gave
> > me no idea what they were.  Even after the example, I was left
> > wondering what that "regular index" thing actually was.  I didn't
> > see anything called "regular index" in the example code.  It
> > wasn't until the "Index types" section that I find the definition
> > of a "regular index."
> 
> I'm not sure what I could do to improve this part. Any specific
> suggestion. I thought it'd be clear indices are wht one specifies
> with unique<> etc.

Here's what you've written:

"Boost.IndexedSet features regular indices, designed to help
programmers in need of sequences of elements for which more than
one sorting criteria are relevant."

I note that "regular indices" is a forward link to the
definition, but this still leaves the reader confused here.  That
is, if the reader doesn't want to jump to another context, but
wants to continue reading the tutorial here, then there's no help
to understand "regular indices."  Here is a suggestion for
rewriting that sentence:

   Boost.IndexedSet features "regular" indices, which are sorted
   by keys using predicates, and were designed to help
   programmers in need of sequences of elements for which more
   than one sorting criteria are relevant.

The difference is the "short and sweet" definition of a "regular"
index that allows the reader to continue in the current context.

> > Your "safe mode" name is inconsistent with the
> > "invariant-checking mode."  The latter clearly indicates what is
> > being checked, whereas the other doesn't.
> 
> I retained the name "safe mode" because users are likely
> familiar with the name as given in STLport.

I've never used STLport, so that carries no significance for me.
I'm still in favor of being explicit and consistent.

> >  I expected that "safe
> > mode" would be a superset, but it is orthogonal.  How about
> > naming it "precondition-checking mode?"  A related issue is that
> > you say that invariant-checking can be turned on separately from
> > "safe mode" and that the former indicates an internal error.
> > However, I don't see how you can assert that the failure to
> > maintain an invariant is an internal error if you don't ensure
> > the preconditions were met.  IOW, shouldn't turning on
> > invariant-checking mode imply turning on precondition-checking?
> 
> I'd like to give maximum flexibility to the user. Your reasoning
> is correct, but then again you can follow your own advice in
> your program and never enable invariant-checking without
> enabling safe mode also. I guess you're for stricter enforcing
> of this.

You're right, the user can decide to always enable "safe mode"
when using "invariant-checking mode" but if they are likely to
get incorrect information, why allow them to avoid it?

> > In Debugging support:Invariant-checking mode, in the advanced
> > topics page, you write:
> >
> > > It is recommended that users of Boost.IndexedSet always set the
> > > invariant-checking mode. By default (i.e. if the user has not
> > > provided a definition for BOOST_INDEXED_SET_INVARIANT_ASSERT),
> > > this mode will not perform any check at all in NDEBUG builds,
> > > but it does not have a significant impact in the compiled
> > > binary either, so you need not set off invariant-checking for
> > > release compilations.
> >
> > I have two questions.  First, why is this information buried in
> > the advanced topics page?  The mode should be highlighted in the
> > main documentation path.
> 
> I thought the tutorial was hard enough as it was and decided to
> move all the non-essential stuff to a different page. Admittedly,
> other topics covered in this section are really much more advanced.

The point is that this issue isn't "advanced."  It is part of
normal usage of the library.  Indeed, it is quite possibly of
more use to less advanced users.

> > Both the tutorial and the advanced topics pages claim
> > indexed_set's simulation of std::set, for example, is as
> > efficient as the real thing, yet the performance page shows a
> > 10-20% overhead.  You should qualify your claims of equal
> > performance such that you say indexed_set has "nearly" as good
> > performance.
> 
> You're right. Added the "nearly" qualifier in the tutorial bit.
> In the advanced topics section, the efficient is said to be
> "comparable", which is IMHO fair enough.

Right.

> > ----------------------
> > Design Issues
> >
> > I don't really like that index 0 is the default behavior.  I'd
> > rather an Index Set not behave like any of its indexes.  Yes that
> > means you must say get(_index)<0>() when you want the first
> > index, but I like the idea of that being explicit.  There's no
> > opportunity to change a typedef from std::list, for example, to
> > boost::indexed_set and silently use the wrong index or silently
> > change the complexities.  I don't see indexed_set as a drop-in
> > replacement for existing types, so I don't want it to be easy to
> > do that.
> 
> Darren also disliked this approach. To me it has some value:
> in a sense, the first index is treated as the primary one (which
> in many situations really is). Put another way, what disadvantages
> do you find in having the default behavior?

First, it depends upon how one views indexed_set.  On the one
hand, you can see it as a drop-in replacement for another
container that happens to permit adding additional indices.
Thus, the original code is largely unaffected by the substitution
and new code can be written to take advantage of the new
capabilities.

OTOH, you can see indexed_set as a completely different animal
with different performance characteristics that happens to work
similarly to existing containers.  The similarity means that
programming with an indexed_set is familiar, but the new
capabilities require conscious application to ensure the
differences are properly accounted for.

My view is the second one, but I can understand the value of the
first.

> > I don't like the assymmetry between get<> and the pair
> > nth_indexed_type<> and indexed_type<>.  I'd prefer that
> > indexed_type<> be used, like get<>, for either a number or a tag.
> 
> I'd prefer it also, but AFAIK it cannot be done. You just cannot
> "overload" a template to accept type and non-type arguments.

I haven't looked at the code, but I'm confused.  How can one use
type and non-type arguments with get<> but not with the others?

> > Why does tag<> accept multiple "names?"  Is there a motivating
> > example for why a single name isn't sufficient?  I ask because
> > the class is more complicated than it otherwise needs to be.
> > That translates into more documentation to explain it and longer
> > -- by however much -- compilation times.
> 
> No movitating example that I know of. It was implemented like that
> cause having multiple tags was no harder than having just one.

The explanation of indexed_set, if not its implementation, is
more difficult.  Without any reason for this "feature," it adds
unwarranted complexity.  Granted, you've said it wasn't any
harder to support multiple tags, and the tutorial section on
multiple tag support is very short.  Still, it smacks of a
solution in search of a problem.

Perhaps someone else can envision a good use for this feature?

-- 
Rob Stewart                           stewart_at_[hidden]
Software Engineer                     http://www.sig.com
Susquehanna International Group, LLP  using std::disclaimer;