# Async and Parallel Prgramming

## 1- Understanding the Dangers of Concurrency

### Race condition

A race condition exists when the outcome depends on the timing of events

### Shared resources (Most common pitfall)

```csharp
int sum = 0;
Task.Factory.StartNew(() => {
    sum = sum + obj1.Computation();
})
Task.Factory.StartNew(() => {
    sum = sum + obj2.Computation();
})
```

### Sequential to Parallel

```csharp
// Sequential
private int SearchFiles(List<string> filenames, string pattern)
{
    int hits = 0;

    Regex re = new Regex(pattern, RegexOptions.Compiled | RegexOptions.Multipline);

    foreach (string f in filenames)
    {
        byte[] bytes = File.ReadAllBytes(f);

        string contents = System.Text.Encoding.UTF8.GetString(bytes);

        Match m = re.Match(contents);

        while(m.Success)
        {
            hits++;
            m = m.NextMatch();
        }
    }

    return hits;
}

// Parallel
private int SearchFiles(List<string> filenames, string pattern)
{
    int hits = 0;

    Regex re = new Regex(pattern, RegexOptions.Compiled | RegexOptions.Multipline);

    var tasks = new List<Task>();

    foreach (string f in filenames)
    {
        var t = new Task.Factory.StartNew((arg) => {
            var fn = (string)arg;

            byte[] bytes = File.ReadAllBytes(fn);

            string contents = System.Text.Encoding.UTF8.GetString(bytes);

            Match m = re.Match(contents);

            while(m.Success)
            {
                hits++; // Shared Resource
                m = m.NextMatch();
            }
        });

        tasks.Add(t);
    }

    tasks.WaitAll(tasks.ToArray());

    return hits;
}
```

### Solutions

- Redesign - To eliminate shared resources (eg. Each task uses only local storage)
- Thread-safe - TPL offers thread-safe data structures (eg. ConcurrentDictionary)
- Synchronization - To control access critical section (eg. Lock, Interlocked )

### Solution 1 - Locking

```csharp
private int SearchFiles(List<string> filenames, string pattern)
{
    int hits = 0;

    Regex re = new Regex(pattern, RegexOptions.Compiled | RegexOptions.Multipline);

    var tasks = new List<Task>();
    var l = new object();

    foreach (string f in filenames)
    {
        var t = new Task.Factory.StartNew((arg) => {
            var fn = (string)arg;

            byte[] bytes = File.ReadAllBytes(fn);

            string contents = System.Text.Encoding.UTF8.GetString(bytes);

            Match m = re.Match(contents);

            while(m.Success)
            {
                lock (l)
                {
                    hits++;
                }
                m = m.NextMatch();
            }
        });

        tasks.Add(t);
    }

    tasks.WaitAll(tasks.ToArray());

    return hits;
}
```

### Solution 2 - InterLocking

```csharp
private int SearchFiles(List<string> filenames, string pattern)
{
    int hits = 0;

    Regex re = new Regex(pattern, RegexOptions.Compiled | RegexOptions.Multipline);

    var tasks = new List<Task>();

    foreach (string f in filenames)
    {
        var t = new Task.Factory.StartNew((arg) => {
            var fn = (string)arg;

            byte[] bytes = File.ReadAllBytes(fn);

            string contents = System.Text.Encoding.UTF8.GetString(bytes);

            Match m = re.Match(contents);

            while(m.Success)
            {
                System.Threading.Interlocked.Increment(ref hits);
                m = m.NextMatch();
            }
        });

        tasks.Add(t);
    }

    tasks.WaitAll(tasks.ToArray());

    return hits;
}
```

### Solution 3 - Lock-free

```csharp
private int SearchFiles(List<string> filenames, string pattern)
{
    int hits = 0;

    Regex re = new Regex(pattern, RegexOptions.Compiled | RegexOptions.Multipline);

    var tasks = new List<Task<int>>();

    foreach (string f in filenames)
    {
        var t = new Task.Factory.StartNew<int>((arg) => {
            var lhits = 0;
            var fn = (string)arg;

            byte[] bytes = File.ReadAllBytes(fn);

            string contents = System.Text.Encoding.UTF8.GetString(bytes);

            Match m = re.Match(contents);

            while(m.Success)
            {
                lhits++;
                m = m.NextMatch();
            }

            return lhits++;
        });

        tasks.Add(t);
    }

    tasks.WaitAll(tasks.ToArray());

    var hits = 0;
    foreach (var t in tasks)
        hits += t.Result;

    return hits;
}
```

### Wait All One by One Pattern

```csharp
private int SearchFiles(List<string> filenames, string pattern)
{
    int hits = 0;

    Regex re = new Regex(pattern, RegexOptions.Compiled | RegexOptions.Multipline);

    var tasks = new List<Task<int>>();

    foreach (string f in filenames)
    {
        var t = new Task.Factory.StartNew<int>((arg) => {
            var lhits = 0;
            var fn = (string)arg;

            byte[] bytes = File.ReadAllBytes(fn);

            string contents = System.Text.Encoding.UTF8.GetString(bytes);

            Match m = re.Match(contents);

            while(m.Success)
            {
                lhits++;
                m = m.NextMatch();
            }

            return lhits++;
        });

        tasks.Add(t);
    }

    // tasks.WaitAll(tasks.ToArray());
    var results = WaitAllOneByOne(tasks);

    // var hits = 0;
    // foreach (var t in tasks)
    //     hits += t.Result;
    int hits = results.AsParallel().Sum();

    return hits;
}

private List<int> WaitAllOneByOne(List<Task<int> tasks)
{
    var results = new List<int>();

    while(tasks.Count > 0)
    {
        int i = Task.WaitAny(tasks.ToArray());
        results.Add(tasks[i].Result);
        tasks.RemoveAt(i);
    }

    return results;
}
```

### Shared objects and non thread safe classes

```csharp
var results = new List<int>(); // non thread safe
var rand = new Random(); // non thread safe

for (int i = 0; i < n; i++)
{
    Task.Factory.StartNew(() => {
        int r = SimulationMethod(rand);
        results.Add(r);
    });
}
```

### Solution - Use thread safe classes

```csharp
var results = new ConcurrentQueue<int>();

for (int i = 0; i < n; i++)
{
    Task.Factory.StartNew(() => {
        var rng = new RNGCryptoServiceProvider();
        var data = byte[4];
        rng.GetBytes(data);
        int seed = BitConverter.ToInt32(data, 0);
        var rand = new Random(seed);

        int r = SimulationMethod(rand);
        results.Enqueue(r);
    });
}
```

### Solution 5 - Thread safe object

```csharp
var tasks = new List<Task<int>>();

private int SearchFiles(List<string> filenames, string pattern)
{
    int hits = 0;

    Regex re = new Regex(pattern, RegexOptions.Compiled | RegexOptions.Multipline);

    var tasks = new List<Task<int>>();

    foreach (string f in filenames)
    {
        var t = new Task.Factory.StartNew<int>((arg) => {
            var lhits = 0;
            var fn = (string)arg;

            byte[] bytes = File.ReadAllBytes(fn);

            // Non thread safe
            // string contents = System.Text.Encoding.UTF8.GetString(bytes);
            // Thread safe
            var encoding = new System.Text.UTF8Encoding();
            string contents = encoding.GetString(bytes)

            Match m = re.Match(contents);

            while(m.Success)
            {
                lhits++;
                m = m.NextMatch();
            }

            return lhits++;
        });

        tasks.Add(t);
    }

    tasks.WaitAll(tasks.ToArray());

    var hits = 0;
    foreach (var t in tasks)
        hits += t.Result;

    return hits;
}
```
### Solution 6 - Local object

```csharp
var tasks = new List<Task<int>>();

private int SearchFiles(List<string> filenames, string pattern)
{
    int hits = 0;

    // Regex re = new Regex(pattern, RegexOptions.Compiled | RegexOptions.Multipline);

    var tasks = new List<Task<int>>();

    foreach (string f in filenames)
    {
        var t = new Task.Factory.StartNew<int>((arg) => {
            var lhits = 0;
            var fn = (string)arg;

            byte[] bytes = File.ReadAllBytes(fn);

            var encoding = new System.Text.UTF8Encoding();
            string contents = encoding.GetString(bytes)

            // Local object
            Regex re = new Regex(pattern, RegexOptions.Compiled | RegexOptions.Multipline);
            Match m = re.Match(contents);

            while(m.Success)
            {
                lhits++;
                m = m.NextMatch();
            }

            return lhits++;
        });

        tasks.Add(t);
    }

    tasks.WaitAll(tasks.ToArray());

    var hits = 0;
    foreach (var t in tasks)
        hits += t.Result;

    return hits;
}
```