bool-vector implementation in the Emacs core

[Ted Zlatanov]

It looks like the current Emacs bool-vector implementation uses true
uncompressed bit vectors (bit strings).  For applications such as
Gnus, where bit ranges can be large, this is unnecessary.  Can there
be either an alternate implementation (bool-inversion-list) or an
alternate internal storage of bool-vectors in the Emacs C core?

I'm thinking, specifically, of either the Gnus ranges or inversion
lists.  Gnus ranges are like this:

(1 (6 . 8) 1000 (1500 . 1600) 2000)

Inversion lists store the number where the toggle occurs, so the
above example would be:

(1 2 6 8 1000 1001 1500 1600 2000 2001) [ or the equivalent vector ]

as an inversion list.  Inversion lists are faster for searching and
most other set operations (I heard about them in the context of
Unicode programming), while ranges are more intuitive to a human
reader.  I prefer inversion lists, personally - if something should
go in the core, it better be fast.  It won't be as fast as bit
strings, of course, but the difference in memory consumption should
be significant.

We're talking about implementations of ranges in the Gnus developer
list right now, and our implementations of ranges is written in
Lisp.  I can implement inversion lists in Lisp as well, but ranges
are such an essential Gnus piece that it seems like seeking core
support for them would be a good idea.

When dealing with vectors, we can preallocate a fixed number of slots
at the end of the vector to allow for growth or shrinkage of the
inversion list.  The empty slots can be contain the repetition of
the last value, or 0 as an out-of-band value.  I think a list-based
implementation is slightly better, though.

I did a search on this topic, but could not find anything.  I hope my
proposal is of interest to people other than Gnus developers (Unicode
coders, for instance).

Thanks
Ted