Allowing uncopyable allocators

[quic...@gmail.com]

Currently, allocators seem to be absolutely required to be copy constructable. This is actually a very stringent requirement; the copy constructed allocator must compare equal to the original allocator, which for allocators implies that they can allocate and deallocate each other's pointers. This is fine if your allocators simply hold pointers back to a memory pool. But what if your allocators want to own their own resources? Such allocators can never really allocate or deallocate each other's pointers, so they can never compare equal. This sounds like a big deal, but if your allocator is uncopyable, then it's not an issue; there's no real situation where you would ever necessarily expect them to compare equal. The current requirement of copyability is artificial though, all of the tools are already in place to avoid it. An allocator that sets propagate_on_container_copy_assignment to false  already doesn't need to be copy assignable. And if an allocator defines select_on_container_copy_construction it is never "conceptually" copied. Consider the following example:

#include <vector>

#include <iostream>

template <class T>

struct SimpleAllocator {

  typedef T value_type;

  SimpleAllocator() = default;

  template <class U> SimpleAllocator(const SimpleAllocator<U>& other) {};

  T* allocate(std::size_t n) { return new T[n]; };

  void deallocate(T* p, std::size_t n) { delete [] p; };

  SimpleAllocator(const SimpleAllocator&) { std::cerr << "copy\n"; };

  SimpleAllocator(SimpleAllocator&&) = default;

  SimpleAllocator& operator=(const SimpleAllocator&) = delete;

  SimpleAllocator& operator=(SimpleAllocator&&) = default;

  SimpleAllocator select_on_container_copy_construction() const {

    std::cerr << "blah\n";

    return SimpleAllocator{};

  }

};

template <class T, class U>

bool operator==(const SimpleAllocator<T>&, const SimpleAllocator<U>&) { return true; }

template <class T, class U>

bool operator!=(const SimpleAllocator<T>&, const SimpleAllocator<U>&) { return false; }

int main(int argc, char **argv) {

  std::vector<double, SimpleAllocator<double>> x{1.0};

  std::cerr << x[0] << "\n";

  auto y = x;

}

This example runs and prints:

copy

1

blah

copy

So constructing our container, which should simply default construct an allocator, also makes a copy, despite there being no "conceptual" copy. When we copy construct, we create a new allocator using select_on_container_copy_construction, and copy that new allocator, which is also unnecessary.

If these unnecessary copies were eliminated, then it would actually be quite simple  to write allocators that owned their own resources. Such an allocator just needs a default constructor and move/swap, which is typically  These have multiple applications:

• For data structures that perform many small allocations (like map and set), such an allocator would allow making some speed vs space trade-offs by chunking up allocations. This can be done in the current framework, but requires introducing a memory pool, which often has separate lifetime, or perhaps is co-owned by its allocators via shared_ptr. Using an owning allocator is much simpler and hassle free; it is a drop in replacement with a typedef.
• It allows one to force the small X optimization on any data structure (less efficiently, of course). For instance, one could create an allocator that deliberately contains 64 bytes of empty storage. Allocation requests for 64 bytes or less are served from this buffer, anything larger is sent to the heap. Convenient e.g. for std::function, or std::vector, and easy to customize.
• It has interesting possibilities combined with scoped_allocators. I admit I haven't investigated these in depth, but it seems like it would allow scenarios similar to the first example; e.g. consider a vector<string>. The inside strings are likely to make many small allocation requests. If the vector has a scoped allocator that owns it own resources (i.e. allocates large chunks of memory), then it can give the strings allocators that reference the outer allocator. Again, the same can be accomplished with memory pools, but this is cleaner.

My proposal would basically be to change the Allocator concept so that copy constructability is only necessary if select_on_container_copy_construction is not defined, or if the allocator uses it internally. In turn, AllocatorAware would be changed to never make unnecessary copies; which would also mean changing the standard library. This does not require any core language changes, and what's more it is backwards compatible. Since it broadens the definition of legal allocators, all existing allocators would continue to be allocators and usable in the STL. It would mean that technically, user written AllocatorAware containers would not be strictly compliant, but they would keep working with std::allocator (which is copyable of course) and any allocators they had written themselves. 

Thoughts and criticism welcome!

[Zhihao Yuan]

On Sat, Jan 16, 2016 at 5:38 PM, <quic...@gmail.com> wrote:
>
> SimpleAllocator(const SimpleAllocator&) { std::cerr << "copy\n"; };
> SimpleAllocator(SimpleAllocator&&) = default;
> SimpleAllocator& operator=(const SimpleAllocator&) = delete;
> SimpleAllocator& operator=(SimpleAllocator&&) = default;
>
> SimpleAllocator select_on_container_copy_construction() const {
> std::cerr << "blah\n";
> return SimpleAllocator{};
> }

There won't be any issue after

http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0135r0.html

being accepted.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://bit.ly/blog4bsd

[quic...@gmail.com]

While this proposal may make it easier to implement such containers, and may even cause certain containers of certain standard library types to happen to work with such an allocator, this is not sufficient. Even if copy elision is mandatory under certain circumstances, this doesn't change the fact that a conforming implementation is free to copy around allocators as much as it wants, because a conforming allocator has to be copy constructible. Any allocator written in that environment would be non-portable, which isn't acceptable for many. It's still necessary to change the definition of a conforming allocator.

This proposal may make it so that the standard library doesn't have to make any changes to have compliant containers, but that is all, and even that I'm not certain about. Even without this proposal it is certainly possible to make things work, though it may be trickier. The proposal in any case seems to be largely about situations where at least a move can be guaranteed instead of a copy, it is just that total elision cannot be guaranteed. In this situation, moving is fine, it's that actual unnecessary copies are taking place.

Let me know if you feel I've misunderstood.

[Zhihao Yuan]

On Sun, Jan 17, 2016 at 12:36 AM, <quic...@gmail.com> wrote:
> Even if copy elision is mandatory under certain circumstances, this doesn't
> change the fact that a conforming implementation is free to copy around
> allocators as much as it wants, because a conforming allocator has to be
> copy constructible.

I see where the "problem" is. But this will require changing all
functions taking a default constructed allocator as const& in the
signatures.

And you need to convince people about why it's useful.
To me, only polymorphic memory resource is useful; other
people may have different opinions.

[quic...@gmail.com]

THat would be one solution, and the preferred one. I don't see a big problem with taking it by value. Since it is stored by value, slicing is not an issue. And a copy is being made anyway, passing by value when a copy is needed is accepted practice. Another solution would be to leave the pass by const ref but eliminate the default, and then provide additional overloads that simply construct the allocator internally. This is less desirable as it will limit uncopyable allocators to default construction.

Not sure what polymorphic means in this context (polymorphic allocator?), but I did give three use cases. I've literally seen examples of people rewriting std::function from scratch so that they could change the size of the small function optimization because heap allocation is a major issue for them. I've also seen people ask about having a small vector optimization. Right now, people are forever saddled with the standard library's decisions when it comes to small object stack optimization, this seems like something allocators should be able to do. I think my other two examples are good as well; memory pools are great in many cases, but they certainly are a hassle, there are both liffetime and threading issues with them. A chunk allocator for std::map seems like an almost free (minor memory cost) performance boost.

[Yun Chen]

I second the usefulness. Our allocator owns the resource as well and it has been very painful to tweak STL implementations to do that.

We should extend it to move construction through select_on_container_move_construction, as we need the ability of default constructing the allocator too. This would be required to move construct an container in an arena from stack.  

[David Krauss]

On 2016–01–17, at 7:38 AM, quic...@gmail.com wrote:

But what if your allocators want to own their own resources? Such allocators can never really allocate or deallocate each other's pointers, so they can never compare equal. This sounds like a big deal, but if your allocator is uncopyable, then it's not an issue; there's no real situation where you would ever necessarily expect them to compare equal.

It would be nice to see this avenue pursued. It would allow “small” or “local” vectors to be specializations of std::vector. Locally-optimized versions of all the standard containers would appear for minimal effort.

On 2016–01–17, at 12:12 PM, Zhihao Yuan <z...@miator.net> wrote:

There won't be any issue after

 http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0135r0.html

being accepted.

The interface for initializing and retrieving the internal allocator would need to be revised, at least for the new local allocators. It would be nice to even remove it, but querying the remaining capacity is too useful.

(Regarding “never equal,” pedantically, if you can obtain a reference to a local allocator, then it should compare equal to itself.)

On 2016–01–17, at 3:50 PM, quic...@gmail.com wrote:

Not sure what polymorphic means in this context (polymorphic allocator?),

Polymorphic allocators exist on the opposite end of the overall problem domain of allocators. Every allocator object gets reduced to a polymorphic pointer, and every allocation and deallocation is dispatched as a virtual function. This helps interoperability at the expense of performance. It’s part of the Fundamentals TS; it may or may not be adopted by C++17.

I've literally seen examples of people rewriting std::function from scratch so that they could change the size of the small function optimization because heap allocation is a major issue for them.

This seems to be fairly common. Unfortunately, the small function optimization takes place outside the allocator. You could perhaps hack a local allocator into my function_container template. But you’d want to forbid converting that back to an ordinary function, or else do something clever like heap-allocate the local allocator. The library doesn’t provide for that. Also, the ordinary small-function optimization would be made redundant… it’s possible that this is an entirely different problem.

On 2016–03–26, at 11:44 PM, Yun Chen <yun.g...@gmail.com> wrote:

We should extend it to move construction through select_on_container_move_construction, as we need the ability of default constructing the allocator too. This would be required to move construct an container in an arena from stack.  

… and lest it be overlooked, if these allocators aren’t copyable, they’re not movable either.

[quic...@gmail.com]

That is a good point. Currently, from what I can see, containers purely assume that they can "take ownership" of existing elements on move construction. This means that the container never calls copy or move constructors on individual elements during container move construction. It's worth being aware though that select_on_container_move_construction is actually more complex than any of the existing traits. The select_on_..._copy equivalent is simply a function that's called to get the new allocator (which, if not provided, calls the allocator copy constructor), after which the elements are copied over; there's no branching per se. The other traits (propagate_on{copy/move_assignment, swap}) are simply booleans, if they are true than the allocator is propagated, if not then it isn't. Here, there's a bit of a mixture of both logic: if select_on_...move_ is defined, then the container should call it, and then call the move constructor for each element individually. If it is not defined, then it should move the allocator and do nothing else.

It's getting to the point where it might just be preferable for allocators to have an "is_movable" trait, since generally select_on_...move, propagate on move, propagate on swap are all very closely related. But it's unlikely such a major change could be accepted.

[quic...@gmail.com]

Thanks for the good point about "never equal".

The fact that the small function optimization takes place outside the allocator isn't what makes it impossible (as I later realized) to exploit this technique for std::function. After all, the small string optimization takes place outside the allocator for string, yet it would still be possible to write an allocator that owns stack resources and get a "medium" string optimization without touching string's source code in any way. The problem is that std::function type erases its allocator. Since the allocator is not part of the type, it already lives on the heap from the get-go, so the allocator cannot help you put anything on the stack. I understand why std::function is written this way; it makes sense in the common use case even if it happens to make this optimization impossible.

> … and lest it be overlooked, if these allocators aren’t copyable, they’re not movable either.

Yes, that is a good point. It took me a while to parse Yun's post. I may need to think a bit more about a stack-space owning allocator. For anything that lives entirely on the stack and contains no pointers, copying and moving are equivalent as you point out. So making it uncopyable is the same as making it unmovable. The problem is I really don't like the idea of unmovable objects; they're extremely rare, and hard to work with. The flip side is though that the stack owning allocator cannot really copy/move itself without copying/moving the elements. This may actually be ok as the allocator is templated on the type it holds, so it can actually move the objects around if it needs to. I'm not sure which alternative is better/worse.

[David Krauss]

On 2016–03–29, at 10:59 PM, quic...@gmail.com wrote:

Thanks for the good point about "never equal".

The fact that the small function optimization takes place outside the allocator isn't what makes it impossible (as I later realized) to exploit this technique for std::function. After all, the small string optimization takes place outside the allocator for string, yet it would still be possible to write an allocator that owns stack resources and get a "medium" string optimization without touching string's source code in any way. The problem is that std::function type erases its allocator. Since the allocator is not part of the type, it already lives on the heap from the get-go, so the allocator cannot help you put anything on the stack. I understand why std::function is written this way; it makes sense in the common use case even if it happens to make this optimization impossible.

That’s right for std::function, but you still might take a look at the function_container class in my library  I’ve written one proposal for it already (P0043), and I’d like for such a thing to be either standard or user-implementable with interoperability with std::function. (The distinction between “small” and “medium” represents unnecessary overhead, though.)

> … and lest it be overlooked, if these allocators aren’t copyable, they’re not movable either.

Yes, that is a good point. It took me a while to parse Yun's post. I may need to think a bit more about a stack-space owning allocator. For anything that lives entirely on the stack and contains no pointers, copying and moving are equivalent as you point out. So making it uncopyable is the same as making it unmovable. The problem is I really don't like the idea of unmovable objects; they're extremely rare, and hard to work with. The flip side is though that the stack owning allocator cannot really copy/move itself without copying/moving the elements. This may actually be ok as the allocator is templated on the type it holds, so it can actually move the objects around if it needs to. I'm not sure which alternative is better/worse.

The semantics are what they are what they are, like it or not: the allocator isn’t practically able to make another of itself.

An allocator should certainly not be aware of the contents of its allocation blocks. For one thing, it can’t assume that they contain constructed objects. (This may be sort-of implementable if construct and destroy perform bookkeeping, but not without overhead. And the user is free to reuse the storage for other things.)

Which is easier:

1. An allocator which lives inside a movable and copyable container, but which is ill-formed if you attempt a move operation on the allocator itself.

2. An allocator which allows copy (and move-as-copy) operations, with surprising and not-allocator-like semantics.

“Hard to work with” is a good thing for objects with tricky semantics.

[Sean Middleditch]

On Saturday, March 26, 2016 at 9:59:20 AM UTC-7, David Krauss wrote:

On 2016–01–17, at 7:38 AM, quic...@gmail.com wrote:

But what if your allocators want to own their own resources? Such allocators can never really allocate or deallocate each other's pointers, so they can never compare equal. This sounds like a big deal, but if your allocator is uncopyable, then it's not an issue; there's no real situation where you would ever necessarily expect them to compare equal.

It would be nice to see this avenue pursued. It would allow “small” or “local” vectors to be specializations of std::vector. Locally-optimized versions of all the standard containers would appear for minimal effort.

Not by itself. There's still that small problem where the allocator has no idea what growth pattern the vector uses while the vector has no idea what the best initial size classes for the allocator would be. There's an extra missing bit of "protocol" needed between the two in order to fully genericize "small" or "fixed" containers like vector. Otherwise you end up with allocators that have room for up to 7 elements while the container tries to allocate room for an initial capacity of 16 elements.

The naive approach would work for just the small/fixed container use case. A good approach would likely work for other cases, e.g. a page allocator backing a vector requiring that the vector grow only in multiple-of-page-size increments.