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.
And it's much simpler to understand than the old code.
Passes 32-bit and 64-bit "make check". I don't have a machine that I can configure with 32-bit adigits and 16-bit mdigits (i.e., no "long long").
Brad
Afficher les réponses par date
On 2013-10-21, at 4:55 PM, Bradley Lucier lucier@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?
And it's much simpler to understand than the old code.
Passes 32-bit and 64-bit "make check". I don't have a machine that I can configure with 32-bit adigits and 16-bit mdigits (i.e., no "long long").
It also passes "make check" here, so I have committed your patch to the repo.
I wish there was a more substantial suite of unit tests, particularly for the numerical lib which has several intricate algorithms. There are some unit tests in tests/error.scm but they don't cover every function and special case. Would you be willing to create a unit test suite for the numerical lib which tests each function individually, and all the corner cases?
I have started the development of a unit test suite for the Gambit compiler backends. It is a bunch of small Scheme files testing individual primitive functions. Perhaps that can be a source of inspiration. You can try it like this:
cd gsc ./runtests.scm -c
Of course, I invite everyone to pitch in to build the test suite.
Marc
On 10/22/2013 10:48 AM, Marc Feeley wrote:
On 2013-10-21, at 4:55 PM, Bradley Lucier lucier@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
On 10/22/2013 10:48 AM, Marc Feeley wrote:
I wish there was a more substantial suite of unit tests, particularly for the numerical lib which has several intricate algorithms. There are some unit tests in tests/error.scm but they don't cover every function and special case. Would you be willing to create a unit test suite for the numerical lib which tests each function individually, and all the corner cases?
Willing?
How about every time I send a patch, I send a little test program for it.
For example, here's the final (cough, cough) patch in my series of patches for naive div. I refactored the code so that I could special case when you know the quotient can't be a bignum, because it's at most one mdigit long.
I'm not quite sure what a "unit test" is (yes, I've used the google), so feel free to offer guidance if you don't like my test file.
This patch passes "make check" and the test program I've included below with both 64-bit and 32-bit gambit. Performance (on a faster machine than last time) is after the signature.
Brad
For very small (one adigit) bignums, with a small fixnum quotient, done a million times; "naive-div-old" is 4.6.8, "naive-div-current" is what's currently in git head, and "naive-div-new" is the patched naive div; n is 1,000,000.
64-bit gambit:
(time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-current dividend divisor))) 193 ms real time 196 ms cpu time (196 user, 0 system) 33 collections accounting for 2 ms real time (0 user, 0 system) 160009984 bytes allocated no minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-new dividend divisor))) 162 ms real time 160 ms cpu time (160 user, 0 system) 26 collections accounting for 1 ms real time (4 user, 0 system) 128005808 bytes allocated no minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-old dividend divisor))) 244 ms real time 244 ms cpu time (244 user, 0 system) 45 collections accounting for 2 ms real time (0 user, 0 system) 224010144 bytes allocated no minor faults no major faults
32-bit gambit:
(time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-current dividend divisor))) 223 ms real time 220 ms cpu time (220 user, 0 system) 28 collections accounting for 3 ms real time (4 user, 0 system) 120007168 bytes allocated no minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-new dividend divisor))) 185 ms real time 184 ms cpu time (180 user, 4 system) 21 collections accounting for 1 ms real time (0 user, 0 system) 88005088 bytes allocated no minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-old dividend divisor))) 286 ms real time 284 ms cpu time (284 user, 0 system) 47 collections accounting for 3 ms real time (4 user, 0 system) 200025568 bytes allocated no minor faults no major faults
To divide two (roughly) 10,000 bit integers, with a small fixnum quotient, a million iterations:
64-bit gambit:
(time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-current dividend divisor))) 8871 ms real time 8844 ms cpu time (6472 user, 2372 system) 2591 collections accounting for 1237 ms real time (788 user, 396 system) 12688000000 bytes allocated 2911875 minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-new dividend divisor))) 8835 ms real time 8808 ms cpu time (6472 user, 2336 system) 2584 collections accounting for 1237 ms real time (728 user, 392 system) 12656000000 bytes allocated 2912144 minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-old dividend divisor))) 17879 ms real time 17816 ms cpu time (15832 user, 1984 system) 7712 collections accounting for 1220 ms real time (1036 user, 120 system) 37792000000 bytes allocated 2920757 minor faults no major faults
32-bit gambit:
(time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-current dividend divisor))) 18663 ms real time 18608 ms cpu time (17028 user, 1580 system) 2941 collections accounting for 905 ms real time (856 user, 84 system) 12616000000 bytes allocated 1931750 minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-new dividend divisor))) 19112 ms real time 19044 ms cpu time (17368 user, 1676 system) 2933 collections accounting for 989 ms real time (868 user, 52 system) 12584000000 bytes allocated 1935604 minor faults no major faults (time (do ((i 0 (fx+ i 1))) ((fx= i n)) (naive-div-old dividend divisor))) 40852 ms real time 40724 ms cpu time (39228 user, 1496 system) 8797 collections accounting for 1099 ms real time (980 user, 24 system) 37672000000 bytes allocated 1944579 minor faults no major faults
-
Bradley Lucier -
Marc Feeley