[PATCH] ox: Cache locations of fuzzy links

[Lawrence Mitchell <wence@gmx.li>]

* ox.el (org-export-resolve-fuzzy-link): Look for fuzzy link in a
  cache before trying to resolve it in the parse tree.

When a document contains a large number of identical fuzzy links, it
doesn't make sense to continually search for them.  Instead, as
long as we're looking for position independent links, cache the
locations and look there first.
---
 lisp/ox.el | 48 +++++++++++++++++++++++++++++++++++-------------
 1 file changed, 35 insertions(+), 13 deletions(-)

Achim Gratz wrote:
> Lawrence Mitchell writes:
>> I did a bit of digging and here are the results.  No potential
>> fixes though.

I couldn't see how to fix up org-export-data, but here's some
band-aid to speed up resolving fuzzy links.  It works much better
for the fake test case (where there are many identical links)
than the real org manual, but I do get a slight improvement
(about 6%).  As per elp:

Before:

org-latex-export-to-latex      1           373.02289908  373.02289908
org-export-resolve-fuzzy-link  281         42.108304211  0.1498516164

After:

org-latex-export-to-latex      1           349.7238257   349.7238257
org-export-resolve-fuzzy-link  281         19.329938028  0.0687898150

Cheers,
Lawrence

diff --git a/lisp/ox.el b/lisp/ox.el
index 88b4122..bb49512 100644
--- a/lisp/ox.el
+++ b/lisp/ox.el
@@ -3976,27 +3976,49 @@ significant."
 	 ;; Split PATH at white spaces so matches are space
 	 ;; insensitive.
 	 (path (org-split-string
-		(if match-title-p (substring raw-path 1) raw-path))))
+		(if match-title-p (substring raw-path 1) raw-path)))
+	 (link-cache (plist-get info :fuzzy-link-cache)))
+    ;; Cache for locations of fuzzy links that are not position dependent
+    (unless link-cache
+      (setq info (plist-put info :fuzzy-link-cache
+			    (make-hash-table :test 'equal)))
+      (setq link-cache (plist-get info :fuzzy-link-cache)))
     (cond
      ;; First try to find a matching "<<path>>" unless user specified
      ;; he was looking for a headline (path starts with a "*"
      ;; character).
      ((and (not match-title-p)
-	   (org-element-map (plist-get info :parse-tree) 'target
-	     (lambda (blob)
-	       (and (equal (org-split-string (org-element-property :value blob))
-			   path)
-		    blob))
-	     info t)))
+	   (let ((found (gethash (cons 'path path)
+				 link-cache
+				 'fuzzy-link-not-found)))
+	     (or (not (eq found 'fuzzy-link-not-found))
+		 (puthash (cons 'path path)
+			  (org-element-map (plist-get info :parse-tree) 'target
+			    (lambda (blob)
+			      (and (equal (org-split-string
+					   (org-element-property :value blob))
+					  path)
+				   blob))
+			    info t)
+			  link-cache)))))
      ;; Then try to find an element with a matching "#+NAME: path"
      ;; affiliated keyword.
      ((and (not match-title-p)
-	   (org-element-map (plist-get info :parse-tree)
-	       org-element-all-elements
-	     (lambda (el)
-	       (let ((name (org-element-property :name el)))
-		 (when (and name (equal (org-split-string name) path)) el)))
-	     info 'first-match)))
+	   (let ((found (gethash (cons 'name path)
+				 link-cache
+				 'fuzzy-link-not-found)))
+	     (or (not (eq found 'fuzzy-link-not-found))
+		 (puthash (cons 'name path)
+			  (org-element-map (plist-get info :parse-tree)
+			      org-element-all-elements
+			    (lambda (el)
+			      (let ((name (org-element-property :name el)))
+				(when (and name (equal
+						 (org-split-string name)
+						 path))
+				  el)))
+			    info 'first-match)
+			  link-cache)))))
      ;; Last case: link either points to a headline or to nothingness.
      ;; Try to find the source, with priority given to headlines with
      ;; the closest common ancestor.  If such candidate is found,
-- 
1.8.2-rc3