Show HN: Fdir – Faster Node.js glob alternative | Hacker News Reader

Show HN: Fdir – Faster Node.js glob alternative

github.com

48 pointsthecodrr30 comments

Hey everyone,

I recently created fdir mostly out of curiosity about how fast a program written in Node.js could be. It so happened that I (accidentally) created the fastest directory crawler in the NodeJS environment. fdir can easily crawl around 1 million files in under 1 second. 1 million files distributed in about 100k directories. (your mileage may vary depending on hardware).

It's also < 1kb in size (gzipped). Supports all node versions (> 6).

Feel free to give it a run and ask me any questions (if any) :D

Blog post: https://dev.to/thecodrr/how-i-wrote-the-fastest-directory-cr...

Take care, thecodrr

Hi! Thanks for sharing, this could be promising for build tooling.

What tools/processes did you use to optimize performance here?

That is one of the potential use cases behind fdir. I am actively using it for a testing framework (private).

The main methodology was benchmarking every little line of code. Since JS has many alternatives for every thing, I had to benchmark a lot of code.

No special tools were used. The performance gains are mostly from not using recursion, less function calls etc. It could further be optimized of course (and I am working on that).

Thanks for taking the interest :)

Do you mind sharing how you did the benchmarking? console.time, inspector?

I used `benny`. If you have a NodeJS setup you can easily run the benchmarks by:

  npm install

And then:

  node benchmark.js

That will start the asynchronous and synchronous benchmark sequentially.

Thanks for taking the interest.

Edit: benny uses the Benchmark.js library underneath.

I don't like it when a software description includes claims like "fast", "lightweight", "secure", "simple".

That is not an intrinsic trait of your software, just an aspirational thing.

How is it not an intrinsic trait? Is "bloated", "huge", "slow" an intrinsic trait of a software? If so then the opposite should be true as well.

The claims are true intrinsic or not and they are also claims other software developers classify different libraries with.

You define it/describe it as being "the fastest".

This claim translates into: for the universe of libraries that do this same thing, this has the best performance for each one of the features this library provides.

That is claim that is not very hard to disprove. You only need 1 library that does better in one specific way and the claim is invalidated. It is a very broad claim.

Then, performance in node is very subjective. The same code can perform better or worse depending on node/v8 versions. Can perform better or worse depending on which parameters you used, or how many times a function was invoked.

You say "1m files in < 1s" but your benchmark has N=7386.

Then: what filesystem was used? was it encrypted? was it in a RAID array? There is some missing context here as well.

You seem to have read that statement wrong. I never said the fastest directory crawler on Planet earth. I said "the fastest directory crawler for NodeJS" restricting that claim because I am aware of the implications and how far-fetched it would sound.

As for the "1m files in < 1s", yes I benchmarked that privately. That is not a false statement and to back that up, I will be uploading a gif showing the time (once the cli for fdir is done).

> The same code can perform better or worse depending on node/v8 versions.

I provided benchmarks for 2 node versions. The benchmark was fair for all libraries. It was run in the same way on the same machine for the same number of times on the same directory. So relatively the results should be fair. They were all also used barebones without parameters. Of course each library has its own approach. I cannot be held accountable for that.

> what filesystem was used? was it encrypted? was it in a RAID array? There is some missing context here as well.

You seem to have missed the whole point. You seem knowledgeable enough so let me say it in simple words. All node libraries that crawl directories for files use the `fs` module internally. Now, fs uses LibUV underneath. That is true for all libraries. There's no exception (to my knowledge). Now since the underlying i/o and the v8 engine are exactly the same, the only thing that makes the difference (and very slight at that) is the logic. Fdir wins only against other node libraries through that logic not because of some new i/o approach.

The figure 1m files in < 1s is just to give an idea of speed not to show that you'll be getting the same exact number.

I am aware of how fragile this claim is but until there comes a faster libraries I have the right to hold it. :)

- There are millions of modules on npm and you are claiming this is the fastest of them all? I doubt it, and not only I doubt it: I find it misleading since it's hard to verify and reflects a lack of humility. To say "Our goal is to have the fastest node module" or "A module with performance in mind" is VERY different to "The fastest module".

- If I decide to use your code for something serious I cannot take your numbers for granted. The benchmark methodology does matter. You need show some signs of rigor so other people can assess how credible your claims are.

- Did you run this benchmark in a controlled environment without other processes running? Did you disable frequency scaling before running your benchmark? If you ran it in a desktop computer with a bunch of other stuff running and frequency scaling enabled then your processor speed was constantly oscillating while running your benchmark and the numbers are completely random.

- Did you know that v8 is full of optimizations that are conditional to how your code is written? Did you know that even a comment can dramatically affect how your code is treated by v8? In some cases V8 just gives up trying to optimize your code. Did you profile your code? did you trace v8 deoptimizations? Even if you did, you should not say this:

    Why are all the other libraries so slow?

    Because they did not spend enough time optimizing it.
    Most developers give readability and cool code more importance
    than actual performance and usability.

It's really the self-promoting tone and unbelievable claims that make the README file so irritating.

All projects make trade-offs on values, and I'm happy to see what values the author would like to identify their project with. Unless the project is already done and in maintenance mode, yes, it's aspirational.

It is also irresponsible and misleading to say it. It is self-promoting in a way that is against the best interest of the user.

We are engineers not snake oil salesmen.

This here looks wrong: https://github.com/thecodrr/fdir/blob/master/index.js#L86 It's calling a blocking method from async in Node <10

Another thing I noticed, it looks you only handle `dirent.isDirectory()`, but not `dirent.isSymbolicLink()` (meaning the library won't find files in symlinked folders, e.g. lerna node_modules)

> Because they did not spend enough time optimizing it. Most developers give readability and cool code more importance than actual performance and usability.

Aged like milk.

Hey, thanks for taking the interest.

Yes, that sync method call is intentional (for now) +. I have been meaning to add separate lstat call for async/sync for < node 10 without impacting performance. So that will change. Thanks for pointing that out.

Handling symlinks is work in progress. (it will be exposed as an option that you can enable/disable because symlinks resolution is expensive and not everyone wants that).

This has absolutely nothing to do with globbing. The title is very misleading – I was super excited to see a new glob library.

How so? You can easily extend the searchFn to do the glob matching of files for you. I wanted to keep it dependency free. So I fail to see how fdir has "absolutely nothing to do with globbing"? Care to explain?

Not parent, but I think their argument is that this lib doesn't implement a glob interface so calling it a glob alternative is misleading, i.e. one cannot easily replace a globbing library with this if they expose the glob DSL as an interface. It's more accurate to say that your lib is a recursive-readdir alternative.

In that case, fair enough. But no reason to be dishearted, we can always make "fdir-glob" that has globbing built in :D but you are right, not an easy* alternative but still an alternative.

Would you mind changing the submission title? Your library simply does not glob (that's a word with fixed meaning), which is likely a rather expensive part of the hot path for real use cases.

Aside: Looking at the hyperfine results below, have you benchmarked this JS optimization vs. implementing it in C++ instead and consuming the results of that?

Hey, thanks for the interest. No, I cannot change the title because I don't have editing capabilities anymore.

I don't see the point of implementing it in c++ simply because I wanted to keep it simple, dependency free and easy to maintain. The fact that I know very little C++ also influenced that decision. Moreover, I am sure that way would be faster (from my understanding).

The upside would be that you can specifically control when to pass values between the underlying C++ and the v8 runtime.

But anyway, this implementation is quite nice. I tried to recreate a more meaningful benchmark between a few of the libraries you compared with but on a real file system structure rrdir and node-walk just noped out by exceeding the maximum call stack size. Increasing that yielded pretty much the same results as your library for rrfind in the sync setting with the overhead likely being down to that one returning an object (mean difference between 50-100ms higher on ~1.1 million files).

You give a very valid reason to tryout an implementation in C++. I will definitely look into it. Thanks.

Would love to see the benchmark results! Do share a link if you can.

Thanks for auditing and taking the interest!

I took it for a ride

They all list all files recursively in a sync fashion, from the node_modules dir (like in the benchmark), excluding dirs, and print a total count.

Here are the results calculated with hyperfine (https://github.com/sharkdp/hyperfine):

    hyperfine "bash test.sh" --warmup 5
    Benchmark #1: bash test.sh
    Time (mean ± σ):       7.5 ms ±   0.5 ms    [User: 4.5 ms, System: 4.2 ms]
    Range (min … max):     6.9 ms …  10.5 ms    332 runs

    hyperfine "perl test.pl" --warmup 5
    Benchmark #1: perl test.pl
    Time (mean ± σ):      25.6 ms ±   1.2 ms    [User: 16.8 ms, System: 8.8 ms]
    Range (min … max):    24.0 ms …  30.8 ms    97 runs

    hyperfine "python3.7 test.py" --warmup 5
    Benchmark #1: python3.7 test.py
    Time (mean ± σ):      43.4 ms ±   1.4 ms    [User: 32.6 ms, System: 10.9 ms]
    Range (min … max):    40.9 ms …  46.8 ms    66 runs
    
    hyperfine "ruby test.rb" --warmup 5
    Benchmark #1: ruby test.rb
    Time (mean ± σ):      66.5 ms ±   2.0 ms    [User: 52.1 ms, System: 14.4 ms]
    Range (min … max):    63.2 ms …  70.3 ms    42 runs

    hyperfine "node test.js" --warmup 5
    Benchmark #1: node test.js
    Time (mean ± σ):      83.7 ms ±   4.0 ms    [User: 74.7 ms, System: 15.6 ms]
    Range (min … max):    79.4 ms …  95.3 ms    36 runs

Here are the results of an hello world with each runtime for comparison:

    hyperfine "bash test.sh" --warmup 5
    Benchmark #1: bash test.sh
    Time (mean ± σ):       1.2 ms ±   0.3 ms    [User: 1.1 ms, System: 0.3 ms]
    Range (min … max):     0.9 ms …   3.8 ms    1521 runs

    hyperfine "perl test.pl" --warmup 5
    Benchmark #1: perl test.pl
    Time (mean ± σ):       1.3 ms ±   0.3 ms    [User: 1.3 ms, System: 0.3 ms]
    Range (min … max):     1.0 ms …   5.3 ms    1103 runs

    hyperfine "python3.7 test.py" --warmup 5
    Benchmark #1: python3.7 test.py
    Time (mean ± σ):      19.5 ms ±   0.9 ms    [User: 16.2 ms, System: 3.4 ms]
    Range (min … max):    18.3 ms …  23.7 ms    144 runs

    hyperfine "ruby test.rb" --warmup 5
    Benchmark #1: ruby test.rb
    Time (mean ± σ):      55.2 ms ±   2.2 ms    [User: 47.2 ms, System: 8.1 ms]
    Range (min … max):    52.2 ms …  61.9 ms    51 runs
    
    hyperfine "node test.js" --warmup 5
    Benchmark #1: node test.js
    Time (mean ± σ):      55.4 ms ±   1.8 ms    [User: 49.5 ms, System: 7.0 ms]
    Range (min … max):    53.0 ms …  60.0 ms    53 runs

Now, my machine is not setup for a clean benchmark. The disk cache is warmed up. Hyperthreading is on. Other softwares are running.

Plus the scripts all found a slightly different number of files :) I suspect they all treat symlinks/dotted dirs differently, and I didn't take the time to normalize. Although I don't think this makes up for the difference.

Still the result is a bit interesting. The non JS tests are not using any 3rd party libs. Ruby and Node seems to have the same cost for VM startup.

I'm quite surprised that node is last frankly, especially on a uber optimized code. I'm expecting V8 code to be blazing fast as it's Google made and C++.

1) Did you take frequency scaling into consideration while benchmarking?

2) v8 doesn't make your code blazing fast by default. It has many optimizations but your code may be written in a way that v8 cannot fully optimize.

3) I recommend this tool as an alternative to using "time": https://github.com/sharkdp/hyperfine

As stated: "the times varied a lot because my machine is not setup for a clean benchmark"

So this is not a benchmark. Just a fun observation of a trend. A proper benchmark would require to have a dedicated machine with no other softwares running, hyperthreading off and run each of them a 100 times, without fs cache.

EDIT: gonna edit the original post with hyperfine results.

Hey, thanks for taking the interest and the time to audit and benchmark.

You can get a rough idea of VM startup time by running a simple hello world program.

fdir is supposed to compete against nodejs alternatives so I am not surprised it comes last. Maybe the next goal should be to optimize it against other cross language platforms.

V8 does a lot of optimizations but there is still overhead. A native solution in bash has little to no overhead so no wonder it's the fastest.

Anyway, thanks again. This benchmark was insightful (also humbling).

Gonna add test with hello world to see vm startup time.

If we subtract the vm time from total time that should (very roughly) be the time taken for fdir to crawl the directory.

So basically:

83ms - 55ms = 28ms

Not bad, not bad. :D the scale remains the same tho so not that beneficial.

This is a replacement for walk, not glob.

Reply on news.ycombinator.com