Resolver perf: Implement TreeFS.hierarchicalLookup for getClosestPackage (2/n)

[robhogan]

Summary: Implement a new method on TreeFS that is able to "natively" perform hierarchical lookup, such as frequently used during node_modules resolution, config path resolution, etc., and use it initially to find the closest package scope of a given candidate path (context.getClosestPackage()).

This operation currently dominates resolution time, with an algorithm that uses repeated path.dirname() and fileSystem.lookup(). The current algorithm is O(n^2) on path segments (~length), because the outer loop is O(n) and each lookup is O(n) - additionally, it's slow in constant time because each path.dirname() and path.join() involves unnecessarily parsing and normalising their own outputs - path.join() calls alone account for >30% of resolution time.

The new implementation:

• Performs a lookup on the start path, collecting a list of all nodes along the way.
• Looks back through each node, and checks for the existence of the subpath on each one.

Benchmarks based on collecting and running all resolutions performed during a build of rn-tester:

Before

• Total resolution time: 1210ms
• Time in getClosestPackage: 910ms

After

• Total resolution time: 390ms (~3x faster)
• Time in getClosestPackage: 105ms (~9x faster)

Differential Revision: D58062988

[facebook-github-bot]

This pull request was exported from Phabricator. Differential Revision: D58062988

[facebook-github-bot]

This pull request was exported from Phabricator. Differential Revision: D58062988

[facebook-github-bot]

This pull request was exported from Phabricator. Differential Revision: D58062988

[facebook-github-bot]

This pull request was exported from Phabricator. Differential Revision: D58062988

[facebook-github-bot]

This pull request has been merged in facebook/metro@62feafa072cf2a99bec18bfdb7602c8a55054390.