Leverage parallel capabilities

[sylvestre]

Rust is amazing at parallelism, we could probably leverage that to run the analysis in parallel:

findutils/src/find/mod.rs

Line 156 in ac576f5

for path in paths_and_matcher.paths {

[asder8215]

From the discussion in #142 and from what I am seeing in how do_find() works, my understanding of how this was being parallelized in the PR @thecotne made was that we give each thread a directory to traverse through.

The benefit I see out of this approach is if all the directories have an even distribution of files to look through and that there are no redundant directories or files that could be checked (i.e. find dir1 dir1/dir2; if dir2 was checked in dir1's traversal, then the dir2's check is redundant), then this would be efficient in comparison to traversing the given input directories one at a time. But the moment we have redundant directories or that there is a large skew of files in one directory and not that many files in the other directories, parallelizing this would not give much of a performance benefit and could possibly cause some hindrances.

What I want to suggest is the following:

• Instead of each thread owning a path to traverse through, we use up to max core threads per path. Here's what I'm thinking:
  • Each thread has a specific bounded queue that takes in directory paths. It pops off from this queue to traverse that directory, seeing the files and directories contained inside.
  • Initially, we could push the current path that we are examining into the first thread/queue.
  • To load balance the directory traversal among threads, for a certain batch number of directories that a thread visits/collects (including following symlinks to a directory with -L flag), it enqueues those directories onto another thread's queue.
  • The data structure needed for this would be a shared multiqueue data structure, where you use it so that threads only dequeue from their own specific queue, but are otherwise free to enqueue to another queue.
• To take care of avoiding redundant directories, we could use a HashSet guarded by a RwLock that contains directory paths. When a thread pops off a directory it visits in its queue, it confirms with the HashSet first to see if this directory was visited already. If so, then we don't need to traverse this directory again. Otherwise, we would perform the traversal.
  • The one thing that I am concerned about this is how expensive this check and insertion of paths to the HashSet would be.
• Because doing this synchronously could potentially cause some blocking issues or delays (i.e. if a thread is trying to insert a directory path in another thread's bounded queue, but that thread's queue is full), maybe we could do this in asynchronous manner and give threads dequeue/enqueue tasks on the directories it can traverse + give directories to other thread's queues in a nonblocking manner.

I actually created an asynchronous multiqueue data structure that's perfectly suited and tuned for this sort of work.

What do you think about this approach?

Edit: Had a pseudo code approach on how this might work. The pseudo code is as follows:

find dir1 dir2 dir3 // we can treat each of these directories as root nodes

initializing a shardedringbuf with max core threads queues with some initial size per queue
initialize a shared channel that is either unbounded MPSC lock-free or unbounded MPMC lock-free
initialize a HashSet with a RwLock lock guard
initialize a Vec containing the results of paths that find was looking for

for path in paths {

    First push in path into that shared channel
    loop {
        // in case the enqueue tasks terminated itself
        // early and there are still directories in the channel
        if shared channel is empty {
            break;
        }

        spawn min(max core, shared channel size) dequeue task per shard where each dequeue task wants to
        complete traversing through a directory (checking HashSet first for visited) and pushes collected directories into the shared 
        channel

        spawn an enqueue (or multiple enqueue) task that it's sole responsibility is to pop off from shared channel
        and distribute the directories evenly among threads, finishing the task when it pops off None or channel is empty

        await enqueue task(s) to finish

        set poison flag of the ring buffer to signal to gracefully terminate dequeue tasks

        await dequeue tasks, pushing the results into the Vec
   }
   clear poison flag to use the buffer again in next iteration
}

handle any actions find must do on the results (this could probably be parallelized as well).

[asder8215]

I realized that parallelism in the manner I described above would not preserve the same output behavior as to what GNU find and the current implementation of find does, especially because the approach used right now is a DFS approach and the one I suggested is BFS + parallelization. This would definitely fail a few of the test cases that's currently inside this repository.

@sylvestre regarding this issue, when you wanted parallel capabilities to be leveraged, the way I am looking at it is that each thread is responsible to traverse an independent path (i.e. for "find dir1 dir2 ....", we have thread 1 traverse through 'dir1' and thread 2 traverse through 'dir2'). The slight delay seen in @thecotne's PR is coming from:

1. No real parallelization seems to be occurring from my understanding. The hyperfine benchmarking shown in Leverage parallel capabilities #142 does not take in multiple paths; it's only one path ("~"), and hence as @tavianator mentioned, there's the bottleneck of a single thread performing DFS via WalkDir to fully traverse the "~" path.
2. Because no real parallelization occurs, using rayon in this case with .par_iter() introduces slight overhead due to unnecessarily spawning a thread pool equal to the machine's core count by default (we could minimize this overhead through manually creating a ThreadPoolBuilder using min(# of paths, max core count)).

I would expect using rayon to be pretty beneficial and efficient if the user provides multiple paths and we spawn a thread pool based on min(# of paths, max core count). I can re-implement what @thecotne had and use a manual ThreadPoolBuilder if that is good with you?

Creating test cases for this might be tricky however. While struct StandardDependencies has thread safe fields in outputting to stdout() and using SystemTime::now(), struct FakeDependencies has an output field that is not thread safe (the Vec<u8> needs a lock), so I'm concerned about how data is being written there in a multithreaded scenario. In this case, would it be appropriate to use a different struct (like struct ConcurrentFakeDependencies) specifically purposed for test cases using multiple threads? If locked properly, then one approach I am thinking about is if the ordering of the output is sequentially correct in respect to what the individual path should output. For example, if find dir1 dir2 [expression] makes dir1 produce result:

dir1/test1
dir1/test2

and dir2 produces the result:

dir2/test3
dir2/test4

Then what matters here is that "dir1/test1" comes before "dir1/test2" and "dir2/test3" comes before "dir2/test4".

How does this sound for this issue?