9a/e22608021c27f812b87cbd605af720e34e3967

   1 Return-Path: <amthrax@awakening.csail.mit.edu>\r
   2 X-Original-To: notmuch@notmuchmail.org\r
   3 Delivered-To: notmuch@notmuchmail.org\r
   4 Received: from localhost (localhost [127.0.0.1])\r
   5         by olra.theworths.org (Postfix) with ESMTP id 24A3A431FD0\r
   6         for <notmuch@notmuchmail.org>; Tue,  8 Nov 2011 18:53:01 -0800 (PST)\r
   7 X-Virus-Scanned: Debian amavisd-new at olra.theworths.org\r
   8 X-Spam-Flag: NO\r
   9 X-Spam-Score: -0.7\r
  10 X-Spam-Level: \r
  11 X-Spam-Status: No, score=-0.7 tagged_above=-999 required=5\r
  12         tests=[RCVD_IN_DNSWL_LOW=-0.7] autolearn=disabled\r
  13 Received: from olra.theworths.org ([127.0.0.1])\r
  14         by localhost (olra.theworths.org [127.0.0.1]) (amavisd-new, port 10024)\r
  15         with ESMTP id BnZISlLgwMH9 for <notmuch@notmuchmail.org>;\r
  16         Tue,  8 Nov 2011 18:53:00 -0800 (PST)\r
  17 Received: from dmz-mailsec-scanner-4.mit.edu (DMZ-MAILSEC-SCANNER-4.MIT.EDU\r
  18         [18.9.25.15])\r
  19         by olra.theworths.org (Postfix) with ESMTP id 4B18F431FB6\r
  20         for <notmuch@notmuchmail.org>; Tue,  8 Nov 2011 18:53:00 -0800 (PST)\r
  21 X-AuditID: 1209190f-b7f6e6d0000008df-78-4eb9eb0bd86a\r
  22 Received: from mailhub-auth-4.mit.edu ( [18.7.62.39])\r
  23         by dmz-mailsec-scanner-4.mit.edu (Symantec Messaging Gateway) with SMTP\r
  24         id B6.37.02271.B0BE9BE4; Tue,  8 Nov 2011 21:52:59 -0500 (EST)\r
  25 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103])\r
  26         by mailhub-auth-4.mit.edu (8.13.8/8.9.2) with ESMTP id pA92qwUC010993; \r
  27         Tue, 8 Nov 2011 21:52:59 -0500\r
  28 Received: from awakening.csail.mit.edu (awakening.csail.mit.edu [18.26.4.91])\r
  29         (authenticated bits=0)\r
  30         (User authenticated as amdragon@ATHENA.MIT.EDU)\r
  31         by outgoing.mit.edu (8.13.6/8.12.4) with ESMTP id pA92qv2Y010455\r
  32         (version=TLSv1/SSLv3 cipher=AES256-SHA bits=256 verify=NOT);\r
  33         Tue, 8 Nov 2011 21:52:58 -0500 (EST)\r
  34 Received: from amthrax by awakening.csail.mit.edu with local (Exim 4.77)\r
  35         (envelope-from <amthrax@awakening.csail.mit.edu>)\r
  36         id 1RNyK3-0003aG-QX; Tue, 08 Nov 2011 21:55:31 -0500\r
  37 From: Austin Clements <amdragon@MIT.EDU>\r
  38 To: notmuch@notmuchmail.org\r
  39 Subject: [PATCH] emacs: Use a single buffer invisibility spec to fix quadratic\r
  40         search cost.\r
  41 Date: Tue,  8 Nov 2011 21:55:28 -0500\r
  42 Message-Id: <1320807328-13728-1-git-send-email-amdragon@mit.edu>\r
  43 X-Mailer: git-send-email 1.7.7.1\r
  44 X-Brightmail-Tracker:\r
  45  H4sIAAAAAAAAA+NgFprFIsWRmVeSWpSXmKPExsUixG6nrsv9eqefwa9VehbXb85kdmD0eLbq\r
  46         FnMAYxSXTUpqTmZZapG+XQJXxofG+4wFW6QqmvqusDUw3hHtYuTkkBAwkTg/7Q0ThC0mceHe\r
  47         erYuRi4OIYF9jBKfn11ihnDWM0r8aWtkhHBOMEk8PbIPKrOZUWLywg3MIP1sAhoS2/YvZwSx\r
  48         RQSkJXbenc3axcjBwSygJvGnSwUkLCwQLXGpaREbiM0ioCqx+fZ6FhCbV8BB4sWMnywg5RIC\r
  49         ChLLdlRPYORdwMiwilE2JbdKNzcxM6c4NVm3ODkxLy+1SNdELzezRC81pXQTIygIOCX5dzB+\r
  50         O6h0iFGAg1GJh/dy0U4/IdbEsuLK3EOMkhxMSqK8gq+AQnxJ+SmVGYnFGfFFpTmpxYcYJTiY\r
  51         lUR49+cA5XhTEiurUovyYVLSHCxK4ryNOxz8hATSE0tSs1NTC1KLYLIyHBxKErxTQYYKFqWm\r
  52         p1akZeaUIKSZODhBhvMADZ8AUsNbXJCYW5yZDpE/xagoJc5b9xQoIQCSyCjNg+uFRekrRnGg\r
  53         V4Qh2nmAEQ7X/QpoMBPQ4HbdbSCDSxIRUlINjGJJ+p9ftj9cJ/J8w3KHK4d4F8+XFjtza8+s\r
  54         ffXK5598CdPMlkpPu5j/Y8un1FXeqU9WeDTcWzLx08v7cwpePFQQLYtYLvz8vN6qp9duzd/U\r
  55         IOVp+3Al34Qwiz1R1baOIut+Lma32uOybNJOEZfim8zvauUC/SO0i2+2T2utOpe9Rt7wfsj8\r
  56         zgtKLMUZiYZazEXFiQDveZVArQIAAA==\r
  57 X-BeenThere: notmuch@notmuchmail.org\r
  58 X-Mailman-Version: 2.1.13\r
  59 Precedence: list\r
  60 List-Id: "Use and development of the notmuch mail system."\r
  61         <notmuch.notmuchmail.org>\r
  62 List-Unsubscribe: <http://notmuchmail.org/mailman/options/notmuch>,\r
  63         <mailto:notmuch-request@notmuchmail.org?subject=unsubscribe>\r
  64 List-Archive: <http://notmuchmail.org/pipermail/notmuch>\r
  65 List-Post: <mailto:notmuch@notmuchmail.org>\r
  66 List-Help: <mailto:notmuch-request@notmuchmail.org?subject=help>\r
  67 List-Subscribe: <http://notmuchmail.org/mailman/listinfo/notmuch>,\r
  68         <mailto:notmuch-request@notmuchmail.org?subject=subscribe>\r
  69 X-List-Received-Date: Wed, 09 Nov 2011 02:53:01 -0000\r
  70 \r
  71 Buffer redisplay requires traversing the buffer's invisibility spec\r
  72 for every part of the display that has an 'invisible text or overlay\r
  73 property.  Previously, the search buffer's invisibility spec list\r
  74 contained roughly one entry for each search result.  As a result,\r
  75 redisplay took O(NM) time where N is the number of visible lines and M\r
  76 is the total number of results.  On a slow computer, this is enough to\r
  77 make even buffer motion noticeably slow.  Worse, during a search\r
  78 operation, redisplay is triggered for each search result (even if\r
  79 there are no visible buffer changes), so search was quadratic\r
  80 (O(NM^2)) in the number of search results.\r
  81 \r
  82 This change switches to using a single element buffer invisibility\r
  83 spec.  To un-hide authors, instead of removing an entry from the\r
  84 invisibility spec, it simply removes the invisibility overlay from\r
  85 those authors.\r
  86 \r
  87 \r
  88 I tested using a query with 6633 results on a 9 year old machine.\r
  89 Before this patch, Emacs took 70 seconds to fill the search buffer;\r
  90 toward the end of the search, Emacs consumed 10-20x as much CPU as\r
  91 notmuch; and moving point in the buffer took about a second.  With\r
  92 this patch, the same query takes 40 seconds, Emacs consumes ~3x the\r
  93 CPU of notmuch by the end, and there's no noticeable lag to moving\r
  94 point.  (There's still some source of non-linearity, because Emacs and\r
  95 notmuch consume roughly the same amount of CPU early in the search.)\r
  96 ---\r
  97  emacs/notmuch.el |   11 +++--------\r
  98  1 files changed, 3 insertions(+), 8 deletions(-)\r
  99 \r
 100 diff --git a/emacs/notmuch.el b/emacs/notmuch.el\r
 101 index bb7565c..58fdea0 100644\r
 102 --- a/emacs/notmuch.el\r
 103 +++ b/emacs/notmuch.el\r
 104 @@ -378,7 +378,7 @@ Complete list of currently available key bindings:\r
 105    (make-local-variable 'notmuch-search-target-line)\r
 106    (set (make-local-variable 'notmuch-search-continuation) nil)\r
 107    (set (make-local-variable 'scroll-preserve-screen-position) t)\r
 108 -  (add-to-invisibility-spec 'notmuch-search)\r
 109 +  (add-to-invisibility-spec (cons 'ellipsis t))\r
 110    (use-local-map notmuch-search-mode-map)\r
 111    (setq truncate-lines t)\r
 112    (setq major-mode 'notmuch-search-mode\r
 113 @@ -679,9 +679,6 @@ foreground and blue background."\r
 114                               (append (overlay-get overlay 'face) attributes)))))\r
 115           notmuch-search-line-faces)))\r
 116  \r
 117 -(defun notmuch-search-isearch-authors-show (overlay)\r
 118 -  (remove-from-invisibility-spec (cons (overlay-get overlay 'invisible) t)))\r
 119 -\r
 120  (defun notmuch-search-author-propertize (authors)\r
 121    "Split `authors' into matching and non-matching authors and\r
 122  propertize appropriately. If no boundary between authors and\r
 123 @@ -755,13 +752,11 @@ non-authors is found, assume that all of the authors match."\r
 124        (insert visible-string)\r
 125        (when (not (string= invisible-string ""))\r
 126         (let ((start (point))\r
 127 -             (invis-spec (make-symbol "notmuch-search-authors"))\r
 128               overlay)\r
 129           (insert invisible-string)\r
 130 -         (add-to-invisibility-spec (cons invis-spec t))\r
 131           (setq overlay (make-overlay start (point)))\r
 132 -         (overlay-put overlay 'invisible invis-spec)\r
 133 -         (overlay-put overlay 'isearch-open-invisible #'notmuch-search-isearch-authors-show)))\r
 134 +         (overlay-put overlay 'invisible 'ellipsis)\r
 135 +         (overlay-put overlay 'isearch-open-invisible #'delete-overlay)))\r
 136        (insert padding))))\r
 137  \r
 138  (defun notmuch-search-insert-field (field date count authors subject tags)\r
 139 -- \r
 140 1.7.7.1\r
 141 \r