SortedAction - Guaranteeing order of execution in pure C# delegate

There is something comforting about looking at a UnityEvent when serialized in Unity Editor's Inspector. It executes the actions assigned to it from top to bottom, in that order. No runtime accident can happen, this order of execution is pretty much guaranteed. Order of execution can make or break the logic of any program - did you refresh the money label before or after you subtract the amount of money paid for a restaurant meal?

Order of execution is such an important concern that rearranging the actions on UnityEvent has been a recurring question asked many times on the Unity official forum, and a feature implemented by just as many packages. Order of execution is serious business.

How then do we control order of execution without UnityEvent? Surely you will encounter scenarios even within a Unity project where you have only access to pure C# delegates, such as a static event.

In a pure C# delegate, actions are invoked in the ordered they are registered. This presents all sort of runtime problems. There are valid use cases where you want actions registered later to still execute before certain other actions, due to unpredictable runtime environments.

 

Workaround #1: Multiple delegates

The first thing that comes to mind for many of you reading this is probably to split one event into multiple. Instead of one OnXYZ event, you have OnEarlyXYZ, OnXYZ and OnLateXYZ events, invoked in that order in the same place where you would previously call OnXYZ.Invoke().

This may work on first glance, but then what if you need to guarantee something that executes even after OnLateXYZ? Do you create yet another event and call it OnEvenLaterXYZ? And another called OnEvenLatererXYZ? *Sniff* *Sniff* Did you smell that? That's some smell in your code.

This approach requires you to hard-code every segmentation of your event, which leads to awkward moments when you have to think of increasingly different names to differentiate one from another and also describe their invocation order.

Workaround #2: Manual list of invocations

If you have come to this idea, you are sort of getting a good execution-order-to-code mapping, but not quite.

Let's say instead of OnXYZ being a System.Action, it is a List<Action>. Alright, a C# List collection allows adding elements at the dead-last position with the Add method, or inserting elements at any arbitrary position within the list with the Insert method. "Unregister" with the Remove method. And in-order invocation is simply a for loop invoking each element from beginning to end.

The problem with this approach comes when you actually have to use it. Let's say you have an OnXYZ invocation list, you have M actions registered at the beginning belonging to some pre-processing tasks, you have N actions registered by objects created at runtime and N is unpredictable, will change many times during runtime, and you have O actions registered at the end belonging to some post-processing tasks. You have a new action that you want to execute right after the runtime objects execute their actions, but not before the post-processing tasks, so you have to insert the new action at index M + N, right?

But how do you actually calculate M and N? You have to manually keep track of the number of delegates that runtime objects register to OnXYZ, right? That sounds like a lot of work! And leaves room for hidden runtime logic error too.

What if you want to register your new action to execute before certain post-processing tasks? Do you remember how many actions that were? That sounds like another number you have to keep track of outside of the invocation list.

That is the problem with a manual invocation list in a nutshell. It's not structured to help you get an idea of where you should insert your actions to get your desired execution order. It delegates (completely unintended pun, I swear!) that hard work to you.

So how do we properly map execution order to code? An invocation list is a good place to start, but we don't want to calculate the correct index number required to have our actions sorted in the desired order. Can't we just... let the invocation list do the sorting for us?

Enters SortedList

SortedList is quite possibly one of the most underrated and overlooked collections in the .NET class library. It is much more like a Dictionary than a List, but what makes it different from a Dictionary is that upon every insertion, elements are sorted once using a key associated with each of them so that when you iterate through the SortedList using foreach, you always retrieve the elements in the key order.

So when you create a SortedList<byte, System.Action>, you can do this:

SortedList<byte, Action> OnXYZ = new SortedList<byte, Action>();

OnXYZ.Add(129, Action3);

OnXYZ.Add(52, Action1);

OnXYZ.Add(83, Action2);

// Execution order: Action1 -> Action2 -> Action3

foreach (var action in OnXYZ.Values) action.Invoke();

Notice that the key type of SortedList is defined first and you can save a bit of memory by giving it a key type with small memory footprint such as byte if you don't expect your invocation list to hold a lot of delegates.

From here, you can start to architect the source code in your project to define which system will execute at which execution number. You can define a safe range in which runtime delegates can register to and reserved ranges where your systems register to. Let's say your key type is uint, 0-99 is your pre-processing range, 100-1,999,999,999 as your runtime actions range and 2,000,000,000+ as your post-processing range. And that's how we guarantee execution order with pure C# delegate.

If you are perceptive, you will notice too that this architecture is similar to how Unity guarantees execution order of scripts in the Project Settings:

I will readily admit that this SortedList approach was wholly inspired by Unity's methodology to sort script executions. If you look further, you will also see this approach being used in shaders to sort objects in front and back, but instead of "execution order", you have "z-buffer".

Getting back to the topic of execution order, since we are not done here yet. Iterating through a list of Actions to invoke them will be something you do a lot, so we can shorten our syntax to get something more familiar with this:

public static partial class ExtensionMethods

{

  public static void Invoke<TKey>(this SortedList<TKey, Action> source)

  { foreach (var action in source) action.Value(); }

}

[...]

OnXYZ.Invoke();

Ah yes, OnXYZ.Invoke() is a much more familiar syntax. It informs the code readers how they should treat a SortedList<byte, Action> as too - like a delegate that you can specify execution orders.

In fact, if we're going to treat a SortedList of delegates as a special type of its own, why don't we subclass it to give it a name that makes semantic sense to its role?

public class SortedAction<TKey> : SortedList<TKey, Action> { }

[...] 

SortedAction<byte> OnXYZ = new SortedAction<byte>();

OnXYZ.Add(129, Action3);

OnXYZ.Add(52, Action1);

OnXYZ.Add(83, Action2);

// Execution order: Action1 -> Action2 -> Action3

OnXYZ.Invoke();

And there you have it. With some very minimal syntactical sugar on top of .NET class library, we get ourselves SortedAction - a delegate-like type that guarantees execution order. You only have to adjust somewhat to the syntax - with an additional key type parameter always preceding the argument types.

Oh yes, you can create SortedAction for the built-in Action delegates with arguments as well, so that you have SortedAction<TKey, T>, SortedAction<TKey, T1, T2>, etc...

I posted a gist of all possible SortedAction variations for all available Action delegates here. Drop it into any C# project and you're ready to use this type.

In the future, if this proposal makes it to the language, you may not even need to subclass SortedList to have an alias for SortedList<TKey, Action>, you can just write using SortedAction<TKey> = SortedList<TKey, Action>.

"But wait," - I hear you ask - "how should I use this class if I just want to add a bunch of actions at the same point in the execution queue without keeping track of a key number for each of them?"

Yes, that is a good question and a valid concern. Sometimes you want to register a bunch of text label updates to reflect the same variable's change in value and you don't particularly care label A or label B get updated first, or you can have an unpredictable number of text labels on runtime and you can't exactly keep track of a key number for each of them. How do you use SortedAction then?

Well, since SortedAction is just a pseudo-alias for SortedList<TKey, Action> which in turn is an implementation of the IDictionary<TKey,TValue> interface at the end of the day, and each delegate such as Action can also have other delegates added to it, you can just do this:

var OnXYZ = new SortedAction<int, string>();

// No-op anonymous method to make sure the action at this key is always

// non-null and invokable.

OnXYZ[1000] = delegate { };

// When you need to register en masse without knowing number of actions

// ahead of time.

foreach (var item in items) OnXYZ[1000] += item.OnUpdate;

// When you need to de-register en masse.

foreach (var item in items) OnXYZ[1000] -= item.OnUpdate;

That's all there is to it. All you need to keep in mind is a category of items have their actions registered to key 1000 (alternatively, a named constant integer with the samer value so you can write OnXYZ[PRE_UPDATE] for example). How the items are sorted within that category is inconsequential to your program. In this regard, SortedAction is even more flexible than Unity's Script Execution Order.

There is one last thing I want to briefly cover about SortedAction: Performance cost. The SortedList collection has some overhead over a plain List. Not the least of which is the cost of additions and removals. There is still no way to batch-add a collection of key-value pair so that only 1 sort is done per batch instead of per pair. This is a bigger issue with the IDictionary interface of C#, which is a story for another time. Furthermore, foreach loop on a SortedList collection creates more memory allocations than most of the other C# collections. SortedAction was conceptualized as the solution to a software architecture problem, not a performance optimization, so do keep this in mind.

Guaranteed order of callback execution in other languages

This post is firstly about SortedAction as implemented in C#, but it's also secondarily about software architecture. Order of execution is no doubt a concern in any programming language that enables the observer pattern. With that in mind, is there a way to replicate the functionality of SortedAction in other programming languages?

At the heart of SortedAction lies a particular type of data structure: a key-sorted dictionary. If we can find this data structure in the standard library of other languages, we can replicate SortedAction without too much friction.

In C++, we are blessed with the std::map class in the STL, and in fact, creating a sorted_action class in C++ involves much less boilerplate than in C# thanks to the robustness of C++ template programming:

#include <iostream>

#include <map>

#include <functional>

using namespace std;

template<class K, class... As>

class sorted_action : public map<K, function<void(As...)>> {

public:

  void invoke(As... args)

  {

    for (auto const& p : *this) p.second(args...);

  }

};

int main()

{

  sorted_action<int, float> on_xyz;

  on_xyz[16] = [](float _) { cout << "printing 16" << endl; };

  on_xyz[41] = [](float _) { cout << "printing 41" << endl; };

  on_xyz[34] = [](float _) { cout << "printing 34" << endl; };

  on_xyz.invoke(5.1);

  // Output:

  // printing 16

  // printing 34

  // printing 41

}

In Java, we have the TreeMap class in the JCL, which enables us to do this:

// SortedAction.java

import java.util.*;

import java.util.function.*;

public class SortedAction<K, A> extends TreeMap<K, Consumer<A>> {

  public void invoke(A arg) {

    for (Map.Entry<K, Consumer<A>> p : this.entrySet())

      p.getValue().accept(arg);

  }

}

// We will leave the inuniformity of Java's functional features for other

// pundits to talk about and just use Consumer as a demonstration of guaranteed

// execution order of event callbacks in Java.

In JavaScript, we don't have much luck. Its native Map type does not sort by keys on insertion, neither does its Object. You can still put callables into the values of a Map and sort by key before each iteration, but that may incur too much of a runtime cost. Sorting on insertion is the behavior we are looking for so that the keys are already in order by the time we iterate and invoke. You may want to search for a package for this type of data structure.

In Python, we once again don't have much luck with its dictionary type for similar reason.

These examples hopefully will point you in the right direction to implement guaranteed execution order in your respective languages.

Thank you for reading.