]> git.notmuchmail.org Git - notmuch/commit
emacs: Use a single buffer invisibility spec to fix quadratic search cost.
authorAustin Clements <amdragon@MIT.EDU>
Wed, 9 Nov 2011 02:55:28 +0000 (21:55 -0500)
committerDavid Bremner <bremner@debian.org>
Sat, 12 Nov 2011 14:21:03 +0000 (09:21 -0500)
commita2d78fba200d0342d90cf27f2ac3eb9091911275
tree8b23fe944334d5118db90082abe17427b85eac68
parentac46c6fdc23c0699ec53972a4082588b046559a2
emacs: Use a single buffer invisibility spec to fix quadratic search cost.

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