Re: Improving Gnus speed

[Dan Christensen <jdc@uwo.ca>]

Dan Christensen <jdc@uwo.ca> writes:

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

I've done some tests on the threads from a group I have with about 
6500 articles.  It takes about 1.6s to do the sorting step using
gnus-thread-sort-by-most-recent-date, and it turns out that the majority
of the time is taken by converting the dates from the string stored in
the header to an emacs time, i.e. the function gnus-date-get-time (and
what it calls).

Even though that function caches its result, I thought that it might be
worth caching the most-recent-date results too, since they currently
involve traversing all sub-threads of all threads.  But it turns out
that that would barely make any difference, at least for groups of
this size.

Here's how I determined this.  First, I saved the thread tree in a file,
so I could do isolated tests of just the sorting.  

Here's the total time required:

(benchmark-run 1 (gnus-sort-threads threads))
(1.638083 8 0.38992400000000016)  [The first number is the time in seconds.]

Now I get a fresh copy of threads, and do the latest-date computation on
all of the articles, using a maptree function I wrote:

(benchmark-run 1 (maptree (lambda (header) (gnus-date-get-time
					    (mail-header-date header))) 
			  threads))
(1.31202 4 0.2062689999999998)

That's 1.3 of the total 1.6 seconds right there.

If I do that again, without resetting threads, the time goes to near
zero, which shows how effective the caching of the date-conversion
results is:

(0.056382999999999996 0 0.0)

And now if we do the sort after having pre-computed the date-conversion,
it only takes about 0.3s!

(benchmark-run 1 (gnus-sort-threads threads))
(0.299614 1 0.0529029999999997)

The upshot is that about 1.3s is date conversion for each article, the
rest has to do with the latest-date traversal and the actual sorting.

In fact, further tests show that the latest-date sub-thread traversal
barely adds anything.

So there doesn't seem to be much point in adding caching for these
recursively defined sort functions.  To improve the speed here, what
needs to be done is to improve the speed of the date conversion.

Moreover, for me, other stages of preparing the summary buffer take
significantly longer, so it would be worth investigating these.

I should also note that I first did the timings yesterday, and got a
total time of 2.5s (reproducibly).  Then, 24 hours later, in the same
emacs, the total time was almost double that (reproducibly).  So I
started a fresh emacs, and got the times above (1.6s total).  Maybe this
has to do with emacs memory management?  In any case, the effect means
that the time varies by a factor of 3 or more, so tracking this down
would be another good way to speed up Gnus.

Dan