Introduction
This is the third and final part of a three part series on algorithmic runtime comparison. For the full introduction to the series check out the first post. Additionally, if you haven't done the demo from the second part of the series please do so now.
Today we will add three more merge algorithms as ServiceBus Topic Triggers to our Functions App. Once we have all of our ServiceBus Triggers in place we can do some comparison of the complexity/performance. Depending on how the tests are written there may some surprising results.
Errata
- Donna Malayeri posted an update to the Azure Functions deployment story for Visual Studio 2017 that is quite intriguing. I was actually asking about this a couple weeks ago on Twitter as I couldn't figure out how to set up the build and deployment steps for an Azure Functions app. The big news here is it completes a gap that had existed where developers couldn't do Project --> New and then go about deploying their Functions App using Visual Studio Team Services. It looks like it should be ready to go sometime in the second week of June and I look forward to creating a new Functions App and playing around with it. Congrats to Donna and team!
- MS Cloud Show has a recap episode of the MS Build conference. I was out on paternity leave when the conference happened so I wasn't able to catch any of it. Oops. Because of the recap I am able to check out the new announcements and note any of the announcements I want to take a closer look at. Thanks for the great content AC and CJ!
Prerequisites
- The source for today's demo is located on and deployed from GitHub. If you want to save some copy/pasting grab it here: AzureFunctionsBlogDemos. Feel free to clone the repository and use it for a reference as we go through the demo.
- Today's demo assumes that you have completed the demo for part one of the series. If you haven't already, please complete the first demo now. As well as part two. Just like with part one, if you haven't completed the demo already please do so now.
Add the QuickFind ServiceBusTopic Trigger
QuickFindSBTopicTrigger.cs
using Microsoft.Azure.WebJobs;
using Microsoft.Azure.WebJobs.Host;
using System;
using System.Diagnostics;
using System.IO;
using System.Security.Cryptography;
namespace AzureFunctionsBlogDemos.Merging
{
public class QuickFindSBTopicTrigger
{
public static void Run(MergingArray myQueueItem, TraceWriter log, IAsyncCollector outputTable,
IBinder binder)
{
log.Info("QuickFindSBTopicTrigger processed a request.");
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
MergingArray.Merge(myQueueItem, Shared.Enums.MergeAlgorithms.QuickFind);
stopwatch.Stop();
var performance = new MergePerformance();
performance.Runtime = stopwatch.Elapsed;
performance.AlgorithmName = "QuickFind";
performance.PartitionKey = "QuickFind";
performance.RowKey = Guid.NewGuid().ToString();
performance.NumberOfElements = myQueueItem.Output.Length;
outputTable.AddAsync(performance);
var blobPath = "merging" + "/" + "quickfind" + DateTime.UtcNow.ToString("yyyyMMddHHmmss") + ".txt";
using (var outputBlob = binder.Bind(
new BlobAttribute(blobPath)))
{
outputBlob.WriteLine($"Number to Union From: {string.Join(",", myQueueItem.NumberToUnionFrom)}");
outputBlob.WriteLine($"Number to Union To: {string.Join(",", myQueueItem.NumberToUnionTo)}");
outputBlob.WriteLine($"Output of Merge: {string.Join(",", myQueueItem.Output)}");
outputBlob.WriteLine();
outputBlob.WriteLine($"Runtime: {performance.Runtime.ToString()}");
// create Sha1 Hash
var sha = new SHA512CryptoServiceProvider();
// This is one implementation of the abstract class SHA512.
var result = sha.ComputeHash(System.Text.Encoding.UTF8.GetBytes(blobPath + myQueueItem.NumberToUnionFrom + myQueueItem.NumberToUnionTo + myQueueItem.Output));
outputBlob.WriteLine($"Hash of Inputs, Output and Runtime: {BitConverter.ToString(result).Replace("-", "")}");
}
}
}
}
function.json
{
"bindings": [
{
"name": "myQueueItem",
"topicName": "algorithmsmerge",
"subscriptionName": "QuickFind",
"connection": "AzureWebJobsServiceBus",
"accessRights": "manage",
"type": "serviceBusTrigger",
"direction": "in"
},
{
"connection": "AzureWebJobsStorage",
"direction": "out",
"name": "outputTable",
"tableName": "Merging",
"type": "table"
},
{
"connection": "AzureWebJobsStorage",
"direction": "out",
"name": "outputBlob",
"path": "Merging/{QuickFindSBTopicTrigger}.txt",
"type": "blob"
}
],
"disabled": false,
"entryPoint": "AzureFunctionsBlogDemos.Merging.QuickFindSBTopicTrigger.Run",
"scriptFile": "..\\bin\\AzureFunctionsBlogDemos.dll"
}
Add the QuickUnion ServiceBusTopic Trigger
QuickUnionTopicTrigger.cs
using Microsoft.Azure.WebJobs;
using Microsoft.Azure.WebJobs.Host;
using System;
using System.Diagnostics;
using System.IO;
using System.Security.Cryptography;
namespace AzureFunctionsBlogDemos.Merging
{
public class QuickUnionTopicTrigger
{
public static void Run(MergingArray myQueueItem, TraceWriter log, IAsyncCollector outputTable,
IBinder binder)
{
log.Info("QuickUnionTopicTrigger processed a request.");
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
MergingArray.Merge(myQueueItem, Shared.Enums.MergeAlgorithms.QuickUnion);
stopwatch.Stop();
var performance = new MergePerformance();
performance.Runtime = stopwatch.Elapsed;
performance.AlgorithmName = "QuickUnion";
performance.PartitionKey = "QuickUnion";
performance.RowKey = Guid.NewGuid().ToString();
performance.NumberOfElements = myQueueItem.Output.Length;
outputTable.AddAsync(performance);
var blobPath = "merging" + "/" + "quickunion" + DateTime.UtcNow.ToString("yyyyMMddHHmmss") + ".txt";
using (var outputBlob = binder.Bind(
new BlobAttribute(blobPath)))
{
outputBlob.WriteLine($"Number to Union From: {string.Join(",", myQueueItem.NumberToUnionFrom)}");
outputBlob.WriteLine($"Number to Union To: {string.Join(",", myQueueItem.NumberToUnionTo)}");
outputBlob.WriteLine($"Output of Merge: {string.Join(",", myQueueItem.Output)}");
outputBlob.WriteLine();
outputBlob.WriteLine($"Runtime: {performance.Runtime.ToString()}");
// create Sha1 Hash
var sha = new SHA512CryptoServiceProvider();
// This is one implementation of the abstract class SHA512.
var result = sha.ComputeHash(System.Text.Encoding.UTF8.GetBytes(blobPath + myQueueItem.NumberToUnionFrom + myQueueItem.NumberToUnionTo + myQueueItem.Output));
outputBlob.WriteLine($"Hash of Inputs, Output and Runtime: {BitConverter.ToString(result).Replace("-", "")}");
}
}
}
}
function.json
{
"bindings": [
{
"name": "myQueueItem",
"topicName": "algorithmsmerge",
"subscriptionName": "QuickUnion",
"connection": "AzureWebJobsServiceBus",
"accessRights": "manage",
"type": "serviceBusTrigger",
"direction": "in"
},
{
"connection": "AzureWebJobsStorage",
"direction": "out",
"name": "outputTable",
"tableName": "Merging",
"type": "table"
},
{
"connection": "AzureWebJobsStorage",
"direction": "out",
"name": "outputBlob",
"path": "Merging/{WQUWPCTopicTrigger}.txt",
"type": "blob"
}
],
"disabled": false,
"entryPoint": "AzureFunctionsBlogDemos.Merging.QuickUnionTopicTrigger.Run",
"scriptFile": "..\\bin\\AzureFunctionsBlogDemos.dll"
}
Add the WeightedQuickUnion ServiceBusTopic Trigger
WeightedQuickUnionTopicTrigger.cs
using Microsoft.Azure.WebJobs;
using Microsoft.Azure.WebJobs.Host;
using System;
using System.Diagnostics;
using System.IO;
using System.Security.Cryptography;
namespace AzureFunctionsBlogDemos.Merging
{
public class WeightedQuickUnionTopicTrigger
{
public static void Run(MergingArray myQueueItem, TraceWriter log, IAsyncCollector outputTable,
IBinder binder)
{
log.Info("WeightedQuickUnionTopicTrigger processed a request.");
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
MergingArray.Merge(myQueueItem, Shared.Enums.MergeAlgorithms.WeightedQuickUnionWithPathCompression);
stopwatch.Stop();
var performance = new MergePerformance();
performance.Runtime = stopwatch.Elapsed;
performance.AlgorithmName = "WeightedQuickUnion";
performance.PartitionKey = "WeightedQuickUnion";
performance.RowKey = Guid.NewGuid().ToString();
performance.NumberOfElements = myQueueItem.Output.Length;
outputTable.AddAsync(performance);
var blobPath = "merging" + "/" + "weightedquickuniontopictrigger" + DateTime.UtcNow.ToString("yyyyMMddHHmmss") + ".txt";
using (var outputBlob = binder.Bind(
new BlobAttribute(blobPath)))
{
outputBlob.WriteLine($"Number to Union From: {string.Join(",", myQueueItem.NumberToUnionFrom)}");
outputBlob.WriteLine($"Number to Union To: {string.Join(",", myQueueItem.NumberToUnionTo)}");
outputBlob.WriteLine($"Output of Merge: {string.Join(",", myQueueItem.Output)}");
outputBlob.WriteLine();
outputBlob.WriteLine($"Runtime: {performance.Runtime.ToString()}");
// create Sha512 Hash
var sha = new SHA512CryptoServiceProvider();
// This is one implementation of the abstract class SHA512.
var result = sha.ComputeHash(System.Text.Encoding.UTF8.GetBytes(blobPath + myQueueItem.NumberToUnionFrom + myQueueItem.NumberToUnionTo + myQueueItem.Output));
outputBlob.WriteLine($"Hash of Inputs, Output and Runtime: {BitConverter.ToString(result).Replace("-", "")}");
}
}
}
}
function.json
{
"bindings": [
{
"name": "myQueueItem",
"topicName": "algorithmsmerge",
"subscriptionName": "WeightedQuickUnion",
"connection": "AzureWebJobsServiceBus",
"accessRights": "manage",
"type": "serviceBusTrigger",
"direction": "in"
},
{
"connection": "AzureWebJobsStorage",
"direction": "out",
"name": "outputTable",
"tableName": "Merging",
"type": "table"
},
{
"connection": "AzureWebJobsStorage",
"direction": "out",
"name": "outputBlob",
"path": "merging/{WeightedQuickUnionTopicTrigger}.txt",
"type": "blob"
}
],
"disabled": false,
"entryPoint": "AzureFunctionsBlogDemos.Merging.WeightedQuickUnionTopicTrigger.Run",
"scriptFile": "..\\bin\\AzureFunctionsBlogDemos.dll"
}
Run and Test New Service Bus Triggers
Now we should be able to hit F5 and run our new ServiceBus Topic Triggers by sending in a message to MergeTrigger. Just like in part two the Triggers will read our messages from the ServiceBus Topics, run the merge algorithms and write the output to Blob and Table storage.
In Visual Studio, set desired breakpoints so you can walk through the Functions as desired.
In order to send in requests to MergeTrigger let's use the Console App I created. Grab it from the GitHub repo - AzureFunctionsBlogDemos.
Just like in part two all you need to do in order to test your functions is set the Debug value, add your ApiKey and update the BaseUrl values.
Analysis... And A Bug
There is actually a very intriguing bug in the current iteration of the Console App that makes it so that QuickUnion outperforms WeightedQuickUnion and WeightedQuickUnionWithPathCompression.
Essentially, it has to do with how the Random class works in C#. Because the Random class uses the CPU clock we get the same numbers in both arrays. See this StackOverflow.com article for information. So, since the numbers to union from and union to are the same QuickUnion operates at it's optimal performance which ends up being O(n) (credit to this StackOverflow post).
We can run with the bug and we will see that QuickUnion is running at optimal efficiency (in linear time) while WeightedQuickUnion and WeightedQuickUnionWithPathCompression are running at their least efficient (linear time) as the amount of trees to merge are high and the structure of the output would be very flat due to merging EACH number to itself.
The one thing that we can prove, regardless of the existence of the bug, is that QuickFind is always going to be the slowest merge algorithm due to it having a complexity of O(n)2. Sadly, this merge algorithm will never be Usain Bolt and is doomed to be as slow as an ogre stuck in low viscosity liquid.
Analysis Post Bug Fix
Now that we've identified the culprit for our merges being slow, let's make a fix and do some more analysis.
The simple fix for our Console App is to initialize the Random object as a static member of the class.
using System;
using System.Configuration;
using System.Net.Http;
using System.Net.Http.Headers;
using System.Threading.Tasks;
// Client code adapted from the following example: https://docs.microsoft.com/en-us/aspnet/web-api/overview/advanced/calling-a-web-api-from-a-net-client
namespace HttpClientSample
{
class Program
{
static Random r = new Random();
static HttpClient client = new HttpClient();
Now we will see that the NumberToUnionFrom and NumberToUnionTo arrays are indeed different.
So, now what will happen?
By fixing the bug we will have two random arrays for NumberToUnionFrom and NumberToUnionTo. Cool, but what does this do to complexity?
Now we can see that QuickUnion is running at less than optimal efficiency (which is somewhere between linear and quadratic time).
The clear winner with this change are WeightedQuickUnion and WeightedQuickUnionWithPathCompression are running at somewhere between their most efficient (logrithmic time) and linear time as the amount of trees to merge will decrease with each merge (since the likelihood of repeat numbers in the arrays will increase) and the structure of the output should now be deeper due to the merging of different trees to each other.
Commit to Git
Now, we're ready to make a commit from Powershell which will trigger another deployment.
git add -A
git commit -m "Added remaining merge algorithms as ServiceBus Triggers."
git push origin master
It should take a minute or so and then your function will be visible. Grab the URL just like we did yesterday. Can now use the console app to send in 100 requests to MergeTrigger which will create 100 messages for the all of our Triggers.
Note: switch the value for Debug in secretappsettings.config back to true. Otherwise we will be sending to the wrong endpoint.
Analyzing the Algorithmic Complexity and Performance
Today's demonstration shows four different merge algorithms and how to make them perform at their worst and their best.
QuickFind is always going to be one of the slowest merge algorithms. Regardless of input the runtime will almost always be quadratic.
QuickUnion is better than QuickFind and with the right input can even show linear run time. However, once we fixed the bug in our Console App QuickUnion proved to be less than optimal and started showing performance more in line with QuickFind. The worst case run time for QuickUnion will be quadratic.
WeightedQuickUnion and WeightedQuickUnionWithPathCompression proved to be the true champions of this experiment as their runtime will AT WORST be linear when we merged every number in the arrays to itself. The optimization introduced simply had nothing to do. Once we fixed the bug we were able to see run times that were logarithmic and at their worst still half the run time of the best run of QuickUnion. Even comparing different runs it was plain to see that the optimizations were indeed paying off.
Conclusion
Today we wrap up our series on Merge Algorithms using Azure Functions but we are still not done. There was a lot of code duplication between the four ServiceBus Topic Triggers. Simply, we violated the Don't Repeat Yourself principle. One way to fix this would be to use the Inversion of Control pattern. We will explore how we can refactor our ServiceBus Triggers in a future post.