220 31165 article Path: news.gmane.org!.POSTED!not-for-mail From: Nicol Bolas Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Domains of specialized `vector` variance Date: Sun, 26 Feb 2017 08:08:41 -0800 (PST) Lines: 275 Approved: news@gmane.org Message-ID: References: <38052307-8ef9-4d41-b902-826f56630c10@isocpp.org> <3fcee1aa-2092-20c0-ee9c-7b81f1f81d0f@gmail.com> <81ec3e8e-c380-416d-8f02-6f3c5180728f@isocpp.org> <8f092e67-d3d2-b1c2-a20a-6b4bcfd9417c@gmail.com> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_4524_329792716.1488125321067" X-Trace: blaine.gmane.org 1488125329 30479 195.159.176.226 (26 Feb 2017 16:08:49 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 26 Feb 2017 16:08:49 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCEKFTV6ZUMBBCP3ZPCQKGQEMSHYSII@isocpp.org Sun Feb 26 17:08:42 2017 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-it0-f69.google.com ([209.85.214.69]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ci1NE-0006pu-Rh for gclcip-std-proposals@m.gmane.org; Sun, 26 Feb 2017 17:08:37 +0100 Original-Received: by mail-it0-f69.google.com with SMTP id d9sf58839009itc.4 for ; Sun, 26 Feb 2017 08:08:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=rC/yRxSaz2SkahYJCFGOmgD9sVwyC2PqTRpiZkKx8C8=; b=XrTOQPLMWE9nSesxUXhRv0+rS9KB2wqMaSJ2sC1amztfqTX6iDra4o/FUlaPrdfVPD yIOnqPVbS7POfBERby78/IcTlqG1ZvYYOf6R1Zs2WxwTwCE/E5qVQtTzCUDAoN/nYSlJ 0Dy4luevoyorVPtTdyT4vnA1OYe1OHCCmgFihfHkJdvus3e2XVU4jaDlx5PitmefLdbK Om7s607Syp715YRzw8H6d0yp7jwDQwK0+rXGf1EhzZf7PVlI0104mZnzZXTYASc5HNna OIARzCI8t+xZDKval1+WdUkTvGKC1IRjV2APclKKEiN07FML3fuZs2xWWHpEiIHtPL7H 7JyA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=rC/yRxSaz2SkahYJCFGOmgD9sVwyC2PqTRpiZkKx8C8=; b=XCm4dQYETMvi7aARz4lD+r7q8mIee4YGQkY36JaB+Sm/6Dnsy9Rxi1npbTistrTjSr LLxj3S3XO0oEYPijYJAMMbrTyNQsy9d6DhlGASut7S4UawSZmtqfe57TfFzyUfl+BZbm Y8jNRqlEhPWCeRk3woSmq8NdJu8jgp8hY//snpxMyDZXAAI3lXKIQ3yNVw0E7O+q/zSO a+k7arkSaeqjj/7ghIZb29LQATNH+Rilv69h14bz2hk6MdcCWkzLrWiwf8389gtVw9N/ L0juaEU5cG0aph8MkSv/ge2o/G6nKGzGgZs6k52ziCTLnNJ9puKdJ34xgZGnXlaj76mb qaUQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:x-original-sender:reply-to:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=rC/yRxSaz2SkahYJCFGOmgD9sVwyC2PqTRpiZkKx8C8=; b=lnOhazlSQ0pmyyw8UPSd9VHWfSslo+4YS1pN4vWtq+iaIBohvFt5y6aECiB6kbwuhB afcZ0eQuvLfU2uh89Z8QmEFcuPYryq7cBP7r3PapEP0fgO4A+sfkxdWoX1AR8qzH0cMV hontUil3zXSVh95kcbi9KYj1mJ6xncfA//MYalX1zgAqOQdQRFlEMB2rJUPJRY8kRBLE y05OVHwQQ/eKWYaoU3RO1Xemw4rWfNL0KsuCA4LZr2UlzGZQhSZIDNeJjlORBa3IY0GP mp9QT3MAS5gwPTZ+OSWHq7xIikATHc0VKowTJw35Za46WDmFCfkocwbiNRHhYNM0HEXi HH0w== X-Gm-Message-State: AMke39kVgdBcUWWDfXdQD6b4r1H/9k8pie99uISlAjC+SRn5gTKNBave7j6nw0jZb5VseQ== X-Received: by 10.36.122.149 with SMTP id a143mr3094573itc.37.1488125322643; Sun, 26 Feb 2017 08:08:42 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.157.8.210 with SMTP id 76ls10004449otf.33.gmail; Sun, 26 Feb 2017 08:08:41 -0800 (PST) X-Received: by 10.157.5.247 with SMTP id 110mr771434otd.14.1488125321800; Sun, 26 Feb 2017 08:08:41 -0800 (PST) In-Reply-To: <8f092e67-d3d2-b1c2-a20a-6b4bcfd9417c@gmail.com> X-Original-Sender: jmckesson@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:31165 Archived-At: ------=_Part_4524_329792716.1488125321067 Content-Type: multipart/alternative; boundary="----=_Part_4525_1493802673.1488125321067" ------=_Part_4525_1493802673.1488125321067 Content-Type: text/plain; charset=UTF-8 On Sunday, February 26, 2017 at 10:24:19 AM UTC-5, Andrey Semashev wrote: > > On 02/26/17 17:44, Nicol Bolas wrote: > > On Sunday, February 26, 2017 at 7:24:48 AM UTC-5, Andrey Semashev wrote: > > > > Personally, I don't see the benefit of unification of various > > flavors of > > vector under the common name. Having specialized names, actually, > makes > > more sense for code readability and searchability. I'm sure, it will > > also be better for compile times as there's no need for > metaprogramming > > layer for sorting out policy template parameters. > > > > The benefit of putting them under a common name is not to have a common > > name. It's to allow users to mix and match behavior as they see fit, > > with /guaranteed/ interoperability. > > > > Here are all of the possibilities that someone might genuinely want: > > > > static_vector: compile-time maximum size, but allocates memory up to > > that size. > > static_small_vector: compile-time maximum size with an internal buffer > > store. > > dynamic_vector: runtime maximum size. > > dynamic_small_vector: runtime maximum size with an internal buffer > store. > > vector: grows as needed. > > small_vector: grows as needed, with an internal buffer store. > > > > Each of those combinations has just as much justification as the others. > > An allocating `static_vector` really is useful in some cases; you want > > it to allocate, but you don't want it to grow beyond that allocation. A > > `static_small_vector` that stores its data internally is also useful; it > > does no allocations. For the dynamic case, having small buffer > > optimization is useful, but it's also useful to have guarantees of > > pointer stability on move operations. And vector vs. small_vector is > > similarly well understood. > > > > So it is clear that there is a need for each and every such combination. > > And thus, we should have each and every one of those classes. But what > > happens if we add another domain to that, like `stability` from > > `boost:stable_vector`? Now all of a sudden, we need /twelve/ classes, > > not 6. Why shouldn't someone be able to have a `static_stable_vector`? > > Why not a `dynamic_small_stable_vector`? > > Thing is, some combinations are not possible or practical. For instance, > `stable_vector` allocates each element separately, which would prohibit > using a local storage for it. Well, you could preallocate storage for > max number of elements *and* the table of pointers to them, but that's a > different amount of storage than a different kind of `vector` would > require, which means the user's code can't predict the amount of storage > needed. > By asking for a stable vector of any sort, you explicitly requested the class to take up more space than a non-stable one would. So adding small storage on top of that wouldn't change that fact. You gave up the assumption of `sizeof(T)*capacity` when you asked for stability. Besides, the point of small storage is not to be able to predict exactly how big that vector instance will be (the standard won't guarantee that anyway). It's to prevent dynamic allocation outside of circumstances that would be exceptional for your needs. And internally, these vectors may be very very different - so different > in fact that the common name and interface would only complicate the > implementation by having to dispatch between the different backends. > This also means that anyone who needs only one of those backends must > bring in the other ones as well as dependencies. > > > See the problem? The multiplicative explosion of vectors makes this > > unworkable. This leaves us either with lots and lots of vector classes, > > or we only provide the lowest common denominator: `vector`, > > `small_vector`, `static_vector`, `dynamic_vector` and `stable_vector`. > > No combinations of any of those features with each other. > > Well, I'm not convinced that every combination would be useful in > practice, and that the problem you describe needs solving. > > I guess, if you limit your proposal to only allocation strategies, the > ones from your list above, it would make more sense. But then I would > rather see a different design based on allocators, something along these > lines: > > template< typename T, typename... Allocators = std::allocator< T > > > class multistorage_vector; > > template< typename T, typename Allocator = std::allocator< T > > > using vector = multistorage_vector< T, Allocator >; > > The `multistorage_vector` container would attempt to use storage > provided by the first allocator in the `Allocators` list that succeeds. > This way one would be able to specify first an allocator with a static > local buffer and then an allocator that uses heap. > That would needlessly bloat the `vector`. After all, the `vector` still needs its own 3 pointers. So it would have to have its own storage plus the storage of the allocator. -- 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. To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/b2c5567a-5ece-486c-855b-156caad4b0fc%40isocpp.org. ------=_Part_4525_1493802673.1488125321067 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On Sunday, February 26, 2017 at 10:24:19 AM UTC-5, Andrey = Semashev wrote:
On 02/26/17 17:= 44, Nicol Bolas wrote:
> On Sunday, February 26, 2017 at 7:24:48 AM UTC-5, Andrey Semashev = wrote:
>
> =C2=A0 =C2=A0 Personally, I don't see the benefit of unificati= on of various
> =C2=A0 =C2=A0 flavors of
> =C2=A0 =C2=A0 vector under the common name. Having specialized nam= es, actually, makes
> =C2=A0 =C2=A0 more sense for code readability and searchability. I= 'm sure, it will
> =C2=A0 =C2=A0 also be better for compile times as there's no n= eed for metaprogramming
> =C2=A0 =C2=A0 layer for sorting out policy template parameters.
>
> The benefit of putting them under a common name is not to have a c= ommon
> name. It's to allow users to mix and match behavior as they se= e fit,
> with /guaranteed/ interoperability.
>
> Here are all of the possibilities that someone might genuinely wan= t:
>
> static_vector: compile-time maximum size, but allocates memory up = to
> that size.
> static_small_vector: compile-time maximum size with an internal bu= ffer
> store.
> dynamic_vector: runtime maximum size.
> dynamic_small_vector: runtime maximum size with an internal buffer= store.
> vector: grows as needed.
> small_vector: grows as needed, with an internal buffer store.
>
> Each of those combinations has just as much justification as the o= thers.
> An allocating `static_vector` really is useful in some cases; you = want
> it to allocate, but you don't want it to grow beyond that allo= cation. A
> `static_small_vector` that stores its data internally is also usef= ul; it
> does no allocations. For the dynamic case, having small buffer
> optimization is useful, but it's also useful to have guarantee= s of
> pointer stability on move operations. And vector vs. small_vector = is
> similarly well understood.
>
> So it is clear that there is a need for each and every such combin= ation.
> And thus, we should have each and every one of those classes. But = what
> happens if we add another domain to that, like `stability` from
> `boost:stable_vector`? Now all of a sudden, we need /twelve/ class= es,
> not 6. Why shouldn't someone be able to have a `static_stable_= vector`?
> Why not a `dynamic_small_stable_vector`?

Thing is, some combinations are not possible or practical. For instance= ,=20
`stable_vector` allocates each element separately, which would prohibit= =20
using a local storage for it. Well, you could preallocate storage for= =20
max number of elements *and* the table of pointers to them, but that= 9;s a=20
different amount of storage than a different kind of `vector` would=20
require, which means the user's code can't predict the amount o= f storage=20
needed.

By asking for a stable vector of any s= ort, you explicitly requested the class to take up more space than a non-st= able one would. So adding small storage on top of that wouldn't change = that fact. You gave up the assumption of `sizeof(T)*capacity` when you aske= d for stability.

Besides, the point of small storage is not to be ab= le to predict exactly how big that vector instance will be (the standard wo= n't guarantee that anyway). It's to prevent dynamic allocation outs= ide of circumstances that would be exceptional for your needs.

And internally, these vectors= may be very very different - so different=20
in fact that the common name and interface would only complicate the=20
implementation by having to dispatch between the different backends.=20
This also means that anyone who needs only one of those backends must= =20
bring in the other ones as well as dependencies.
=C2=A0
> See the= problem? The multiplicative explosion of vectors makes this
> unworkable. This leaves us either with lots and lots of vector cla= sses,
> or we only provide the lowest common denominator: `vector`,
> `small_vector`, `static_vector`, `dynamic_vector` and `stable_vect= or`.
> No combinations of any of those features with each other.

Well, I'm not convinced that every combination would be useful in= =20
practice, and that the problem you describe needs solving.

I guess, if you limit your proposal to only allocation strategies, the= =20
ones from your list above, it would make more sense. But then I would= =20
rather see a different design based on allocators, something along thes= e=20
lines:

=C2=A0 =C2=A0template< typename T, typename... Allocators =3D std::a= llocator< T > >
=C2=A0 =C2=A0class multistorage_vector;

=C2=A0 =C2=A0template< typename T, typename Allocator =3D std::alloc= ator< T > >
=C2=A0 =C2=A0using vector =3D multistorage_vector< T, Allocator >= ;

The `multistorage_vector` container would attempt to use storage=20
provided by the first allocator in the `Allocators` list that succeeds.= =20
This way one would be able to specify first an allocator with a static= =20
local buffer and then an allocator that uses heap.

That would needlessly bloat the `vector`. After a= ll, the `vector` still needs its own 3 pointers. So it would have to have i= ts own storage plus the storage of the allocator.

--
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.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/b2c5567a-5ece-486c-855b-156caad4b0fc= %40isocpp.org.
------=_Part_4525_1493802673.1488125321067-- ------=_Part_4524_329792716.1488125321067-- .