220 32104 <92026194-86f7-4e1d-94e5-d5c0f1cfd602@isocpp.org> article Path: news.gmane.org!.POSTED!not-for-mail From: Nicol Bolas Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Add all useful array types to the standard library Date: Mon, 17 Apr 2017 13:04:59 -0700 (PDT) Lines: 383 Approved: news@gmane.org Message-ID: <92026194-86f7-4e1d-94e5-d5c0f1cfd602@isocpp.org> References: <642f3c7d-c20f-4dd2-bfd2-b0c9c326f9b5@isocpp.org> <59238645-c3d5-4282-86d8-b4044731f3cf@isocpp.org> <20170414111554.5148754.67724.28881@gmail.com> <12437571.3omJd9UHM2@tjmaciei-mobl1> <4b989332-5ff1-4321-a276-aff41d87a140@isocpp.org> <5125f9e2-161d-4a3f-9ff4-66a94db0fe73@isocpp.org> <6492fd26-fea9-4765-a173-599ec8899647@isocpp.org> <401585fc-6648-4dcd-b3ba-25e135833d85@isocpp.org> <31af4b2d-2481-419e-856b-5363635d6a7a@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_5549_1456587966.1492459499890" X-Trace: blaine.gmane.org 1492459504 15999 195.159.176.226 (17 Apr 2017 20:05:04 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 17 Apr 2017 20:05:04 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCEKFTV6ZUMBB3F72TDQKGQEF7II4GI@isocpp.org Mon Apr 17 22:04:58 2017 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-qt0-f197.google.com ([209.85.216.197]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1d0CtL-0003zU-QV for gclcip-std-proposals@m.gmane.org; Mon, 17 Apr 2017 22:04:56 +0200 Original-Received: by mail-qt0-f197.google.com with SMTP id 7sf43877806qtp.8 for ; Mon, 17 Apr 2017 13:05:01 -0700 (PDT) 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=1apjZuJL5ZOB7LfvJbBQDlarkXiwaOyQro5uIIlSzO8=; b=DZBe/i7j9Dbw/1yxXCfWHZiVoKk2Yu0Rrn52++TRux2PX0xIkUuTuJ7n0uoISTy4Km bZGCLJbBFKQV9ki/EKYdYLoGyljelfATq2tWui/U5SaScNuBrXP7k2R0RvX8MbqYWwTS bqQAeRkNF/NaMUJYupDNmbfjJYpTSHNam5ONgrwzPldOtofMTtTZx3VIktFCkDpigKFo 7dQl1UqOmuvB9hRKWi8KdZfFsbU5bDGwmV28/LGu+NBa29988VpRhhzwMAKqOpTMmsja quLZ3TGY+K8sUFas/XAaWTnHldpnbPlQTwAlNR4f0jnJe51X51fTZOYoe6834Qmlivpb EigQ== 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=1apjZuJL5ZOB7LfvJbBQDlarkXiwaOyQro5uIIlSzO8=; b=MF7XZWuv/6mCJjfiJ3DMb6emKWqEXF7qUvSehjiTGWScWB+PUqDAohEJ883qD7QK91 ZpxuzKF3+dI9HoQc/DReOagpXd6jkuIkxSVLVIFU5QGipxl6cPqjDFcfhbNd6RGnxg4T rCmokBDoa7yQsy16R7eeBxufZjNPVAkTZJgCNO4hzPYoK2rhA1YC98PtVfIyXVByq40U coGlWSXPPKrhZihtLCMRMblM3UEqSwkqmBVgeurnC7lsdTenvyEl0n55MWqC+GjnltN0 yBLGqjH+7lvLxygflD1MnLNGhwUlEC1ZhxLZhzxesC9V0QCvqZUy5vIMDCBPzHzVt42w 1nNQ== 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=1apjZuJL5ZOB7LfvJbBQDlarkXiwaOyQro5uIIlSzO8=; b=IIDxzrWV9Ukpym5tpOlmstL8lpQmElD1n5kdmighdna6OQj8bmBAT7rWdOSVnIn77t p0SnB52Ky0uBKx078i6KlDrPoRZePey4ryqABhs/uoSzHmbQIiF55EUB9diXu0cKH7mj 8cR+YTPS+8m72MNnKZyzN5cWsUeJBCO8u0HoUaRnI5uKpEKgViE65J9JO4gAKWH+BxJJ n3rd0MFS9Axb7FTvvigMmLvI8RYz3fj6Kqf0KCc92Kin4cwrMPv2+SkY2KrUeDxKc9Aj HPE16MP6+/OUTqme4ZNFCuPWxf7y9lFCFiuelEi8ydCJeh45dxOCbp92aDWyGZdTNP5N ggkw== X-Gm-Message-State: AN3rC/7/UfAt+nl9uKG0JBC2JNMHwfTmTFlF4rj+f0GxiePP/2qBitkL GYGv/OAgegM1/w== X-Received: by 10.200.36.226 with SMTP id t31mr5822430qtt.2.1492459501320; Mon, 17 Apr 2017 13:05:01 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.157.46.9 with SMTP id q9ls9741044otb.2.gmail; Mon, 17 Apr 2017 13:05:00 -0700 (PDT) X-Received: by 10.157.15.205 with SMTP id m13mr3103otd.18.1492459500411; Mon, 17 Apr 2017 13:05:00 -0700 (PDT) In-Reply-To: <31af4b2d-2481-419e-856b-5363635d6a7a@isocpp.org> 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:32104 Archived-At: ------=_Part_5549_1456587966.1492459499890 Content-Type: multipart/alternative; boundary="----=_Part_5550_1891250717.1492459499891" ------=_Part_5550_1891250717.1492459499891 Content-Type: text/plain; charset=UTF-8 On Monday, April 17, 2017 at 2:28:11 PM UTC-4, Matthew Fioravante wrote: > > On Monday, April 17, 2017 at 12:47:01 PM UTC-5, Nicol Bolas wrote: >> >> On Monday, April 17, 2017 at 12:51:15 PM UTC-4, Matthew Fioravante wrote: >>> >>> As for configuration options, here's all I can think of at the moment: >>> >> >> There is a very great deal of overlap in that list. As well as >> contradictory dimensions: you can't have a static capacity stored in the >> object with dynamic resizing that's allocated. >> > > Sure, this is an off the cuff list I produced in 2 minutes. Certainly > there are various illegal combinations, contradictions, and possibly other > options I've left out. But hopefully it gives a starting point for fleshing > out a real interface. > > For example, I just realized that growth_factor should actually just be a > function object instead of a size or ratio. Sometimes you really want an > additive linear growth factor. > > >> The parameterization system should be designed to avoid such >> contradictory options, rather than simply declaring them illegal. >> > > At a minimum, I would suggest using static_asserts in omni_vec to detect > and complain about all illegal combinations with helpful diagnostics. > Obviously if the interface is designed well to lead you avoid mistakes all > the better. > > >> >> Also, there are several options of... dubious merit. Control over >> `size_type`, for example. >> > > This is not dubious at all. I can give you 2 solid use cases, both of > which I've done in the past. > > On 64 bit platforms, a vector using size_t is 24 bytes, whereas vector > using uint32_t is only 16 bytes. Those 8 bytes can be valuable if you have > several of these packed tightly in a single cache line in hot memory. For a > lot of use cases, we'll never need more than 4 billions elements in a > vector. > You assume that `size_type` is actually stored in the `vector` to contain the size. Many `vector` implementations simply contain 3 pointers, computing `size` and `capacity` as needed. So controlling `size_type` will not help you on such implementations. Signed size_type also might let me finally start using gcc's -Wconversion > without getting a ton of false positives. I don't use -Wconversion because > all of the required casts around STL containers can easily cause bugs of > their own. Signed size() might also enable optimizations in some cases > because the compiler can assume signed arithmetic sourced from a call to > size() can never overflow. > And what exactly would control over `size_type` do for that problem *in general*? Because it won't change the fact that *every other* container uses an unsigned `size_type`. Nor will it change the fact that `span` will use an unsigned `size_type`. Nor will it change the fact that the unparameterized `vector` will use an unsigned `size_type`. Nor will it change the fact that someone else can pass you a `vector` that uses an unsigned `size_type`. Also, `container::size_type` is *required* by the standard to be an unsigned integer, big enough to store any non-negative value of `container::difference_type`. If you have a problem with the way containers/ranges return their sizes, then that's a problem that needs to be handled at the specification level, not in a specific container class. And having a sentinel value rather than a genuine size; that's just begging >> for someone to break the container. Even `basic_string`, a type designed >> specifically for such a use case, doesn't actually use the NUL character to >> determine the string's size. >> > > I've used the sentinel in production code as well. > I never said that nobody uses such things in production code. I said that it's not something the standard library should support. It's just too fragile of a container for the standard library. Again I don't need to store a size variable anywhere, saving valuable cache > space. The most common use case for this is when you have a list of > pointers to callbacks to be iterated through. All of the pointers except > the last one are null. > > This makes size() and push_back() slow, but in my use case it was a > situation where I set everything up on startup and then need to iterate the > list over and over again in the hotpath. I don't give a damn about a bit > slower slow setup (not even measurable in real tests), when it buys me the > fastest possible iteration loop. > > This optimizes the hell out of iteration. After optimization its > essentially this: > for(T**p = v.data(); *p != nullptr; ++p) { > doSomething(*p); > } > > Which you can do right now by manually putting a NULL pointer at the end of the list. This sounds like something best handled by some kind of iterator/range adapter, not by changing the container itself. Indeed, by making it an adapter rather than part of the class, it can now be used for lots of tasks, the equivalent of doing a loop until you reach the value that `find_if` would return. The vector itself only stores a single pointer and is only 8 bytes in size. > So you create this incredibly fragile container... just to save 16 bytes. Capacity can either be a function of size (size % N, next power of 2, > etc..) or a static compile time upper bound. > Um, if the capacity is a function of the size, then the capacity must change whenever the size does. Which makes the capacity functionally useless; it will have to reallocate on any insertion or removal. Now I agree that this is easy to use wrong in the general case. But again, > omni_vec is a toolbox that doesn't always have to stand on its own in the > wild. I can create a sentinel based omni_vec inside and then further wrap > it in a safer interface. > > I think the decision for string was more about 2 things: (1) allowing for > strings with embedded nulls (mandatory for binary string data) and (2) > making size() O(1). For string data, this is the right trade-off because in > the context of string, those are 2 very important properties to have. For > some other generic situations, they may not be necessary. > > One might also want to make a C style null terminated string type which > doesn't store the size, and they could easily start out by using > omni_vec to define the storage policy and build a semantic > string wrapper on-top. > > >> Similarly, no form of `vector` should support "Bit Storage and proxy >> iterators". `vector` is supposed to mean "contiguous storage of `T`", >> and every form of `vector` ought to provide that. >> > > I think my original idea of using some kind of type T to enable this is > wrong, as its similar to vector. Certaintly though it could make > sense to add a traits parameter to enable bitset behavior, with a > static_assert() that T is bool. > > Iterating over bits is fundamentally different than iterating over T. I > agree that it is a bit uncomfortable how it crosses the turf of vector a > bitset. However, if we added some facility to omni_vec, it means we get all > the storage foundations for all possible bitsets for free. > > Bitsets operate exactly like vectors and arrays. > No, they do not. A `vector` is a contiguous container of `T`s, which can be iterated over and accessed by pointers. A bitset isn't that. So no, they do not "operate *exactly*" like `vector`. You can use a `vector` to *create* a bitset, but that's different from a bitset actually *being* a specialization of `vector`. I could even imagine a new `bitset` class that takes the same parameters as `omni_vector`, forwarding them to an internal `vector` implementation. > The only difference is that bits need special handling because they can't > be represented with a type T directly. > > Another option could be an omni_bitset, which uses the exact same traits > as omni_vec but has bitset semantics. > > I guess the idea I'm envisioning here is a completely flexible array-like > storage backend for any possible kind of array like thing you would want. > Simple inheritance/composition can be used to add additional semantic > layers as needed (strings, bitsets, circular buffers, etc..). > You can use `vector` in an implementation of bitset as it currently stands; you don't need to shove bitset functionality *into* `vector` to do that. You'll just have to write a bit more code. And that "bit more code" is not the hard code of implementing `vector`. -- 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/92026194-86f7-4e1d-94e5-d5c0f1cfd602%40isocpp.org. ------=_Part_5550_1891250717.1492459499891 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On Monday, April 17, 2017 at 2:28:11 PM UTC-4, Matthew Fio= ravante wrote:
On Monday, April 17, 2017 at 12:47:01 PM UTC-5, Nicol Bolas wrote:
On Monday, April 17, 2017 = at 12:51:15 PM UTC-4, Matthew Fioravante wrote:
As for configuration options, here's all I= can think of at the moment:

There is a very gre= at deal of overlap in that list. As well as contradictory dimensions: you c= an't have a static capacity stored in the object with dynamic resizing = that's allocated.

Sure, thi= s is an off the cuff list I produced in 2 minutes. Certainly there are vari= ous illegal combinations, contradictions, and possibly other options I'= ve left out. But hopefully it gives a starting point for fleshing out a rea= l interface.

For example, I just realized that gro= wth_factor should actually just be a function object instead of a size or r= atio. Sometimes you really want an additive linear growth factor.
=C2=A0
= The parameterization system should be designed to avoid such contradictory = options, rather than simply declaring them illegal.

At a minimum, I would suggest using static_asserts= in omni_vec to detect and complain about all illegal combinations with hel= pful diagnostics. Obviously if the interface is designed well to lead you a= void mistakes all the better.
=C2=A0

Also, there are several options = of... dubious merit. Control over `size_type`, for example.

This is not dubious at all. I can give you 2 = solid use cases, both of which I've done in the past.

On 64 bit platforms, a vector using size_t is 24 bytes, whereas vec= tor using uint32_t is only 16 bytes. Those 8 bytes can be valuable if you h= ave several of these packed tightly in a single cache line in hot memory. F= or a lot of use cases, we'll never need more than 4 billions elements i= n a vector.

You assume that `size_type` is= actually stored in the `vector` to contain the size. Many `vector` impleme= ntations simply contain 3 pointers, computing `size` and `capacity` as need= ed.

So controlling `size_type` will not help you on such implementat= ions.

Signed size_type also might let me finally start usin= g gcc's -Wconversion without getting a ton of false positives. I don= 9;t use -Wconversion because all of the required casts around STL container= s can easily cause bugs of their own. Signed size() might also enable optim= izations in some cases because the compiler can assume signed arithmetic so= urced from a call to size() can never overflow.

And what exactly would control over `size_type` do for that problem <= i>in general? Because it won't change the fact that every other<= /i> container uses an unsigned `size_type`. Nor will it change the fact tha= t `span<T>` will use an unsigned `size_type`. Nor will it change the = fact that the unparameterized `vector` will use an unsigned `size_type`. No= r will it change the fact that someone else can pass you a `vector` that us= es an unsigned `size_type`.

Also, `container::size_type` is requi= red by the standard to be an unsigned integer, big enough to store any = non-negative value of `container::difference_type`. If you have a problem w= ith the way containers/ranges return their sizes, then that's a problem that needs to be handled at the specification le= vel, not in a specific container class.

And having a sentinel value rather than a genuin= e size; that's just begging for someone to break the container. Even `b= asic_string`, a type designed specifically for such a use case, doesn't= actually use the NUL character to determine the string's size.

I've used the sentinel in prod= uction code as well.

I never said that nob= ody uses such things in production code. I said that it's not something= the standard library should support. It's just too fragile of a contai= ner for the standard library.

Again I don't need to store a size v= ariable anywhere, saving valuable cache space. The most common use case for= this is when you have a list of pointers to callbacks to be iterated throu= gh. All of the pointers except the last one are null.

<= div>This makes size() and push_back() slow, but in my use case it was a sit= uation where I set everything up on startup and then need to iterate the li= st over and over again in the hotpath. I don't give a damn about a bit = slower slow setup (not even measurable in real tests), when it buys me the = fastest possible iteration loop.

This optimizes th= e hell out of iteration. After optimization its essentially this:
for(T**p =3D v.data(); *p !=3D nullptr; ++p) = {
=C2=A0 doSomething(*p);
}

=

Which you can do right now by manually putting a NULL pointer at t= he end of the list. This sounds like something best handled by some kind of= iterator/range adapter, not by changing the container itself. Indeed, by m= aking it an adapter rather than part of the class, it can now be used for l= ots of tasks, the equivalent of doing a loop until you reach the value that= `find_if` would return.

The vector itself only stores a single pointe= r and is only 8 bytes in size.

So you crea= te this incredibly fragile container... just to save 16 bytes.

<= div>Capacity can either be a function of size (size % N, next power of 2, e= tc..) or a static compile time upper bound.
Um, if the capacity is a function of the size, then the capacity must cha= nge whenever the size does. Which makes the capacity functionally useless; = it will have to reallocate on any insertion or removal.

Now= I agree that this is easy to use wrong in the general case. But again, omn= i_vec is a toolbox that doesn't always have to stand on its own in the = wild. I can create a sentinel based omni_vec inside and then further wrap i= t in a safer interface.

I think the decision for s= tring was more about 2 things: (1) allowing for strings with embedded nulls= (mandatory for binary string data) and (2) making size() O(1). For string = data, this is the right trade-off because in the context of string, those a= re 2 very important properties to have. For some other generic situations, = they may not be necessary.

One might also want to = make a C style null terminated string type which doesn't store the size= , and they could easily start out by using omni_vec<char,Traits> to d= efine the storage policy and build a semantic string wrapper on-top.
<= div>=C2=A0
Similarly, no form of `vector` should support "Bit Storage and prox= y iterators". `vector<T>` is supposed to mean "contiguous s= torage of `T`", and every form of `vector` ought to provide that.
<= /div>

I think my original idea of usi= ng some kind of type T to enable this is wrong, as its similar to vector<= ;bool>. Certaintly though it could make sense to add a traits parameter = to enable bitset behavior, with a static_assert() that T is bool.

Iterating over bits is fundamentally different than iterati= ng over T. I agree that it is a bit uncomfortable how it crosses the turf o= f vector a bitset. However, if we added some facility to omni_vec, it means= we get all the storage foundations for all possible bitsets for free.

Bitsets operate exactly like vectors and arrays.
=

No, they do not. A `vector<T>` is a conti= guous container of `T`s, which can be iterated over and accessed by pointer= s. A bitset isn't that. So no, they do not "operate exactly= " like `vector`.

You can use a `vector` to create a bits= et, but that's different from a bitset actually being a speciali= zation of `vector`. I could even imagine a new `bitset` class that takes th= e same parameters as `omni_vector`, forwarding them to an internal `vector`= implementation.
=C2=A0
The only difference is that bits need special handl= ing because they can't be represented with a type T directly.

Another option could be an omni_bitset, which uses the exac= t same traits as omni_vec but has bitset semantics.

I guess the idea I'm envisioning here is a completely flexible array-= like storage backend for any possible kind of array like thing you would wa= nt. Simple inheritance/composition can be used to add additional semantic l= ayers as needed (strings, bitsets, circular buffers, etc..).

You can use `vector` in an implementation of bitset as i= t currently stands; you don't need to shove bitset functionality int= o `vector` to do that. You'll just have to write a bit more code.
And that "bit more code" is not the hard code of implementi= ng `vector`.

--
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/92026194-86f7-4e1d-94e5-d5c0f1cfd602= %40isocpp.org.
------=_Part_5550_1891250717.1492459499891-- ------=_Part_5549_1456587966.1492459499890-- .