220 14749 article Path: news.gmane.org!not-for-mail From: =?UTF-8?Q?David_Rodr=C3=ADguez_Ibeas?= Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: allocators with size_type size(const_pointer ptr) const noexcept; Date: Wed, 26 Nov 2014 14:33:06 +0000 Lines: 180 Approved: news@gmane.org Message-ID: References: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a1133e4cc0345be0508c3e8b8 X-Trace: ger.gmane.org 1417012399 4247 80.91.229.3 (26 Nov 2014 14:33:19 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 26 Nov 2014 14:33:19 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDIIVO6GQULBBJGJ26RQKGQEJ2FTEZQ@isocpp.org Wed Nov 26 15:33:13 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-pa0-f70.google.com ([209.85.220.70]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1XtdeY-0001n0-12 for gclcip-std-proposals@m.gmane.org; Wed, 26 Nov 2014 15:33:10 +0100 Original-Received: by mail-pa0-f70.google.com with SMTP id lj1sf16000459pab.5 for ; Wed, 26 Nov 2014 06:33:09 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:references:from:date:message-id :subject:to:content-type:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=MfxS0SbzTy7InO74ErNNTZebfcOxdyQ52nikkUV7HAI=; b=dRkVRuY2+hy4teE5g1d4wWZ+ANggbDjW9TNfE7FDWqKb5GL9hGyeBJSTW93yLEyEP/ tZyb0kzsat4KuzFqZWelcFHaXxTB8tyokcBTV+Q1iJy3twl2J0R6+6UHjiAnqFoF6X1d q9L1fVSO/CL3R0Mcv5BNtk8ajLLsKzoJh4SJJvNfAH8ausqIf/9L7O3g+lX+nsJPhiwF jp2zBuc9E6YyJXUoaMoUvLNjQJIipoaTBCmAePrI0eiFgQfo3di/iQCMbmAaw8h7qQek hAzv9GsjWw8oDcqUhFp1+CADkCs9IU5w86Ju+Vg1k7wDBCrXMoz47q3tN4X57tjLMlbR G6fA== X-Gm-Message-State: ALoCoQl0bnxMhuewIhJPBYYbsYxBAmf16Atk7FAmudBDwJo87lfJvBv7B2ibcUUC1o8a2/WuuIoq X-Received: by 10.66.248.8 with SMTP id yi8mr31214226pac.26.1417012389080; Wed, 26 Nov 2014 06:33:09 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.90.38 with SMTP id w35ls2838935qgd.82.gmail; Wed, 26 Nov 2014 06:33:08 -0800 (PST) X-Received: by 10.140.34.21 with SMTP id k21mr45121481qgk.21.1417012388263; Wed, 26 Nov 2014 06:33:08 -0800 (PST) Original-Received: from mail-qg0-f47.google.com (mail-qg0-f47.google.com. [209.85.192.47]) by mx.google.com with ESMTPS id s15si5163264qay.93.2014.11.26.06.33.08 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 26 Nov 2014 06:33:08 -0800 (PST) Received-SPF: pass (google.com: domain of dribeas@gmail.com designates 209.85.192.47 as permitted sender) client-ip=209.85.192.47; Original-Received: by mail-qg0-f47.google.com with SMTP id z60so2109456qgd.34 for ; Wed, 26 Nov 2014 06:33:08 -0800 (PST) X-Received: by 10.229.16.197 with SMTP id p5mr45704505qca.3.1417012387724; Wed, 26 Nov 2014 06:33:07 -0800 (PST) X-Original-Sender: dibeas@ieee.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dribeas@gmail.com designates 209.85.192.47 as permitted sender) smtp.mail=dribeas@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: 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:14749 Archived-At: --001a1133e4cc0345be0508c3e8b8 Content-Type: text/plain; charset=UTF-8 For reference, Facebook's FBVector implementation uses internal knowledge of the jemalloc allocator to adjust the growth factor to be the same of the allocator. The proposal above would allow libraries to make the same type of decisions in a standard way. https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md That being said, I am not sure this is the correct approach. I played with the idea of doing something like this in the past, without requiring a change in the standard by having the allocator return the exact size that was allocated together with the pointer (the simplest hack being the allocator writing the value into the allocated memory and the container using knowledge of the allocator to pull that value out and adjusting the 'capacity' before overwriting the value... but it felt too much like a hack). David On Wed Nov 26 2014 at 7:34:09 AM Antony Polukhin wrote: > Hello, > > Motivation > > Many implementations of `malloc` and `new` internally keep actual size of > an allocated memory block. There are even some vendor extensions that > return size of an allocated memory block (see malloc_size[1] and _msize[2]). > > With that information we could make more effective containers. Let's take > a look at the vector for example: > > * We could get capacity using malloc_size(ptr), so there's no need to > store capacity directly in std::vector. Size of vector is reduced > > * Even if std::vector continues to store capacity, that capacity could be > more accurate if we store capacity from malloc_size(ptr). > > * Calls to insert(), push_back() and other calls become more effective in > some cases: > vector v; > v.reserve(3); // actual capacity could be 4 or even 8 > // ... some code goes here > v.insert(v.end(), {1, 2, 3, 4}); // won't reallocate memory > > > The Solution > > Let's add following optional function to allocators > size_type size(const_pointer ptr) const noexcept; > > We'll need also a trait > template struct is_allocator_has_size; > > Now containers could get all the benefits from 'Motivation' section. > Moreover, vendors without `malloc_size` need nothing to change, > compatibility with old code remains. > > > So, what do you think? > > > [1] > https://developer.apple.com/library/mac/documentation/Darwin/Reference/Manpages/man3/malloc_size.3.html > [2] http://msdn.microsoft.com/en-us/library/z2s077bc%28VS.80%29.aspx > > -- > Best regards, > Antony Polukhin > > -- > > --- > 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 > http://groups.google.com/a/isocpp.org/group/std-proposals/. > -- --- 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 http://groups.google.com/a/isocpp.org/group/std-proposals/. --001a1133e4cc0345be0508c3e8b8 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable For reference, Facebook's FBVector implementation uses internal knowled= ge of the jemalloc allocator to adjust the growth factor to be the same of = the allocator.=C2=A0 The proposal above would allow libraries to make the s= ame type of decisions in a standard way.

https://github.com/fa= cebook/folly/blob/master/folly/docs/FBVector.md

That being said,= I am not sure this is the correct approach. I played with the idea of doin= g something like this in the past, without requiring a change in the standa= rd by having the allocator return the exact size that was allocated togethe= r with the pointer (the simplest hack being the allocator writing the value= into the allocated memory and the container using knowledge of the allocat= or to pull that value out and adjusting the 'capacity' before overw= riting the value... but it felt too much like a hack).

=C2=A0 =C2=A0= David
On Wed Nov 26 2014 at 7:34:09 AM Anton= y Polukhin <antoshkka@gmail.com> wrote:
=
Hello,

Motivation

Many implem= entations of `malloc` and `new` internally keep actual size of an allocated= memory block. There are even some vendor extensions that return size of an= allocated memory block (see malloc_size[1] and _msize[2]).

Wi= th that information we could make more effective containers. Let's take= a look at the vector<int> for example:

* We could get c= apacity using malloc_size(ptr), so there's no need to store capacity di= rectly in std::vector. Size of vector is reduced

* Even if std::vect= or continues to store capacity, that capacity=20 could be more accurate if we store capacity from malloc_size(ptr).

<= /div>* Calls to insert(), push_back() and other calls become more effective= in some cases:
=C2=A0=C2=A0=C2=A0 vector<int> v;
=C2=A0=C2=A0= =C2=A0 v.reserve(3); // actual capacity could be 4 or even 8
=C2= =A0=C2=A0=C2=A0 // ... some code goes here

--

---
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-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/gro= up/std-proposals/.

--

---
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 http://groups.google.com/a/isocpp.org/group/std-proposals/<= /a>.
--001a1133e4cc0345be0508c3e8b8-- .