Improving performance of node-find et. al

Development
22

I ran the profiler and here is where 70% of the time is spent:

org-roam-format-template

But, most of the time spent is in the lambda passed to it.

I reckon that building the list of candidates can be done in at least 1/4 of the current time by doing them all at once rather than one at a time. The template is invariant, so there is no point on parsing it with regexp N-nodes times * number of template variables (in my case 4: “${title} ${tags} ${file} ${todo}”.

And once an attribute is identified (eg. title), all the nodes will have the same processing.

1 Like
23

@dmg
Results are as we expect it to be

#'org-roam-node-list 
> pass off semi formatted data from db
#'org-roam-node-read--completions
> after applying filter-fn
> iteratively call 
#'org-roam-node-read--to-candidate
#'org-roam-node-format-entry
#'org-roam-format-template

So indeed - using a filter-fn and not querying the full breadth of nodes will be beneficial somewhat – although the #'org-roam-node-list also takes some time – due to its formatting – but its nothing compared to when we iteratively call the final formatting after choosing from the nodes that pass the filter-fn in question.

Keep me updated with what tests you do and their results.

24

I think I got it: memoize org-roam-node-read–to-candidate. Give it a try.

in theory it should be possible to memoize it without redefining the function. No more lag for my 1000 nodes, but it still has to do the query. By the way, the function that does the query, it spends 4-5 times more time formatting the result than the actual time sqlite takes.

1 Like
25

Good work. I tested with 20000 files – its really fast. Thank you, will keep you updated if I find any problems. Awesome.

26

Just keep in mind: it uses memory, but it should never go out of control, since the nodes don’t change that much. Perhaps we should have a function to reset the cache once in a while. Maybe with at a fixed time.

27

I spent this morning making the existing cache more compact – I also converted your function to an advice function. Your cache will kick in and make the first update after db changes more fast and make the process more better.

No need to embed garbage collection inside the function – users can simple run with idle timer.

(defvar org-roam-node--cache-list nil)
(defvar org-roam-node--cache-time nil)
(defvar org-roam-node--cache-prev-filter-fn nil)
(defvar org-roam-node--cache-candidate-list nil)
(defvar cache/org-roam-node-read--to-candidate (make-hash-table :test 'equal))

(defun advice/org-roam-node-list (fn &optional force-refresh &rest args)
  (unless (and (not force-refresh)
	       org-roam-node--cache-list
	       org-roam-node--cache-time
	       (time-less-p
		(file-attribute-modification-time (file-attributes org-roam-db-location))
		org-roam-node--cache-time))
    (setq org-roam-node--cache-list (apply fn args))
    (setq org-roam-node--cache-time (current-time)))
  org-roam-node--cache-list)

(defun advice/org-roam-node-read--completions (fn &optional filter-fn sort-fn &rest args)
  (unless (and (eq filter-fn org-roam-node--cache-prev-filter-fn)
	       org-roam-node--cache-candidate-list
               org-roam-node--cache-time
	       (time-less-p
		(file-attribute-modification-time (file-attributes org-roam-db-location))
		org-roam-node--cache-time))
    (setq org-roam-node--cache-candidate-list (apply fn filter-fn sort-fn args))
    (setq org-roam-node--cache-time (current-time))
    (setq org-roam-node--cache-prev-filter-fn filter-fn))
  org-roam-node--cache-candidate-list)

(defun advice/org-roam-node-read--to-candidate (fn &rest args)
  (or (gethash args cache/org-roam-node-read--to-candidate)
      (let ((result (apply fn args)))
        (puthash args result cache/org-roam-node-read--to-candidate)
        result)))

(advice-add 'org-roam-node-list :around #'advice/org-roam-node-list)
(advice-add 'org-roam-node-read--completions :around #'advice/org-roam-node-read--completions)
(advice-add 'org-roam-node-read--to-candidate :around #'advice/org-roam-node-read--to-candidate)

BENCHMARKS

(cl-loop
 for i from 1 to 3
 collect (benchmark-run 1 (org-roam-node-read--completions)))

Return a list of the total elapsed time for execution, the number of
garbage collections that ran, and the time taken by garbage collection.

## Control
((7.649120578 54 5.009940180999999) (7.583503781 54 4.968937586999999) (7.5839354409999995 54 4.974406888000001))
((7.574322854 54 4.959506367000003) (7.5684444300000004 54 4.958837869999996) (7.570610555 54 4.965173413999999))

## With cache-ing org-roam-node-read--to-candidate
((7.878010436 81 5.239681224999998) (1.029478217 6 0.5180810800000017) (1.0431949680000001 6 0.5246768650000035))
((1.056822699 6 0.534673472999998) (1.038674243 6 0.5248725759999999) (1.037299049 6 0.5212900809999965))

## With cache-ing org-roam-node-read--to-candidates + org-roam-node-read--candidates
((1.045045204 6 0.527334610000004) (5.8931e-05 0 0.0) (1.4195e-05 0 0.0))
((5.2189000000000005e-05 0 0.0) (1.5915999999999998e-05 0 0.0) (1.3924000000000001e-05 0 0.0))

## With cache-ing org-roam-node-read--to-candidates + org-roam-node-read--candidates + org-roam-node-list
((4.9402e-05 0 0.0) (1.5792e-05 0 0.0) (1.3996e-05 0 0.0))
((4.5766e-05 0 0.0) (1.5731e-05 0 0.0) (1.405e-05 0 0.0))

Numbers are in scientific notation (in exponents)

28

I like using the advice. I was planning to write a decorator for the memoization (forgot that it is done by the advice).

thanks, I’ll use your version in my init. For my database (around 1000 nodes) org-roam-node-read–to-candidate seems good enough and it is the least intrusive of all of the caches. I’ll add a timer that invalidates the cache once a day.

1 Like
29

how do I read the results? I see the each row has 3 results, one after another.
but what does the second row mean?

you might want to invalidate the caches between sets of tests, so you get an accurate timing for each

30

The data is replicated twice for each case - each benchmark runs thrice, in total 2 benchmark runs were taken for each case - this duplication allows us to extract a confidence interval over the data. If the range between each benchmark run was wide for the same case then the benchmark is not useful to do control study.

The control case shows the benchmark when all cache is turned off for node size 20,000 (twenty thousand)

The last case of the benchmark gives wrong inference - to benchmark #'org-roam-node-list properly the cache over '#org-roam-node-node-read--candidates should be turned off. Apologies for oversight.

31

Thank you. Now I understand how it works and was able to use it.

In my computer the original org-roam-node-read–completions takes between 1.5 and 2 seconds. With the cache and the improves to the node processing only, it goes down to 0.15 seconds. one order of magnitude! and no need to worry about caching db data.

32

Seems you guys found a method to speed up org-roam around the same time as I gave up and wrote a replacement: GitHub - meedstrom/org-node: A notetaking system like Roam using Emacs Org-mode! A lot of the same ideas, with caching completions, and it has highlighted for me that there’s a bunch of things could be improved in org-roam.

For starters, there’s no good reason that building completion candidates should take so long that they need to be memoized. Org-node can build the candidates nearly instantly, and caches them anyway only because I want it to feel instant even on super-low-powered devices like a Kindle.

Aside from the matter of completions, you guys might have use of org-node-fakeroam-db-feed-mode if saving large files is slow. And org-node-fakeroam-db-rebuild if you frequently rebuild the DB.

3 Likes
33

I encourage you to try this minor mode:

Enable with org-roam-gt-mode-enable
and disable with org-roam-gt-mode-disable

This is the result of discussions with @akashp

  1. It optimizes the creation of the nodes (the original constructor is very slow)
  2. It replaces the code to format the node given the template. I gives the option of replacing the processing of the template (which is currently very expensive) with a call to a function.

The overall result is that, a typical database (say 1-2 k nodes) it feels instantaneous.

The best part is that there is no caching to worry about.

I plan to extend this minor mode with my improved template processing for org-roam (more in line with org templates).

I have been using it for more than 1 month and it seems stable. Since it does not modify the database, there is no risk to those using it (simply disable the minor mode if you don’t like it)

4 Likes