[gambit-list] Re: Re: Regarding garbage collection

Bradley Lucier lucier at math.purdue.edu
Thu Sep 10 12:35:53 EDT 2009


On Fri, 2009-09-11 at 00:32 +0900, Adrien Piérard wrote:
> 2009/9/11 Bradley Lucier <lucier at math.purdue.edu>:
> > Or home-grown extensible u8vectors?  Or strings (after configuring
> > with --enable-char-size=1)?  How many distinct "characters" are being
> > distinguished?
> 
> Warning: *Beware of the following question, for I should already be sleeping*
> Supposing I have an alphabet of 2 letters (to make things simple), I
> can code it with two bits.
> Despite the possible algorithmic and computational pain somehow, since
> we have bignums, how about encoding a string of this alphabet into a
> number, using bitwise operations?
> Appending a char to a string is a SHIFT of two bits, then an OR.
> Referencing should be a matter of LOG (to get the size), and then
> shifting and an AND 3.
> 
> I'm still awake enough to encode just 2 letters and not three on 2
> bits (for concatenating "01" to "00" would not work as expected).
> I guess that it relies on the representation of bignums in memory.
> 
> What would be such a misuse of bignums worth?

Bignums are not mutable at the "user" level, but they are mutable in the
internal implementation of course.

At one point I wrapped integers in operations that implemented mutable
sets of nonnegative integers (sets either with a finite number of
elements (nonnegative exact integers) or all but a finite number of
elements (negative exact integers)) as fixnum/bignum bitmaps.  The
ultimate extensible bit-vectors, to interpret as you wish.

The trouble is, such an implementation of sets of nonnegative integers
is efficient only if the chance of a bit being set in your application
is about 1/2.  If you have very sparse sets, or sets whose elements tend
to cluster, or any other kind of non-uniformity in your sets, other data
structures are much more efficient.  And if you keep adding elements on
the end, it's quite inefficient (you don't increase the size by 20% at a
time, you add 64 bits at a time; you'd probably want to start a set with
a sentinel element if you know how big it will be eventually).

If I remember correctly, Marc didn't think they were worth inserting
into the runtime. Perhaps I should resurrect them as an SRFI (but that's
*so* much work) or just dump the code into the dumping grounds (if I can
find it again).

Brad




More information about the Gambit-list mailing list