[gambit-list] Another patch for naive-div
Bradley Lucier
lucier at math.purdue.edu
Fri Oct 25 19:48:35 EDT 2013
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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: div-test-1.scm
Type: text/x-scheme
Size: 1987 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20131025/07d59c25/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: _num-scm.patch
Type: text/x-patch
Size: 13738 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20131025/07d59c25/attachment-0001.bin>
More information about the Gambit-list
mailing list