------=_Part_2087_973212256.1462700698492
Content-Type: multipart/alternative;
 boundary="----=_Part_2088_2045467701.1462700698492"

------=_Part_2088_2045467701.1462700698492
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Another quick idea: sometimes we know that we will perform an operation on=
=20
the next N element of an iterable, where N is known at compile-time. It=20
might be the case for what we could call =C2=AB bottom-up divide-and-conque=
r =C2=BB=20
algorithms. For example, WikiSort=20
<https://github.com/BonzaiThePenguin/WikiSort> starts by dividing the=20
collection to sort in chunks of 8 elements and sorting them before=20
proceeding with soe smart merging operations. We know how to speed up some=
=20
operations when the number of elements is small and known at compile-time:=
=20
sorting networks are an excellent tool to sort integers when the size of=20
the collection to sort is known at compile-time.

However there is no simple way to tell to the standard library's algorithms=
=20
that they will work with a small number of elements known at compile-time.=
=20
A solution would be to add span and view classes that take an integer=20
template parameter for their size, and let library implementers add=20
overloads to algorithms for such utility classes when they think it is=20
useful (it could still fit the Ranges TS design).

Any thoughts about the usefulness of such fixed-size span and view classes?

--=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.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/09bfdbe7-70d9-4d25-9f51-4b79cecfb79f%40isocpp.or=
g.

------=_Part_2088_2045467701.1462700698492
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Another quick idea: sometimes we know that we will perform=
 an operation on the next N element of an iterable, where N is known at com=
pile-time. It might be the case for what we could call =C2=AB bottom-up div=
ide-and-conquer =C2=BB algorithms. For example, <a href=3D"https://github.c=
om/BonzaiThePenguin/WikiSort">WikiSort</a> starts by dividing the collectio=
n to sort in chunks of 8 elements and sorting them before proceeding with s=
oe smart merging operations. We know how to speed up some operations when t=
he number of elements is small and known at compile-time: sorting networks =
are an excellent tool to sort integers when the size of the collection to s=
ort is known at compile-time.<br><br>However there is no simple way to tell=
 to the standard library&#39;s algorithms that they will work with a small =
number of elements known at compile-time. A solution would be to add span a=
nd view classes that take an integer template parameter for their size, and=
 let library implementers add overloads to algorithms for such utility clas=
ses when they think it is useful (it could still fit the Ranges TS design).=
<br><br>Any thoughts about the usefulness of such fixed-size span and view =
classes?<br></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/09bfdbe7-70d9-4d25-9f51-4b79cecfb79f%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/09bfdbe7-70d9-4d25-9f51-4b79cecfb79f=
%40isocpp.org</a>.<br />

------=_Part_2088_2045467701.1462700698492--
------=_Part_2087_973212256.1462700698492--

.

------=_Part_2056_1605771060.1462700714171
Content-Type: multipart/alternative;
 boundary="----=_Part_2057_1137107448.1462700714171"

------=_Part_2057_1137107448.1462700714171
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Another quick idea: sometimes we know that we will perform an operation on=
=20
the next N element of an iterable, where N is known at compile-time. It=20
might be the case for what we could call =C2=AB bottom-up divide-and-conque=
r =C2=BB=20
algorithms. For example, WikiSort=20
<https://github.com/BonzaiThePenguin/WikiSort> starts by dividing the=20
collection to sort in chunks of 8 elements and sorting them before=20
proceeding with soe smart merging operations. We know how to speed up some=
=20
operations when the number of elements is small and known at compile-time:=
=20
sorting networks are an excellent tool to sort integers when the size of=20
the collection to sort is known at compile-time.

However there is no simple way to tell to the standard library's algorithms=
=20
that they will work with a small number of elements known at compile-time.=
=20
A solution would be to add span and view classes that take an integer=20
template parameter for their size, and let library implementers add=20
overloads to algorithms for such utility classes when they think it is=20
useful (it could still fit the Ranges TS design).

Any thoughts about the usefulness of such fixed-size span and view classes?

--=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.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/dc128d7b-df5a-4a2f-a21b-136029ae3a84%40isocpp.or=
g.

------=_Part_2057_1137107448.1462700714171
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Another quick idea: sometimes we know that we will perform=
 an operation on the next N element of an iterable, where N is known at com=
pile-time. It might be the case for what we could call =C2=AB bottom-up div=
ide-and-conquer =C2=BB algorithms. For example, <a href=3D"https://github.c=
om/BonzaiThePenguin/WikiSort">WikiSort</a> starts by dividing the collectio=
n to sort in chunks of 8 elements and sorting them before proceeding with s=
oe smart merging operations. We know how to speed up some operations when t=
he number of elements is small and known at compile-time: sorting networks =
are an excellent tool to sort integers when the size of the collection to s=
ort is known at compile-time.<br><br>However there is no simple way to tell=
 to the standard library&#39;s algorithms that they will work with a small =
number of elements known at compile-time. A solution would be to add span a=
nd view classes that take an integer template parameter for their size, and=
 let library implementers add overloads to algorithms for such utility clas=
ses when they think it is useful (it could still fit the Ranges TS design).=
<br><br>Any thoughts about the usefulness of such fixed-size span and view =
classes?<br></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/dc128d7b-df5a-4a2f-a21b-136029ae3a84%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/dc128d7b-df5a-4a2f-a21b-136029ae3a84=
%40isocpp.org</a>.<br />

------=_Part_2057_1137107448.1462700714171--
------=_Part_2056_1605771060.1462700714171--

.

--001a1133b5503aa07b053251fb21
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On 8 May 2016 at 10:44, Morwenn <morwenn29@gmail.com> wrote:

> Another quick idea: sometimes we know that we will perform an operation o=
n
> the next N element of an iterable, where N is known at compile-time. It
> might be the case for what we could call =C2=AB bottom-up divide-and-conq=
uer =C2=BB
> algorithms. For example, WikiSort
> <https://github.com/BonzaiThePenguin/WikiSort> starts by dividing the
> collection to sort in chunks of 8 elements and sorting them before
> proceeding with soe smart merging operations. We know how to speed up som=
e
> operations when the number of elements is small and known at compile-time=
:
> sorting networks are an excellent tool to sort integers when the size of
> the collection to sort is known at compile-time.
>
> However there is no simple way to tell to the standard library's
> algorithms that they will work with a small number of elements known at
> compile-time. A solution would be to add span and view classes that take =
an
> integer template parameter for their size, and let library implementers a=
dd
> overloads to algorithms for such utility classes when they think it is
> useful (it could still fit the Ranges TS design).
>
> Any thoughts about the usefulness of such fixed-size span and view classe=
s?
>

You can have a merge sort algorithm for arbitrary sizes be defined in terms
of a kernel to sort 8 elements built with a sorting network.
I already plan to provide that as part of the SIMD algorithms.

--=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.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CALnjya8DWi2pdiFDJOoF3G4mF7UzOW8NbA%3DN8zc5OCdqt=
6NxQw%40mail.gmail.com.

--001a1133b5503aa07b053251fb21
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On 8=
 May 2016 at 10:44, Morwenn <span dir=3D"ltr">&lt;<a href=3D"mailto:morwenn=
29@gmail.com" target=3D"_blank">morwenn29@gmail.com</a>&gt;</span> wrote:<b=
r><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;borde=
r-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204)=
;padding-left:1ex"><div dir=3D"ltr">Another quick idea: sometimes we know t=
hat we will perform an operation on the next N element of an iterable, wher=
e N is known at compile-time. It might be the case for what we could call =
=C2=AB bottom-up divide-and-conquer =C2=BB algorithms. For example, <a href=
=3D"https://github.com/BonzaiThePenguin/WikiSort" target=3D"_blank">WikiSor=
t</a> starts by dividing the collection to sort in chunks of 8 elements and=
 sorting them before proceeding with soe smart merging operations. We know =
how to speed up some operations when the number of elements is small and kn=
own at compile-time: sorting networks are an excellent tool to sort integer=
s when the size of the collection to sort is known at compile-time.<br><br>=
However there is no simple way to tell to the standard library&#39;s algori=
thms that they will work with a small number of elements known at compile-t=
ime. A solution would be to add span and view classes that take an integer =
template parameter for their size, and let library implementers add overloa=
ds to algorithms for such utility classes when they think it is useful (it =
could still fit the Ranges TS design).<br><br>Any thoughts about the useful=
ness of such fixed-size span and view classes?</div></blockquote><div><br><=
/div>You can have a merge sort algorithm for arbitrary sizes be defined in =
terms of a kernel to sort 8 elements built with a sorting network.<div>I al=
ready plan to provide that as part of the SIMD algorithms.=C2=A0</div></div=
></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CALnjya8DWi2pdiFDJOoF3G4mF7UzOW8NbA%3=
DN8zc5OCdqt6NxQw%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">h=
ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CALnjya8DWi2pdi=
FDJOoF3G4mF7UzOW8NbA%3DN8zc5OCdqt6NxQw%40mail.gmail.com</a>.<br />

--001a1133b5503aa07b053251fb21--

.

------=_Part_2199_227591671.1462714838609
Content-Type: multipart/alternative;
 boundary="----=_Part_2200_620974199.1462714838610"

------=_Part_2200_620974199.1462714838610
Content-Type: text/plain; charset=UTF-8

The GSL `span` type already supports being compile-time sized. Being
dynamically sized is simply a specialization.

As for specializations in standard library algorithms... I don't much care
for that. Sure, they can be *allowed*, but we shouldn't expect them.

First, WikiSort seems to be able to work based solely on random-access
iterators. So it's not clear why we would need specializations for that.
Also WikiSort appears to have an implicit requirement of `value_type` being
default constructible (for the cache), which is not something that
`stable_sort` requires. So it could not be a general replacement in the
library (though this requirement may merely be lazy programming, not a
requirement of the algorithm).

Second, if I have a need for the properties of WikiSort, it would be silly
of me to just use `stable_sort` and hope that the implementation provides
this specializations. Yes, quality-of-implementation matters, but that is
simply expecting way too much from your implementation. The standard
library is a general tool for general uses; if you need such specific
algorithms, then you *need* specific algorithms.

I wouldn't be against having a few of these newer sorting algorithms added
to the standard library. But they should be new functions which have the
explicit behavior of their particular algorithms.

--
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/1f37ba85-fbfe-4a00-97fd-ac9125111bea%40isocpp.org.

------=_Part_2200_620974199.1462714838610
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">The GSL `span` type already supports being compile-time si=
zed. Being dynamically sized is simply a specialization.<br><br>As for spec=
ializations in standard library algorithms... I don&#39;t much care for tha=
t. Sure, they can be <i>allowed</i>, but we shouldn&#39;t expect them.<br><=
br>First, WikiSort seems to be able to work based solely on random-access i=
terators. So it&#39;s not clear why we would need specializations for that.=
 Also WikiSort appears to have an implicit requirement of `value_type` bein=
g default constructible (for the cache), which is not something that `stabl=
e_sort` requires. So it could not be a general replacement in the library (=
though this requirement may merely be lazy programming, not a requirement o=
f the algorithm).<br><br>Second, if I have a need for the properties of Wik=
iSort, it would be silly of me to just use `stable_sort` and hope that the =
implementation provides this specializations. Yes, quality-of-implementatio=
n matters, but that is simply expecting way too much from your implementati=
on. The standard library is a general tool for general uses; if you need su=
ch specific algorithms, then you <i>need</i> specific algorithms.<br><br>I =
wouldn&#39;t be against having a few of these newer sorting algorithms adde=
d to the standard library. But they should be new functions which have the =
explicit behavior of their particular algorithms.<br></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/1f37ba85-fbfe-4a00-97fd-ac9125111bea%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/1f37ba85-fbfe-4a00-97fd-ac9125111bea=
%40isocpp.org</a>.<br />

------=_Part_2200_620974199.1462714838610--
------=_Part_2199_227591671.1462714838609--

.

------=_Part_31_767047886.1462726442590
Content-Type: multipart/alternative;
 boundary="----=_Part_32_1038504208.1462726442591"

------=_Part_32_1038504208.1462726442591
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable



Le dimanche 8 mai 2016 15:40:38 UTC+2, Nicol Bolas a =C3=A9crit :
>
> The GSL `span` type already supports being compile-time sized. Being=20
> dynamically sized is simply a specialization.
>
=20
Woops, useless topic then, sorry.
=20

>
> As for specializations in standard library algorithms... I don't much car=
e=20
> for that. Sure, they can be *allowed*, but we shouldn't expect them.
>
> First, WikiSort seems to be able to work based solely on random-access=20
> iterators. So it's not clear why we would need specializations for that.=
=20
> Also WikiSort appears to have an implicit requirement of `value_type` bei=
ng=20
> default constructible (for the cache), which is not something that=20
> `stable_sort` requires. So it could not be a general replacement in the=
=20
> library (though this requirement may merely be lazy programming, not a=20
> requirement of the algorithm).
>
> Second, if I have a need for the properties of WikiSort, it would be sill=
y=20
> of me to just use `stable_sort` and hope that the implementation provides=
=20
> this specializations. Yes, quality-of-implementation matters, but that is=
=20
> simply expecting way too much from your implementation. The standard=20
> library is a general tool for general uses; if you need such specific=20
> algorithms, then you *need* specific algorithms.
>
> I wouldn't be against having a few of these newer sorting algorithms adde=
d=20
> to the standard library. But they should be new functions which have the=
=20
> explicit behavior of their particular algorithms.
>
=20
You're totally missing the point :p

I was just looking for an example of an algorithm that splits a range into=
=20
fixed-size range is known at compile-time and performs a well-known=20
operations (in this case sorting) on these fixed-size subranges to=20
highlight the fact that *allowing* standard algorithms to recognize a=20
fixed-size span or view might sometimes be useful. I'm not proposing to=20
standardize any specific sorting algorithm or anything, that would be=20
~useless at best.

Anyway, I only saw the standard view proposals and didn't notice that=20
gsl::span already provided the feature. I don't think I need anything more=
=20
then.

--=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.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/c225b7f4-8ae3-4d67-aed0-b5233e180bfe%40isocpp.or=
g.

------=_Part_32_1038504208.1462726442591
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>Le dimanche 8 mai 2016 15:40:38 UTC+2, Nicol Bolas=
 a =C3=A9crit=C2=A0:<blockquote class=3D"gmail_quote" style=3D"margin: 0;ma=
rgin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr">The GSL `span` type already supports being compile-time sized. Bei=
ng dynamically sized is simply a specialization.<br></div></blockquote><div=
>=C2=A0</div><div>Woops, useless topic then, sorry.<br>=C2=A0<br></div><blo=
ckquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-=
left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><br>As for specia=
lizations in standard library algorithms... I don&#39;t much care for that.=
 Sure, they can be <i>allowed</i>, but we shouldn&#39;t expect them.<br><br=
>First, WikiSort seems to be able to work based solely on random-access ite=
rators. So it&#39;s not clear why we would need specializations for that. A=
lso WikiSort appears to have an implicit requirement of `value_type` being =
default constructible (for the cache), which is not something that `stable_=
sort` requires. So it could not be a general replacement in the library (th=
ough this requirement may merely be lazy programming, not a requirement of =
the algorithm).<br><br>Second, if I have a need for the properties of WikiS=
ort, it would be silly of me to just use `stable_sort` and hope that the im=
plementation provides this specializations. Yes, quality-of-implementation =
matters, but that is simply expecting way too much from your implementation=
.. The standard library is a general tool for general uses; if you need such=
 specific algorithms, then you <i>need</i> specific algorithms.<br><br>I wo=
uldn&#39;t be against having a few of these newer sorting algorithms added =
to the standard library. But they should be new functions which have the ex=
plicit behavior of their particular algorithms.<br></div></blockquote><div>=
=C2=A0<br>You&#39;re totally missing the point :p<br><br>I was just looking=
 for an example of an algorithm that splits a range into fixed-size range i=
s known at compile-time and performs a well-known operations (in this case =
sorting) on these fixed-size subranges to highlight the fact that <i>allowi=
ng</i> standard algorithms to recognize a fixed-size span or view might som=
etimes be useful. I&#39;m not proposing to standardize any specific sorting=
 algorithm or anything, that would be ~useless at best.<br><br>Anyway, I on=
ly saw the standard view proposals and didn&#39;t notice that <span style=
=3D"font-family: courier new,monospace;">gsl::span</span> already provided =
the feature. I don&#39;t think I need anything more then.<br></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/c225b7f4-8ae3-4d67-aed0-b5233e180bfe%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/c225b7f4-8ae3-4d67-aed0-b5233e180bfe=
%40isocpp.org</a>.<br />

------=_Part_32_1038504208.1462726442591--
------=_Part_31_767047886.1462726442590--

.