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

*To*: kddlab!atr-ln.atr.co.jp!myers@uunet.UU.NET, slug@Warbucks.AI.SRI.COM*Subject*: Huge Bit Arrays*From*: Qobi@ZERMATT.LCS.MIT.EDU (Jeffrey Mark Siskind)*Date*: Thu, 29 Mar 90 11:50:00 EST*Cc*: Qobi@AI.MIT.EDU*In-reply-to*: <9003290746.AA04684@atr-ln.atr.co.jp>

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

**References**:**Huge Bit Arrays***From:*kddlab!atr-ln.atr.co.jp!myers@uunet.UU.NET (John K. Myers)

- Prev by Date:
**Data bits across LGP2 stream** - Next by Date:
**Undoing a presentation deftype ..** - Previous by thread:
**Huge Bit Arrays** - Next by thread:
**Huge Bit Arrays** - Index(es):