fs.realpath 70x slower than native

[stefanpenner]

repost of nodejs/node-v0.x-archive#7902 to ensure it is not lost, as per @jasnell suggestion.

credit goes to @joliss I am merely transplanting the issue.

---

The fs.realpath function is 70x slower than native C realpath. On my system, fs.realpath takes 32 µs, while C realpath takes 0.45 µs.

This is a real problem in the Broccoli build tool, where we need to resolve symlinks in hot code paths. Resolving 1000 symlinked files - not an unusual case - would take 45 ms, slowing down the build considerably. [1]

As for a solution: I haven't looked at the fs.js source in detail, but it seems we might be able to call the realpath function in the C standard library, where available, instead of using our own implementation.

Benchmark code for Node:

var fs = require('fs')

var start = Date.now()
var n = 10000
for (var i = 0; i < n; i++) {
  if (fs.realpathSync('.') === 'dummy') throw new Error('never happens')
}
console.log(((Date.now() - start) * 1000 / n) + ' us') // => 32 us on Node 0.11.13

Benchmark code for C:

#include <limits.h> /* PATH_MAX */
#include <stdio.h>
#include <stdlib.h>

// Adapted from http://stackoverflow.com/a/1563237/525872

int main(void) {
  char buf[PATH_MAX + 1]; /* not sure about the "+ 1" */
  int i;
  for (i = 0; i < 1000000; i++) {
    char *res = realpath(".", buf);
    if (res) {
      // printf("This source is at %s.\n", buf);
    } else {
      perror("realpath");
      exit(EXIT_FAILURE);
    }
  }
  return 0;
}

Run with gcc -std=gnu99 realpath-benchmark.c -o realpath-benchmark && time ./realpath-benchmark. This yields 0.45 µs per iteration on my Linux system.

[1] We cannot work around this by using naïve string concatenation, because path_resolution(7) requires that we resolve symlinks in all path components. Here is a gist to show why this matters.

[ChALkeR]

@stefanpenner, about your hot path: does it modify those symlinks (or parent directories) in the same hot path? If not, you could pass a cache argument, it would speed up fs.realpath (and fs.realpathSync) several times. Not 70, though.

For example, if you resolve a lot of symlinks in the same dir in a loop, it could help to use a single cache for all those fs.realpath calls.

[ChALkeR]

Ah. @joliss ↑↑

[stefanpenner]

@ChALkeR i was about to implement something (what i believe to be) very similar. Can you share docs on cache argument?

cache is an object literal of mapped paths that can be used to force a specific path resolution or avoid additional fs.stat calls for known real paths.

-- source: the docs

[Fishrock123]

@stefanpenner https://iojs.org/api/fs.html#fs_fs_realpath_path_cache_callback

[ChALkeR]

@stefanpenner Also, each fs.realpath call updates the passed cache object, when needed.
So using a single object (initialized with {} at the start) for several calls would save some time.

[ChALkeR]

@Fishrock123 Btw I think the above fact isn't properly documented.

[stefanpenner]

@Fishrock123, btw, I think the above fact isn't properly documented.

I would agree, but largely due to this pattern not being very common in the stdlib, so i wasn't looking for it.

I'll give this pattern a try in the next day or so and report back. It may prove to be a nice win.

That being said, we shouldn't assume this is the solution and a fast realpath should still be the goal.

[Fishrock123]

Repost of @trevnorris at nodejs/node-v0.x-archive#7902 (comment)

Here's the flamegraph for fs.realpathSync('.'): https://i.cloudup.com/n9pPZFuyc0.svg

[Fishrock123]

Fwiw I'm +1 on using realpath(3) when possible.

[thefourtheye]

Why can't this be proposed to uv and we use it?

[Fishrock123]

Why can't this be proposed to uv and we use it?

Depends if it is available cross-platform or not.

Looks like this would be on windows though? https://msdn.microsoft.com/en-us/library/windows/desktop/aa364963(v=vs.85).aspx

[stefanpenner]

IMHO Libuv would be the ideal place for this.

[ronkorving]

cc @saghul @bnoordhuis

[saghul]

Another options would be _fullpath, though we tend to prefer to use NT APIs.

A quick search for how MinGW handles this tells that sadly none of these functions check for junction point loops, whereas realpath(3) does.

I'd be fine having it in libuv, if someone wants to do the work :-)

[thefourtheye]

@saghul I would like to try my hand at implementing it :-)

[saghul]

Go for it!

[trevnorris]

Is the consensus then to wait for uv_realpath() before implementing anything here?

[trevnorris]

Since this is such low hanging fruit in terms of performance, I'd prefer we make the change to use realpath(3) where supported.

[jhamhader]

1. I wrote a native uv_realpath() for Linux libuv and it seems like the above test goes down to about 4.3 µs (no cache). @trevnorris - is that acceptable? (If so, I will prepare a PR for libuv)
2. Is GetFullPathName() the way to go for Windows?

[stefanpenner]

@jhamhader awesome :)

[saghul]

@jhamhader See the note for GetFullPathName:

Note  The GetFullPathName function is not recommended for multithreaded applications or shared library code. For more information, see the Remarks section.

Whereas realpath seems to be MT safe.

Also:

This function does not verify that the resulting path and file name are valid, or that they see an existing file on the associated volume.

Last, naming: it should be called uv_fs_realpath.

@thefourtheye are you also working on this? Let's not duplicate efforts! :-)

[jhamhader]

@saghul Currently:

• libuv: created uv_fs_realpath() (linux implementation + tests)
• node: modified fs.realpath() and fs.realpathSync() to use the libuv implementation
• node: tests
• libuv: Windows uv_fs_realpath()

I will try to finish that over the weekend.

[thefourtheye]

@saghul I completed the Linux part but couldn't test in other platforms. So lets go with @jhamhader's work itself.

[jhamhader]

Resolving realpath using the above test:

	No Cache	Cache
Current	50 µs	9 µs
Native	1 µs	9 µs

Using cache with the native realpath degrades performance.

However, one issue bothers me:
In the current implementation, we iterate each path component, checking whether it is already in cache in order to optimize performance. This backfires when using the native implementation with cache. Checking each individual path component when using the native implementation degrades performance even more.

Performance can be optimized by looking only for the full absolute path in the cache. However, then the 'test_lying_cache_liar' from test-fs-realpath.js fails - it 'fakes' partial path and expects us to resolve it according to cache. By not trying to resolve each path component, this behavior can not achieved.

[ChALkeR]

@jhamhader It is a documented behavior of cache:

cache is an object literal of mapped paths that can be used to force a specific path resolution or avoid additional fs.stat calls for known real paths.

That behavior should not be broken, and I guess there is no way around the fact that «Native» implementation would be slower when cache is present. It won't be slower then what we have now, so it's still an improvement.

[trevnorris]

Can you explain what this is getting at?

can be used to force a specific path resolution

And the latter part is pointless since native would remove Stat calls.

[ChALkeR]

@trevnorris

require('fs').realpathSync('/HOME/.config', {'/HOME': '/home/user/'})
'/home/user/.config'

Is a perfectly fine usage example, isn't it? And that is currently documented.