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
Afficher les réponses par date
On 2013-01-12, at 7:40 PM, Bradley Lucier lucier@math.purdue.edu wrote:
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.
After examining your program, I notice that the call to ##cons at the end of the code is in a loop (and is called 4 times). My guess is that you expected this call to ##cons to only happen once. This is probably because you did not nest your loops properly, so the call to ##cons which you expect to be a tail call, actually isn't.
Marc
ARGHHHH! I owe you. And since it's rare when I can pay you back with programming help, perhaps I can pay you back some other way.
Brad
On 01/16/2013 02:59 PM, Marc Feeley wrote:
On 2013-01-12, at 7:40 PM, Bradley Lucier lucier@math.purdue.edu wrote:
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.
After examining your program, I notice that the call to ##cons at the end of the code is in a loop (and is called 4 times). My guess is that you expected this call to ##cons to only happen once. This is probably because you did not nest your loops properly, so the call to ##cons which you expect to be a tail call, actually isn't.
Marc