Patchworkβ emacs: Use a single buffer invisibility spec to fix quadratic search cost.

login
register
about
Submitter Austin Clements
Date 2011-11-09 02:55:28
Message ID <1320807328-13728-1-git-send-email-amdragon@mit.edu>
Download mbox | patch
Permalink /patch/1476/
State New
Headers show

Comments

Austin Clements - 2011-11-09 02:55:28
Buffer redisplay requires traversing the buffer's invisibility spec
for every part of the display that has an 'invisible text or overlay
property.  Previously, the search buffer's invisibility spec list
contained roughly one entry for each search result.  As a result,
redisplay took O(NM) time where N is the number of visible lines and M
is the total number of results.  On a slow computer, this is enough to
make even buffer motion noticeably slow.  Worse, during a search
operation, redisplay is triggered for each search result (even if
there are no visible buffer changes), so search was quadratic
(O(NM^2)) in the number of search results.

This change switches to using a single element buffer invisibility
spec.  To un-hide authors, instead of removing an entry from the
invisibility spec, it simply removes the invisibility overlay from
those authors.


I tested using a query with 6633 results on a 9 year old machine.
Before this patch, Emacs took 70 seconds to fill the search buffer;
toward the end of the search, Emacs consumed 10-20x as much CPU as
notmuch; and moving point in the buffer took about a second.  With
this patch, the same query takes 40 seconds, Emacs consumes ~3x the
CPU of notmuch by the end, and there's no noticeable lag to moving
point.  (There's still some source of non-linearity, because Emacs and
notmuch consume roughly the same amount of CPU early in the search.)
---
 emacs/notmuch.el |   11 +++--------
 1 files changed, 3 insertions(+), 8 deletions(-)
Dmitry Kurochkin - 2011-11-09 06:31:58
Hi Austin.

The patch looks good to me.  Thanks for it!  A very nice optimization!

Regards,
  Dmitry
Sebastian Spaeth - 2011-11-10 13:33:58
On Tue,  8 Nov 2011 21:55:28 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
>  emacs/notmuch.el |   11 +++--------
>  1 files changed, 3 insertions(+), 8 deletions(-)


Tested and works great here! +1 for quick inclusion.

Sebastian
Austin Clements - 2011-11-11 05:27:16
Quoth myself on Nov 10 at 11:53 pm:
> Quoth Pieter Praet on Nov 11 at  4:04 am:
> > I've tried getting some hard numbers using
> > 
> >   #+begin_src sh
> >     time emacs --eval '(progn
> >         (notmuch)
> >         (notmuch-search "*")
> >         (while (get-buffer-process (current-buffer))
> >             (sleep-for 0.1))
> >         (kill-emacs))'
> >   #+end_src
> > 
> > ... but the results vary wildly on subsequent runs.
> 
> For me, this doesn't actually display the results buffer (though I
> don't know why not), which means it won't test this, since the problem
> lies in the Emacs redisplay logic.

This may or may not actually be correct, but the following seems more
representative on my system:

    time emacs --eval '(progn
        (notmuch)
        (notmuch-search "*")
        (while (get-buffer-process (current-buffer))
            (redisplay)
            (sleep-for 0.1))
        (kill-emacs))'

This at least displays the buffer.  I also tried
(accept-process-output) instead of the (sleep-for 0.1), which clearly
behaved differently, but gave only slightly higher numbers.  If I
timed just the search part, to exclude emacs start-up, I would have a
better idea of which more closely matches my manual measurements.
David Bremner - 2011-11-12 14:35:11
On Tue,  8 Nov 2011 21:55:28 -0500, Austin Clements <amdragon@MIT.EDU> wrote:
> Buffer redisplay requires traversing the buffer's invisibility spec
> This change switches to using a single element buffer invisibility
> spec.  To un-hide authors, instead of removing an entry from the
> invisibility spec, it simply removes the invisibility overlay from
> those authors.

Pushed to master.

d

Patch

diff --git a/emacs/notmuch.el b/emacs/notmuch.el
index bb7565c..58fdea0 100644
--- a/emacs/notmuch.el
+++ b/emacs/notmuch.el
@@ -378,7 +378,7 @@  Complete list of currently available key bindings:
   (make-local-variable 'notmuch-search-target-line)
   (set (make-local-variable 'notmuch-search-continuation) nil)
   (set (make-local-variable 'scroll-preserve-screen-position) t)
-  (add-to-invisibility-spec 'notmuch-search)
+  (add-to-invisibility-spec (cons 'ellipsis t))
   (use-local-map notmuch-search-mode-map)
   (setq truncate-lines t)
   (setq major-mode 'notmuch-search-mode
@@ -679,9 +679,6 @@  foreground and blue background."
 			      (append (overlay-get overlay 'face) attributes)))))
 	  notmuch-search-line-faces)))
 
-(defun notmuch-search-isearch-authors-show (overlay)
-  (remove-from-invisibility-spec (cons (overlay-get overlay 'invisible) t)))
-
 (defun notmuch-search-author-propertize (authors)
   "Split `authors' into matching and non-matching authors and
 propertize appropriately. If no boundary between authors and
@@ -755,13 +752,11 @@  non-authors is found, assume that all of the authors match."
       (insert visible-string)
       (when (not (string= invisible-string ""))
 	(let ((start (point))
-	      (invis-spec (make-symbol "notmuch-search-authors"))
 	      overlay)
 	  (insert invisible-string)
-	  (add-to-invisibility-spec (cons invis-spec t))
 	  (setq overlay (make-overlay start (point)))
-	  (overlay-put overlay 'invisible invis-spec)
-	  (overlay-put overlay 'isearch-open-invisible #'notmuch-search-isearch-authors-show)))
+	  (overlay-put overlay 'invisible 'ellipsis)
+	  (overlay-put overlay 'isearch-open-invisible #'delete-overlay)))
       (insert padding))))
 
 (defun notmuch-search-insert-field (field date count authors subject tags)