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

[Lars Magne Ingebrigtsen <larsi@gnus.org>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> 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).

Actually, I think Emacs could do with moving more things down into the C
layer.  I mean, having en elisp implementation of sha1 is quite an
achievement, but linking with libgcrypt would have given you that and
much more.  Just to take a random example.

I don't think the C layer should be considered "second class".  I mean,
C isn't as nice as Lisp, but it's not like the C style in Emacs is less
maintainable than most Emacs-Lisp functions out there.  :-)

Anyway, back to the range functions.  I think it's slightly generally
useful.  My guess would be that if there was a faster
sorted-integer-list interface, it would be used by others with similar
needs.  `range-memq' would be much faster than `memq' on a list of
integers in most use cases.

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

Would that help much, though?  Anyway, that reminds me -- I think the
module support in XEmacs hurt XEmacs more than it helped.  You have to
program so very defensively because you don't know what packages are
installed by the user.  In Emacs, it's so much more productive
programming, because you can rely on all its bits being present.

> 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.

In general, the ranges come from the .newsrc.eld file, and are then
uncompressed before being worked on.  The lists are generally kept
sorted, so it's not necessary to re-sort them before compressing.

But I think you kinda underestimate how slow Emacs Lisp is compared to
C.  An O(n) function in Emacs Lisp can be slow enough to make it
unpleasant for the user.

> Ah, so you don't just convert to/from lists of points to intervals, but
> you also work directly on intervals.

At present, they're compressed and uncompressed, because memq is much
faster in the general use cases than the Lisp range-member functions.
But if range-memq was present in C, then I'd never uncompress.

> 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)?

It varies a bit.  The "read" range is usually on the form
`(1 . 24254214)', and this is (of course) never uncompressed.  But you'd
usually have additional ranges for, say, ticked, and these would be
quite sparse, like `(45 (90 . 96) (200 . 259))'  Or something like that.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen