From patchwork Mon Mar 20 16:01:17 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 1759130 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=umfo37SZ; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4PgKJG3Mngz247C for ; Tue, 21 Mar 2023 03:02:38 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 6F7253850866 for ; Mon, 20 Mar 2023 16:02:36 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6F7253850866 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1679328156; bh=3u64IfKotUugQPWp2zGSuWRQB0NGnN/Qd5x2UDx3jAE=; h=To:Cc:Subject:Date:In-Reply-To:References:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=umfo37SZBM+Z1eUQTrWAx57RBbED58Xpj3AulMZDPCpy0rh8O7bYTSj5EODve5o8r Bc8QJJtH5FTrMM/eXzjOdHEtDyVgCI6aXIRadC1MB/0Cq0RLLZv6rLx+7TRDQSpwFm Tl1IbZYX4whSlnDkoT/qQ4c4Y13BPq6ioDL9N7W8= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-oa1-x2a.google.com (mail-oa1-x2a.google.com [IPv6:2001:4860:4864:20::2a]) by sourceware.org (Postfix) with ESMTPS id 88257385141E for ; Mon, 20 Mar 2023 16:01:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 88257385141E Received: by mail-oa1-x2a.google.com with SMTP id 586e51a60fabf-17aceccdcf6so13478166fac.9 for ; Mon, 20 Mar 2023 09:01:34 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; t=1679328093; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=3u64IfKotUugQPWp2zGSuWRQB0NGnN/Qd5x2UDx3jAE=; b=OMMRX3+zNEBPjLWbvJbLuCvcAix+lTyJLpYnEkk5VYGvD++3U9BqDizk45PVN8BcN/ J8yUjqSYUeDzPg5q0HHfWWSqGWddYT+e8GBlkTUYJamfdHTRO92nbLwV2+8aFQ8a5RMe v7Y9tV61sGGJPurelBp/MLdbJgLPCJUUoDfax232nOvbgoVZsdx03NBY/3TmlF4V6swq ISi0HRsh2UWrFg0aqYD4UjYc+mDUd+0awZuHAwOSJIV+9fZDFXLitck73Tr1SRFp5DRG FhTEYpz+5xU+Xf13r3+rebikzTUQWaYrB3OeQlfIS5C1vNam+JUT0EKv9Dhg/lFajsOm bq/w== X-Gm-Message-State: AO0yUKUBVA3mwAyeQNEP/KcMSgqhGXSmIZgFE5f2qmfFUZ02gVL4Q8RB C1bWgC3ZOGDfXCVjC5YNI4IEV1y7O7fj78cTe2vFEQ== X-Google-Smtp-Source: AK7set/zC5/plhRoHz0Uy7Avej39E2Xr9OBd13biaO/xXzauzhbqRjimkkCuRtraRDy8VM6T82n9iw== X-Received: by 2002:a05:6870:9581:b0:17a:aeff:5228 with SMTP id k1-20020a056870958100b0017aaeff5228mr5927097oao.47.1679328093135; Mon, 20 Mar 2023 09:01:33 -0700 (PDT) Received: from mandiga.. ([2804:1b3:a7c0:c260:e868:74cf:5638:4f8]) by smtp.gmail.com with ESMTPSA id ax35-20020a05687c022300b0017243edbe5bsm3355725oac.58.2023.03.20.09.01.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 20 Mar 2023 09:01:32 -0700 (PDT) To: libc-alpha@sourceware.org, Wilco Dijkstra , "H . J . Lu" Cc: kirill Subject: [PATCH v4 4/5] math: Improve fmodf Date: Mon, 20 Mar 2023 13:01:17 -0300 Message-Id: <20230320160118.352206-5-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230320160118.352206-1-adhemerval.zanella@linaro.org> References: <20230320160118.352206-1-adhemerval.zanella@linaro.org> MIME-Version: 1.0 X-Spam-Status: No, score=-12.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Adhemerval Zanella via Libc-alpha From: Adhemerval Zanella Netto Reply-To: Adhemerval Zanella Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org Sender: "Libc-alpha" This uses a new algorithm similar to already proposed earlier [1]. With x = mx * 2^ex and y = my * 2^ey (mx, my, ex, ey being integers), the simplest implementation is: mx * 2^ex == 2 * mx * 2^(ex - 1) while (ex > ey) { mx *= 2; --ex; mx %= my; } With mx/my being mantissa of double floating pointer, on each step the argument reduction can be improved 8 (which is sizeof of uint32_t minus MANTISSA_WIDTH plus the signal bit): while (ex > ey) { mx << 8; ex -= 8; mx %= my; } */ The implementation uses builtin clz and ctz, along with shifts to convert hx/hy back to doubles. Different than the original patch, this path assume modulo/divide operation is slow, so use multiplication with invert values. I see the following performance improvements using fmod benchtests (result only show the 'mean' result): Architecture | Input | master | patch -----------------|-----------------|----------|-------- x86_64 (Ryzen 9) | subnormals | 17.2549 | 12.0318 x86_64 (Ryzen 9) | normal | 85.4096 | 49.9641 x86_64 (Ryzen 9) | close-exponents | 19.1072 | 15.8224 aarch64 (N1) | subnormal | 10.2182 | 6.81778 aarch64 (N1) | normal | 60.0616 | 20.3667 aarch64 (N1) | close-exponents | 11.5256 | 8.39685 I also see similar improvements on arm-linux-gnueabihf when running on the N1 aarch64 chips, where it a lot of soft-fp implementation (for modulo, and multiplication): Architecture | Input | master | patch -----------------|-----------------|----------|-------- armhf (N1) | subnormal | 11.6662 | 10.8955 armhf (N1) | normal | 69.2759 | 34.1524 armhf (N1) | close-exponents | 13.6472 | 18.2131 Instead of using the math_private.h definitions, I used the math_config.h instead which is used on newer math implementations. Co-authored-by: kirill [1] https://sourceware.org/pipermail/libc-alpha/2020-November/119794.html Reviewed-by: Wilco Dijkstra --- math/libm-test-fmod.inc | 4 + sysdeps/ieee754/flt-32/e_fmodf.c | 228 ++++++++++++++++----------- sysdeps/ieee754/flt-32/math_config.h | 41 +++++ 3 files changed, 180 insertions(+), 93 deletions(-) diff --git a/math/libm-test-fmod.inc b/math/libm-test-fmod.inc index 8841c1332c..43376c3df2 100644 --- a/math/libm-test-fmod.inc +++ b/math/libm-test-fmod.inc @@ -213,6 +213,10 @@ static const struct test_ff_f_data fmod_test_data[] = TEST_ff_f (fmod, -0x1p127L, -0x3p-148L, -0x1p-147L, NO_INEXACT_EXCEPTION|ERRNO_UNCHANGED), TEST_ff_f (fmod, -0x1p127L, 0x3p-126L, -0x1p-125L, NO_INEXACT_EXCEPTION|ERRNO_UNCHANGED), TEST_ff_f (fmod, -0x1p127L, -0x3p-126L, -0x1p-125L, NO_INEXACT_EXCEPTION|ERRNO_UNCHANGED), + TEST_ff_f (fmod, 0x1.3a3e6p-127, 0x1.8b8338p-128, 0x1.d1f31p-129, NO_INEXACT_EXCEPTION|ERRNO_UNCHANGED), + TEST_ff_f (fmod, 0x1.3a3e6p-127, -0x1.8b8338p-128, 0x1.d1f31p-129, NO_INEXACT_EXCEPTION|ERRNO_UNCHANGED), + TEST_ff_f (fmod, -0x1.3a3e6p-127, 0x1.8b8338p-128, -0x1.d1f31p-129, NO_INEXACT_EXCEPTION|ERRNO_UNCHANGED), + TEST_ff_f (fmod, -0x1.3a3e6p-127, -0x1.8b8338p-128, -0x1.d1f31p-129, NO_INEXACT_EXCEPTION|ERRNO_UNCHANGED), #if !TEST_COND_binary32 TEST_ff_f (fmod, 0x1p1023L, 0x3p-1074L, 0x1p-1073L, NO_INEXACT_EXCEPTION|ERRNO_UNCHANGED), TEST_ff_f (fmod, 0x1p1023L, -0x3p-1074L, 0x1p-1073L, NO_INEXACT_EXCEPTION|ERRNO_UNCHANGED), diff --git a/sysdeps/ieee754/flt-32/e_fmodf.c b/sysdeps/ieee754/flt-32/e_fmodf.c index b71c4f754f..53db32cbe2 100644 --- a/sysdeps/ieee754/flt-32/e_fmodf.c +++ b/sysdeps/ieee754/flt-32/e_fmodf.c @@ -1,102 +1,144 @@ -/* e_fmodf.c -- float version of e_fmod.c. - */ - -/* - * ==================================================== - * Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved. - * - * Developed at SunPro, a Sun Microsystems, Inc. business. - * Permission to use, copy, modify, and distribute this - * software is freely granted, provided that this notice - * is preserved. - * ==================================================== - */ - -/* - * __ieee754_fmodf(x,y) - * Return x mod y in exact arithmetic - * Method: shift and subtract - */ +/* Floating-point remainder function. + Copyright (C) 2023 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ -#include -#include #include +#include +#include "math_config.h" + +/* With x = mx * 2^ex and y = my * 2^ey (mx, my, ex, ey being integers), the + simplest implementation is: + + mx * 2^ex == 2 * mx * 2^(ex - 1) -static const float one = 1.0, Zero[] = {0.0, -0.0,}; + while (ex > ey) + { + mx *= 2; + --ex; + mx %= my; + } + + With mx/my being mantissa of double floating pointer, on each step the + argument reduction can be improved 11 (which is sizeo of uint64_t minus + MANTISSA_WIDTH plus the signal bit): + + while (ex > ey) + { + mx << 11; + ex -= 11; + mx %= my; + } */ float __ieee754_fmodf (float x, float y) { - int32_t n,hx,hy,hz,ix,iy,sx,i; - - GET_FLOAT_WORD(hx,x); - GET_FLOAT_WORD(hy,y); - sx = hx&0x80000000; /* sign of x */ - hx ^=sx; /* |x| */ - hy &= 0x7fffffff; /* |y| */ - - /* purge off exception values */ - if(hy==0||(hx>=0x7f800000)|| /* y=0,or x not finite */ - (hy>0x7f800000)) /* or y is NaN */ - return (x*y)/(x*y); - if(hx>31]; /* |x|=|y| return x*0*/ - - /* determine ix = ilogb(x) */ - if(hx<0x00800000) { /* subnormal x */ - for (ix = -126,i=(hx<<8); i>0; i<<=1) ix -=1; - } else ix = (hx>>23)-127; - - /* determine iy = ilogb(y) */ - if(hy<0x00800000) { /* subnormal y */ - for (iy = -126,i=(hy<<8); i>=0; i<<=1) iy -=1; - } else iy = (hy>>23)-127; - - /* set up {hx,lx}, {hy,ly} and align y to x */ - if(ix >= -126) - hx = 0x00800000|(0x007fffff&hx); - else { /* subnormal x, shift x to normal */ - n = -126-ix; - hx = hx<= -126) - hy = 0x00800000|(0x007fffff&hy); - else { /* subnormal y, shift y to normal */ - n = -126-iy; - hy = hy<>31]; - hx = hz+hz; - } - } - hz=hx-hy; - if(hz>=0) {hx=hz;} - - /* convert back to floating value and restore the sign */ - if(hx==0) /* return sign(x)*0 */ - return Zero[(uint32_t)sx>>31]; - while(hx<0x00800000) { /* normalize x */ - hx = hx+hx; - iy -= 1; - } - if(iy>= -126) { /* normalize output */ - hx = ((hx-0x00800000)|((iy+127)<<23)); - SET_FLOAT_WORD(x,hx|sx); - } else { /* subnormal output */ - n = -126 - iy; - hx >>= n; - SET_FLOAT_WORD(x,hx|sx); - x *= one; /* create necessary signal */ - } - return x; /* exact output */ + uint32_t hx = asuint (x); + uint32_t hy = asuint (y); + + uint32_t sx = hx & SIGN_MASK; + /* Get |x| and |y|. */ + hx ^= sx; + hy &= ~SIGN_MASK; + + /* Special cases: + - If x or y is a Nan, NaN is returned. + - If x is an inifinity, a NaN is returned. + - If y is zero, Nan is returned. + - If x is +0/-0, and y is not zero, +0/-0 is returned. */ + if (__glibc_unlikely (hy == 0 || hx >= EXPONENT_MASK || hy > EXPONENT_MASK)) + return (x * y) / (x * y); + + if (__glibc_unlikely (hx <= hy)) + { + if (hx < hy) + return x; + return asfloat (sx); + } + + int ex = hx >> MANTISSA_WIDTH; + int ey = hy >> MANTISSA_WIDTH; + + /* Common case where exponents are close: ey >= -103 and |x/y| < 2^8, */ + if (__glibc_likely (ey > MANTISSA_WIDTH && ex - ey <= EXPONENT_WIDTH)) + { + uint64_t mx = (hx & MANTISSA_MASK) | (MANTISSA_MASK + 1); + uint64_t my = (hy & MANTISSA_MASK) | (MANTISSA_MASK + 1); + + uint32_t d = (ex == ey) ? (mx - my) : (mx << (ex - ey)) % my; + return make_float (d, ey - 1, sx); + } + + /* Special case, both x and y are subnormal. */ + if (__glibc_unlikely (ex == 0 && ey == 0)) + return asfloat (sx | hx % hy); + + /* Convert |x| and |y| to 'mx + 2^ex' and 'my + 2^ey'. Assume that hx is + not subnormal by conditions above. */ + uint32_t mx = get_mantissa (hx) | (MANTISSA_MASK + 1); + ex--; + + uint32_t my = get_mantissa (hy) | (MANTISSA_MASK + 1); + int lead_zeros_my = EXPONENT_WIDTH; + if (__glibc_likely (ey > 0)) + ey--; + else + { + my = hy; + lead_zeros_my = __builtin_clz (my); + } + + int tail_zeros_my = __builtin_ctz (my); + int sides_zeroes = lead_zeros_my + tail_zeros_my; + int exp_diff = ex - ey; + + int right_shift = exp_diff < tail_zeros_my ? exp_diff : tail_zeros_my; + my >>= right_shift; + exp_diff -= right_shift; + ey += right_shift; + + int left_shift = exp_diff < EXPONENT_WIDTH ? exp_diff : EXPONENT_WIDTH; + mx <<= left_shift; + exp_diff -= left_shift; + + mx %= my; + + if (__glibc_unlikely (mx == 0)) + return asfloat (sx); + + if (exp_diff == 0) + return make_float (mx, ey, sx); + + /* Assume modulo/divide operation is slow, so use multiplication with invert + values. */ + uint32_t inv_hy = UINT32_MAX / my; + while (exp_diff > sides_zeroes) { + exp_diff -= sides_zeroes; + uint32_t hd = (mx * inv_hy) >> (BIT_WIDTH - sides_zeroes); + mx <<= sides_zeroes; + mx -= hd * my; + while (__glibc_unlikely (mx > my)) + mx -= my; + } + uint32_t hd = (mx * inv_hy) >> (BIT_WIDTH - exp_diff); + mx <<= exp_diff; + mx -= hd * my; + while (__glibc_unlikely (mx > my)) + mx -= my; + + return make_float (mx, ey, sx); } libm_alias_finite (__ieee754_fmodf, __fmodf) diff --git a/sysdeps/ieee754/flt-32/math_config.h b/sysdeps/ieee754/flt-32/math_config.h index 23045f59d6..829430ea28 100644 --- a/sysdeps/ieee754/flt-32/math_config.h +++ b/sysdeps/ieee754/flt-32/math_config.h @@ -110,6 +110,47 @@ issignalingf_inline (float x) return 2 * (ix ^ 0x00400000) > 2 * 0x7fc00000UL; } +#define BIT_WIDTH 32 +#define MANTISSA_WIDTH 23 +#define EXPONENT_WIDTH 8 +#define MANTISSA_MASK 0x007fffff +#define EXPONENT_MASK 0x7f800000 +#define EXP_MANT_MASK 0x7fffffff +#define QUIET_NAN_MASK 0x00400000 +#define SIGN_MASK 0x80000000 + +static inline bool +is_nan (uint32_t x) +{ + return (x & EXP_MANT_MASK) > EXPONENT_MASK; +} + +static inline uint32_t +get_mantissa (uint32_t x) +{ + return x & MANTISSA_MASK; +} + +/* Convert integer number X, unbiased exponent EP, and sign S to double: + + result = X * 2^(EP+1 - exponent_bias) + + NB: zero is not supported. */ +static inline double +make_float (uint32_t x, int ep, uint32_t s) +{ + int lz = __builtin_clz (x) - EXPONENT_WIDTH; + x <<= lz; + ep -= lz; + + if (__glibc_unlikely (ep < 0 || x == 0)) + { + x >>= -ep; + ep = 0; + } + return asfloat (s + x + (ep << MANTISSA_WIDTH)); +} + #define NOINLINE __attribute__ ((noinline)) attribute_hidden float __math_oflowf (uint32_t);