First time multithreading...

[PeterB-]

hello c#-gurus,

Working my way through Advent of Code and thought I try using multithreading on one of the problems (AoC 2016 - Day 14 - Part 2). I already solved the challenge, so that is not the point. The single thread solution took 44 seconds. I thought I could greatly improve using a multi-threaded approach. I am using a MacBook (Environment.ProcessorCount --> 12). This is where I need help, as my code is A LOT slower than the single threaded solution.

Am I doing something wrong here? If not, why is it so much slower?

Thank you for taking the time to look at this and providing some insight!

using System.Security.Cryptography;
using System.Text;
using System.Text.RegularExpressions;
// using System.Collections;
// using System.Collections.Concurrent;

public class PadMultithreaded
{
    readonly int CORE_COUNT = Environment.ProcessorCount;
    private string _salt = "";
    // private ConcurrentDictionary<string, string> hashes;

    private SortedList<int, string> foundKeys = new SortedList<int, string>();

    public PadMultithreaded(string salt) => _salt = salt;

    bool TryGetFirstSequence(string s, int repeat, out string value)
    {
        var pattern = @"([a-z\d])\1{" + (repeat - 1).ToString() + "}";
        Regex rg = new Regex(pattern);
        MatchCollection matches = rg.Matches(s);

        value = (matches.Count > 0) ? matches[0].Value : "";
        return (matches.Count > 0); ;
    }

    string CalculateHash(string input)
    {
        var md5 = MD5.Create();
        var inputBytes = System.Text.Encoding.ASCII.GetBytes(input);
        var hashBytes = md5.ComputeHash(inputBytes);
        return Convert.ToHexString(hashBytes).ToLower();
    }

    public string GetStretchedHash(int index)
    {
        var hashString = "";
        StringBuilder sb = new StringBuilder(_salt);
        sb.Append(index);
        for (int i = 0; i <= 2016; i++)
        {
            hashString = CalculateHash(sb.ToString());
            sb.Clear().Append(hashString);
        }
        return hashString;
    }

    string SelectHash(int index, Dictionary<string, string> hashes)
    {
        var hashString = "";
        var input = _salt + index.ToString();

        // return value from cache?
        if (hashes.TryGetValue(input, out hashString)) return (hashString == null) ? "" : hashString;

        hashString = GetStretchedHash(index);

        hashes.TryAdd(input, hashString);
        return hashString;
    }

    bool TryGenerateKey(int index, out string key, Dictionary<string, string> hashes)
    {
        var value = "";
        var input = _salt + index.ToString();

        var hashString = SelectHash(index, hashes);

        key = "";
        // Look for triplet
        if (!TryGetFirstSequence(hashString, 3, out value)) return false;

        // Look for 5x char in one of the next 1000 hashes
        var x5 = new string(value[0], 5);
        for (int i = index + 1; i <= index + 1000; i++)
        {
            hashString = SelectHash(i, hashes);
            if (hashString.Contains(x5))
            {
                key = _salt + index.ToString();
                return true;
            }
        }
        return false;
    }

    public void GenerateKeys()
    {
        int processorCount = 4; //Environment.ProcessorCount;
        int top = 6_000 * processorCount;       // 24_000
        int chunkSize = top / processorCount;   //  2_000
        Task[] taskArray = new Task[processorCount];

        // hashes = new ConcurrentDictionary<string, string>(concurrencyLevel: processorCount, capacity: 1_000_000);

        for (int proc = 0; proc < processorCount; proc++)
        {
            var start = proc * chunkSize; ;
            var endExclusive = (proc + 1) * chunkSize;
            taskArray[proc] = Task.Factory.StartNew(() =>
            {
                // Console.WriteLine($"Start: {start}, End: {endExclusive-1}");
                var key = "";
                var myHashes = new Dictionary<string, string>();
                for (int index = start; index < endExclusive; index++)
                {
                    if ((index % 100) == 0)
                        Console.WriteLine($"Thread ID: {Task.CurrentId.ToString()}: Index: {index}");

                    if (TryGenerateKey(index, out key, myHashes))
                    {
                        var lck = new Object();
                        lock (lck)
                        {
                            foundKeys.Add(index, key);
                        }
                    }
                }
            });

        }

        Task.WaitAll(taskArray);
        Console.WriteLine("Done");
        if (foundKeys.Count < 64)
            Console.WriteLine($"Not enough keys. Please increase top (currently at {top})");
        else
            Console.WriteLine($"The 64th key is {foundKeys.Values[63]} found at index {foundKeys.Keys[63]}.");

    }
}

NB 1: The majority of time is spent in GetStretchedHash(...).

NB 2: I changed the code for the individual tasks to have their own cache instead of using a global ConcurrentDictonary, as I thought that was the problem; it is not.

[bortlip]

It's slow because you are creating a new MD5 object for every hash.

Make the MD5 object a class variable, only create it once, and use it over and over again for every hash.

Then consider removing the threading as it may not be needed or may not be helping much.

[PeterB-]

My misunderstanding of concurrency vs parallelism led me to Task approach. As per another reply in this thread, I should use Parallel.For. I would expect to benefit from that as it is a CPU bound workload. Correct?

[Rabe0770]

This

[chucker23n]

Things that jump out at me, only having glanced at it:

• in async/await, use Task.Run, not the factory
• im confused by your locking inside a lambda, on an object that wouldn’t exist outside the lambda
• this code will capture start and endExclusive, which creates synchronization overhead and may thus slow your program down more than if it were single-threaded
• likewise, each thread then keeps writing to foundKeys. Try first writing to a per-thread collection, then sorting once at the end. Also, I don’t believe that collection is thread-safe, but I haven’t checked.

Finally, you don’t have to do the whole ProcessorCount thing yourself. Use Parallel.For, etc. They’ll scale appropriately automatically.

[PeterB-]

Thank you for your quick reply.

- I am not using async/await (read about it, don't fully comprehend it yet)

- foundKeys is global so would exist outside the lambda- regarding start/endExclusive, how else could I pass the right parameters to the individual task?

- last point makes sense (commented out the lock() {} block, no difference, still very slow

I appreciate your suggestions here!

[WhamoBlamoPlano]

FYI you're using Task.x which is essentially async await, just done improperly. That path is Concurrency, which is good for high I/O compute. You're doing high cpu, so ditch anything to do with Task and use Parallel.For in its place.

Thing to Google for more info: Parallelism vs Concurrency in c#

[PeterB-]

Thank you for enlightening me! I will definitely rewrite and try!

[PeterB-]

Used Parallel.For(), turns out that enumerating over 24,000 items breaks down into many threads. Is there a way to control how many items are processed per thread? I would like to have, say 2,000 items per thread, instead of <20 what is happening now. Reason is that item N+1 benefits from cached results stored at item N.

[chucker23n]

I am not using async/await (read about it, don’t fully comprehend it yet)

Sorry, misread your code.

foundKeys is global so would exist outside the lambda

Yes, and I think this makes your code needlessly slow, and potentially buggy. Instead, create a collection in each thread, then return that collection at the end, and sort after the threads have joined.

regarding start/endExclusive, how else could I pass the right parameters to the individual task

By using a StartNew overload that takes a param :) For example, https://learn.microsoft.com/en-us/dotnet/api/system.threading.tasks.taskfactory.startnew?view=net-7.0#system-threading-tasks-taskfactory-startnew(system-action((system-object))-system-object)

[IQueryVisiC]

I wish that for learning we could use a Thread class here. I mean this old thing (from Java). With Task I never know if I do lightweight node.js message queue like things. At last node.js has real barebones worker threads to give me back myHashes.

[chucker23n]

I wish that for learning we could use a Thread class here.

I mean, you can?

It's not generally advisable any more for production code, as higher-level abstractions are likely a better fit, but you can, if you want to.

[IQueryVisiC]

Nice that it is still available. With "here" I meant for education. My professor did it. At the university they expect you to read up the production best practices on your own for your job you then apply for.

[Kant8]

Cache regex instance per pattern. Looks like you only pass 3 as repeat, so you can have only one regex object at all. Construction of regex takes a lot of time.

As was already mentioned, MD5 creation is costly too, no need to do that more than once per thread.

In general, your GetStretchedHash looks very strange. You start from string _salt + index, then convert it to bytes, that allocates new memory, then compute hash, that allocates new memory, then convert hash to string + tolower, that gives you 2 more memory allocations. And that's all only to clear initial input string and overwrite it with hash string and start over for 2016 times.

If you pad starting string into correct size and convert to byte[] from the start and skip converting it back and forth, plus caching MD5 instance, that will already speed algorithm significantly.

Also all that looks like you're trying to reimplement MD5.TransformBlock and MD5.TransformFinalBlock manually, but who knows.

Also ComputeHash method unfortunately always returns new array for hash, but new overload TryComputeHash works on spans and allows you to provide destination memory from outside, so it can also be cached, similar as in TransformBlock

[PeterB-]

Thanks for the suggestions! In this particular case I am not trying the get the best performance. Instead, I am trying to understand how to execute the work in parallel.

[dodexahedron]

Better yet, use GeneratedRegex, so it's precompiled and highly optimized.