[gambit-list] Little debugging help?

Bradley Lucier lucier at math.purdue.edu
Sat Jan 12 19:40:33 EST 2013


Marc:

I have some ideas for speeding up some of the algorithms in _num.scm, but my first attempt at something is going awry and I can't fathom it; I'm beginning to thing that there might be a compiler error (quelle horreur!), or an error in reporting how much memory is allocated.

I've written a new naive-div, called, oddly enough, naive-div-new, that is supposed to allocate much less memory when two large bignums of roughly the same size are divided.  It relies on a new routine, ##bignum.arithmetic-shift-into!.

naive-div-new has two new arguments, to say whether we want to keep (not overwrite) the dividend and whether we need a quotient.  If we don't need a quotient and we're allowed to overwrite the dividend, then I think the routine should allocate 24 bytes on a 64-bit machine with 32-bit mdigits.  It calls ##bignum.normalize!, but that doesn't allocate any memory.

However, time is reporting that 240 bytes are allocated.  Even accounting for the fact that time's report might double the number of bytes allocated, as explained in your previous e-mail, I don't see anywhere near 240 bytes allocated.

So, can you help a fella out here and tell me where I'm allocating this phantom memory?

Brad

Here's a script showing some issues:

> (load "formarc")
"/Users/lucier/programs/gambit/gambit-1/gambit/shift/formarc.o1"
> (define a (expt 2 250))
> (define b (expt 2 240))
> (define c (##bignum.make (##bignum.adigit-length a) a #f))
> (define d (##bignum.make (##bignum.adigit-length b) b #f))
> (time (naive-div-new c d #f #f))
(time (naive-div-new c d #f #f))
    0 ms real time
    0 ms cpu time (0 user, 0 system)
    no collections
    240 bytes allocated
    no minor faults
    no major faults
(#f . 0)
> (define result (##bignum.make 2 #f #f))
> (##bignum.normalize! (time (##bignum.arithmetic-shift-into! a -200 result)))
(time (##bignum.arithmetic-shift-into! a -200 result))
    0 ms real time
    0 ms cpu time (0 user, 0 system)
    no collections
    no bytes allocated
    no minor faults
    no major faults
1125899906842624

-------------- next part --------------
A non-text attachment was scrubbed...
Name: formarc.scm
Type: application/octet-stream
Size: 7837 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20130112/b3535bfe/attachment.obj>


More information about the Gambit-list mailing list