220 25350 <8a887b00-e400-4f63-8a66-c947448880d9@isocpp.org> article Path: news.gmane.org!not-for-mail From: Yun Chen Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Allowing uncopyable allocators Date: Sat, 26 Mar 2016 08:44:01 -0700 (PDT) Lines: 271 Approved: news@gmane.org Message-ID: <8a887b00-e400-4f63-8a66-c947448880d9@isocpp.org> References: <657cb0a7-4854-41c6-963f-5a11cc677157@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_1002_1058651017.1459007041523" X-Trace: ger.gmane.org 1459007047 6278 80.91.229.3 (26 Mar 2016 15:44:07 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 26 Mar 2016 15:44:07 +0000 (UTC) Cc: quicknir@gmail.com To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBC65FXV244GBBQW43K3QKGQE6I3VMXY@isocpp.org Sat Mar 26 16:44:06 2016 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-pf0-f197.google.com ([209.85.192.197]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1ajqNh-0007ju-Ry for gclcip-std-proposals@m.gmane.org; Sat, 26 Mar 2016 16:44:06 +0100 Original-Received: by mail-pf0-f197.google.com with SMTP id x3sf168669084pfb.3 for ; Sat, 26 Mar 2016 08:44:04 -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=APfiE2GqMbIhCPetDqrAi0obYIp9eJSDbajqrgoCcU4=; b=oN5MwtusIBohDtBqiL3uXbnDa6/QbXnwXyywGDdePUpLlQJ1uesIw4+yZeL9//gorU RmcbMKSirZ2oQ+8QeRJMCNobEHQZPBB751TbQPRFz0+ZgVNNpNJFPRTTk+9zPzvYbIU0 eB4SdZSXhbsJyNpYH32tAzCb7kY0/3cQ4hU9vDS9efS5C7BXpYTf1xqf7TrEsb7lsdZq z/LEHbvDPEouVdolHnnofvv8YV8PsNJunU77xGGEpjMRLnS003na1I8Wsg3TlDksOleD UmThbtZg/ukUmig+Ugw2YXc0BNLOfeG0ZZqJ0g9zD/6CXkgRvY7jWE1AdT/yN5fitTFO rAZw== 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=APfiE2GqMbIhCPetDqrAi0obYIp9eJSDbajqrgoCcU4=; b=vFcsBJcD+6cdy4V8KjY3i34KrFnVT7dxyFl+H89ECwHmWrM0ta6bXYAFo2odDmzZKT pPZL2YMCH5SsuPItmpqL1jkbaBEYWIWFJ09DbJhrAUX0GYmxsO0ZPU4wjXt05tIuEWhY y9lEF9mzPcOMIe0MsJXHmTaEHu9/WP7VKKBeP5ME2oPQYNU9LNfbTmKxzlnYZSRXwIDR GNKFd9/M9gK7ls5ryn7xUFFGH9Kw8eHh5pN230IZDdnHoiuvRWI6l/IO3zY9RePWzBIG n0WDzpkk6LE8YrtEQDhS+1Ebpy1rEHyhluBoBTJoBr/vGijZ0yb6dhAx/tNikoSE6iMJ eu5A== 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=APfiE2GqMbIhCPetDqrAi0obYIp9eJSDbajqrgoCcU4=; b=mEBsM1rEd1bS/kFEviZl/LmZiWGclUuhH6xranNQnsCFIPR/+3Wt2XXWqYN9nPar19 14tT3ji+l1I2xSlwKcJ7B30DpXgW5vck2Dn00VJq+hwBTVdrt7aBgCx1uRj5Fvsh56Tw 1B9Ip1U7ERAswUEZWAYglu49mU44PipqgyEVy7YMg+YOv8TzLgSWi0fpXs1+khHXGePo canXhF/XxzqqyppDPPl8fiBo7dECJRh2pcdyb3T80zDST6/O5qJzx1c3i0UM/qjo4LAC ltIB+MLca0UXeaAQHUkeaul4TfnZh52UqncwFZkPmxTgM0AlNaG4UoeN53SVeaC5bYsv GENA== X-Gm-Message-State: AD7BkJIILPO0286xtRoIsR6Kqj2LkCUEgo4xzwLwqZHXJomtlOxegNGrHIzZN4XS5iUW7A== X-Received: by 10.66.146.194 with SMTP id te2mr11894627pab.17.1459007043916; Sat, 26 Mar 2016 08:44:03 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.50.142.1 with SMTP id rs1ls435860igb.7.canary; Sat, 26 Mar 2016 08:44:02 -0700 (PDT) X-Received: by 10.50.147.8 with SMTP id tg8mr21262igb.8.1459007042679; Sat, 26 Mar 2016 08:44:02 -0700 (PDT) In-Reply-To: <657cb0a7-4854-41c6-963f-5a11cc677157@isocpp.org> X-Original-Sender: yun.go.chen@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:25350 Archived-At: ------=_Part_1002_1058651017.1459007041523 Content-Type: multipart/alternative; boundary="----=_Part_1003_963224163.1459007041524" ------=_Part_1003_963224163.1459007041524 Content-Type: text/plain; charset=UTF-8 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/8a887b00-e400-4f63-8a66-c947448880d9%40isocpp.org. ------=_Part_1003_963224163.1459007041524 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I second the usefulness. Our allocator owns the resou= rce as well and it has been very painful to tweak STL implementations to do= that.

We should extend it to move construction th= rough select_on_container_move_construction, as we need the ability of defa= ult constructing the allocator too. This would be required to move construc= t an container in an arena from stack. =C2=A0


On Sa= turday, January 16, 2016 at 6:38:45 PM UTC-5, quic...@gmail.com wrote:
C= urrently, allocators seem to be absolutely required to be copy constructabl= e. This is actually a very stringent requirement; the copy constructed allo= cator must compare equal to the original allocator, which for allocators im= plies 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 c= an never really allocate or deallocate each other's pointers, so they c= an 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 wh= ere you would ever necessarily expect them to compare equal. The current re= quirement of copyability is artificial though, all of the tools are already= in place to avoid it. An allocator that=C2=A0sets=C2=A0propaga= te_on_container_copy_assignment=C2=A0to false=C2=A0 already doe= sn't need to be copy assignable. And if an allocator defines=C2=A0select_on_container_copy_construction=C2=A0it is never &= quot;conceptually" copied. Consider the following example:
=
#include <v= ector>
#include <iostream>

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

= =C2=A0 SimpleAllocator(const SimpleAllocator&) { std::cerr << &qu= ot;copy\n"; };
=C2=A0 SimpleAllocato= r(SimpleAllocator&&) =3D default;
=C2=A0 SimpleAllocator& operator=3D(const SimpleAllocator&) = =3D delete;
=C2=A0 SimpleAllocator& o= perator=3D(SimpleAllocator&&) =3D default;

=C2=A0 SimpleAllocator sel= ect_on_container_copy_construction() const {
=C2=A0 =C2=A0 std::cerr << "blah\n";
<= div>=C2=A0 =C2=A0 return SimpleAllocator{};
=C2=A0 }
};

template &l= t;class T, class U>
bool operator=3D= =3D(const SimpleAllocator<T>&, const SimpleAllocator<U>&= ;) { return true; }
template <class T,= class U>
bool operator!=3D(const Simp= leAllocator<T>&, const SimpleAllocator<U>&) { return fa= lse; }

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

This example runs and prints:
<= div>
copy
1
blah
copy
<= br>
So constructing our container, which = should simply default construct an allocator, also makes a copy, despite th= ere 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 w= ere eliminated, then it would actually be quite simple =C2=A0to write alloc= ators that owned their own resources. Such an allocator just needs a defaul= t constructor and move/swap, which is typically =C2=A0These have multiple a= pplications:
  • For data structures that perform many small allocations (lik= e map and set), such an allocator would allow making some speed vs space tr= ade-offs by chunking up allocations. This can be done in the current framew= ork, but requires introducing a memory pool, which often has separate lifet= ime, or perhaps is co-owned by its allocators via shared_ptr. Using an owni= ng allocator is much simpler and hassle free; it is a drop in replacement w= ith a typedef.
  • It allows one to force the small X optimization on any data s= tructure (less efficiently, of course). For instance, one could create an a= llocator that deliberately contains 64 bytes of empty storage. Allocation r= equests for 64 bytes or less are served from this buffer, anything larger i= s sent to the heap. Convenient e.g. for std::function, or std::vector, and = easy to customize.
  • It has interesting possibilities combined with scoped_all= ocators. I admit I haven't investigated these in depth, but it seems li= ke it would allow scenarios similar to the first example; e.g. consider a v= ector<string>. The inside strings are likely to make many small alloc= ation requests. If the vector has a scoped allocator that owns it own resou= rces (i.e. allocates large chunks of memory), then it can give the strings = allocators that reference the outer allocator. Again, the same can be accom= plished with memory pools, but this is cleaner.
My proposal would basically be to change the Allocator co= ncept so that copy constructability is only necessary if=C2=A0select_on_container_copy_construction=C2=A0is not defined, or if the allocator uses = it internally. In turn, AllocatorAware would be changed to never make unnec= essary copies; which would also mean changing the standard library. This do= es not require any core language changes, and what's more it is backwar= ds compatible. Since it broadens the definition of legal allocators, all ex= isting 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 themselve= s.=C2=A0

Thoughts and criticism welcome!

--
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/8a887b00-e400-4f63-8a66-c947448880d9= %40isocpp.org.
------=_Part_1003_963224163.1459007041524-- ------=_Part_1002_1058651017.1459007041523-- .