Date: Mon, 25 Nov 2024 19:24:32 +0000 From: bugzilla-noreply@freebsd.org To: standards@FreeBSD.org Subject: [Bug 275661] /usr/bin/dc really slow with a trivial calculation Message-ID: <bug-275661-99-kgJRM0qJKo@https.bugs.freebsd.org/bugzilla/> In-Reply-To: <bug-275661-99@https.bugs.freebsd.org/bugzilla/> References: <bug-275661-99@https.bugs.freebsd.org/bugzilla/>
next in thread | previous in thread | raw e-mail | index | archive | help
https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=3D275661 Stefan E=C3=9Fer <se@FreeBSD.org> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|New |Open --- Comment #4 from Stefan E=C3=9Fer <se@FreeBSD.org> --- 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.=
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?bug-275661-99-kgJRM0qJKo>