220 32910 article Path: news.gmane.org!.POSTED!not-for-mail From: federico.kircheis@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: safe integrals comparison Date: Tue, 27 Jun 2017 08:23:46 -0700 (PDT) Lines: 128 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_2460_530601555.1498577026311" X-Trace: blaine.gmane.org 1498577029 25582 195.159.176.226 (27 Jun 2017 15:23:49 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Tue, 27 Jun 2017 15:23:49 +0000 (UTC) Cc: federico.kircheis@gmail.com To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCZ3PBGHYEBBBA7RZHFAKGQE63W5TSI@isocpp.org Tue Jun 27 17:23:45 2017 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-pg0-f70.google.com ([74.125.83.70]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dPsL9-0006LD-GE for gclcip-std-proposals@m.gmane.org; Tue, 27 Jun 2017 17:23:43 +0200 Original-Received: by mail-pg0-f70.google.com with SMTP id m188sf30323026pgm.2 for ; Tue, 27 Jun 2017 08:23:49 -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=/PKZNGQTUh3SE0piWtecTiDkLVFH8L4CbsFA4+KVEpU=; b=vyhAtLw0fcUcEXCUSbRKWJvL/8xHm3EcvHuJN/sNt5p+NWQW/L6PrY1HTjhW5N+RZ2 jnurZWjbp7oOMZbRht8YpvV0KzX47qw0+6jre4SLDxJQuOhnmJA4087kCWDb7ql8Un2r JQdM6+5zpYLYU3780VTmyDq4JCJi/kkLukMqNC7EAEZwKZVplCmPvcuv1+LgTlrLMmnG BkFRsMmdKV988MLMhjRTvpl0d20de1FeibQ0YsBGCtdavqcJx6qoD4/8xYA902ugXXIb +ZGRj1+hZt7FGfVBfO57dIBDLoztJ4M/YO/fww7mlsuWjUQA/8lHifrBbDGrpGdSoYpB hJ1g== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; 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=/PKZNGQTUh3SE0piWtecTiDkLVFH8L4CbsFA4+KVEpU=; b=pasQoDYwqVRqSNxOYfiqqCCkYkxMuHlYW5YPHneunxPYHn7IlIr3IzfEdZ1dhv0Fic c0My0YngORAfRTdPnOtFoDGSi1nYXbyRv4Nr4hoEvzTg8FlQ2JUW3EJahPkHWn/u/cWl y8Pk8p2v/npRPehRmz5J64IMgyawkMNMk++9i7oNDutQwfDCDHrgszEvYWQcT2PCz3TT c041wA9voxGZpOfP4kea49yUPQgnYGArEU6EY+k+GrPSJl5C8yZhwnY+4w7tW50YEdN6 01dy4RSmpXWg6ojVanJ+qU/ZSloUxgPjwWPeLSl8Ot80lsMRWSf9tdJ2KyLhz5dQ3oXV kR+w== 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=/PKZNGQTUh3SE0piWtecTiDkLVFH8L4CbsFA4+KVEpU=; b=P6sgNnd0bHmkL2x8QJdsmu5XTnJNSRvsI3mavkWp3a8Xe1q6lU3z6P2+8VdbEcFKfA 2566zvgY/+qnLAkfqFej/u9cppkO5oIl2LLq6HnySb9sHVAUQx79TeB++PU6fVwLod6S MEgtgZ7ARd4KG3LFJfOZ6Snw1sJstDX8gu6Fjy63sZZNjtnpX6/Qsb83JlCjpz1NCdbD fw3yDGRc+glb4U1w8GFE4eufKamP2K3Ui4px/QosPMeAvGEImMj+gJkqKNavh3VXqH2x MfewoHZSurgYwtS8c/7rP/02lK7PrHDT851Q7BHZF+s8sFBtE23NZ6K/2Vi6pnc+RH4p dNAg== X-Gm-Message-State: AKS2vOyFxAYufwoGQj34lN7Qc/foj9SGJdnpkfkoLI4LTVJasBiuvX1t SWPkL04YjEohx0hc X-Received: by 10.101.83.195 with SMTP id z3mr3467648pgr.106.1498577028337; Tue, 27 Jun 2017 08:23:48 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.107.41.200 with SMTP id p191ls1168708iop.45.gmail; Tue, 27 Jun 2017 08:23:47 -0700 (PDT) X-Received: by 10.36.69.103 with SMTP id y100mr38165ita.0.1498577026968; Tue, 27 Jun 2017 08:23:46 -0700 (PDT) In-Reply-To: X-Original-Sender: federico.kircheis@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:32910 Archived-At: ------=_Part_2460_530601555.1498577026311 Content-Type: multipart/alternative; boundary="----=_Part_2461_741436227.1498577026311" ------=_Part_2461_741436227.1498577026311 Content-Type: text/plain; charset="UTF-8" I'm sorry, I might have read your message to fast. Yes, the *only* situation where some overhead is involved is when a signed and an unsigned type (your use case actually), because you need to do some minimal checks about the ranges. It's the tradeoff between security/correctness and performance. Of course if you already know that the value is in the good range, there is no need to use my proposed functions (but you should assert it in case the surrounding code changes). The functions is_signed and precision do not take any parameter, they depend on the type of the argument, not the value of it, therefore they can always be executed at compile time. Of course the compiler is not forced to evaluate them at compile time, but I would expect it to do it if optimizations are enabled (and inline the functions too to avoid the function call overhead to, if it makes any difference). Of course the actual implementation does not have to be the one I proposed, there may be other that are simpler for the compiler to optimize, or to optimize to no overhead when comparing to specific values (for example 0). If you can assure that the increment operator will not be an issue, because, like you said, you know the size is not that big, then template std::vector> generate_subsets(const std::vector& v) { std::vector> res; for (int i = 0; cmp_less(i, 1 << v.size()); ++i) { res.emplace_back(); for (int j = 0; cmp_less(j, v.size()); ++j) { if ((i >> j & 1) == 1) { // unsure if >> and & gives an int as result, otherwise replace with "cmp_equal(i>>j & 1, 1)" res.back().push_back(v[j]); } } } return res; } should give you the desired output. If a compiler is good enough, because the functions are pure and so on, the extra comparison could be optimized away, but at this point is QOI issue, and you may not wan't to rely on it if it is a "hot" function. I'm unsure about you comment about __int128. AFAIK my implementation should work with all integral types, __int128 and other compiler-specific included, if they pass (at compile time), the "is_integral_not_bool" test. -- 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/fe04d87e-5b5e-452c-bd66-f7f43a86009c%40isocpp.org. ------=_Part_2461_741436227.1498577026311 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I'm sorry, I might have read your message to fast.
=
Yes, the *only* situation where some overhead is involved is when a sig= ned=20 and an unsigned type (your use case actually), because you need to do=20 some minimal checks about the ranges. It's the tradeoff between=20 security/correctness and performance.
Of course if you already know=20 that the value is in the good range, there is no need to use my proposed functions (but you should assert it in case the surrounding=20 code changes).

The functions is_signed and precision do not take any= parameter, they depend on the type of the argument, not the value of it, t= herefore they can always be executed at compile time. Of course the compile= r is not forced to evaluate them at compile time, but I would expect it to = do it if optimizations are enabled (and inline the functions too to avoid t= he function call overhead to, if it makes any difference).
Of course the= actual implementation does not have to be the one I proposed, there may be= other that are simpler for the compiler to optimize, or to optimize to no = overhead when comparing to specific values (for example 0).


If y= ou can assure that the increment operator will not be an issue, because, li= ke you said, you know the size is not that big, then

template <class T>
std::vector<std::vector<T>> generate_subsets(const std::vecto= r<T>& v) {
=C2=A0 std::vector<std::vector<T>&g= t; res;
=C2=A0 for (int i =3D 0; cmp_less(i, 1 << v.size())= ; ++i) {
=C2=A0 =C2=A0 res.emplace_back();
=C2=A0 =C2= =A0 for (int j =3D 0; cmp_less(j, v.size()); ++j) {
= =C2=A0 =C2=A0 =C2=A0 if ((i >> j & 1) =3D=3D 1) { // unsure if &g= t;> and & gives an int as result, otherwise replace with "cmp_e= qual(i>>j & 1, 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;
}
should give you the desired output.
If a compiler = is good enough, because the functions are pure and so on, the extra compari= son could be optimized away, but at this point is QOI issue, and you may no= t wan't to rely on it if it is a "hot" function.


<= br>I'm unsure about you comment about __int128. AFAIK my implementation= should work with all integral types, __int128 and other compiler-specific = included, if they pass (at compile time), the "is_integral_not_bool&qu= ot; test.



--
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/fe04d87e-5b5e-452c-bd66-f7f43a86009c= %40isocpp.org.
------=_Part_2461_741436227.1498577026311-- ------=_Part_2460_530601555.1498577026311-- .