220 41357 article Path: news.gmane.org!.POSTED!not-for-mail From: Arthur O'Dwyer Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Optimizing Power Function for Integral Types Date: Fri, 18 Jan 2019 14:38:49 -0800 (PST) Lines: 264 Approved: news@gmane.org Message-ID: References: Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_1127_813155791.1547851129276" X-Trace: blaine.gmane.org 1547851005 5862 195.159.176.226 (18 Jan 2019 22:36:45 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Fri, 18 Jan 2019 22:36:45 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBDLZJYWNDQIPVKUJ4ICRUBDDLQKC2@isocpp.org Fri Jan 18 23:36:41 2019 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yw1-f70.google.com ([209.85.161.70]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1gkckj-0001Oc-3i for gclcip-std-proposals@m.gmane.org; Fri, 18 Jan 2019 23:36:41 +0100 Original-Received: by mail-yw1-f70.google.com with SMTP id f10sf7707962ywc.21 for ; Fri, 18 Jan 2019 14:38:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=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; bh=m/TQxgmaLnHh+Cecb6yz3D702lTPyUgzVRbuu61flI0=; b=treDhW2MjPHYL74GDnCZX9n1gaQPA9RT/8AfbVXr0wOT2km3L7s7xPMYr9RJrWkWwH NfxUCVYOfjbei0HLI6+pOr9NU2GmBBCTSS5fouv9eJYpgEOzAzhlY7RRx55C7vrwRQvc dMSXExibWEEmC5qLtm+wsOFGsPZabCSSLTiK/UC+RIsnL/kSMltJQueGcHXXgDTWI/Mt QGgEJI7jeOzZ7gzgql2ro9C03Ze9IcZsWE1FNee3gyQ3A4EZ5b/s3GXzwNkMwLZYgTxe rwmuC5PoNonRmMu9zCuc4VZGYKDHTI+mqrmvhhVrrznKYoBPlM8uJVKsmVpIahinX4am SyCw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=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; bh=m/TQxgmaLnHh+Cecb6yz3D702lTPyUgzVRbuu61flI0=; b=eAbM9QCpCniHAVx4w6f1KTFxPkJVEgZQmLD1XyVSurRspezuCDw0umzmwa/QO2qEnX o7lZ5u70vNHVktP3ItLFZoDOMkLEBPaUfgxo2W4fnjdCxRN57T6e9ssGAqcyGvqcRVR9 WN+/cKu1xzmzjwf9uqS3U0TFjP53R1oB0c7K7/J7rKhjLfKz2gmIAh1MSic8Av+4GGWR 6AqwSE6P/Piibr+PaTdcoeEsnXW2k70ZZKTXtmNJuiyntuXHrEwfX65cIG+SBwUbOBah aAR21ztTqDhEzzN2LjFc9m3OGTTVA/gpj0nmOB2K1CGFgnyvCeS/DcrET9KgP0mOMd1i b82g== 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: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=m/TQxgmaLnHh+Cecb6yz3D702lTPyUgzVRbuu61flI0=; b=HQryDH1/GiBfIAEQSSo8CWqC0ckMk9TSkB6Fej7kh1rDU0W566KnPftawQ6vK6Nnqb OaIFcqAkG+1fB2uf8MBAphfvUmgTHEE2mZxS3IuF+EuFpjZsEi239xICtj0TsxF1CaeM 9jfoG5dNrxlW4smivRqEV7gfuAAZhsITXDLc/aAcL65Dw3mUb9wZJKtIfheltGK7saRr tsabcapAOhxH6G5NfZsJAnTqVTfhcd1PyTqQQt10DiC1vvwWblK1/wUKR5doWqUsSaBR B4TaqicuMzBZQEJqGpCwtrl8e95fDa++iw3Fa23ZKmMaTWjqS5FA9jc8F1yuIOhf58y+ BTKA== X-Gm-Message-State: AJcUukfpW4zMl0MPs/+rfbjJ40DPs1dd4uxrjsvMYB0nenh91I2Dx1c8 dkS9UDLUIkWmtwzwoKCyXUHiJg== X-Google-Smtp-Source: ALg8bN74uED9lF8Wp3T/xECm3v8bxUZgnXb07uEZgsH2Q0fRzOH1Ng+exRVoIj+2d3aKkAkV2c/mWg== X-Received: by 2002:a25:cc8:: with SMTP id 191mr4056473ybm.30.1547851131809; Fri, 18 Jan 2019 14:38:51 -0800 (PST) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a81:7589:: with SMTP id q131ls265511ywc.1.gmail; Fri, 18 Jan 2019 14:38:50 -0800 (PST) X-Received: by 2002:a81:27cd:: with SMTP id n196mr209713ywn.2.1547851130155; Fri, 18 Jan 2019 14:38:50 -0800 (PST) In-Reply-To: X-Original-Sender: arthur.j.odwyer@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org 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:41357 Archived-At: ------=_Part_1127_813155791.1547851129276 Content-Type: multipart/alternative; boundary="----=_Part_1128_1455883637.1547851129277" ------=_Part_1128_1455883637.1547851129277 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Thursday, January 17, 2019 at 11:02:13 AM UTC-5, joel.g....@gmail.com=20 wrote: > > As of C++11, per overload 7 of the 'pow' function ( > https://en.cppreference.com/w/cpp/numeric/math/pow), integral types can= =20 > be used as parameters, but they will be cast to double before calculation= ..=20 > I believe that an integral-specific overload should be made, which makes= =20 > use of faster integer-operations available to CPUs. > > As a disclaimer, I am still a rather inexperienced programmer (College=20 > Sophomore), and I my have some misunderstands as to what would fall under= =20 > the ISO standard and what would fall under compiler-implementations. As I= =20 > understand it, the line about "If any argument has integral type, it is= =20 > cast to double." is a component of the ISO standard. > > As stated on isocpp.org's FAQ section, this idea is based on existing=20 > practices. As discussed here ( > https://stackoverflow.com/questions/2398442/why-isnt-int-powint-base-int-= exponent-in-the-standard-c-libraries),=20 > multiple implementations of this function have been made on a per-user=20 > basis, due to its general simplicity and lack of inclusion in previous=20 > standards. In the below testing, I created a function using x86 asm. It i= s=20 > worth noting that even with more standard C++ approaches, as testified in= =20 > the stackoverflow discussion above, a significant performance improvement= =20 > can be made. > > For the sake of brevity, the data-table and source have been withheld, bu= t=20 > if it is relevant to the conversation, I would be more than willing to=20 > provide them. > > Do any of you agree that this is a useful addition to the C++ standards? > > *Performance Testing:* > Tests were run on an Intel Core i3 6006U @ 2.0GHz > > Custom Function (VS 2017) :=20 > __declspec(naked) __int32 __fastcall powi(__int32 base, __int32 exp) {=20 > __asm { ... } } > > Test Range: > > base: [-46340, 46340] (int-truncation of the sqrt of MAX_INT) > > exp: [-19, 19] (highest power of 3, that does not overflow the int type) > > > Results: (Approx. x20 avg. improvement) > > [image: Untitled.png] > > > I am skeptical of this graph's reality. It looks too neat to me, with an=20 identical dip at n^0 and a constant gap between the two lines even on a log= =20 scale. (I could believe a constant gap on a linear scale, if what we were= =20 witnessing is the constant cost of two int-to-double conversions. But not a= =20 constant gap on a log scale!) Do you have a link to your exact test cases and the software that produced= =20 this graph, such that other people could reproduce your experiment from=20 scratch on their own hardware? Another thing that makes me skeptical of this graph is the weirdly constant= =20 and very low latencies for n^-19 through n^-1 (which are displayed as -n^19= =20 to -n^1 on the X-axis, but I assume that's a typo). Solving n^-19 (a.k.a.= =20 1/n^19) in integers is just "return (n =3D=3D 1) ? 1 : (n =3D=3D -1) ? -1 := 0;",=20 right? Whereas solving n^-19 in floating-point ought to require the exact= =20 same "log, multiply, exp" that would be required for n^19. As for adding a new overload of std::pow =E2=80=94 no, you'll never get awa= y with=20 that. double x =3D std::pow(10, 20); currently has well-defined behavior =E2=80=94 it yields 1e+20. You're prop= osing to=20 make it have undefined behavior instead. I don't think that's going to fly= .. You'd have better luck asking GCC and Clang to optimize `__builtin_pow` for= =20 small integers. Which I think they might already do? https://godbolt.org/z/7lPPLf Looks like maybe they special-case std::pow(1, n) but nothing else. HTH, Arthur --=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/c5128f98-b764-4576-90fc-eda8d40d980e%40isocpp.or= g. ------=_Part_1128_1455883637.1547851129277 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Thursday, January 17, 2019 at 11:02:13 AM UTC-5, joel.g= .....@gmail.com wrote:
As of C++11, per overload 7 of the 'pow' function (= https://en.cppreference.com/w/cpp/numeric/math/pow), integral type= s can be used as parameters, but they will be cast to double before calcula= tion. I believe that an integral-specific overload should be made, which ma= kes use of faster integer-operations available to CPUs.

= As a disclaimer, I am still a rather inexperienced programmer (College Soph= omore), and I my have some misunderstands as to what would fall under the I= SO standard and what would fall under compiler-implementations. As I unders= tand it, the line about "If any= argument has integral type,=C2=A0it is cast to double." is a component of the ISO standard.=

As stated on = isocpp.org's FAQ section, this = idea is based on existing practices. As discussed here (https://stackoverflow.com/q= uestions/2398442/why-isnt-int-powint-base-int-exponent-in-the-sta= ndard-c-libraries), multiple implement= ations=C2=A0of this function have been made on a per-user basis, due to its= general simplicity and lack of inclusion in previous standards. In the bel= ow testing, I created a function using x86 asm. It is worth noting that eve= n with more standard C++ approaches, as testified in the stackoverflow disc= ussion above, a significant performance improvement can be made.
<= br>
For the sake of brevity, the data-table and source have been w= ithheld, but if it is relevant=C2=A0to the conversation, I would be more th= an willing to provide them.

Do any of you agree that= this is a useful addition to the C++ standards?

Performance Testing:
Tests were run on an Intel Core i3 6006U @ 2.0GHz
<= br>
Custom Function (VS 2017) :
__declspec(naked) __int32 __fastcall powi= (__int3= 2 base,= __int32 exp) = { __asm { ...<= /span> } }

Test Range:
base: [-46340, 46340]= =C2=A0 (int-truncation of the sqrt of MAX_INT)
exp: [-19, 19] (highe= st power of 3, that does not overflow the int type)

Results: (Approx. x20 avg. improvement)

3D"Untitled.png"



I am skeptical of = this graph's reality. It looks too neat to me, with an identical dip at= n^0 and a constant gap between the two lines even on a log scale. (I could= believe a constant gap on a linear scale, if what we were witnessing is th= e constant cost of two int-to-double conversions. But not a constant gap on= a log scale!)
Do you have a link to your exact test cases and th= e software that produced this graph, such that other people could reproduce= your experiment from scratch on their own hardware?

Another thing that makes me skeptical of this graph is the weirdly const= ant and very low latencies for n^-19 through n^-1 (which are displayed as -= n^19 to -n^1 on the X-axis, but I assume that's a typo). =C2=A0Solving = n^-19 (a.k.a. 1/n^19) in integers is just "return (n =3D=3D 1) ? 1 : (= n =3D=3D -1) ? -1 : 0;", right? Whereas solving n^-19 in floating-poin= t ought to require the exact same "log, multiply, exp" that would= be required for n^19.

As for adding a new overloa= d of std::pow =E2=80=94 no, you'll never get away with that.
=
=C2=A0 =C2=A0 double x =3D std::pow(10, 20);
<= br>
currently has well-defined behavior =E2=80=94 it yields 1e+20= .. =C2=A0You're proposing to make it have undefined behavior instead. = =C2=A0I don't think that's going to fly.

Y= ou'd have better luck asking GCC and Clang to optimize `__builtin_pow` = for small integers. Which I think they might already do?
https://godbolt.org/z/7lPPLf
Looks like maybe they special-case std::pow(1, n) but nothing else.

HTH,
Arthur

--
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/c5128f98-b764-4576-90fc-eda8d40d980e= %40isocpp.org.
------=_Part_1128_1455883637.1547851129277-- ------=_Part_1127_813155791.1547851129276-- .