220 11426 article Path: news.gmane.org!not-for-mail From: =?UTF-8?Q?=C5=81ukasz_Mendakiewicz?= Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Comments on n3976 (array_view) Date: Sun, 15 Jun 2014 21:38:24 -0700 (PDT) Lines: 923 Approved: news@gmane.org Message-ID: References: <81f95afc-7a67-45cd-950c-433528b2b8db@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_519_6490396.1402893504503" X-Trace: ger.gmane.org 1402893515 1142 80.91.229.3 (16 Jun 2014 04:38:35 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 16 Jun 2014 04:38:35 +0000 (UTC) To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBC2NDJ47YMLBBQXJ7GOAKGQEAY4XYRQ@isocpp.org Mon Jun 16 06:38:29 2014 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yh0-f71.google.com ([209.85.213.71]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1WwOge-0000li-BH for gclcip-std-proposals@m.gmane.org; Mon, 16 Jun 2014 06:38:28 +0200 Original-Received: by mail-yh0-f71.google.com with SMTP id t59sf24539141yho.6 for ; Sun, 15 Jun 2014 21:38:27 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; 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:list-post:list-help:list-archive :list-subscribe:list-unsubscribe:content-type; bh=YncwlApW5FzA82Sa6eTo27V2KHvtMg76aQJi4vLUCu8=; b=FgZ9/CuRfKWvJ3GYXQPgULAoThQl7KhFNQf3nl5fIWpq3Ys+wZDIdG1HKW+LuGHx3W uszy1C28W3gqutn2CNfgbgqyAwxBqZHYIa9+zSqDVKERJgqORGU1c4gN1JuRbmOolhkL Ln4YRyDmCrMiwlOtcoEqWTE4vElheCm4xTFVSSevmQrapDmGD/OMNBtOILmYb3XhuzSz IzOTgA/QlNLkTovhEcEIfGvvj2CMLrb30IKoG4f+c9Y6z+jd55nKrHSgmVz1tRqSCIJg OA5yluzrIHo3lJeQs3SkZ2z9av4FYs7yVUiuv/sLh5hh8lO03vH+zOnMYbpeCtzP/VUB jNaA== X-Gm-Message-State: ALoCoQlmD1K7lWNLuo2EFy+K1s12SNeRegv6FRcuacnVcQDXCDEWuu38W4uvHCmr0P7c1DDpsIsz X-Received: by 10.58.41.33 with SMTP id c1mr281884vel.2.1402893507374; Sun, 15 Jun 2014 21:38:27 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.50.148.65 with SMTP id tq1ls763672igb.31.gmail; Sun, 15 Jun 2014 21:38:26 -0700 (PDT) X-Received: by 10.50.164.129 with SMTP id yq1mr395223igb.15.1402893506317; Sun, 15 Jun 2014 21:38:26 -0700 (PDT) In-Reply-To: <81f95afc-7a67-45cd-950c-433528b2b8db@isocpp.org> X-Original-Sender: l.mendakiewicz@live.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:11426 Archived-At: ------=_Part_519_6490396.1402893504503 Content-Type: text/plain; charset=UTF-8 Thank you Jeffrey for adding me on the thread and for your initial response -- which I almost universally agree with. Jeremy, thank you for your detailed feedback. First, I believe that most of the disagreement stems from the approach to the proposal. You've commented that "it doesn't make sense to standardize a partial solution; better to work out a good, complete interface outside the standard". This is opposite to the "crawl, walk, run" philosophy we have taken when writing this document up. We recognize that we have only explored some parts of the design space, because as you have rightly observed our experience is limited to C++ AMP, which constitutes only a specific data parallel approach to algorithms. Of course we believe that this is a solid foundation that can be generalized and built upon, hence the proposal. But we deliberately avoided any design decisions which may be controversial or result in a prolonged tug of war, instead intending for subsequent proposals (not necessarily authored by us) to fill the gaps. Certainly, should anything being proposed now be a possible hindrance for any reasonable extension, it must be addressed sooner than later, however I think that none of the lacks pointed by you belong to this category. >>> Some particular issues with the proposed design include: >>> >>> - No iterators are provided for array_view or strided_array_view, a clear >>> omission in the interface. For a multidimensional array, there are two >>> obvious types of iteration that may be desired: >>> 1. iterating over just the first dimension; >>> 2. iterating over a flat view of all of the elements. For a strided >>> array, iterating over a flat view cannot be done efficiently without >>> segmented/hierarchical iterators. >>> Which of these should be the default (i.e. provided through begin() and >>> end() rather than through some adaptor) is not clear, >> >> From the Zen of Python, "In the face of ambiguity, refuse the >> temptation to guess." > > That's true, but no adaptors to provide the functionality unambiguously are provided either. For the particular case of a one-dimensional array, there is no ambiguity, and not being able to easily use array_view with standard algorithms or range-based for is a serious usability issue. This will only become worse if/when standard algorithm overloads that take ranges rather than iterator pairs are added. To the list of possible alternatives, I would add an option that was proposed somewhere in the prior discussion on the proposal -- "hierarchical" array_view/elemental iterator, i.e. an iterator that for array_view with Rank > 1 iterates over array_view; and over T for Rank == 1. It is however worth pointing out that in the first round of review with LEWG at Issaquah meeting, the vocal unchallenged feedback for iterators was "I do not want iterators for the views", thus we did not put much effort into contemplating adding any. Even though the choice for Rank == 1 is "obvious", we consider this a corner case for array_view, and would rather have a holistic approach. There remains the possibility to add some form of the iterator as a future extension. >>> - No data() access member for strided_array_view. This is presumably >>> omitted because the memory is non-contiguous, but given that >>> strided_array_view is a thin wrapper, there has to be a convenient way to >>> get at the underlying memory. >> >> Why "has to"? > > Because the user might want to convert the array to another representation for use by another piece of code/library, e.g. FFTW or Eigen, CUDA memcpy, etc. Under the proposed interface, for a 3-dimensional stided array view, you have to use &arr[0][0][0]. This is even worse than having to do &vec[0] for std::vector, since the same expression cannot be used independent of the dimensionality. data() on strided_array_view could be harmful, as there is no guarantee of contiguity, which a developer / function template might assume. Please note that for every other case in the Standard, the range [data(), data()+size()) is valid/safe, thus providing other semantics here would be dubious. Granted, one can perform &arr[0][0][0] and run afoul, but that is no different than e.g. &my_list.front(). It could be possible to provide "unsafe_data()" interface, which would have to be consumed along with stride(), however I do not see much benefit here over just using the "proper" interface -- bounds() and operator[](). >>> - Slicing is limited: it is not possible to take a slice in a dimension >>> other than the first. >> >> I think that's called "section()". > > Well, that takes a "section" but does not reduce the dimensionality like "slice". [...] Certainly there is a large design space for general subscripting and it almost certainly requires a fair amount of template metaprogramming, but this is very useful functionality Yes, slicing and sectioning are slightly different. It is however important to note that slicing in its current form always guarantees the contiguity of the result, thus the return type may be array_view. The more general cases (as you are describing) would result in a potentially strided resulting view, which would need to be typed strided_array_view. This is why it is important IMO to distinguish these two cases. In the current form of the proposal we decided to provide the minimal design -- only the first version, which in our opinion might be handy for users used to C-style multidimensional addressing (i.e. arr[3][1][4] v arr[{3, 1, 4}]), which actually you used above :). The latter generic case can be trivially added as an extension to the interface. I agree it may be useful, and if the current design is accepted for the TS, I encourage you to propose such extension (or nag us for follow ups :)). >>> - It is not clear whether it is really useful to have bounds and index be >>> separate types (though should probably at least be explicitly convertible to >>> each other). >> >> It adds a bit of type safety. Adding two bounds, for instance, doesn't >> make a lot of sense. > > I agree that type safety is in principle useful, but it is impossible to predict what relationships might hold in any given program, and so there is the question of whether the safety it adds is worth the cost of having to explicitly work around it in the cases that it is too restrictive. Certainly if they are separate types there needs to be a way to (explicitly) convert. I agree with both of you :). These are separate types, because their meaning and semantics are different. It was also discussed in N3851, Appendix, II. The mental model I use for reasoning about them is: index ~ vector and bounds ~ point (more specifically: a zero-bound, axis-aligned rectangle described by its maximum point), which makes the set of available operators apparent. I understand the explicit conversions between these two types, even though not theoretically sound, might be handy in practice and should be added. > As a specific example, consider if we want to compute the bounds of a valid convolution if we have an array x and a filter k. The bounds of the result are: x.bounds - k.bounds + 1. None of the arithmetic operators defined in the proposal help me with that; I'd just have to write a loop. Even if the arithmetic operators weren't limited by the bounds/index distinction, there would still be no way to create a constant-valued vector, i.e. to handle the constant 1. Explicit conversions would help with the first part, right? I hope you are also not suggesting any such conversion should be implicit? However I do not really understand what do you mean in the second part, "a constant-valued vector". We purposefully allow to create both bounds<1> and index<1> from a scalar; and disallow such operation for Rank > 1 (mostly because the semantics are not obvious, e.g. for rank 2, should index<2>{16} be {0, 16}, {16, 0} or {16, 16}). So net-net, in your example you should be able to do: x.bounds - index<2>{k.bounds} + {1, 1}. It a little more long-winded, but IMO easier to comprehend than the original. > Another related issue I didn't notice before: the only way to construct an index or bounds type is from an initializer_list. There is no (explicit) conversion from std::array, for instance. It is quite likely that an index or bounds value would be computed by some other code, that may use a different representation. Yes, we should add (const value_type* begin, const value_type* end) constructors for both types. Or it should be possible to create initializer_list explicitly from such pair which would solve this issue universally. >>> Furthermore, bounds and index essentially represent a >>> fixed-size discrete vector type, i.e. an augmented interface for std::array. >>> Arguably the interface of std::array should just be extended to add >>> component-wise operators instead. Also, a much more comprehensive set of >>> component-wise operations should be provided. A statically-sized vector >>> type is sorely needed in C++, but it does not make sense to standardize >>> these limited, single-purposes types when they could be, and should be, much >>> more general. >> >> We don't necessarily want to go for the most general possible type all at once > > Certainly there is a large design space, but that is a reason to be cautious about standardizing anything. [...] There are two separate issue raised here: - Why novel types -- this is primarily to introduce "vocabulary" types and allow to discriminate index and bounds, as they have different semantics, as discussed before. This was also touched upon in the previously referred N3851, Appendix, II. - Why so little functionality -- I agree with Jeffrey on this, and I have described more of the philosophy in the introduction. I would be interested however what exactly you mean by "a much more comprehensive set of component-wise operations". Having said that, I assume this is something that can be added later as a pure extension, correct? > Given the long turn around time for revisions to C++ The Committee is certainly trying to get better at quicker iterations, let's not be discouraged by the ghosts of the past... > Other omissions from index and bounds include: > 1. no data() access to the components > 2. no iterators over components for index or bound index and bounds are not containers and should not be used as such. For the limited number of scenario where I want to use/modify indeterminate number of components, it was always sufficient for me to use a raw loop, and operator[]... In case I'm wrong, these as well should be easy to add later as extensions. > for_each(x_array, y_array, x_array.bounds(), [&](auto &x, auto &y, auto pos) { > if (x != y) std::cout << "mismatch at position " << pos << std::endl; > }); I assume the idea here is that such "for_each" uses begin(X), end(X) for all provided arguments, passing dereferenced iterators to the function object. If so, I do not see how the current semantics of bounds_iterator would get into way here? It should just work as is, no? Actually, it should be possible to write the following with just the current proposal and the current standard for_each: auto x_av = array_view{x_array}; auto y_av = array_view{y_array}; for_each(begin(x_av.bounds()), end(x_av.bounds()), [&](index pos) { if(x_av[pos] != y_av[pos]) std::cout << "mismatch at position " << pos << std::endl; }); > From my perspective, the only way to properly explore this design space for multidimensional arrays/containers/ranges is through an actively developed and widely used open source library. Our (Microsoft) prototype implementation is in the pipeline to be published as an open source project. It should happen really soon, and I hope it will help to convey the discussed ideas. On Friday, June 13, 2014 9:30:45 PM UTC-7, Jeremy Maitin-Shepard wrote: > > > On Friday, June 13, 2014 5:54:21 PM UTC-7, Jeffrey Yasskin wrote: >> >> Thanks for the comments. Lukasz, FYI in case you're not on this list. >> >> On Fri, Jun 13, 2014 at 9:17 PM, Jeremy Maitin-Shepard >> wrote: >> > C++ is sorely in need of a "vocabulary type" for representing pointer >> > ranges. It is also sorely in need of a good, standard library for >> > multidimensional arrays/containers/ranges. While the design space for >> a >> > one-dimensional, unstrided array view is fairly limited, the design >> space >> > for a multidimensional array/container/range is very large. Finding >> the >> > right design certainly involves numerous design iterations and very >> > substantial user experience. While the proposed design in n3976 is a >> very >> > useful starting point, it would be premature to standardize it at this >> > point, as it is far from comprehensive and it is difficult to know how >> well >> > the proposed interface could be extended to provide a larger set of >> > functionality on par with the facilities available in many other >> languages. >> >> According to N3851, >> http://msdn.microsoft.com/en-us/library/vstudio/hh305260(v=vs.110).aspx >> >> seems to be that user experience. We'll also have a chance to get more >> experience while this is in a TS before being standardized. >> > > I saw that, but the fact that it is part of AMP suggests that the focus is > a bit more specialized than a general multidimensional array. > > >> > Some particular issues with the proposed design include: >> > >> > - No iterators are provided for array_view or strided_array_view, a >> clear >> > omission in the interface. For a multidimensional array, there are two >> > obvious types of iteration that may be desired: >> > 1. iterating over just the first dimension; >> > 2. iterating over a flat view of all of the elements. For a strided >> > array, iterating over a flat view cannot be done efficiently without >> > segmented/hierarchical iterators. >> > Which of these should be the default (i.e. provided through begin() >> and >> > end() rather than through some adaptor) is not clear, >> >> From the Zen of Python, "In the face of ambiguity, refuse the >> temptation to guess." >> >> That's true, but no adaptors to provide the functionality unambiguously > are provided either. For the particular case of a one-dimensional array, > there is no ambiguity, and not being able to easily use array_view with > standard algorithms or range-based for is a serious usability issue. This > will only become worse if/when standard algorithm overloads that take > ranges rather than iterator pairs are added. > > > - No data() access member for strided_array_view. This is presumably >> > omitted because the memory is non-contiguous, but given that >> > strided_array_view is a thin wrapper, there has to be a convenient way >> to >> > get at the underlying memory. >> >> Why "has to"? >> > > Because the user might want to convert the array to another representation > for use by another piece of code/library, e.g. FFTW or Eigen, CUDA memcpy, > etc. Under the proposed interface, for a 3-dimensional stided array view, > you have to use &arr[0][0][0]. This is even worse than having to do > &vec[0] for std::vector, since the same expression cannot be used > independent of the dimensionality. > > >> >> > Given the definition of Viewable, the use of >> > the name data() might be problematic as it would allow the incorrect >> (albeit >> > explicit) conversion from strided_array_view to array_view. Possibly >> > Viewable should be traits-based rather than based only on the presence >> of >> > data() and size(). >> >> The downside of traits, of course, is that we'd burden users with >> marking their types. If nearly all existing contiguous types expose >> data()/size(), the library can save people work by using them. >> > > That's a valid point. > > >> >> > - Slicing is limited: it is not possible to take a slice in a dimension >> > other than the first. >> >> I think that's called "section()". >> > > Well, that takes a "section" but does not reduce the dimensionality like > "slice". For instance, suppose I have a two-dimensional 20x10 array arr > and want to do the equivalent of the numpy: > > arr[:,5] > > and obtain a 1-dimensional strided_array_view of length 20. > > Certainly there is a large design space for general subscripting and it > almost certainly requires a fair amount of template metaprogramming, but > this is very useful functionality. > > >> > - operator++ and operator-- on index seem very questionable. The >> semantics >> > are rather arbitrary and not that likely to be useful except for a >> single >> > dimension anyway. >> >> They're marked with "Requires: Rank == 1." This should be more like >> "Ill-formed unless ...", but the goal is there. >> > Sorry, I missed that requirement. No problem there then. > > >> >> > - It is not clear whether it is really useful to have bounds and index >> be >> > separate types (though should probably at least be explicitly >> convertible to >> > each other). >> >> It adds a bit of type safety. Adding two bounds, for instance, doesn't >> make a lot of sense. >> > I agree that type safety is in principle useful, but it is impossible to > predict what relationships might hold in any given program, and so there is > the question of whether the safety it adds is worth the cost of having to > explicitly work around it in the cases that it is too restrictive. > Certainly if they are separate types there needs to be a way to > (explicitly) convert. Right now the only way to convert is to write a > manual loop and use operator[], or possibly use operator[] to obtain > pointers and then call memcpy or std::copy. > > As a specific example, consider if we want to compute the bounds of a > valid convolution if we have an array x and a filter k. The bounds of the > result are: x.bounds - k.bounds + 1. None of the arithmetic operators > defined in the proposal help me with that; I'd just have to write a loop. > Even if the arithmetic operators weren't limited by the bounds/index > distinction, there would still be no way to create a constant-valued > vector, i.e. to handle the constant 1. > > Another related issue I didn't notice before: the only way to construct an > index or bounds type is from an initializer_list. There is no (explicit) > conversion from std::array, for instance. It is quite likely that an index > or bounds value would be computed by some other code, that may use a > different representation. > >> >> > Furthermore, bounds and index essentially represent a >> > fixed-size discrete vector type, i.e. an augmented interface for >> std::array. >> > Arguably the interface of std::array should just be extended to add >> > component-wise operators instead. Also, a much more comprehensive set >> of >> > component-wise operations should be provided. A statically-sized >> vector >> > type is sorely needed in C++, but it does not make sense to standardize >> > these limited, single-purposes types when they could be, and should be, >> much >> > more general. >> >> We don't necessarily want to go for the most general possible type all at >> once. >> > > Certainly there is a large design space, but that is a reason to be > cautious about standardizing anything. Given the long turn around time for > revisions to C++, it doesn't make sense to standardize a partial solution; > better to work out a good, complete interface outside the standard. Given > that there is no standard fixed-length vector, users will be tempted to use > index as one, but will quickly find it to be lacking in important > functionality. > > >> > Other omissions from index and bounds include: >> > 1. no data() access to the components >> > 2. no iterators over components for index or bound >> >> How are those related to indexing? >> > > Maybe I want to print out the index, by iterating over the components. > Maybe I want to convert the index to/from another representation using the > raw array representation. An index is just a value in the program, and > there is no way of knowing what operations the user may want to perform on > it. The philosophy of C++ is to not get in the user's way. > > >> >> > 3. the iterators for bounds iterate over positions, but are >> inefficient >> > without segment/hierarchical iterators. >> >> Show us your measurements when you make an efficiency claim. >> > > Alright, fair enough. Still, it would be nice to be able to generate code > equivalent to N nested for loops for an N dimensional bounds. > > > >> > This position iteration is clearly >> > useful but the facility at present is very limited: it should likely be >> > presented as a multidimensional range itself, and support a non-zero >> origin. >> >> What's the use case? > > > This is useful in conjunction with a multdimensional, multiple range > for_each. Suppose we have two multidimensional arrays x_array and y_array > with the same bounds. We then might want: > for_each(x_array, y_array, [&](auto &x, auto &y) { x += y; }); > > However, we might also want: > > for_each(x_array, y_array, x_array.bounds(), [&](auto &x, auto &y, auto > pos) { > if (x != y) std::cout << "mismatch at position " << pos << std::endl; > }); > > This could also be further improved by the use of macros or a language > extension that allows x and x_array, y and y_array, x_array.bounds() and > pos to be syntactically related. > -- --- 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/. ------=_Part_519_6490396.1402893504503 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

Thank you Jeffrey for adding me on the thread and for y= our initial response -- which I almost universally agree with.

Jeremy= , thank you for your detailed feedback. First, I believe that most of the d= isagreement stems from the approach to the proposal. You've commented = that "it doesn't make sense to standardize a partial solution; better to wo= rk out a good, complete interface outside the standard". This is opposite t= o the "crawl, walk, run" philosophy we have taken when writing this documen= t up. We recognize that we have only explored some parts of the design spac= e, because as you have rightly observed our experience is limited to C++ AM= P, which constitutes only a specific data parallel approach to algorithms. = Of course we believe that this is a solid foundation that can be generalize= d and built upon, hence the proposal. But we deliberately avoided any desig= n decisions which may be controversial or result in a prolonged tug of war,= instead intending for subsequent proposals (not necessarily authored by us= ) to fill the gaps. Certainly, should anything being proposed now be a poss= ible hindrance for any reasonable extension, it must be addressed sooner th= an later, however I think that none of the lacks pointed by you belong to t= his category.

>>> Some particular issues with the proposed d= esign include:
>>>
>>> - No iterators are provide= d for array_view or strided_array_view, a clear
>>> omission i= n the interface.  For a multidimensional array, there are two
>= >> obvious types of iteration that may be desired:
>>>&n= bsp;  1. iterating over just the first dimension;
>>>&nbs= p;  2. iterating over a flat view of all of the elements.  For a = strided
>>> array, iterating over a flat view cannot be done e= fficiently without
>>> segmented/hierarchical iterators.
&= gt;>>   Which of these should be the default (i.e. provided= through begin() and
>>> end() rather than through some adapto= r) is not clear,
>>
>> From the Zen of Python, "In the f= ace of ambiguity, refuse the
>> temptation to guess."
>> That's true, but no adaptors to provide the functionality unambiguous= ly are provided either.  For the particular case of a one-dimensional = array, there is no ambiguity, and not being able to easily use array_view w= ith standard algorithms or range-based for is a serious usability issue.&nb= sp; This will only become worse if/when standard algorithm overloads that t= ake ranges rather than iterator pairs are added.

To the list of possi= ble alternatives, I would add an option that was proposed somewhere in the = prior discussion on the proposal -- "hierarchical" array_view/elemental ite= rator, i.e. an iterator that for array_view<T, Rank> with Rank > 1= iterates over array_view<T, Rank-1>; and over T for Rank =3D=3D 1.It is however worth pointing out that in the first round of review with L= EWG at Issaquah meeting, the vocal unchallenged feedback for iterators was = "I do not want iterators for the views", thus we did not put much effort in= to contemplating adding any. Even though the choice for Rank =3D=3D 1 is "o= bvious", we consider this a corner case for array_view, and would rather ha= ve a holistic approach.
There remains the possibility to add some form o= f the iterator as a future extension.

>>> - No data() access= member for strided_array_view.  This is presumably
>>> o= mitted because the memory is non-contiguous, but given that
>>>= ; strided_array_view is a thin wrapper, there has to be a convenient way to=
>>> get at the underlying memory.
>>
>> Wh= y "has to"?
>
> Because the user might want to convert the arr= ay to another representation for use by another piece of code/library, e.g.= FFTW or Eigen, CUDA memcpy, etc.  Under the proposed interface, for a= 3-dimensional stided array view, you have to use &arr[0][0][0].  = This is even worse than having to do &vec[0] for std::vector, since the= same expression cannot be used independent of the dimensionality.

da= ta() on strided_array_view could be harmful, as there is no guarantee of co= ntiguity, which a developer / function template might assume. Please note t= hat for every other case in the Standard, the range [data(), data()+size())= is valid/safe, thus providing other semantics here would be dubious.
Gr= anted, one can perform &arr[0][0][0] and run afoul, but that is no diff= erent than e.g. &my_list.front().
It could be possible to provide "u= nsafe_data()" interface, which would have to be consumed along with stride(= ), however I do not see much benefit here over just using the "proper" inte= rface -- bounds() and operator[]().

>>> - Slicing is limited= : it is not possible to take a slice in a dimension
>>> other = than the first.
>>
>> I think that's called "section()".=
>
> Well, that takes a "section" but does not reduce the dime= nsionality like "slice". [...] Certainly there is a large design space for = general subscripting and it almost certainly requires a fair amount of temp= late metaprogramming, but this is very useful functionality

Yes, slic= ing and sectioning are slightly different. It is however important to note = that slicing in its current form always guarantees the contiguity of the re= sult, thus the return type may be array_view. The more general cases (as yo= u are describing) would result in a potentially strided resulting view, whi= ch would need to be typed strided_array_view. This is why it is important I= MO to distinguish these two cases.
In the current form of the proposal w= e decided to provide the minimal design -- only the first version, which in= our opinion might be handy for users used to C-style multidimensional addr= essing (i.e. arr[3][1][4] v arr[{3, 1, 4}]), which actually you used above = :).
The latter generic case can be trivially added as an extension to th= e interface. I agree it may be useful, and if the current design is accepte= d for the TS, I encourage you to propose such extension (or nag us for foll= ow ups :)).

>>> - It is not clear whether it is really usefu= l to have bounds and index be
>>> separate types (though shoul= d probably at least be explicitly convertible to
>>> each othe= r).
>>
>> It adds a bit of type safety. Adding two bound= s, for instance, doesn't
>> make a lot of sense.
>
>= I agree that type safety is in principle useful, but it is impossible to p= redict what relationships might hold in any given program, and so there is = the question of whether the safety it adds is worth the cost of having to e= xplicitly work around it in the cases that it is too restrictive.  Cer= tainly if they are separate types there needs to be a way to (explicitly) c= onvert.

I agree with both of you :).
These are separate types, bec= ause their meaning and semantics are different. It was also discussed in N3= 851, Appendix, II. The mental model I use for reasoning about them is: inde= x ~ vector and bounds ~ point (more specifically: a zero-bound, axis-aligne= d rectangle described by its maximum point), which makes the set of availab= le operators apparent.
I understand the explicit conversions between the= se two types, even though not theoretically sound, might be handy in practi= ce and should be added.

> As a specific example, consider if we wa= nt to compute the bounds of a valid convolution if we have an array x and a= filter k.  The bounds of the result are: x.bounds - k.bounds + 1.&nbs= p; None of the arithmetic operators defined in the proposal help me with th= at; I'd just have to write a loop.  Even if the arithmetic operators w= eren't limited by the bounds/index distinction, there would still be no way= to create a constant-valued vector, i.e. to handle the constant 1.

E= xplicit conversions would help with the first part, right? I hope you are a= lso not suggesting any such conversion should be implicit?
However I do = not really understand what do you mean in the second part, "a constant-valu= ed vector". We purposefully allow to create both bounds<1> and index&= lt;1> from a scalar; and disallow such operation for Rank > 1 (mostly= because the semantics are not obvious, e.g. for rank 2, should index<2&= gt;{16} be {0, 16}, {16, 0} or {16, 16}).
So net-net, in your example yo= u should be able to do: x.bounds - index<2>{k.bounds} + {1, 1}. It a = little more long-winded, but IMO easier to comprehend than the original.

> Another related issue I didn't notice before: the only way to cons= truct an index or bounds type is from an initializer_list.  There is n= o (explicit) conversion from std::array, for instance.  It is quite li= kely that an index or bounds value would be computed by some other code, th= at may use a different representation.

Yes, we should add (const valu= e_type* begin, const value_type* end) constructors for both types. <rant= >Or it should be possible to create initializer_list explicitly from suc= h pair which would solve this issue universally.</rant>

>>= ;> Furthermore, bounds and index essentially represent a
>>>= ; fixed-size discrete vector type, i.e. an augmented interface for std::arr= ay.
>>> Arguably the interface of std::array should just be ex= tended to add
>>> component-wise operators instead.  Also= , a much more comprehensive set of
>>> component-wise operatio= ns should be provided.  A statically-sized vector
>>> typ= e is sorely needed in C++, but it does not make sense to standardize
&g= t;>> these limited, single-purposes types when they could be, and sho= uld be, much
>>> more general.
>>
>> We don= 't necessarily want to go for the most general possible type all at once>
> Certainly there is a large design space, but that is a reason= to be cautious about standardizing anything. [...]

There are two sep= arate issue raised here:
- Why novel types -- this is primarily to intro= duce "vocabulary" types and allow to discriminate index and bounds, as they= have different semantics, as discussed before. This was also touched upon = in the previously referred N3851, Appendix, II.
- Why so little function= ality -- I agree with Jeffrey on this, and I have described more of the phi= losophy in the introduction. I would be interested however what exactly you= mean by "a much more comprehensive set of component-wise operations". Havi= ng said that, I assume this is something that can be added later as a pure = extension, correct?

> Given the long turn around time for revision= s to C++

The Committee is certainly trying to get better at quicker i= terations, let's not be discouraged by the ghosts of the past...

>= Other omissions from index and bounds include:
>  1. no data() = access to the components
>  2. no iterators over components for = index or bound

index and bounds are not containers and should not be = used as such. For the limited number of scenario where I want to use/modify= indeterminate number of components, it was always sufficient for me to use= a raw loop, and operator[]...
In case I'm wrong, these as well should b= e easy to add later as extensions.

> for_each(x_array, y_array, x_= array.bounds(), [&](auto &x, auto &y, auto pos) {
> =   if (x !=3D y) std::cout << "mismatch at position " << po= s << std::endl;
> });

I assume the idea here is that such= "for_each" uses begin(X), end(X) for all provided arguments, passing deref= erenced iterators to the function object. If so, I do not see how the curre= nt semantics of bounds_iterator would get into way here? It should just wor= k as is, no?
Actually, it should be possible to write the following with= just the current proposal and the current standard for_each:
 auto= x_av =3D array_view<N>{x_array};
 auto y_av =3D array_view&l= t;N>{y_array};
 for_each(begin(x_av.bounds()), end(x_av.bounds()= ), [&](index<N> pos) {
  if(x_av[pos] !=3D y_av[pos]) std= ::cout << "mismatch at position " << pos << std::endl; });

> From my perspective, the only way to properly explore= this design space for multidimensional arrays/containers/ranges is through= an actively developed and widely used open source library.

Our (Mi= crosoft) prototype implementation is in the pipeline to be published as an = open source project. It should happen really soon, and I hope it will help = to convey the discussed ideas.



On Friday, = June 13, 2014 9:30:45 PM UTC-7, Jeremy Maitin-Shepard wrote:


On Friday, June 13, 2014 5:54:= 21 PM UTC-7, Jeffrey Yasskin wrote:
Thanks for= the comments. Lukasz, FYI in case you're not on this list.

On Fri, Jun 13, 2014 at 9:17 PM, Jeremy Maitin-Shepard
<jer...@jeremyms.com> wrote:
> C++ is sorely in need of a "vocabulary type" for representing poin= ter
> ranges.  It is also sorely in need of a good, standard librar= y for
> multidimensional arrays/containers/ranges.  While the design = space for a
> one-dimensional, unstrided array view is fairly limited, the desig= n space
> for a multidimensional array/container/range is very large.  = Finding the
> right design certainly involves numerous design iterations and ver= y
> substantial user experience.  While the proposed design in n3= 976 is a very
> useful starting point, it would be premature to standardize it at = this
> point, as it is far from comprehensive and it is difficult to know= how well
> the proposed interface could be extended to provide a larger set o= f
> functionality on par with the facilities available in many other l= anguages.

According to N3851,
http:/= /msdn.microsoft.com/en-us/library/vstudio/hh305260(v=3Dvs.110).as= px
seems to be that user experience. We'll also have a chance to get more
experience while this is in a TS before being standardized.

I saw that, but the fact that it is part of AMP s= uggests that the focus is a bit more specialized than a general multidimens= ional array.


> Some particular issues with the proposed design include:
>
> - No iterators are provided for array_view or strided_array_view, = a clear
> omission in the interface.  For a multidimensional array, the= re are two
> obvious types of iteration that may be desired:
>   1. iterating over just the first dimension;
>   2. iterating over a flat view of all of the elements.  = ;For a strided
> array, iterating over a flat view cannot be done efficiently witho= ut
> segmented/hierarchical iterators.
>   Which of these should be the default (i.e. provided through= begin() and
> end() rather than through some adaptor) is not clear,

From the Zen of Python, "In the face of ambiguity, refuse the
temptation to guess."

That's true, but no adaptors to provide the functiona= lity unambiguously are provided either.  For the particular case of a = one-dimensional array, there is no ambiguity, and not being able to easily = use array_view with standard algorithms or range-based for is a serious usa= bility issue.  This will only become worse if/when standard algorithm = overloads that take ranges rather than iterator pairs are added.

> - No data() access member for strided_= array_view.  This is presumably
> omitted because the memory is non-contiguous, but given that
> strided_array_view is a thin wrapper, there has to be a convenient= way to
> get at the underlying memory.

Why "has to"?

Because the user might want to convert the array = to another representation for use by another piece of code/library, e.g. FF= TW or Eigen, CUDA memcpy, etc.  Under the proposed interface, for a 3-= dimensional stided array view, you have to use &arr[0][0][0].  Thi= s is even worse than having to do &vec[0] for std::vector, since the sa= me expression cannot be used independent of the dimensionality.
 

>  Given the definition of Viewable, the use of
> the name data() might be problematic as it would allow the incorre= ct (albeit
> explicit) conversion from strided_array_view to array_view.  = Possibly
> Viewable should be traits-based rather than based only on the pres= ence of
> data() and size().

The downside of traits, of course, is that we'd burden users with
marking their types. If nearly all existing contiguous types expose
data()/size(), the library can save people work by using them.

That's a valid point.
 

> - Slicing is limited: it is not possible to take a slice in a dime= nsion
> other than the first.

I think that's called "section()".

Well, that takes a "section" but does not reduce = the dimensionality like "slice".  For instance, suppose I have a two-d= imensional 20x10 array arr and want to do the equivalent of the numpy:
<= br>arr[:,5]
 
and obtain a 1-dimensional strided_array_view of l= ength 20.

Certainly there is a large design space for general subscr= ipting and it almost certainly requires a fair amount of template metaprogr= amming, but this is very useful functionality.


> - operator++ and operator-- on index seem very questionable.  = ;The semantics
> are rather arbitrary and not that likely to be useful except for a= single
> dimension anyway.

They're marked with "Requires: Rank =3D=3D 1." This should be more like
"Ill-formed unless ...", but the goal is there.
Sorry, I missed that requirement.  No problem th= ere then.
 

> - It is not clear whether it is really useful to have bounds and i= ndex be
> separate types (though should probably at least be explicitly conv= ertible to
> each other).

It adds a bit of type safety. Adding two bounds, for instance, doesn't
make a lot of sense.
I agree that type safety is in principle useful, but = it is impossible to predict what relationships might hold in any given prog= ram, and so there is the question of whether the safety it adds is worth th= e cost of having to explicitly work around it in the cases that it is too r= estrictive.  Certainly if they are separate types there needs to be a = way to (explicitly) convert.  Right now the only way to convert is to = write a manual loop and use operator[], or possibly use operator[] to obtai= n pointers and then call memcpy or std::copy.

As a specific example,= consider if we want to compute the bounds of a valid convolution if we hav= e an array x and a filter k.  The bounds of the result are: x.bounds -= k.bounds + 1.  None of the arithmetic operators defined in the propos= al help me with that; I'd just have to write a loop.  Even if the arit= hmetic operators weren't limited by the bounds/index distinction, there wou= ld still be no way to create a constant-valued vector, i.e. to handle the c= onstant 1.

Another related issue I didn't notice before: the only wa= y to construct an index or bounds type is from an initializer_list.  T= here is no (explicit) conversion from std::array, for instance.  It is= quite likely that an index or bounds value would be computed by some other= code, that may use a different representation.

> Furthermore, bounds and index essentially represent a
> fixed-size discrete vector type, i.e. an augmented interface for s= td::array.
> Arguably the interface of std::array should just be extended to ad= d
> component-wise operators instead.  Also, a much more comprehe= nsive set of
> component-wise operations should be provided.  A statically-s= ized vector
> type is sorely needed in C++, but it does not make sense to standa= rdize
> these limited, single-purposes types when they could be, and shoul= d be, much
> more general.

We don't necessarily want to go for the most general possible type all = at once.

Certainly there is a large design space, but that= is a reason to be cautious about standardizing anything.  Given the l= ong turn around time for revisions to C++, it doesn't make sense to standar= dize a partial solution; better to work out a good, complete interface outs= ide the standard.  Given that there is no standard fixed-length vector= , users will be tempted to use index as one, but will quickly find it to be= lacking in important functionality.
 
> Other omissions from index and bounds include:
>  1. no data() access to the components
>  2. no iterators over components for index or bound

How are those related to indexing?

Maybe I want to print out the index, by iterating= over the components.  Maybe I want to convert the index to/from anoth= er representation using the raw array representation.  An index is jus= t a value in the program, and there is no way of knowing what operations th= e user may want to perform on it.  The philosophy of C++ is to not get= in the user's way.
 

>  3. the iterators for bounds iterate over positions, but are = inefficient
> without segment/hierarchical iterators.

Show us your measurements when you make an efficiency claim.

Alright, fair enough.  Still, it would be ni= ce to be able to generate code equivalent to N nested for loops for an N di= mensional bounds.

 
> This position iteration is clearly
> useful but the facility at present is very limited: it should like= ly be
> presented as a multidimensional range itself, and support a non-ze= ro origin.

What's the use case?

This is useful in conjunction= with a multdimensional, multiple range for_each.  Suppose we have two= multidimensional arrays x_array and y_array with the same bounds.  We= then might want:
for_each(x_array, y_array, [&](auto &x, auto &= amp;y) { x +=3D y; });

However, we might also want:

for_each(= x_array, y_array, x_array.bounds(), [&](auto &x, auto &y, auto = pos) {
  if (x !=3D y) std::cout << "mismatch at position " &= lt;< pos << std::endl;
});
 
This could also be furt= her improved by the use of macros or a language extension that allows x and= x_array, y and y_array, x_array.bounds() and pos to be syntactically relat= ed.

--

---
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>.
------=_Part_519_6490396.1402893504503-- .