Re: bool-vector implementation in the Emacs core

[Ted Zlatanov <tzz@lifelogs.com>]

On 23 Jan 2004, no-spam@cua.dk wrote:

> Ted Zlatanov <tzz@lifelogs.com> writes:
> 
>> 
>> 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.
> 
> What kind of C-level support are you looking for?

Something like a bool-vector, but internally implemented with an
inversion list.  A double-linked C list of integers is perfect, so you
can insert and delete quickly.  I can base it on the ELisp lists, I
was just hoping to make the bool-vector operations insanely fast :)

Now, there are two approaches - either provide an alternate internal
implementation of the bool-vector when you create it, or provide a
whole new data type.  I'd rather be able to make a bool-vector with
an inversion list internally.

> If you implement inversion lists with lists, I don't really think
> lookups or inserts will be significantly faster in C than in
> byte-compiled Elisp.

You may be right, I'm not familiar with the differences.  It seems to
me that a double-linked list in C that can only hold integers will be
significantly faster than the equivalent interpreted code using the
general-purpose ELisp lists.

> I do think that it would be a good idea to add the bool-vector
> support to the emacs lisp core files though, e.g. in subr.el.
> 
> What kind of API do you envision?

Same as bool-vector: aref, aset.  Also union, intersection, inversion,
etc. set operations would be nice.  With inversion lists those
operations are very simple.  Inversion, for instance - you just
precede the list with a 0, or delete the 0 if it's already there.

Thanks
Ted