220 32903 article Path: news.gmane.org!.POSTED!not-for-mail From: Mingxin Wang Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: safe integrals comparison Date: Mon, 26 Jun 2017 23:43:34 -0700 (PDT) Lines: 266 Approved: news@gmane.org Message-ID: References: <66f9bab2-7220-4bf1-afb7-77c5efa1bac3@isocpp.org> <7fa4ec6e-de06-414c-880a-7c9e52132803@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_2107_1791991667.1498545814293" X-Trace: blaine.gmane.org 1498545815 10876 195.159.176.226 (27 Jun 2017 06:43:35 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 27 Jun 2017 06:43:35 +0000 (UTC) Cc: federico.kircheis@gmail.com To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBDNMBNHJWIGBBF75Y7FAKGQE76PACKI@isocpp.org Tue Jun 27 08:43:31 2017 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-it0-f71.google.com ([209.85.214.71]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dPkDi-0002Y9-Nd for gclcip-std-proposals@m.gmane.org; Tue, 27 Jun 2017 08:43:31 +0200 Original-Received: by mail-it0-f71.google.com with SMTP id v193sf14010578itc.10 for ; Mon, 26 Jun 2017 23:43:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc: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; bh=dz0zFwB9QK4RhqZFKIQvraWTuJNDKds1e2+P3Wo1e1s=; b=DBl76ZCzulnoex0ROOedpQfPfvJmaODaP07Dsg3fsBFKtjoS9Gx0LHzPLPuDotuWA+ Cmpu1DIB9ze1h4c020I0clieSXJBqJnHp06auEoYoV3tFB+YKrLh8XiLl/A/OsuSqdLq I8wcBuAP5bfHTiLU+ZM7rRLMXOnr3A+3a6TvICjap7tYoaNukdEFOvaWVk3IYYAD3+BH x8RZo6JLcny97BpGp35dMh80BrlKHBuOsLu2fbIOwQWN5WVDDu0jJr6+l+rWSEiR+hFu UR3OiokHx4CpMesaNE20zRRax84VgJUl7TT2a0M7NIdwCHzlatPreQWL8bNI6JeE06uO CiEg== 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:cc: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=dz0zFwB9QK4RhqZFKIQvraWTuJNDKds1e2+P3Wo1e1s=; b=cwktsArHGAcX73yry11+sd+TfO5EP5idKCQ1QrmGKho6wHhQn2RpgUjeAg+l82oTBB yKAGED2GGZmA7Hhnu+K3fVx+HX7Mf6jej7+FcGklnt6WTDMDLKkqr7Vtb6+Z0t9YAgdb 9+GkgqjHhJQBPTgaUXqrqi41F2DJ4HjHjalAlVqHRquFBuEejXe7hNsdq1R9mkg7pHdT +bleemmm4yzwB9P8qC4K1FSuZzItEVX8kW9BnH70cRYEhkUxfJURrUusl4PxsyLx4fDB kG8HKogcKhRY+b9Ny7uALqFy5guNrU1E0S2hq+XSuccNQV02Jd4BQwu53BtANADGMwu3 Q7gw== X-Gm-Message-State: AKS2vOyaN8ObZcoykp4kNt+y9GllDvxIf5Y7VVRntoBindlN63T3hxIC v+txsoEESvfQlK8Y X-Received: by 10.107.133.226 with SMTP id p95mr2049248ioi.58.1498545815724; Mon, 26 Jun 2017 23:43:35 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.157.13.230 with SMTP id 93ls4811700ots.0.gmail; Mon, 26 Jun 2017 23:43:34 -0700 (PDT) X-Received: by 10.157.12.161 with SMTP id b30mr76422otb.3.1498545814855; Mon, 26 Jun 2017 23:43:34 -0700 (PDT) In-Reply-To: <7fa4ec6e-de06-414c-880a-7c9e52132803@isocpp.org> X-Original-Sender: wmx16835vv@163.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:32903 Archived-At: ------=_Part_2107_1791991667.1498545814293 Content-Type: multipart/alternative; boundary="----=_Part_2108_1423952121.1498545814293" ------=_Part_2108_1423952121.1498545814293 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Tuesday, June 27, 2017 at 1:39:48 PM UTC+8, federico...@gmail.com wrote: > > Hi, thank you for your feedback. > > The correct usage for the for-loop would be to use the right type,=20 > otherwise you may overflow. > I would not use cmp_less or cmp_equal here the real point of failure is= =20 > the ++ operation. > =20 Discard of the possibility of overflow, this sort of for-loop was widely=20 used in many cases, e.g. enumerating all subsets of a set with binary=20 operations: template std::vector> generate_subsets(const std::vector& v) { std::vector> res; for (int i =3D 0; i < (1 << (int)v.size()); ++i) { res.emplace_back(); for (int j =3D 0; j < (int)v.size(); ++j) { if ((i >> j & 1) =3D=3D 1) { res.back().push_back(v[j]); } } } return res; } This is an algorithm whose complexity is O(2^n). Providing n is not greater= =20 than 20, I perfer to use "int" to implement this algorithm instead of=20 std::size_t to gain higher performance. =20 > HI, I'm not sure what you mean about the extra overhead. > The functions are constexpr and the branch std::is_signed can also be=20 > evaluated at compile time. > > Therefore comparing an unsigned value with 0 is equivalent to > > return (t() / 2>precision()) ? (t =3D= =3D static_cast(u)) : (static_cast(t) =3D=3D u); > > precision is constexpr too, so it should be a simple =3D=3D operation wit= h a=20 > static_cast. I don't see the extra comparison, or am I missing something? > > Of course it depends on the ability of the compiler to optimize the=20 > branches at compile time (doable AFAIK), and if those functions are part = of=20 > the std::, i would expect such an optimization even more. > If a function is constexpr, it is only guaranteed that the returned value= =20 is constexpr providing the input data is constexpr, otherwise (when the=20 input data is not constexpr) the function is not guaranteed to be=20 calculated at compile time. Il giorno marted=C3=AC 27 giugno 2017 07:05:44 UTC+2, Mingxin Wang ha scrit= to: >> >> This is a good idea! However, I think maybe the following issues shall b= e=20 >> considered. >> >> *This feature may introduce unnecessary extra overhead* >> >> Comparing to bare comparators between signed and unsigned integral types= ,=20 >> this feature requires *one extra comparation* between the signed one and= =20 >> ZERO at runtime. Actually, it is not always necessary in some cases, e.g= .. >> >> std::vector v; >> for (int i =3D 0; i < v.size(); ++i) { >> // ... >> } >> >> Although variable i is a signed integer, the comparation is always=20 >> executed correctly providing v.size() won't=20 >> exceed std::numeric_limits::max(). Thus the extra comparation=20 >> introduced in your solution is redundant as we can assert that i is alwa= ys=20 >> positive. Still, I think there is enough motivation for us to have this= =20 >> feature. >> >> *A uniform wrapper* >> >> Although the problem can be solved with a uniform wrapper, that would=20 >> introduce even much overhead, especially when there are implementation= =20 >> defined integral types, e.g. __int128 in GCC. >> >> *Implementation with Concepts TS* >> >> I think the implementation could be much simpler with Concepts TS. For= =20 >> instance, we can define different overloads for the function template=20 >> cmp_less with different constraints, as is shown below: >> >> template >> bool cmp_less(const T&, const U&); // undefined >> >> template >> bool cmp_less(const T& lhs, const U& rhs) requires std::is_signed_v = =3D=3D=20 >> std::is_signed_v { >> return lhs < rhs; >> } >> >> template >> bool cmp_less(const T& lhs, const U& rhs) requires std::is_signed_v &= &=20 >> !std::is_signed_v { >> return lhs < 0 ? true : lhs < rhs; >> } >> >> template >> bool cmp_less(const T& lhs, const U& rhs) requires !std::is_signed_v= =20 >> && std::is_signed_v { >> return rhs < 0 ? false : lhs < rhs; >> } >> >> I hope these would help. >> >> Mingxin Wang >> > --=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/da719152-215c-420a-9b3d-cccdea4171d4%40isocpp.or= g. ------=_Part_2108_1423952121.1498545814293 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Tuesday, June 27, 2017 at 1:39:48 PM UTC+8, federico...= @gmail.com wrote:
Hi, thank you for your feedback.

The correct usage for the for-l= oop would be to use the right type, otherwise you may overflow.
I would = not use cmp_less or cmp_equal here the real point of failure is the ++ oper= ation.
=C2=A0
Discard of the possibili= ty of overflow, this sort of for-loop was widely used in many cases, e.g.= =C2=A0enumerating all subsets of a set with binary operations:

template <class T>
std::vector<std::vector<T>> generate_subsets(const std::vector= <T>& v) {
=C2=A0 std::vector&l= t;std::vector<T>> res;
=C2=A0 f= or (int i =3D 0; i < (1 << (int)v.size()); ++i) {
=C2=A0 =C2=A0 res.emplace_back();
=C2=A0 =C2=A0 for (int j =3D 0; j < (int)v.size(); ++j) {<= /div>
=C2=A0 =C2=A0 =C2=A0 if ((i >> j &= amp; 1) =3D=3D 1) {
=C2=A0 =C2=A0 =C2=A0= =C2=A0 res.back().push_back(v[j]);
=C2= =A0 =C2=A0 =C2=A0 }
=C2=A0 =C2=A0 }
=C2=A0 }
= =C2=A0 return res;
}
<= /div>
This is an algorithm whose complexity is O(2^n). Providing n is no= t greater than 20, I perfer to use "int" to implement this algori= thm instead of std::size_t to gain higher performance.
=C2=A0
HI, I'm= not sure what you mean about the extra overhead.
The functions are cons= texpr and the branch std::is_signed can also be evaluated at compile time.<= br>
Therefore comparing an unsigned value with 0 is equivalent to

return (t<=
T{ 0 }) ? false : (precision<T>() / 2>precision<U>()) ? (t =
=3D=3D static_cast<T>(u)) : (static_cast<U>(t) =3D=3D u);
= 
precision is constexpr too, so it shoul=
d be a simple =3D=3D operation with a static_cast. I don't see the extr=
a comparison, or am I missing something?

Of course it depends on the=
 ability of the compiler to optimize the branches at compile time (doable A=
FAIK), and if those functions are part of the std::, i would expect such an=
 optimization even more.

If a fun=
ction is constexpr, it is only guaranteed that the returned value is conste=
xpr providing the input data is constexpr, otherwise (when the input data i=
s not constexpr) the function is not guaranteed to be calculated at compile=
 time.

Il giorno marted=C3=AC 27 giugno 2017 07:05:44 UTC+2, Mingxin=
 Wang ha scritto:
T=
his is a good idea! However, I think maybe the following issues shall be co=
nsidered.

This feature=C2=A0may introduce unnecessary=
 extra overhead

Comparing to bare comparators =
between signed and unsigned integral types, this feature requires one ex=
tra comparation between the signed one and ZERO at runtime. Actually, i=
t is not always necessary in some cases, e.g.

std::vector<int> v;
for (int i =3D 0; i < v.size(); ++i) {
=C2=A0 // ...
}

Although variable i is a signed=
 integer, the comparation is always executed=C2=A0correctly providing v.siz=
e() won't exceed=C2=A0std::numeric_limits<int>::max(). Thus =
the extra comparation introduced in your solution is redundant as we can as=
sert that i is always positive. Still, I think there is enough motivation f=
or us to have this feature.

A uniform wrapper

Although the problem can be solved with a unifo=
rm wrapper, that would introduce even much overhead, especially when there =
are implementation defined integral types, e.g.=C2=A0__int128 in GCC.
=


Implementation with Concepts TS

I think the implementation could be much simpler with Concepts TS.=
 For instance, we can define different overloads for the function template =
cmp_less with different constraints, as is shown below:

=
template <class T, class U>
bool cmp_less(const T&, con=
st U&); // undefined

template <class T, cla=
ss U>
bool cmp_less(const T& lhs, const U& rhs) requir=
es std::is_signed_v<T> =3D=3D std::is_signed_v<U> {
=
=C2=A0 return lhs < rhs;
}

template &=
lt;class T, class U>
bool cmp_less(const T& lhs, const U&a=
mp; rhs) requires std::is_signed_v<T> && !std::is_signed_v<=
;U> {
=C2=A0 return lhs < 0 ? true : lhs < rhs;
}

template <class T, class U>
bo=
ol cmp_less(const T& lhs, const U& rhs) requires !std::is_signed_v&=
lt;T> && std::is_signed_v<U> {
=C2=A0 return rhs=
 < 0 ? false : lhs < rhs;
}
=


I hope these would help.

Mingxin Wang





-- 

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/da719152-215c-420a-9b3d-cccdea4171d4=
%40isocpp.org.


------=_Part_2108_1423952121.1498545814293--

------=_Part_2107_1791991667.1498545814293--

.