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
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).
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.
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++.
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).
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.
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).
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).
31 comments
[ 2.5 ms ] story [ 77.7 ms ] threadI 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
What tools/processes did you use to optimize performance here?
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 :)
Thanks for taking the interest.
Edit: benny uses the Benchmark.js library underneath.
That is not an intrinsic trait of your software, just an aspirational thing.
The claims are true intrinsic or not and they are also claims other software developers classify different libraries with.
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.
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. :)
- 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:
It's really the self-promoting tone and unbelievable claims that make the README file so irritating.We are engineers not snake oil salesmen.
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):
Here are the results of an hello world with each runtime for comparison: 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++.
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
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.
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).
So basically:
83ms - 55ms = 28ms
Not bad, not bad. :D the scale remains the same tho so not that beneficial.
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)
Aged like milk.
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).
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?
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).
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).
Would love to see the benchmark results! Do share a link if you can.
Thanks for auditing and taking the interest!