--089e0102edfe7054c90508c23e36
Content-Type: text/plain; charset=UTF-8

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<int> 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<int> 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 <class T> 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/.

--089e0102edfe7054c90508c23e36
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div><div><div><div><div><div>Hello,<br><br></div>Motivati=
on<br><br></div>Many implementations of `malloc` and `new` internally keep =
actual size of an allocated memory block. There are even some vendor extens=
ions that return size of an allocated memory block (see malloc_size[1] and =
_msize[2]).<br><br></div>With that information we could make more effective=
 containers. Let&#39;s take a look at the vector&lt;int&gt; for example:<br=
><br></div>* We could get capacity using malloc_size(ptr), so there&#39;s n=
o need to store capacity directly in std::vector. Size of vector is reduced=
<br><br>* Even if std::vector continues to store capacity, that capacity=20
could be more accurate if we store capacity from malloc_size(ptr).<br><br><=
/div>* Calls to insert(), push_back() and other calls become more effective=
 in some cases:<br>=C2=A0=C2=A0=C2=A0 vector&lt;int&gt; v;<br>=C2=A0=C2=A0=
=C2=A0 v.reserve(3); // actual capacity could be 4 or even 8<br></div>=C2=
=A0=C2=A0=C2=A0 // ... some code goes here<br><div>=C2=A0=C2=A0=C2=A0 v.ins=
ert(v.end(), {1, 2, 3, 4}); // won&#39;t reallocate memory<br clear=3D"all"=
><div><div><div><div><div><div><div><br><br></div>The Solution<br><br><div>=
Let&#39;s add following optional function to allocators <br>=C2=A0=C2=A0=C2=
=A0 size_type size(const_pointer ptr) const noexcept;<br></div><div><br></d=
iv><div>We&#39;ll need also a trait<br></div><div>=C2=A0=C2=A0=C2=A0 templa=
te &lt;class T&gt; struct is_allocator_has_size;<br></div><div><br></div><d=
iv>Now containers could get all the benefits from &#39;Motivation&#39; sect=
ion. Moreover, vendors without `malloc_size` need nothing to change, compat=
ibility with old code remains.<br></div><div><br><br></div><div>So, what do=
 you think?<br></div><div><br></div><div><br>[1] <a href=3D"https://develop=
er.apple.com/library/mac/documentation/Darwin/Reference/Manpages/man3/mallo=
c_size.3.html">https://developer.apple.com/library/mac/documentation/Darwin=
/Reference/Manpages/man3/malloc_size.3.html</a><br>[2] <a href=3D"http://ms=
dn.microsoft.com/en-us/library/z2s077bc%28VS.80%29.aspx">http://msdn.micros=
oft.com/en-us/library/z2s077bc%28VS.80%29.aspx</a><br><br>-- <br><div class=
=3D"gmail_signature">Best regards,<br>Antony Polukhin</div>
</div></div></div></div></div></div></div></div></div>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--089e0102edfe7054c90508c23e36--

.

--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 <antoshkka@gmail.com>
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<int> 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<int> 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 <class T> 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&#39;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.<br><br><a href=3D"https://github.c=
om/facebook/folly/blob/master/folly/docs/FBVector.md">https://github.com/fa=
cebook/folly/blob/master/folly/docs/FBVector.md</a><br><br>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 &#39;capacity&#39; before overw=
riting the value... but it felt too much like a hack).<br><br>=C2=A0 =C2=A0=
 David<br><div class=3D"gmail_quote">On Wed Nov 26 2014 at 7:34:09 AM Anton=
y Polukhin &lt;<a href=3D"mailto:antoshkka@gmail.com">antoshkka@gmail.com</=
a>&gt; wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><div>=
<div><div><div><div>Hello,<br><br></div>Motivation<br><br></div>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]).<br><br></div>Wi=
th that information we could make more effective containers. Let&#39;s take=
 a look at the vector&lt;int&gt; for example:<br><br></div>* We could get c=
apacity using malloc_size(ptr), so there&#39;s no need to store capacity di=
rectly in std::vector. Size of vector is reduced<br><br>* Even if std::vect=
or continues to store capacity, that capacity=20
could be more accurate if we store capacity from malloc_size(ptr).<br><br><=
/div>* Calls to insert(), push_back() and other calls become more effective=
 in some cases:<br>=C2=A0=C2=A0=C2=A0 vector&lt;int&gt; v;<br>=C2=A0=C2=A0=
=C2=A0 v.reserve(3); // actual capacity could be 4 or even 8<br></div>=C2=
=A0=C2=A0=C2=A0 // ... some code goes here<br><div>=C2=A0=C2=A0=C2=A0 v.ins=
ert(v.end(), {1, 2, 3, 4}); // won&#39;t reallocate memory<br clear=3D"all"=
><div><div><div><div><div><div><div><br><br></div>The Solution<br><br><div>=
Let&#39;s add following optional function to allocators <br>=C2=A0=C2=A0=C2=
=A0 size_type size(const_pointer ptr) const noexcept;<br></div><div><br></d=
iv><div>We&#39;ll need also a trait<br></div><div>=C2=A0=C2=A0=C2=A0 templa=
te &lt;class T&gt; struct is_allocator_has_size;<br></div><div><br></div><d=
iv>Now containers could get all the benefits from &#39;Motivation&#39; sect=
ion. Moreover, vendors without `malloc_size` need nothing to change, compat=
ibility with old code remains.<br></div><div><br><br></div><div>So, what do=
 you think?<br></div><div><br></div><div><br>[1] <a href=3D"https://develop=
er.apple.com/library/mac/documentation/Darwin/Reference/Manpages/man3/mallo=
c_size.3.html" target=3D"_blank">https://developer.apple.com/library/mac/do=
cumentation/Darwin/Reference/Manpages/man3/malloc_size.3.html</a><br>[2] <a=
 href=3D"http://msdn.microsoft.com/en-us/library/z2s077bc%28VS.80%29.aspx" =
target=3D"_blank">http://msdn.microsoft.com/en-us/library/z2s077bc%28VS.80%=
29.aspx</a><br><br>-- <br><div>Best regards,<br>Antony Polukhin</div>
</div></div></div></div></div></div></div></div></div>

<p></p>

-- <br>
<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org" target=3D"_=
blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</blockquote></div>

<p></p>

-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--001a1133e4cc0345be0508c3e8b8--

.