[gambit-list] Another patch for naive-div
Bradley Lucier
lucier at math.purdue.edu
Tue Oct 22 13:39:01 EDT 2013
On 10/22/2013 10:48 AM, Marc Feeley wrote:
>
> On 2013-10-21, at 4:55 PM, Bradley Lucier <lucier at math.purdue.edu> wrote:
>
>> Marc:
>>
>> This patch estimates the size of the quotient much more carefully (at the bit level); it also starts the computation with the first possible nonzero mdigit of the quotient. So it's faster in the very important case of small (but still bignum) dividend and divisor.
> Have you measured how much faster?
With
(define (time-test n)
(let* ((divisor (do ((i 1 (* i 2)))
((##bignum? i) (+ i 1))))
(dividend (+ (* divisor 3)
(quotient divisor 4))))
(pretty-print (list ##bignum.adigit-width
##bignum.mdigit-width
(##bignum.adigit-length dividend)
(##bignum.adigit-length divisor)))
(time (do ((i 0 (fx+ i 1)))
((fx= i n))
(naive-div-orig dividend divisor)))
(time (do ((i 0 (fx+ i 1)))
((fx= i n))
(naive-div-new dividend divisor)))))
(the quotient is 3) with a 32-bit gambit (64-bit adigits, 16-bit
mdigits) configured with
v4.7.0 20131009203852 x86_64-unknown-linux-gnu "./configure 'CC=gcc
-march=native -m32' '--enable-single-host'"
on a rather old
model name : Intel(R) Core(TM)2 Quad CPU Q8200 @ 2.33GHz
you get
> (time-test 1000000)
(64 16 1 1)
(time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-orig dividend divisor)))
1364 ms real time
1364 ms cpu time (1364 user, 0 system)
129 collections accounting for 25 ms real time (28 user, 0 system)
136034976 bytes allocated
no minor faults
no major faults
(time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-new dividend divisor)))
585 ms real time
584 ms cpu time (584 user, 0 system)
113 collections accounting for 21 ms real time (4 user, 0 system)
120029024 bytes allocated
no minor faults
no major faults
with a 64-bit gambit (64-bit adigits, 32-bit mdigits) configured with
v4.7.0 20131009203852 x86_64-unknown-linux-gnu "./configure 'CC=gcc
-march=native' '--enable-single-host'"
on the same machine you get
> (time-test 1000000)
(64 32 1 1)
(time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-orig dividend divisor)))
901 ms real time
900 ms cpu time (896 user, 4 system)
148 collections accounting for 30 ms real time (24 user, 0 system)
176026208 bytes allocated
no minor faults
no major faults
(time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-new dividend divisor)))
536 ms real time
536 ms cpu time (536 user, 0 system)
135 collections accounting for 27 ms real time (24 user, 0 system)
160028064 bytes allocated
no minor faults
no major faults
That's with the additional slight tweak in the included patch.
So that was almost a "brown paper bag" patch: for small quotients (fits
in an mdigit) and small dividends it's about twice as fast.
Brad
-------------- next part --------------
A non-text attachment was scrubbed...
Name: _num-scm.patch
Type: text/x-patch
Size: 1032 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20131022/8a185496/attachment.bin>
More information about the Gambit-list
mailing list