From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/11276 Path: news.gmane.org!.POSTED!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: [PATCH] math: rewrite fma with mostly int arithmetics Date: Mon, 24 Apr 2017 00:35:33 +0200 Message-ID: <20170423223533.GS2082@port70.net> References: <20170418224140.GN2082@port70.net> <20170422222425.GI17319@brightrain.aerifal.cx> <20170423110052.GQ2082@port70.net> <20170423151539.GO17319@brightrain.aerifal.cx> <20170423223448.GR2082@port70.net> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="TRYliJ5NKNqkz5bu" X-Trace: blaine.gmane.org 1492986946 25013 195.159.176.226 (23 Apr 2017 22:35:46 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 23 Apr 2017 22:35:46 +0000 (UTC) User-Agent: Mutt/1.6.0 (2016-04-01) To: musl@lists.openwall.com Original-X-From: musl-return-11291-gllmg-musl=m.gmane.org@lists.openwall.com Mon Apr 24 00:35:42 2017 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.84_2) (envelope-from ) id 1d2Q6X-0006OB-M0 for gllmg-musl@m.gmane.org; Mon, 24 Apr 2017 00:35:41 +0200 Original-Received: (qmail 16317 invoked by uid 550); 23 Apr 2017 22:35:45 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 16293 invoked from network); 23 Apr 2017 22:35:45 -0000 Mail-Followup-To: musl@lists.openwall.com Content-Disposition: inline In-Reply-To: <20170423223448.GR2082@port70.net> Xref: news.gmane.org gmane.linux.lib.musl.general:11276 Archived-At: --TRYliJ5NKNqkz5bu Content-Type: text/plain; charset=us-ascii Content-Disposition: inline * Szabolcs Nagy [2017-04-24 00:34:48 +0200]: > * Rich Felker [2017-04-23 11:15:39 -0400]: > > On Sun, Apr 23, 2017 at 01:00:52PM +0200, Szabolcs Nagy wrote: > > > * Rich Felker [2017-04-22 18:24:25 -0400]: > > > > Is it difficult to determine when the multiplication part of an fma is > > > > exact? If you can determine this quickly, you can just return x*y+z in > > > > this special case and avoid all the costly operations. For normal > > > > range, I think it's roughly just using ctz to count mantissa bits of x > > > > and y, and checking whether the sum is <= 53. Some additional handling > > > > for denormals is needed of course. > > > > > > it is a bit more difficult than that: > > > > > > bits(a) + bits(b) < 54 || (bits(a) + bits(b) == 54 && a*b < 2) > > > > > > this is probably possible to handle when i do the int mul. > > > > > > however the rounding mode special cases don't get simpler > > > and inexact flag still may be raised incorrectly when tail > > > bits of x*y beyond 53 bits are eliminated when z is added > > > (the result is exact but the dekker algorithm raises inexact). > > > > One thing to note: even if it's not a replacement for the whole > > algorithm, this seems like a very useful optimization for a case > > that's easy to test. "return x*y+z;" is going to be a lot faster than > > anything else you can do. But maybe it's rare to hit cases where the > > optimization works; it certainly "should" be rare if people are using > > fma for the semantics rather than as a misguided optimization. > > i didn't see a simple way to check for exact x*y result > (if it were easy then that could capture the exact 0 result > case which means one less special case later, but this is > not easy if x*y is in the subnormal range or overflows) > > > > > If the only constraint here is that top 10 bits and last bit are 0, I > > > > don't see why clz is even needed. You can meet this constraint for > > > > denormals by always multiplying by 2 and using a fixed exponent value. > > > > > > yeah that should work, but i also use clz later > > > > Ah, I missed that. Still it might be a worthwhile optimization here; I > > think it shaves off a few ops in normalize(). > > attached a new version with updated normalize. > now really > on my laptop latency and code size: > > old x86_64: 67 ns/call 893 bytes > new x86_64: 20 ns/call 960 bytes > old i386: 80 ns/call 942 bytes > new i386: 75 ns/call 1871 bytes > old arm: - 960 bytes > new arm: - 1200 bytes --TRYliJ5NKNqkz5bu Content-Type: text/x-csrc; charset=us-ascii Content-Disposition: attachment; filename="fma.c" #include #include #include #include "atomic.h" #define ASUINT64(x) ((union {double f; uint64_t i;}){x}).i #define ZEROINFNAN (0x7ff-0x3ff-52-1) struct num { uint64_t m; int e; int sign; }; static struct num normalize(double x) { uint64_t ix = ASUINT64(x); int e = ix>>52; int sign = e & 0x800; e &= 0x7ff; if (!e) { ix = ASUINT64(x*0x1p63); e = ix>>52 & 0x7ff; e = e ? e-63 : 0x800; } ix &= (1ull<<52)-1; ix |= 1ull<<52; ix <<= 1; e -= 0x3ff + 52 + 1; return (struct num){ix,e,sign}; } static void mul(uint64_t *hi, uint64_t *lo, uint64_t x, uint64_t y) { uint64_t t1,t2,t3; uint64_t xlo = (uint32_t)x, xhi = x>>32; uint64_t ylo = (uint32_t)y, yhi = y>>32; t1 = xlo*ylo; t2 = xlo*yhi + xhi*ylo; t3 = xhi*yhi; *lo = t1 + (t2<<32); *hi = t3 + (t2>>32) + (t1 > *lo); } double fma(double x, double y, double z) { #pragma STDC FENV_ACCESS ON /* normalize so top 10bits and last bit are 0 */ struct num nx, ny, nz; nx = normalize(x); ny = normalize(y); nz = normalize(z); if (nx.e >= ZEROINFNAN || ny.e >= ZEROINFNAN) return x*y + z; if (nz.e >= ZEROINFNAN) { if (nz.e > ZEROINFNAN) /* z==0 */ return x*y + z; return z; } /* mul: r = x*y */ uint64_t rhi, rlo, zhi, zlo; mul(&rhi, &rlo, nx.m, ny.m); /* either top 20 or 21 bits of rhi and last 2 bits of rlo are 0 */ /* align exponents */ int e = nx.e + ny.e; int d = nz.e - e; /* shift bits z<<=kz, r>>=kr, so kz+kr == d, set e = e+kr (== ez-kz) */ if (d > 0) { if (d < 64) { zlo = nz.m<>64-d; } else { zlo = 0; zhi = nz.m; e = nz.e - 64; d -= 64; if (d == 0) { } else if (d < 64) { rlo = rhi<<64-d | rlo>>d | !!(rlo<<64-d); rhi = rhi>>d; } else { rlo = 1; rhi = 0; } } } else { zhi = 0; d = -d; if (d == 0) { zlo = nz.m; } else if (d < 64) { zlo = nz.m>>d | !!(nz.m<<64-d); } else { zlo = 1; } } /* add */ int sign = nx.sign^ny.sign; int samesign = !(sign^nz.sign); int nonzero = 1; if (samesign) { /* r += z */ rlo += zlo; rhi += zhi + (rlo < zlo); } else { /* r -= z */ uint64_t t = rlo; rlo -= zlo; rhi = rhi - zhi - (t < rlo); if (rhi>>63) { rlo = -rlo; rhi = -rhi-!!rlo; sign = !sign; } nonzero = !!rhi; } /* set rhi to top 63bit of the result (last bit is sticky) */ if (nonzero) { e += 64; d = a_clz_64(rhi)-1; /* note: d > 0 */ rhi = rhi<>64-d | !!(rlo<>1 | (rlo&1); else rhi = rlo<>1 | (rhi&1) | 1ull<<62; if (sign) i = -i; r = i; r = 2*r - c; /* remove top bit */ volatile double uflow = DBL_MIN/FLT_MIN; uflow *= uflow; } } else { /* only round once when scaled */ d = 10; i = ( rhi>>d | !!(rhi<<64-d) ) << d; if (sign) i = -i; r = i; } } return scalbn(r, e); } --TRYliJ5NKNqkz5bu--