Re: [boost] Minimizing Dependencies within Generic Classes for Faster and Smaller Programs

Subject: Re: [boost] Minimizing Dependencies within Generic Classes for Faster and Smaller Programs
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2010-11-13 07:37:29

vicente.botet <vicente.botet <at> wanadoo.fr> writes:

> 
> ----- Original Message ----- 
> From: "Andy Venikov" <avenikov <at> gmail.com>
> To: <boost <at> lists.boost.org>
> Sent: Friday, November 12, 2010 7:21 PM
> Subject: Re: [boost] Minimizing Dependencies within Generic Classes for Faster
and Smaller Programs
> 
> It looks like multi index container could greatly benefit from it.
> In fact, I think the example in the paper really represents an 
> implementation of a multiindex container.
> 
> Or is multi-index already employing this technique?
> 
> _______________________________________________
> Hi,
> The example in the paper coudl be considered as a kind of dynamic
> polymorphic multi-index.
> Boost.MultiIndex uses static polymorphism. I don't know if MultiIndex
> uses this technique. Joaquin?

Hi Andy and Vicente,

Boost.MultiIndex iterators are not SCARY (better said, they are
not SCARY in the way it'd be really useful) for the following
independent reasons:

1. When in safe mode (http://tinyurl.com/37cq7tp ), iterators need
to access internal information of the index they are associated to,
hence they are dependent on the index type. In fact, I think
this is a general problem of the SCARY approach with safe- or
checked- iterator modes provided by some STL implementations.

2. When not in safe mode, the iterator type is not pure-SCARY
in that it depends not only on the value type, but also on
the allocator type. Why so? Because this dependency allows for
the creation of advanced (and useful) shared-memory containers
by way of Boost.Interprocess allocators, see
http://tinyurl.com/2vfpbpw . Again, I think this is a potential
general problem (not specifically related to Boost.MultiIndex)
of the SCARY approach.

3. With these caveats, Boost.MultiIndex iterators can be said
to be SCARY as long as they belong to the same category
of index (ordered, hashed, sequenced, random.access) in some
situations, not in others. For instance, the following compiles
and works:

  // example 1

  typedef multi_index_container<
    int,
    indexed_by<
      ordered_unique<identity<int> >
    >
  > multi_t1;

  typedef multi_index_container<
    int,
    indexed_by<
      ordered_non_unique<identity<int>,std::greater<int> >
    >
  > multi_t2;

  multi_t1::nth_index<0>::type::iterator it1;
  multi_t2::nth_index<0>::type::iterator it2;

  it1=it2; // SCARY!

but the following, which would be far more useful, does
*not* work:

  // example 2

  typedef multi_index_container<
    int,
    indexed_by<
      ordered_unique<identity<int> >,
      ordered_non_unique<identity<int>,std::greater<int> >
    >
  > multi_t;

  multi_t::nth_index<0>::type::iterator it1;
  multi_t::nth_index<1>::type::iterator it2;

  it1=it2;

To understand why example 2does not work, and cannot be made
to work without some runtime penalty, consider the
typical (somewhat idealized) node structure of a std::set:

  struct node
  {
    int        color;
    node*      parent,left,right;
    value_type value; 
  };

Obviously, iterators for independent std::set types
with the same value_type are pointing to the same
kinf of stuff, so SCARY is in principle possible. Now,
the node structure of a two-index multi_index_container
like the one defined at example 2 looks like this:

  struct node
  {
    int        color1;
    node*      parent1,left1,right1;
    int        color2;
    node*      parent2,left2,right2;
    value_type value; 
  };

iterators associated to the first index do use the
first group of tree traversal parameters (color1, parent1,
left1, right1) whereas iterators associated to the
second index use the second group (color2, parent2,
left2, right2). So, it1 and it2 types *need* to be different
because they act differently, and this is why the line

    it1=it2;

results in a compiler error. To make the SCARY assignment
work, that is, to allow for it1 and it2 to be of the same
type, such a "unified" operator would have to be provided
with some runtime info as to whether to use the first
or the second group of tree taversal parameters. This
of course is not optimal in terms of speed or space.

The example developed at N2911 comes close to what could
be thought of as a dynamic multi_index_container. This
beast has pros and cons with respect to the current
static multi_index_container, which are more or less
those of dynamic vs. static approaches:

  - dynamic allows for run-time specification and
  modification of the indices comprising the container,
  and, if well designed, for SCARY assignment.
  - dynamic has some unavoidable penalties in performance
  and space consumption.

Some years ago I played a little with a toy prototype
of a dynamic multi_index_container but never went too
far since I didn't see much public interest in the
idea (and, truth be said, writing this is no minor task).

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo