Re: Improving Gnus speed

[Dan Christensen <jdc@uwo.ca>]

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

> Dan Christensen <jdc@uwo.ca> writes:
>
>> Separate from that low-level cache, the sorting function could
>> probably annotate the thread tree and re-use that information
>> for all of the recursive sorts.  Or use a decorate-sort-undecorate
>> pattern. 
>
> It sounds possible, but peeking at the code, it doesn't seem trivial to
> do generally, since the user can compose their own composited sorting
> functions.  So the cache would have to be per
> article+sorting-function...  hm...

Re: caching:

I think caching mainly makes sense for the functions which require
traversing the thread tree: gnus-thread-sort-by-total-score and
gnus-thread-sort-by-most-recent-number and -date.  Are there
any others?  If these tucked away their result when called,
I imagine there would be a big savings.  Depending on the shape
of the tree, this would reduce sort key computation time from
somewhere between O(n log n) and O(n^2) to O(n).

Re: decorate-sort-undecorate (DSU):

Here for each article you create a key which is a list of the relevant
values.  For example, if the sort functions are

           '((not gnus-thread-sort-by-number)
             gnus-thread-sort-by-score))

then the key would be (-number score) [or maybe the reverse].  Then you
replace the list of threads with a list of pairs (key thread) and sort
on the keys.  This avoids recomputing the key each time an article needs
to be compared with another, which would reduce overhead a lot.  After
sorting, you make a pass through to extract the list of threads in
sorted order.

When computing the keys, if you traverse the threads from leaves to the
root, you can compute the keys quickly without needing to implement the
caching.

But I don't know what to do if the user implements their own sorting
function.  It would be easier if the interface was changed: instead
of providing a list of comparison functions, you provide a list of
functions which compute key values which are then compared using
the default emacs order.  Then we could always use DSU.  But maybe
it's not worth changing the interface for this?

Options:

(a) Try caching, and see if it is good enough.
(b) Use DSU when only built-in sort functions are used, and fall
back to existing behaviour?  (Complicates code to have a fall-back,
and also would have to assume that the user didn't redefine the
built-in functions.)
(c) Change the interface so DSU can always be used?

Dan