C# Scan tree recursively with multiple threads

Question

I'm scanning some directory for items. I've just read Multithreaded Directory Looping in C# question but I still want to make it multithreated. Even though everyone says the drive will be the bottleneck I have some points:

• The drives may mostly be "single threaded" but how you know what they going to bring up in the future?
• How you know the different sub-paths you are scanning are one the same physical drive?
• I using an abstraction layer (even two) over the System.IO so that I can later reuse the code in different scenarios.

So, my first idea was to use Task and first dummy implementation was this:

public async Task Scan(bool recursive = false) {
    var t = new Task(() => {
        foreach (var p in path.scan) Add(p);
        if (!recursive) return;
        var tks = new Task[subs.Count]; var i = 0;
        foreach (var s in subs) tks[i++] = s.Scan(true);
        Task.WaitAll(tks);
    }); t.Start();
    await t;
}

I don't like the idea of creating a Task for each item and generally this doesn't seem ideal, but this was just for a test as Tasks are advertised to automatically manage the threads...

This method works but it's very slow. It takes above 5s to complete, while the single threated version below takes around 0.5s to complete the whole program on the same data set:

public void Scan2(bool recursive = false) {
    foreach (var p in path.scan) Add(p);
    if (!recursive) return;
    foreach (var s in subs) s.Scan2(true);
}

I wander what really goes wrong with fist method. The machine is not on load, CUP usage is insignificant, drive is fine... I've tried profiling it with NProfiler it don't tell me much besides the program sits on Task.WaitAll(tks) all the time.

I also wrote a thread-locked counting mechanism that is invoked during addition of each item. Maybe it's the problem with it?

#region SubCouting
public Dictionary<Type, int> counters = new Dictionary<Type, int>(); 
private object cLock = new object();
private int _sc = 0;
public int subCount => _sc;
private void inCounter(Type t) {
    lock (cLock) {
        if (!counters.ContainsKey(t)) counters.Add(t, 1);
        counters[t]++;
        _sc++;
    }
    if (parent) parent.inCounter(t);
}
#endregion

But even if threads are waiting here, wouldn't the execution time be similar to single threaded version as opposed to 10x slower?

I'm not sure how to approach this. If I don't want to use tasks, do I need to manage threads manually or is there already some library that would fit nicely for the job?

Answer 1

I think you almost got it. Task.WaitAll(tks) is the problem. You block one thread for this as this is synchronous operation. You get out of threads soon, all threads are just waiting for some tasks that have no threads to run on. You can solve this with async, replace the waiting with await Task.WhenAll(...). It would free the thread when waiting. With some workload the multithreaded version is significantly faster. When just IO bound it is roughly equal.

ConcurrentBag<string> result = new ConcurrentBag<string>();
List<string> result2 = new List<string>();

public async Task Scan(string path)
{
    await Task.Run(async () =>
    {
        var subs = Directory.GetDirectories(path);
        await Task.WhenAll(subs.Select(s => Scan(s)));

        result.Add(Enumerable.Range(0, 1000000).Sum(i => path[i % path.Length]).ToString());
    });
}

public void Scan2(string path)
{
    result2.Add(Enumerable.Range(0, 1000000).Sum(i => path[i % path.Length]).ToString());

    var subs = Directory.GetDirectories(path);
    foreach (var s in subs) Scan2(s);
}

private async void button4_Click(object sender, EventArgs e)
{
    string dir = @"d:\tmp";

    System.Diagnostics.Stopwatch st = new System.Diagnostics.Stopwatch();
    st.Start();
    await Scan(dir);
    st.Stop();
    MessageBox.Show(st.ElapsedMilliseconds.ToString());

    st = new System.Diagnostics.Stopwatch();
    st.Start();
    Scan2(dir);            
    st.Stop();
    MessageBox.Show(st.ElapsedMilliseconds.ToString());

    MessageBox.Show(result.OrderBy(x => x).SequenceEqual(result2.OrderBy(x => x)) ? "OK" : "ERROR");
}