[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://webmail.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://webmail.iro.umontreal.ca/pipermail/gambit-list/attachments/20131025/07d59c25/attachment-0001.bin 


More information about the Gambit-list mailing list