Fat Agnus

Loop unrolling, is a loop transformation technique that attempts to optimize a program’s execution speed at the expense of its size. – Wikipedia

What this means is that we are trying to limit the number of iterations to mitigate the overhead in a loop.

Consider this.

1
2
3
4

var i=values.length;
while(i--){
	processData(values[i]);
}

If we say that there are only 5 items in the array that will make it easier for us to unroll it.

1
2
3
4
5

processData(values[0]);
processData(values[1]);
processData(values[2]);
processData(values[3]);
processData(values[4]);

It isn’t pretty and it would probably be annoying to maintain such an approach if the size of the array grow or shrinks. The performance gain for this example wont make the downside worth it, but if the array was quite large then it would be useful, but still even more annoying to maintain.

Tom Duff to the rescue

Tom came up with a brilliant solution/pattern for unrolling loops in C, which got the name Duff’s Device and was later on converted to Javascript by Jeff Greenberg.

Here is the javascript version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

var iterations = Math.ceil(values.length / 8); 
var startAt = values.length % 8; 
var i = 0;  
 
do {     
	switch(startAt){         
		case 0: process(values[i++]);         
		case 7: process(values[i++]);         
		case 6: process(values[i++]);         
		case 5: process(values[i++]);         
		case 4: process(values[i++]);         
		case 3: process(values[i++]);         
		case 2: process(values[i++]);         
		case 1: process(values[i++]);     
	}     
	startAt = 0; 
} while (--iterations > 0);

The idea with this pattern is that each trip through the loop does the work of 1-8 iterations of a normal loop and Tom also figured out that 8 was the optimal number to use. A very important aspect of this pattern is the use of modulus, because not all arrays will be divisible by 8.

This technique might look a bit strange but it will actually run faster then a normal loop. How ever, we can make it run even faster, if we remove the switch statement from the loop, because conditionals have a performance overhead.

This example was introduced in Speed Up Your Site by Andrew B. King.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

var iterations = Math.floor(values.length / 8); 
var leftover = values.length % 8; 
var i = 0;  
 
if (leftover > 0){     
	do {         
		process(values[i++]);     
	} while (--leftover > 0); 
}  
 
do {     
	process(values[i++]);     
	process(values[i++]);     
	process(values[i++]);     
	process(values[i++]);     
	process(values[i++]);     
	process(values[i++]);     
	process(values[i++]);     
	process(values[i++]); 
} while (--iterations > 0);

This optimized Duff’s Device is 39 percent faster than the original and 67 percent faster than a normal for loop. - Speed Up Your Site, Andrew B. King

Finale word

Before you go and change all of your loops, you should consider if you really need to use this pattern. For small arrays the performance gain is to small to have any greater impact, so you should only applied this technique when you find a bottleneck that is related to a loop.

Further Reading

Even Faster Web Sites: Performance Best Practices for Web Developers

There are a few ways to implement this pattern and I will show you two different ways to do it, but first things first.

The Observer Pattern defines a one-to-many dependency between objects so that when one object changes state, all of its dependents are notified and updated automatically. - Head First, Design Patterns

When you are working with this pattern you usually have something called a Subject (sometimes referred to as Observerable) and an Observer. The Subject is an object that messages the Observers when its state is changed, just like it says in the above definition.

To illustrate how the pattern works you should think of a newspaper subscription, there you (the observer) subscribe to a newspaper (the subject) which you will receive when ever they send out a new issue.

In the first example we will look at how this pattern can be applied with a few interfaces and in the second example we will use a delegate and an event.

When this pattern is implemented in the right way you will have a loosely coupled design, which of course is something we want.

Example 1 – Using interfaces

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

public interface ISubject
{
	void RegisterObserver(IObserver o);
 
	void RemoveObserver(IObserver o);
 
	void NotifyObservers();
}
 
public interface IObserver
{
	void Update(string story);
}
 
public class NewsPublisher : ISubject
{
	private List<IObserver> observers = new List<IObserver>();
 
	private List<string> archive = new List<string>();
 
	public void RegisterObserver(IObserver o)
	{
		observers.Add(o);
	}
 
	public void RemoveObserver(IObserver o)
	{
		observers.Remove(o);
	}
 
	public void NotifyObservers()
	{
		foreach(IObserver o in observers)
		{
			o.Update(archive[archive.Count - 1]);
		}
	}
 
	public void PublishBreakingNews(string story)
	{
		archive.Add(story);
		ArchiveChanged();
	}
 
	private void ArchiveChanged()
	{
		NotifyObservers();
	}
}
 
public class NewsSubscriber : IObserver
{
	public void Update(string story)
	{
        Console.WriteLine("--------------------- Breaking News ---------------------");
        Console.Write(story);
        Console.WriteLine();
	}
}
 
class Program
{
	static void Main(string[] args)
	{
		NewsSubscriber me = new NewsSubscriber();
 
		NewsPublisher publisher = new NewsPublisher();
 
		publisher.RegisterObserver(me);
 
		publisher.PublishBreakingNews("hello world");
	}
}

Example 2 – Using delegates and events

This example look a lot like the Event Pattern, but there are a few conventions that differs like the name convention but also how the signature of the method looks like for the delegate, but since we aren’t using that pattern let’s move on.

I have added a few comments here and there to show the similarities between the previous example and this one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/// <summary>
/// Observer
/// </summary>
public class NewsSubscriber
{
	public void Update(string story)
	{
		Console.WriteLine("--------------------- Breaking News ---------------------");
		Console.Write(story);
		Console.WriteLine();
	}
}
 
/// <summary>
/// Subject
/// </summary>
public class NewsPublisher
{
	private readonly List<string> archive = new List<string>();
 
	public delegate void NotifyObserversHandler(string story);
 
	public event NotifyObserversHandler ArchiveChanged;
 
	public void PublishBreakingNews(string story)
	{
		archive.Add(story);
 
		// Notify observers
		ArchiveChanged(archive[archive.Count - 1]);
	}
}
 
class Program
{
	static void Main(string[] args)
	{
		NewsSubscriber me = new NewsSubscriber();
		NewsPublisher publisher = new NewsPublisher();
 
		//add the delegate to the event (register observer)
		publisher.ArchiveChanged += me.Update;
 
		publisher.PublishBreakingNews("Hello world");
	}
}

Finale word

As you can see the two examples work pretty much the same way, so it is really up to you to choose which one you prefer.

Further reading

Head First, Design Patterns

Events and Delegates

Exploring the Observer Design Pattern

I first learned about ActiveRecord (AR) when I was introduced to the MonoRail framework made by Castle. Then a few years later I started to learn about Domain-Driven Design (DDD) and found that is was an interesting way to design software. Just like so many other software design techniques, DDD also uses design patterns and one of them is the Repository Pattern.

Repository - A mechanism for encapsulating storage, retrieval, and search behaviour which emulates a collection of objects.
– Eric Evans, Domain-driven design

Usually when you use ActiveRecord from Castle, then your entities would have to inherit from a base class like ActiveRecordBase, but in this example we don’t need to do that anymore.

You need to have some basic understanding of ActiveRecords, NHibernate and the Repository Pattern to implement the example.

1
2
3
4
5
6
7

public interface IRepository<T>
{
	T FindBy(Guid id);
	IList<T> FindAll();
	void Save(T item);
	void Delete(T item);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class RepositoryBase<T> : IRepository<T> where T : IAggregateRoot
{
 
	public T FindBy(Guid id)
	{
		return (T)ActiveRecordMediator.FindByPrimaryKey(typeof(T), id);
	}
 
	public IList<T> FindAll()
	{
		return (IList<T>)ActiveRecordMediator.FindAll(typeof(T));
	}
 
	public virtual void Save(T item)
	{
		ActiveRecordMediator.Save(item);
	}
 
	public virtual void Delete(T item)
	{
		ActiveRecordMediator.Delete(item);
	}
}

The IAggregateRoot is just a marker interface, meaning that it doesn’t specify any functionality. I know that this might look like “code smell” to some, but it really depends on what you are trying to achieve.

Custom attributes are preferred when you can defer checking for the attribute until the code is executing. If your scenario requires compile-time checking, you cannot comply with this guideline.
- MSDN, Guidelines for developing Class libraries.

The problem with using AR with DDD

Well, PI means clean, ordinary classes where you focus on the business problem at hand without adding stuff for infrastructure-related reasons.
– Applying DDD and Patterns, Jimmy Nilsson

Using AR will you get up and running pretty fast, but you might want to remove the AR parts later on and then re-implement your repository to only use NHibernate. The reason for this is that entities shouldn’t know about how they are persisted (i.e. Persistence Ignorance) and when you apply them with AR attributes they do.

If you want to achieve a higher Persistence Ignorance, then you could try out Ayende’s Rhino-Tools (also know as rhino-commons). There you can find a better implementation of the Repository Pattern, which also uses NHibernate. Another solution would of course be to create one your self.

Further reading

Domain-Driven Design: Tackling Complexity in the Heart of Software

Applying Domain-Driven Design and Patterns: With Examples in C# and .NET