220 16709 article Path: news.gmane.org!not-for-mail From: "dgutson ." Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Configurable Small Object Optimization for vector and string Date: Wed, 4 Mar 2015 12:39:15 -0300 Lines: 272 Approved: news@gmane.org Message-ID: References: <65b9af57-f8fb-4b11-9da1-1f5fc504dacf@isocpp.org> <3248556.Isfy8bpADO@tjmaciei-mobl4> <7d0b7959-54e3-4b59-bb69-d91949509b6e@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a11421f2efa4c1405107840bd X-Trace: ger.gmane.org 1425483559 9454 80.91.229.3 (4 Mar 2015 15:39:19 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 4 Mar 2015 15:39:19 +0000 (UTC) To: std-proposals Original-X-From: std-proposals+bncBDE3NBMV6UFBBJGO3STQKGQEH4UZKUY@isocpp.org Wed Mar 04 16:39:19 2015 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-pd0-f199.google.com ([209.85.192.199]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1YTBOI-0006GU-Ku for gclcip-std-proposals@m.gmane.org; Wed, 04 Mar 2015 16:39:19 +0100 Original-Received: by pdno5 with SMTP id o5sf67072288pdn.3 for ; Wed, 04 Mar 2015 07:39:17 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:content-type:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=9l5zssh+weWLm2kCVjwsdOOSuUbQwx+ejdYB3jr1X0c=; b=THVczKnIkfkUU1L/u/bTf1A3MoRDQX7B6wHn7vBSe/l9x8pK3qniPu+JDUf6JGnFTj /U4ANzZmO1Y4Tddfkgn3+xsxZ0osxVUeM5QHG57dQ8A/mc33MC7pw6oZGoxZ/buMLDyo Tw8vXwdYfG6CAV1LHJPTEWVvuoHFoczuaOiEwNozzR6Lyzs9ZybVj83N3TX65FoSmNJJ JHF+RUwSQIObFwO4LA+ubCR98wyXnSDvjvuJ21gduZFi2V9ecxS+mz/VlCEVoxH0z+nU bkK6f3ptqiyq/XQWEu7EHzCC3kEdLXTDKzI16Ba1PEnsZKVoDtlycSdSJ/6bxKwg9VvN RPwg== X-Gm-Message-State: ALoCoQnnUOBxl7P5wAASNKx6077tQAog1q7M9QGzdG2uXpvgWziGwm5ma380qi6gCfsSRV25tXIt X-Received: by 10.66.144.69 with SMTP id sk5mr4505000pab.41.1425483557714; Wed, 04 Mar 2015 07:39:17 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.107.154.85 with SMTP id c82ls589391ioe.42.gmail; Wed, 04 Mar 2015 07:39:16 -0800 (PST) X-Received: by 10.50.107.7 with SMTP id gy7mr12085660igb.49.1425483555977; Wed, 04 Mar 2015 07:39:15 -0800 (PST) Original-Received: from mail-ig0-x229.google.com (mail-ig0-x229.google.com. [2607:f8b0:4001:c05::229]) by mx.google.com with ESMTPS id rt8si15424211igb.31.2015.03.04.07.39.15 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 04 Mar 2015 07:39:15 -0800 (PST) Received-SPF: pass (google.com: domain of danielgutson@gmail.com designates 2607:f8b0:4001:c05::229 as permitted sender) client-ip=2607:f8b0:4001:c05::229; Original-Received: by igkb16 with SMTP id b16so37534960igk.1 for ; Wed, 04 Mar 2015 07:39:15 -0800 (PST) X-Received: by 10.107.168.5 with SMTP id r5mr11872413ioe.87.1425483555816; Wed, 04 Mar 2015 07:39:15 -0800 (PST) Original-Received: by 10.36.56.70 with HTTP; Wed, 4 Mar 2015 07:39:15 -0800 (PST) Original-Received: by 10.36.56.70 with HTTP; Wed, 4 Mar 2015 07:39:15 -0800 (PST) In-Reply-To: X-Original-Sender: danielgutson@gmail.com X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of danielgutson@gmail.com designates 2607:f8b0:4001:c05::229 as permitted sender) smtp.mail=danielgutson@gmail.com; dkim=pass header.i=@gmail.com; dmarc=pass (p=NONE dis=NONE) header.from=gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:16709 Archived-At: --001a11421f2efa4c1405107840bd Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable El 04/03/2015 12:31, "David Rodr=C3=ADguez Ibeas" 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 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 is a different type from std::foo 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). >> >> >> In my opinion, "small_vector" would be a great addition to the standard library, but only if small_vector& and vector& 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 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 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, 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


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 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.
>
> 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...

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= ?

>
> =C2=A0 =C2=A0 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 wro= te:
>>>
>>> On Tuesday 03 March 2015 20:00:15 Matthew Fioravante wrote: >>> > Modern implementations are encouraged to implement the sm= all string
>>> > optimization (with implementation defined size) for std::= string, reasoning
>>> > that most strings tend to be small. While this may work v= ery well in the
>>> > general case, it can be either inadequate or a pessimizat= ion in other cases.
>>
>> [...]=C2=A0
>>>
>>> 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 cur= rent
>>> basic_string. Instead, be explicit that this is a different ty= pe and define the
>>> SmallSize default value to be sizeof(std::basic_string<Char= T>).
>>
>>
>> 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.
>>
>> The use-case would be things like
>>
>> struct ChessPosition {
>> =C2=A0 =C2=A0 std::small_vector<ChessPiece,32> pieces;
>> };
>>
>> 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.
>>
>> 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.
>>
>> 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).
>>
>> 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."= ;
>>
>> 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-pr= oposals/.
>
>
> --
>
> ---
> You received this message because you are subscribed to the Google Gro= ups "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-propos= als/.

--

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