220 25367 <33f9bac7-4b88-4620-b3c7-ed914f93299a@isocpp.org> article Path: news.gmane.org!not-for-mail From: quicknir@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Allowing uncopyable allocators Date: Tue, 29 Mar 2016 07:42:54 -0700 (PDT) Lines: 317 Approved: news@gmane.org Message-ID: <33f9bac7-4b88-4620-b3c7-ed914f93299a@isocpp.org> References: <657cb0a7-4854-41c6-963f-5a11cc677157@isocpp.org> <8a887b00-e400-4f63-8a66-c947448880d9@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_5522_1515053557.1459262574756" X-Trace: ger.gmane.org 1459262604 26009 80.91.229.3 (29 Mar 2016 14:43:24 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 29 Mar 2016 14:43:24 +0000 (UTC) Cc: quicknir@gmail.com To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCH65356YUARB35I5K3QKGQERTJU6FI@isocpp.org Tue Mar 29 16:43:23 2016 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-qk0-f199.google.com ([209.85.220.199]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1akurM-0003BI-IF for gclcip-std-proposals@m.gmane.org; Tue, 29 Mar 2016 16:43:08 +0200 Original-Received: by mail-qk0-f199.google.com with SMTP id e124sf28927164qkc.3 for ; Tue, 29 Mar 2016 07:43:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=vJhem9srkeb9elNLxLspIRkmYGdjXl/H/L38VXBSAxA=; b=13PGV0AcOh+wVUpcehOTKJVmbJgJaqT6i3WAQpxynEroEOAf5Zv7Z3ILJnxc5VQvNZ fiYc65N88o3AUAHQdKVg5ALJtMZB6NLjeNjMEZPI0q7l0xqZ6eZIKVhabgFwHe13JYKl Y8AFLTwXbLZ54AoU7UQSyNAHnvQFXH7u+uCUPfK5MQslgP/Qoe8eGDKZ9hnr94qVamMx +fGap1FwCXlsh7yRVwQw/ZdZZzpui/i0DtNYAipzsXksUP9+T871QQZNYMExVu0BIqPB Xm7mxBpbvFCbEmJlvTSsCshG+1B2y0LqTzxWANh1fE0zTTAz6Ar1xbwuQRO1OuEiVKrw H8wQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:cc:message-id:in-reply-to:references:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=vJhem9srkeb9elNLxLspIRkmYGdjXl/H/L38VXBSAxA=; b=MDRWyqhv/haaS1ahlz4x1ZBZnT1+YK0ey/qWfnHVqz9f4ad70RyMLeCAIN1Z+SiB8e NH6iAPXse8Z8BJrbwPBVK2wVM+wlTKdzSi+Umw7Gxlk9UBMZnZLW+SXALLKqWABGl5cl cDGi8TxtjxMEKhemkM/ilyWP31qyEYfdc0W5zvKcPH+4x8ln+7ad37hWyrfLii+4okRe cSkXKHVHvPgDwQ3q/iUJJmWVwyaqtqGMPgJ6239SfbD+o1idE26BpvR5kW2GO31wcS2y D7yhmZx4e10h9vlBSC09o6MY0XDK4sQQVIqMqockkqlb9W4itBcouTw8l/ZPJ4GzTsPT XiPA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:date:from:to:cc:message-id:in-reply-to :references:subject:mime-version:x-original-sender:reply-to :precedence:mailing-list:list-id:x-spam-checked-in-group:list-post :list-help:list-archive:list-subscribe:list-unsubscribe; bh=vJhem9srkeb9elNLxLspIRkmYGdjXl/H/L38VXBSAxA=; b=bR2c8EctvukppJHjXKoO8UgYIfMS8zsW50RPZwjpc67Aff7CoBuUng8Rd9CXFeqIF8 Lt3kmtof+XiOHUQa4gBDho9A3o8Xu9xwU+2DUGqSNxN0ryOgSDZL+8M/jm8qJJ/TohiS ABzDVPwsmLvG19jI/Sdtnw5EI6ewRbx3ROzK/DZh0c9gX9te6nrEYULPEFIE2BvLjClz m5r8BtyTgww8JOzW2IjCpbG9dE+CWfm9dASVR2vCb0lqoVR33wWL3ER0gVdQLrWiVH6V ZiWFhoHuBOIP/CMpNUE654OVXli++4OfQRXnsCCzwuGQvA8IrTiGVfEm3ZtLdEebshG5 PNVQ== X-Gm-Message-State: AD7BkJJ7tRLO/xvMFzn3f/0Ol6KDu9o5/5P6PCfKPAFioc/b+iKoaoq2rS8443pe7gQ5qA== X-Received: by 10.13.230.75 with SMTP id p72mr1392830ywe.45.1459262577292; Tue, 29 Mar 2016 07:42:57 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.107.62.69 with SMTP id l66ls222354ioa.54.gmail; Tue, 29 Mar 2016 07:42:55 -0700 (PDT) X-Received: by 10.50.155.72 with SMTP id vu8mr15284igb.5.1459262575774; Tue, 29 Mar 2016 07:42:55 -0700 (PDT) In-Reply-To: <8a887b00-e400-4f63-8a66-c947448880d9@isocpp.org> X-Original-Sender: quickNir@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:25367 Archived-At: ------=_Part_5522_1515053557.1459262574756 Content-Type: multipart/alternative; boundary="----=_Part_5523_1702318432.1459262574757" ------=_Part_5523_1702318432.1459262574757 Content-Type: text/plain; charset=UTF-8 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. On Saturday, March 26, 2016 at 11:44:01 AM UTC-4, Yun Chen wrote: > > 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. > > > On Saturday, January 16, 2016 at 6:38:45 PM UTC-5, quic...@gmail.com > wrote: >> >> 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 >> #include >> >> template >> struct SimpleAllocator { >> typedef T value_type; >> SimpleAllocator() = default; >> template SimpleAllocator(const SimpleAllocator& 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 >> bool operator==(const SimpleAllocator&, const SimpleAllocator&) { >> return true; } >> template >> bool operator!=(const SimpleAllocator&, const SimpleAllocator&) { >> return false; } >> >> int main(int argc, char **argv) { >> std::vector> 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. 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! >> > -- You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/33f9bac7-4b88-4620-b3c7-ed914f93299a%40isocpp.org. ------=_Part_5523_1702318432.1459262574757 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
That is a good point. Currently, from what I can see,= containers purely assume that they can "take ownership" of exist= ing elements on move construction. This means that the container never call= s copy or move constructors on individual elements during container move co= nstruction. 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 ge= t the new allocator (which, if not provided, calls the allocator copy const= ructor), after which the elements are copied over; there's no branching= per se. The other traits (propagate_on{copy/move_assignment, swap}) are si= mply booleans, if they are true than the allocator is propagated, if not th= en it isn't. Here, there's a bit of a mixture of both logic: if sel= ect_on_...move_ is defined, then the container should call it, and then cal= l 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 a= llocators to have an "is_movable" trait, since generally select_o= n_...move, propagate on move, propagate on swap are all very closely relate= d. But it's unlikely such a major change could be accepted.

On= Saturday, March 26, 2016 at 11:44:01 AM UTC-4, Yun Chen wrote:
I second the usefuln= ess. Our allocator owns the resource as well and it has been very painful t= o tweak STL implementations to do that.

We should = extend it to move construction through select_on_container_move_constr= uction, as we need the ability of default constructing the allocator too. T= his would be required to move construct an container in an arena from stack= .. =C2=A0


On Saturday, January 16, 2016 at 6:38:45 P= M UTC-5, quic...@gmail.com wrote:
Currently, allocators seem to be abs= olutely required to be copy constructable. This is actually a very stringen= t requirement; the copy constructed allocator must compare equal to the ori= ginal allocator, which for allocators implies that they can allocate and de= allocate 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 ow= n their own resources? Such allocators can never really allocate or dealloc= ate 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 expe= ct them to compare equal. The current requirement of copyability is artific= ial though, all of the tools are already in place to avoid it. An allocator= that=C2=A0sets=C2=A0propagate_on_container_copy_assignmen= t=C2=A0to false=C2=A0 already doesn't need to be copy assignable= .. And if an allocator defines=C2=A0select_on_container_cop= y_construction=C2=A0it is never "conceptually" copied. Con= sider the following example:

<= div>
#include <vector>
#include <iostream>

template <class T>
= struct SimpleAllocator {
=C2=A0 typedef T value_type;
=C2=A0 Simp= leAllocator() =3D default;
=C2=A0 templat= e <class U> SimpleAllocator(const SimpleAllocator<U>& other= ) {};
=C2=A0 T* allocate(std::size_t n) {= return new T[n]; };
=C2=A0 void dealloca= te(T* p, std::size_t n) { delete [] p; };

=C2=A0 SimpleAllocator(const Simple= Allocator&) { std::cerr << "copy\n"; };
=C2=A0 SimpleAllocator(SimpleAllocator&&) = =3D default;
=C2=A0 SimpleAllocator& = operator=3D(const SimpleAllocator&) =3D delete;
=C2=A0 SimpleAllocator& operator=3D(SimpleAllocator&&= ;) =3D default;

=C2=A0 SimpleAllocator select_on_container_copy_construc= tion() const {
=C2=A0 =C2=A0 std::cerr &l= t;< "blah\n";
=C2=A0 =C2=A0 = return SimpleAllocator{};
=C2=A0 }=
};

template <class T, class U>
=
bool operator=3D=3D(const SimpleAllocator<T>&am= p;, const SimpleAllocator<U>&) { return true; }
= template <class T, class U>
bool operator!=3D(const SimpleAllocator<T>&, const Simp= leAllocator<U>&) { return false; }

int main(int argc, char **argv) = {
=C2=A0 std::vector<double, SimpleAll= ocator<double>> x{1.0};
=C2=A0 s= td::cerr << x[0] << "\n";
=C2=A0 auto y =3D x;
}

This ex= ample runs and prints:

<= div>
copy
1
blah
copy

S= o constructing our container, which should simply default construct an allo= cator, also makes a copy, despite there being no "conceptual" cop= y. When we copy construct, we create a new allocator using select_on_contai= ner_copy_construction, and copy that new allocator, which is also unne= cessary.

If these unnecessary copies were eliminated, then it would actually = be quite simple =C2=A0to write allocators that owned their own resources. S= uch an allocator just needs a default constructor and move/swap, which is t= ypically =C2=A0These have multiple applications:
  • <= span style=3D"line-height:normal">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. Th= is 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 allo= cators 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 th= e 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 po= ssibilities combined with scoped_allocators. I admit I haven't investig= ated 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 sco= ped allocator that owns it own resources (i.e. allocates large chunks of me= mory), then it can give the strings allocators that reference the outer all= ocator. Again, the same can be accomplished with memory pools, but this is = cleaner.
My proposal would bas= ically be to change the Allocator concept so that copy constructability is = only necessary if=C2=A0select_on_contain= er_copy_construction=C2=A0is no= t defined, or if the allocator uses it internally. In turn, AllocatorAware = would be changed to never make unnecessary copies; which would also mean ch= anging the standard library. This does not require any core language change= s, and what's more it is backwards compatible. Since it broadens the de= finition of legal allocators, all existing allocators would continue to be = allocators and usable in the STL. It would mean that technically, user writ= ten AllocatorAware containers would not be strictly compliant, but they wou= ld keep working with std::allocator (which is copyable of course) and any a= llocators they had written themselves.=C2=A0

Thoughts and criticism wel= come!

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/33f9bac7-4b88-4620-b3c7-ed914f93299a= %40isocpp.org.
------=_Part_5523_1702318432.1459262574757-- ------=_Part_5522_1515053557.1459262574756-- .