HOW WE ACCIDENTALLY MADE ROUTE MATCHING MORE PERFORMANT BY AIMING FOR CORRECTNESS

Summary from the TLDR Dev newsletter

TanStack Router achieved a 20,000× performance improvement in route matching by switching from a flat list iteration approach to a segment trie data structure. This changed the algorithmic complexity from O(N), based on the number of routes, to O(M), based on pathname segments. It also added backwards stack processing, bitmasking for optional segments, and reusing typed arrays for parsing to further boost performance across both small apps (60× faster) and large apps (10,000× faster).