Saturday, April 9, 2011

The story of IIterable

I like the .NET Framework. To me, C# is a much better programming language than Java or C++, and it offers good performance at the same time. However, some of the fundamental design decisions in the .NET framework bother me. Which brings me to the subject of this post: I'm remaking some of the .NET collections library, built on top of a replacement for IEnumerable<T> called IIterable<T>.

You see, I'm a bit of a performance nut. So it bothers me that the IEnumerator<T> interface requires two interface calls to retrieve each element of a collection: MoveNext() and Current. Therefore, I invented a replacement and named it Iterator<T>:
   public delegate T Iterator<out T>(ref bool ended);

It had a corresponding interface called IIterable<T>, which is analogous to IEnumerable<T>:
   public interface IIterable<out T>
{
Iterator<T> GetIterator();
}

Microbenchmarks show that this iterator has (at most) half the overhead of IEnumerator, as you would expect. More on that later.

When an iterator is called, it returns the next value in the sequence, and sets ended to true if there are no more elements. It should be noted that Iterator<T> was originally defined as follows:
   public delegate bool Iterator<out T>(out T current);

This version was supposed to behave like IEnumerator.MoveNext(), returning true on success and false if there were no more elements in the sequence. It also happened to return the next value in the sequence, eliminating the need for IEnumerator.Current. Code that used the original Iterator<T> might look like this:

T current;
for (var moveNext = list.GetIterator(); moveNext(out current);)
{
...
}

This was very similar to code that uses IEnumerator directly (instead of using a foreach loop):
   for (var e = list.GetEnumerator(); e.MoveNext();)
{
T current = e.Current;
...
}

Unfortunately, the .NET Framework did not allow this signature because the CLR does not support true "out" arguments--"out" arguments are the same as "ref" arguments but with a special attribute on them, so at the CIL level they still permit the caller to supply an input value. That makes them incompatible with the <out T> part of the declaration: since they technically accept an input value, they must be invariant, not covariant. Thus I had to change the definition as written above:
   public delegate T Iterator<out T>(ref bool ended);

That's unfortunate, because using the iterator is much clumsier this way. for-loops like the one above must be written like this instead:
   bool ended = false;
for (var it = list.GetIterator();;)
{
T current = it(ref ended);
if (ended)
break;
...
}

This clumsiness is avoided using an extension method:
   public static bool MoveNext<T>(this Iterator<T> it, out T value)
{
bool ended = false;
value = it(ref ended);
return !ended;
}

Unfortunately, there is a performance penalty for calling MoveNext(), which eliminates most of the performance gain you get from using Iterator in the first place.

Anyway, these "Iterators" are returned from IIterable<T>.GetIterator. There's more to it than this--I actually created a whole series of collection interfaces to fix other things I don't like about the design of .NET collection interfaces--but for this post I'm just going to focus on IIterable<T> and Iterator<T>.

I spent the last two days working on an implementation of LINQ-to-Iterators, and then discovered that there is a problem. A rather serious problem.

Iterator<T> and IIterable<T> and various other interfaces derived from it are covariant: Iterator<out T> and IIterable<out T>. This makes it possible to write pointless code such as this:
   IIterable<object> Combine(IIterable<string> a, IIterable<Uri> b)
{
return a.Concat<object>(b);
}

That is, IIterable<string> and IIterable<Uri> is implicitly convertible to IIterable<object>. It requires C# 4.0, but in theory you can do this with any version of the .NET Framework since 2.0. With a helper method written in C# 4.0, it's even possible to write code that does the same thing in C# 2.0.

However, as I began to implement LINQ-to-Iterable I realized that there is one major problem. In practice, any collection that implements IIterable<T> will also implement IEnumerable<T>, for fairly obvious reasons: Microsoft and third-party libraries expect IEnumerable<T>, and the foreach loop expects a GetEnumerator method.

But if a class implements both IIterable<T> and IEnumerable<T>, that class would suddenly have weird problems with LINQ. Why? Well, IEnumerable<T> supports LINQ, and once I finish LINQ-to-Iterable, IIterable<T> will support LINQ too, and that's precisely the problem. Let's consider what happens if I try to run a LINQ query on my Deque<T> collection that implements IIterable<T> and IEnumerable<T>:
   Deque<int> list = ...;
var odds = Iterable.CountForever(3, 2);
var primes = from p in list
where (p > 2 && (p & 1) == 1) || p == 2
where !odds.TakeWhile(n => n * n <= p).Any(n => p % n == 0)
select p;

The compiler complains because it doesn't know which LINQ implementation to use: "Multiple implementations of the query pattern were found for source type 'Loyc.Runtime.Deque<int>'. Ambiguous call to 'Where'." The problem disappears if I remove "using System.Linq" from the top of my source file, or if I do the query against "(IIterable<int>)list" instead of just "list". However, it's an inconvenience at best. At worst, if the user doesn't understand why the error occurred and how to solve it, it's a showstopper.

I solved this problem by changing the definition of IIterable as follows:
   public interface IIterable<out T> : IEnumerable<T>

This forces all implementations of IIterable to also implement IEnumerable, but it solves the problem because the compiler no longer considers the choice ambiguous: if a class implements IIterable<T>, the compiler will choose LINQ-to-iterable without complaint. The reason is that IIterable is now considered more specific, and the compiler prefers more specific method signatures.

The variance dilemma

Unfortunately, this causes a new problem: it refuses to compile for any .NET Framework version before 4.0! This is because Microsoft made a very strange decision: even though CLR version 2.0 supports generic variance, IEnumerable<T> is defined as invariant before version 4.0.

Interesting, is it not, how the interaction of seemingly unrelated issues--the way extension method resolution works in C# 3.0 (2006) and the decision Microsoft made in 2005 to mark IEnumerable<T> as invariant--combine to screw up my LINQ implementation?

I could only think of two ways to work around this problem.

(1) Restrict covariance to .NET 4.0, i.e. in .NET 2.0, make IIterable<T> invariant.

If I choose this option, not only do we lose covariance in .NET 2.0 and .NET 3.5 (which is sad because it's a cool feature), but it also forces me to release at least two DLLs, one for .NET 2.0 (which relies on LinqBridge for some features), and one for .NET 4.0. Probably a .NET 3.0 version is needed too, for those that don't want a dependency on LinqBridge.

If this problem didn't exist then you could have at least used the same DLL for .NET 3 and 4. Technically you could reference the .NET 3 DLL in .NET 4 and lose variance, but this would have the side effect of breaking interoperability with any program that uses the .NET 4 DLL instead.

(2) Don't derive IIterable<T> from IEnumerable<T>.

This option allows IIterable<T> to remain covariant, but causes conflicts with LINQ-to-Enumerable as I already described. I fear that a lot of developers, when confronted with the "Ambiguous call to 'Where'" error, will immediately say "screw this" and refuse to use my collection classes.

Therefore, my decision is to keep the following definition of IIterable<T>:
public interface IIterable<out T> : IEnumerable<T> { ... }

Blah, blah, blah

I have a couple of comments about the design of Iterator<T>. Firstly, unlike IEnumerator, Iterator<T> does not implement IDisposable (indeed, it can't, since it's a delegate). My main rationale for this is that if your collection's iterator (as opposed to the collection itself) needs to implement IDisposable, you may as well continue using IEnumerator<T>. Certainly if Microsoft had chosen to use my "fast iterator" implementation when it first gave birth to .NET, it should have included IDisposable:
   interface IEnumerator<out T> : IDisposable
{
bool MoveNext(out T current);
}

Of course, back in the original .NET Framework of 2002, they weren't especially concerned with performance yet. And they hadn't invented generics yet. Plus, to make this interface variance-ready, they would have had to formally define "out" parameters as equivalent to return values. And while they were at it they could have maybe implemented return value inheritance covariance. But I digress...

Also, the C# language makes Iterator<T> much easier to implement as a delegate. For example, the implementation of Iterator.CountForever is very simple:
   public static Iterator<int> CountForever(int start, int step)
{
start -= step;
return (ref bool ended) => start += step;
}

Although it would be possible to write a helper class that converts a lambda function to the hypothetical "IIterator<T>" interface, this would incur an extra interface invocation above the cost of invoking the lambda, not to mention an extra memory allocation. Therefore, IIterator<T> would generally not be any faster than IEnumerator<T> (without special compiler support to eliminate the overhead).

Secondly, you may have noticed that "ref bool ended" is "ref" instead of "out". My reasoning, again, is that if you're using Iterator instead of IEnumerator it's because you want to squeeze out every last drop of performance. Therefore, to save time, Iterators are not required to clear "ended" on every iteration; they only need to set it once, at the end.

One more thing. After I release this library, if you want to implement IIterable<T>, you can make your job easier by using IterableBase<T> or ListSourceBase<T> as your base class, which provides implementations of GetEnumerator(). If your collection class already has GetEnumerator, and you want to add IIterable<T>, you could add this method:
   public Iterator<T> GetIterator()
{
return GetEnumerator().AsIterator();
}

But that's not necessarily a good idea, because the iterator itself will be slightly slower than the IEnumerator it was derived from. Only if a multi-step LINQ-to-Iterable query is built on top of this would there be any performance benefit. (I'll get around to some benchmarks later).

The performance of Iterator

I wrote some simple loops that call IEnumerator<T> (MoveNext and Current) on the one hand, and Iterator<T> on the other. The collections being enumerated just count numbers:
   public static IEnumerator<int> Counter1(int limit)
{
for (int i = 0; i < limit; i++)
yield return i;
}
public static Iterator<int> Counter2(int limit)
{
int i = -1;
return (ref bool ended) =>
{
if (++i < limit)
return i;
ended = true;
return 0;
};
}

On my machine, in a Release build, it basically takes 7.1 seconds to count to a billion if I use IEnumerator<int>, 3.552 if I invoke Iterator<int> directly, and 6.1 seconds if I call the Iterator<int>.MoveNext extension method. The raw Iterator is thus about twice as fast as IEnumerator, although my test is imperfect since it ignores loop overhead and the content of Counter1 and Counter2. (It should also be noted that results vary from run to run, and seemingly irrelevant changes to the benchmark code also change the results. Sometimes my benchmark reports that IEnumerator requires 250% as much time, and sometimes only 170%, depending on the weather and the test PC.)

Conclusion

With a performance difference of only 3.5 seconds in a billion iterations, it's fair to ask whether IIterable is really worth it. Well, in most circumstances it probably isn't. But LINQ queries tend to be composed of many simple components, which means that the time spent invoking MoveNext, Current, and your lambdas may be a large fraction of the total runtime. In the future I'll try to quantify the difference.

If you do find that your LINQ-to-objects queries are slow, it often means you're doing it wrong: maybe you're using an O(N^2) algorithm when you should have picked a O(N log N) algorithm. But I believe in "the pit of success": developers shouldn't have to work much harder to write fast code. Microoptimizations, like writing out a LINQ query longhand with "foreach" or "for" loops, and calling through a List<T> reference instead of IList<T>, should virtually never be necessary. Instead, the low-level code they use as their foundation should be as fast as possible.

It's a hobby of mine to explore how the most basic components of the .NET Framework can be adjusted for better performance, in order to slide high-level code closer to that "performance pit of success". I don't really expect you to go out of your way to use IIterable<T>, because most of the time the performance difference is quite small. However, those who want to finally write a video game, compiler, simulation or other computationally intensive program in a truly high-level language like C# with LINQ--instead of juggling pointers in C++ and writing "for (int i = 0; i < (int)collection.size(); i++)" on the chalkboard another thousand times--will appreciate libraries like the one I'm developing.

Microsoft, if you're reading this: yes, I would consider a job offer. Put me with the cool kids that are designing C# 5.0. I'll tack on support for IIterable via yield return, and needless to say I have many other ideas for improvement. Also, if you pay me to write Loyc and rename it C# 6.0, I promise not to complain.

Thanks for reading!

Monday, April 4, 2011

Update Controls

I've felt for a long time that something was wrong with the way we do GUI development. For instance, suppose we have a form with a list of people and some information about them:

A pointless person editor
(This used to be an HTML form but CodeProject wouldn't render it.)

Suppose that the "serial number" box should be disabled if the user does not have a bike. Traditionally, we would write an event handler for when the value of the checkbox changes, and update the Enabled property when it does. Some code bases would also have code when the current person changes, and we must also handle the situation that the list of persons is empty.

GUI-specific data binding can solve this particular problem most of the time; typically you can bind the Enabled property on the serial number box to the value of the checkbox. However, it might not handle the case that no person is selected. And there are many other scenarios where data binding is insufficient:
  • Suppose we would like the ListBox of persons to show a summary of each person (based on multiple properties of the person)--well, traditional data binding can't aggregate different properties of an object.
  • Suppose we have an options dialog box that controls the appearance of the main window, we would like any changes to the options to immediately alter the main window's appearance--well, traditional data binding doesn't work across different windows.
  • Suppose we are showing a shopping cart and we'd like to keep a label up-to-date that shows the total number of items and the total price--well, data binding can't aggregate properties of multiple objects.
  • Suppose we'd like to display a certain panel only if the application is running in "administrator" mode, AND an item is selected, AND a check box is checked--well, traditional data binding can't derive a value from multiple unrelated sources of information.
  • Suppose we'd like to filter a list based on a user's search string--in general, data binding doesn't help with filtering.

In these cases, if data binding helps at all, it requires you to jump through hoops, or add event handlers for edge cases, or at least keep dependencies in mind when you invoke your INotifyPropertyChanged events. For example, suppose you're using WPF and your ListBox is bound to a Person.ListLabel property that returns a summary string with the name and rank of a Person. If nothing else, you'll have to make sure you raise the PropertyChanged event for "ListLabel" when the name or rank is changed. That is, the code for the Name and Rank properties must explicitly state that ListLabel depends on them. (Now, you can avoid creating the ListLabel property by using a DataTemplate, but if you've programmed WPF then you have probably encountered the need to fire multiple PropertyChanged events for a single property change.)

Ideally, the actual code of a program should be closely related to the behavior rules it is supposed to follow. More generally, the solution space should resemble the problem space; your code should express your business rules. Usually, behavior rules can be described in a simple way:
  • "The serial number field is enabled only if 'Has a bike' is checked and a person is selected".
  • "The list box will show the name and rank of each person."
  • "The font size of the main dialog is to match the font size selected on the options dialog."
  • "In the shopping cart, the total price is shown under the list of items."
  • "The list only shows items that contain the text typed in the 'Filter' box."
Notice how all of these requirements are declarative. They describe the desired results, without considering how to keep the user interface up-to-date when changes occur. What must the program do when the user selects a different person or a different invoice? What must it do when the server tells us there a new person, or that a new item was created remotely in the shopping cart? The requirements don't say anything about that. Wouldn't it be nice if we didn't have to write code to handle these circumstances either?

Introducing Update Controls

In a University undergrad project I experimented with starting to solve this problem, using a concept I called "propagating variables". I didn't entirely figure out how to make it work, though. So I was delighted to find that someone had solved this problem in .NET land, with a framework called Update Controls. Update Controls is a different way of programming, so it takes some practice, but I am delighted with how it streamlines my code.

UpdateControls not only keeps your GUI up-to-date, but it also separates the GUI from the rest of the code better than any framework I have seen before. UpdateControls supports not only WPF but WinForms and Silverlight, too, and it encourages you to write your code in such a way that the view is replacable. I'm using UpdateControls for WinForms right now, because I find it easier, but if I ever want to upgrade to WPF, I will be able to do so with minimal changes to my Model and ViewModel code. Moreover, I could easily design a program that supports both a WinForms user interface and a Silverlight one at the same time: two views, one ViewModel. If somebody decides to create "UpdateControls for MonoTouch" someday, I could add an iPhone version, sharing the same viewmodel between Silverlight, WinForms and MonoTouch.

By strictly separating the ViewModel from the View, and placing all nontrivial logic in the ViewModel, you can effectively write unit tests for your GUI by writing tests for the ViewModel. Just make sure that the code in the View is so simple that no tests are needed, and that the output you want to test for is computed by the ViewModel instead of the View. You still have to manually test the view to make sure it looks right, but its logic and behavior can be unit-tested.

The Presentation and Navigation Models

Moreover, I am finding that the "Update Controls" way of doing things leads to clean, maintainable code. I especially like the Presentation Model concept. I think of the presentation model as a kind of "file system" of GUI state. That is, the presentation model is the root of a tree structure from which you can reach all of your application's important state information: the list of open documents, the currently selected item in each listbox, the options in your Options dialog, and so forth. The view (Forms and Controls) merely reflects the state of the presentation model.

Conceptually the presentation model (PM) is broken down into two parts: the model, and the navigation model. I am not sure where the view-models fit into this pattern; heck, maybe this "file system" idea isn't exactly what Micheal Perry (author of Update Controls) was thinking of when he described the pattern.

But I don't think it's necessary to follow the pattern exactly as described in his blog. The key idea is that you can put all important state information in a big tree (analogous to a file system, or to the DOM in web programming), filled with the two basic Update Controls primitives, Independents and Dependents (known collectively as Precedents). Placing state in the UC-enabled presentation model makes your code very maintainable, because
  • You no longer need to answer questions like "what events do I have to fire when I change this?" or "what properties change when this property changes?"
  • If your state is in the presentation model, you no longer have to worry about what physical control(s) display a piece of state information--because controls don't depend on each other--and you can even move controls between different dialog boxes without breaking anything (other than the controls being moved).
  • A tree structure is a good basis for a mental model of the application. In applications that hold state in many different ways, in separate "islands", it may be hard to keep track of everything. But the PM concept gives you a way to mentally visualize your program state and to communicate about state variables (because everything important has a named location in the tree.)

Have you ever fiddled with the console variables (CVars) in a video game such as Quake or Crysis? It's cool how you can change a variable and the game's output instantly matches the changes you make. Update Controls and the presentation model bring this kind of magic to your own code. You just define the state variables, stick them in a tree, and write simple snippets of code that describe how a GUI control depends on the tree.

The Presentation Model tree

The tree I'm describing isn't anything fancy. It's just an ordinary collection of classes, organized and nested in whatever way is most natural for the application. For instance, I'm writing an application that displays a collection of objects on a form. Well, actually there might be more than one collection of objects, with each collection shown on a different tab on the user interface; but I decided that my presentation model would only represent one data set (I create extra instances for multiple data sets). This data set has two fundamentally different kinds of objects, but for this discussion it doesn't matter what they are, so let's call them Apples and Bananas.

The user can have either a "live view" which shows the current state of the objects, or a historical view, which shows the state of the objects at some point in the past. Plus, there is an options dialog, and the Presentation Model has a reference to the options. Note that there are no GUI objects in the presentation model; it provides access to the options, not to the dialog! It has four main properties (HModel, ApplesVM, BananasVM, Options) which, in turn, contain other properties, forming a tree:

PresentationModel (class)
.HModel (HistoryBrowserModel class: represents the model at one instant in time)
.Model (Model class: holds the core data model)
.Apples (list of FruitObject with state and history of each apple)
.Bananas (list of FruitObject with state and history of each banana)
(properties of FruitObject are not shown because they are not relevant
to this blog entry. In reality, my app is not fruit-related.)
.StartTime (DateTime: minimum value of the time slider in the GUI)
.EndTime (DateTime: maximum value of the time slider in the GUI;
derived automatically from time stamps on the FruitObjects)
.ViewTime (DateTime: current time being viewed in the GUI)
.LiveMode (bool: if true, ViewTime will be locked to EndTime)
.Apples (a projection of Model.Apples at the current ViewTime)
.Bananas (a projection of Model.Bananas at the current ViewTime)
.ApplesVM (FruitListViewModel class)
.CompleteList (list of FruitViewModels derived from HModel.Apples)
.Filter (user-defined filter that reduces the set of objects to display)
.FilteredList (list of FruitViewModels limited by the Filter)
.SelectedItem (currently selected FruitViewModel, or if multiple apples are
selected, a fake ViewModel that provides a combined view)
.BananasVM (another instance of FruitListViewModel)
.CompleteList
.Filter
.FilteredList
.SelectedItem
.Options (shared between all instances of PresentationModel)
.ServerAddress
... (more options)

What I'm most proud of is the time slider. Basically, the time slider is bound to the value of _pm.HModel.ViewTime (where _pm is the presentation model). When the user moves the slider, an event written by me updates _pm.HModel.ViewTime. UpdateControls figures out the rest:
  1. It knows that _pm.HModel.Apples and _pm.HModel.Bananas depend on ViewTime and automatically updates them.
  2. It also knows that _pm.ApplesVM.CompleteList and _pm.BananasVM.CompleteList depend on _pm.HModel.Apples and _pm.HModel.Bananas so it updates the CompleteLists too.
  3. In turn, the FilteredList properties depend on the CompleteList properties so they are updated.
  4. Finally, the Update Controls in the tab (ListBoxes, etc.) know that they depend on FilteredList, so they update themselves too. Like magic!

All I had to do was correctly associate my data with Update Controls primitives such as Independent, Dependent, Independent<T>, Dependent<T>, DependentList<T> and IndependentList<T>; and to implement GetHashCode and Equals on wrapper objects such as ViewModels (it's important to tell UpdateControls that two wrappers are equal if the wrapped objects are equal.) UpdateControls automatically detects dependencies between properties that use these primitives, and updates all Dependents on-demand (i.e. when their values are requested).

Has a bike?

So let's say you've designed a presentation model "PModel" for your application and it represents the form shown at the beginning of this blog entry. You're using Windows Forms. So, first, you need to give the form a reference to the presentation model:
PModel _pm;
public Form1(PModel pm)
{
InitializeComponent();
_pm = pm;
}

// Somewhere else
Application.Run(new Form1(new PModel()));

Then, to ensure that the "serial number" checkbox (an instance of UpdateCheckBox) is enabled at the right time, use the WinForms designer to create an event handler for the "GetEnabled" event, and put the following code in it:
return _pm.SelectedPerson != null && _pm.SelectedPerson.HasBike;

Similar code snippets must be written for the control's Text property and for properties of all the other controls on the dialog. I'm not going to explain right now how to actually use Independents and Dependents to create the presentation model; I would refer you to the Update Controls blog for that information. Right now I just want to point out the two key advantages of this approach over conventional event-driven code:
  1. The code closely follows the requirement: "The serial number field is enabled only if 'Has a bike' is checked and a person is selected". If the requirements change, it's easy to update the code to match them.
  2. If you used Update Controls correctly (assuming no bugs in UC itself), there is no way the program can malfunction with respect to this requirement. It will always behave as that one line of code describes. The UC Way automatically leads to fewer bugs--although if you're new to UC, bugs that do occur tend to be serious head-scratchers.

I should point out one disadvantage to UpdateControls: it will permeate your codebase, changing the way you write both your ViewModels and your Models, so you'll be making a major commitment. And while UpdateControls integrates with WPF very closely, the WinForms version requires a special "Update" version of every control that you want to stay up-to-date automatically, and only a few properties currently support automatic updates. If you need to use 3rd-party Model classes in an UpdateControls app, you'll have to write decorator classes to augment the model classes with "Independent sentries". Similarly, to use 3rd-party controls in a WinForms app, you'll need to create a derived class or a special container that has private "Dependent sentries" and updates them during Application.Idle events. For example, I had to write an UpdateTrackBar class to represent my time slider, because UpdateControls didn't come with one.

Another issue, currently, is that the way UpdateControls handles lists is not scalable. Normally lists have a single "independent sentry" that controls updates to the lists. Adding, removing, or modifying a single item will cause each dependency to scan the entire list. If you are filtering a million-item list down to 100 items that you show on-screen, that million items will be scanned and filtered every time any item is added, removed, or changed, even if that item is not one of the 100 items displayed.

I'm trying to think of a way to make it more scalable, but I have no solutions to offer yet. There is one mitigating factor: UpdateControls updates dependencies in a kind of "lazy" fashion. If you change several items at once (e.g. in a single method or for-loop) in the million-item list, each of its dependencies is typically updated only once (in WinForms, dependencies will be updated in the next Application.Idle event; in WPF they will be updated in a posted message. Early updates occur on-demand, however, e.g. if your code explicitly accesses the filtered list.)

Still, I am quite certain that using a framework like UpdateControls will become an industry standard practice someday.

To get started with UpdateControls yourself, read its blog, check out examples such as Noteworthy, and write a small app to try it out. Noteworthy is odd--a "blog editor" that doesn't have a body text field?--but it seems to be the best example available at the moment. If you have any questions about UpdateControls, it's probably best to ask them on the discussions list.