tree-sitter navigation speed test

test_treesitter.el

(let (cnt tm node res)
  (goto-char (point-min))
  (while (< (point) (point-max))
    (setq tm
          (benchmark-run 100
            (setq node (treesit-node-at (point)))
            (while node
              (setq node (treesit-node-parent node))))
          node (treesit-node-at (point)))
    (setq cnt 0)
    (while node (setq node (treesit-node-parent node)) (cl-incf cnt))
    (setq res (push (cons cnt tm) res))
    (beginning-of-line 2))
  (with-output-to-temp-buffer "*ts-test-output*"
    (cl-loop for (cnt tau ngc tgc) in (nreverse res)
             for i from 1
             do (princ (format "%d\t%d\t%f\t%d\t%f\n"
                               i cnt (* tau 10) ngc (* tgc 10))))))

ts_plot.py

import matplotlib.pyplot as plt
import numpy as np
plt.clf()
d=np.loadtxt('test.dat')
sc=plt.scatter(d[:,0],d[:,2], c=d[:,1], alpha=0.5, s=60, cmap='rainbow', linewidths=0)
plt.xlabel('Line Number')
plt.ylabel('Root Navigation Time (ms)')
plt.title('Tree Sitter Navigation Time\nfrom start of each line in _axes.py')
plt.colorbar(sc, label='Node Depth')
plt.xscale('log')
plt.yscale('log')
plt.tight_layout()
first = d[d[:,0]<=10,:]
fac = np.mean(np.sqrt(first[:,0])/first[:,2])
plt.plot([1,1e4],np.sqrt([1,1e4])/fac, label='$t\propto\sqrt{N}$')
plt.legend()
plt.savefig('ts.png', dpi=300)

Update: a similar test for treesitter-node-at shows very slow growth with line number (after excluding points with GC occurring):

Another update: this plot compares the time taken to find a node at point with locating it's parent, both off which should be using positional winnowing to skip branches of the syntax tree that do not contain point.

I have applied a patch developed by Dimitry Gutov, which uses ts_node_parent, vs. the original ts_tree_cursor_goto_parent, on a freshly compiled NS build of main. The results are striking:

With ts_tree_cursor_goto_parent (current design of node-parent):

This looks quite similar to the emacs-29 results.

With ts_node_parent (Dimitry's patch):

Note the reduced y range and much shallower scaling. This indicates that the scaling and long navigation time at the end of the file are related to the cursor walk, not the parent search from root per se. The patched version results also make more sense in terms of their similar logarithmic growth as node-at-point, since the method of search for a node at point and for its parent is quite similar.

Another new patch, from Yuan Fu, retains the cursor walk, but applies a byte position pruning. These look like:

So intermediate between the two, rising to about 300µs, i.e. 10x faster than the current algorithm. node_parent is still ~10x faster yet, and rises more slowly across the tree.

An updated patch along these lines, which trims the tree search using both the start and end coverage position of nodes:

This has similar performance and scaling as the simple node_parent version above. Looks like the right solution.