(untagged)

MONADs in C#

PureNsanity

0.00/5 (No votes)

4 Sep 2015

What a MONAD is and how they impact your C# code

Introduction

MONADs are the cornerstone to LINQ, but few people know what they are and even fewer know how they work. It's possible to use MONADs in ways that destroy performance, so this tip is going to share how they work and how you can avoid that.

Background

Before reading this tip, you should be familiar with:

Collections
IEnumerable
IQueryable
LINQ
Enumerators

What is a MONAD?

A MONAD as defined by Wikipedia is a structure that represents computations defined as sequences of steps: a type with a monad structure defines what it means to chain operations, or nest functions of that type together.

Why Should I Care?

So what's the big deal and who cares if I know what the definition is? Well the problem is that if you don't understand how a MONAD executes versus how traditional lines of code execute, you risk disastrous performance effects. LINQ builds MONADs so you might not have realized it, but you're probably using MONADs all the time.

When you build a MONAD, the code doesn't actually execute until you call a finalizer (not sure if this is the actual term) that causes the MONAD to evaluate. Some common finalizers are Count(), First(), Last(), and ToList().

At first, this could sound like a good thing. Less code executing is better, right? Well... Not always... Let's say my MONAD includes some sort of intensive service call to return a result set of items. If I have five places that use the Count() of the result set is going to call that intensive service call five times!

So How Disastrous is Disastrous?

Below is a sample app you can run to see how bad this can get:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MONAD
{
    class Program
    {
        static void Main(string[] args)
        {
            var people = new List<Person>()
            {
                new Person("Alan"),
                new Person("Kiersten"),
                new Person("Bryan"),
                new Person("Madeline"),
                new Person("Jessica"),
                new Person("Mabel"),
                new Person("Diane"),
                new Person("David")
            };

            Console.WriteLine("Creating MONADs");

            var sortedPeople = people.OrderBy(p => 
                { 
                    Console.WriteLine("Ordering for " + p.Name); 
                    return p.Name; 
                });

            var sortedPeopleNotStartingWithD = sortedPeople.Where(p => 
                { 
                    Console.WriteLine("Checking start for " + p.Name); 
                    return !p.Name.StartsWith("D"); 
                });

            Console.WriteLine("Starting loop");

            for (int i = 0; i < sortedPeopleNotStartingWithD.Count(); ++i)
            {
                var personToPrint = sortedPeopleNotStartingWithD.ElementAt(i);

                Console.WriteLine("Retrieved " + personToPrint.Name);
            }

            Console.WriteLine("Finished loop, press any key to continue...");
            Console.ReadKey();
        }

        public class Person
        {
            public Person(string name)
            {
                Name = name;
            }

            public string Name { get; set; }
        }
    }
}

Here's the output:

Creating MONADs
Starting loop
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Checking start for Madeline
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Retrieved Alan
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Checking start for Madeline
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Retrieved Bryan
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Checking start for Madeline
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Retrieved Jessica
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Checking start for Madeline
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Retrieved Kiersten
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Checking start for Madeline
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Retrieved Mabel
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Checking start for Madeline
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Checking start for Madeline
Retrieved Madeline
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Checking start for Madeline
Finished loop, press any key to continue...

The reason why you get so many excessive calls is that in a MONAD, it's evaluated on demand and there is nothing that I'm doing in that sample Console application to push the results to a physical list.

Notice how "Starting loop" is called before any elements are ordered? That's because the first time the MONAD is demanded to be evaluated is when I call Count(). Since neither sortedPeople nor sortedPeopleNotStartingWithD are evaluated, I have to call each of those. And the next time the loop has an iteration, guess what? They're still evaluated on demand so everything gets run again.

If I add one little ToList() to push the results to a physical list as such:

var sortedPeopleNotStartingWithD = sortedPeople.Where(p =>
    {
        Console.WriteLine("Checking start for " + p.Name);
        return !p.Name.StartsWith("D");
    })
    .ToList();

Here's what you get:

Creating MONADs
Ordering for Alan
Ordering for Kiersten
Ordering for Bryan
Ordering for Madeline
Ordering for Jessica
Ordering for Mabel
Ordering for Diane
Ordering for David
Checking start for Alan
Checking start for Bryan
Checking start for David
Checking start for Diane
Checking start for Jessica
Checking start for Kiersten
Checking start for Mabel
Checking start for Madeline
Starting loop
Retrieved Alan
Retrieved Bryan
Retrieved Jessica
Retrieved Kiersten
Retrieved Mabel
Retrieved Madeline
Finished loop, press any key to continue...

The General Rules

Because of how disastrous an expensive call can get if left in a MONAD, I always return an evaulated collection (i.e., List<T>, Dictionary<TKey, TValue>) instead of a MONAD (i.e. IEnumerable<T>, IGrouping<TKey, TSource>) for expensive calls.

It's not optimal to evaluate everything all the time though. There are cases where you can build a MONAD but it never gets consumed, so you save if you didn't evaluate it. LINQ will also try to optimize the calls so it can be beneficial to leave it unevaluated until completely built.

If I have the time, I'll generally try to optimize it accordingly, but I default to finalizing everything.

Any() versus Count() > 0

So these are two LINQ extension methods commonly used, but do you know which one you should use? If you didn't notice in the output calls to Count() functions by incrementing a count as it enumerates the entire collection. After all, Count() is an extension method for IEnumerables.

Any() simply needs to iterate the first item. Once it verifies, it reaches an item or not, you have your result - much more efficient.

Obviously, if you need the actual count like in the code example iterator, you can't replace it with a call to Any(). Just be aware of how it's working though so you can determine what you can do to improve performance when you need to.

Points of Interest

Seriously folks, I have seen applications destory performance with MONAD service and database calls. Be aware of how each LINQ method operates so you can avoid these situations.

History

2015-09-04: Celebrating I wrote about MONADs because no one ever asks about MONADs

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here