Running memcached on Windows

Memcached is a giant distributed hash table, allowing you to cache data in-memory across multiple machines in your data centre. Commonly, in the web 2.0 world, it's used to store the results of frequently-run queries to avoid hitting the database. This allows the database to scale much further, as it moves much of the load into the fast and almost transparent cache, allowing the database to concentrate on write operations. Many users of memcached report (when implemented correctly) database load dropping by a factor of 10 after implementing query caching in memcached.

Running memcached on Windows

Why? Linux is normally the OS of choice for running memcached, due to its stability, performance, and low TCO - I'd never recommend to run memcached on Windows in a production environment. However, the memcached network protocol is the same regardless of the client or server OS, meaning that organisations that develop mainly on the Microsoft platform can use a Linux cluster in production, but still conveniently run memcached on the local Windows development server.

Downloading the memcached server and client

Memcached is available from Danga (of LiveJournal fame) here. Memcached server for Windows is available here, and you can grab the latest .NET client from SourceForge here.

First Look

Unless you get the source release, the downloaded zip file contains a single file, memcached.exe – no documentation, no release notes. If you run this exe with the “–h” option you get the following list of options.

C:\memcached>memcached.exe -h
memcached 1.2.6
-p       TCP port number to listen on (default: 11211)
-U       UDP port number to listen on (default: 0, off)
-s      unix socket path to listen on (disables network support)
-a      access mask for unix socket, in octal (default 0700)
-l   interface to listen on, default is INDRR_ANY
-d start          tell memcached to start
-d restart        tell running memcached to do a graceful restart
-d stop|shutdown  tell running memcached to shutdown
-d install        install memcached service
-d uninstall      uninstall memcached service
-r            maximize core file limit
-u  assume identity of  (only when run as root)
-m       max memory to use for items in megabytes, default is 64 MB
-M            return error on memory exhausted (rather than removing items)
-c       max simultaneous connections, default is 1024
-k            lock down all paged memory.  Note that there is a
              limit on how much memory you may lock.  Trying to
              allocate more than that would fail, so be sure you
              set the limit correctly for the user you started
              the daemon with (not for -u  user;
              under sh this is done with 'ulimit -S -l NUM_KB').
-v            verbose (print errors/warnings while in event loop)
-vv           very verbose (also print client commands/reponses)
-h            print this help and exit
-i            print memcached and libevent license
-b            run a managed instanced (mnemonic: buckets)
-P      save PID in , only used with -d option
-f    chunk size growth factor, default 1.25
-n     minimum space allocated for key+value+flags, default 48

Running the server

Memcached has no configuration file – it's controlled purely by the command line parameters above. To run the server with default settings – 64Mb cache memory, and listening on port 11211.

If you use the “-vv” flag, you get a much more verbose output with details of client connections: Your memcached server is now running.

Running memcached as a Windows Service

The Win32 port also allows you to install and run memcached as a service, using the “-d” (daemonizer) switch with its various options. To install it, run the command:

memcached.exe –d install

This will install the server as a service available in the control panel. To start it, either run the command:

memcached.exe –d start

… or start it from your Services manager:

Configuration

The two main settings that may require configuration are the cache size, and port.

The default cache size is 64mb, which for any web 2.0 application is a pretty paltry cache. You can change the cache size (in megabytes) using the "-m" switch:

memcached.exe –m 1024

The above will configure memcached to use a gigabyte of memory.

Drawbacks to running as a service

If you configure memcached to run as a Windows service, you (as of release 1.2.6) lose the ability to configure the sevice as you would via the command line. The size of the cache defaults to 64mb, and the port to 11211. Parameters supplied on the command line when using “-d start” are ignored.

Generating Fractals with LINQ

Jump to the code

After seeing Luke Hoban's excellent LINQ ray tracer, I wondered if the same techniques could be used in other algorithmic image generators - specifically in generating the Mandlelbrot Set fractal.

I've never written a fractal generator before, so I used the Wikipedia article on the Mandelbrot Set, and some Java sources I found on the web as a base. Using a complex number class (strangely .NET does not provide its own) the algorithm is fairly simple.

Escape Time Algorithm

The simplest method of generating the image uses something called the escape time algorithm. Simply put, it iterates over every pixel in the image and calculates a number which is used to select a colour to draw that pixel - the number comes from repeating a calculation in the complex number plane and determining if during each repetition it satisfies an 'escape' condition - hence the name. Points within the mandelbrot set do not 'escape' (or escape to infinity), and so after a maximum number of iterations is hit the point is coloured black.

The maximum number of iterations is defined by the programmer, and determines the detail level of the fractal. The more iterations allowed, the better quality the output.

It's probably easier to describe in code.

public IEnumerable<PixelData> GenerateSet(int width, int height, int maxIterations)
{
  List<PixelData> result = new List<PixelData>();

  double xmin = -2.5;
  double xmax = 1;
  double ymin = -1.25;
  double ymax = 1.25;
  double dx = (xmax - xmin) / width;
  double dy = (ymax - ymin) / height;
  double x = xmin + dx / 2;
  
  for (int i = 0; i < width; i++)
  {
    double y = ymax - dy / 2;

    for (int j = 0; j < height; j++)
    {
      y = ymax - dy / 2;
      int iterations = countIterations(x, y, maxIterations);
      
      result.Add(new PixelData()
      {  
        X = i,
        Y = j,
        Iterations = iterations < maxIterations ? (int?)iterations : null
      });
      
      y -= dy;
    }
    
    x += dx;
  }
  
  return result;
}


int countIterations(double x, double y, int maxIterations)
{
  int result = 0;
  Complex c = new Complex(x, y);
  Complex z = new Complex(x, y);
  
  while (result <= maxIterations && z.Magnitude() < 2)
  {
    z = z * z + c;
    result++;      
  }

  return result;
}

This simple algorithm can produce some pretty fractals, but it is an iterative method, and this method doesn't translate easily to LINQ.

Eliminating the Outer Loops

The outer loops of the code above are the ones that iterate over the X and Y co-ordinates of the image. Using the Enumerable.Range() iterator we can replace those loops with LINQ statements that have the same effect:

from i in Enumerable.Range(0, width)
   let dx = (xmax - xmin) / width
   let dy = (ymax - ymin) / height
   let x = (xmin + dx / 2) + (i * dx)
   select from j in Enumerable.Range(0, height)
      let y = (ymax - dy / 2) - (j * dy)
      let iterations = countIterations(x, y)
      select new
      {
        X = i,
        Y = j,
        Iterations = iterations < maxIterations ? (int?)iterations : null
      };

This has the same effect as the two nested for-loops in the first example that run over the width and height of the image. But, we're still relying on the countIterations() method, that does the actual calculation of the escape count of the pixel. Clearly, if we are to call this a LINQ fractal generator, we must find some way to do this within in the context of a LINQ query.

This is where it start to get a bit tricky.

Eliminating the inner loop

The countIterations() method essentially counts the number of times it needs to calculate the value of z = z² + c before the magnitude, or absolute value, of z 'escapes' and becomes greater than 2. Since LINQ (or lambda expressions) do not afford us while-loops we must find another way to calculate this.

What we can do is replace the iterative calculation of z with a recursive one. Instead of escaping the algorithm, we can calculate the magnitiude of z for every value between 0 and the maximum number of iterations - then from that set select the maximum value that satisifes our escape condition, that the magnitude of z (| z |) < 2.

We can define a lambda expresssion that calculates the magnitude of z after any iteration by recusively calling itself, like this:

Func<int, Complex, Complex> f = 
    (int n, Complex z) => n > 0 ? f(n - 1, z) * f(n - 1, z) + c : z;

Phew. That's a bit nasty. It also won't compile, as the function f has not yet been fully defined. To get round this, we need to resort to using the Y-combinator. I used the same method as LukeH, and it results in the following code to generate the magnitude of z in the range 0...maxIterations:

from n in Enumerable.Range(0, maxIterations)
  let c = new Complex(x, y)
  let func = (Func<Func<int, Complex, Complex>, Func<int, Complex, Complex>>)
    (f => (n, z) => n > 0 ? f(n - 1, z) * f(n - 1, z) + c : z)
  let escape = Y(func)
  select escape(n, new Complex(x, y))

So, adding a where clause, an orderby clause and using the FirstOrDefault() method, we can get the expression to return the escape iteration count, or 0 if it escapes to infinity, as below.

let c = new Complex(x, y)
let func = (Func<Func<int, Complex, Complex>, Func<int, Complex, Complex>>)
  (f => (n, z) => n > 0 ? f(n - 1, z) * f(n - 1, z) + c : z)
let escape = Y(func)
let iterations = (from n in Enumerable.Range(0, maxIterations)
  where escape(n, new Complex(x, y)).Magnitude() < 2
  orderby n descending
  select n).FirstOrDefault()

So, now all we need to do is fit that into the outer loop query we wrote before.

Final result: the code

The final result looks something like this:

from i in Enumerable.Range(0, width)
  let dx = (xmax - xmin) / width
  let dy = (ymax - ymin) / height
  let x = (xmin + dx / 2) + (i * dx)
  select from j in Enumerable.Range(0, height)
    let y = (ymax - dy / 2) - (j * dy)
    let c = new Complex(x, y)
    let func = (Func<Func<int, Complex, Complex>, Func<int, Complex, Complex>>)
      (f => (n, z) => n > 0 ? f(n - 1, z) * f(n - 1, z) + c : z)
    let escape = Y(func)
    let iterations = (from n in Enumerable.Range(0, maxIterations)
      where escape(n, new Complex(x, y)).Magnitude() < 2
      orderby n descending
      select n).FirstOrDefault()
    select new PixelData()
    {
      X = i,
      Y = j,
      Iterations = iterations < maxIterations ? (int?)iterations : null
    };

Please note the above code is horribly inefficient. Using the iterative version I have been merrily running it over 256 iterations in almost real-time. but the LINQ version takes half a minute or so to execute over 8 - and I haven't managed to have the patience to run it over 16 yet. Since the number of iterations affects the quality of the picture, 8 iterations yields a rather sorry fractal, but given the time this method produces fractals every bit as pretty as the iterative version.

Iterator blocks and the "yield return" statement - #2

This is the second part of a two-part series. For the first post, see Iterator blocks and the "yield return" statement - #1.

IEnumerator

Before we jump into the nasty world of state machines and wotnot, let's start by re-familiarizing ourselves with the IEnumerator interface:

public interface IEnumerator
{
    bool MoveNext();
    object Current { get; }
    void Reset();
}

The important things here are MoveNext() and Current. The MoveNext() method moves to the next item in the set and returns a boolean indicating if there are any more items left in the set, and the Current property allows us to get the current item. This is all we need to support the foreach loop - it simply calls MoveNext() until it returns false, and uses the Current property for get the value for the loop variable.

IEnumerable and Iterator Blocks

Consider the following code from the previous post:

public static IEnumerable Workdays()
{
 yield return "Monday";
 yield return "Tuesday";
 yield return "Wednesday";
 yield return "Thursday";
 yield return "Friday";
}

static void Main()
{
 foreach (string day in Workdays())
 {
  Console.WriteLine(day);
 }
}

The foreach statement only operates over IEnumerable objects - so clearly the Workdays() method must be returning an IEnumerable instance (as its method signature suggests). So how how does it do that? We need to peek inside the compiled code with Reflector to find out the answer.

Inside the compiled code

Using Reflector, we are able to decompile the generated IL and get an approximate view of what the C# to create it would be. So, navigating to our type, we see that the Workdays() method is actually compiled into:

public static IEnumerable Workdays()
{
    return new <Workdays>d__0(-2);
}

What the... ? That is not the code we wrote. And what is this strangely named type, "<Workdays>d__0"?

State machines

To answer those questions, we need to take a step backwards, and look at something computer scientists call a state machine.

A state machine is a structure in which execution has a defined state, and from that state, it has a discrete list of subsequent states that it may transition into. A simple example would be to consider the road network to be a state machine - and the position of your car on the roads to be the state. If your car pulls up to a T-junction, you may turn either left or right - you may not jump somewhere two miles away onto a different road. Therefore the list of states that you can transition to is limited to a finite set, left and right. A state machine in computing works on the same principle - the program that is being executed has a definite state, and the state machine represents the current state, and the list of possible states that it can transition to next.

So how does this relate to our simple yield return example? Lets have another look in Reflector at the generated code, and specifically that strange <Workdays>d__0 type.

Looking closer

The class it generates is quite large and scary looking - I have stripped down to the relevant methods:

private sealed class <Workdays>d__0 : IEnumerable<object>, IEnumerable, IEnumerator<object>, IEnumerator, IDisposable
{
    private int <>1__state;
    private object <>2__current;

    public <Workdays>d__0(int <>1__state)
    {
        this.<>1__state = <>1__state;
    }

    private bool MoveNext()
    {
        switch (this.<>1__state)
        {
            case 0:
                this.<>1__state = -1;
                this.<>2__current = "Monday";
                this.<>1__state = 1;
                return true;

            case 1:
                this.<>1__state = -1;
                this.<>2__current = "Tuesday";
                this.<>1__state = 2;
                return true;

            case 2:
                this.<>1__state = -1;
                this.<>2__current = "Wednesday";
                this.<>1__state = 3;
                return true;

            case 3:
                this.<>1__state = -1;
                this.<>2__current = "Thursday";
                this.<>1__state = 4;
                return true;

            case 4:
                this.<>1__state = -1;
                this.<>2__current = "Friday";
                this.<>1__state = 5;
                return true;

            case 5:
                this.<>1__state = -1;
                break;
        }
        return false;
    }

    object IEnumerator.Current
    {
        get
        {
            return this.<>2__current;
        }
    }
}

The first thing we notice from this is that all the identifier names are mangled and that makes the code hard to follow. So, I've cleaned up the source further with meaningful identifier names:

private sealed class WorkdaysEnumerator : IEnumerable<object>, IEnumerable, IEnumerator<object>, IEnumerator, IDisposable
{
    private int m_State;
    private object m_Current;

    public WorkdaysEnumerator(int initialState)
    {
        this.m_State = initialState;
    }

    private bool MoveNext()
    {
        switch (this.m_State)
        {
            case 0:
                this.m_State = -1;
                this.m_Current = "Monday";
                this.m_State = 1;
                return true;

            case 1:
                this.m_State = -1;
                this.m_Current = "Tuesday";
                this.m_State = 2;
                return true;

            case 2:
                this.m_State = -1;
                this.m_Current = "Wednesday";
                this.m_State = 3;
                return true;

            case 3:
                this.m_State = -1;
                this.m_Current = "Thursday";
                this.m_State = 4;
                return true;

            case 4:
                this.m_State = -1;
                this.m_Current = "Friday";
                this.m_State = 5;
                return true;

            case 5:
                this.m_State = -1;
                break;
        }
        return false;
    }

    object IEnumerator.Current
    {
        get
        {
            return this.m_Current;
        }
    }
}

That's a bit clearer - we can see the all important MoveNext() and Current members. So how does it work?

Stepping into the State Machine

The code above is a simple implementation of a state machine. The current state is an integer, m_State in the cleaned up code, and it holds a value indicating what state the machine is currently in - in this example, it has five valid states, one per workday. The switch statement is the guts of the machine, that reads the state value and determines what do do next. Let's pick apart one branch of the switch statement:

case 3:
    this.m_State = -1;
    this.m_Current = "Thursday";
    this.m_State = 4;
    return true;

This branch is only executed when the state is equal to 3, which is set when it leaves the "Wednesday" branch. It sets the Current property to be "Thursday", and increases the state variable by one, making it ready for the next call to MoveNext() (which would set Current to "Friday").

Let's also have a closer look at the sequence of calls that are generated when a programmer writes a foreach loop over this iterator.

foreach (string day in Workdays())
{
 Console.WriteLine(day);
} 

This code actually compiles into something that looks like the below:

string day;
IEnumerable enumerator = new WorkdayEnumerator(0);

while (enumerator.MoveNext())
{
 day = enumerator.Current;
 Console.Writeline(day);
}

I've simplified the above a touch for clarity. Let's run through the sequence of calls that this loop would make and explain what happens to the state machine.

Step	Value of m_State (before)	Value of m_State (after)	Value of Current	MoveNext() returned
1	0	1	"Monday"	true
2	1	2	"Tuesday"	true
3	2	3	"Wednesday"	true
4	3	4	"Thursday"	true
5	4	5	"Friday"	true
6	5	-1	"Friday"	false

As you can see, when it hits the last valid state ("Friday"), it still makes one more call to MoveNext() - but since it has set the m_State value to 5, which is not a valid state, MoveNext() returns false and the loop exits.

Wrapping up and further reading

yield return allows us to write simple code to generate lists from complex structures without having to implement our own state machines. It also has some nice uses that are not immediately apparent - since an iterator can return an infinite series of values it can be put to use in many different contexts. Hopefully from this series of posts you have learned how to use yield return, and understand some of the complexity of the code that is generated behind the scenes. Go forth and iterate.

For more information, you might want to read the following.

• Wikipedia - Finite State Machines
• yield (C# Reference)
• Under the Hood - Fun with Iterators and State Machines
• Smart Software: Iterators, Not Just For Iteration

Iterator blocks and the "yield return" statement - #1

This is the first part of a two-part series. For the second post, see Iterator blocks and the "yield return" statement - #2.

C# 2.0 introduced a wonderful and underused piece of syntax - the "yield return" statement. This is the first of two posts - in this one I will explain what yield return is and how to use it, and in the second of I'll explain how it actually works internally.

Iterators

An iterator in C# is a coding construct that allows you to loop over a set of values using the foreach loop, without having to implement the entire IEnumerator interface. If you've ever rolled your own collection classes that needed you to implement IEnumerator, you might know what pain it can sometimes be. In particular, it is difficult to implement on non-linear data structures, such as trees, without some nasty hacking.

C# 2.0 allows us to avoid implementing the full IEnumerator interface, by writing a special iterator method, using yield return to provide values back to the caller. Such a method is called an iterator block - a method that returns either IEnumerable or IEnumerable<> - which can be either an instance or a static method.

Yield return

The yield return statement is used to return a single value from the iterator block. A simple example is below (taken from the MSDN documentation)

public static IEnumerable Power(int number, int exponent)
{
    int counter = 0;
    int result = 1;
    while (counter++ < exponent)
    {
        result = result * number;
        yield return result;
    }
}

In this example, the yield return statement is executed once per loop, returning the next value in the power set for the given parameters. It doesn't need to be used in a loop however - the following is perfectly valid:

public static IEnumerable Workdays()
{
 yield return "Monday";
 yield return "Tuesday";
 yield return "Wednesday";
 yield return "Thursday";
 yield return "Friday";
}

static void Main()
{
 foreach (string day in Workdays())
 {
  Console.WriteLine(day);
 }
}

Limitations

You can't nest yield return statements inside a try.. catch block, it can't be unsafe code, and can't appear in an anonymous method or lambda expression. Also, the iterator block cannot take ref or out parameters. This is all due to the way yield return is implemented internally, which I will be covering in the next post of this series.