<p>I was curious about whether <code>filepath.Walk</code> is the fastest way to list files recursively in Go. I wrote a package <a href="https://github.com/schollz/listfiles">schollz/listfiles</a> where I attempt to code two other methods that I thought might be faster. </p>
<p>The alternative <strong>first method (ListInParallel)</strong> uses <code>ioutil.ReadDir</code>, but spawns a goroutine for each new directory and channels the results back. The <strong>second method (ListFilesUsingC)</strong> uses CGo and an adapted <a href="https://github.com/ChristopherSchultz/fast-file-count">C program for fast file listing</a> which also allows some array preallocation and parallel processing.</p>
<p>I've benchmarked the methods using 10,000 - 1,000,000 files on Windows and Linux with SSD and spinning disk. Benchmarks on Windows+SSD show that the <strong>ListInParallel</strong> method is fastest, faster than the standard <code>filepath.Walk</code> approach by about 10 times! (Note: the listing files in C is very slow in Windows because Windows doesn't support <code>lstat</code>). Benchmarks on Linux+SSD/Spinning disk show that the <strong>ListFilesUsingC</strong> is fastest, 5-50% faster than the <code>filepath.Walk</code> method. </p>
<p><em>This is what I find perplexing:</em> The <strong>ListInParallel</strong> method is the slowest on Linux and fastest on Windows. <strong>Why?</strong> Does Windows handle goroutines easier? Does an NTFS SSD drive better support simultaneous access? Its a bit perplexing to me.</p>
<p>The link to my repo above will have all the tests you need to try it yourself (though you need to supply the OS + Disk drive ;) ).</p>
<hr/>**评论：**<br/><br/>BadlyCamouflagedKiwi: <pre><p>FYI <code>filepath.Walk</code> is known not to be the fastest way; <a href="https://github.com/golang/go/issues/16399">https://github.com/golang/go/issues/16399</a> is the upstream issue although it looks like it's unlikely to be fixed given the current interface. <a href="https://github.com/karrick/godirwalk">https://github.com/karrick/godirwalk</a> implements a faster version with a similar but not identical interface; might be interesting to benchmark against that as well.</p></pre>redbo: <pre><p>Yeah, the speed killer is the stat call per file that has to fetch inode data from disk. Not every filesystem on Linux supports getting the file type from dirents instead of doing a stat, but for the ones that can, that method should be a lot faster.</p></pre>qrv3w: <pre><p>That makes sense, but I actually want to use the stat call. All three methods I use do the stat call and the program that imports this library depends on it.</p></pre>non-metal: <pre><p>There are other performance improvements that godirwalk has built in, so even when a program still does a stat it still gets a boost because of the other optimizations. I definitely recommend setting up a scratch buffer for a reduction in GC. If your program also does not care about the order the directory items are enumerated in, set Unsorted to true for an additional performance boost, affecting large directories more than small ones.</p>
<p>Edit: full disclosure: I wrote godirwalk.</p></pre>qrv3w: <pre><p>I compared it with the others, here's the results. Please note! These results include adding a os.Stat call and also hashing the FileInfo. This is not the fastest that you can possibly list a directory at all. I expect Godirwalk is much faster when you don't have to do the Stat call. However, all these methods return the same thing (a list of files with the os.Info and hash), so they are themselves all comparable.</p>
<p><strong>Linux 8-core SSD:</strong></p>
<table><thead>
<tr>
<th align="left">Num files:</th>
<th align="center">213</th>
<th align="right">1,081,321</th>
</tr>
</thead><tbody>
<tr>
<td align="left">ListFilesFileWalk</td>
<td align="center">59,187 files/s</td>
<td align="right">71,121 files/s</td>
</tr>
<tr>
<td align="left">ListFilesInParallel</td>
<td align="center">24,165 files/s</td>
<td align="right">155,636 files/s</td>
</tr>
<tr>
<td align="left">ListFilesUsingC</td>
<td align="center">72,927 files/s</td>
<td align="right">191,782 files/s</td>
</tr>
<tr>
<td align="left">ListFilesGodirwalk</td>
<td align="center">56,287 files/s</td>
<td align="right">65,284 files/s</td>
</tr>
</tbody></table>
<p><strong>Windows 8-core SSD:</strong></p>
<table><thead>
<tr>
<th align="left">Num files:</th>
<th align="center">233</th>
<th align="right">380,226</th>
</tr>
</thead><tbody>
<tr>
<td align="left">ListFilesFileWalk</td>
<td align="center">9,700 files/s</td>
<td align="right">14,524files/s</td>
</tr>
<tr>
<td align="left">ListFilesInParallel</td>
<td align="center">58,206 files/s</td>
<td align="right">228,174 files/s</td>
</tr>
<tr>
<td align="left">ListFilesUsingC</td>
<td align="center">383 files/s</td>
<td align="right">2,675 files/s</td>
</tr>
<tr>
<td align="left">ListFilesGodirwalk</td>
<td align="center">11,640 files/s</td>
<td align="right">14,283 files/s</td>
</tr>
</tbody></table></pre>hsoolien: <pre><p>I don't know for sure, but I'm curious, could this be related to how some os's prefer all system calls to come from the main application thread?</p>
<p>Although to be honest if that was the case I would expect crashing not incredible slowness.</p></pre>littlelowcougar: <pre><blockquote>
<p>I don't know for sure, but I'm curious, could this be related to how some os's prefer all system calls to come from the main application thread?</p>
</blockquote>
<p>I really don’t think that’s a thing.</p></pre>hsoolien: <pre><p>I admit I'm an amateur and could be wrong (actually if I am wrong that would be fantastic), so that in mind:</p>
<p>My experience to date with various ui and graphics wrappers is any calls to those libraries/wrappers either are made with a program where gomaxprocs is set to 1, or you use some tricks to guarantee that any go threads will make their system calls from the main thread. (One wrapper has a do function you're supposed to use with go routines to bind them to the main thread)</p>
<p>The reasons given are always issues with how some os's don't like system calls made outside the main thread of an application.</p>
<p>Now I'm new, I'll admit maybe I misread, perhaps this is limited to ui/graphics calls</p>
<p>If I am wrong, this would be great for at least one project.</p></pre>littlelowcougar: <pre><p>For graphics stuff, yeah, the main thread thing applies.</p>
<p>For underlying OS stuff that the kernel provides, it definitely doesn't.</p></pre>hsoolien: <pre><p>Well it's not as good of news as I hoped, it's nice to know that a little clearer.</p>
<p>Thank you.</p></pre>mcandre: <pre><p>Are goroutines green threads or native? Spawning an arbitrarily large number of threads can tax OS resources.</p></pre>jackmott2: <pre><p>green</p></pre>lepuma: <pre><p>What does that mean?</p></pre>jackmott2: <pre><p>when a language or library provides a "thread" abstraction where the "thread" is scheduled on a pool of actual OS threads by the library/runtime, it is sometimes called "Green threads".</p>
<p>So the runtime may keep a pool of say, 8 actual OS threads, you can then spawn a million coroutines and Go takes care of scheduling them intelligently on the 8 actual OS threads (or whatever it decides). OS threads have a lot of overhead so you wouldn't ever want to make a million of them. Abstraction like go-routines allow you to not have to worry about thread overhead (as much) but can reduce how much low level control you have. You can force goroutines onto actual threads if you need to though.</p></pre>moomaka: <pre><p>How many times did you run the benchmark before collecting numbers? The range is a bit surprising and I think you may be seeing the difference between the files being in the OS disk cache and not. </p></pre>qrv3w: <pre><p>Oh! That could be it....I have no idea how to turn off caching in Windows to test it though.</p></pre>
