[Openmcl-devel] multiply and memory allocation optimization question

[Gary Byers]

On Sun, 25 Apr 2004, Cyrus Harmon wrote:

>
> Dear Openmcl-dev,
>
> I'm trying to figure out why following uses so much memory:
>
> ? (let ((acc 0)) (time (dotimes (i 10000) (incf acc (* i i)))) acc)
> (DOTIMES (I 10000) (INCF ACC (* I I))) took 15 milliseconds (0.015
> seconds) to run.
> Of that, 0 milliseconds (0.000 seconds) were spent in user mode
>           0 milliseconds (0.000 seconds) were spent in system mode
>           15 milliseconds (0.015 seconds) were spent executing other OS
> processes.
>   141,240 bytes of memory allocated.
> 333283335000
> ?

How much memory did you expect to be allocated ?

Why did you expect what you expected ?


>
> Short of using something like fp-ppc, is there a way to write this that
> won't result in so much memory being allocated? Can I force the
> evaluation of the * to be accumulated on a stack variable somehow?

The best solution to your problem is to use numbers with fewer significant
bits in them.  Sadly, this solution isn't always practical; some programming
languages (C, for instance) offer this solution regardless of whether or not
it leads to the correct answer.

In general, the product of 2 N-digit numbers is a 2N-digit number, and the
sum of 2 N-digit numbers is an N+1-digit number.  (Note that this differs
from the floating-point case, where the product/sum of two floats of the same
type is a float of the same type or an overflow condition.)

There are certainly cases where advising the compiler about the size
of (number of bits in) integer arithmetic operands and results can
help it to generate better code; saying:

(the fixnum (+ (the fixnum x) (the fixnum y)))

will cause the addition to compile to a single ADD instruction (and
the result will be correct if the type assertions are.)  Asserting
that operands/results will "fit" in a machine word - as in:

(the (unsigned-byte 32) (+ (the (unsigned-byte 32) x)
                           (the (unsigned-byte 32) y)))

- can avoid bignum consing in some cases (which cases win depend on
how the result is used as well as how big it is.)

Once we start talking about bignums, it's harder to say anything
useful or helpful: the number of bits needed to hold the value of
ACC during the execution of your example varies: at different points
in time, it can be represented as a lisp FIXNUM, as an unboxed machine
word, or as a BIGNUM.  It's generally not possible to preallocate
(on the stack or elsewher) a single type of integer and destructively
modify it.

One could imagine some other type of object - call it an INTEGER-BUFFER,
for want of a better name - that wasn't really an integer but which
held an integral value and which could be mapped to an integer.  If this
type of object supported destructive operations, one could imagine your
example being written as:


(let ((acc (allocate-integer-buffer 64)))  ; allocate a 64-bit "integer-buffer"
 (declare (dynamic-extent acc))            ; stack-allocate it, in fact
 (dotimes (i 10000) (add-to-ingeger-buffer acc (* i i)))
 (integer-from-integer-buffer  acc))

That's slightly more obscure code: you're no longer dealing with integers
exclusively and have to be able to anticipate the sizeo of the "integer-buffer"
you need.  On the other hand, it wouldn't allocate any memory for intermediate
results ...


>
> Thanks,
>
> Cyrus
>
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
>
>