re: How much should I care about allocators?
Dan, I looked into allocators last year when implementing uBLAS's storage abstraction using allocators. You should definitely make use of the ISO standard text when working with allocators! On Monday 21 March 2005 04:19, Dan Rosen <dan.rosen@gmail.com> wrote:
In other words, to respect the allocator I've been given, I need to make sure my internal node structure uses the rebound node allocator's pointer and value types, and so forth. So my first question is, is this assumption correct? This is correct but requires a lot of library programmer discipline!
The reason I ask is that looking over the standard library implementation that comes with gcc 4.0, I noticed that their implementation of std::list<> has nodes which contain straight pointers, rather than the allocator typedef equivalents. To me that seems to contradict my assumption, assuming the gcc implementation is correct.
GCC is correct. There is a get out clause in the library standard. Look at section 20.1.5 "Allocator requirements" paragraph 4: Implementations of containers described in this International Standard are permitted to assume that their Allocator template parameter meets the following two additional requirements beyond those in Table 32. All instances of a given allocator type are required to be interchangeable and always compare equal to each other. The typedef members pointer, const_pointer, size_type, and difference_type are required to be T*, T const*, size_t, and ptrdiff_t, respectively. I suspect many implementation (including those not in the standard) have this requirement!
My second question is about allocator's construct() method. The implementation of std::allocator has construct() invoking the copy ctor using placement new(). That much is self-explanatory. It also seems reasonable to me that allocator does not have construct() methods taking arbitrary parameters. But I'm not sure I understand the reason why it does not have a construct() method to invoke an object's default ctor.?
From this I conclude the construct is semantically identical to calling
In Table 32 "Allocator requirements" construct is specified as a.construct(p,t) Effect: new((void*)p) T(t) placement new. In effect construct does nothing other then provide a nice bit of syntax. I could just as well use placement new syntax directly or indeed call placement new for any other constructor such as the default constructor.
What that implies to me, and seems to be supported by gcc's list implementation, is that the nodes in my tree mustn't have a default ctor that actually does anything, because the only way to properly initialize objects using an allocator is through copying. Is that correct
I think not. My interpretation is that allocators require that their value_type is Copy Constructable but place no restriction on other ways they may be constructed. That said, STL containers have been carefully designed to avoid the need default construct an object which will be subsequently assigned to. They can keep memory in an uninitialised state until an element is needed and then use copy construction. All the standard containers require their value_type to be Assignable but not Default Constructable. Interestingly no mention is made of Copy Constructable in the value_type requirements. I assume this is inherited in the Allocator requirements. Hope this help, Michael -- ___________________________________ Michael Stevens Systems Engineering Navigation Systems, Estimation and Bayesian Filtering http://bayesclasses.sf.net ___________________________________
GCC is correct. There is a get out clause in the library standard. Look at section 20.1.5 "Allocator requirements" paragraph 4 [snip]
Ah, that clears up my first confusion! Though it does leave me wondering, then, how allocators solve that part of the problem they were intended for. If the intent was in part to abstract out platform differences, that abstraction seems undermined by this shortcut. But this probably isn't the place to discuss it.
What that implies to me, and seems to be supported by gcc's list implementation, is that the nodes in my tree mustn't have a default ctor that actually does anything, because the only way to properly initialize objects using an allocator is through copying. Is that correct
I think not. My interpretation is that allocators require that their value_type is Copy Constructable but place no restriction on other ways they may be constructed.
That said, STL containers have been carefully designed to avoid the need default construct an object which will be subsequently assigned to. They can keep memory in an uninitialised state until an element is needed and then use copy construction.
This kind of makes sense ... In implementing a container, I certainly shouldn't have any reason to default-construct instances of the container's value type, except in cases like std::list's default fill constructor (where the default exemplar element can be created on the stack, avoiding any allocation issues). I was more concerned about my own internal node structure, where I did run into the problem of how to construct nodes. I suppose I will follow the standard library's convention of not default-constructing my nodes, even if calling placement new() directly -- rather than construct() -- would have been safe. The other thing I think I'll do is bite the bullet and purchase a copy of the standard. Seems like there's a lot in there that I can't find through a simple Google search! Thanks very much for your help, dr
Michael Stevens wrote:
GCC is correct. There is a get out clause in the library standard. Look at section 20.1.5 "Allocator requirements" paragraph 4:
Implementations of containers described in this International Standard are permitted to assume that their Allocator template parameter meets the following two additional requirements beyond those in Table 32. All instances of a given allocator type are required to be interchangeable and always compare equal to each other. The typedef members pointer, const_pointer, size_type, and difference_type are required to be T*, T const*, size_t, and ptrdiff_t, respectively.
I suspect many implementation (including those not in the standard) have this requirement!
Dinkumware's library doesn't. It is certainly something to strive for when writing a container, since otherwise your container cannot be used with certain useful allocators. Tom
Hi to all, Shmem library makes use of pointer typedef to use a smart relative pointer as allocator::pointer to be able to put containers in shared memory. Standard allows considering pointer as T* and that allocators of equal type are equals, but using typedefs and comparing allocators at run-time opens a new way to use containers. In my case in shared memory. boost::unordered_* family uses does not suppose allocator typedefs and uses (for example, uses construct instead of placement new) and because of that we will be able to place it in shared memory to create in memory data-bases. In my opinion, since it does not hurt, if you respect allocator typedefs and functions, you can get some advantages. Regards, Ion ----- Original Message ----- From: "Tom Widmer" <tom_usenet@hotmail.com> To: <boost@lists.boost.org> Sent: Wednesday, March 23, 2005 3:57 PM Subject: [boost] Re: How much should I care about allocators?
Michael Stevens wrote:
GCC is correct. There is a get out clause in the library standard. Look at section 20.1.5 "Allocator requirements" paragraph 4:
Implementations of containers described in this International Standard are permitted to assume that their Allocator template parameter meets the following two additional requirements beyond those in Table 32. All instances of a given allocator type are required to be interchangeable and always compare equal to each other. The typedef members pointer, const_pointer, size_type, and difference_type are required to be T*, T const*, size_t, and ptrdiff_t, respectively.
I suspect many implementation (including those not in the standard) have this requirement!
Dinkumware's library doesn't. It is certainly something to strive for when writing a container, since otherwise your container cannot be used with certain useful allocators.
Tom
Hi Ion, Thanks for the input. It certainly doesn't hurt to respect allocator typedefs and use the construct() member as intended. It just seems that Google doesn't realize this yet :) However I did manage to find this: http://www.cuj.com/documents/s=8000/cujcexp1812austern It seems like using allocators properly does impose some real design decisions and restrictions. I think I'll study the Dinkumware STL implementation (and also the Boost Graph Library) to see what they do, since as far as I can tell, my code here is illegal: class node_t; typedef typename A::template rebind<node_t>::other node_allocator; typedef typename node_allocator::value_type node; typedef typename node_allocator::pointer node_pointer; class node_t { pointer t_; node_pointer parent_; // etc. }; because I'm instantiating node_allocator with an incomplete type. Such a strange dance this is. Thanks again, dr On Thu, 24 Mar 2005 10:02:10 +0100, Ion Gaztañaga <ion_g_m@terra.es> wrote:
In my opinion, since it does not hurt, if you respect allocator typedefs and functions, you can get some advantages.
Dan Rosen <dan.rosen@gmail.com> writes:
It seems like using allocators properly does impose some real design decisions and restrictions. I think I'll study the Dinkumware STL implementation
I suggest you look at Dinkumware and one other side-by-side, since Dinkumware does something almost no other STL does: they implemented the optional support for allocators of the same type that don't always compare equal. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
Dan Rosen <dan.rosen@gmail.com> writes:
It seems like using allocators properly does impose some real design decisions and restrictions. I think I'll study the Dinkumware STL implementation
I suggest you look at Dinkumware and one other side-by-side, since Dinkumware does something almost no other STL does: they implemented the optional support for allocators of the same type that don't always compare equal.
It's also worth reading: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2004/n1599.html which is about implementing swap for unequal allocators.
----- Original Message ----- From: "David Abrahams" <dave@boost-consulting.com> To: <boost@lists.boost.org> Sent: Thursday, March 24, 2005 7:15 PM Subject: [boost] Re: How much should I care about allocators?
Dan Rosen <dan.rosen@gmail.com> writes:
It seems like using allocators properly does impose some real design decisions and restrictions. I think I'll study the Dinkumware STL implementation
I suggest you look at Dinkumware and one other side-by-side, since Dinkumware does something almost no other STL does: they implemented the optional support for allocators of the same type that don't always compare equal.
Hi Dan, Apart from that feature pointed by David, Dinkum is also very close (specially std::vector) to be able to instantiate containers with an smart pointer as allocator::pointer typedef. Other containers (list, map family) need very little tweaks. When I first proposed Shmem in boost mailing list I was working in containers in shared memory with the following library/article: http://ice.prohosting.com/newfunk/boost_shmemSTL.zip that explains needed changes to make Dinkum containers totally free of (pointer == T*). Last time I checked STLPort and libstdc++ used raw pointers as container members, maybe because of their SGI background. I also know that Metrowerks STL supports pointer typedefs. Although you never know until you instantiate a class with an allocator that defines pointer as something different than T* if the abstraction is good enough. For the moment, all implementations that I checked (STLPort, libstc++ and Dinkum) didn't fully support that. Shmem library containers (vector, list, ...) are modified SGI containers using pointer typedefs, you can have a look if you want to take any idea (Shmem is in boost vault). Another issue with allocators is what to do if allocators are not equal as discussed here: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html Last time I discussed this with Howard Hinnant, the showed me links to some very interesting papers regarding to "move" semantics and allocators, written by some well known boosters: "Impact of the rvalue reference on the Standard Library": http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1771.html For background on the rvalue reference see: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2002/n1377.htm Really allocator interface is not very clear (current "construct" function is a pain since it only allows a copy construction and not a construction from convertible types), but rvalue opens some very interesting options to avoid temporaries and reduce the number of needed allocator instances to abstract the memory model when building containers (specially node containers). Regards, Ion P.D.: Regarding your code, in my list container I define the node outside the containers class, maybe that can help you with your instantation problem: template <class T, class A> struct shmem_list_node { typedef typename boost::detail::allocator:: rebind_to<A, shmem_list_node<T, A> >::type NodeAlloc; typedef typename NodeAlloc::pointer pointer; T m_data; pointer m_next; pointer m_prev; };
participants (6)
-
Dan Rosen -
Daniel James -
David Abrahams -
Ion Gaztañaga -
Michael Stevens -
Tom Widmer