When I try this:
(defun fact (n)
(if (< n 2)
1
(let ((acc 1))
(dotimes (x n acc) (setf acc (* acc (1+ x)))))))
I get the right answers, but it takes a largish amount of memory-seems
to increase linearly with the value of n. If I try to calculate
100000! with this, cmucl chews away for a few minutes, spewing
increasingly dire warnings about how much memory it is eating, and then
crashes. This should be able to run in constant memory, shouldn't it?
On 22 May 2005 09:41:08 -0700, <···········@gmail.com> wrote:
>
> When I try this:
> (defun fact (n)
> (if (< n 2)
> 1
> (let ((acc 1))
> (dotimes (x n acc) (setf acc (* acc (1+ x)))))))
>
> I get the right answers, but it takes a largish amount of memory-seems
> to increase linearly with the value of n. If I try to calculate
> 100000! with this, cmucl chews away for a few minutes, spewing
> increasingly dire warnings about how much memory it is eating, and then
> crashes. This should be able to run in constant memory, shouldn't it?
With what version of CMUCL and how much RAM on your computer? I don't
crash, the GC messages show that during calculation, this costs about
40-60 M, with a slow growth to 90M. Then there is a number spew and
all is well.
--
With sufficient thrust, pigs fly fine.
On 22 May 2005 15:57:18 -0700, <···········@gmail.com> wrote:
>
> I run CVS release-18e-branch + minimal debian patches on a gentoo
> (kernel 2.6.8) and 1Gb of RAM
Newer kernel here: 2.6.11.8, 2.6.8 seemed to have problems that didn't
really clear up until 2.6.10.
Less RAM, system holds 1G, but VMware steals 250M full time.
CMUCL 19a, April binary snapshot.
---
I would suggest that you get a newer CMUCL.
--
With sufficient thrust, pigs fly fine.
>>>>> "matthewknox" == matthewknox <···········@gmail.com> writes:
matthewknox> I run CVS release-18e-branch + minimal debian patches on a gentoo
matthewknox> (kernel 2.6.8) and 1Gb of RAM
This version definitely has problems printing numbers that large. 19a
has this problem too, but a new bignum printer is available with the
later snapshots, and that should work better.
Ray
In article <························@g14g2000cwa.googlegroups.com>,
···········@gmail.com wrote:
> When I try this:
> (defun fact (n)
> (if (< n 2)
> 1
> (let ((acc 1))
> (dotimes (x n acc) (setf acc (* acc (1+ x)))))))
>
> I get the right answers, but it takes a largish amount of memory-seems
> to increase linearly with the value of n. If I try to calculate
> 100000! with this, cmucl chews away for a few minutes, spewing
> increasingly dire warnings about how much memory it is eating, and then
> crashes. This should be able to run in constant memory, shouldn't it?
The numbers are getting bigger...
* Rainer Joswig:
> The numbers are getting bigger...
Yes, but not that big. (fact 100000) is 456574 digits in base 10. I guess
the problem is printing the answer. CMUCL uses huge amount of memory when
printing big bignums.
apparently that is not the issue-cmucl does not seem to like assigning
(fact 100000) to a variable, either.
it seems that either dotimes or setf is leaking memory here-I ended up
with half a gig of memory eaten by this. The computed number itself is
large, but not that large.
Should I be using something other than dotimes? What is the generally
accepted way to deal with big datasets, and large numbers, in lisp?
From: Marco Baringer
Subject: Re: cmucl crashes on this at large values-why?
Date:
Message-ID: <m27jhrj6q7.fsf@soma.local>
···········@gmail.com writes:
> it seems that either dotimes or setf is leaking memory here-I ended up
> with half a gig of memory eaten by this. The computed number itself is
> large, but not that large.
no. on my cmucl most-positive-fixnum is 536870911, this means that
every time you add or subtract or multiply a number larger than that
you end up creating a _new_ bignum. calculating the factorial of
100000 requires creating an obscene amount of bignums, which explains
the constant creation of bignums and the huge memory usage.
--
-Marco
Ring the bells that still can ring.
Forget the perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: cmucl crashes on this at large values-why?
Date:
Message-ID: <87ekbyhnfi.fsf@qrnik.zagroda>
"Marco Baringer" <··@bese.it> writes:
> no. on my cmucl most-positive-fixnum is 536870911, this means that
> every time you add or subtract or multiply a number larger than that
> you end up creating a _new_ bignum. calculating the factorial of
> 100000 requires creating an obscene amount of bignums, which explains
> the constant creation of bignums and the huge memory usage.
It doesn't explain it; they should quickly become garbage.
A wild guess (disclaimer: I haven't checked whether I can reproduce
this behavior and I don't know how CMUCL is implemented): perhaps the
payload of bignums is allocated separately, and garbage collection
doesn't take this memory into account when determining whether it
should be triggered?
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
From: André Thieme
Subject: Re: cmucl crashes on this at large values-why?
Date:
Message-ID: <d6tu0m$ujb$1@ulric.tng.de>
···········@gmail.com schrieb:
> When I try this:
> (defun fact (n)
> (if (< n 2)
> 1
> (let ((acc 1))
> (dotimes (x n acc) (setf acc (* acc (1+ x)))))))
>
> I get the right answers, but it takes a largish amount of memory-seems
> to increase linearly with the value of n. If I try to calculate
> 100000! with this, cmucl chews away for a few minutes, spewing
> increasingly dire warnings about how much memory it is eating, and then
> crashes. This should be able to run in constant memory, shouldn't it?
On my gentoo it works with 19a and one gig of ram.
Only when I try to convert the result into a string cmucl runs out of
memory ;-)
Andr�
--