This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Ext pointer vs N2913


Hi Bob,
> Paolo & libstdc++,
>
> Thanks for bringing this to my attention.  Gave n2913 a quick read.
> It makes sense, but I think the proposal inadvertently breaks the
> ability to have alternative pointer representations in iterators.
>   
[snip]

Thanks for your feedback. I'll try to think more about these issues in
time for Santa Cruz. In the meanwhile people started discussing again
this topic on the library reflector, you may want to fetch from the
recent messages (I'm attaching below for your ease c++std-lib-24855,
c++std-lib-24867 and c++std-lib-24871).

Long term, for the actual C++1x library, I think we should pay more
attention to Ion' work for Boost, among other things.

Paolo.

////////////
From: Bjarne Stroustrup <bs@cs.tamu.edu>
To: undisclosed-recipients:;
Errors-To: c++std-postmaster@accu.org
Reply-To: c++std-lib@accu.org
Sender: c++std=lib@accu.org

To: C++ libraries mailing list
Message c++std-lib-24855

I'd like to re-visit the SCARY decision. I'd like to give my OOPSLA 
presentation (max 20 minutes) and call on people who have studied the 
issue to briefly related their experiences and opinions. The reason I 
want to re-raise the issue is that I feel that two mistakes were made in 
Frankfurt and that we have new information:

    * The proposal was consistently (by some) referred to as "the
      optimization", but it is not just an optimization - it is (also
      and primarily) a technique to simplify design (removing a layer of
      indirection) and make performance portable.
    * It was conjectured that the effort to update libraries (especially
      the Dinkumware library) would be massive; this seems not to be the
      case since implementations in that code base exists.

I would not re-raise an issue unless I thought that

    * the issue is important (we may be taking of a 20% to 60%
      performance improvement of standard library uses  - no other
      current proposal has that large a potential positive effect)
    * the proposal actually simplifies the standard from a user's
      perspective and makes currently used design techniques portable
    * the previous discussion was flawed through misunderstandings.

I'd like to be present in LWG from the start of the discussion.


From: Howard Hinnant <howard.hinnant@gmail.com>
To: undisclosed-recipients:;
Errors-To: c++std-postmaster@accu.org
Reply-To: c++std-lib@accu.org
Sender: c++std=lib@accu.org

To: C++ libraries mailing list
Message c++std-lib-24867

On Oct 12, 2009, at 5:52 PM, Matt Austern wrote:

> I'm afraid the only comment I could find on the Wiki was:
>   N2913 SCARY Iterator Assignment and Initialized
>   No NB comments requesting this.
>   The comparator function can be rewritten to allow SCARY.
>   reinterpret_casting iterator types is an alternative.
>
> Is there a more detailed summary that I missed? Possibly this
> is moot if we aren't going to discuss it in Santa Cruz, but if there
> is going to be some discussion I'd like to get up to speed.

I suppose it is time for me to speak up.  <sigh>  This is what the  
chair just lives for. ;-)

Robert, Herb and Bjarne asked me to put SCARY on the LWG Santa Cruz  
agenda.  That alone is good enough for me.  Done deal, it's there.   
Bill is asking me to take it off.  That again is good enough for me,  
modulo other inputs. :-)

My decision:  I will attempt to discuss it in Santa Cruz at a time  
when all of Herb, Bjarne and Bill are available.  My current estimate  
is that such a time is not prior to Wednesday morning 10am.  If there  
is an LWG quorum willing to discuss it, it will be discussed, else it  
won't.  An LWG quorum is 5 people.  I will do my best to keep the time  
involved to a minimum as I keenly agree with Bill's observations  
regarding the shortage of this valuable resource.

<chair hat off, technical hat on>

Since the Frankfurt meeting I've had the opportunity to become much  
more familiar with SCARY.  In Frankfurt I appreciated that it was more  
than just an optimization.  It is a change in API that enables more  
efficient algorithms to be built.  I also appreciated in Frankfurt  
that the mixture of generalized pointers (i.e. when  
allocator<T>::pointer is a class instead of a T*) and SCARY was, well  
scary.

Post Frankfurt I attempted to implement std::list, std::deque and the  
tree-based associated containers with SCARY.  deque was no problem.   
The node-based containers were a problem, at least for me.  The  
problem boiled down to constructing the container's node, e.g.:

template <class T>
struct __list_node
{
     __list_node* prev_;
     __list_node* next_;
     T            value_;
};

When generalized pointers are included into the mix, one can't really  
say "__list_node*".  This type must be obtained from an allocator.   
And the most straight-forward way to do that is to template  
__list_node on an allocator:

template <class T, class A>
struct __list_node
{
     typedef typename A::template rebind<__list_node>::other::pointer  
pointer;
     pointer prev_;
     pointer next_;
     T       value_;
};

But of course, the above is "anti-SCARY".

Robert, in c++std-lib-24364 suggested:

template <class T>
struct __list_node_base
{
     T       value_;
};

template <class T, class Pointer>
struct __list_node
     : __list_node_base<T>
{
     Pointer prev_;
     Pointer next_;
};

where the client supplies Pointer as A::template  
rebind<__list_node_base>::other::pointer.  This works, but causes  
significant performance problems for me.  For example I can no longer  
form a list "end node" with T optimized out of it.  I prefer to be  
able to have the inverted hierarchy (the prev/next pointers in the  
base and value in the derived node).  There were further performance  
problems with the tree based containers based on the fact that I want  
the tree balancing code to be dependent only upon the parent/left/ 
right pointers and the node color, and independent of T.

Still, there are other implementation techniques such as that  
described in Pablo's pre-Santa Cruz N2946:

template <class T, class VoidPtr>
struct __list_node
{
     VoidPtr prev_;
     VoidPtr next_;
     T       value_;
};

(this is an approximation to the N2946 technique)

And I came up with another that isn't quite as severe:

struct __list_node_base {}

template <class T, class ListNodeBasePtr>
struct __list_node
     : __list_node_base
{
     ListNodeBasePtr prev_;
     ListNodeBasePtr next_;
     T               value_;
};

But even so, this involves a non-trivial amount of casting within the  
containers and their iterators (from VoidPtr or ListNodeBasePtr to  
NodePtr).

I'm happy with none of these solutions.  When Robert, Herb and Bjarne  
asked me to put SCARY on the LWG Santa Cruz agenda I said ok, but  
SCARY is a no-go for me when generalized pointers are involved for the  
above reasons.  I'm fine with SCARY as long as I only have to deal  
with built-in pointers and not generalized pointers.

BUT...

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.

My personal position is that I am completely against SCARY without  
pointer_traits (too much mandated casting for containers -  
std::containers are just examples, customers need to write them too).   
But 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


From: =?ISO-8859-1?Q?Ion_Gazta=F1aga?= <igaztanaga@gmail.com>
To: undisclosed-recipients:;
Errors-To: c++std-postmaster@accu.org
Reply-To: c++std-lib@accu.org
Sender: c++std=lib@accu.org

To: C++ libraries mailing list
Message c++std-lib-24871

Howard Hinnant escribi=F3:

> My personal position is that I am completely against SCARY without=20
> pointer_traits (too much mandated casting for containers -=20
> std::containers are just examples, customers need to write them too). =20
> But with pointer_traits I think SCARY is quite practical.  It provides=20
> the *essential* allocator-less transformation from T* to U*.  With=20
> pointer_traits I can see SCARY as either encouraged or mandated (I'm no=
t=20
> going to nail myself to either one of those two options).

We had the same problem in Boost and pointer_to_other was added:

http://www.boost.org/doc/libs/1_40_0/libs/smart_ptr/pointer_to_other.html

For other traits (mainly difference_type), iterator_traits can be used.=20
This utility is heavily used to build allocatorless node containers=20
(intrusive containers).

Best,

Ion


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]