Recursion – Good, Bad, or Indifferent?

For developers using imperative languages (C, C++, C#, Java, Python, etc…), recursion can seem arcane. It’s just not something encountered regularly. However, recursion is a staple of functional programming. Given the functional programming renaissance, it may be time to “bone up”. Even if you have no interest in learning a functional language, functional concepts have many benefits that can be applied to imperative programming (i.e. LINQ, yeah, who doesn’t LOVE that). This blog post is meant to give a very broad overview of recursion for developers who don’t use it much.

WTF is Recursion?

In order to understand recursion one must first understand recursion. Yeah, I know, that’s a really old joke. Moving on…

There are heaps of rather byzantine definitions floating around. However, for our purposes we are going to say that a recursive method is one that calls back to itself. This is best demonstrated via example. Consider the following function that calculates the greatest common divisor of 2 numbers.

private int GreatestCommonDivisor(int x, int y) { return y == 0 ? x : GreatestCommonDivisor(y, x % y); }

Make sure you fully grok that function before reading on. There is a lot happening in those few lines of code.

Most recursive functions can also be written iteratively. In other words, recursive functions can be rewritten using looping constructs (while, for, etc…). See the example below.

private int GreatestCommonDivisor(int x, int y) { while (true) { if (y == 0) break; var remainder = x % y; x = y; y = remainder; } return x; }

The two functions above are commensurate. So, why would one choose one over the other? Read on! More about this in the next section.

The Bad

In imperative programming languages, recursive functions should be avoided in most cases (please, no hate mail about how this isn’t true 100% of the time). Recursive functions are less efficient than their iterative counterparts. Additionally, they are subject to the perils of stack overflows. Why is this true? I’m glad you asked. Let’s consider a greatly simplified version of what happens when a function is invoked.

  1. function arguments, variables, and return address are pushed on the stack
  2. control jumps to the function
  3. function code runs
  4. function results are copied into the return value
  5. stack is rewound to it’s previous position (memory is reclaimed)
  6. control jumps back to the caller

Often times, all of the above consumes more resources than looping. Therefore, recursive method calls are less performant.

The bigger problem is that the call stack is allocated a relatively meager amount of memory (varies wildly depending on the platform). Exceeding this causes the dreaded stack overflow exception to rear it’s ugly head. Each function call eats up space on the stack like a donkey eating a waffle. That space isn’t reclaimed until the function returns. As a total SWAG, I wouldn’t trust a recursion depth of more than about a thousand. Of course, this number varies wildly depending on the platform and amount of stack space the function consumes.

Methods that employ iteration do not suffer from any of the problems outlined in this section. In spite of that, there are still some good reasons to use recursion. Read on my friend!

The Good

As demonstrated above, recursive functions are generally shorter and more elegant. In the words of the great Donald Knuth, “premature optimization is the root of all evil”. Unless your application is extremely performance critical, chances are you will never notice the few extra microseconds. The added benefit of terse and expressive code far outweighs the performance hit. Obviously, stack overflow exceptions aren’t going away. However, if the estimated recursion depth is modest there is no reason to avoid recursion. Put succinctly, if your use case is not performance critical and the estimated recursion depth is reasonable, it’s a good candidate for recursion.

Now wait a minute, I said that stack overflows aren’t going away but I also said that recursion is a staple for functional programming. How can both of these statements be true? Three words: tail call optimization. Many functional languages employ this witchery. In a nutshell, here’s what happens. If a function’s return expression is a result of a function call, the stack frame is reused instead of pushing a new one on the call stack. That’s all there is to it! Wouldn’t it be wondrous if imperative languages did this? Maybe, someday…

Wrap This Up Already

Recursion is a useful technique for making code terse and comprehensible. However, it is less performant and breeds stack overflow exceptions in non tail call optimized languages. Carefully scrutinize your use case when choosing between recursive and iterative functions.

Thanks for reading!

Constructing the SUT (System Under Test) – Eradicating Brittle Unit Tests

I’m not going to proselytize unit testing in this blog post, there are hoards of articles on the internet for that already. Let’s just agree, for arguments sake, that they do awesome things for any software project. In spite of this majesty, brittle unit tests can suck the life out of programmers. There are many reasons for test frailty (a topic for another time), but the main one I’m going after in this piece is adding dependencies. In short, adding a new dependency to any class makes the existing tests fail. Is there anyway of getting around this? Yes there is!

As a side note: In a perfect world, software would be architected so elegantly that adding dependencies would be unnecessary. Unfortunately, I don’t live in that world. If you know how to get there please send me directions! That being said, adding dependencies may be a sign that you aren’t adhering to the single responsibility principal. Just something to keep in mind… Regardless, the pattern laid out below has made my life easier.

The Developer and the Brittle Test

Once upon a time, in a land far far away, our hero, writes the following really interesting service.

public class ReallyInterstingService { private readonly IDoSomethingAwesome _doSomethingAwesome; public ReallyInterstingService(IDoSomethingAwesome doSomethingAwesome) { this._doSomethingAwesome = doSomethingAwesome; } public string InterstingMethod() { return this._doSomethingAwesome.ToString(); } }

This really interesting service needs tests. Our hero, being a true hero, used TDD so he wrote the tests below before ever writing the service. Problem solved!

[TestClass] public class ReallyInterstingServiceShould { [TestMethod] public void ReturnString() { var awesomeMock = new Mock<IDoSomethingAwesome>(); var sut = new ReallyInterstingService(awesomeMock.Object); var result = sut.InterstingMethod(); Assert.IsInstanceOfType(result, typeof(string)); } }

The tests are fantastic! Anyone can refractor without fear. Life is good! However, as with any great story, along comes the antagonist: the evil manager. Management demands our hero to befoul really interesting service with some inanity. After a long battle, our hero concedes and makes the modifications below.

public class ReallyInterstingService { private readonly IDoSomethingAwesome _doSomethingAwesome; private readonly IDeathToAwesome _deathToAwesome; public ReallyInterstingService(IDoSomethingAwesome doSomethingAwesome, IDeathToAwesome deathToAwesome) { this._doSomethingAwesome = doSomethingAwesome; this._deathToAwesome = deathToAwesome; } public string InterstingMethod() { return this._doSomethingAwesome.ToString(); } public string LoadOfTripe() { return this._deathToAwesome.ToString(); } }

As you can see, a new dependency was added and now all the beautiful tests have failed. Woe to the kingdom. Our hero is vexed! How could he have foreseen this tragedy? What can he do to protect the program against such calamity in the future?

After a long quest our hero stumbles upon the humble author’s DotNetTestHelper open source project. It’s an incredibly simple library still in it’s infancy, but it has something wonderful: SutBuilder! He refractors the test as follows.

[TestClass] public class ReallyInterstingServiceShould { [TestMethod] public void ReturnString() { var awesomeMock = new Mock<IDoSomethingAwesome>(); var sut = new SutBuilder<ReallyInterstingService>() .AddDependency(awesomeMock.Object) .Build(); var result = sut.InterstingMethod(); Assert.IsNotNull(result); Assert.IsInstanceOfType(result, typeof(string)); } }

What wizardry is this say you? The SUT was constructed without the added dependency! The test is also protected against added dependencies in the future. The kingdom is saved! They lived happily ever after.

The End

Ok Ok Ok, that was a bit absurd. Anyway…

SutBuilder is a utility I wrote as part of an open source project of dot net testing utilities. The full source code is available here. What it does is simple: it constructs an instance of the generic type parameter. See the code below.

// These two statements have identical results sut = new ReallyInterstingService( new Mock<IDoSomethingAwesome>().Object, new Mock<IDeathToAwesome>().Object); sut = new SutBuilder<ReallyInterstingService>().Build();

Note: I’m using Moq to create mocks. I really dig that framework! It’s free and easy to use.

SutBuilder finds the constructor with the most arguments and uses it for instantiation. For each constructor argument, SutBuilder determines if an object of the argument type was passed in via the AddDependency method. If it was, it will pass that object to the constructor, otherwise it will pass an empty Moq mock of that type. AddDependency returns an instance of SutBuilder to provide a nice fluent API. See the code below.

IDoSomethingAwesome somethingAwesome = new DoSomethingAwesome(); // These two statements have identical results sut = new ReallyInterstingService( somethingAwesome, new Mock<IDeathToAwesome>().Object); sut = new SutBuilder<ReallyInterstingService>().AddDependency(somethingAwesome).Build();

All the magic happens in the Build method where It returns the created instance. That’s all there is to it!

As mentioned above, DotNetTestHelper is in it’s infancy. I will entertain any and all pull requests!

Thank you for reading!

Two Common Misconceptions about Multithreading and Async

I’ve recently talked to several experienced developers that struggle with the async/await keywords introduced in .NET 4.5. There are literally hundred of good articles out there on the topic; however, they continue to struggle with two misconceptions. The first is that the async keyword is just another way to do multithreading. The other is that multithreading and asynchrony are meant to improve performance. This blog post will give some history and dispel these fallacies.

Multithreading improves performance FALSE

I may be dating myself here, but I remember working with 16 bit windows (when I was a young humpback freak). Back then, the OS would hand over the CPU to an application. The application completely controlled the CPU and would relinquish control once it ran to completion. The OS had no way of breaking into the application process. Therefore, fatal exceptions or infinite loops would cause the machine to become unresponsive and the only way to regain control was a reboot. In order to combat this problem, threads were introduced.

In a nutshell, a thread is a virtualization of the CPU. Threads are provisioned by the OS and scheduled to run for a quantum (slice of time). At the end of each quantum, the OS performs a context switch. A context switch consists of storing away the current state of the registers and restoring the registers for the next thread. Threads are scheduled by the OS in a round robin fashion. This is how OS can do more than one thing at a time. If an application gets caught in an infinite loop, the OS can kill it from a different thread.

The main take away concept here is that, although very efficient, new threads and context switches are not free. The more threads there are, the more context switches, and the less time each thread has on the CPU. When you introduce threading, the overall system performance goes DOWN. Threading was introduced to make the OS fault tolerant against application errors. Any time you can perform work in a single thread, that is preferred.

The most common use of multithreading is to keep an UI responsive. A UI thread needs to be available to respond to user input; therefore, work needs to be done in different threads.

Now, it’s time to make a seemingly contradictory statement: multithreading can make your programs run faster. Raw performance and overall application processing time are two different things. Today, many machines come equipped with multiple CPUs. If you have CPU bound work (see the next section), you can reduce application processing time by scheduling multiple CPUs to do work at the same time. This assumes that the OS does not have the CPUs busy doing other things…

Asynchronous means Multithreading FALSE

Although the two concepts are somewhat related (you can do multithreading with the async/await keywords), they are very different. Asynchronous calls do pretty much the opposite of multithreading; they make a single thread do more. This is accomplished by not holding a thread hostage waiting on I/O bound work. Before we continue, lets define I/O bound verses CPU bound work.

I/O bound work – The OS makes a request to a device driver (network card, printer, hard drive, etc…). The device performs some work and returns data back to the OS.

CPU bound work – Actual processor cycles (long loops, calculations, etc…)

In reality, there is very little CPU bound work. Yes, it does exist but the majority of time intensive tasks fall into the I/O bound category.

When your application makes a request to a device driver (via the OS), it does not return data immediately. The OS sends the request to the device and then forgets about it until the device sends an interrupt indicating that it’s done. If your application is not using an asynchronous method call, the thread will just hang doing nothing while the device is doing it’s thing. An asynchronous method call will return the thread back to the OS so it can do other work. Once the OS receives the “I'm done” interrupt, the OS will schedule the work to resume. In this way, the OS avoids the overhead of creating new threads.

The above is an greatly simplified version of things; however, I hope it gave you enough of a conceptual understanding to enable you to use async/await in the right way. There are plenty of computer science resources out there if you want a deeper dive…

Thank you for reading! As always, feel free to hit me up with any questions.

Map Framework for AutoMapper

AutoMapper is an AMAZING open source project and I can’t do without it in my WebAPI and MVC projects

AutoMapper is an AMAZING open source project and I can’t do without it in my WebAPI and MVC projects. However, creating the class maps can be a bit cumbersome. Creating maps is resource intensive due to heavy use of reflection, so best practices dictate creating all maps at app startup. This is typically done with a single file, like below:

public static class AutoMapperConfig { public static void RegisterMaps() { Mapper.CreateMap<SomeClass, SomeClassViewModel>(); Mapper.CreateMap<SomeClassViewModel, SomeClass>(); Mapper.CreateMap<SomeOjbectDto, SomeObject>(); Mapper.CreateMap<SomeOjbect, SomeObjectDto>(); ... } }

This works; however, this file can become gigantic quickly. Additionally, it’s difficult to determine what maps already exist. This leads to duplicate maps or even the dreaded “Missing type map configuration” errors. Because of this, I created AutoMapperFramework. This is how it works.

First, you need to install the package via NuGet:

PM> Install-Package AutoMapperFramework

Next, you need to decorate the classes you want to create maps for with one or more of three header interfaces: IMapTo<T>, IMapFrom<T>, and IHaveCustomMappings. The first two are fairly self-explanatory: they will create a default map with no additional options. Your code file will look something like below:

public class SomeClass: IMapFrom<SomeClassDto>, IMapTo<SomeClassDto> { public string SomeProperty { get; set; } public string ServerOnlyProperty { get; set; } } public class SomeClassDto { public string SomeProperty { get; set; } }

Use IHaveCustomMappings if you need special options for your map.

public class SomeClass: IHaveCustomMappings { public string SomeProperty { get; set; } public string ServerOnlyProperty { get; set; } public void CreateMappings(IProfileExpression configuration) { configuration.CreateMap<SomeClassDto, SomeClass>() .ForMember(m => m.SomeProperty, opts => opts.MapFrom(s => s.SomePropertyWithADifferntName)); } } public class SomeClassDto { public string SomePropertyWithADifferntName { get; set; } }

Finally, you just need to tell AutoMapperFramework to load your maps. Create a class like the one below and run it on app start (Global.asax or anyway you like). If you have maps that do not exist in the currently executing assembly, just pass those types into LoadMappings separately. LoadMappings just accepts an IEnumerable<Type>.

public static class AutoMapperConfig { public static void RegisterMaps() { var mapLoader = new MapLoader(Mapper.Configuration); mapLoader.LoadMappings(Assembly .GetExecutingAssembly() .GetExportedTypes()); } }

If you have questions, feel free to hit me up on the AutoMapperFramework GitHub page. I’m also happy to accept any pull requests (as long as they build).

Thanks you for reading!

AngularJS – Forms in 1.3

Here is a presentation I did for CincyNG (Cincinnati AngularJS Meet up) on November18th, 2014. I exp

Here is a presentation I did for CincyNG (Cincinnati AngularJS Meet up) on November18th, 2014. I explain what’s new for forms in AngularJS 1.3

 

Here is a link to the slides: Forms and ng-model-options in AngularJs 1.3