[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