How much memory for bignum or other large data structure?

[Robert Elton Maas <REM%IMSSS@SAIL.Stanford.EDU>]

<RAM> Date: Thu, 16 Apr 1987  10:27 EDT
<RAM> From: Rob MacLachlan <RAM@C.CS.CMU.EDU>

<RAM> The problem with running out of storage has no special relation to
<RAM> bignums of course.  Some programs may require data structures larger
<RAM> than some implementations can support on a given hardware
<RAM> configuration.  This is a potential portability problem, but I see
<RAM> nothing that can be done about it.

I do. A program can be aware of how close it is getting to using all
available memory (address space, swap space, etc.) by means of calls
to the LISP (CL) system, and adjust its behaviour accordingly to avoid
actually reaching the absolute limit. In this way a program can
effective utilize virtually all the memory available on any given
machine at any given time, instead of setting some arbitrary portable
limit on memory usage which may be far below that actually available.

Several kinds of programs run better the more memory they actually
use. Examples are: (1) Sort/merge, the more data that can be sorted in
memory, the larger sorted-segments can be emitted from the first pass
and the fewer disk-passes needed to merge the sorted-segments into a
single sorted-segment; (2) Any planning/lookahead program such as game
playing or robotics, the more data that can be stored in a tree
structure or hash table representing choices already analyzed, the
further ahead the program can look without having to recompute the
same choices over and over again, and thus the better "intelligence"
the program can exhibit.

In addition to parameters on particular data types that determine
their limits because of internal representation, every LISP
implementation should provide a way for a running program to ask how
much memory is remaining not currently in use (or in a system with
different kinds of data in different kinds of memory, how much memory
of a particular kind is not currently not in use). A program could ask
once, and if the answer comes back too small then force a
garbage-collect-completion and ask again, and if the answer is still
too small the program truncates its expansion at that point.

This facility is crucial enough for the kinds of "artificial
intelligence" programs typical of LISP, and is trivial enough to
implement in the underlying LISP system and virtually impossible to
hack up by user-level programming, that it should be a *required*
feature of every implementation, i.e. should be in the CL standard.

<RAM> Perhaps Common Lisp should specify a minimum maximum size for bignums
<RAM> and require that an error be signalled if this is ever exceeded.  I
<RAM> would guess that a limit of a few thousand bits would meet every use
<RAM> except the most common, namely impressing non-lispers by typing 
<RAM> (FACT 1000) and getting screens full of digits.

If the limit is representational, then indeed an
implementation-dependent largest-size-allowed parameter should be
provided by the system. If the limit is due to total memory use, any
system query specifically regarding bignums would have to use the
memory-remaining information to compute the bignum-that-would-fit
information, to account for memory already used and hence not
available. For the factorial hack, the toplevel FACT function could
first approximate the factorial by logarithms, check to see whether
there is enough memory for that data, and if not then complain and
advise the user what the maximum workable argument to FACT currently is.

<DLA> Date: Thu, 16 Apr 87 12:29 EDT
<DLA> From: David L. Andre <DLA@DIAMOND.S4CC.Symbolics.COM>

<DLA> I always favored a pair of variables MOST-POSITIVE-BIGNUM and
<DLA> MOST-NEGATIVE-BIGNUM.   :-)

Of course if this is based on memory available, only one of the two
could exist at any time, and as soon as it existed it would contradict
itself because there'd be no room left for the bignum you really
wanted. (This explanation is in case anybody didn't fully get the joke.)

<STS> Date: Thu, 16 Apr 87 13:14:13 MDT
<STS> From: shebs%orion@cs.utah.edu (Stanley T. Shebs)

<STS> Here's a (serious) meta-proposal:  every type of potentially unbounded
<STS> size must have limit parameters.  This would include arrays of all types,
<STS> numbers (both floats and rationals), packages, random states,
<STS> compiled code, hash tables, and structures.  There wouldn't be any
<STS> need for a CONS-LIMIT, because individual conses are always the same
<STS> size, and a possible LIST-LIMIT would not be meaningful, because LIST
<STS> is (OR CONS NULL).

I second that proposal (see the first part of my message) with
amendment (clarification) that these limit parameters refer to
representation rather than memory available. For example, if BIGNUMs
are implemented in a recursive way, there may be no limit on their
size whatsoever other than memory available, and some extremely
gigantic but sparse BIGNUMs may in fact be representable while some
smaller ones that aren't sparse wouldn't; in such a case the limit
parameter would be INFINITY. But if the number-of-digits of a BIGNUM
is a FIXNUM, then there's an absolute representational limit which is
given in the proposed limit parameter. -- In addition to these limit
parameters, of course, is my proposal for runtime memory-not-yet-used query.

<STS> Right now the only limits are on arrays, fixnums, and floats, so
<STS> there would be a lot of extra parameters.

Yes, but compared to the total memory available the limit parameters
would be insignificant in size, thus no problem.

<DH> Date: 16 Apr 1987 14:19:04 EST (Thu)
<DH> From: Dan Hoey <hoey@nrl-aic.ARPA>

<DH> Simpler would be to use ARRAY-TOTAL-SIZE-LIMIT for this value.

I don't understand this proposal. If all arrays are stored in some
special place in memory, that limits their total size without being
affected by CONSs consuming memory elsewhere, that would make sense.
Or do you mean the total number of elements in a single array of
multiple dimensions (axes) because of a machine limit on the size of
an index register?  Please clarify?