From: Erik Naggum <naggum.no at erik>
   
   | > Basically I need to represent a mapping from the set of the n first
   | > positive integers to itself, with n ~= (expt 10 6).  I have try with
   | > an hash-table and with an array, but I run out of memory.
   | 
   | An array of the integers between 0-1,000,000 shouldn't be hard to
   | handle.  You should tell MAKE-ARRAY that you want to store small
   | integers (called 'fixnums', since they use only a fixed number of
   | bits).  So you would say:
   | 
   | (make-array (expt 10 6) :element-type 'fixnum)
   
   if this is under ACL for Windows, remember to check the values of
   MOST-POSITIVE-FIXNUM and ARRAY-DIMENSION-LIMIT.  IIRC, they are _tiny_.
   
ARRAY-DIMENSION-LIMIT is adequate and the size of the array should be
no problem.  But "mapping from the set of the n first positive
integers to itself, with n ~= (expt 10 6)" implies the integer array
elements will indeed be larger than the ((2^16)-1)
MOST-POSITIVE-FIXNUM, and ACLWin 3.* does not have a specialized array
type for integers larger than fixnums.  Therefore

   (make-array (expt 10 6) :element-type `(mod ,(expt 10 6)))

will return an unspecialized array, i.e. an (SIMPLE-ARRAY 1000000 T).
The objects stored in this array will be boxed bignums, and this will
consume several times more space than if the integer elements were
unboxed.

You could fake unboxed bignums by splitting the integers into two
parts, each no larger than a fixnum, and doubling the size of the
array (or possibly using a rank-2 array) and writing your own pseudo
AREF to do the conversions.  This will save a lot of space but will
likely improve performance only if the array elements are not accessed
a huge number of times.  The reason is that in addition to the
computations required to compose and decompose the integer components,
each AREF of an array of unboxed items usually requires boxing the
result; AREF on a boxed array need only return the already-boxed
element, which is faster and cons free.  So ephemeral consing behavior
using an unboxed array has to be weighed against the storage
efficiency.