[Top][All Lists]

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

Re: bool-vector implementation in the Emacs core

From: Ted Zlatanov
Subject: Re: bool-vector implementation in the Emacs core
Date: Fri, 23 Jan 2004 15:26:53 -0500
User-agent: Gnus/5.110002 (No Gnus v0.2) Emacs/21.3.50 (usg-unix-v)

On Fri, 23 Jan 2004, address@hidden wrote:

> I'm not sure.  Emacs-unicode uses char-table for many
> things.  It is a pseudo array of 0..#x3FFFFF.  So, if
> indices fit in this range, you can use it not only for a
> character, but for any integer.

That's good to know, thanks.

> [a char-table] may consume more memory than ranges or inversion
> list, (aref tbl N) is quite faster than them.

Lookups are faster, sure (ignoring the effect of swapping because
you're using too much memory - that effect is very significant
sometimes).  Inversion lists are significantly faster in almost every
other set operation, though: initializing to the same value, union,
intersection, inversion.  They are slower near the worst case, where
every element is a toggle, so the length of the list is the same as
the length of the bit string - but in the more common case of sparse
ranges that we find in Gnus and Unicode programming, I would say
inversion lists will perform very well.

My suggestion was to implement a bool-vector that can use a inversion
list if suitable at the programmer's request, and maybe even convert
it to an alternate representation when necessary.  I would rather see
that than a new data type in Emacs Lisp (that was my alternate
suggestion, if the internal inversion list for a bool-vector is not


reply via email to

[Prev in Thread] Current Thread [Next in Thread]