[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Huge Bit Arrays

I have an application (an ATMS), which I am trying to tune for speed,
that uses lots (~1024) of huge (~2048) bit arrays.  The arrays should 
be able to grow dynamically as the system runs.  Portability is important.

Previously, I used make-array with unsigned-byte 1  and :adjustable T.
I did my own storage management, calling adjust-array on all array
instances when the array size was exceeded.  However, when I ported this
to a Common-Lisp SUN, a 100x decrease in speed was noted.  Apparently,
the SUN represents adjustable bit arrays using a cons for every bit,
and the system was dying under its own weight.

I was happy when I discovered section 2A:, p.110, "Infinite
Bit-vectors and Sets  Represented by Integers".  Using integers for
bit-vectors provides a clean interface, and should not suffer portability
problems.  However, when I transformed my code to use integers, 
the code benchmarked about 3x slower on the same Symbolics.

I am guessing that this is because the advantages seen in not having 
to store large amounts of empty space to the left of the most significant
bit, are outweighed by having to cons up new mega-integer space
every time an integer gets larger, which takes time.

Perhaps if I allocate the space first, I'll only get in trouble if the
integers get really large.  Is there any way to specify an integer 0
that is really an integer, but allocates 2048 bits of zeroed space?
[E.g., not (setq my-array 0), but (setq my-array (mega-zero 2048)]?

Alternatively, if I roll my own management system out of static
arrays and copy/exchange everything myself, is there a way to
explicitly tell the system that a given array is garbage
and should be collected?

Is there something analogous to resources in Common Lisp?

Does anyone have any tips on the "right" way to do this?

Thanks for the input,
   John Myers~~