[audit][perf] Remap path Trie uses 2KB 256-way nodes: one dependent cache miss per URL path character on every lookup

Severity: medium · Category: performance
Location: include/tscore/Trie.h:111

What's wrong

UrlMappingPathIndex::Search (src/proxy/http/remap/UrlMappingPathIndex.cc:91) runs Trie::Search on the request path for every hash-mapped remap lookup. Each Trie node holds 'Node *children[256]' plus value/occupied/rank (~2072 bytes), and Search performs 'curr_node = curr_node->GetChild(key[i])' — a dependent pointer chase into a fresh 2KB heap block per path character until the deepest matching rule prefix. Nodes are individually ats_malloc'd (Trie.h:105), so consecutive characters have no locality: a config whose rules share a 30-character path prefix costs ~30 serialized cache misses per request, per table consulted. The layout is also memory-hostile at config scale (one 2KB node per distinct prefix character across all rules), which further guarantees the working set does not fit in cache.

Evidence

Trie.h:76: static const int N_NODE_CHILDREN = 256;
Trie.h:111: Node *children[N_NODE_CHILDREN];
Trie.h:105: child = static_cast<Node *>(ats_malloc(sizeof(Node)));
Trie.h:210-211: curr_node = curr_node->GetChild(key[i]); ++i;

Suggested fix

Replace with a compressed radix tree (path compression collapses shared prefixes to one node with an inline string compare) or a flat structure; even a first step of storing edges as a small sorted array instead of 256 pointers would cut node size ~60x and make the walk mostly cache-resident.

Filed from an automated multi-lens codebase audit. Full report: CODEBASE_AUDIT.md / audit-report.html on branch claude/codebase-audit-review-9nw7vz.

Start with include/tscore/Trie.h:76, 105, 111, and 210-211, then trace UrlMappingPathIndex::Search in src/proxy/http/remap/UrlMappingPathIndex.cc:91. Compare the proposed radix-tree or flatter edge representations against the current node layout and lookup path. Done means reducing per-node memory and dependent cache misses without changing remap path matching behavior.