`capture_list_pool_acquire` scans the whole pool for a free list

Author: ericmjCreated Sep 16, 2026Updated Sep 16, 2026

AI Policy

I have read the AI Policy and this issue complies with it.

Problem

capture_list_pool_acquire in lib/src/query.c (line 483 at 1b8407d) finds a free capture list by walking list from index 0 until it hits one whose size is the UINT32_MAX sentinel. The pool grows up to the match limit, so once many states hold lists at the same time each acquire costs O(pool size) and a capture pass costs O(captures × pool size).

The nvim-treesitter html highlights query hits this. Each of its 13 (element (start_tag (tag_name) @_tag) (text) @markup.*) patterns captures @_tag at the start tag and then waits for a (text) child that usually never comes, so the list stays allocated until the element closes. On a 90 KB document of nested table markup that keeps around 100k lists in use, and every capture after that walks through them.

Timing from the program below over <tr><td>…</td></tr> rows inside one <div><table><tbody>, html injections + locals + highlights queries, match limit 65535, min of 3 runs, master at 1b8407d:

rows	bytes	time
500	43 KB	187 ms
1000	86 KB	531 ms
2000	172 KB	573 ms
4000	344 KB	645 ms

With the match limit at 4096 the same runs are fast, because the pool never grows far enough for the walk to matter.

Disclosure: the analysis, the benchmark and the patch at https://github.com/ericmj/tree-sitter/tree/capture-list-pool-free-stack were produced with an AI coding agent.

Steps to reproduce

Build libtree-sitter.a from master, take src/ from the tree-sitter-html 0.23.2 crate, and concatenate the nvim-treesitter html queries injections.scm, locals.scm, highlights.scm with the inherited html_tags queries inlined (the file I used is queries/processed/html/*.scm from https://github.com/leandrocp/lumis/tree/b2fe0dc/queries/processed/html, in that order). Then:

bash

cc -O2 -I lib/include -I tree-sitter-html/src tsbench.c tree-sitter-html/src/parser.c tree-sitter-html/src/scanner.c libtree-sitter.a -o tsbench
./tsbench html-combined.scm

tsbench.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "tree_sitter/api.h"

const TSLanguage *tree_sitter_html(void);

static char *slurp(const char *path, size_t *len) {
  FILE *f = fopen(path, "rb");
  if (!f) { perror(path); exit(1); }
  fseek(f, 0, SEEK_END); long n = ftell(f); fseek(f, 0, SEEK_SET);
  char *buf = malloc(n + 1);
  size_t got = fread(buf, 1, n, f); buf[got] = 0; fclose(f);
  *len = got; return buf;
}

static double now_ms(void) {
  struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts);
  return ts.tv_sec * 1000.0 + ts.tv_nsec / 1e6;
}

int main(int argc, char **argv) {
  size_t qlen; char *qsrc = slurp(argv[1], &qlen);
  uint32_t err_off; TSQueryError err_type;
  const TSLanguage *lang = tree_sitter_html();
  TSQuery *query = ts_query_new(lang, qsrc, qlen, &err_off, &err_type);
  if (!query) { fprintf(stderr, "query error %d at %u\n", err_type, err_off); return 1; }

  const char *row = "<tr><td>field_name</td><td>string</td><td>Some description of the field here</td></tr>";
  size_t rowlen = strlen(row);
  int sizes[] = {500, 1000, 2000, 4000};
  printf("%6s %10s | %10s %10s | captures\n", "rows", "bytes", "lim 65535", "lim 4096");
  for (int s = 0; s < 4; s++) {
    int n = sizes[s];
    size_t cap = rowlen * n + 128;
    char *src = malloc(cap);
    int off = sprintf(src, "<div><table><tbody>");
    for (int i = 0; i < n; i++) { memcpy(src + off, row, rowlen); off += rowlen; }
    off += sprintf(src + off, "</tbody></table></div>");
    TSParser *parser = ts_parser_new();
    ts_parser_set_language(parser, lang);
    TSTree *tree = ts_parser_parse_string(parser, NULL, src, off);
    uint32_t limits[2] = {65535, 4096};
    double best[2]; uint32_t caps = 0;
    for (int l = 0; l < 2; l++) {
      best[l] = 1e18;
      for (int rep = 0; rep < 3; rep++) {
        TSQueryCursor *cur = ts_query_cursor_new();
        ts_query_cursor_set_match_limit(cur, limits[l]);
        double t0 = now_ms();
        ts_query_cursor_exec(cur, query, ts_tree_root_node(tree));
        TSQueryMatch m; uint32_t idx; uint32_t k = 0;
        while (ts_query_cursor_next_capture(cur, &m, &idx)) k++;
        double dt = now_ms() - t0;
        if (dt < best[l]) best[l] = dt;
        caps = k;
        ts_query_cursor_delete(cur);
      }
    }
    printf("%6d %10d | %8.0fms %8.0fms | %u\n", n, off, best[0], best[1], caps);
    ts_tree_delete(tree); ts_parser_delete(parser); free(src);
  }
  return 0;
}

Expected behavior

Acquiring a capture list costs O(1), so capture time grows with the document, not with how many lists the pool holds. The branch linked above keeps the free ids in a stack and gives 35 / 74 / 116 / 197 ms for the four sizes with identical captures.

Tree-sitter version (tree-sitter --version)

master at 1b8407d (Cargo.toml 0.28.0)

Operating system/version

macOS 26.6.2, arm64

Source: tree-sitter/tree-sitter

View original on GitHub View discussion on GitHub