From nobody Mon Nov 25 19:24:32 2024 X-Original-To: standards@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4Xxwcx0G7cz5f4vm for ; Mon, 25 Nov 2024 19:24:33 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R10" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4Xxwcw5TdYz4cPX for ; Mon, 25 Nov 2024 19:24:32 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1732562672; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=gK8Rm0eWaw9PJOfRU4w/8ltz/QNrHRQsoA+3kr3Pqk8=; b=fWNX2f60yA7mShINOx2REUsCJeRFnxtEF0fmYP71fOD7a6rAur098T4S9baFoQOaCkwxG3 Coioraw01z+Pudn7IN40LAkiUffRkjyVZuGNSMIbVWBB0t5aI2F640wJ8Kkuh+q1UOGl1K BNvOoF37LQ7NX4rQp3rjGVg64cQRDcFY0a5dxOeN8DrIajWx96hjeSQ+G8mj0XzLZl07HU Bl7SyasaW3cFGQvMQ69I+5thElvp1pNjwMkWr4rQdxlonUyoh8bj2BlNYf8EqBCQyHdBmu ePha4ISY3j4XVuAhyOm+1BdAo1hqY3L6W5IHz2ZJ09P9ti2AN0IX4vQZ9pmxfw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1732562672; a=rsa-sha256; cv=none; b=UxqS9yGuPDmWnRKv0H/L9cid7ZvBxkqb6HOGCP8X9TBMc1LJ8AIX5f6QcofYeuoPMMquEJ bQvlJfM+bhc0Nch8Phia6MYfL8+k/19AqxFwhCaoaAAPuVFZW5uwPQKigR0zur6kVvQukB 5ZNgcSXNZme35DOyZx+hESCi2wtp1bnoI9qSL9PXjhgfobdvXWub6KJ4lcV025Dq22m+76 FkCafZs1SU5AC9mFvRknyrxv4LFjYylrGTUmFLSJYGJn3pglMbEmFxy2wgOKwcclxRkpG4 sDhUX6MDi6FGyU23i8+UDBk5Tt7UuOCliX74+P3urKo0KYmFYdN8nnF8jbjwgg== Received: from kenobi.freebsd.org (kenobi.freebsd.org [IPv6:2610:1c1:1:606c::50:1d]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4Xxwcw560VzsmM for ; Mon, 25 Nov 2024 19:24:32 +0000 (UTC) (envelope-from bugzilla-noreply@freebsd.org) Received: from kenobi.freebsd.org ([127.0.1.5]) by kenobi.freebsd.org (8.15.2/8.15.2) with ESMTP id 4APJOWPR075647 for ; Mon, 25 Nov 2024 19:24:32 GMT (envelope-from bugzilla-noreply@freebsd.org) Received: (from www@localhost) by kenobi.freebsd.org (8.15.2/8.15.2/Submit) id 4APJOWWT075646 for standards@FreeBSD.org; Mon, 25 Nov 2024 19:24:32 GMT (envelope-from bugzilla-noreply@freebsd.org) X-Authentication-Warning: kenobi.freebsd.org: www set sender to bugzilla-noreply@freebsd.org using -f From: bugzilla-noreply@freebsd.org To: standards@FreeBSD.org Subject: [Bug 275661] /usr/bin/dc really slow with a trivial calculation Date: Mon, 25 Nov 2024 19:24:32 +0000 X-Bugzilla-Reason: AssignedTo X-Bugzilla-Type: changed X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: Base System X-Bugzilla-Component: standards X-Bugzilla-Version: 13.2-RELEASE X-Bugzilla-Keywords: X-Bugzilla-Severity: Affects Many People X-Bugzilla-Who: se@FreeBSD.org X-Bugzilla-Status: Open X-Bugzilla-Resolution: X-Bugzilla-Priority: --- X-Bugzilla-Assigned-To: standards@FreeBSD.org X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_status Message-ID: In-Reply-To: References: Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: https://bugs.freebsd.org/bugzilla/ Auto-Submitted: auto-generated List-Id: Standards compliance List-Archive: https://lists.freebsd.org/archives/freebsd-standards List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: freebsd-standards@freebsd.org Sender: owner-freebsd-standards@FreeBSD.org MIME-Version: 1.0 https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=3D275661 Stefan E=C3=9Fer changed: What |Removed |Added ---------------------------------------------------------------------------- Status|New |Open --- Comment #4 from Stefan E=C3=9Fer --- The reason for the long run-time is the precision of intermediate results, which is doubled for each sqare that is computed. Only the final result is truncated to the number of fractional digits given by "scale". Seems that GNU bc and dc behave similarly, but takes at least 10 times as l= ong. TBH, I do not understand why this high precision is required during the calculation. Limiting the scale of the intermediate results to four times t= hat of the final result does not appear to lead to different results, but takes only milliseconds instead of hours for the 2^27 case: diff --git a/contrib/bc/src/num.c b/contrib/bc/src/num.c index 83f84edb91fc..3ca8569ac52e 100644 --- a/contrib/bc/src/num.c +++ b/contrib/bc/src/num.c @@ -2164,6 +2164,8 @@ bc_num_p(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale) for (powrdx =3D a->scale; !(exp & 1); exp >>=3D 1) { powrdx <<=3D 1; + if (powrdx > scale * 4) + powrdx =3D scale * 4; assert(BC_NUM_RDX_VALID_NP(copy)); bc_num_mul(©, ©, ©, powrdx); } @@ -2186,6 +2188,8 @@ bc_num_p(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale) if (exp & 1) { resrdx +=3D powrdx; + if (resrdx > scale * 4) + resrdx =3D scale * 4; assert(BC_NUM_RDX_VALID(c)); assert(BC_NUM_RDX_VALID_NP(copy)); bc_num_mul(c, ©, c, resrdx); $ echo "16k 1.0000001 2 27^ ^ pq" | time dc 674530.4707410845593826 0,00 real 0,00 user 0,00 sys $ echo "16k 1.0000001 2 32^ ^ pq" | time dc 33732640224394636565435618255869697073648757344072857017852662008141\ 33288999890928354175057633500291961443834127786206338597551908514660\ 039786068330051950098862770779120895429155957796324.3657731486704926 0,00 real 0,00 user 0,00 sys $ ./tn -f; echo "16k 1.0000001 2 32^ ^ pq" | dc; ./tn -f=20 1732559461.212034429 33732640224394636565435618255869697073648757344072857017852662008141\ 33288999890928354175057633500291961443834127786206338597551908514660\ 039786068330051950098862770779120895429155957796324.3657731486704926 1732559461.213839029 $ echo "16k 1732559461.213839029 1732559461.212034429 - pq" | dc .001804600 For comparison the results for 2^20 using GNU dc: $ echo "16k 1.0000001 2 20^ ^ pq" | time /usr/local/bin/dc 1.1105524506031247 160,81 real 160,80 user 0,01 sys And with the unpatched FreeBSD dc: $ echo "16k 1.0000001 2 20^ ^ pq" | time dc-unpatched 1.1105524506031247 13,47 real 13,47 user 0,00 sys The limit of 4 times "scale" was chosen just to test the assumption that the excessive length of the intermediate results was the cause of the slow calculation. I have not made any attempt to identify the minimal scale value that guarantees correct results. While doubling the number of fractional di= gits for each sqare operation preserves all fractional digits of each intermedia= te result, I'm not convinced that there are pathological operands that actually require that precision. --=20 You are receiving this mail because: You are the assignee for the bug.=