Build a high-performance version of `resolve`

[cpojer]

In Jest, we use jest-resolve to resolve modules. However, it shells out to two other dependencies, resolve and browser-resolve. resolve hasn't been maintained as much as I'd like, we have a hacky workaround inside of jest-resolve and we actually have knowledge of the entire filesystem (minus directories) in "HasteFS" (currently not passed to jest-resolve but that can be changed as the places it is created already passes a "ModuleMap" which is also coming from jest-haste-map).

The idea is to take the synchronous part of resolve and put it inside of jest-resolve. Then rewrite it and fine-tune it for performance (cc @trueadm) and use "HasteFS" to optimize the best case scenario (you can use jest-file-exists which is O(1) in the best case and fs.stat in the worst case).

The end state should be for Jest not to depend on resolve any longer. We do not need the asynchronous part of resolve.

Call to resolve: https://github.com/cpojer/jest/blob/master/packages/jest-resolve/src/index.js#L84
See: https://github.com/substack/node-resolve/blob/master/lib/sync.js

Follow-up: We should also aim at replacing browser-resolve and making it configurable so that our resolution algorithm can look at any field in package.json to re-route resolution to a module. This can be done in a follow-up, because this is already a big task :)
browser-resolve: https://github.com/defunctzombie/node-browser-resolve

cc @DmitriiAbramov @wanderley

[quantizor]

@cpojer I made a follow up comment in my PR about part 2 of this issue. Waiting for your response to finish the implementation in the current state of things.

[urish]

Update (re #3597) - I added a super simple memoization to resolve/lib/sync.js, seems like it does the trick for me: the number of statSync() calls dropped by an order of magnitude

[tvald]

Since HasteFS isn't available to the public, are there any other plans to improve the performance of resolve?

[cpojer]

HasteFS is open source and part of jest-haste-map, it's simply a simple virtual filesystem that contains a list of all files in a project.

[sebinsua]

@cpojer Is there a guide to setting this up?

[cpojer]

It's all automatic, jest-haste-map is used throughout Jest. jest-resolve only uses ModuleMap but not HasteFS. We can update it to use HasteFS and fall through to fs if the file isn't found. This would optimize the average case, but not worst case, of resolving modules.

[urish]

Here is the workaround I use in my setup to speedup jest-resolve:

https://gist.github.com/urish/1a106ad6d1dbfcf77f5f744ae854fd6a

For me, this small change reduces the test suite run time from about 21 to 14 seconds when using workers, and from about 27 seconds to 16.5 seconds when using --runInBand (I have an Angular app with 250 tests)