faster gnus-thread-latest-date

faster gnus-thread-latest-date

[Dan Christensen]

The function gnus-thread-latest-date is used by
gnus-thread-sort-by-most-recent-date, and is very slow.  The current
code is:

(defun gnus-thread-latest-date (thread)
  "Return the highest article date in THREAD."
  (let ((previous-time 0))
    (apply 'max
	   (mapcar
	    (lambda (header)
	      (setq previous-time
		    (condition-case ()
			(gnus-float-time (mail-header-parse-date
					  (mail-header-date header)))
		      (error previous-time))))
	    (sort
	     (message-flatten-list thread)
	     (lambda (h1 h2)
	       (< (mail-header-number h1)
		  (mail-header-number h2))))))))

Since all that is desired is the latest date, I don't see why dates that
don't parse are replaced by the date of the article with the previous
number.  Why not just replace them with zero?  And if you do that, then
there is no need for a preliminary sort by number.  So I think the
following version should produce identical output:

(defun gnus-thread-latest-date (thread)
  "Return the highest article date in THREAD."
  (apply 'max
	 (mapcar
	  (lambda (header)
	    (condition-case ()
		(gnus-float-time (mail-header-parse-date
				  (mail-header-date header)))
	      (error 0)))
	  (message-flatten-list thread))))

Can someone check my logic?

In my tests, it is noticeable faster.  Can it be improved further?

I have papers on file for Gnus and Emacs, so feel free to apply
this change.

Dan

Re: faster gnus-thread-latest-date

[Dan Christensen]

Dan Christensen <jdc@uwo.ca> writes:

> In my tests, it is noticeable faster.  Can it be improved further?

Actually, in my tests it is only slightly faster.  Still, the code is
much simpler, so unless someone can think of a reason not to, I think
the change should be made (after someone else checks it over and tests
it).

However, I think there's an orthogonal change which could greatly
improve the sorting speed.  For a group I have with about 6000 messages
and maybe 1000 threads (?), gnus-thread-latest-date is called 31028
times, taking about 10.5 seconds in total.  If the output from
gnus-thread-latest-date was cached, that would reduce the number of
computations of this date by at least a factor of 5, and so would
greatly reduce the time needed to enter the summary buffer.

This is the classic situation where decorate-sort-undecorate is a big
win.  The comparison function is slow here and gets called O(n log n)
times, but if you make one pass through the list of threads ahead of
time and compute the information that needs to be compared, you only
need to do the computation O(n) times.

Also, because the sub-threads are recursively sorted, each article
participates in many sorts.

In a perfect world, we would change Gnus to do a
decorate-sort-undecorate for all sorts.  But this would probably require
a change to the user interface for sorting.  The user would supply a
list of functions that each take a single thread and produce a single
output of a standard type (string, int, float, etc), and then Gnus would
do a decorate step that precomputes the list of those values.  The
sorting step would sort based on the usual order for the precomputed
values.  But this is a big change, so it's not ideal.

Another option would be to cache the slow computations with the thread
while doing the sort.  I wasn't sure of the best way to do this, so I
made up another extra-header to temporarily store the date converted
to a float.  And the speed-up is amazing.  The sorting time goes from
about 10 seconds to under 1 second!  Here's the code I used:

The lambda in the original code has been factored out into a separate
function which checks whether the data has been cached:

(defun gnus-article-float-date (header)
  (let ((extra-header (mail-header-extra header)))
    (or (cdr (assq 'Float-Date extra-header))
	(let ((float-date (condition-case ()
			      (gnus-float-time (mail-header-parse-date
						(mail-header-date header)))
			    (error 0))))
	  (mail-header-set-extra header 
				 (cons `(Float-Date . ,float-date) extra-header))
	  float-date))))

(defun gnus-thread-latest-date (thread)
  "Return the highest article date in THREAD."
  (apply 'max
	 (mapcar 'gnus-article-float-date
		 (message-flatten-list thread))))

Can anyone see any problems with caching the data like this?

A more intrusive but more logical change would be to change the header
array to have one more entry, specifically for cached data.  But that's
more than I'd like to tackle.

Dan

Re: faster gnus-thread-latest-date

[Katsumi Yamaoka]

>>>>> In <87my1uiien.fsf@uwo.ca> Dan Christensen wrote:
> The function gnus-thread-latest-date is used by
> gnus-thread-sort-by-most-recent-date, and is very slow.  The current
> code is:
[...]
> Since all that is desired is the latest date, I don't see why dates that
> don't parse are replaced by the date of the article with the previous
> number.  Why not just replace them with zero?  And if you do that, then
> there is no need for a preliminary sort by number.  So I think the
> following version should produce identical output:
[...]

I also concluded neither the use of the previous date nor sorting
by the article number is useful.

>>>>> In <87hbs2yw7f.fsf@uwo.ca> Dan Christensen wrote:
[...]
> However, I think there's an orthogonal change which could greatly
> improve the sorting speed.
[...]
> Another option would be to cache the slow computations with the thread
> while doing the sort.  I wasn't sure of the best way to do this, so I
> made up another extra-header to temporarily store the date converted
> to a float.  And the speed-up is amazing.  The sorting time goes from
> about 10 seconds to under 1 second!  Here's the code I used:

> The lambda in the original code has been factored out into a separate
> function which checks whether the data has been cached:

> (defun gnus-article-float-date (header)
>   (let ((extra-header (mail-header-extra header)))
>     (or (cdr (assq 'Float-Date extra-header))
> 	(let ((float-date (condition-case ()
> 			      (gnus-float-time (mail-header-parse-date
> 						(mail-header-date header)))
> 			    (error 0))))
> 	  (mail-header-set-extra header
> 				 (cons `(Float-Date . ,float-date) extra-header))
> 	  float-date))))

> (defun gnus-thread-latest-date (thread)
>   "Return the highest article date in THREAD."
>   (apply 'max
> 	 (mapcar 'gnus-article-float-date
> 		 (message-flatten-list thread))))

> Can anyone see any problems with caching the data like this?
[...]

Great.  I tried this one and found no problem so far, except for
the subroutine name.  The gnus-article- prefix reminds me of an
article function in gnus-art.el.  Could it be changed into
something another?  And please provide the ChangeLog entry.

The Emacs 23.2 pretest will begin soon and we will be in feature
freeze.

Re: faster gnus-thread-latest-date

[Ted Zlatanov]

On Mon, 07 Dec 2009 22:35:16 -0500 Dan Christensen <jdc@uwo.ca> wrote: 

DC> A more intrusive but more logical change would be to change the header
DC> array to have one more entry, specifically for cached data.  But that's
DC> more than I'd like to tackle.

I like the mail header approach and hope it can be generalized and used
across all backends as you describe.  Regardless of the bigger change, I
think at least the sorting optimization makes change in the trunk if
Reiner is OK with it.

Ted

Re: faster gnus-thread-latest-date

[Dan Christensen]

It turns out that the time hog is parse-time-string.  If that were sped
up, it would benefit lots of other uses too.  Maybe it should be in C?

In the meantime, we can cache the data.  I'll be submitting a patch
tonight or tomorrow.

Dan

Re: faster gnus-thread-latest-date

[Dan Christensen]

I'm now thinking that caching the parsed time in "time value" format (a
pair of integers) rather than a float might be more useful, since many
parts of Gnus need this information.  For example, gnus-dd-mmm and
gnus-user-date take the date in this format to produce the summary
lines.  If the user is using dates for sorting and in summary lines,
then the slow part (parse-time-string) will only need to be done once.

But in looking around the code, I noticed the following discrepancies:

In gnus-thread-latest-date, the time value is computed using

  (mail-header-parse-date (mail-header-date header))

and mail-header-parse-date is an alias for ietf-drums-parse-date, which
is defined to be (apply 'encode-time (parse-time-string string)).

On the other hand, *every* other part of Gnus that needs to convert
a date string to a time value uses date-to-time, which is defined
to be

  (apply 'encode-time (parse-time-string
                       (timezone-make-date-arpa-standard date)))

The comments near the last one suggest that this makes conversion
more robust.  However, it is 3 times slower than the first way.

Since everywhere else in Gnus uses the slower way, and we're going to
cache the output anyways, I guess the right thing to do is to switch
gnus-thread-latest-date to use date-to-time as well.

Once this is done, is there any reason to keep ietf-drums-parse-date
around?  It's not used anywhere else in the code that I can see.

Dan

Re: faster gnus-thread-latest-date

[Dan Christensen]

[-- Attachment #1: Type: text/plain, Size: 1076 bytes --]

Dan Christensen <jdc@uwo.ca> writes:

> I'm now thinking that caching the parsed time in "time value" format (a
> pair of integers) rather than a float might be more useful, since many
> parts of Gnus need this information.  

It turns out that someone thought of this before, and implemented it as
gnus-date-get-time in gnus-util, which caches the emacs time value as a
text property on the date string that is being parsed!  Clever idea:  it
works more generally than my method and doesn't require api changes to
various functions.  So all I had to do was call this function in a few
places, and things are faster.  For a group with about 6000 articles,
the time for sorting with gnus-thread-sort-by-most-recent-date when from
about 12 seconds to 1 second, and the time for generating the summary
went from 8 seconds to 6 seconds.

The patch below includes a ChangeLog.  It also adds a message to
gnus-sort-threads if the recursive sort fails and it falls back to the
loop.  That could be useful debugging information when timing these
things.

Please test and apply.

Dan


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: latest-date.patch --]
[-- Type: text/x-diff, Size: 4368 bytes --]

Index: ChangeLog
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/ChangeLog,v
retrieving revision 7.2042
diff -u -r7.2042 ChangeLog
--- ChangeLog	2 Dec 2009 12:10:00 -0000	7.2042
+++ ChangeLog	11 Dec 2009 02:53:52 -0000
@@ -1,3 +1,12 @@
+2009-12-10  Dan Christensen  <jdc@uwo.ca>
+
+	* gnus-util.el (gnus-user-date): Use gnus-date-get-time.
+	(gnus-dd-mmm): Use gnus-date-get-time.
+	* gnus-sum.el (gnus-thread-latest-date): Use gnus-date-get-time and
+	simplify logic.
+	(gnus-summary-limit-to-age): Use gnus-date-get-time.
+	(gnus-sort-threads): emit message if gnus-sort-threads-loop used.
+
 2009-12-02  Katsumi Yamaoka  <yamaoka@jpl.org>
 
 	* lpath.el: Always bind default-file-name-coding-system for (S)XEmacs.
Index: gnus-util.el
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/gnus-util.el,v
retrieving revision 7.89
diff -u -r7.89 gnus-util.el
--- gnus-util.el	9 Sep 2009 10:42:27 -0000	7.89
+++ gnus-util.el	11 Dec 2009 02:53:52 -0000
@@ -455,10 +455,10 @@
 
 (defun gnus-user-date (messy-date)
   "Format the messy-date according to gnus-user-date-format-alist.
-Returns \"  ?  \" if there's bad input or if an other error occurs.
+Returns \"  ?  \" if there's bad input or if another error occurs.
 Input should look like this: \"Sun, 14 Oct 2001 13:34:39 +0200\"."
   (condition-case ()
-      (let* ((messy-date (gnus-float-time (safe-date-to-time messy-date)))
+      (let* ((messy-date (gnus-float-time (gnus-date-get-time messy-date)))
 	     (now (gnus-float-time))
 	     ;;If we don't find something suitable we'll use this one
 	     (my-format "%b %d '%y"))
@@ -477,7 +477,7 @@
 (defun gnus-dd-mmm (messy-date)
   "Return a string like DD-MMM from a big messy string."
   (condition-case ()
-      (format-time-string "%d-%b" (safe-date-to-time messy-date))
+      (format-time-string "%d-%b" (gnus-date-get-time messy-date))
     (error "  -   ")))
 
 (defmacro gnus-date-get-time (date)
Index: gnus-sum.el
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/gnus-sum.el,v
retrieving revision 7.245
diff -u -r7.245 gnus-sum.el
--- gnus-sum.el	30 Nov 2009 09:36:17 -0000	7.245
+++ gnus-sum.el	11 Dec 2009 02:53:58 -0000
@@ -4826,7 +4826,8 @@
 	  ;; Even after binding max-lisp-eval-depth, the recursive
 	  ;; sorter might fail for very long threads.  In that case,
 	  ;; try using a (less well-tested) non-recursive sorter.
-	  (error (gnus-sort-threads-loop
+	  (error (gnus-message 9 "Sorting threads with loop...")
+		 (gnus-sort-threads-loop
 		  threads (gnus-make-sort-function
 			   gnus-thread-sort-functions))))
       (gnus-message 8 "Sorting threads...done"))))
@@ -4993,22 +4994,17 @@
   "Sort threads such that the thread with the most recently dated article comes first."
   (> (gnus-thread-latest-date h1) (gnus-thread-latest-date h2)))
 
+; Since this is called not only to sort the top-level threads, but
+; also in recursive sorts to order the articles within a thread, each
+; article will be processed many times.  Thus it speeds things up
+; quite a bit to use gnus-date-get-time, which caches the time value.
 (defun gnus-thread-latest-date (thread)
   "Return the highest article date in THREAD."
-  (let ((previous-time 0))
-    (apply 'max
-	   (mapcar
-	    (lambda (header)
-	      (setq previous-time
-		    (condition-case ()
-			(gnus-float-time (mail-header-parse-date
-					  (mail-header-date header)))
-		      (error previous-time))))
-	    (sort
-	     (message-flatten-list thread)
-	     (lambda (h1 h2)
-	       (< (mail-header-number h1)
-		  (mail-header-number h2))))))))
+  (apply 'max
+	 (mapcar '(lambda (header) (gnus-float-time 
+				    (gnus-date-get-time
+				     (mail-header-date header))))
+		 (message-flatten-list thread))))
 
 (defun gnus-thread-total-score-1 (root)
   ;; This function find the total score of the thread below ROOT.
@@ -8232,9 +8228,7 @@
 	  (when (and (vectorp (gnus-data-header d))
 		     (setq date (mail-header-date (gnus-data-header d))))
 	    (setq is-younger (time-less-p
-			      (time-since (condition-case ()
-					      (date-to-time date)
-					    (error '(0 0))))
+			      (time-since (gnus-date-get-time date))
 			      cutoff))
 	    (when (if younger-p
 		      is-younger

Re: faster gnus-thread-latest-date

[Dan Christensen]

[-- Attachment #1: Type: text/plain, Size: 530 bytes --]

Here's another patch that I think should be applied.  When parsing a
date, it first tries parse-time-string, and only falls back to using
timezone-make-date-arpa-standard if parse-time-string gives an error.
This is about 4 times faster in my tests with good dates, and shaves
0.6s off of opening a summary buffer with 6000 articles.  I've cc'd 
Dave Love since I believe he introduced this.  If he can confirm that
the problematic dates he encountered triggered an error in
parse-time-string, then this patch should be ok.

Dan


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: time-date.patch --]
[-- Type: text/x-diff, Size: 1653 bytes --]

Index: time-date.el
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/time-date.el,v
retrieving revision 7.18
diff -u -r7.18 time-date.el
--- time-date.el	9 Sep 2009 09:31:35 -0000	7.18
+++ time-date.el	11 Dec 2009 22:02:32 -0000
@@ -97,19 +97,19 @@
 (autoload 'timezone-make-date-arpa-standard "timezone")
 
 ;;;###autoload
+;; `parse-time-string' isn't sufficiently general or robust.  It fails
+;; to grok some of the formats that timezone does (e.g. dodgy
+;; post-2000 stuff from some Elms) and either fails or returns bogus
+;; values.  timezone-make-date-arpa-standard should help.
 (defun date-to-time (date)
   "Parse a string DATE that represents a date-time and return a time value."
   (condition-case ()
-      (apply 'encode-time
-	     (parse-time-string
-	      ;; `parse-time-string' isn't sufficiently general or
-	      ;; robust.  It fails to grok some of the formats that
-	      ;; timezone does (e.g. dodgy post-2000 stuff from some
-	      ;; Elms) and either fails or returns bogus values.  Lars
-	      ;; reverted this change, but that loses non-trivially
-	      ;; often for me.  -- fx
-	      (timezone-make-date-arpa-standard date)))
-    (error (error "Invalid date: %s" date))))
+      (apply 'encode-time (parse-time-string date))
+    (error (condition-case ()
+	       (apply 'encode-time 
+		      (parse-time-string
+		       (timezone-make-date-arpa-standard date)))
+	     (error (error "Invalid date: %s" date))))))
 
 ;; Bit of a mess.  Emacs has float-time since at least 21.1.
 ;; This file is synced to Gnus, and XEmacs packages may have been written

Re: faster gnus-thread-latest-date

[Dan Christensen]

Dave Love <fx@gnu.org> writes:

> I don't know from where this was Cc'd, as I only got the Cc address
> without a To.

Sorry, it's from ding@gnus.org, which I read via
gmane.emacs.gnus.general.  That might have been put in the Newsgroups
header, but I understand why that might have been confusing.  This post
is the same.

> Dan Christensen <jdc@uwo.ca> writes:
>
>> Here's another patch that I think should be applied.  When parsing a
>> date, it first tries parse-time-string, and only falls back to using
>> timezone-make-date-arpa-standard if parse-time-string gives an error.
>> This is about 4 times faster in my tests with good dates, and shaves
>> 0.6s off of opening a summary buffer with 6000 articles.  I've cc'd 
>> Dave Love since I believe he introduced this.  If he can confirm that
>> the problematic dates he encountered triggered an error in
>> parse-time-string, then this patch should be ok.
>
> The comment says that parse-time-string can produce bogus results rather
> than fail.  I vaguely remember this was about getting silly results from
> two-digit dates around the millennium -- returning the epoch, I guess --
> but I don't know for sure.

Well, I guess we shouldn't apply the date-to-time patch then, although
it would be better if we really knew what the problem was and could fix
it without slowing things down by a factor of 4.

On the other hand, if the caching patch gets applied, then it shouldn't
matter too much in practise.  (The 0.6s above is with the caching patch
applied; the time difference would be *much* larger without the caching
patch.)

Dan

Re: faster gnus-thread-latest-date

[Dave Love]

Dan Christensen <jdc@uwo.ca> writes:

>> I don't know from where this was Cc'd, as I only got the Cc address
>> without a To.
>
> Sorry, it's from ding@gnus.org, which I read via
> gmane.emacs.gnus.general.  That might have been put in the Newsgroups
> header, but I understand why that might have been confusing.  This post
> is the same.

Sort of sorry from me.  I forget when I'm reading stuff at work that it
comes through the magnificent MS Exchange, which not only mangles
headers, but also bodies.  `Newsgroups' was actually there in the
original, so it wasn't Gnus' fault.

> Well, I guess we shouldn't apply the date-to-time patch then, although
> it would be better if we really knew what the problem was and could fix
> it without slowing things down by a factor of 4.

Sorry I didn't stash an example but, especially as I made the change on
2000-01-06, I'm pretty sure the problematic dates I found were just
double-digit years, though there are doubtless others.  Maybe it's
enough to check for nulls in (in?)appropriate places in the result of
parse-time-string?

Re: faster gnus-thread-latest-date

[Dan Christensen]

[-- Attachment #1: Type: text/plain, Size: 317 bytes --]

I'd just like to clarify the current thread by emphasizing that the
patch below is small and yet produces a very large speed-up.  I hope
that it can be tested and applied.

The context lines don't show that the last change is to the function
gnus-summary-limit-to-age.  The rest should be clear from the patch.

Dan


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: latest-date.patch --]
[-- Type: text/x-diff, Size: 4368 bytes --]

Index: ChangeLog
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/ChangeLog,v
retrieving revision 7.2042
diff -u -r7.2042 ChangeLog
--- ChangeLog	2 Dec 2009 12:10:00 -0000	7.2042
+++ ChangeLog	11 Dec 2009 02:53:52 -0000
@@ -1,3 +1,12 @@
+2009-12-10  Dan Christensen  <jdc@uwo.ca>
+
+	* gnus-util.el (gnus-user-date): Use gnus-date-get-time.
+	(gnus-dd-mmm): Use gnus-date-get-time.
+	* gnus-sum.el (gnus-thread-latest-date): Use gnus-date-get-time and
+	simplify logic.
+	(gnus-summary-limit-to-age): Use gnus-date-get-time.
+	(gnus-sort-threads): emit message if gnus-sort-threads-loop used.
+
 2009-12-02  Katsumi Yamaoka  <yamaoka@jpl.org>
 
 	* lpath.el: Always bind default-file-name-coding-system for (S)XEmacs.
Index: gnus-util.el
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/gnus-util.el,v
retrieving revision 7.89
diff -u -r7.89 gnus-util.el
--- gnus-util.el	9 Sep 2009 10:42:27 -0000	7.89
+++ gnus-util.el	11 Dec 2009 02:53:52 -0000
@@ -455,10 +455,10 @@
 
 (defun gnus-user-date (messy-date)
   "Format the messy-date according to gnus-user-date-format-alist.
-Returns \"  ?  \" if there's bad input or if an other error occurs.
+Returns \"  ?  \" if there's bad input or if another error occurs.
 Input should look like this: \"Sun, 14 Oct 2001 13:34:39 +0200\"."
   (condition-case ()
-      (let* ((messy-date (gnus-float-time (safe-date-to-time messy-date)))
+      (let* ((messy-date (gnus-float-time (gnus-date-get-time messy-date)))
 	     (now (gnus-float-time))
 	     ;;If we don't find something suitable we'll use this one
 	     (my-format "%b %d '%y"))
@@ -477,7 +477,7 @@
 (defun gnus-dd-mmm (messy-date)
   "Return a string like DD-MMM from a big messy string."
   (condition-case ()
-      (format-time-string "%d-%b" (safe-date-to-time messy-date))
+      (format-time-string "%d-%b" (gnus-date-get-time messy-date))
     (error "  -   ")))
 
 (defmacro gnus-date-get-time (date)
Index: gnus-sum.el
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/gnus-sum.el,v
retrieving revision 7.245
diff -u -r7.245 gnus-sum.el
--- gnus-sum.el	30 Nov 2009 09:36:17 -0000	7.245
+++ gnus-sum.el	11 Dec 2009 02:53:58 -0000
@@ -4826,7 +4826,8 @@
 	  ;; Even after binding max-lisp-eval-depth, the recursive
 	  ;; sorter might fail for very long threads.  In that case,
 	  ;; try using a (less well-tested) non-recursive sorter.
-	  (error (gnus-sort-threads-loop
+	  (error (gnus-message 9 "Sorting threads with loop...")
+		 (gnus-sort-threads-loop
 		  threads (gnus-make-sort-function
 			   gnus-thread-sort-functions))))
       (gnus-message 8 "Sorting threads...done"))))
@@ -4993,22 +4994,17 @@
   "Sort threads such that the thread with the most recently dated article comes first."
   (> (gnus-thread-latest-date h1) (gnus-thread-latest-date h2)))
 
+; Since this is called not only to sort the top-level threads, but
+; also in recursive sorts to order the articles within a thread, each
+; article will be processed many times.  Thus it speeds things up
+; quite a bit to use gnus-date-get-time, which caches the time value.
 (defun gnus-thread-latest-date (thread)
   "Return the highest article date in THREAD."
-  (let ((previous-time 0))
-    (apply 'max
-	   (mapcar
-	    (lambda (header)
-	      (setq previous-time
-		    (condition-case ()
-			(gnus-float-time (mail-header-parse-date
-					  (mail-header-date header)))
-		      (error previous-time))))
-	    (sort
-	     (message-flatten-list thread)
-	     (lambda (h1 h2)
-	       (< (mail-header-number h1)
-		  (mail-header-number h2))))))))
+  (apply 'max
+	 (mapcar '(lambda (header) (gnus-float-time 
+				    (gnus-date-get-time
+				     (mail-header-date header))))
+		 (message-flatten-list thread))))
 
 (defun gnus-thread-total-score-1 (root)
   ;; This function find the total score of the thread below ROOT.
@@ -8232,9 +8228,7 @@
 	  (when (and (vectorp (gnus-data-header d))
 		     (setq date (mail-header-date (gnus-data-header d))))
 	    (setq is-younger (time-less-p
-			      (time-since (condition-case ()
-					      (date-to-time date)
-					    (error '(0 0))))
+			      (time-since (gnus-date-get-time date))
 			      cutoff))
 	    (when (if younger-p
 		      is-younger

Re: faster gnus-thread-latest-date

[Dan Christensen]

[-- Attachment #1: Type: text/plain, Size: 418 bytes --]

Any chance someone could apply this patch?

Dan

Dan Christensen <jdc@uwo.ca> writes:

> I'd just like to clarify the current thread by emphasizing that the
> patch below is small and yet produces a very large speed-up.  I hope
> that it can be tested and applied.
>
> The context lines don't show that the last change is to the function
> gnus-summary-limit-to-age.  The rest should be clear from the patch.
>
> Dan


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: latest-date.patch --]
[-- Type: text/x-diff, Size: 4368 bytes --]

Index: ChangeLog
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/ChangeLog,v
retrieving revision 7.2042
diff -u -r7.2042 ChangeLog
--- ChangeLog	2 Dec 2009 12:10:00 -0000	7.2042
+++ ChangeLog	11 Dec 2009 02:53:52 -0000
@@ -1,3 +1,12 @@
+2009-12-10  Dan Christensen  <jdc@uwo.ca>
+
+	* gnus-util.el (gnus-user-date): Use gnus-date-get-time.
+	(gnus-dd-mmm): Use gnus-date-get-time.
+	* gnus-sum.el (gnus-thread-latest-date): Use gnus-date-get-time and
+	simplify logic.
+	(gnus-summary-limit-to-age): Use gnus-date-get-time.
+	(gnus-sort-threads): emit message if gnus-sort-threads-loop used.
+
 2009-12-02  Katsumi Yamaoka  <yamaoka@jpl.org>
 
 	* lpath.el: Always bind default-file-name-coding-system for (S)XEmacs.
Index: gnus-util.el
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/gnus-util.el,v
retrieving revision 7.89
diff -u -r7.89 gnus-util.el
--- gnus-util.el	9 Sep 2009 10:42:27 -0000	7.89
+++ gnus-util.el	11 Dec 2009 02:53:52 -0000
@@ -455,10 +455,10 @@
 
 (defun gnus-user-date (messy-date)
   "Format the messy-date according to gnus-user-date-format-alist.
-Returns \"  ?  \" if there's bad input or if an other error occurs.
+Returns \"  ?  \" if there's bad input or if another error occurs.
 Input should look like this: \"Sun, 14 Oct 2001 13:34:39 +0200\"."
   (condition-case ()
-      (let* ((messy-date (gnus-float-time (safe-date-to-time messy-date)))
+      (let* ((messy-date (gnus-float-time (gnus-date-get-time messy-date)))
 	     (now (gnus-float-time))
 	     ;;If we don't find something suitable we'll use this one
 	     (my-format "%b %d '%y"))
@@ -477,7 +477,7 @@
 (defun gnus-dd-mmm (messy-date)
   "Return a string like DD-MMM from a big messy string."
   (condition-case ()
-      (format-time-string "%d-%b" (safe-date-to-time messy-date))
+      (format-time-string "%d-%b" (gnus-date-get-time messy-date))
     (error "  -   ")))
 
 (defmacro gnus-date-get-time (date)
Index: gnus-sum.el
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/gnus-sum.el,v
retrieving revision 7.245
diff -u -r7.245 gnus-sum.el
--- gnus-sum.el	30 Nov 2009 09:36:17 -0000	7.245
+++ gnus-sum.el	11 Dec 2009 02:53:58 -0000
@@ -4826,7 +4826,8 @@
 	  ;; Even after binding max-lisp-eval-depth, the recursive
 	  ;; sorter might fail for very long threads.  In that case,
 	  ;; try using a (less well-tested) non-recursive sorter.
-	  (error (gnus-sort-threads-loop
+	  (error (gnus-message 9 "Sorting threads with loop...")
+		 (gnus-sort-threads-loop
 		  threads (gnus-make-sort-function
 			   gnus-thread-sort-functions))))
       (gnus-message 8 "Sorting threads...done"))))
@@ -4993,22 +4994,17 @@
   "Sort threads such that the thread with the most recently dated article comes first."
   (> (gnus-thread-latest-date h1) (gnus-thread-latest-date h2)))
 
+; Since this is called not only to sort the top-level threads, but
+; also in recursive sorts to order the articles within a thread, each
+; article will be processed many times.  Thus it speeds things up
+; quite a bit to use gnus-date-get-time, which caches the time value.
 (defun gnus-thread-latest-date (thread)
   "Return the highest article date in THREAD."
-  (let ((previous-time 0))
-    (apply 'max
-	   (mapcar
-	    (lambda (header)
-	      (setq previous-time
-		    (condition-case ()
-			(gnus-float-time (mail-header-parse-date
-					  (mail-header-date header)))
-		      (error previous-time))))
-	    (sort
-	     (message-flatten-list thread)
-	     (lambda (h1 h2)
-	       (< (mail-header-number h1)
-		  (mail-header-number h2))))))))
+  (apply 'max
+	 (mapcar '(lambda (header) (gnus-float-time 
+				    (gnus-date-get-time
+				     (mail-header-date header))))
+		 (message-flatten-list thread))))
 
 (defun gnus-thread-total-score-1 (root)
   ;; This function find the total score of the thread below ROOT.
@@ -8232,9 +8228,7 @@
 	  (when (and (vectorp (gnus-data-header d))
 		     (setq date (mail-header-date (gnus-data-header d))))
 	    (setq is-younger (time-less-p
-			      (time-since (condition-case ()
-					      (date-to-time date)
-					    (error '(0 0))))
+			      (time-since (gnus-date-get-time date))
 			      cutoff))
 	    (when (if younger-p
 		      is-younger

Re: faster gnus-thread-latest-date

[Reiner Steib]

On Sat, Jan 02 2010, Dan Christensen wrote:

> Any chance someone could apply this patch?
>
> Dan
>
> Dan Christensen <jdc@uwo.ca> writes:
>
>> I'd just like to clarify the current thread by emphasizing that the
>> patch below is small and yet produces a very large speed-up.  I hope
>> that it can be tested and applied.
>>
>> The context lines don't show that the last change is to the function
>> gnus-summary-limit-to-age.  The rest should be clear from the patch.

Emacs is in pretest for 23.2 now and Gnus is synched manually to the
Emacs repository.

In fact we should probably create a branch for Gnus 5.13 (Emacs 23)
and install non-bugfixes on the trunk.  But that's for Lars to decide.

Bye, Reiner.

[ Resent via mail. Sorry if the posting thru Gmane arrives too. ]
-- 
       ,,,
      (o o)
---ooO-(_)-Ooo---  |  PGP key available  |  http://rsteib.home.pages.de/

Re: faster gnus-thread-latest-date

[Dan Christensen]

[-- Attachment #1: Type: text/plain, Size: 542 bytes --]

Dan Christensen <jdc@uwo.ca> writes:

> I'd just like to clarify the current thread by emphasizing that the
> patch below is small and yet produces a very large speed-up.  I hope
> that it can be tested and applied.
>
> The context lines don't show that the last change is to the function
> gnus-summary-limit-to-age.  The rest should be clear from the patch.

Are we still in pre-test, or would it be reasonable to apply the patch
below?  I've been using it for more than 5 months without a problem.
Let me know if I should rebase it.

Dan


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: latest-date.patch --]
[-- Type: text/x-diff, Size: 4368 bytes --]

Index: ChangeLog
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/ChangeLog,v
retrieving revision 7.2042
diff -u -r7.2042 ChangeLog
--- ChangeLog	2 Dec 2009 12:10:00 -0000	7.2042
+++ ChangeLog	11 Dec 2009 02:53:52 -0000
@@ -1,3 +1,12 @@
+2009-12-10  Dan Christensen  <jdc@uwo.ca>
+
+	* gnus-util.el (gnus-user-date): Use gnus-date-get-time.
+	(gnus-dd-mmm): Use gnus-date-get-time.
+	* gnus-sum.el (gnus-thread-latest-date): Use gnus-date-get-time and
+	simplify logic.
+	(gnus-summary-limit-to-age): Use gnus-date-get-time.
+	(gnus-sort-threads): emit message if gnus-sort-threads-loop used.
+
 2009-12-02  Katsumi Yamaoka  <yamaoka@jpl.org>
 
 	* lpath.el: Always bind default-file-name-coding-system for (S)XEmacs.
Index: gnus-util.el
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/gnus-util.el,v
retrieving revision 7.89
diff -u -r7.89 gnus-util.el
--- gnus-util.el	9 Sep 2009 10:42:27 -0000	7.89
+++ gnus-util.el	11 Dec 2009 02:53:52 -0000
@@ -455,10 +455,10 @@
 
 (defun gnus-user-date (messy-date)
   "Format the messy-date according to gnus-user-date-format-alist.
-Returns \"  ?  \" if there's bad input or if an other error occurs.
+Returns \"  ?  \" if there's bad input or if another error occurs.
 Input should look like this: \"Sun, 14 Oct 2001 13:34:39 +0200\"."
   (condition-case ()
-      (let* ((messy-date (gnus-float-time (safe-date-to-time messy-date)))
+      (let* ((messy-date (gnus-float-time (gnus-date-get-time messy-date)))
 	     (now (gnus-float-time))
 	     ;;If we don't find something suitable we'll use this one
 	     (my-format "%b %d '%y"))
@@ -477,7 +477,7 @@
 (defun gnus-dd-mmm (messy-date)
   "Return a string like DD-MMM from a big messy string."
   (condition-case ()
-      (format-time-string "%d-%b" (safe-date-to-time messy-date))
+      (format-time-string "%d-%b" (gnus-date-get-time messy-date))
     (error "  -   ")))
 
 (defmacro gnus-date-get-time (date)
Index: gnus-sum.el
===================================================================
RCS file: /usr/local/cvsroot/gnus/lisp/gnus-sum.el,v
retrieving revision 7.245
diff -u -r7.245 gnus-sum.el
--- gnus-sum.el	30 Nov 2009 09:36:17 -0000	7.245
+++ gnus-sum.el	11 Dec 2009 02:53:58 -0000
@@ -4826,7 +4826,8 @@
 	  ;; Even after binding max-lisp-eval-depth, the recursive
 	  ;; sorter might fail for very long threads.  In that case,
 	  ;; try using a (less well-tested) non-recursive sorter.
-	  (error (gnus-sort-threads-loop
+	  (error (gnus-message 9 "Sorting threads with loop...")
+		 (gnus-sort-threads-loop
 		  threads (gnus-make-sort-function
 			   gnus-thread-sort-functions))))
       (gnus-message 8 "Sorting threads...done"))))
@@ -4993,22 +4994,17 @@
   "Sort threads such that the thread with the most recently dated article comes first."
   (> (gnus-thread-latest-date h1) (gnus-thread-latest-date h2)))
 
+; Since this is called not only to sort the top-level threads, but
+; also in recursive sorts to order the articles within a thread, each
+; article will be processed many times.  Thus it speeds things up
+; quite a bit to use gnus-date-get-time, which caches the time value.
 (defun gnus-thread-latest-date (thread)
   "Return the highest article date in THREAD."
-  (let ((previous-time 0))
-    (apply 'max
-	   (mapcar
-	    (lambda (header)
-	      (setq previous-time
-		    (condition-case ()
-			(gnus-float-time (mail-header-parse-date
-					  (mail-header-date header)))
-		      (error previous-time))))
-	    (sort
-	     (message-flatten-list thread)
-	     (lambda (h1 h2)
-	       (< (mail-header-number h1)
-		  (mail-header-number h2))))))))
+  (apply 'max
+	 (mapcar '(lambda (header) (gnus-float-time 
+				    (gnus-date-get-time
+				     (mail-header-date header))))
+		 (message-flatten-list thread))))
 
 (defun gnus-thread-total-score-1 (root)
   ;; This function find the total score of the thread below ROOT.
@@ -8232,9 +8228,7 @@
 	  (when (and (vectorp (gnus-data-header d))
 		     (setq date (mail-header-date (gnus-data-header d))))
 	    (setq is-younger (time-less-p
-			      (time-since (condition-case ()
-					      (date-to-time date)
-					    (error '(0 0))))
+			      (time-since (gnus-date-get-time date))
 			      cutoff))
 	    (when (if younger-p
 		      is-younger

Re: faster gnus-thread-latest-date

[Katsumi Yamaoka]

Dan Christensen wrote:
> Dan Christensen <jdc@uwo.ca> writes:

>> I'd just like to clarify the current thread by emphasizing that the
>> patch below is small and yet produces a very large speed-up.  I hope
>> that it can be tested and applied.
>>
>> The context lines don't show that the last change is to the function
>> gnus-summary-limit-to-age.  The rest should be clear from the patch.

> Are we still in pre-test, or would it be reasonable to apply the patch
> below?  I've been using it for more than 5 months without a problem.
> Let me know if I should rebase it.

Thank you for posting the patch again.  I've applied it to the
Gnus trunk and the Emacs trunk.

Gnus new commits (was: faster gnus-thread-latest-date)

[Ted Zlatanov]

On Thu, 10 Jun 2010 09:32:14 +0900 Katsumi Yamaoka <yamaoka@jpl.org> wrote: 

KY> Dan Christensen wrote:

>> Are we still in pre-test, or would it be reasonable to apply the patch
>> below?  I've been using it for more than 5 months without a problem.
>> Let me know if I should rebase it.

KY> Thank you for posting the patch again.  I've applied it to the
KY> Gnus trunk and the Emacs trunk.

Dan, thanks for re-posting the patch.

I think it's safe to say we're open to new commits in Gnus.  I don't
plan to make a new Gnus release myself and don't know when Reiner plans
to do so; meanwhile any new features can be considered (and bugfixes and
optimizations too, of course).

Ted

Re: faster gnus-thread-latest-date

[Daniel Pittman]

Dan Christensen <jdc@uwo.ca> writes:
> Dan Christensen <jdc@uwo.ca> writes:
>
>> In my tests, it is noticeable faster.  Can it be improved further?
>
> Actually, in my tests it is only slightly faster.  Still, the code is much
> simpler, so unless someone can think of a reason not to, I think the change
> should be made (after someone else checks it over and tests it).

Replacing reasonably sensible behaviour (use delivery time if no accurate time
is available) with nonsense (delivered before everything else if no accurate
time is available) doesn't look like a usability win to me. :(

I guess that either was this isn't this going to be hit very often at all, is
it, these days?  After all, threads with no sane time information are rare, so
the fallback isn't hit much either way.

> However, I think there's an orthogonal change which could greatly improve
> the sorting speed.  For a group I have with about 6000 messages and maybe
> 1000 threads (?), gnus-thread-latest-date is called 31028 times, taking
> about 10.5 seconds in total.  If the output from gnus-thread-latest-date was
> cached, that would reduce the number of computations of this date by at
> least a factor of 5, and so would greatly reduce the time needed to enter
> the summary buffer.

This sounds like a vastly more useful way to fix the problem; the results
below show that memoizing the function returns better performance
improvements.

        Daniel

-- 
✣ Daniel Pittman            ✉ daniel@rimspace.net            ☎ +61 401 155 707
               ♽ made with 100 percent post-consumer electrons

Re: faster gnus-thread-latest-date

[Dan Christensen]

Daniel Pittman <daniel@rimspace.net> writes:

> Dan Christensen <jdc@uwo.ca> writes:
>
>> Actually, in my tests it is only slightly faster.  Still, the code is much
>> simpler, so unless someone can think of a reason not to, I think the change
>> should be made (after someone else checks it over and tests it).
>
> Replacing reasonably sensible behaviour (use delivery time if no
> accurate time is available) with nonsense (delivered before everything
> else if no accurate time is available) doesn't look like a usability
> win to me. :(

I'm not sure what you mean, here.  When taking the maximum of a list of
data, replacing bad data with the previous thing on the list or with a
very small value won't change the maximum.

>> However, I think there's an orthogonal change which could greatly
>> improve the sorting speed.  For a group I have with about 6000
>> messages and maybe 1000 threads (?), gnus-thread-latest-date is
>> called 31028 times, taking about 10.5 seconds in total.  If the
>> output from gnus-thread-latest-date was cached, that would reduce the
>> number of computations of this date by at least a factor of 5, and so
>> would greatly reduce the time needed to enter the summary buffer.
>
> This sounds like a vastly more useful way to fix the problem; the results
> below show that memoizing the function returns better performance
> improvements.

Which results below?  How did you memoize the function?  And how does it
compare to the trick of caching the results as a text property that I
discussed in a later message?

Dan