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

[Wojciech Meyer <wojciech.meyer@googlemail.com>]

Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

> 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.
>
> 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)
>
> (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.  However, Emacs
> Lisp isn't really fast at doing this, so if you exit from a group that
> needs lots (I mean *lots*) of range handling, you get an annoying wait
> while it sits there computing.
>
> So I'm proposing implementing a set of useful functions in C, like
> `range-memq', `range-add', `range-intersection' and stuff.
>
> Thoughts?

Hi,

In my opinion your algorithm might need to change, but that's maybe I
that I don't understand the problem domain correctly :). You don't
really need to care about ranges or intervals. You load them into array
of chars, each char index representing one article index and set to 0 or
1, if article was read. (ideally a bit array) Then at exit perform
operation at array in the same way as you loaded, and save it back to
ranges. It has linear complexity. You trade off space complexity for
computational complexity. As a bonus you get the minimal representation
in intervals. So I don't think you would need a specific core support
(but that's my personal opinion).  If you really want a clean solution,
then there are algorithms. (I know they exist, but unfortunately I don't
remember the name of it).

Just mine two cents,

Wojciech