------=_Part_677_1850101629.1462021782288
Content-Type: multipart/alternative;
 boundary="----=_Part_678_1738248194.1462021782289"

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

The title is the proposal, quite.
For example, the parallelized version of std::sort would run at O(log=C2=B2=
 n)=20
time complexity and O(n log=C2=B2n) space complexity, using Batcher odd-eve=
n=20
mergesort.

--=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/c1a0bac5-c21d-4697-b2be-f53a98a184b1%40isocpp.or=
g.

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

<div dir=3D"ltr"><div>The title is the proposal, quite.</div><div>For examp=
le, the parallelized version of std::sort would run at O(log=C2=B2 n) time =
complexity and O(n log=C2=B2n) space complexity, using Batcher odd-even mer=
gesort.</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/c1a0bac5-c21d-4697-b2be-f53a98a184b1%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/c1a0bac5-c21d-4697-b2be-f53a98a184b1=
%40isocpp.org</a>.<br />

------=_Part_678_1738248194.1462021782289--
------=_Part_677_1850101629.1462021782288--

.

------=_Part_240_393790923.1462027919712
Content-Type: multipart/alternative;
 boundary="----=_Part_241_384233690.1462027919712"

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

On Saturday, April 30, 2016 at 9:09:42 AM UTC-4, NDos Dannyu wrote:
>
> The title is the proposal, quite.
> For example, the parallelized version of std::sort would run at O(log=C2=
=B2 n)=20
> time complexity
>

The only way to know that a parallel sort would be O(log(n)) would be if=20
you know that you could have n simultaneous paths of execution. And you=20
don't; that's rather hardware specific.

The only complexity you could guarantee would be O((n/k)log(n)), where `k`=
=20
is the number of simultaneous threads on the particular piece of hardware.=
=20
And because `k` is a constant (relative to the workload `n`), it gets=20
factored out of asymptotic analysis, leaving us back with `O(n log(n))`.

--=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/576e8365-59fa-47a9-8ef1-570f008e006a%40isocpp.or=
g.

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

<div dir=3D"ltr">On Saturday, April 30, 2016 at 9:09:42 AM UTC-4, NDos Dann=
yu wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: =
0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div=
>The title is the proposal, quite.</div><div>For example, the parallelized =
version of std::sort would run at O(log=C2=B2 n) time complexity</div></div=
></blockquote><div><br>The only way to know that a parallel sort would be O=
(log(n)) would be if
 you know that you could have n simultaneous paths of execution. And you
 don&#39;t; that&#39;s rather hardware specific.<br><br>The only complexity=
 you could guarantee would be O((n/k)log(n)), where `k` is the number of si=
multaneous threads on the particular piece of hardware. And because `k` is =
a constant (relative to the workload `n`), it gets factored out of asymptot=
ic analysis, leaving us back with `O(n log(n))`.<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/576e8365-59fa-47a9-8ef1-570f008e006a%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/576e8365-59fa-47a9-8ef1-570f008e006a=
%40isocpp.org</a>.<br />

------=_Part_241_384233690.1462027919712--
------=_Part_240_393790923.1462027919712--

.

------=_Part_1831_1476222522.1473585314132
Content-Type: multipart/alternative;
 boundary="----=_Part_1832_164172317.1473585314132"

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



2016=EB=85=84 4=EC=9B=94 30=EC=9D=BC =ED=86=A0=EC=9A=94=EC=9D=BC =EC=98=A4=
=ED=9B=84 11=EC=8B=9C 52=EB=B6=84 0=EC=B4=88 UTC+9, Nicol Bolas =EB=8B=98=
=EC=9D=98 =EB=A7=90:
>
>
> The only way to know that a parallel sort would be O(log(n)) would be if=
=20
> you know that you could have n simultaneous paths of execution. And you=
=20
> don't; that's rather hardware specific.
>
> The only complexity you could guarantee would be O((n/k)log(n)), where `k=
`=20
> is the number of simultaneous threads on the particular piece of hardware=
..=20
> And because `k` is a constant (relative to the workload `n`), it gets=20
> factored out of asymptotic analysis, leaving us back with `O(n log(n))`.
>
But that doesn't mean we don't need to specify it. Although we can only=20
have finite number of simultaneous, it is possible to have enough (Say,=20
MPPA-256, a 256-core processor). So I still think we should specify it.
=20

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/9c94ffef-2f12-47e3-84e2-866d050fcd5c%40isocpp.or=
g.

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

<div dir=3D"ltr"><br><br>2016=EB=85=84 4=EC=9B=94 30=EC=9D=BC =ED=86=A0=EC=
=9A=94=EC=9D=BC =EC=98=A4=ED=9B=84 11=EC=8B=9C 52=EB=B6=84 0=EC=B4=88 UTC+9=
, Nicol Bolas =EB=8B=98=EC=9D=98 =EB=A7=90:<blockquote class=3D"gmail_quote=
" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding=
-left: 1ex;"><div dir=3D"ltr"><div><br>The only way to know that a parallel=
 sort would be O(log(n)) would be if
 you know that you could have n simultaneous paths of execution. And you
 don&#39;t; that&#39;s rather hardware specific.<br><br>The only complexity=
 you could guarantee would be O((n/k)log(n)), where `k` is the number of si=
multaneous threads on the particular piece of hardware. And because `k` is =
a constant (relative to the workload `n`), it gets factored out of asymptot=
ic analysis, leaving us back with `O(n log(n))`.<br></div></div></blockquot=
e><div>But=C2=A0that doesn&#39;t mean we don&#39;t need to specify it. Alth=
ough we can only have finite number of simultaneous, it is possible to have=
 enough (Say, MPPA-256, a 256-core processor). So I still think we should s=
pecify it.</div><div>=C2=A0</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/9c94ffef-2f12-47e3-84e2-866d050fcd5c%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/9c94ffef-2f12-47e3-84e2-866d050fcd5c=
%40isocpp.org</a>.<br />

------=_Part_1832_164172317.1473585314132--

------=_Part_1831_1476222522.1473585314132--

.