Re: Pushing the `gnus-range-*' functions down into the C layer

[Stefan Monnier <monnier@iro.umontreal.ca>]

> Would anyone mind if I implemented the `gnus-range-*' functions in C for
> Emacs 24?  Gnus spends significant time on group entry/exit doing range
> handling/compressing/etc, and I think the functions are (slightly)
> generally useful.

I wouldn't rule it out, but I'm reluctant to move Elisp code to C for
the same kinds of reason Andy just gave.  Especially for such a thing as
range/interval algorithms where the best algorithm depends a fair bit on
the particular shape of your data.
OTOH, speeding up Elisp is not something I expect to happen soon
(although moving to lexical bindings is a step in the right direction).

Maybe once we have dyn-loading in place, Gnus can provide its own
C functions outside of Emacs's own C code.

> Gnus addresses articles by their number, so you have things like the
> "marked" list of articles that looks like
> (3 4 5 6 7 11 14 15 16 17 18)

What algorithm does Gnus use currently?  I guess you call `sort' and
then scan the list looking for contiguous points?  That would make it
O(n log n), which isn't too bad, but it also means that the C part of
the code is O(n log n) and the Elisp part is O(n), so the speed of Elisp
should not be a big issue.

> (or something).  To save loading/saving time, these are stored in the
> .newsrc.eld file as range structures, which look like this:

> ((3 . 7) 11 (14 . 18))

> To handle this, Gnus has a set of functions for computing
> intersections/differences/etc on the range structures.

Ah, so you don't just convert to/from lists of points to intervals, but
you also work directly on intervals.  What algorithms do you use there?
These should be O(n), right?  What do you know about the usual shape of
your data?  E.g. what's the expected difference between the smallest and
the largest element (if it's not too large, we could store them in
bitvectors and then provide bitwise or/and on bitvectors)?

> However, Emacs Lisp isn't really fast at doing this,

It's not fast at other things either ;-)


        Stefan