nnmail-split-it

nnmail-split-it

[Johan Danielsson]

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


Nnmail-split-it is currently using re-search-backward, this fails with
splits like this:

("sender" "\\(.*\\)@foo.org" "foo-\\1")

What will searching forward break?

/Johan


[-- Attachment #2: Type: text/plain, Size: 1387 bytes --]

--- nnmail.el	1997/02/02 21:31:10	1.1
+++ nnmail.el	1997/02/02 21:33:46
@@ -1133,7 +1133,7 @@
    ;; Check the cache for the regexp for this split.
    ;; FIX FIX FIX could avoid calling assq twice here
    ((assq split nnmail-split-cache)
-    (goto-char (point-max))
+    (goto-char (point-min))
     ;; FIX FIX FIX problem with re-search-backward is that if you have
     ;; a split: (from "foo-\\(bar\\|baz\\)@gnus.org "mail.foo.\\1")
     ;; and someone mails a message with 'To: foo-bar@gnus.org' and
@@ -1148,15 +1148,15 @@
     ;; removed duplicates, since there might be more of those.
     ;; I guess we could also remove duplicates in the & split case, since
     ;; that's the only thing that can introduce them.
-    (when (re-search-backward (cdr (assq split nnmail-split-cache)) nil t)
+    (when (re-search-forward (cdr (assq split nnmail-split-cache)) nil t)
       ;; Someone might want to do a \N sub on this match, so get the
       ;; correct match positions.
-      (goto-char (match-end 0))
+      (goto-char (match-end 2))
       (let ((value (nth 1 split)))
-	(re-search-backward (if (symbolp value)
+	(re-search-forward (if (symbolp value)
 				(cdr (assq value nnmail-split-abbrev-alist))
 			      value)
-			    (match-end 1)))
+			   (match-end 0)))
       (nnmail-split-it (nth 2 split))))
 
    ;; Not in cache, compute a regexp for the field/value pair.

Re: nnmail-split-it

[David Moore]

joda@pdc.kth.se (Johan Danielsson) writes:

> Nnmail-split-it is currently using re-search-backward, this fails with
> splits like this:
> 
> ("sender" "\\(.*\\)@foo.org" "foo-\\1")
> 
> What will searching forward break?

	If there are multiple headers which match, it'll get the earlier
ones rather than the latter ones.  The problem in this case however is
the two competing .*'s in the regexp.  A better fix is probably just
make the innermost regexp-search-backwards into a forwards, not both of
them.

	And a much better fix would be to preparse the message headers,
to allow much faster comparisons, as it's really slow currently with
lots of split rules.  Something like making a list of header names to
the start/end points of that header's value in the buffer might be
good.  Then you just do string-match of the field designator to each
thing in the list, and the first one which matches, you apply the value
regexp to the buffer limited to the start/end region.

-- 
David Moore <dmoore@ucsd.edu>       | Computer Systems Lab      __o
UCSD Dept. Computer Science - 0114  | Work: (619) 534-8604    _ \<,_
La Jolla, CA 92093-0114             | Fax:  (619) 534-1445   (_)/ (_)
<URL:http://oj.egbt.org/dmoore/>    | In a cloud bones of steel.

Re: nnmail-split-it

[Paul Franklin]

>>>>> David Moore writes:

 > 	And a much better fix would be to preparse the message headers,
 > to allow much faster comparisons, as it's really slow currently with
 > lots of split rules.

Hmm.  I wrote some elisp code to do splitting like this.  I didn't
distribute it because:

* I realized that the bottleneck was disk access time (over NFS).

* I heard that elisp operations on buffers tend to be faster than
  operations on strings.  (Tracking start/end points would help this,
  but either make it less useful to me or more complex.)

It generates a alist of headers, unwrapping lines within headers and
separating values from duplicate headers with "\n".  You then match
with a header or multiple ones concatenated (very useful, for me at
least).  I never compared them with the default split rules, but I'm
fairly sure that this code is tight enough that it's very unlikely to
be a bottleneck.

If you're interested in the code, drop me a line.

--Paul

Re: nnmail-split-it

[Lars Magne Ingebrigtsen]

Paul Franklin <paul@cs.washington.edu> writes:

> Hmm.  I wrote some elisp code to do splitting like this.  I didn't
> distribute it because:
> 
> * I realized that the bottleneck was disk access time (over NFS).

The box I'm sitting with now is a 486/slow without NFS, and splitting
is kinda slow here as well.

> It generates a alist of headers, unwrapping lines within headers and
> separating values from duplicate headers with "\n".  You then match
> with a header or multiple ones concatenated (very useful, for me at
> least).  I never compared them with the default split rules, but I'm
> fairly sure that this code is tight enough that it's very unlikely to
> be a bottleneck.

We should probably wait with this until the total mail
splitting/fetching makeover in Quassia Gnus.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@ifi.uio.no * Lars Ingebrigtsen

Re: nnmail-split-it

[David Moore]

Lars Magne Ingebrigtsen <larsi@ifi.uio.no> writes:

> Paul Franklin <paul@cs.washington.edu> writes:
> 
> > Hmm.  I wrote some elisp code to do splitting like this.  I didn't
> > distribute it because:
> > 
> > * I realized that the bottleneck was disk access time (over NFS).
> 
> The box I'm sitting with now is a 486/slow without NFS, and splitting
> is kinda slow here as well.

	Two different costs.  There is a per message cost (like NFS and
file stating).  There is also a per split cost (which is roughly O(n*m)
where n is the number of splits, and m is the number of headers in the
message).

> > It generates a alist of headers, unwrapping lines within headers and
> > separating values from duplicate headers with "\n".  You then match
> > with a header or multiple ones concatenated (very useful, for me at
> > least).  I never compared them with the default split rules, but I'm
> > fairly sure that this code is tight enough that it's very unlikely to
> > be a bottleneck.

	This is similar to what I suggested, but I wasn't going to
bother to put the headers into concatenated strings, since that is quite
slow itself.  But tracking the start/end position of those strings makes
doing a buffer regexp search much much faster since it limits the scope
of the search.

	As far as why it's a reverse search.  Well, I added the \1 sub
ability, and didn't think about the double .* affects with that,
probably because I wasn't using it with 'sender', and I think I used
`\\w' instead of `.'.  I recommend that people try [^ :]* or \\w*
instead of .* and see if that helps.  I'm not totally sure why Per used
a reverse search in the first place, but I left it because most of the
"uninteresting" headers are at the beginning (received, etc), and it'll
hit the lowest of any multiply matching lines.


-- 
David Moore <dmoore@ucsd.edu>       | Computer Systems Lab      __o
UCSD Dept. Computer Science - 0114  | Work: (619) 534-8604    _ \<,_
La Jolla, CA 92093-0114             | Fax:  (619) 534-1445   (_)/ (_)
<URL:http://oj.egbt.org/dmoore/>    | In a cloud bones of steel.

Re: nnmail-split-it

[anonymous]

From: Paul Franklin <paul@cs.washington.edu>
Date: 03 Feb 1997 22:16:24 -0800
Message-ID: <r9qpvyhayfb.fsf@fester.cs.washington.edu>
Organization: Computer Science, U of Washington, Seattle, WA, USA
Lines: 192
X-Newsreader: Gnus v5.4.10/Emacs 19.34
Path: fester.cs.washington.edu
NNTP-Posting-Host: fester.cs.washington.edu

Warning:  I'm about to throw out some performance numbers from what I
remember from 6 months ago when my spool was on a local disk...

>>>>> David Moore writes:

 > Lars Magne Ingebrigtsen <larsi@ifi.uio.no> writes:

 >> Paul Franklin <paul@cs.washington.edu> writes:

 >> > Hmm.  I wrote some elisp code to do splitting like this.  I didn't
 >> > distribute it because:

 >> > * I realized that the bottleneck was disk access time (over NFS).

 >> The box I'm sitting with now is a 486/slow without NFS, and splitting
 >> is kinda slow here as well.

 > 	Two different costs.  There is a per message cost (like NFS and
 > file stating).  There is also a per split cost (which is roughly O(n*m)
 > where n is the number of splits, and m is the number of headers in the
 > message).

I tried hard to lower the per split cost while not worrying as much
about the per message cost.  The significant per split costs are an
assq and a string-match.  But the per header line costs aren't small;
I'd be very surprised if the per header line cost were lower than the
per split cost.

 >> > It generates a alist of headers, unwrapping lines within headers and
 >> > separating values from duplicate headers with "\n".  You then match
 >> > with a header or multiple ones concatenated (very useful, for me at
 >> > least).  I never compared them with the default split rules, but I'm
 >> > fairly sure that this code is tight enough that it's very unlikely to
 >> > be a bottleneck.

 > 	This is similar to what I suggested, but I wasn't going to
 > bother to put the headers into concatenated strings, since that is quite
 > slow itself.  But tracking the start/end position of those strings makes
 > doing a buffer regexp search much much faster since it limits the scope
 > of the search.

I did this for flexibility, not speed.  It allows searching, in order,
from, apparently-from, to, cc, apparently-to, ... with a single rule.
I really wanted this, so if I was going to write my own split
function, it was going to have this feature.

I'm attaching my code with sample rules, in case people want to
experiment, run timing tests, or whatever.  Until I spend some effort
to clean it up for qgnus, if Lars wants to include it (at which point
it'll be GPL'd), or decide not to clean it up, please don't
redistribute it.  I suppose Lars will want me to do something other
than performing list surgery on a user-configurable variable.  (Yes,
this is truly evil code.)

Be warned, I'm likely to change the rule forms to
	;;	(GROUP . REGEXP)
	;;	(GROUP WORDS...)
where the second is converted to the first by inserting "\\<", "\\>",
and "\\|" as appropriate.

--Paul

;;Copyright 1996, 1997 Paul Franklin

(setq nnmail-split-methods 'pdf-nnmail-split-function)

(setq pdf-nnmail-split-abbrev-alist
	;;Using these is particularly efficient 
	;;because their expansions are cached.
	;; Elements are of the form
	;; (ABBREV . HEADER-LIST)
	;;which is equivalent to
	;; (ABBREV HEADERS...)
      '(
	(f from sender)
	(l f to apparently-to)
	(t to apparently-to cc)
	(a f t)
	(s a subject)))

(setq pdf-nnmail-split-methods
	(list

	;;Rule groups are of the form (HEADER-LIST RULES...)
	;;Headers are specified with lowercase symbols, not strings.
	;;Rules come in two forms:
	;;	(GROUP . REGEXP)
	;;	(GROUP REGEXPS...)
	;;  The second is converted to the first by list surgery (!);
	;;  "\\|" is inserted between regexps.

	;;Rule groups are considered in order, a match terminates the
	;;search.

	;;Rules withing a rule group are considered simultaneously,
	;;with the one matching earlier in the specified headers
	;;winning.

	 '((gnus-warning)
	   ("-mail.duplicates" . "\\<duplicate\\>"))

	 '((a)
	   ("-conf.cs.chi97.sv" 
	    "\\<chi97-sv\\>" "\\<tutorial-chi97\\>")
	   ("-net.gnus.list" . "\\<ding@ifi\\.uio\\.no\\>"))

	 '((subject) 
	   ("-uw.cs.csl.dots" . "dot"))

	 '((t)
	   ("-seminar.uw.cs.systems"
	    "\\<cse590s\\>" "\\<cer-systems\\>" "\\<uw-systems\\>")
	   ("-seminar.uw.cs.ui" . "\\<ui-students\\>")
	   ("-seminar.uw.cs.lis" 
	    "590m\\>" "\\<590f\\>" "\\<vlsi\\>")
	   ("-seminar.uw.cs.arch" "\\<arch-lunch\\>" "590g\\>"))

	 '((s)
	   ("-class.uw.cse-568" "568\\>")
	   ("-uw.cs.acm" "\\<acm\\>")
	   ("-uw.cs.sports"
	    "\\<stp-riders\\>" "\\<soccer\\>" "\\<ultimate\\>"
	    "\\<cyclists\\>" "\\<stp-1dayers\\>")
	   ("-uw.cs.room.sieg-431" . "\\<431\\>")
	   ("-uw.cs.csl.uns" . "\\<uns")))))


(defun pdf-nnmail-extract-header-alist (&optional init-header-alist)
  "Extract alist of headers"
  (let ((header-alist init-header-alist))
    (goto-char (point-min))
    (while (re-search-forward
	    "^\\([^ \t\n]*\\):[ \t]*\\(\\([^\n]*\n[ \t]\\)*[^\n]*\\)\n"
	    nil t)
      (let ((header-sym (intern-soft (downcase (match-string 1)))))
	(if header-sym
	    (let ((header-alist-elt (assq header-sym header-alist))
		  (header-data (match-string 2)))
	      (string-match "" header-data) ; reset match-data
	      (while (string-match "\n" header-data (match-end 0))
		(setq header-data (replace-match "" t t header-data)))
	      (if header-alist-elt
		  (setcdr header-alist-elt
			  (concat header-data "\n" (cdr header-alist-elt)))
		(setq header-alist (cons (cons header-sym header-data)
					 header-alist)))))))
    header-alist))

(defun pdf-nnmail-header-list-lookup (field-list header-alist)
  "Lookup fields in an alist.
Returns results, concatenated with newlines."
  (mapconcat
   '(lambda (field)
      (let* ((field-cons (assq field header-alist))
	     (field-cdr (cdr-safe field-cons)))
	(cond
	 ((atom field-cons)
	  "")
	 ((atom field-cdr)
	  field-cdr)
	 (t
	  (setcdr field-cons ;**new cdr is returned, not modified field-cons
		  (pdf-nnmail-header-list-lookup field-cdr header-alist))))))
   field-list "\n"))

(defun pdf-nnmail-split-function nil
  "Do splitting based on generated alist of header fields"
  (interactive)
  (let ((header-alist (pdf-nnmail-extract-header-alist
		       (copy-alist pdf-nnmail-split-abbrev-alist)))
	(methods-walker pdf-nnmail-split-methods)
	dest)
    (while methods-walker
      (let* ((current-method (car methods-walker))
	     (wanted-headers (pdf-nnmail-header-list-lookup
			      (car current-method) header-alist))
	     (clauses-walker (cdr current-method))
	     loc)
	(while clauses-walker
	(let ((current-clause (car clauses-walker)))
	  (if (listp (cdr current-clause))
	      (setcdr current-clause (mapconcat 'identity
						(cdr current-clause)
						"\\|")))
	  (let ((cur-loc (string-match (cdr current-clause) wanted-headers)))
	    (if (and cur-loc (or (not loc) (< cur-loc loc)))
		(setq loc cur-loc
		      dest (car current-clause)
		      methods-walker nil))))
	  (setq clauses-walker (cdr clauses-walker))))
      (setq methods-walker (cdr-safe methods-walker)))
    (list dest)))

Re: nnmail-split-it

[Per Abrahamsen]

Lars Magne Ingebrigtsen <larsi@ifi.uio.no> writes:

> The box I'm sitting with now is a 486/slow without NFS, and splitting
> is kinda slow here as well.

I really want to see some numbers before I believe the bottleneck is
in the lisp code, rather than in i/o (and in particular directory
synchronization).  Are you using Linux ext2fs?

Re: nnmail-split-it

[David Moore]

Per Abrahamsen <abraham@dina.kvl.dk> writes:

> Lars Magne Ingebrigtsen <larsi@ifi.uio.no> writes:
> 
> > The box I'm sitting with now is a 486/slow without NFS, and splitting
> > is kinda slow here as well.
> 
> I really want to see some numbers before I believe the bottleneck is
> in the lisp code, rather than in i/o (and in particular directory
> synchronization).  Are you using Linux ext2fs?


Ok, the numbers.  This is to file 40 messages to myself (ie, not many
received headers) which do not match any of my filing patterns, and one
message to xemacs-beta which arrived just before I hit `M-g'.  I have
about 140 filing patterns in my nnmail-split-fancy.

I also did `s' after fetching the mail.  Note that it took 45 seconds
just to split 41 messages in the nnmail-split-it routine.  And it
took 14 seconds to write those 41 mesages to disk.  Another 3 or so
seconds went to writing out my newsrc.

Function Name                              # Calls  Elapsed  Average
=========================================  =======  =======  =======
gnus-topic-get-new-news-this-topic         1        63.6572  63.6572
gnus-group-get-new-news-this-group         1        63.6555  63.6555
gnus-activate-group                        1        62.7958  62.7958
gnus-request-scan                          1        62.5327  62.5327
nnml-request-scan                          1        62.5297  62.5297
nnmail-get-new-mail                        1        62.5134  62.5134
nnmail-split-incoming                      1        60.0041  60.0041
nnmail-process-unix-mail-format            1        59.9781  59.9781
nnmail-check-duplication                   41       59.7227  1.45665
nnmail-article-group                       41       45.7249  1.11524
nnmail-split-fancy                         41       44.9484  1.09630
nnmail-split-it                            5876     44.9365  1.09601
nnml-save-mail                             41       13.7885  0.33630
write-region                               48       13.4512  0.28023
nnmail-write-region                        44       12.0977  0.27494
gnus-group-save-newsrc                     1        2.8573   2.8573


PS. This output does not have the recursive miscounting or time window
    overflow bugs of standard elp.

-- 
David Moore <dmoore@ucsd.edu>       | Computer Systems Lab      __o
UCSD Dept. Computer Science - 0114  | Work: (619) 534-8604    _ \<,_
La Jolla, CA 92093-0114             | Fax:  (619) 534-1445   (_)/ (_)
<URL:http://oj.egbt.org/dmoore/>    | In a cloud bones of steel.

Re: nnmail-split-it

[Lars Magne Ingebrigtsen]

David Moore <dmoore@UCSD.EDU> writes:

> Ok, the numbers.

Here's some more numbers.  I don't use fancy splitting, 

Function Name                           Call Count  Elapsed Time  Average Time
======================================  ==========  ============  ============
nnmail-get-new-mail                     2           9.6420090000  4.8210045000
nnml-request-scan                       1           9.5177219999  9.5177219999
nnmail-split-incoming                   1           4.9987040000  4.9987040000
nnmail-process-unix-mail-format         1           4.9663250000  4.9663250000
nnmail-check-duplication                22          4.7403299999  0.2154695454
nnmail-article-group                    22          2.5469890000  0.1157722272
nnml-save-mail                          22          1.9137599999  0.0869890909
nnmail-write-region                     24          0.9803770000  0.0408490416
nnml-add-nov                            22          0.3610729999  0.0164124090
nnmail-group-pathname                   67          0.2864010000  0.0042746417

We see that the actial writing of the files only takes one tenth of
the time consumed by the splitting.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@ifi.uio.no * Lars Ingebrigtsen

Re: nnmail-split-it

[Paul Franklin]

OK, I gathered some performance numbers for my splitting method.  

I have 58 split rules in 14 groups; I grabbed some old mail from an
Incoming file and resplit its 29 messages.  I don't know where one got
put, but from the ones I found, I know I evaluated 1044 split rules
(~37/msg) in 205 rule groups (~7/msg).  Note that parsing the headers
took up 1/3 of the total time to split.

Concatenations can happen in both pdf-nnmail-header-list-lookup and
pdf-nnmail-extract-header-alist.  Also, pdf-nnmail-header-list-lookup
is called at least once per rule group, but not once per rule.

The only way I can think of to compare these is by normalizing on
nnmail-check-duplication.  Does anyone have a better suggestion?

Function Name                           Call Count  Elapsed Time  Average Time
======================================  ==========  ============  ============
nnmail-get-new-mail                     1           30.084111999  30.084111999
nnmail-split-incoming                   1           18.756096000  18.756096000
nnmail-process-unix-mail-format         1           18.575437000  18.575437000
nnmail-check-duplication                29          18.501307999  0.6379761379
nnmail-write-region                     43          15.935499000  0.3705930000
nnmail-move-inbox                       2           2.6384170000  1.3192085000
nnmail-article-group                    29          1.8114500000  0.0624637931
pdf-nnmail-split-function               29          1.0585440000  0.0365015172
pdf-nnmail-header-list-lookup           314         0.2344180000  0.0007465541
pdf-nnmail-extract-header-alist         29          0.3682350000  0.0126977586

--Paul

Re: nnmail-split-it

[Per Abrahamsen]

David Moore <dmoore@UCSD.EDU> writes:

> Ok, the numbers. 

You are right.

I get a 2x speedup by using 

	(setq nnmail-split-fancy "misc.misc")

instead of the usual 194 line definition on mail that doesn't match
any of the 193 first lines.  And this is over NFS on a fast machine,
so for anyone using a local disk or a slower cpu the split time will
be dominating, unless it matches one of the first splits.

It is probably a good idea to put the active mailing lists first in
your rules, if possible.

Re: nnmail-split-it

[Lars Magne Ingebrigtsen]

joda@pdc.kth.se (Johan Danielsson) writes:

> Nnmail-split-it is currently using re-search-backward, this fails with
> splits like this:
> 
> ("sender" "\\(.*\\)@foo.org" "foo-\\1")
> 
> What will searching forward break?

I don't know, but there must have been a reason for doing it that
way.  Does anybody remember?

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@ifi.uio.no * Lars Ingebrigtsen