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)

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.