Auditing an Accidentally Quadratic Indexer

Algorithmic complexity bugs are among the most consequential findings in code review engagements, yet they are routinely missed by both automated analysis tools and human reviewers. The reason is structural: the code that creates them looks correct. Each function does what it is supposed to do. The performance catastrophe emerges from the interaction between functions, specifically from an inner function whose cost is proportional to the size of the data being processed by an outer loop. During a code review of a language indexer—a tool that parses source code and emits structured symbol information—we identified a textbook case of accidental quadratic behaviour that turned a 24-second operation into an 8-minute one on a single moderately large input file.

The Root Cause

The indexer processed source files by walking the abstract syntax tree (AST) and emitting a record for each identifier: its name, type, position, and associated documentation comment. To find the documentation comment for a given identifier, the indexer called a findComments function that traversed the AST from the root, searching for comment nodes whose position immediately preceded the identifier's position. This traversal was O(n) in the number of AST nodes. Since it was called once per identifier, and the number of identifiers was also proportional to n, the overall complexity was O(n^2). For small files—a few hundred lines—this was imperceptible. For the file that triggered the investigation, an auto-generated API client with 94 exported constants, 76 struct definitions, and 510 method declarations, the quadratic behaviour was catastrophic. The AST contained tens of thousands of nodes. Each of the roughly 680 identifiers triggered a full traversal, resulting in millions of redundant node visits.

The fix was a single-pass comment cache. Before processing any identifiers, the indexer performed one traversal of the AST, building a map from source position ranges to their associated comment nodes. The per-identifier lookup then became a constant-time map access instead of a linear traversal. This single change reduced the processing time for the problematic file from over 7 minutes to under 2 seconds. The total indexer runtime for the repository containing this file dropped from 8 minutes to 24 seconds.

I/O and Concurrency Findings

The same review uncovered two additional performance issues with security implications. First, the indexer wrote its output using unbuffered I/O, issuing a system call for every record emitted. On a file that produced 50,000 records, this meant 50,000 write syscalls. Wrapping the output in a buffered writer with a 64 KB buffer reduced the syscall count by 98% and cut I/O time proportionally. The security relevance is indirect but real: excessive syscalls increase the process's scheduling overhead and make it more susceptible to resource contention under concurrent load. In a CI/CD environment where indexers run in parallel across hundreds of repositories, this overhead compounds into measurable infrastructure cost and increased vulnerability to noisy-neighbour effects.

Second, the indexer processed files sequentially within each repository. We restructured it to process files in parallel using a bounded worker pool. The synchronisation primitive we recommended was a striped mutex scheme: rather than using a single global lock (which would serialise all workers) or a per-key lock (which, with 50,000+ keys, would consume 2.7 GB of memory for mutex objects alone), we used a fixed array of 256 mutexes and hashed each key to a stripe. This provided sufficient concurrency—workers only blocked when two happened to hash to the same stripe—with fixed, predictable memory overhead. The parallel implementation with striped locking achieved the full 24-second runtime on a machine with 8 cores, processing files roughly 6 times faster than the sequential version.

The engagement reinforced a principle we apply to every code review: performance characteristics are security characteristics. An accidentally quadratic algorithm is not merely slow; it is a resource exhaustion vector. If an attacker can submit or cause the processing of an input that triggers worst-case behaviour, they can consume arbitrary amounts of CPU, memory, or I/O bandwidth. In this case, the attacker would not even need to craft a malicious input—they would only need to point the indexer at a legitimately large, auto-generated source file, the kind that exists in nearly every enterprise codebase. Identifying and eliminating superlinear complexity in data processing paths is as much a security activity as input validation or access control, and should be treated with the same rigour in code review.