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: Dan Tsafrir (dan.tsafrir_at_[hidden])
Date: 2010-11-13 19:32:54

On Nov 13, 2:37 pm, Joaquin M Lopez Munoz <joaq..._at_[hidden]> wrote:
>
> 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.

I think you're right, but I believe the original SCARY paper (see [1])
suggests a way to address this issue (or at least a similar issue) in
the last paragraph of Section 3.2.

> 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.

I believe this very issue was addressed and solved by the committee.
Specifically, the allocator proposal (which got accepted to c++0x) was
revised to include the following paragraph (see p. 5 of [2]):

    "The key requirements for an allocator’s pointer type are that it
    has pointer-like syntax (i.e., it can be dereferenced using
    operator*), that it is implicitly convertible to the corresponding
    void_pointer and explicitly convertible from the corresponding
    void_pointer, and that there exists a specialization of the
    pointer_traits class template, which describes a number of key
    attributes of the pointer type. If an allocator does not define a
    pointer type, allocator_traits will provide default types for
    pointer, const_pointer, void_pointer, and const_void_pointer of
    value_type*, const value*, void*, and const void*,
    respectively. The above pointer requirements were carefully
    crafted to be harmonious with the intent of N2913 (SCARY Iterator
    Assignment and Initialization)."

The SCARY proposal was synchronously revised to allow the iterator to
depend upon the types X::allocator_type::const_void_pointer and
X::allocator_type::void_pointer (where X is a container) thereby
ridding programmers from the need to depend on the allocator type
(see [3]).

The mailing list thread in [4] includes the discussion of this issue
by Stroustrup and friends, and, in particular, it includes Howard
Hinnant's explanation regarding how/why the SCARY proposal prompted
the revision of the allocator definition (I'm quoting the relevant
text below).

---- refs: ----

[1]
"Minimizing Dependencies within Generic Classes for Faster & Smaller
Programs",
http://www2.research.att.com/~bs/SCARY.pdf

[2]
"Allocators post Removal of C++ Concepts (Rev 1)", committee paper
N2982
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2982.pdf

[3]
"SCARY Iterator Assignment & Initialization (Rev 1)", committee paper
N2980
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2980.pdf

[4]
"Ext pointer vs N2913", libstdc++ mailing list thread,
http://gcc.gnu.org/ml/libstdc++/2009-10/msg00074.html

---- relevant text from [4]: ----

From: Howard Hinnant <howard.hinnant_at_[hidden]>
To: undisclosed-recipients:;
Errors-To: c++std-postmaster_at_[hidden]
Reply-To: c++std-lib_at_[hidden]
Sender: c++std=lib_at_[hidden]
To: C++ libraries mailing list
Message c++std-lib-24867

[snip]

Then I came upon a very simple piece of infrastructure (only two
weeks
ago) which allows SCARY and generalized pointers to mix without
forcing node hierarchies or forcing casting:

namespace std {

template <class Ptr>
struct pointer_traits
{
    typedef Ptr                          pointer;
    typedef typename pointer::value_type value_type;
    template <class U> using rebind = typename pointer::template
rebind<U>;
};

template <class T>
struct pointer_traits<T*>
{
    typedef T* pointer;
    typedef T  value_type;
    template <class U>  using rebind = U*;
};

} // std

Now one can say:

template <class T, class VoidPtr>
struct __list_node
{
     typedef pointer_traits<VoidPtr>::template rebind<__list_node>
pointer;
     pointer prev_;
     pointer next_;
     T       value_;
};

I.e. you can get a generalized void* -> node* type transformation.
Generalized pointers can easily hook into this infrastructure.

I've prototyped it.  Pablo has independently implemented it and is
busy writing it up as a very minor revision to his pre-Santa Cruz
N2946.  Daniel is reviewing the heck out of it (as usual).

I believe this is significant new information for the SCARY debate.

[snip]

With pointer_traits I think SCARY is quite practical.  It provides
the *essential* allocator-less transformation from T* to U*.  With
pointer_traits I can see SCARY as either encouraged or mandated (I'm
not going to nail myself to either one of those two options).

I encourage all to take another look in light of this new
information.  And I feel it is worth the time to discuss again in
Santa Cruz.

-Howard