Poor org-babel-tangle-file performance with more than 100 trivial noweb-references

[pareto optimal <pareto.optimal@mailfence.com>]

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

Using =emacs -Q= to tangle org files with more than over 100 noweb-refs gets slow fast.

Given this org code for N=2:

#+begin_src org :tangle 2.org
  ,#+begin_src elisp :noweb yes :tangle 2.el
  <<some-reference>>
  ,#+end_src

  ,#+begin_src elisp :noweb-ref some-reference :tangle no
  ;; comment
  ,#+end_src

  ,#+begin_src elisp :noweb-ref some-reference :tangle no
  ;; comment
  ,#+end_src
#+end_src

and this macro for benchmarking:

#+begin_src emacs-lisp
(cl-defmacro bench (&optional (times 100000) &rest body)
  (declare (indent defun))
  `(progn
     (garbage-collect)
     (list '("Total runtime" "# of GCs" "Total GC runtime")
           'hline
           (benchmark-run-compiled ,times
             (progn
               ,@body)))))
#+end_src

and the org-babel-tangle-file call with gc-cons-threshold at most-positive-fixnum:

#+begin_src emacs-lisp
  (let ((gc-cons-threshold most-positive-fixnum))
    (bench (org-babel-tangle-file "2.org")))
#+end_src

Using Gcc Emacs 28.0.91 (which I typicall use) I get these results:

| N blocks | runtime | # of GCs |
|----------+---------+----------|
|       10 |   0.027 |        0 |
|       20 |   0.049 |        0 |
|       40 |   0.121 |        0 |
|       80 |   0.391 |        0 |
|      160 |   1.426 |        0 |
|      320 |   6.765 |        0 |
|      640 |  23.972 |        0 |

so roughly it scales like:

#+begin_example
0.8x (10-20)
2.5x  (20-40)
3x  (40-80)
3.5x  (160-320)
4x  (320-640)
#+end_example

Though I'm not sure how much that can tell us... my guess is noweb-ref's don't use a dictionary with =O(1)= lookups?

Out of curiousity I also benchmarked emacs 27.2 which came with org 9.4.4 and it gave roughly the same results:

* emacs -Q (emacs 27.2/org-9.4.4)
** =gc-cons-threshold= most-positive-fixnum

| N blocks | runtime | # of GCs |
|----------+---------+----------|
|       10 |   0.031 |        0 |
|       20 |   0.054 |        0 |
|       40 |   0.142 |        0 |
|       80 |   0.445 |        0 |
|      160 |   1.641 |        0 |
|      320 |   6.478 |        0 |
|      640 |  25.729 |        0 |

I have the full benchmarking experiment here: https://www.paretooptimal.dev/poor-org-babel-performance-with-lots-of-noweb-references/

Emacs  : GNU Emacs 28.0.91 (build 1, x86_64-pc-linux-gnu, GTK+ Version 3.24.30, cairo version 1.16.0)
Package: Org mode version 9.5.2 (9.5.2-gfbff08 @ /nix/store/3ff9visj5fl1a3d4krpv9wgmd078f5l1-emacs-packages-deps/share/emacs/site-lisp/elpa/org-9.5.2/)

current state:
==============
(setq
 org-link-elisp-confirm-function 'yes-or-no-p
 org-bibtex-headline-format-function #[257 "\300\x01\236A\207" [:title] 3 "\n\n(fn ENTRY)"]
 org-export-before-parsing-hook '(org-attach-expand-links)
 org-archive-hook '(org-attach-archive-delete-maybe)
 org-cycle-hook '(org-cycle-hide-archived-subtrees org-cycle-hide-drawers org-cycle-show-empty-lines
          org-optimize-window-after-visibility-change)
 org-mode-hook '(#[0 "\300\301\302\303\304$\207" [add-hook change-major-mode-hook org-show-all append local] 5]
         #[0 "\300\301\302\303\304$\207"
           [add-hook change-major-mode-hook org-babel-show-result-all append local] 5]
         org-babel-result-hide-spec org-babel-hide-all-hashes)
 org-confirm-shell-link-function 'yes-or-no-p
 outline-isearch-open-invisible-function 'outline-isearch-open-invisible
 org-agenda-before-write-hook '(org-agenda-add-entry-text)
 org-src-mode-hook '(org-src-babel-configure-edit-buffer org-src-mode-configure-edit-buffer)
 org-confirm-elisp-link-function 'yes-or-no-p
 org-speed-command-hook '(org-speed-command-activate org-babel-speed-command-activate)
 org-tab-first-hook '(org-babel-hide-result-toggle-maybe org-babel-header-arg-expand)
 org-link-shell-confirm-function 'yes-or-no-p
 org-babel-pre-tangle-hook '(save-buffer)
 org-agenda-loop-over-headlines-in-active-region nil
 org-occur-hook '(org-first-headline-recenter)
 org-metadown-hook '(org-babel-pop-to-session-maybe)
 org-link-parameters '(("attachment" :follow org-attach-follow :complete org-attach-complete-link)
               ("id" :follow org-id-open) ("eww" :follow org-eww-open :store org-eww-store-link)
               ("rmail" :follow org-rmail-open :store org-rmail-store-link)
               ("mhe" :follow org-mhe-open :store org-mhe-store-link)
               ("irc" :follow org-irc-visit :store org-irc-store-link :export org-irc-export)
               ("info" :follow org-info-open :export org-info-export :store org-info-store-link)
               ("gnus" :follow org-gnus-open :store org-gnus-store-link)
               ("docview" :follow org-docview-open :export org-docview-export :store
            org-docview-store-link)
               ("bibtex" :follow org-bibtex-open :store org-bibtex-store-link)
               ("bbdb" :follow org-bbdb-open :export org-bbdb-export :complete org-bbdb-complete-link
            :store org-bbdb-store-link)
               ("w3m" :store org-w3m-store-link)
               ("doi" :follow org-link-doi-open :export org-link-doi-export) ("file+sys") ("file+emacs")
               ("shell" :follow org-link--open-shell)
               ("news" :follow
            #[514 "\301\300\302\x04Q\x02\"\207" ["news" browse-url ":"] 6 "\n\n(fn URL ARG)"])
               ("mailto" :follow
            #[514 "\301\300\302\x04Q\x02\"\207" ["mailto" browse-url ":"] 6 "\n\n(fn URL ARG)"])
               ("https" :follow
            #[514 "\301\300\302\x04Q\x02\"\207" ["https" browse-url ":"] 6 "\n\n(fn URL ARG)"])
               ("http" :follow
            #[514 "\301\300\302\x04Q\x02\"\207" ["http" browse-url ":"] 6 "\n\n(fn URL ARG)"])
               ("ftp" :follow
            #[514 "\301\300\302\x04Q\x02\"\207" ["ftp" browse-url ":"] 6 "\n\n(fn URL ARG)"])
               ("help" :follow org-link--open-help :store org-link--store-help)
               ("file" :complete org-link-complete-file) ("elisp" :follow org-link--open-elisp))
 org-metaup-hook '(org-babel-load-in-session-maybe)
 )

-- Sent with https://mailfence.com  Secure and private email

[-- Attachment #2: Type: text/html, Size: 9606 bytes --]