[boost] IndexedSet Review

From: David B. Held (dheld_at_[hidden])
Date: 2004-03-29 03:34:34

*** What is your evaluation of the design?

Overall, the design seems sound.  I didn't look at every aspect
of the design in my review, but the usage seems straightforward,
and as the end-goal, I think it passes.

It's too bad that you have to specify the type of the member when
using member<>, but I don't see a way to infer it without having
measurable runtime overhead.

The range() member is very clever and is a good use case for
Boost.Lambda, IMO.

It seems to me that modify() need not have the destructive policy
that it does.  It appears that modify() erases the node from the
index, then reinserts it into the appropriate place.  However, it seems
to me that modify() could first look to see if the modified node
already exists, save the iterator to the correct insertion point, and
then only unlink the node if the modification would be succesful.

So the strategy would be like this:

1) Change the modifier function object to require a value() member
    that gives the new value to be used.
2) Instead of calling mod() right away, call something like
    lower_bound(), using mod.value().  Save the iterator if there isn't
    already an element there that conflicts.
3) Perform the erase as usual, and then do mod(), link2(), etc.

Wow, Boost.Lambda looks like a home run, were it not for the
fact that directly assigning to members through the set interface
is a serious violation of encapsulation. ;)

The safe mode and invariant checking are also nice features.
Perhaps they could be a guideline or recommended feature for
Boost libraries.

One thing that I think should be added (though not affecting my
vote) is ranked indexes.  So just as an index might be unique or
non-unique, it can be ranked or not ranked.  Ranking gives an
index an O(log n) ordinal search.  That is, you can search for the
ith item according to a certain index in O(log n) time, given an
ordered index (obviously, the sequenced indexes would have an
O(n) search time).  This does change the structure of the nodes,
and necessarily makes them bigger for ranked indexes.  So it is
not a trivial change.  However, I am sure that it is doable and would
add value to the library.

*** What is your evaluation of the implementation?

The implementation seems fairly clean, modulo the regular
portability hacks.  The coding style is tighter than I prefer (w.r.t
whitespace) but doesn't affect my opinion of the code itself.  It
seems that some care has been taken to consider performance
issues without necessarily providing the fastest implementation
possible.  While the use of MPL, Lambda, and Tuples makes
the implementation a little fat, this is the kind of compile-time
cost that I think is justified by the run-time and code expressivity
benefits.

Some of the lines are > 80 columns (e.g.: the copyright notice).

I don't like the C-style comments, but I don't expect to be modifying
the source, so it's not really an issue.

I think that BOOST_NO_MEMBER_TEMPLATES should be
deprecated.  I don't think there's a single supported compiler in
the Boost compiler configs that defines this any more.  I think
checking against BOOST_MSVC6_MEMBER_TEMPLATES is
sufficient, but it would be nice to not even have to check against
that.

I do believe the parts that come from other code need to retain the
original copyright.  The parts that were inspired by, but not directly
derived from, another implementation probably don't need a
copyright notice, but should probably give a mention in the copyright,
at the least as a matter of professional courtesy.

*** What is your evaluation of the documentation?

The documentation is very good, except that it could use some very
minor editing (which does not affect the clarity or understandability
of the documentation).

Here is a somewhat minor nitpick.  In the tutorial, the index_list is
specified as so:

    (type of index)<[(tag)[,(key extractor)[,(comparison predicate)]]]>
    (type of index)<[(key extractor)[,(comparison predicate)]]>

I would change it to thus:

    (unique | non_unique)<[(tag)[,(key extractor)[,(comparison
predicate)]]]>
    (unique | non_unique)<[(key extractor)[,(comparison predicate)]]>

It would be nice to be able to read through the documentation like
a manual.  Thus, next links on each page would be appropriate.

On the performance page, you state that the tests were performed on
a system with 260 KB "RAM memory", running W2K.  I'm absolutely
certain that is not correct. ;)  "256 MB RAM" sounds a lot more likely.

Something that I think should be added to the documentation is a
concept page that lists the main concepts in IndexedSet and a concept
interface a la the SGI STL reference (www.sgi.com/tech/stl).

*** What is your evaluation of the potential usefulness of the library?

I think the library is very useful and fills an important gap in the STL.
I think it would be "complete" if it were to add ranked index support.
Then it would be a total replacement of containers like VB's
Collection.  In particular, I think the key functors alone make it
useful, let alone multiple indexes and the like.

*** Did you try to use the library?  With what compiler?
 Did you have any problems?

I did try very briefly.  However, I got blocked by BJam, and didn't
take the time to d/l the latest Boost to fix it (assuming it does).  I
will try to get BJam working later, and if I succeed before the
review is over, I will at least run the tests and create a few small
test programs myself.

*** How much effort did you put into your evaluation? A glance? A
quick reading? In-depth study?

I read all the documentation except for the reference section, and
I spent some time looking over random parts of the code.

*** Are you knowledgeable about the problem domain?

Yes.  I've had need for similar containers and have hand-rolled
some solutions.  The scope of IndexedSet is impressive without
being too feature-bloated.

*** Do you think the library should be accepted as a Boost library?

Yes, most definitely.

*** Naming issues:

Here's my take on names, but should not be construed as affecting
my vote for inclusion...

Namespace: I think too many namespace levels are not helpful.
A separate 'container' namespace seems a bit superfluous to me.
There is no danger in name clashes within Boost between container
libraries and other kinds of libraries that I can see, and I don't see
that it provides a significant documentation benefit.  I think additional
namespace depth is most appropriate for collections of algorithms,
where a proliferation of names is more likely to lead to name
collisions.

Library name: I don't think IndexedSet is so bad, but an alternative
that I like is CompositeSet.  Then there could be a Composite
Sorted Associative Container concept which would support the
notion of containers with multiple keys.  Then CompositeSet
would be a model of Composite Sorted Associative Container.
A synonym for Sorted Associative Container could be Simple
Sorted Associative Container or Trivial Sorted Associative
Container.

Indexes: According to the American Heritage Dictionary, Fourth
Edition, as channeled by www.dictionary.com, "indexes" is
preferred to "indices".  Another spelling metric I like to use is
Google.  According to Google, "indexes" returns 5.8 million
hits, while "indices" returns 5.5 million hits.  So that's only a
5% difference, but it's statistically significant. ;)  I personally
think the preferred spelling should be used throughout the
documentation, but that's more of a nitpick than a criticism.

Anyway, I prefer "ordered index" to "regular index".  As far as
index types go, I prefer "ordered_unique" to "set_like", due to
consistency.  I think Ordered Index should be a concept for
this library.

Key extraction: Leave it in the library.

nth_index_type: I don't like the word "nth", personally.  I suggest
either of the following naming schemes:

nth_index_type -> ordinal_index
index_type -> named_index | tagged_index

nth_index_type -> index_byval | index_bynum
index_type -> index_byname | index_bytag

Generalize appropriately to the iterator types.

update(): Actually, I do prefer "replace()" over "update()", because
it does more accurately reflect the operation.

As far as header organization goes, I would think of it this way:
What are the major features and concepts of the library, and
how will they be used separately or together?  Organize the
headers in a way that allows users to include feature sets as
modules.  If you have to, create dummy headers that just include
sets of headers that are logically dependent so that users can
activate a certain feature by including that header.  Also,
consider the cost of each header.  It is worth the extra effort
to isolate expensive headers than cheap ones.  Other than
that, I don't have any particular suggestions.

Dave

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.581 / Virus Database: 368 - Release Date: 2/10/2004