Huge Bit Arrays

[Qobi@ZERMATT.LCS.MIT.EDU (Jeffrey Mark Siskind)]

Why don't you use "Infinite Bit-vectors and Sets Represented by Integers"
(which I assume means bignums) and just set some high order bit to one.
That way you force the system to allocate a bignum of the size you want
and just ignore the extra bit. Whenever you want to grow an existing
bignum just pick an even higher order bit, set it to one and now you
can use all of the intervening bits (including the old high order bit
used to force the allocation) as data.

Anyway, I would expect that setting, clearing, and accessing bits in
a bignum would take longer than AREF on a bit array but who knows? I
guess it depends what the ratio of accessing to growing you program
requires.

Another idea which would work and presumably have portable and predictable
performance is as follows. Have a two level scheme where you have an
array of length say (1000) each of whose elements points to a bit
array of length 1000. Initially, the top level array has all NIL entries
except for the first one which points to a bit array. When you want to
grow the vectors, just allocate a new (nonadjustable) bit vector of length
1000 and store it in the next NIL slot in the top level array. Accessing
the bit vector requires only two levels of array access and should be only
marginally slower (2X-3X) than a normal AREF while growing a vector should
only take normal MAKE-ARRAY times since the array is nonadjustable, there
are no forwarding pointers, and there is no copying.
        Jeff