[move semantics] Containers supporting movable-only types
Hi to all, I committed to trunk some days ago (and I plan to merge them to the release branch) some changes in Interprocess containers so that they can take advantage of C++0x rvalue references of gcc 4.3. The goal is that anyone experimenting with compilers with rvalue references (gcc 4.3 for now) can take advantage of containers that can hold movable-only types. Most of these containers (list, map/set/multimap/multiset, slist) are based on Intrusive containers. Vector and deque have more code and a move-aware vector is specially useful to achieve efficient associative ordered vectors like flat_map/flat_set/flat_multimap/flat_multiset. Current move-emulation is still based on Interprocess' own types. For Boost 1.37 I would like to change move emulation to a general Boost.Move library (if that library is ready). With new containers (forward_list) in the standard and having move-aware containers in Interprocess, I was wondering if it would be a good idea to move those containers outside Interprocess. In the future we could make those containers compatible with Scoped Allocators (2554, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2554.pdf). Opinions? Regards, Ion
Ion Gaztañaga wrote:
The goal is that anyone experimenting with compilers with rvalue references (gcc 4.3 for now) can take advantage of containers that can hold movable-only types.
I hardly see how any other datatype than a vector (or a hash map) can require movability. For the rest, you only need to put in-place construction in the interface.
Mathias Gaunard wrote:
Ion Gaztañaga wrote:
The goal is that anyone experimenting with compilers with rvalue references (gcc 4.3 for now) can take advantage of containers that can hold movable-only types.
I hardly see how any other datatype than a vector (or a hash map) can require movability. For the rest, you only need to put in-place construction in the interface.
Don't forget deque and ordered vector family (once move semantics are in game, insertion performance is quite interesting). I don't see any problem to implement in-place for those containers and I would be able to provide in-place insertion ASAP. Meanwhile, users with movable objects can speed up their implementations. Regards, Ion
On 22/06/2008, Ion Gaztañaga <igaztanaga@gmail.com> wrote:
Current move-emulation is still based on Interprocess' own types. For Boost 1.37 I would like to change move emulation to a general Boost.Move library (if that library is ready).
It might not meet all your needs. My work so far has been based on the Adobe move library, which only supports 'regular' types, and move-only types are not considered regular. For details see: http://stlab.adobe.com/group__concept__regular__type.html http://stlab.adobe.com/group__concept__movable.html In most cases it relies on return value optimization to move the type. The library also supplies several functions and algorithms for dealing with movable types. So my plan was to separate the library into two parts - move emulation and the move functions and algorithms. And then work on making the algorithms generic enough to support other move emulation methods. So that a container will be able to efficiently deal with Boost.Thread's move-only objects, Adobe movable object and objects using rvalue references. I'm not going to work on a new way of making the container itself movable when its elements aren't. I think there are already ways of doing this in boost. One of these could possibly be brought into the move library. But I'm not sure that consensus could be reached on a single way to emulate move semantics which is why I'm going to try to support multiple emulation types. So, in summary, the library will supply algorithms for moving the containers' elements (e.g. when resizing an array or implementing emplace), but you might want to use one of the existing mechanisms to make the container itself movable.
With new containers (forward_list) in the standard and having move-aware containers in Interprocess, I was wondering if it would be a good idea to move those containers outside Interprocess. In the future we could make those containers compatible with Scoped Allocators (2554, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2554.pdf).
I think this might be a good idea. We could possibly bring together all the containers from the C++0x draft (of the top of my head: your containers, the unordered containers and Boost.Array). It'll also be good to cooperate when implementing some of the latest features (such as 'emplace') which will probably require similar features across the containers. Daniel
Daniel James wrote:
On 22/06/2008, Ion Gaztañaga <igaztanaga@gmail.com> wrote:
Current move-emulation is still based on Interprocess' own types. For Boost 1.37 I would like to change move emulation to a general Boost.Move library (if that library is ready).
It might not meet all your needs. My work so far has been based on the Adobe move library, which only supports 'regular' types, and move-only types are not considered regular. For details see:
http://stlab.adobe.com/group__concept__regular__type.html http://stlab.adobe.com/group__concept__movable.html
I have a hunch that it would be really easy to add support for move-only types, though. Do you see any specific obstacles?
In most cases it relies on return value optimization to move the type. The library also supplies several functions and algorithms for dealing with movable types. So my plan was to separate the library into two parts - move emulation and the move functions and algorithms. And then work on making the algorithms generic enough to support other move emulation methods. So that a container will be able to efficiently deal with Boost.Thread's move-only objects, Adobe movable object and objects using rvalue references.
Sounds like a good strategy.
I'm not going to work on a new way of making the container itself movable when its elements aren't.
Hm. I don't know what you mean by "a new way," but for most containers, movability of the element is irrelevant. boost::array and tuples are the only exceptions I can think of. Could you clarify?
I think there are already ways of doing this in boost. One of these could possibly be brought into the move library. But I'm not sure that consensus could be reached on a single way to emulate move semantics which is why I'm going to try to support multiple emulation types.
So, in summary, the library will supply algorithms for moving the containers' elements (e.g. when resizing an array or implementing emplace), but you might want to use one of the existing mechanisms to make the container itself movable.
With new containers (forward_list) in the standard and having move-aware containers in Interprocess, I was wondering if it would be a good idea to move those containers outside Interprocess. In the future we could make those containers compatible with Scoped Allocators (2554, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2554.pdf).
I don't know whether you consider this relevant, but I think that Boost ought to adopt something like Adobe's move-aware standard container collection, just to avoid layering issues (something in boost needs a move-aware container, so it uses ASL, which in turn uses boost). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
2008/6/23 David Abrahams <dave@boostpro.com>:
I have a hunch that it would be really easy to add support for move-only types, though. Do you see any specific obstacles?
I haven't really thought about it much. Since there are already other solutions, I thought the easiest thing might be to use one of them. But I haven't looked at them in detail yet.
I'm not going to work on a new way of making the container itself movable when its elements aren't.
Hm. I don't know what you mean by "a new way," but for most containers, movability of the element is irrelevant. boost::array and tuples are the only exceptions I can think of. Could you clarify?
I believe that if the container uses the current Adobe move implementation to make itself movable, then it will only be movable when it is also copyable, which it won't be if the elements are move-only. But we'd probably want the container to be movable in this case, which would require something extra (the 'new way' I was referring to). If it's easy to add support for move-only types, then maybe this wouldn't be too much to do.
I don't know whether you consider this relevant, but I think that Boost ought to adopt something like Adobe's move-aware standard container collection, just to avoid layering issues (something in boost needs a move-aware container, so it uses ASL, which in turn uses boost).
I think that's pretty much what Ion is proposing for the Interprocess containers. Daniel
Daniel James wrote:
2008/6/23 David Abrahams <dave@boostpro.com>:
I have a hunch that it would be really easy to add support for move-only types, though. Do you see any specific obstacles?
I haven't really thought about it much. Since there are already other solutions, I thought the easiest thing might be to use one of them. But I haven't looked at them in detail yet.
I'm not going to work on a new way of making the container itself movable when its elements aren't. Hm. I don't know what you mean by "a new way," but for most containers, movability of the element is irrelevant. boost::array and tuples are the only exceptions I can think of. Could you clarify?
I believe that if the container uses the current Adobe move implementation to make itself movable, then it will only be movable when it is also copyable,
Agreed.
which it won't be if the elements are move-only. But we'd probably want the container to be movable in this case, which would require something extra (the 'new way' I was referring to). If it's easy to add support for move-only types, then maybe this wouldn't be too much to do.
If you have been proposing some kind of external adaptation that allows the library to recognize the funky conversions used... that makes sense and I don't have any better ideas. A few litmus tests we could consider are the ability to work with http://www.coderage.com/move_ptr, the usual std::auto_ptr implementations, and the one proposed in http://groups.google.com/group/comp.std.c++/msg/71e5799e3c1b70c7
I don't know whether you consider this relevant, but I think that Boost ought to adopt something like Adobe's move-aware standard container collection, just to avoid layering issues (something in boost needs a move-aware container, so it uses ASL, which in turn uses boost).
I think that's pretty much what Ion is proposing for the Interprocess containers.
Well, yeah, but I mean for the regular std:: containers -- Dave Abrahams BoostPro Computing http://www.boostpro.com
2008/6/23 David Abrahams <dave@boostpro.com>:
A few litmus tests we could consider are the ability to work with http://www.coderage.com/move_ptr, the usual std::auto_ptr implementations, and the one proposed in http://groups.google.com/group/comp.std.c++/msg/71e5799e3c1b70c7
I don't expect to support everything that's out there. But std::auto_ptr is an important case.
I think that's pretty much what Ion is proposing for the Interprocess containers.
Well, yeah, but I mean for the regular std:: containers
You might have confused the Interprocess containers with the Intrusive ones. The Interprocess containers are STL containers with full allocator support. This is needed because most STL implementations only have the bare minimum so they won't work with the Interprocess allocators. There's some documentation at: http://tinyurl.com/4jyocx and http://tinyurl.com/3vxrt2 Daniel
Daniel James wrote:
2008/6/23 David Abrahams <dave@boostpro.com>:
A few litmus tests we could consider are the ability to work with http://www.coderage.com/move_ptr, the usual std::auto_ptr implementations, and the one proposed in http://groups.google.com/group/comp.std.c++/msg/71e5799e3c1b70c7
I don't expect to support everything that's out there. But std::auto_ptr is an important case.
I don't mean we should have OOTB support for everything out there, but the ability to use external adaptation to make everything out there work is at least a reasonable thing to think about.
I think that's pretty much what Ion is proposing for the Interprocess containers. Well, yeah, but I mean for the regular std:: containers
You might have confused the Interprocess containers with the Intrusive ones. The Interprocess containers are STL containers with full allocator support. This is needed because most STL implementations only have the bare minimum so they won't work with the Interprocess allocators. There's some documentation at: http://tinyurl.com/4jyocx and http://tinyurl.com/3vxrt2
Yep, I guess I had forgotten that. See my other recent posting, too: http://news.gmane.org/find-root.php?message_id=%3c486394D0.3040500%40boostpr... -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On 23/06/2008, Daniel James <daniel_james@fmail.co.uk> wrote:
2008/6/23 David Abrahams <dave@boostpro.com>:
I have a hunch that it would be really easy to add support for move-only types, though. Do you see any specific obstacles?
I had a quick try at implementing move-only types. It looks like you're right: http://svn.boost.org/trac/boost/changeset/46631 y.hpp contains the move-only type. The code might look familiar. It mostly works. I've found two problems so far. Firstly, is_convertible didn't work for the type, but I managed to work around that (I'll probably need to refine the change to is_movable). Secondly, it doesn't seem to be able to pass rvalues by reference. I'm not sure how to get round that, I'll have to learn more about the trick used to implement it. Daniel
Daniel James wrote:
On 23/06/2008, Daniel James <daniel_james@fmail.co.uk> wrote:
2008/6/23 David Abrahams <dave@boostpro.com>:
I have a hunch that it would be really easy to add support for move-only types, though. Do you see any specific obstacles?
I had a quick try at implementing move-only types. It looks like you're right:
http://svn.boost.org/trac/boost/changeset/46631
y.hpp contains the move-only type. The code might look familiar.
:-)
It mostly works. I've found two problems so far. Firstly, is_convertible didn't work for the type,
You found a bug in is_convertible?
but I managed to work around that (I'll probably need to refine the change to is_movable). Secondly, it doesn't seem to be able to pass rvalues by reference. I'm not sure how to get round that, I'll have to learn more about the trick used to implement it.
IIRC there is a rule in C++03 that when binding a reference to an rvalue, that rvalue must be copyable (and may in fact be copied at the discretion of the compiler). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
I don't know whether you consider this relevant, but I think that Boost ought to adopt something like Adobe's move-aware standard container collection, just to avoid layering issues (something in boost needs a move-aware container, so it uses ASL, which in turn uses boost).
I agree. Maybe just adopting ASL code is better for Boost. My intention was to have containers compatible with shared memory, move semantics and start adding features like Scoped Allocators or realloc for vectors. Regards, Ion
Daniel James wrote:
In most cases it relies on return value optimization to move the type. The library also supplies several functions and algorithms for dealing with movable types. So my plan was to separate the library into two parts - move emulation and the move functions and algorithms. And then work on making the algorithms generic enough to support other move emulation methods. So that a container will be able to efficiently deal with Boost.Thread's move-only objects, Adobe movable object and objects using rvalue references.
Sounds good.
With new containers (forward_list) in the standard and having move-aware containers in Interprocess, I was wondering if it would be a good idea to move those containers outside Interprocess. In the future we could make those containers compatible with Scoped Allocators (2554, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2554.pdf).
I think this might be a good idea. We could possibly bring together all the containers from the C++0x draft (of the top of my head: your containers, the unordered containers and Boost.Array). It'll also be good to cooperate when implementing some of the latest features (such as 'emplace') which will probably require similar features across the containers.
Great. We should try to add MultiIndex, Bimap, CircularBuffer (and maybe for some features Intrusive) to the game.
Daniel
Regards, Ion
participants (4)
-
Daniel James -
David Abrahams -
Ion Gaztañaga -
Mathias Gaunard