search

microsoft / TypeScript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
https://www.typescriptlang.org
Apache License 2.0
101.23k stars 12.52k forks source link

Investigate Wildcard Matching Performance #59058

Open DanielRosenwasser opened 5 months ago

DanielRosenwasser commented 5 months ago

Recently I investigated optimizing path matching in https://github.com/microsoft/TypeScript/pull/59048 since an internal project had over 5500 path mapping entries.

@dmichon-msft brought up a similar issue they had with a project where using wildcard entries in include caused a 14 second slowdown in their builds. Some of the same optimizations might be usable in include/exclude globbing, or we could adapt a different solution with a radix tree or a similar data structure (e.g. https://github.com/microsoft/rushstack/blob/1bf90f890d59de5babaf07ccc2551b77df704b18/libraries/rush-lib/src/logic/LookupByPath.ts as pointed out at https://github.com/microsoft/TypeScript/pull/59048#discussion_r1657649883).

dmichon-msft commented 5 months ago

Note that the performance issues were last checked in version 5.3.3 for include (exclude doesn't have a performance issue because it is already order-independent). The time was previously spent in the visitDirectory function.

The scenario being tested involved a project with ~750 single-file include patterns.

fatcerberus commented 5 months ago

5500 path mapping entries

😱 what is this I don’t even