Huge Bit Arrays

[barmar@Think.COM (Barry Margolin)]

    Date: Thu, 29 Mar 90 16:46:07+0900
    From: kddlab!atr-ln.atr.co.jp!myers@uunet.UU.NET (John K. Myers)

    I was happy when I discovered section 2A:7.4.8.1, 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)]?

No, this isn't the problem.  The problem is that integers are immutable,
so you have to cons a new bignum EVERY time you modify it, not just when
you grow it.  Allocating a huge 0 won't help because it will just become
garbage as soon as you set any bit.

Also, if your application needs adjustable arrays this implies that you
have multiple references to the same set.  If you use integers then you
won't get the right results; consider the following:

	(setq foo (make-bit-set))
	(setq bar foo)
	(setq foo (set-bit 23 foo))
	(bit-set-equal? foo bar)

If bit-sets are implemented using adjustable arrays then bit-set-equal?
should return true, while if they're implemented using integers it will
return nil because set-bit must return a different integer but bar still
points to the original integer.

If you don't need multiple references to work then you don't really need
adjustable arrays.  Any Common Lisp worthy of the name should be able to
implement simple bit vectors efficiently.

    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?

There are no portable interfaces to garbage collection.

    Is there something analogous to resources in Common Lisp?

No, but Lucid Common Lisp includes a resource facility very similar to
Symbolics's, and it should be relatively straightforward to implement a
portable resource facility yourself.

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

I think the best approach would be to implement a simple resource facility
                                                barmar