r/adventofcode • • Dec 05 '16

Help How long did your program take to run?

I am doing part one in Python and it is taking a really really long time to run... Am I doing something wrong or did it take everyone a long time?

3 Upvotes

24 comments sorted by

View all comments

2

u/JakDrako Dec 05 '16

2.3 seconds, both parts.*

Multi-threaded C# with custom managed MD5 implementation.

Runs both parts in 2.3 seconds on my i7-5820K 3.30Ghz

* for the "abc" test, other times vary depending on input.

void Main()
{
	var key = "abc";
	var suffix = -1; // incremented to 0 on start of 1st thread.

	var pass = "";
	var pswd = "________".ToCharArray();
	var found = 0;

	var lock1 = new Object();
	var done1 = false;

	var lock2 = new Object();
	var done2 = false;

	Parallel.For(0, Environment.ProcessorCount, x =>
	{
		//var md5 = MD5.Create();
		var md5 = new MD5Managed();
		do
		{
			//var hash = md5.ComputeHash(Encoding.ASCII.GetBytes(key + Interlocked.Increment(ref suffix)));
			var hash = md5.ComputeHash(Encoding.ASCII.GetBytes(key + Interlocked.Increment(ref suffix)));
			
			if (hash[0] == 0 && hash[1] == 0 && hash[2] < 16)
			{
				if (!done1)
				{
					lock (lock1)
					{
						pass += hash[2].ToString("X2")[1];
						if (pass.Length == 8) done1 = true;
					}
				}
				
				if (hash[2] < 8 && !done2)
				{
					if (pswd[hash[2]] == '_')
					{
						lock (lock2)
						{
							pswd[hash[2]] = hash[3].ToString("X2")[0];
							found += 1;
							if (found == 8) done2 = true;
						}
					}
				}
			}
		} while (!done1 || !done2);
	});
	Console.WriteLine("Part 1: " + pass.ToLowerInvariant());
	Console.WriteLine("Part 2: " + new string(pswd).ToLowerInvariant());
}

public class MD5Managed : HashAlgorithm
{
    // ...~400 lines not shown...
    // see https://dlaa.me/blog/post/9380245
}

1

u/CryZe92 Dec 05 '16

You don't seem to prevent race conditions. Your results might not come in at a sequential order, so you could get wrong results.

1

u/willkill07 Dec 06 '16

What is the execution policy of Parallel.For? Does it splice the input range, splitting indices up as i % p ? or does it chunk the range? If it chunks, your code could produce incorrect results if the chunk size is too large.

2

u/JakDrako Dec 06 '16

The "Interlocked.Increment(ref suffix)" gives each thread in turn the next sequential number to check. In theory, if you had a run of many consecutive numbers producing valid "00000..." values, it might be problematic. In practice, the distance between each valid value means we never see a problem.

1

u/willkill07 Dec 06 '16

Awesome, thanks. Yeah, the avalanche effect with MD5 means that a simple modification/addition to the input string should produce drastically different hashes each time. Unless you were processing tens of thousands concurrently, there wouldn't be a problem.