220 23756 <657cb0a7-4854-41c6-963f-5a11cc677157@isocpp.org> article Path: news.gmane.org!not-for-mail From: quicknir@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Allowing uncopyable allocators Date: Sat, 16 Jan 2016 15:38:45 -0800 (PST) Lines: 251 Approved: news@gmane.org Message-ID: <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_176_1034829407.1452987525462" X-Trace: ger.gmane.org 1452987533 21013 80.91.229.3 (16 Jan 2016 23:38:53 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 16 Jan 2016 23:38:53 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCH65356YUARBBVJ5O2AKGQEU5N6FOY@isocpp.org Sun Jan 17 00:38:49 2016 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-oi0-f72.google.com ([209.85.218.72]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1aKaQi-0000OR-EW for gclcip-std-proposals@m.gmane.org; Sun, 17 Jan 2016 00:38:48 +0100 Original-Received: by mail-oi0-f72.google.com with SMTP id x140sf451772413oif.2 for ; Sat, 16 Jan 2016 15:38:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:message-id:subject:mime-version:content-type :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=otgKgv2h/FTmW9rGMjI6HoSX+dia7TsiM4TZt3k8s9A=; b=XAp565/9Nl+EJ/jfUTHxnSCzPhPnp1USiRNRY7LJaFqxQS4PqGZ3HV3lgFGcCrZqQN qCSdbAryyHsErK2OxJvoCQGRNm8+ZJ/RNOpP0/MnRoPiQ8fSJl5eaPWb2TfTkXjCsf5o giJjPgSXHC18HtcN9uUMGtOUQCvZVDRpH86WfkSHasNY4RfZgFKxOgWVWpDG8AvPfOrV PyZTeQ5YyExQnd9l94RGdeQnSq08eD8lbEDjzL2F0ElsSbgumDaiCbuvrzzzPepRyGxZ CBD1v8c0M10dgGZx56D9DyKxMKlSaFc7nUop2NHoTu4Jr5L9idUjDhvnSH/nAbSbzz+x gOOQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=date:from:to:message-id:subject:mime-version:content-type :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=otgKgv2h/FTmW9rGMjI6HoSX+dia7TsiM4TZt3k8s9A=; b=DO1Csv9vgsnyOTdtjdDecDcAVN2KUOg9WwljD4Bb19LSmNslWWO1pliOuBefuA1n4o CTvGuN1E/veppdddrmcJT0taLwuc42X7Swg79g1uKLD1eAWsuPopR3YYDOv915iE+Ok3 8rfbJXjxXo/sV4YIexqn6pDLw6Pr0WjN+7PEwAmYkW3vYWJlSTojzyIegVYvhEtFbQmC 6wAet7KQe1+xOIQgsMfhKAowPTq38UeWMoSW+hcOa17CqF+9c5y+1ZEydw1gyY70LkOD YS0p/DyWBrgilrVAJmdha0eQwAdY3Su4wO7njnm+dSltk9k3aeJKOILRn0X666EM6KTC eLGQ== 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:message-id:subject:mime-version :content-type: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=otgKgv2h/FTmW9rGMjI6HoSX+dia7TsiM4TZt3k8s9A=; b=Bg0CsUzhvkM5CRS0gaN0A59nTTgGz7rcBZEjhOexxsEIXr+jhOp6EzG7im+mr9zf8c k6Y/5gaueyLbAqI/mTbleBtcbsLitK/odSG/qovFDjldZmM6UJujHe+5gNnXGy3u0+dX Uz4Vd+GDPEO6xWEUVs/T8ZmbzXs5FHzrk5uxy4RwRYu21FinUWNsuUaPjlPnbU3knPHT 2FX4++4WJ8oVFcyIzqUgAOAF1h4C5r5RDKglWTIZLMI1bizTz2qOpJ3Wf4N9wx+4JpDy /LDSoVlvTNQKWBXVJ8O15vNpedNq9WiQcMDu/gNMxaJLpIHYgbbZMMWI3vuSYlK4e08n N58g== X-Gm-Message-State: ALoCoQkZP7m8csgH+MK2TwrRRrnsAAEVLb6hfTh3nqkcHIkknA3EXIoPoWjnq1REJ2SXEPdx2wYzb8hFdn9wBzqi125VtCTfiA== X-Received: by 10.107.136.20 with SMTP id k20mr16680847iod.5.1452987527435; Sat, 16 Jan 2016 15:38:47 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.50.43.129 with SMTP id w1ls532685igl.22.canary; Sat, 16 Jan 2016 15:38:46 -0800 (PST) X-Received: by 10.50.115.69 with SMTP id jm5mr102883igb.10.1452987526520; Sat, 16 Jan 2016 15:38:46 -0800 (PST) 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:23756 Archived-At: ------=_Part_176_1034829407.1452987525462 Content-Type: multipart/alternative; boundary="----=_Part_177_425754619.1452987525462" ------=_Part_177_425754619.1452987525462 Content-Type: text/plain; charset=UTF-8 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. Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/. ------=_Part_177_425754619.1452987525462 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Currently, allocators seem to be absolute= ly required to be copy constructable. This is actually a very stringent req= uirement; the copy constructed allocator must compare equal to the original= allocator, which for allocators implies that they can allocate and dealloc= ate 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 the= ir own resources? Such allocators can never really allocate or deallocate e= ach 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 issu= e; there's no real situation where you would ever necessarily expect th= em to compare equal. The current requirement of copyability is artificial t= hough, all of the tools are already in place to avoid it. An allocator that= =C2=A0sets=C2=A0propagate_on_container_copy_ass= ignment=C2=A0to false=C2=A0 already doesn't need to be copy assi= gnable. And if an allocator defines=C2=A0select= _on_container_copy_construction=C2=A0it is never "conceptually&= quot; copied. Consider the following example:
<= br>
#include <vector>
#include <iostream>

template <class T><= /font>
struct SimpleAllocator {
=C2=A0 typedef T value_type;
=C2=A0 SimpleAllocator() =3D default;
=C2=A0 template <class U> SimpleAllocator(const SimpleAllocator&l= t;U>& other) {};
=C2=A0 T* allocat= e(std::size_t n) { return new T[n]; };
= =C2=A0 void deallocate(T* p, std::size_t n) { delete [] p; };
<= div>
=C2=A0 SimpleAl= locator(const SimpleAllocator&) { std::cerr << "copy\n"= ; };
=C2=A0 SimpleAllocator(SimpleAllocat= or&&) =3D default;
=C2=A0 SimpleA= llocator& operator=3D(const SimpleAllocator&) =3D delete;
=C2=A0 SimpleAllocator& operator=3D(SimpleAllo= cator&&) =3D default;

=
=C2=A0 SimpleAllocator select_on_container_copy= _construction() const {
=C2=A0 =C2=A0 std= ::cerr << "blah\n";
=C2= =A0 =C2=A0 return SimpleAllocator{};
=C2= =A0 }
};

template <class T, class U><= /font>
bool operator=3D=3D(const SimpleAllocator= <T>&, const SimpleAllocator<U>&) { return true; }
template <class T, class U>
=
bool operator!=3D(const SimpleAllocator<T>&= , const SimpleAllocator<U>&) { return false; }
<= font size=3D"2">
int main(int argc, c= har **argv) {
=C2=A0 std::vector<doubl= e, SimpleAllocator<double>> x{1.0};
=C2=A0 std::cerr << x[0] << "\n";
=C2=A0 auto y =3D x;
}=

This example runs and prints:

=
copy
1
blah
copy

So constructing our container, which should simply default con= struct an allocator, also makes a copy, despite there being no "concep= tual" copy. When we copy construct, we create a new allocator using se= lect_on_container_copy_construction, and copy that new allocator, which is = also unnecessary.

<= font size=3D"2">If these unnecessary copies were eliminated, then it would = actually be quite simple =C2=A0to write allocators that owned their own res= ources. Such an allocator just needs a default constructor and move/swap, w= hich is typically =C2=A0These have multiple applications:
=
  • For data stru= ctures that perform many small allocations (like map and set), such an allo= cator would allow making some speed vs space trade-offs by chunking up allo= cations. This can be done in the current framework, but requires introducin= g 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 on= e 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 le= ss are served from this buffer, anything larger is sent to the heap. Conven= ient e.g. for std::function, or std::vector, and easy to customize.<= /span>
  • It has= interesting possibilities combined with scoped_allocators. I admit I haven= 't investigated these in depth, but it seems like it would allow scenar= ios similar to the first example; e.g. consider a vector<string>. The= inside strings are likely to make many small allocation requests. If the v= ector has a scoped allocator that owns it own resources (i.e. allocates lar= ge chunks of memory), then it can give the strings allocators that referenc= e the outer allocator. Again, the same can be accomplished with memory pool= s, but this is cleaner.
My pro= posal would basically be to change the Allocator concept so that copy const= ructability is only necessary if=C2=A0select_on_container_copy_construction=C2=A0is not defined, or if the allocator uses it intern= ally. In turn, AllocatorAware would be changed to never make unnecessary co= pies; which would also mean changing the standard library. This does not re= quire any core language changes, and what's more it is backwards compat= ible. Since it broadens the definition of legal allocators, all existing al= locators would continue to be allocators and usable in the STL. It would me= an that technically, user written AllocatorAware containers would not be st= rictly compliant, but they would keep working with std::allocator (which is= copyable of course) and any allocators they had written themselves.=C2=A0<= /span>

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.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals= /.
------=_Part_177_425754619.1452987525462-- ------=_Part_176_1034829407.1452987525462-- .