Topic: Configurable Small Object Optimization for vector
Author: Thiago Macieira <thiago@macieira.org>
Date: Tue, 03 Mar 2015 21:19:29 -0800
Raw View
On Tuesday 03 March 2015 20:00:15 Matthew Fioravante wrote:
> Modern implementations are encouraged to implement the small string
> optimization (with implementation defined size) for std::string, reasoning
> that most strings tend to be small. While this may work very well in the
> general case, it can be either inadequate or a pessimization in other cases.
>
> It would be nice if string got an additional size_t template argument:
>
>
> template <typename CharT, typename Traits, typename Allocator, size_t
> SmallSize = /* implementation defiend*/> class basic_string;
Please choose a different name than basic_string.
Since std::foo<N> is a different type from std::foo<M> where N != M, I don't
see the point in attempting to keep compatibility with the current
basic_string. Instead, be explicit that this is a different type and define the
SmallSize default value to be sizeof(std::basic_string<CharT>).
> - Identifiers such a stock tickers which have a fixed upper bound on length.
If the fixed upper bound is small enough, you want to have a non-dynamic
version only. SSO isn't that. You want a real "small string".
--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
--
---
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/.
.
Author: Nevin Liber <nevin@eviloverlord.com>
Date: Wed, 4 Mar 2015 00:01:08 -0600
Raw View
--001a1133d7cad7a5550510702fd8
Content-Type: text/plain; charset=UTF-8
On 3 March 2015 at 22:00, Matthew Fioravante <fmatthew5876@gmail.com> wrote:
> template <typename CharT, typename Traits, typename Allocator, size_t
> SmallSize = /* implementation defiend*/> class basic_string;
>
Adding a template parameter is an ABI breakage, and extremely unlikely to
pass.
For instance, someone had a proposal in Urbana to add a template parameter
to bitset. It went nowhere.
The small object optimization is also very useful for vector.
>
Besides the ABI breakage, this also breaks things like the nothrow swap
guarantee (at least for std::allocator).
--
Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404
--
---
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/.
--001a1133d7cad7a5550510702fd8
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On 3 March 2015 at 22:00, Matthew Fioravante <span dir=3D"=
ltr"><<a href=3D"mailto:fmatthew5876@gmail.com" target=3D"_blank">fmatth=
ew5876@gmail.com</a>></span> wrote:<br><div class=3D"gmail_extra"><div c=
lass=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 =
0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div><=
div style=3D"border:1px solid rgb(187,187,187);word-wrap:break-word;backgro=
und-color:rgb(250,250,250)"><code><div><font color=3D"#660066"><span style=
=3D"color:#008">template</span><span style=3D"color:#000"> </span><span sty=
le=3D"color:#660"><</span><span style=3D"color:#008">typename</span><spa=
n style=3D"color:#000"> </span><span style=3D"color:#606">CharT</span><span=
style=3D"color:#660">,</span><span style=3D"color:#000"> </span><span styl=
e=3D"color:#008">typename</span><span style=3D"color:#000"> </span><span st=
yle=3D"color:#606">Traits</span><span style=3D"color:#660">,</span><span st=
yle=3D"color:#000"> </span><span style=3D"color:#008">typename</span><span =
style=3D"color:#000"> </span><span style=3D"color:#606">Allocator</span><sp=
an style=3D"color:#660">,</span><span style=3D"color:#000"> size_t </span><=
span style=3D"color:#606">SmallSize</span><span style=3D"color:#000"> </spa=
n><span style=3D"color:#660">=3D</span><span style=3D"color:#000"> </span><=
span style=3D"color:#800">/* implementation defiend*/</span><span style=3D"=
color:#660">></span><span style=3D"color:#000"> </span><span style=3D"co=
lor:#008">class</span><span style=3D"color:#000"> basic_string</span><span =
style=3D"color:#660">;</span></font></div></code></div></div></div></blockq=
uote><div><br></div><div>Adding a template parameter is an ABI breakage, an=
d extremely unlikely to pass.</div><div><br></div><div>For instance, someon=
e had a proposal in Urbana to add a template parameter to bitset.=C2=A0 It =
went nowhere.</div><div><br></div><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=
=3D"ltr"><div>The small object optimization is also very useful for vector.=
<br></div></div></blockquote><div><br></div><div>Besides the ABI breakage, =
this also breaks things like the nothrow swap guarantee (at least for std::=
allocator).</div><div>=C2=A0--=C2=A0</div></div><div class=3D"gmail_signatu=
re">=C2=A0Nevin ":-)" Liber=C2=A0 <mailto:<a href=3D"mailto:ne=
vin@eviloverlord.com" target=3D"_blank">nevin@eviloverlord.com</a>>=C2=
=A0 (847) 691-1404</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" 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 />
--001a1133d7cad7a5550510702fd8--
.
Author: Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
Date: Tue, 3 Mar 2015 23:42:49 -0800 (PST)
Raw View
------=_Part_1382_269737184.1425454969659
Content-Type: multipart/alternative;
boundary="----=_Part_1383_134872671.1425454969659"
------=_Part_1383_134872671.1425454969659
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Tuesday, March 3, 2015 at 9:19:36 PM UTC-8, Thiago Macieira wrote:
>
> On Tuesday 03 March 2015 20:00:15 Matthew Fioravante wrote:=20
> > Modern implementations are encouraged to implement the small string=20
> > optimization (with implementation defined size) for std::string,=20
> reasoning=20
> > that most strings tend to be small. While this may work very well in th=
e=20
> > general case, it can be either inadequate or a pessimization in other=
=20
> cases.=20
>
[...]=20
> Since std::foo<N> is a different type from std::foo<M> where N !=3D M, I=
=20
> don't=20
> see the point in attempting to keep compatibility with the current=20
> basic_string. Instead, be explicit that this is a different type and=20
> define the=20
> SmallSize default value to be sizeof(std::basic_string<CharT>).=20
>
In my opinion, "small_vector" would be a great addition to the standard=20
library, but *only* if small_vector<T,N>& and vector<T>& are=20
inter-convertible (in constant time). I believe that's doable, although I'm=
=20
not sure how to write the *implementation* in purely standard-conforming=20
C++ =E2=80=94 it might require some reinterpret_casts.
The use-case would be things like
struct ChessPosition {
std::small_vector<ChessPiece,32> pieces;=20
};
where ChessPosition's copy constructor and destructor get called *very*=20
often, so copying the members needs to be *very* fast. Inlining the data=20
(so no heap allocation needs to happen) is a big win.
But then do we just want ChessPiece pieces[32]? No, because (for the=20
programmer's sanity) we need to track pieces.size() (which won't always be=
=20
32; usually it will be much less) separately from the fixed number 32.
But if we know a maximum size for the vector (32 items), do we really want=
=20
a kind of bounded_vector<ChessPiece,32> which would behave basically like a=
=20
std::array plus a size member? Well, that would definitely be useful in=20
some cases, and I do wish there were a standard implementation of such a=20
thing. But in the case of ChessPosition, we actually don't want that,=20
because as noted above, pieces.size() will usually be much less than 32.=20
We'd like to be able to tune the N parameter =E2=80=94 for example, if we u=
se=20
small_vector<ChessPiece,16>, then early-game positions with more than 16=20
pieces will require a heap allocation (relatively slower), but *every*=20
position will take half the RAM (shrinking our memory footprint and the=20
expense of copy-constructing these things).
Some of these use-cases might be solved other ways. For example,=20
bounded_vector could be described as "a vector_view onto an array."
my $.02,
=E2=80=93Arthur
--=20
---=20
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 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/group/std-proposa=
ls/.
------=_Part_1383_134872671.1425454969659
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Tuesday, March 3, 2015 at 9:19:36 PM UTC-8, Thiago Maci=
eira wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left=
: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On Tuesday 03 March=
2015 20:00:15 Matthew Fioravante wrote:
<br>> Modern implementations are encouraged to implement the small strin=
g
<br>> optimization (with implementation defined size) for std::string, r=
easoning
<br>> that most strings tend to be small. While this may work very well =
in the
<br>> general case, it can be either inadequate or a pessimization in ot=
her cases.
<br></blockquote><div>[...] </div><blockquote class=3D"gmail_quote" st=
yle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-lef=
t: 1ex;">Since std::foo<N> is a different type from std::foo<M>=
where N !=3D M, I don't=20
<br>see the point in attempting to keep compatibility with the current=20
<br>basic_string. Instead, be explicit that this is a different type and de=
fine the=20
<br>SmallSize default value to be sizeof(std::basic_string<<wbr>CharT>=
;).
<br></blockquote><div><br></div><div>In my opinion, "small_vector" would be=
a great addition to the standard library, but <i>only</i> if <font face=3D=
"courier new, monospace">small_vector<T,N>&</font> and <font face=
=3D"courier new, monospace">vector<T>&</font> are inter-convertib=
le (in constant time). I believe that's doable, although I'm not sure how t=
o write the <i>implementation</i> in purely standard-conforming C++ =E2=80=
=94 it might require some reinterpret_casts.</div><div><br></div><div>The u=
se-case would be things like</div><div><br></div><div class=3D"prettyprint"=
style=3D"background-color: rgb(250, 250, 250); border: 1px solid rgb(187, =
187, 187); word-wrap: break-word;"><code class=3D"prettyprint"><div class=
=3D"subprettyprint"><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">struct</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> =
</span><span style=3D"color: #606;" class=3D"styled-by-prettify">ChessPosit=
ion</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span=
><span style=3D"color: #660;" class=3D"styled-by-prettify">{</span><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify"><br> std</sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span=
style=3D"color: #000;" class=3D"styled-by-prettify">small_vector</span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify"><</span><span sty=
le=3D"color: #606;" class=3D"styled-by-prettify">ChessPiece</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"col=
or: #066;" class=3D"styled-by-prettify">32</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">></span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> pieces</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> <br></span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">};</span></div></code></div><div><br></div><div>where <font face=
=3D"courier new, monospace">ChessPosition</font>'s copy constructor and des=
tructor get called <i>very</i> often, so copying the members needs to be <i=
>very</i> fast. Inlining the data (so no heap allocation needs to happen) i=
s a big win.</div><div><br></div><div>But then do we just want <font face=
=3D"courier new, monospace">ChessPiece pieces[32]</font>? No, because (for =
the programmer's sanity) we need to track <font face=3D"courier new, monosp=
ace">pieces.size()</font> (which won't always be 32; usually it will b=
e much less) separately from the fixed number <font face=3D"courier new, mo=
nospace">32</font>.</div><div><br></div><div>But if we know a maximum size =
for the vector (32 items), do we really want a kind of <font face=3D"courie=
r new, monospace">bounded_vector<ChessPiece,32></font> which would be=
have basically like a <font face=3D"courier new, monospace">std::array</fon=
t> plus a size member? Well, that would definitely be useful in some cases,=
and I do wish there were a standard implementation of such a thing. But in=
the case of ChessPosition, we actually don't want that, because as noted a=
bove, <font face=3D"courier new, monospace">pieces.size()</font> will usual=
ly be much less than 32. We'd like to be able to tune the <font face=3D"cou=
rier new, monospace">N</font> parameter =E2=80=94 for example, if we use <f=
ont face=3D"courier new, monospace">small_vector<ChessPiece,16></font=
>, then early-game positions with more than 16 pieces will require a heap a=
llocation (relatively slower), but <i>every</i> position will take half the=
RAM (shrinking our memory footprint and the expense of copy-constructing t=
hese things).</div><div><br></div><div>Some of these use-cases might be sol=
ved other ways. For example, <font face=3D"courier new, monospace">bounded_=
vector</font> could be described as "a <font face=3D"courier new, monospace=
">vector_view</font> onto an array."</div><div><br></div><div>my $.02,</div=
><div>=E2=80=93Arthur</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" 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 />
------=_Part_1383_134872671.1425454969659--
------=_Part_1382_269737184.1425454969659--
.
Author: Thiago Macieira <thiago@macieira.org>
Date: Tue, 03 Mar 2015 23:58:37 -0800
Raw View
On Tuesday 03 March 2015 23:42:49 Arthur O'Dwyer wrote:
> In my opinion, "small_vector" would be a great addition to the standard
> library, but *only* if small_vector<T,N>& and vector<T>& are
> inter-convertible (in constant time). I believe that's doable, although I=
'm
> not sure how to write the *implementation* in purely standard-conforming
> C++ =E2=80=94 it might require some reinterpret_casts.
You can't create a copy in constant time, unless you're using reference=20
counting. You could move in constant time, provided that you could transfer=
=20
ownership of the data, but not in this case. The whole objective of the "sm=
all=20
vector" is that it has excslusive space for N elements, so if you moved fro=
m=20
one small_vector<T, N> to anything else, it needs to do a full copy in line=
ar=20
time.
> The use-case would be things like
>=20
> struct ChessPosition {
> std::small_vector<ChessPiece,32> pieces;
> };
>=20
> where ChessPosition's copy constructor and destructor get called *very*
> often, so copying the members needs to be *very* fast. Inlining the data
> (so no heap allocation needs to happen) is a big win.
True, but this is still O(n).
> But if we know a maximum size for the vector (32 items), do we really wan=
t
> a kind of bounded_vector<ChessPiece,32> which would behave basically like=
a
> std::array plus a size member? Well, that would definitely be useful in
> some cases, and I do wish there were a standard implementation of such a
> thing. But in the case of ChessPosition, we actually don't want that,
> because as noted above, pieces.size() will usually be much less than 32.
> We'd like to be able to tune the N parameter =E2=80=94 for example, if we=
use
> small_vector<ChessPiece,16>, then early-game positions with more than 16
> pieces will require a heap allocation (relatively slower), but *every*
> position will take half the RAM (shrinking our memory footprint and the
> expense of copy-constructing these things).
>=20
> Some of these use-cases might be solved other ways. For example,
> bounded_vector could be described as "a vector_view onto an array."
Makes a lot of sense.
--=20
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358
--=20
---=20
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 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/group/std-proposa=
ls/.
.
Author: =?UTF-8?Q?David_Rodr=C3=ADguez_Ibeas?= <dibeas@ieee.org>
Date: Wed, 4 Mar 2015 10:31:01 -0500
Raw View
--047d7ba97c2a7f744705107823f2
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
I think that your problem is/should be addressed in a different direction,
having an array_view/vector_view (I have heard about those in the past, I
don't know if there has been any actual proposal, but it would be a
simplified string_view). The 'ChessPosition' class looks like it should be
an 'std::array', and if interfaces that only act on the data are
implemented in terms of a *_view, then it should work just fine.
In current C++, and if you need a dynamic size (i.e. std::array does not
solve your problem), you can use an allocator to control where the memory
comes from and make it local, you would still be paying for the additional
bookkeeping inside vector, but if you need it to actually work that is
available today...
David
On Wed, Mar 4, 2015 at 2:42 AM, Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
wrote:
> On Tuesday, March 3, 2015 at 9:19:36 PM UTC-8, Thiago Macieira wrote:
>>
>> On Tuesday 03 March 2015 20:00:15 Matthew Fioravante wrote:
>> > Modern implementations are encouraged to implement the small string
>> > optimization (with implementation defined size) for std::string,
>> reasoning
>> > that most strings tend to be small. While this may work very well in
>> the
>> > general case, it can be either inadequate or a pessimization in other
>> cases.
>>
> [...]
>
>> Since std::foo<N> is a different type from std::foo<M> where N !=3D M, I
>> don't
>> see the point in attempting to keep compatibility with the current
>> basic_string. Instead, be explicit that this is a different type and
>> define the
>> SmallSize default value to be sizeof(std::basic_string<CharT>).
>>
>
> In my opinion, "small_vector" would be a great addition to the standard
> library, but *only* if small_vector<T,N>& and vector<T>& are
> inter-convertible (in constant time). I believe that's doable, although I=
'm
> not sure how to write the *implementation* in purely standard-conforming
> C++ =E2=80=94 it might require some reinterpret_casts.
>
> The use-case would be things like
>
> struct ChessPosition {
> std::small_vector<ChessPiece,32> pieces;
> };
>
> where ChessPosition's copy constructor and destructor get called *very*
> often, so copying the members needs to be *very* fast. Inlining the data
> (so no heap allocation needs to happen) is a big win.
>
> But then do we just want ChessPiece pieces[32]? No, because (for the
> programmer's sanity) we need to track pieces.size() (which won't always
> be 32; usually it will be much less) separately from the fixed number 32.
>
> But if we know a maximum size for the vector (32 items), do we really wan=
t
> a kind of bounded_vector<ChessPiece,32> which would behave basically like
> a std::array plus a size member? Well, that would definitely be useful in
> some cases, and I do wish there were a standard implementation of such a
> thing. But in the case of ChessPosition, we actually don't want that,
> because as noted above, pieces.size() will usually be much less than 32.
> We'd like to be able to tune the N parameter =E2=80=94 for example, if we=
use
> small_vector<ChessPiece,16>, then early-game positions with more than 16
> pieces will require a heap allocation (relatively slower), but *every*
> position will take half the RAM (shrinking our memory footprint and the
> expense of copy-constructing these things).
>
> Some of these use-cases might be solved other ways. For example,
> bounded_vector could be described as "a vector_view onto an array."
>
> my $.02,
> =E2=80=93Arthur
>
> --
>
> ---
> 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/.
>
--=20
---=20
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 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/group/std-proposa=
ls/.
--047d7ba97c2a7f744705107823f2
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">I think that your problem is/should be addressed in a diff=
erent direction, having an array_view/vector_view (I have heard about those=
in the past, I don't know if there has been any actual proposal, but i=
t would be a simplified string_view).=C2=A0 The 'ChessPosition' cla=
ss looks like it should be an 'std::array', and if interfaces that =
only act on the data are implemented in terms of a *_view, then it should w=
ork just fine.<br><br>In current C++, and if you need a dynamic size (i.e. =
std::array does not solve your problem), you can use an allocator to contro=
l where the memory comes from and make it local, you would still be paying =
for the additional bookkeeping inside vector, but if you need it to actuall=
y work that is available today... <br><div><br></div><div>=C2=A0 =C2=A0 Dav=
id</div></div><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">On =
Wed, Mar 4, 2015 at 2:42 AM, Arthur O'Dwyer <span dir=3D"ltr"><<a hr=
ef=3D"mailto:arthur.j.odwyer@gmail.com" target=3D"_blank">arthur.j.odwyer@g=
mail.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote" style=
=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=
=3D"ltr"><span class=3D"">On Tuesday, March 3, 2015 at 9:19:36 PM UTC-8, Th=
iago Macieira wrote:<blockquote class=3D"gmail_quote" style=3D"margin:0;mar=
gin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex">On Tuesday 03 M=
arch 2015 20:00:15 Matthew Fioravante wrote:
<br>> Modern implementations are encouraged to implement the small strin=
g
<br>> optimization (with implementation defined size) for std::string, r=
easoning
<br>> that most strings tend to be small. While this may work very well =
in the
<br>> general case, it can be either inadequate or a pessimization in ot=
her cases.
<br></blockquote></span><div>[...]=C2=A0</div><span class=3D""><blockquote =
class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #=
ccc solid;padding-left:1ex">Since std::foo<N> is a different type fro=
m std::foo<M> where N !=3D M, I don't=20
<br>see the point in attempting to keep compatibility with the current=20
<br>basic_string. Instead, be explicit that this is a different type and de=
fine the=20
<br>SmallSize default value to be sizeof(std::basic_string<<u></u>CharT&=
gt;).
<br></blockquote><div><br></div></span><div>In my opinion, "small_vect=
or" would be a great addition to the standard library, but <i>only</i>=
if <font face=3D"courier new, monospace">small_vector<T,N>&</fon=
t> and <font face=3D"courier new, monospace">vector<T>&</font> ar=
e inter-convertible (in constant time). I believe that's doable, althou=
gh I'm not sure how to write the <i>implementation</i> in purely standa=
rd-conforming C++ =E2=80=94 it might require some reinterpret_casts.</div><=
div><br></div><div>The use-case would be things like</div><div><br></div><d=
iv style=3D"background-color:rgb(250,250,250);border:1px solid rgb(187,187,=
187);word-wrap:break-word"><code><div><span style=3D"color:#008">struct</sp=
an><span style=3D"color:#000"> </span><span style=3D"color:#606">ChessPosit=
ion</span><span style=3D"color:#000"> </span><span style=3D"color:#660">{</=
span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 std</span><span style=3D"=
color:#660">::</span><span style=3D"color:#000">small_vector</span><span st=
yle=3D"color:#660"><</span><span style=3D"color:#606">ChessPiece</span><=
span style=3D"color:#660">,</span><span style=3D"color:#066">32</span><span=
style=3D"color:#660">></span><span style=3D"color:#000"> pieces</span><=
span style=3D"color:#660">;</span><span style=3D"color:#000"> <br></span><s=
pan style=3D"color:#660">};</span></div></code></div><div><br></div><div>wh=
ere <font face=3D"courier new, monospace">ChessPosition</font>'s copy c=
onstructor and destructor get called <i>very</i> often, so copying the memb=
ers needs to be <i>very</i> fast. Inlining the data (so no heap allocation =
needs to happen) is a big win.</div><div><br></div><div>But then do we just=
want <font face=3D"courier new, monospace">ChessPiece pieces[32]</font>? N=
o, because (for the programmer's sanity) we need to track <font face=3D=
"courier new, monospace">pieces.size()</font>=C2=A0(which won't always =
be 32; usually it will be much less) separately from the fixed number <font=
face=3D"courier new, monospace">32</font>.</div><div><br></div><div>But if=
we know a maximum size for the vector (32 items), do we really want a kind=
of <font face=3D"courier new, monospace">bounded_vector<ChessPiece,32&g=
t;</font> which would behave basically like a <font face=3D"courier new, mo=
nospace">std::array</font> plus a size member? Well, that would definitely =
be useful in some cases, and I do wish there were a standard implementation=
of such a thing. But in the case of ChessPosition, we actually don't w=
ant that, because as noted above, <font face=3D"courier new, monospace">pie=
ces.size()</font> will usually be much less than 32. We'd like to be ab=
le to tune the <font face=3D"courier new, monospace">N</font> parameter =E2=
=80=94 for example, if we use <font face=3D"courier new, monospace">small_v=
ector<ChessPiece,16></font>, then early-game positions with more than=
16 pieces will require a heap allocation (relatively slower), but <i>every=
</i> position will take half the RAM (shrinking our memory footprint and th=
e expense of copy-constructing these things).</div><div><br></div><div>Some=
of these use-cases might be solved other ways. For example, <font face=3D"=
courier new, monospace">bounded_vector</font> could be described as "a=
<font face=3D"courier new, monospace">vector_view</font> onto an array.&qu=
ot;</div><div><br></div><div>my $.02,</div><div>=E2=80=93Arthur</div></div>=
<div class=3D"HOEnZb"><div class=3D"h5">
<p></p>
-- <br>
<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" 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>
</div></div></blockquote></div><br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" 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 />
--047d7ba97c2a7f744705107823f2--
.
Author: "dgutson ." <danielgutson@gmail.com>
Date: Wed, 4 Mar 2015 12:39:15 -0300
Raw View
--001a11421f2efa4c1405107840bd
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
El 04/03/2015 12:31, "David Rodr=C3=ADguez Ibeas" <dibeas@ieee.org> escribi=
=C3=B3:
>
> I think that your problem is/should be addressed in a different
direction, having an array_view/vector_view (I have heard about those in
the past, I don't know if there has been any actual proposal, but it would
be a simplified string_view). The 'ChessPosition' class looks like it
should be an 'std::array', and if interfaces that only act on the data are
implemented in terms of a *_view, then it should work just fine.
>
> In current C++, and if you need a dynamic size (i.e. std::array does not
solve your problem), you can use an allocator to control where the memory
comes from and make it local, you would still be paying for the additional
bookkeeping inside vector, but if you need it to actually work that is
available today...
I had the same thought. Why an allocator having an initial pre-allocated
buffer of user-specified length and then use basic_string with that
allocator wouldn't be an equivalent currently conformant solution?
>
> David
>
> On Wed, Mar 4, 2015 at 2:42 AM, Arthur O'Dwyer <arthur.j.odwyer@gmail.com=
>
wrote:
>>
>> On Tuesday, March 3, 2015 at 9:19:36 PM UTC-8, Thiago Macieira wrote:
>>>
>>> On Tuesday 03 March 2015 20:00:15 Matthew Fioravante wrote:
>>> > Modern implementations are encouraged to implement the small string
>>> > optimization (with implementation defined size) for std::string,
reasoning
>>> > that most strings tend to be small. While this may work very well in
the
>>> > general case, it can be either inadequate or a pessimization in other
cases.
>>
>> [...]
>>>
>>> Since std::foo<N> is a different type from std::foo<M> where N !=3D M, =
I
don't
>>> see the point in attempting to keep compatibility with the current
>>> basic_string. Instead, be explicit that this is a different type and
define the
>>> SmallSize default value to be sizeof(std::basic_string<CharT>).
>>
>>
>> In my opinion, "small_vector" would be a great addition to the standard
library, but only if small_vector<T,N>& and vector<T>& are
inter-convertible (in constant time). I believe that's doable, although I'm
not sure how to write the implementation in purely standard-conforming C++
=E2=80=94 it might require some reinterpret_casts.
>>
>> The use-case would be things like
>>
>> struct ChessPosition {
>> std::small_vector<ChessPiece,32> pieces;
>> };
>>
>> where ChessPosition's copy constructor and destructor get called very
often, so copying the members needs to be very fast. Inlining the data (so
no heap allocation needs to happen) is a big win.
>>
>> But then do we just want ChessPiece pieces[32]? No, because (for the
programmer's sanity) we need to track pieces.size() (which won't always be
32; usually it will be much less) separately from the fixed number 32.
>>
>> But if we know a maximum size for the vector (32 items), do we really
want a kind of bounded_vector<ChessPiece,32> which would behave basically
like a std::array plus a size member? Well, that would definitely be useful
in some cases, and I do wish there were a standard implementation of such a
thing. But in the case of ChessPosition, we actually don't want that,
because as noted above, pieces.size() will usually be much less than 32.
We'd like to be able to tune the N parameter =E2=80=94 for example, if we u=
se
small_vector<ChessPiece,16>, then early-game positions with more than 16
pieces will require a heap allocation (relatively slower), but every
position will take half the RAM (shrinking our memory footprint and the
expense of copy-constructing these things).
>>
>> Some of these use-cases might be solved other ways. For example,
bounded_vector could be described as "a vector_view onto an array."
>>
>> my $.02,
>> =E2=80=93Arthur
>>
>> --
>>
>> ---
>> 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/.
--=20
---=20
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 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/group/std-proposa=
ls/.
--001a11421f2efa4c1405107840bd
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<p dir=3D"ltr"><br>
El 04/03/2015 12:31, "David Rodr=C3=ADguez Ibeas" <<a href=3D"=
mailto:dibeas@ieee.org">dibeas@ieee.org</a>> escribi=C3=B3:<br>
><br>
> I think that your problem is/should be addressed in a different direct=
ion, having an array_view/vector_view (I have heard about those in the past=
, I don't know if there has been any actual proposal, but it would be a=
simplified string_view).=C2=A0 The 'ChessPosition' class looks lik=
e it should be an 'std::array', and if interfaces that only act on =
the data are implemented in terms of a *_view, then it should work just fin=
e.<br>
><br>
> In current C++, and if you need a dynamic size (i.e. std::array does n=
ot solve your problem), you can use an allocator to control where the memor=
y comes from and make it local, you would still be paying for the additiona=
l bookkeeping inside vector, but if you need it to actually work that is av=
ailable today... </p>
<p dir=3D"ltr">I had the same thought. Why an allocator having an initial p=
re-allocated buffer of user-specified length and then use basic_string with=
that allocator wouldn't be an equivalent currently conformant solution=
?</p>
<p dir=3D"ltr">><br>
> =C2=A0 =C2=A0 David<br>
><br>
> On Wed, Mar 4, 2015 at 2:42 AM, Arthur O'Dwyer <<a href=3D"mail=
to:arthur.j.odwyer@gmail.com">arthur.j.odwyer@gmail.com</a>> wrote:<br>
>><br>
>> On Tuesday, March 3, 2015 at 9:19:36 PM UTC-8, Thiago Macieira wro=
te:<br>
>>><br>
>>> On Tuesday 03 March 2015 20:00:15 Matthew Fioravante wrote: <b=
r>
>>> > Modern implementations are encouraged to implement the sm=
all string <br>
>>> > optimization (with implementation defined size) for std::=
string, reasoning <br>
>>> > that most strings tend to be small. While this may work v=
ery well in the <br>
>>> > general case, it can be either inadequate or a pessimizat=
ion in other cases. <br>
>><br>
>> [...]=C2=A0<br>
>>><br>
>>> Since std::foo<N> is a different type from std::foo<M=
> where N !=3D M, I don't <br>
>>> see the point in attempting to keep compatibility with the cur=
rent <br>
>>> basic_string. Instead, be explicit that this is a different ty=
pe and define the <br>
>>> SmallSize default value to be sizeof(std::basic_string<Char=
T>). <br>
>><br>
>><br>
>> In my opinion, "small_vector" would be a great addition =
to the standard library, but only if small_vector<T,N>& and vecto=
r<T>& are inter-convertible (in constant time). I believe that=
9;s doable, although I'm not sure how to write the implementation in pu=
rely standard-conforming C++ =E2=80=94 it might require some reinterpret_ca=
sts.<br>
>><br>
>> The use-case would be things like<br>
>><br>
>> struct ChessPosition {<br>
>> =C2=A0 =C2=A0 std::small_vector<ChessPiece,32> pieces; <br>
>> };<br>
>><br>
>> where ChessPosition's copy constructor and destructor get call=
ed very often, so copying the members needs to be very fast. Inlining the d=
ata (so no heap allocation needs to happen) is a big win.<br>
>><br>
>> But then do we just want ChessPiece pieces[32]? No, because (for t=
he programmer's sanity) we need to track pieces.size()=C2=A0(which won&=
#39;t always be 32; usually it will be much less) separately from the fixed=
number 32.<br>
>><br>
>> But if we know a maximum size for the vector (32 items), do we rea=
lly want a kind of bounded_vector<ChessPiece,32> which would behave b=
asically like a std::array plus a size member? Well, that would definitely =
be useful in some cases, and I do wish there were a standard implementation=
of such a thing. But in the case of ChessPosition, we actually don't w=
ant that, because as noted above, pieces.size() will usually be much less t=
han 32. We'd like to be able to tune the N parameter =E2=80=94 for exam=
ple, if we use small_vector<ChessPiece,16>, then early-game positions=
with more than 16 pieces will require a heap allocation (relatively slower=
), but every position will take half the RAM (shrinking our memory footprin=
t and the expense of copy-constructing these things).<br>
>><br>
>> Some of these use-cases might be solved other ways. For example, b=
ounded_vector could be described as "a vector_view onto an array."=
;<br>
>><br>
>> my $.02,<br>
>> =E2=80=93Arthur<br>
>><br>
>> -- <br>
>><br>
>> --- <br>
>> You received this message because you are subscribed to the Google=
Groups "ISO C++ Standard - Future Proposals" group.<br>
>> To unsubscribe from this group and stop receiving emails from it, =
send an email to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org">=
std-proposals+unsubscribe@isocpp.org</a>.<br>
>> To post to this group, send email to <a href=3D"mailto:std-proposa=
ls@isocpp.org">std-proposals@isocpp.org</a>.<br>
>> Visit this group at <a href=3D"http://groups.google.com/a/isocpp.o=
rg/group/std-proposals/">http://groups.google.com/a/isocpp.org/group/std-pr=
oposals/</a>.<br>
><br>
><br>
> -- <br>
><br>
> --- <br>
> You received this message because you are subscribed to the Google Gro=
ups "ISO C++ Standard - Future Proposals" group.<br>
> To unsubscribe from this group and stop receiving emails from it, send=
an email to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org">std-=
proposals+unsubscribe@isocpp.org</a>.<br>
> To post to this group, send email to <a href=3D"mailto:std-proposals@i=
socpp.org">std-proposals@isocpp.org</a>.<br>
> Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/g=
roup/std-proposals/">http://groups.google.com/a/isocpp.org/group/std-propos=
als/</a>.<br>
</p>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" 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 />
--001a11421f2efa4c1405107840bd--
.
Author: Matthew Fioravante <fmatthew5876@gmail.com>
Date: Wed, 4 Mar 2015 09:38:37 -0800 (PST)
Raw View
------=_Part_5944_902185831.1425490717073
Content-Type: multipart/alternative;
boundary="----=_Part_5945_1802713797.1425490717073"
------=_Part_5945_1802713797.1425490717073
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Wednesday, March 4, 2015 at 12:19:36 AM UTC-5, Thiago Macieira wrote:
>
> > - Identifiers such a stock tickers which have a fixed upper bound on=20
> length.=20
>
> If the fixed upper bound is small enough, you want to have a non-dynamic=
=20
> version only. SSO isn't that. You want a real "small string".=20
>
I agree and this class would be great to have. Good luck getting such a=20
beast approved by the standards committee though.
On Wednesday, March 4, 2015 at 10:31:03 AM UTC-5, David Rodr=C3=ADguez Ibea=
s=20
wrote:
>
> I think that your problem is/should be addressed in a different direction=
,=20
> having an array_view/vector_view (I have heard about those in the past, I=
=20
> don't know if there has been any actual proposal, but it would be a=20
> simplified string_view). The 'ChessPosition' class looks like it should =
be=20
> an 'std::array', and if interfaces that only act on the data are=20
> implemented in terms of a *_view, then it should work just fine.
>
Instead of using an external view object, I would suggest an adapter which=
=20
contains the actual array and adds runtime size / compile time capacity=20
semantics ontop of it.
The external view approach has a few problems. One is that you have 2=20
separate objects maintaining state invariants over a single collection of=
=20
data. Anyone with access to the underlying std::array can easily violate=20
your invariants. Also if you want to pass the aggregate data structure=20
around, you have to pass 2 things instead of one which is a great idiom to=
=20
use if you want to write bugs. Finally its also less efficient,=20
particularly if you are storing the array and the view as data members of a=
=20
class. The view will contain a redundant pointer to the array. Not only=20
does this pointer waste valuable cache line bytes, its also an "internal=20
pointer", that is a data member pointer which points to another data member=
=20
of the class. The idiom of using internal pointers is often frowned upon=20
because it prevents your type from be memcpyable.
On Wednesday, March 4, 2015 at 10:39:18 AM UTC-5, dgutson wrote:
>
> I had the same thought. Why an allocator having an initial pre-allocated=
=20
> buffer of user-specified length and then use basic_string with that=20
> allocator wouldn't be an equivalent currently conformant solution?
>
You can optimize further by putting the SSO feature directly in the class.=
=20
For example the SSO buffer and the capacity can share space using a union=
=20
since whenever the SSO buffer is used, we implicitly know the capacity and=
=20
don't need to store it. If you're storing a vector<small_vector<T,N>>, the=
=20
space savings can add up.
Even if using an allocator is the chosen solution, a standard allocator to=
=20
do this along with a small_vector / small_string template alias would be=20
helpful.=20
--=20
---=20
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 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/group/std-proposa=
ls/.
------=_Part_5945_1802713797.1425490717073
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br>On Wednesday, March 4, 2015 at 12:19:36 AM UTC-5, =
Thiago Macieira wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;=
margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">> - I=
dentifiers such a stock tickers which have a fixed upper bound on length.
<br>
<br>If the fixed upper bound is small enough, you want to have a non-dynami=
c=20
<br>version only. SSO isn't that. You want a real "small string".
<br></blockquote><div><br>I agree and this class would be great to have. Go=
od luck getting such a beast approved by the standards committee though.<br=
></div><br>On Wednesday, March 4, 2015 at 10:31:03 AM UTC-5, David Rodr=C3=
=ADguez Ibeas wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;ma=
rgin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr">I
think that your problem is/should be addressed in a different=20
direction, having an array_view/vector_view (I have heard about those in
the past, I don't know if there has been any actual proposal, but it=20
would be a simplified string_view). The 'ChessPosition' class looks=
=20
like it should be an 'std::array', and if interfaces that only act on=20
the data are implemented in terms of a *_view, then it should work just=20
fine.<br></div></blockquote><div><br>Instead of using an external view obje=
ct, I would suggest an adapter which contains the actual array and adds run=
time size / compile time capacity semantics ontop of it.<br><br>The externa=
l view approach has a few problems. One is that you have 2 separate objects=
maintaining state invariants over a single collection of data. Anyone with=
access to the underlying std::array can easily violate your invariants. Al=
so if you want to pass the aggregate data structure around, you have to pas=
s 2 things instead of one which is a great idiom to use if you want to writ=
e bugs. Finally its also less efficient, particularly if you are storing th=
e array and the view as data members of a class. The view will contain a re=
dundant pointer to the array. Not only does this pointer waste valuable cac=
he line bytes, its also an "internal pointer", that is a data member pointe=
r which points to another data member of the class. The idiom of using inte=
rnal pointers is often frowned upon because it prevents your type from be m=
emcpyable.<br><br></div>On Wednesday, March 4, 2015 at 10:39:18 AM UTC-5, d=
gutson wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-le=
ft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">
<p dir=3D"ltr">I had the same thought. Why an allocator having an initial p=
re-allocated buffer of user-specified length and then use basic_string with=
that allocator wouldn't be an equivalent currently conformant solution?</p=
></blockquote><div>You can optimize further by putting the SSO feature dire=
ctly in the class. For example the SSO buffer and the capacity can share sp=
ace using a union since whenever the SSO buffer is used, we implicitly know=
the capacity and don't need to store it. If you're storing a vector<sma=
ll_vector<T,N>>, the space savings can add up.<br><br>Even if usin=
g an allocator is the chosen solution, a standard allocator to do this alon=
g with a small_vector / small_string template alias would be helpful. <br><=
/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" 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 />
------=_Part_5945_1802713797.1425490717073--
------=_Part_5944_902185831.1425490717073--
.
Author: "Arthur O'Dwyer" <arthur.j.odwyer@gmail.com>
Date: Wed, 4 Mar 2015 11:04:06 -0800
Raw View
--14dae9cc988e8b289605107b1d95
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Tue, Mar 3, 2015 at 11:58 PM, Thiago Macieira <thiago@macieira.org>
wrote:
> On Tuesday 03 March 2015 23:42:49 Arthur O'Dwyer wrote:
> > In my opinion, "small_vector" would be a great addition to the standard
> > library, but *only* if small_vector<T,N>& and vector<T>& are
> > inter-convertible (in constant time). I believe that's doable, although
> I'm
> > not sure how to write the *implementation* in purely standard-conformin=
g
> > C++ =E2=80=94 it might require some reinterpret_casts.
>
> You can't create a copy in constant time
I didn't say you should be able to create copies in constant time; I said
that small_vector<T,N>& should be convertible to vector<T>& and vice versa.
void generic_func(const std::vector<ChessPiece>& pieces) { ... }
std::small_vector<ChessPiece, 16> mypieces;
generic_func(mypieces);
std::small_vector<ChessPiece, 18> hispieces;
generic_func(hispieces);
There's no (semantic) reason this code shouldn't work, since vector and
small_vector have exactly the same API. We shouldn't need to make
generic_func a template just to get this to work, and we should even be
able to do it without virtuals.
- All vectors and small_vectors have size and capacity members; we just
need to make sure they're at the same offsets.
- We might need a boolean flag to indicate whether the data is on the heap
or inline; this is the part I'm unsure of.
- Since we know the size and capacity of the vector, we can even push_back,
up to a point...
- ...and if we need to reallocate the data, then we have to be conservative
and put it on the heap.
Matthew Fioravante wrote:
> For example the SSO buffer and the capacity can share space using a union
since whenever
> the SSO buffer is used, we implicitly know the capacity and don't need to
store it
I agree that this would be a useful goal, but I'm pretty sure it conflicts
with my own pet goal to make std::small_vector<T,M>& interconvertible with
std::small_vector<T,N>&, so you get to pick one or the other but not both.
In my current design (which is not fully implemented) every kind of
small_vector needs to know its "real" capacity; it can't trust its template
parameter to reflect reality.
Also, consider:
#define is_SSOed(vec) ((uintptr_t)&vec <=3D (uintptr_t)vec.data() &&
(uintptr_t)vec.data() <=3D (uintptr_t)&vec + sizeof(vec));
std::small_vector<int, 4> vec =3D { 1, 2, 3 };
assert(vec.size() =3D=3D 3 && vec.capacity() =3D=3D 4 && is_SSOed(vec))=
;
vec.push_back(0);
assert(vec.size() =3D=3D 4 && vec.capacity() =3D=3D 4 && is_SSOed(vec))=
;
vec.push_back(0);
assert(vec.size() =3D=3D 5 && vec.capacity() >=3D 5 && !is_SSOed(vec));
vec.pop_back(); // must not reallocate the vector
assert(vec.size() =3D=3D 4 && vec.capacity() >=3D 5 && !is_SSOed(vec));
vec.pop_back(); // must not reallocate the vector
assert(vec.size() =3D=3D 3 && vec.capacity() >=3D 5 && !is_SSOed(vec));
That is, (vec.size() <=3D decltype(vec)::SSO_capacity) does not necessarily
imply is_SSOed(vec).
Notice that std::vector<T> could simply be an alias for small_vector<T,0> =
=E2=80=94
that is, std::vector is exactly equivalent to a small_vector where the SSO
buffer is big enough to store zero elements.
> The use-case would be things like
> >
> > struct ChessPosition {
> > std::small_vector<ChessPiece,32> pieces;
> > };
> >
> > where ChessPosition's copy constructor and destructor get called *very*
> > often, so copying the members needs to be *very* fast. Inlining the dat=
a
> > (so no heap allocation needs to happen) is a big win.
>
> True, but this is still O(n).
>
Actually it's O(32), which is to say, O(1). The thing we're trying to
optimize here is the constant factor: copying a std::vector of size 32
requires calling (the equivalent of) malloc followed by memcpy, whereas
copying a small_vector requires calling (the equivalent of) memcpy alone.
> We'd like to be able to tune the N parameter =E2=80=94 for example, if we=
use
> > small_vector<ChessPiece,16>, then early-game positions with more than 1=
6
> > pieces will require a heap allocation (relatively slower), but *every*
> > position will take half the RAM (shrinking our memory footprint and the
> > expense of copy-constructing these things).
>
This is another example of trying to shrink the constant factor in that
O(1). Using small_vector (in my opinion) shouldn't change the *semantics*
of my program; it should merely make my program run *faster*.
=E2=80=93Arthur
--=20
---=20
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 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/group/std-proposa=
ls/.
--14dae9cc988e8b289605107b1d95
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Tue, Mar 3, 2015 at 11:58 PM, Thiago Macieira <span dir=
=3D"ltr"><<a href=3D"mailto:thiago@macieira.org" target=3D"_blank">thiag=
o@macieira.org</a>></span> wrote:<br><div class=3D"gmail_extra"><div cla=
ss=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0p=
x 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border=
-left-style:solid;padding-left:1ex">On Tuesday 03 March 2015 23:42:49 Arthu=
r O'Dwyer wrote:<br>
> In my opinion, "small_vector" would be a great addition to t=
he standard<br>
> library, but *only* if small_vector<T,N>& and vector<T>=
;& are<br>
> inter-convertible (in constant time). I believe that's doable, alt=
hough I'm<br>
> not sure how to write the *implementation* in purely standard-conformi=
ng<br>
> C++ =E2=80=94 it might require some reinterpret_casts.<br>
<br>
You can't create a copy in constant time</blockquote><div><br></div><di=
v>I didn't say you should be able to create copies in constant time; I =
said that small_vector<T,N>& should be convertible to vector<T=
>& and vice versa.</div><div><br></div><div><font face=3D"monospace,=
monospace">=C2=A0 =C2=A0 void=C2=A0</font><span style=3D"font-family:monos=
pace,monospace">generic_func</span><font face=3D"monospace, monospace">(con=
st std::vector<ChessPiece>& pieces) { ... }</font></div><div><fon=
t face=3D"monospace, monospace"><br></font></div><div><font face=3D"monospa=
ce, monospace">=C2=A0 =C2=A0 std::small_vector<ChessPiece, 16> mypiec=
es;</font></div><div><font face=3D"monospace, monospace">=C2=A0 =C2=A0=C2=
=A0</font><span style=3D"font-family:monospace,monospace">generic_func</spa=
n><font face=3D"monospace, monospace">(mypieces);</font></div><div><div><fo=
nt face=3D"monospace, monospace">=C2=A0 =C2=A0 std::small_vector<ChessPi=
ece, 18> hispieces;</font></div><div><font face=3D"monospace, monospace"=
>=C2=A0 =C2=A0 generic_func(hispieces);</font></div></div><div><font face=
=3D"monospace, monospace"><br></font></div><div>There's no (semantic) r=
eason this code shouldn't work, since vector and small_vector have exac=
tly the same API. We shouldn't need to make <span style=3D"font-family:=
monospace,monospace">generic_func</span>=C2=A0a template just to get this t=
o work, and we should even be able to do it without virtuals.</div><div><br=
></div><div>- All vectors and small_vectors have size and capacity members;=
we just need to make sure they're at the same offsets.</div><div>- We =
might need a boolean flag to indicate whether the data is on the heap or in=
line; this is the part I'm unsure of.</div><div>- Since we know the siz=
e and capacity of the vector, we can even push_back, up to a point...</div>=
<div>- ...and if we need to reallocate the data, then we have to be conserv=
ative and put it on the heap.</div><div><br></div><div>Matthew Fioravante w=
rote:</div><div><span style=3D"font-size:13px">> For example the SSO buf=
fer and the capacity can share space using a union since</span><span style=
=3D"font-size:13px">=C2=A0</span><span style=3D"font-size:13px">whenever</s=
pan></div><div><span style=3D"font-size:13px">> the SSO buffer is used, =
we implicitly know the capacity and don't need to store it</span><br></=
div><div><br></div><div>I agree that this would be a useful goal, but I'=
;m pretty sure it conflicts with my own pet goal to make std::small_vector&=
lt;T,M>& interconvertible with std::small_vector<T,N>&, so=
you get to pick one or the other but not both.=C2=A0 In my current design =
(which is not fully implemented) every kind of small_vector needs to know i=
ts "real" capacity; it can't trust its template parameter to =
reflect reality.</div><div><br></div><div>Also, consider:</div><div><br></d=
iv><div><font face=3D"monospace, monospace">=C2=A0 =C2=A0 #define is_SSOed(=
vec) ((uintptr_t)&vec <=3D (uintptr_t)vec.data() && (uintptr=
_t)vec.data() <=3D (uintptr_t)&vec + sizeof(vec));</font></div><div>=
<font face=3D"monospace, monospace"><br></font></div><div><font face=3D"mon=
ospace, monospace">=C2=A0 =C2=A0 std::small_vector<int, 4> vec =3D { =
1, 2, 3 };</font></div><div><font face=3D"monospace, monospace">=C2=A0 =C2=
=A0 assert(vec.size() =3D=3D 3 && vec.capacity() =3D=3D 4 &&=
; is_SSOed(vec));</font></div><div><font face=3D"monospace, monospace">=C2=
=A0 =C2=A0 vec.push_back(0);</font></div><div><div><font face=3D"monospace,=
monospace">=C2=A0 =C2=A0 assert(vec.size() =3D=3D 4 && vec.capacit=
y() =3D=3D 4 && is_SSOed(vec));</font></div></div><div><div><font f=
ace=3D"monospace, monospace">=C2=A0 =C2=A0 vec.push_back(0);</font></div><d=
iv><font face=3D"monospace, monospace">=C2=A0 =C2=A0 assert(vec.size() =3D=
=3D 5 && vec.capacity() >=3D 5 && !is_SSOed(vec));</font=
></div></div><div><font face=3D"monospace, monospace">=C2=A0 =C2=A0 vec.pop=
_back(); =C2=A0// must not reallocate the vector</font></div><div><div><fon=
t face=3D"monospace, monospace">=C2=A0 =C2=A0 assert(vec.size() =3D=3D 4 &a=
mp;& vec.capacity() >=3D 5 && !is_SSOed(vec));</font></div><=
/div><div><div><font face=3D"monospace, monospace">=C2=A0 =C2=A0 vec.pop_ba=
ck(); =C2=A0// must not reallocate the vector</font></div><div><font face=
=3D"monospace, monospace">=C2=A0 =C2=A0 assert(vec.size() =3D=3D 3 &&am=
p; vec.capacity() >=3D 5 && !is_SSOed(vec));</font></div></div><=
div><br></div><div>That is, <font face=3D"monospace, monospace">(vec.size()=
<=3D decltype(vec)::SSO_capacity)</font> does not necessarily imply <fo=
nt face=3D"monospace, monospace">is_SSOed(vec)</font>.</div><div><br></div>=
<div>Notice that std::vector<T> could simply be an alias for small_ve=
ctor<T,0> =E2=80=94 that is, std::vector is exactly equivalent to a s=
mall_vector where the SSO buffer is big enough to store zero elements.</div=
><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0=
px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-le=
ft-style:solid;padding-left:1ex">> The use-case would be things like<br>
><br>
> struct ChessPosition {<br>
>=C2=A0 =C2=A0 =C2=A0std::small_vector<ChessPiece,32> pieces;<br>
> };<br>
><br>
> where ChessPosition's copy constructor and destructor get called *=
very*<br>
> often, so copying the members needs to be *very* fast. Inlining the da=
ta<br>
> (so no heap allocation needs to happen) is a big win.<br>
<br>
True, but this is still O(n).<br></blockquote><div><br></div><div>Actually =
it's O(32), which is to say, O(1). The thing we're trying to optimi=
ze here is the constant factor: copying a std::vector of size 32 requires c=
alling (the equivalent of) malloc followed by memcpy, whereas copying a sma=
ll_vector requires calling (the equivalent of) memcpy alone.</div><div><br>=
</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;b=
order-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:s=
olid;padding-left:1ex">> We'd like to be able to tune the N paramete=
r =E2=80=94 for example, if we use<br>
> small_vector<ChessPiece,16>, then early-game positions with more=
than 16<br>
> pieces will require a heap allocation (relatively slower), but *every*=
<br>
> position will take half the RAM (shrinking our memory footprint and th=
e<br>
> expense of copy-constructing these things).<br></blockquote><div><br><=
/div><div>This is another example of trying to shrink the constant factor i=
n that O(1). Using small_vector (in my opinion) shouldn't change the <i=
>semantics</i> of my program; it should merely make my program run <i>faste=
r</i>.</div><div><br></div><div>=E2=80=93Arthur</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" 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 />
--14dae9cc988e8b289605107b1d95--
.
Author: "Arthur O'Dwyer" <arthur.j.odwyer@gmail.com>
Date: Wed, 4 Mar 2015 11:24:27 -0800
Raw View
--047d7bb04bbe577a7e05107b6612
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Wed, Mar 4, 2015 at 7:39 AM, dgutson . <danielgutson@gmail.com> wrote:
> El 04/03/2015 12:31, "David Rodr=C3=ADguez Ibeas" <dibeas@ieee.org> escri=
bi=C3=B3:
> >
> > I think that your problem is/should be addressed in a different
> direction, having an array_view/vector_view (I have heard about those in
> the past, I don't know if there has been any actual proposal, but it woul=
d
> be a simplified string_view). The 'ChessPosition' class looks like it
> should be an 'std::array', and if interfaces that only act on the data ar=
e
> implemented in terms of a *_view, then it should work just fine.
>
Right; bounded_vector is *exactly* a vector_view onto an array. (Except for
the sad fact that SGI STL's vector_view doesn't track "capacity", and so
will buffer-overflow if you push too many things onto it, if I read the
code correctly. But that would be fixable.)
Notice that SGI vector_view isn't exactly analogous to string_view, because
string_view is immutable whereas vector_view allows you to modify elements,
push, pop, and resize (but not reserve, because the vector_view doesn't
know how to allocate memory).
> In current C++, and if you need a dynamic size (i.e. std::array does not
> solve your problem), you can use an allocator to control where the memory
> comes from and make it local, you would still be paying for the additiona=
l
> bookkeeping inside vector, but if you need it to actually work that is
> available today...
>
Oh, totally! All these things are "available today", if your definition of
"available today" is "you have to write it yourself from scratch." :D I
don't think anyone in this thread is claiming that the standard library
MUST provide this functionality because it's IMPOSSIBLE to implement by
oneself. People (myself included) are claiming that the standard library
SHOULD provide this functionality because it's TEDIOUS and ERROR-PRONE to
implement by oneself.
Also, unless I'm mistaken, C++14's std::vector doesn't make any guarantees
about how much memory it's going to "allocate" via its allocator. In order
for an allocator-based solution to work, we need a strong guarantee that
std::vector<T>().resize(n) will make exactly one allocation of size
n*sizeof(T). This is a good idea and must be coming soon anyway, but
technically at the present moment there's no such guarantee, is there?
/pedantry
=E2=80=93Arthur
--=20
---=20
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 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/group/std-proposa=
ls/.
--047d7bb04bbe577a7e05107b6612
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Wed, Mar 4, 2015 at 7:39 AM, dgutson . <span dir=3D"ltr=
"><<a href=3D"mailto:danielgutson@gmail.com" target=3D"_blank">danielgut=
son@gmail.com</a>></span> wrote:<div class=3D"gmail_extra"><div class=3D=
"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;=
border-left:1px #ccc solid;padding-left:1ex"><p dir=3D"ltr">
El 04/03/2015 12:31, "David Rodr=C3=ADguez Ibeas" <<a href=3D"=
mailto:dibeas@ieee.org" target=3D"_blank">dibeas@ieee.org</a>> escribi=
=C3=B3:<span class=3D""><br>
><br>
> I think that your problem is/should be addressed in a different direct=
ion, having an array_view/vector_view (I have heard about those in the past=
, I don't know if there has been any actual proposal, but it would be a=
simplified string_view).=C2=A0 The 'ChessPosition' class looks lik=
e it should be an 'std::array', and if interfaces that only act on =
the data are implemented in terms of a *_view, then it should work just fin=
e.</span></p></blockquote><div>Right; bounded_vector is <i>exactly</i> a ve=
ctor_view onto an array. (Except for the sad fact that SGI STL's vector=
_view doesn't track "capacity", and so will buffer-overflow i=
f you push too many things onto it, if I read the code correctly. But that =
would be fixable.)</div><div><br></div><div>Notice that SGI vector_view isn=
't exactly analogous to string_view, because string_view is immutable w=
hereas vector_view allows you to modify elements, push, pop, and resize (bu=
t not reserve, because the vector_view doesn't know how to allocate mem=
ory).</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin=
:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir=3D"ltr"><sp=
an class=3D"">> In current C++, and if you need a dynamic size (i.e. std=
::array does not solve your problem), you can use an allocator to control w=
here the memory comes from and make it local, you would still be paying for=
the additional bookkeeping inside vector, but if you need it to actually w=
ork that is available today...</span></p></blockquote><div>Oh, totally! All=
these things are "available today", if your definition of "=
available today" is "you have to write it yourself from scratch.&=
quot; :D =C2=A0I don't think anyone in this thread is claiming that the=
standard library MUST provide this functionality because it's IMPOSSIB=
LE to implement by oneself. People (myself included) are claiming that the =
standard library SHOULD provide this functionality because it's TEDIOUS=
and ERROR-PRONE to implement by oneself.</div><div><br></div><div>Also, un=
less I'm mistaken, C++14's std::vector doesn't make any guarant=
ees about how much memory it's going to "allocate" via its al=
locator. In order for an allocator-based solution to work, we need a strong=
guarantee that <font face=3D"monospace, monospace">std::vector<T>().=
resize(n)</font> will make exactly one allocation of size <font face=3D"mon=
ospace, monospace">n*sizeof(T)</font>. This is a good idea and must be comi=
ng soon anyway, but technically at the present moment there's no such g=
uarantee, is there? /pedantry</div><div><br></div><div>=E2=80=93Arthur</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" 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 />
--047d7bb04bbe577a7e05107b6612--
.
Author: Douglas Boffey <douglas.boffey@gmail.com>
Date: Wed, 4 Mar 2015 20:17:28 +0000
Raw View
O(1) time is still unachievable. The best you can hope for is
amortised constant time.
On 3/4/15, Arthur O'Dwyer <arthur.j.odwyer@gmail.com> wrote:
> On Tue, Mar 3, 2015 at 11:58 PM, Thiago Macieira <thiago@macieira.org>
> wrote:
>
>> On Tuesday 03 March 2015 23:42:49 Arthur O'Dwyer wrote:
>> > In my opinion, "small_vector" would be a great addition to the standar=
d
>> > library, but *only* if small_vector<T,N>& and vector<T>& are
>> > inter-convertible (in constant time). I believe that's doable, althoug=
h
>> I'm
>> > not sure how to write the *implementation* in purely
>> > standard-conforming
>> > C++ =E2=80=94 it might require some reinterpret_casts.
>>
>> You can't create a copy in constant time
>
>
> I didn't say you should be able to create copies in constant time; I said
> that small_vector<T,N>& should be convertible to vector<T>& and vice vers=
a.
>
> void generic_func(const std::vector<ChessPiece>& pieces) { ... }
>
> std::small_vector<ChessPiece, 16> mypieces;
> generic_func(mypieces);
> std::small_vector<ChessPiece, 18> hispieces;
> generic_func(hispieces);
>
> There's no (semantic) reason this code shouldn't work, since vector and
> small_vector have exactly the same API. We shouldn't need to make
> generic_func a template just to get this to work, and we should even be
> able to do it without virtuals.
>
> - All vectors and small_vectors have size and capacity members; we just
> need to make sure they're at the same offsets.
> - We might need a boolean flag to indicate whether the data is on the hea=
p
> or inline; this is the part I'm unsure of.
> - Since we know the size and capacity of the vector, we can even push_bac=
k,
> up to a point...
> - ...and if we need to reallocate the data, then we have to be conservati=
ve
> and put it on the heap.
>
> Matthew Fioravante wrote:
>> For example the SSO buffer and the capacity can share space using a unio=
n
> since whenever
>> the SSO buffer is used, we implicitly know the capacity and don't need t=
o
> store it
>
> I agree that this would be a useful goal, but I'm pretty sure it conflict=
s
> with my own pet goal to make std::small_vector<T,M>& interconvertible wit=
h
> std::small_vector<T,N>&, so you get to pick one or the other but not both=
..
> In my current design (which is not fully implemented) every kind of
> small_vector needs to know its "real" capacity; it can't trust its templa=
te
> parameter to reflect reality.
>
> Also, consider:
>
> #define is_SSOed(vec) ((uintptr_t)&vec <=3D (uintptr_t)vec.data() &&
> (uintptr_t)vec.data() <=3D (uintptr_t)&vec + sizeof(vec));
>
> std::small_vector<int, 4> vec =3D { 1, 2, 3 };
> assert(vec.size() =3D=3D 3 && vec.capacity() =3D=3D 4 && is_SSOed(vec=
));
> vec.push_back(0);
> assert(vec.size() =3D=3D 4 && vec.capacity() =3D=3D 4 && is_SSOed(vec=
));
> vec.push_back(0);
> assert(vec.size() =3D=3D 5 && vec.capacity() >=3D 5 && !is_SSOed(vec)=
);
> vec.pop_back(); // must not reallocate the vector
> assert(vec.size() =3D=3D 4 && vec.capacity() >=3D 5 && !is_SSOed(vec)=
);
> vec.pop_back(); // must not reallocate the vector
> assert(vec.size() =3D=3D 3 && vec.capacity() >=3D 5 && !is_SSOed(vec)=
);
>
> That is, (vec.size() <=3D decltype(vec)::SSO_capacity) does not necessari=
ly
> imply is_SSOed(vec).
>
> Notice that std::vector<T> could simply be an alias for small_vector<T,0>=
=E2=80=94
> that is, std::vector is exactly equivalent to a small_vector where the SS=
O
> buffer is big enough to store zero elements.
>
>> The use-case would be things like
>> >
>> > struct ChessPosition {
>> > std::small_vector<ChessPiece,32> pieces;
>> > };
>> >
>> > where ChessPosition's copy constructor and destructor get called *very=
*
>> > often, so copying the members needs to be *very* fast. Inlining the
>> > data
>> > (so no heap allocation needs to happen) is a big win.
>>
>> True, but this is still O(n).
>>
>
> Actually it's O(32), which is to say, O(1). The thing we're trying to
> optimize here is the constant factor: copying a std::vector of size 32
> requires calling (the equivalent of) malloc followed by memcpy, whereas
> copying a small_vector requires calling (the equivalent of) memcpy alone.
>
>> We'd like to be able to tune the N parameter =E2=80=94 for example, if w=
e use
>> > small_vector<ChessPiece,16>, then early-game positions with more than
>> > 16
>> > pieces will require a heap allocation (relatively slower), but *every*
>> > position will take half the RAM (shrinking our memory footprint and th=
e
>> > expense of copy-constructing these things).
>>
>
> This is another example of trying to shrink the constant factor in that
> O(1). Using small_vector (in my opinion) shouldn't change the *semantics*
> of my program; it should merely make my program run *faster*.
>
> =E2=80=93Arthur
>
> --
>
> ---
> 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/.
>
--=20
---=20
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 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/group/std-proposa=
ls/.
.
Author: Matthew Fioravante <fmatthew5876@gmail.com>
Date: Wed, 4 Mar 2015 12:27:25 -0800 (PST)
Raw View
------=_Part_523_384880177.1425500845350
Content-Type: multipart/alternative;
boundary="----=_Part_524_460390075.1425500845351"
------=_Part_524_460390075.1425500845351
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Wednesday, March 4, 2015 at 2:04:11 PM UTC-5, Arthur O'Dwyer wrote:
>
> On Tue, Mar 3, 2015 at 11:58 PM, Thiago Macieira <thi...@macieira.org=20
> <javascript:>> wrote:
>
>> On Tuesday 03 March 2015 23:42:49 Arthur O'Dwyer wrote:
>> > In my opinion, "small_vector" would be a great addition to the standar=
d
>> > library, but *only* if small_vector<T,N>& and vector<T>& are
>> > inter-convertible (in constant time). I believe that's doable, althoug=
h=20
>> I'm
>> > not sure how to write the *implementation* in purely standard-conformi=
ng
>> > C++ =E2=80=94 it might require some reinterpret_casts.
>>
>> You can't create a copy in constant time
>
>
> I didn't say you should be able to create copies in constant time; I said=
=20
> that small_vector<T,N>& should be convertible to vector<T>& and vice vers=
a.
>
> void generic_func(const std::vector<ChessPiece>& pieces) { ... }
>
> std::small_vector<ChessPiece, 16> mypieces;
> generic_func(mypieces);
> std::small_vector<ChessPiece, 18> hispieces;
> generic_func(hispieces);
>
If you're only reading/writing the data and not modifying the container=20
itself, you can use array_view.
For your approach to work we have to use inheritance and have small_vector=
=20
inherit from vector. The only way this approach would acceptable is if=20
std::vector can still operate the same way it always did with zero overhead=
=20
because std::vector is the most important and most efficiency critical data=
=20
structure in the entire standard library.
One big problem which probably kills this approach is resizing. If your=20
vector pointer is pointing to the SSO buffer, how does the vector know not=
=20
to try to free() this pointer after it moves the data to a new dynamically=
=20
allocated buffer. Adding any additional state to std::vector breaks the=20
zero overhead requirement I just mentioned.
If you really want this level of generality without templates or copy=20
construction, then I believe the correct solution is a vector_view which=20
can keep bools and any other state necessary to handle the SSO logic.
=20
> There's no (semantic) reason this code shouldn't work, since vector and=
=20
> small_vector have exactly the same API. We shouldn't need to make=20
> generic_func a template just to get this to work, and we should even be=
=20
> able to do it without virtuals.
>
virtuals are a no-go, std::vector cannot have an additional vptr bloating=
=20
its size by sizeof(void*). d a flag. Just have the vector base class=20
pointer point to the buffer when SSO is active. Adding a flag to=20
std::vector is also the kind of unacceptable overhead I mentioned before.
- Since we know the size and capacity of the vector, we can even push_back,=
=20
> up to a point...
> - ...and if we need to reallocate the data, then we have to be=20
> conservative and put it on the heap.
>
> Matthew Fioravante wrote:
> > For example the SSO buffer and the capacity can share space using a=20
> union since whenever
> > the SSO buffer is used, we implicitly know the capacity and don't need=
=20
> to store it
>
> I agree that this would be a useful goal, but I'm pretty sure it conflict=
s=20
> with my own pet goal to make std::small_vector<T,M>& interconvertible wit=
h=20
> std::small_vector<T,N>&, so you get to pick one or the other but not both=
.. =20
> In my current design (which is not fully implemented) every kind of=20
> small_vector needs to know its "real" capacity; it can't trust its templa=
te=20
> parameter to reflect reality.
>
With the vector_view approach, implementations are not so constrained.=20
--=20
---=20
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 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/group/std-proposa=
ls/.
------=_Part_524_460390075.1425500845351
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br>On Wednesday, March 4, 2015 at 2:04:11 PM UTC-5, A=
rthur O'Dwyer wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;ma=
rgin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr">On Tue, Mar 3, 2015 at 11:58 PM, Thiago Macieira <span dir=3D"ltr"=
><<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"Xvz=
nxFIcpiwJ" rel=3D"nofollow" onmousedown=3D"this.href=3D'javascript:';return=
true;" onclick=3D"this.href=3D'javascript:';return true;">thi...@macieira.=
org</a>></span> wrote:<br><div><div class=3D"gmail_quote"><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px=
;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1e=
x">On Tuesday 03 March 2015 23:42:49 Arthur O'Dwyer wrote:<br>
> In my opinion, "small_vector" would be a great addition to the standar=
d<br>
> library, but *only* if small_vector<T,N>& and vector<T>=
;& are<br>
> inter-convertible (in constant time). I believe that's doable, althoug=
h I'm<br>
> not sure how to write the *implementation* in purely standard-conformi=
ng<br>
> C++ =E2=80=94 it might require some reinterpret_casts.<br>
<br>
You can't create a copy in constant time</blockquote><div><br></div><div>I =
didn't say you should be able to create copies in constant time; I said tha=
t small_vector<T,N>& should be convertible to vector<T>&=
; and vice versa.</div><div><br></div><div><font face=3D"monospace, monospa=
ce"> void </font><span style=3D"font-family:monospace,mon=
ospace">generic_func</span><font face=3D"monospace, monospace">(const std::=
vector<ChessPiece>& pieces) { ... }</font></div><div><font face=
=3D"monospace, monospace"><br></font></div><div><font face=3D"monospace, mo=
nospace"> std::small_vector<ChessPiece, 16> mypieces;</f=
ont></div><div><font face=3D"monospace, monospace"> </fon=
t><span style=3D"font-family:monospace,monospace">generic_func</span><font =
face=3D"monospace, monospace">(mypieces);</font></div><div><div><font face=
=3D"monospace, monospace"> std::small_vector<ChessPiece, 18=
> hispieces;</font></div><div><font face=3D"monospace, monospace"> =
generic_func(hispieces);</font></div></div></div></div></div></bloc=
kquote><div><br>If you're only reading/writing the data and not modifying t=
he container itself, you can use array_view.<br><br>For your approach to wo=
rk we have to use inheritance and have small_vector inherit from vector. Th=
e only way this approach would acceptable is if std::vector can still opera=
te the same way it always did with zero overhead because std::vector is the=
most important and most efficiency critical data structure in the entire s=
tandard library.<br><br>One big problem which probably kills this approach =
is resizing. If your vector pointer is pointing to the SSO buffer, how does=
the vector know not to try to free() this pointer after it moves the data =
to a new dynamically allocated buffer. Adding any additional state to std::=
vector breaks the zero overhead requirement I just mentioned.<br><br>If you=
really want this level of generality without templates or copy constructio=
n, then I believe the correct solution is a vector_view which can keep bool=
s and any other state necessary to handle the SSO logic.<br> </div><bl=
ockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border=
-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div class=
=3D"gmail_quote"><div><font face=3D"monospace, monospace"></font></div><div=
>There's no (semantic) reason this code shouldn't work, since vector and sm=
all_vector have exactly the same API. We shouldn't need to make <span style=
=3D"font-family:monospace,monospace">generic_func</span> a template ju=
st to get this to work, and we should even be able to do it without virtual=
s.</div></div></div></div></blockquote><div><br>virtuals are a no-go, std::=
vector cannot have an additional vptr bloating its size by sizeof(void*). d=
a flag. Just have the vector base class pointer point to the buffer when S=
SO is active. Adding a flag to std::vector is also the kind of unacceptable=
overhead I mentioned before.<br><br><br><br></div><blockquote class=3D"gma=
il_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid=
;padding-left: 1ex;"><div dir=3D"ltr"><div><div class=3D"gmail_quote"><div>=
- Since we know the size and capacity of the vector, we can even push_back,=
up to a point...</div><div>- ...and if we need to reallocate the data, the=
n we have to be conservative and put it on the heap.</div><div><br></div><d=
iv>Matthew Fioravante wrote:</div><div><span style=3D"font-size:13px">> =
For example the SSO buffer and the capacity can share space using a union s=
ince</span><span style=3D"font-size:13px"> </span><span style=3D"font-=
size:13px">whenever</span></div><div><span style=3D"font-size:13px">> th=
e SSO buffer is used, we implicitly know the capacity and don't need to sto=
re it</span><br></div><div><br></div><div>I agree that this would be a usef=
ul goal, but I'm pretty sure it conflicts with my own pet goal to make std:=
:small_vector<T,M>& interconvertible with std::small_vector<T,=
N>&, so you get to pick one or the other but not both. In my c=
urrent design (which is not fully implemented) every kind of small_vector n=
eeds to know its "real" capacity; it can't trust its template parameter to =
reflect reality.</div></div></div></div></blockquote><div><br>With the vect=
or_view approach, implementations are not so constrained. <br></div><br></d=
iv>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" 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 />
------=_Part_524_460390075.1425500845351--
------=_Part_523_384880177.1425500845350--
.
Author: =?UTF-8?Q?David_Rodr=C3=ADguez_Ibeas?= <dibeas@ieee.org>
Date: Wed, 04 Mar 2015 22:37:48 +0000
Raw View
--001a11471190deb66005107e193b
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Wed, Mar 4, 2015 at 2:24 PM Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
wrote:
> On Wed, Mar 4, 2015 at 7:39 AM, dgutson . <danielgutson@gmail.com> wrote:
>
>> El 04/03/2015 12:31, "David Rodr=C3=ADguez Ibeas" <dibeas@ieee.org> escr=
ibi=C3=B3:Right;
>> bounded_vector is *exactly* a vector_view onto an array. (Except for the
>> sad fact that SGI STL's vector_view doesn't track "capacity", and so wil=
l
>> buffer-overflow if you push too many things onto it, if I read the code
>> correctly. But that would be fixable.)
>>
> I did not mean to have an interface that allows insertion, only a *view*
(you can transverse the existing elements but not add/remove). This might
not apply to your particular problem, but it is a simple way of
representing a sequence of contiguous elements.
Notice that SGI vector_view isn't exactly analogous to string_view, because
> string_view is immutable whereas vector_view allows you to modify element=
s,
> push, pop, and resize (but not reserve, because the vector_view doesn't
> know how to allocate memory).
>
The problem with providing an interface for adding/removing elements ins
that in some cases you might not be able to (say that the sequence is
really an array), or the semantics may be different (vector can always
reallocate and grow, you don't need to call 'capacity()' to determine
whether you can push one more element).
> Oh, totally! All these things are "available today", if your definition o=
f
>> "available today" is "you have to write it yourself from scratch." :D
>>
> https://github.com/bloomberg/bde
It is mostly a C++03 library implementation with all of the building blocks
for the above. You can pull the 'bsl::allocator' template and the
'bslma::Allocator' protocol and implementation out and use that in your
favorite C++11 library. In particular you might want to look at
'bslma::BufferSequentialAllocator' which takes a buffer and allocates out
of it if possible, or falls back to the heap (really to another allocator,
you can configure which). The work to get this running is not HUGE, it is
actually quite small.
> Also, unless I'm mistaken, C++14's std::vector doesn't make any guarantee=
s
>> about how much memory it's going to "allocate" via its allocator. In ord=
er
>> for an allocator-based solution to work, we need a strong guarantee that
>> std::vector<T>().resize(n) will make exactly one allocation of size
>> n*sizeof(T). This is a good idea and must be coming soon anyway, but
>> technically at the present moment there's no such guarantee, is there?
>> /pedantry
>>
> Correct, you need to check your implementation. In my case I know the
implementation and I know how the vector will grow, I can verify in test
drivers how much memory is allocated.
Again, I don't think polymorphic allocators (so that the type of this
vector is not different than any other vector) are for everyone, but they
are a solution for some problems. Also, I am not even sure that you will
get a huge advantage from using a local array versus dynamically allocated
memory (the cost of allocation is becoming smaller and smaller), so using a
plain std::vector with tcmalloc might give you most of the performance in
most of the cases, but you should really measure.
David
--=20
---=20
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 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/group/std-proposa=
ls/.
--001a11471190deb66005107e193b
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br><div class=3D"gmail_quote">On Wed, Mar 4, 2015 at =
2:24 PM Arthur O'Dwyer <<a href=3D"mailto:arthur.j.odwyer@gmail.com"=
>arthur.j.odwyer@gmail.com</a>> wrote:<br><blockquote class=3D"gmail_quo=
te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"=
><div dir=3D"ltr">On Wed, Mar 4, 2015 at 7:39 AM, dgutson . <span dir=3D"lt=
r"><<a href=3D"mailto:danielgutson@gmail.com" target=3D"_blank">danielgu=
tson@gmail.com</a>></span> wrote:</div><div dir=3D"ltr"><div class=3D"gm=
ail_extra"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" sty=
le=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir=
=3D"ltr">
El 04/03/2015 12:31, "David Rodr=C3=ADguez Ibeas" <<a href=3D"=
mailto:dibeas@ieee.org" target=3D"_blank">dibeas@ieee.org</a>> escribi=
=C3=B3:<span style=3D"font-size:13.1999998092651px">Right; bounded_vector i=
s </span><i style=3D"font-size:13.1999998092651px">exactly</i><span style=
=3D"font-size:13.1999998092651px"> a vector_view onto an array. (Except for=
the sad fact that SGI STL's vector_view doesn't track "capaci=
ty", and so will buffer-overflow if you push too many things onto it, =
if I read the code correctly. But that would be fixable.)</span></p></block=
quote></div></div></div></blockquote><div>=C2=A0I did not mean to have an i=
nterface that allows insertion, only a *view* (you can transverse the exist=
ing elements but not add/remove). This might not apply to your particular p=
roblem, but it is a simple way of representing a sequence of contiguous ele=
ments.=C2=A0<br><br></div><blockquote class=3D"gmail_quote" style=3D"margin=
:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><=
div class=3D"gmail_extra"><div class=3D"gmail_quote"><div></div><div>Notice=
that SGI vector_view isn't exactly analogous to string_view, because s=
tring_view is immutable whereas vector_view allows you to modify elements, =
push, pop, and resize (but not reserve, because the vector_view doesn't=
know how to allocate memory).</div></div></div></div></blockquote><div><br=
>The problem with providing an interface for adding/removing elements ins t=
hat in some cases you might not be able to (say that the sequence is really=
an array), or the semantics may be different (vector can always reallocate=
and grow, you don't need to call 'capacity()' to determine whe=
ther you can push one more element).=C2=A0</div><blockquote class=3D"gmail_=
quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1=
ex"><div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">=
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><p dir=3D"ltr"><span style=3D"font-size:13.1=
999998092651px">Oh, totally! All these things are "available today&quo=
t;, if your definition of "available today" is "you have to =
write it yourself from scratch." :D </span></p></blockquote></div></di=
v></div></blockquote><div>=C2=A0<a href=3D"https://github.com/bloomberg/bde=
">https://github.com/bloomberg/bde</a><br><br>It is mostly a C++03 library =
implementation with all of the building blocks for the above.=C2=A0 You can=
pull the 'bsl::allocator' template and the 'bslma::Allocator&#=
39; protocol and implementation out and use that in your favorite C++11 lib=
rary. In particular you might want to look at 'bslma::BufferSequentialA=
llocator' which takes a buffer and allocates out of it if possible, or =
falls back to the heap (really to another allocator, you can configure whic=
h).=C2=A0 The work to get this running is not HUGE, it is actually quite sm=
all.</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bord=
er-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gma=
il_extra"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><p dir=
=3D"ltr"><span style=3D"font-size:13.1999998092651px">Also, unless I'm =
mistaken, C++14's std::vector doesn't make any guarantees about how=
much memory it's going to "allocate" via its allocator. In o=
rder for an allocator-based solution to work, we need a strong guarantee th=
at </span><font face=3D"monospace, monospace" style=3D"font-size:13.1999998=
092651px">std::vector<T>().resize(n)</font><span style=3D"font-size:1=
3.1999998092651px"> will make exactly one allocation of size </span><font f=
ace=3D"monospace, monospace" style=3D"font-size:13.1999998092651px">n*sizeo=
f(T)</font><span style=3D"font-size:13.1999998092651px">. This is a good id=
ea and must be coming soon anyway, but technically at the present moment th=
ere's no such guarantee, is there? /pedantry</span></p></blockquote></d=
iv></div></div></blockquote><div>Correct, you need to check your implementa=
tion. In my case I know the implementation and I know how the vector will g=
row, I can verify in test drivers how much memory is allocated.=C2=A0<br><b=
r>Again, I don't think polymorphic allocators (so that the type of this=
vector is not different than any other vector) are for everyone, but they =
are a solution for some problems.=C2=A0 Also, I am not even sure that you w=
ill get a huge advantage from using a local array versus dynamically alloca=
ted memory (the cost of allocation is becoming smaller and smaller), so usi=
ng a plain std::vector with tcmalloc might give you most of the performance=
in most of the cases, but you should really measure.<br><br>=C2=A0 =C2=A0 =
David</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" 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 />
--001a11471190deb66005107e193b--
.
Author: Matthew Fioravante <fmatthew5876@gmail.com>
Date: Wed, 4 Mar 2015 14:51:28 -0800 (PST)
Raw View
------=_Part_3575_1074062432.1425509488050
Content-Type: multipart/alternative;
boundary="----=_Part_3576_19757942.1425509488050"
------=_Part_3576_19757942.1425509488050
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Wednesday, March 4, 2015 at 5:37:51 PM UTC-5, David Rodr=C3=ADguez Ibeas=
=20
wrote:
>
>
>
> On Wed, Mar 4, 2015 at 2:24 PM Arthur O'Dwyer <arthur....@gmail.com=20
> <javascript:>> wrote:
>
>> On Wed, Mar 4, 2015 at 7:39 AM, dgutson . <daniel...@gmail.com=20
>> <javascript:>> wrote:
>>
>>> El 04/03/2015 12:31, "David Rodr=C3=ADguez Ibeas" <dib...@ieee.org=20
>>> <javascript:>> escribi=C3=B3:Right; bounded_vector is *exactly* a=20
>>> vector_view onto an array. (Except for the sad fact that SGI STL's=20
>>> vector_view doesn't track "capacity", and so will buffer-overflow if yo=
u=20
>>> push too many things onto it, if I read the code correctly. But that wo=
uld=20
>>> be fixable.)
>>>
>> I did not mean to have an interface that allows insertion, only a *view=
*=20
> (you can transverse the existing elements but not add/remove). This might=
=20
> not apply to your particular problem, but it is a simple way of=20
> representing a sequence of contiguous elements.=20
>
array_view<T> is what you want.
=20
> Also, I am not even sure that you will get a huge advantage from using a=
=20
> local array versus dynamically allocated memory (the cost of allocation i=
s=20
> becoming smaller and smaller), so using a plain std::vector with tcmalloc=
=20
> might give you most of the performance in most of the cases, but you shou=
ld=20
> really measure.
>
It really depends on your usage pattern. If you create the buffer once and=
=20
reuse it multiple times, the allocation cost is probably low. If you're=20
constantly creating new objects (such as using a "modern" API which returns=
=20
strings by value) then you need the SSO the avoid multiple allocations.
Another use case is one I mentioned earlier:
vector<small_vector<T,N>>;
In this situation, all of the SSO buffers will be lined up linearly in one=
=20
memory allocation block, providing optimal cache locality. If we can use=20
union tricks to hide data members not needed when SSO is turned on, the=20
cache locality improves further.
--=20
---=20
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 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/group/std-proposa=
ls/.
------=_Part_3576_19757942.1425509488050
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br>On Wednesday, March 4, 2015 at 5:37:51 PM UTC-5, D=
avid Rodr=C3=ADguez Ibeas wrote:<blockquote class=3D"gmail_quote" style=3D"=
margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;=
"><div dir=3D"ltr"><br><br><div class=3D"gmail_quote">On Wed, Mar 4, 2015 a=
t 2:24 PM Arthur O'Dwyer <<a href=3D"javascript:" target=3D"_blank" gdf-=
obfuscated-mailto=3D"8OwVaZ679DAJ" rel=3D"nofollow" onmousedown=3D"this.hre=
f=3D'javascript:';return true;" onclick=3D"this.href=3D'javascript:';return=
true;">arthur....@gmail.com</a>> wrote:<br><blockquote class=3D"gmail_q=
uote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1e=
x"><div dir=3D"ltr">On Wed, Mar 4, 2015 at 7:39 AM, dgutson . <span dir=3D"=
ltr"><<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D=
"8OwVaZ679DAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D'javascript:';re=
turn true;" onclick=3D"this.href=3D'javascript:';return true;">daniel...@gm=
ail.com</a>></span> wrote:</div><div dir=3D"ltr"><div><div class=3D"gmai=
l_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;borde=
r-left:1px #ccc solid;padding-left:1ex"><p dir=3D"ltr">
El 04/03/2015 12:31, "David Rodr=C3=ADguez Ibeas" <<a href=3D"javascript=
:" target=3D"_blank" gdf-obfuscated-mailto=3D"8OwVaZ679DAJ" rel=3D"nofollow=
" onmousedown=3D"this.href=3D'javascript:';return true;" onclick=3D"this.hr=
ef=3D'javascript:';return true;">dib...@ieee.org</a>> escribi=C3=B3:<spa=
n style=3D"font-size:13.1999998092651px">Right; bounded_vector is </span><i=
style=3D"font-size:13.1999998092651px">exactly</i><span style=3D"font-size=
:13.1999998092651px"> a vector_view onto an array. (Except for the sad fact=
that SGI STL's vector_view doesn't track "capacity", and so will buffer-ov=
erflow if you push too many things onto it, if I read the code correctly. B=
ut that would be fixable.)</span></p></blockquote></div></div></div></block=
quote><div> I did not mean to have an interface that allows insertion,=
only a *view* (you can transverse the existing elements but not add/remove=
). This might not apply to your particular problem, but it is a simple way =
of representing a sequence of contiguous elements. <br></div></div></d=
iv></blockquote><div><br>array_view<T> is what you want.<br> </d=
iv><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;=
border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div class=
=3D"gmail_quote"><div>Also, I am not even sure that you will get a huge adv=
antage from using a local array versus dynamically allocated memory (the co=
st of allocation is becoming smaller and smaller), so using a plain std::ve=
ctor with tcmalloc might give you most of the performance in most of the ca=
ses, but you should really measure.<br></div></div></div></blockquote><div>=
<br>It really depends on your usage pattern. If you create the buffer once =
and reuse it multiple times, the allocation cost is probably low. If you're=
constantly creating new objects (such as using a "modern" API which return=
s strings by value) then you need the SSO the avoid multiple allocations.<b=
r><br>Another use case is one I mentioned earlier:<br><br>vector<small_v=
ector<T,N>>;<br><br>In this situation, all of the SSO buffers will=
be lined up linearly in one memory allocation block, providing optimal cac=
he locality. If we can use union tricks to hide data members not needed whe=
n SSO is turned on, the cache locality improves further.<br></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" 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 />
------=_Part_3576_19757942.1425509488050--
------=_Part_3575_1074062432.1425509488050--
.
Author: Douglas Boffey <douglas.boffey@gmail.com>
Date: Thu, 5 Mar 2015 13:11:42 +0000
Raw View
--001a113552c62a7c0705108a4ff0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Wed, Mar 4, 2015 at 8:17 PM, Douglas Boffey <douglas.boffey@gmail.com>
wrote:
> O(1) time is still unachievable. The best you can hope for is
> amortised constant time.
>
>
My mistake=E2=80=94I misread the thread.
> On 3/4/15, Arthur O'Dwyer <arthur.j.odwyer@gmail.com> wrote:
> > On Tue, Mar 3, 2015 at 11:58 PM, Thiago Macieira <thiago@macieira.org>
> > wrote:
> >
> >> On Tuesday 03 March 2015 23:42:49 Arthur O'Dwyer wrote:
> >> > In my opinion, "small_vector" would be a great addition to the
> standard
> >> > library, but *only* if small_vector<T,N>& and vector<T>& are
> >> > inter-convertible (in constant time). I believe that's doable,
> although
> >> I'm
> >> > not sure how to write the *implementation* in purely
> >> > standard-conforming
> >> > C++ =E2=80=94 it might require some reinterpret_casts.
> >>
> >> You can't create a copy in constant time
> >
> >
> > I didn't say you should be able to create copies in constant time; I sa=
id
> > that small_vector<T,N>& should be convertible to vector<T>& and vice
> versa.
> >
> > void generic_func(const std::vector<ChessPiece>& pieces) { ... }
> >
> > std::small_vector<ChessPiece, 16> mypieces;
> > generic_func(mypieces);
> > std::small_vector<ChessPiece, 18> hispieces;
> > generic_func(hispieces);
> >
> > There's no (semantic) reason this code shouldn't work, since vector and
> > small_vector have exactly the same API. We shouldn't need to make
> > generic_func a template just to get this to work, and we should even be
> > able to do it without virtuals.
> >
> > - All vectors and small_vectors have size and capacity members; we just
> > need to make sure they're at the same offsets.
> > - We might need a boolean flag to indicate whether the data is on the
> heap
> > or inline; this is the part I'm unsure of.
> > - Since we know the size and capacity of the vector, we can even
> push_back,
> > up to a point...
> > - ...and if we need to reallocate the data, then we have to be
> conservative
> > and put it on the heap.
> >
> > Matthew Fioravante wrote:
> >> For example the SSO buffer and the capacity can share space using a
> union
> > since whenever
> >> the SSO buffer is used, we implicitly know the capacity and don't need
> to
> > store it
> >
> > I agree that this would be a useful goal, but I'm pretty sure it
> conflicts
> > with my own pet goal to make std::small_vector<T,M>& interconvertible
> with
> > std::small_vector<T,N>&, so you get to pick one or the other but not
> both.
> > In my current design (which is not fully implemented) every kind of
> > small_vector needs to know its "real" capacity; it can't trust its
> template
> > parameter to reflect reality.
> >
> > Also, consider:
> >
> > #define is_SSOed(vec) ((uintptr_t)&vec <=3D (uintptr_t)vec.data() &=
&
> > (uintptr_t)vec.data() <=3D (uintptr_t)&vec + sizeof(vec));
> >
> > std::small_vector<int, 4> vec =3D { 1, 2, 3 };
> > assert(vec.size() =3D=3D 3 && vec.capacity() =3D=3D 4 && is_SSOed(v=
ec));
> > vec.push_back(0);
> > assert(vec.size() =3D=3D 4 && vec.capacity() =3D=3D 4 && is_SSOed(v=
ec));
> > vec.push_back(0);
> > assert(vec.size() =3D=3D 5 && vec.capacity() >=3D 5 && !is_SSOed(ve=
c));
> > vec.pop_back(); // must not reallocate the vector
> > assert(vec.size() =3D=3D 4 && vec.capacity() >=3D 5 && !is_SSOed(ve=
c));
> > vec.pop_back(); // must not reallocate the vector
> > assert(vec.size() =3D=3D 3 && vec.capacity() >=3D 5 && !is_SSOed(ve=
c));
> >
> > That is, (vec.size() <=3D decltype(vec)::SSO_capacity) does not necessa=
rily
> > imply is_SSOed(vec).
> >
> > Notice that std::vector<T> could simply be an alias for
> small_vector<T,0> =E2=80=94
> > that is, std::vector is exactly equivalent to a small_vector where the
> SSO
> > buffer is big enough to store zero elements.
> >
> >> The use-case would be things like
> >> >
> >> > struct ChessPosition {
> >> > std::small_vector<ChessPiece,32> pieces;
> >> > };
> >> >
> >> > where ChessPosition's copy constructor and destructor get called
> *very*
> >> > often, so copying the members needs to be *very* fast. Inlining the
> >> > data
> >> > (so no heap allocation needs to happen) is a big win.
> >>
> >> True, but this is still O(n).
> >>
> >
> > Actually it's O(32), which is to say, O(1). The thing we're trying to
> > optimize here is the constant factor: copying a std::vector of size 32
> > requires calling (the equivalent of) malloc followed by memcpy, whereas
> > copying a small_vector requires calling (the equivalent of) memcpy alon=
e.
> >
> >> We'd like to be able to tune the N parameter =E2=80=94 for example, if=
we use
> >> > small_vector<ChessPiece,16>, then early-game positions with more tha=
n
> >> > 16
> >> > pieces will require a heap allocation (relatively slower), but *ever=
y*
> >> > position will take half the RAM (shrinking our memory footprint and
> the
> >> > expense of copy-constructing these things).
> >>
> >
> > This is another example of trying to shrink the constant factor in that
> > O(1). Using small_vector (in my opinion) shouldn't change the *semantic=
s*
> > of my program; it should merely make my program run *faster*.
> >
> > =E2=80=93Arthur
> >
> > --
> >
> > ---
> > You received this message because you are subscribed to the Google Grou=
ps
> > "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/.
> >
>
--=20
---=20
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 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/group/std-proposa=
ls/.
--001a113552c62a7c0705108a4ff0
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<br>
<div class=3D"gmail_quote">On Wed, Mar 4, 2015 at 8:17 PM, Douglas Boffey <=
span dir=3D"ltr"><<a href=3D"mailto:douglas.boffey@gmail.com" target=3D"=
_blank">douglas.boffey@gmail.com</a>></span> wrote:<br>
<blockquote style=3D"BORDER-LEFT:#ccc 1px solid;MARGIN:0px 0px 0px 0.8ex;PA=
DDING-LEFT:1ex" class=3D"gmail_quote">O(1) time is still unachievable.=C2=
=A0 The best you can hope for is<br>amortised constant time.<br>
<div>
<div class=3D"h5">=C2=A0</div></div></blockquote>
<div>My mistake=E2=80=94I misread the thread.</div>
<blockquote style=3D"BORDER-LEFT:#ccc 1px solid;MARGIN:0px 0px 0px 0.8ex;PA=
DDING-LEFT:1ex" class=3D"gmail_quote">
<div>
<div class=3D"h5">On 3/4/15, Arthur O'Dwyer <<a href=3D"mailto:arthu=
r.j.odwyer@gmail.com">arthur.j.odwyer@gmail.com</a>> wrote:<br>> On T=
ue, Mar 3, 2015 at 11:58 PM, Thiago Macieira <<a href=3D"mailto:thiago@m=
acieira.org">thiago@macieira.org</a>><br>> wrote:<br>><br>>>=
On Tuesday 03 March 2015 23:42:49 Arthur O'Dwyer wrote:<br>>> &g=
t; In my opinion, "small_vector" would be a great addition to the=
standard<br>>> > library, but *only* if small_vector<T,N>&a=
mp; and vector<T>& are<br>>> > inter-convertible (in con=
stant time). I believe that's doable, although<br>>> I'm<br>&=
gt;> > not sure how to write the *implementation* in purely<br>>&g=
t; > standard-conforming<br>>> > C++ =E2=80=94 it might require=
some reinterpret_casts.<br>>><br>>> You can't create a cop=
y in constant time<br>><br>><br>> I didn't say you should be a=
ble to create copies in constant time; I said<br>> that small_vector<=
T,N>& should be convertible to vector<T>& and vice versa.<=
br>><br>>=C2=A0 =C2=A0 =C2=A0void generic_func(const std::vector<C=
hessPiece>& pieces) { ... }<br>><br>>=C2=A0 =C2=A0 =C2=A0std::=
small_vector<ChessPiece, 16> mypieces;<br>>=C2=A0 =C2=A0 =C2=A0gen=
eric_func(mypieces);<br>>=C2=A0 =C2=A0 =C2=A0std::small_vector<ChessP=
iece, 18> hispieces;<br>>=C2=A0 =C2=A0 =C2=A0generic_func(hispieces);=
<br>><br>> There's no (semantic) reason this code shouldn't w=
ork, since vector and<br>> small_vector have exactly the same API. We sh=
ouldn't need to make<br>> generic_func a template just to get this t=
o work, and we should even be<br>> able to do it without virtuals.<br>&g=
t;<br>> - All vectors and small_vectors have size and capacity members; =
we just<br>> need to make sure they're at the same offsets.<br>> =
- We might need a boolean flag to indicate whether the data is on the heap<=
br>> or inline; this is the part I'm unsure of.<br>> - Since we k=
now the size and capacity of the vector, we can even push_back,<br>> up =
to a point...<br>> - ...and if we need to reallocate the data, then we h=
ave to be conservative<br>> and put it on the heap.<br>><br>> Matt=
hew Fioravante wrote:<br>>> For example the SSO buffer and the capaci=
ty can share space using a union<br>> since whenever<br>>> the SSO=
buffer is used, we implicitly know the capacity and don't need to<br>&=
gt; store it<br>><br>> I agree that this would be a useful goal, but =
I'm pretty sure it conflicts<br>> with my own pet goal to make std::=
small_vector<T,M>& interconvertible with<br>> std::small_vecto=
r<T,N>&, so you get to pick one or the other but not both.<br>>=
; In my current design (which is not fully implemented) every kind of<br>&g=
t; small_vector needs to know its "real" capacity; it can't t=
rust its template<br>> parameter to reflect reality.<br>><br>> Als=
o, consider:<br>><br>>=C2=A0 =C2=A0 =C2=A0#define is_SSOed(vec) ((uin=
tptr_t)&vec <=3D (uintptr_t)vec.data() &&<br>> (uintptr_t=
)vec.data() <=3D (uintptr_t)&vec + sizeof(vec));<br>><br>>=C2=
=A0 =C2=A0 =C2=A0std::small_vector<int, 4> vec =3D { 1, 2, 3 };<br>&g=
t;=C2=A0 =C2=A0 =C2=A0assert(vec.size() =3D=3D 3 && vec.capacity() =
=3D=3D 4 && is_SSOed(vec));<br>>=C2=A0 =C2=A0 =C2=A0vec.push_bac=
k(0);<br>>=C2=A0 =C2=A0 =C2=A0assert(vec.size() =3D=3D 4 && vec.=
capacity() =3D=3D 4 && is_SSOed(vec));<br>>=C2=A0 =C2=A0 =C2=A0v=
ec.push_back(0);<br>>=C2=A0 =C2=A0 =C2=A0assert(vec.size() =3D=3D 5 &=
;& vec.capacity() >=3D 5 && !is_SSOed(vec));<br>>=C2=A0 =
=C2=A0 =C2=A0vec.pop_back();=C2=A0 // must not reallocate the vector<br>>=
;=C2=A0 =C2=A0 =C2=A0assert(vec.size() =3D=3D 4 && vec.capacity() &=
gt;=3D 5 && !is_SSOed(vec));<br>>=C2=A0 =C2=A0 =C2=A0vec.pop_bac=
k();=C2=A0 // must not reallocate the vector<br>>=C2=A0 =C2=A0 =C2=A0ass=
ert(vec.size() =3D=3D 3 && vec.capacity() >=3D 5 && !is_=
SSOed(vec));<br>><br>> That is, (vec.size() <=3D decltype(vec)::SS=
O_capacity) does not necessarily<br>> imply is_SSOed(vec).<br>><br>&g=
t; Notice that std::vector<T> could simply be an alias for small_vect=
or<T,0> =E2=80=94<br>> that is, std::vector is exactly equivalent =
to a small_vector where the SSO<br>> buffer is big enough to store zero =
elements.<br>><br>>> The use-case would be things like<br>>>=
><br>>> > struct ChessPosition {<br>>> >=C2=A0 =C2=A0=
=C2=A0std::small_vector<ChessPiece,32> pieces;<br>>> > };<b=
r>>> ><br>>> > where ChessPosition's copy constructor=
and destructor get called *very*<br>>> > often, so copying the me=
mbers needs to be *very* fast. Inlining the<br>>> > data<br>>&g=
t; > (so no heap allocation needs to happen) is a big win.<br>>><b=
r>>> True, but this is still O(n).<br>>><br>><br>> Actual=
ly it's O(32), which is to say, O(1). The thing we're trying to<br>=
> optimize here is the constant factor: copying a std::vector of size 32=
<br>> requires calling (the equivalent of) malloc followed by memcpy, wh=
ereas<br>> copying a small_vector requires calling (the equivalent of) m=
emcpy alone.<br>><br>>> We'd like to be able to tune the N par=
ameter =E2=80=94 for example, if we use<br>>> > small_vector<Ch=
essPiece,16>, then early-game positions with more than<br>>> > =
16<br>>> > pieces will require a heap allocation (relatively slowe=
r), but *every*<br>>> > position will take half the RAM (shrinking=
our memory footprint and the<br>>> > expense of copy-constructing=
these things).<br>>><br>><br>> This is another example of tryi=
ng to shrink the constant factor in that<br></div></div>> O(1). Using sm=
all_vector (in my opinion) shouldn't change the *semantics*<br>> of =
my program; it should merely make my program run *faster*.<br>
<div class=3D"HOEnZb">
<div class=3D"h5">><br>> =E2=80=93Arthur<br>><br>> --<br>><b=
r>> ---<br>> You received this message because you are subscribed to =
the Google Groups<br>> "ISO C++ Standard - Future Proposals" g=
roup.<br>> To unsubscribe from this group and stop receiving emails from=
it, send an<br>> email to <a href=3D"mailto:std-proposals%2Bunsubscribe=
@isocpp.org">std-proposals+unsubscribe@isocpp.org</a>.<br>> To post to t=
his group, send email to <a href=3D"mailto:std-proposals@isocpp.org">std-pr=
oposals@isocpp.org</a>.<br>> Visit this group at<br>> <a href=3D"http=
://groups.google.com/a/isocpp.org/group/std-proposals/" target=3D"_blank">h=
ttp://groups.google.com/a/isocpp.org/group/std-proposals/</a>.<br>><br><=
/div></div></blockquote></div><br>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" 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 />
--001a113552c62a7c0705108a4ff0--
.