Proposal: High performance code with readonly parameters within methods

[devedse]

Introduction

I've been building quite some algorithms in C# and doing this you often want to add some code where you can do things like logging progress or some other intermediate things that should only be executed if a certain flag is set to true. For example, let's take the following method:

        public static void DoSomething(int count, Action<int, int> progress)
        {
            for (int i = 0; i < count; i++)
            {
                if (progress != null)
                {
                    progress(i, count);
                }

                //Do something, e.g. sorting or w/e
            }
        }

If you would pass null as the value for progress it would still execute the if check. Which does for a lot of these low level algorithms actually impact the performance by quite some percentage.

In this case it would ofcourse be easy to just implement the method twice, one with the call to progress and one without, but as we'd all hate code duplication, let's see what else we could do.

Actual measurements

Do back up all my crazy claims let's look at a Maze generation algorithm that I've written. It's a simple implementation of the Backtrack algorithm:

        private InnerMap GoGenerateInternal(InnerMap map, IRandom random, Action<int, int, long, long> pixelChangedCallback)
        {
            if (pixelChangedCallback == null)
            {
                pixelChangedCallback = (vvv, yyy, zzz, www) => { };
            }

            long totSteps = (map.Width - 1L) / 2L * ((map.Height - 1L) / 2L);
            long currentStep = 1;

            int width = map.Width;
            int height = map.Height;
            int x = 1;
            int y = 1;

            var stackje = new Stack<MazePoint>();
            stackje.Push(new MazePoint(x, y));
            map[x, y] = true;

            pixelChangedCallback.Invoke(x, y, currentStep, totSteps);

            MazePoint[] targets = new MazePoint[4];

            while (stackje.Count != 0)
            {
                MazePoint cur = stackje.Peek();
                x = cur.X;
                y = cur.Y;

                int targetCount = 0;
                if (x - 2 > 0 && !map[x - 2, y])
                {
                    targets[targetCount].X = x - 2;
                    targets[targetCount].Y = y;
                    targetCount++;
                }
                if (x + 2 < width - 1 && !map[x + 2, y])
                {
                    targets[targetCount].X = x + 2;
                    targets[targetCount].Y = y;
                    targetCount++;
                }
                if (y - 2 > 0 && !map[x, y - 2])
                {
                    targets[targetCount].X = x;
                    targets[targetCount].Y = y - 2;
                    targetCount++;
                }
                if (y + 2 < height - 1 && !map[x, y + 2])
                {
                    targets[targetCount].X = x;
                    targets[targetCount].Y = y + 2;
                    targetCount++;
                }

                if (targetCount > 0)
                {
                    var target = targets[random.Next(targetCount)];
                    stackje.Push(target);
                    map[target.X, target.Y] = true;

                    currentStep++;

                    if (target.X < x)
                    {
                        map[x - 1, y] = true;
                        pixelChangedCallback.Invoke(x - 1, y, currentStep, totSteps);
                    }
                    else if (target.X > x)
                    {
                        map[x + 1, y] = true;
                        pixelChangedCallback.Invoke(x + 1, y, currentStep, totSteps);
                    }
                    else if (target.Y < y)
                    {
                        map[x, y - 1] = true;
                        pixelChangedCallback.Invoke(x, y - 1, currentStep, totSteps);
                    }
                    else if (target.Y > y)
                    {
                        map[x, y + 1] = true;

                        pixelChangedCallback.Invoke(x, y + 1, currentStep, totSteps);
                    }

                    pixelChangedCallback.Invoke(target.X, target.Y, currentStep, totSteps);
                }
                else
                {
                    stackje.Pop();
                }
            }

            return map;
        }

If the pixelChangedCallback is provided it will call this method 2 times per loop. However if it's not provided, it stubs it with an action that does nothing which is then being called.

If I completely remove the calls to the pixelChangedCallback we're looking at maze generation times of about 5.1 seconds. If I put a boolean around it the algorithm runs in 5.6 seconds and if I put the callback to null it takes about 5.7 seconds.

Implementing a boolean was done by doing a check once and then simply using the bool value everywhere else.

E.g.:

// At the start
bool isNullCallback = pixelChangedCallback == null;

// In the rest of the code
if (!isNullCallback)
{
    //Invoke...
}

Implementation	Average Duration
No callback	5.1 seconds
if check around callback	5.6 seconds
callback set to () => {}	5.7 seconds

It's ofcourse also possible to implement the whole algorithm with just one giant if check around it, but in my oppinion it doesn't produce clean code.

Proposal

Instead of trying to fix this with the current capabilities of C# / CoreCLR I think we might be able to implement something in the Compiler / JIT that could solve this.

Readonly parameters (or something similar)

If we could mark parameters in a method as readonly, the compiler could start making assumptions based on them to optimize the code execution path.

For example, if that Action would've been made null, all checks on the object itself (so not Properties of the object) which are compared to other readonly/constants could be assumed as always false or true.

This would probably mean we'd have multiple instances of the same method to be compiled, but we could quite easily limit this to only null checks / constants / or booleans for example.

If we would do this, code could still look the same, but using the knowledge that's available in the compiler could speed up high performance code.

Example implemenatation

An example of this implementation could be something like this:

        private InnerMap GoGenerateInternal(InnerMap map, IRandom random, Action<int, int, long, long> readonly pixelChangedCallback)
        {
            ....

What do you guys think?

[benaadams]

Change
if (progress != null)
to either
if (!ReferenceEquals(progress, null))
or
if ((object)progress != null))
or
if (progress is object)
or
if (!(progress is null))

Otherwise you go via the MulticastDelegate ==operator which doesn't inline and is a bit slower.

[devedse]

@benaadams , would this not incur a performance penalty? (And why?)

And the way I've implemented the ifcheck was this:
Implementing a boolean was done by doing a check once and then simply using the bool value everywhere else.

E.g.:

// At the start
bool isNullCallback = pixelChangedCallback == null;

// In the rest of the code
if (!isNullCallback)
{
    //Invoke...
}

So there shouldn't be any penalty because I'm only comparing a boolean to true or false.

Full example:

        private InnerMap GoGenerateInternal(InnerMap map, IRandom random, Action<int, int, long, long> pixelChangedCallback)
        {
            bool shouldInvokeCallback = pixelChangedCallback != null;

            if (pixelChangedCallback == null)
            {
                pixelChangedCallback = (vvv, yyy, zzz, www) => { };
            }

            long totSteps = (map.Width - 1L) / 2L * ((map.Height - 1L) / 2L);
            long currentStep = 1;

            int width = map.Width;
            int height = map.Height;
            int x = 1;
            int y = 1;

            var stackje = new Stack<MazePoint>();
            stackje.Push(new MazePoint(x, y));
            map[x, y] = true;

            if (shouldInvokeCallback)
                pixelChangedCallback.Invoke(x, y, currentStep, totSteps);

            MazePoint[] targets = new MazePoint[4];

            while (stackje.Count != 0)
            {
                MazePoint cur = stackje.Peek();
                x = cur.X;
                y = cur.Y;

                int targetCount = 0;
                if (x - 2 > 0 && !map[x - 2, y])
                {
                    targets[targetCount].X = x - 2;
                    targets[targetCount].Y = y;
                    targetCount++;
                }
                if (x + 2 < width - 1 && !map[x + 2, y])
                {
                    targets[targetCount].X = x + 2;
                    targets[targetCount].Y = y;
                    targetCount++;
                }
                if (y - 2 > 0 && !map[x, y - 2])
                {
                    targets[targetCount].X = x;
                    targets[targetCount].Y = y - 2;
                    targetCount++;
                }
                if (y + 2 < height - 1 && !map[x, y + 2])
                {
                    targets[targetCount].X = x;
                    targets[targetCount].Y = y + 2;
                    targetCount++;
                }

                if (targetCount > 0)
                {
                    var target = targets[random.Next(targetCount)];
                    stackje.Push(target);
                    map[target.X, target.Y] = true;

                    currentStep++;

                    if (target.X < x)
                    {
                        map[x - 1, y] = true;
                        if (shouldInvokeCallback)
                            pixelChangedCallback.Invoke(x - 1, y, currentStep, totSteps);
                    }
                    else if (target.X > x)
                    {
                        map[x + 1, y] = true;
                        if (shouldInvokeCallback)
                            pixelChangedCallback.Invoke(x + 1, y, currentStep, totSteps);
                    }
                    else if (target.Y < y)
                    {
                        map[x, y - 1] = true;
                        if (shouldInvokeCallback)
                            pixelChangedCallback.Invoke(x, y - 1, currentStep, totSteps);
                    }
                    else if (target.Y > y)
                    {
                        map[x, y + 1] = true;
                        if (shouldInvokeCallback)
                            pixelChangedCallback.Invoke(x, y + 1, currentStep, totSteps);
                    }

                    if (shouldInvokeCallback)
                        pixelChangedCallback.Invoke(target.X, target.Y, currentStep, totSteps);
                }
                else
                {
                    stackje.Pop();
                }
            }

            return map;
        }

[benaadams]

@benaadams , would this not incur a performance penalty? (And why?)

if (progress != null) calls the method bool operator !=(MulticastDelegate d1, MulticastDelegate d2) and if (progress == null) calls the method bool operator ==(MulticastDelegate d1, MulticastDelegate d2); the method then returns a bool which it then tests for true/false so are more expensive

The other 4 examples I gave just test if the pointer is zero; so wouldn't be much difference than doing a pretest and using a bool

[devedse]

@benaadams , thanks that might make sense to implement that way for some situations.

In my proposal there's still about a 15% overhead of the simple ifcheck which my proposal would omit.

[omariom]

Looks like C# knows what we actually want

[mikedn]

This is basically a case for loop unswitching, where the compiler (JIT) would create 2 versions of the loop - one with delegate calls and one without - and select between the two versions of the loop base on the delegate being null or not.

While perhaps it wouldn't be that hard for the JIT to do this, it would probably have to rely on some kind of runtime profiling because otherwise it would be difficult to decide when it would be beneficial to version loops like this. Especially in cases like yours, where the loop is rather large.

[mikedn]

// At the start
bool isNullCallback = pixelChangedCallback == null;
// In the rest of the code
if (!isNullCallback)
{
//Invoke...
}

That's more likely to hurt rather than help. Checking for null has the same cost as checking for true. But you have one more variable that needs to be kept alive within what's already a pretty large loop.

[benaadams]

You can sorta do what you want already using structs to do generic specialization with the type system; though its a bit messy

using System;

class Program
{
    public interface IAction
    {
        void Invoke(int step, int total);
    }

    public readonly struct HasAction : IAction
    {
        private readonly Action<int, int> _action;

        public HasAction(Action<int, int> action) => _action = action;
        public void Invoke(int step, int total) => _action(step, total);
    }

    public readonly struct NoAction : IAction
    {
        public void Invoke(int step, int total) => throw new NotImplementedException();
    }

    public static void DoSomething<TAction>(int count, TAction progress)
        where TAction : struct, IAction
    {
        for (int i = 0; i < count; i++)
        {
            // Branch elminated when TAction is a struct
            if (typeof(TAction) != typeof(NoAction))
            {
                // This call is eliminated when type is NoAction due to above type check
                progress.Invoke(i, count);
            }

            //Do something, e.g. sorting or w/e
        }
    }

    static void Main(string[] args)
    {
        // If checks are eliminated, and invoke is called 
        DoSomething(10, new HasAction((i, count) => { }));

        // If checks are eliminated, and invoke is *not* called
        DoSomething(10, default(NoAction));
    }
}

Note you have to use structs as classes when used as the type parameter create shared generics and won't specialize this way.

@redknightlois talks about it in his talk https://youtu.be/4yALYEINbyI?t=1878

[devedse]

Looks like C# knows what we actually want

Hi @omariom, not sure if you read my code but the IL does show that there's still an if check happening in your case. If I remove the action() call you can see there's a lot less IL generated, so it proves my point:

https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBLANgHwAEAmARgFgAoQ0pAAhLoGE6BvKuzujrwgZga062AHYZhdALx0ADAG4enRYPqEUdALIAKGsToBDMBmwQRASm6UubZdewAzOlsPHTdAITSRAV1y4ztlzsVtahnC4mIlpmCiFhdgDUCbHxdAC+yhlxltY0quoaxDqkehGmFsrBqQ5O7gBKMPYwsCJgMACiAI7e+rgAzs5GkWh0Pn5mAdnWValcZVExgWHYSSnxWdYbXMp5DAV8xaVD5TlBVACQ5yvJmVRpQA

@mikedn, I agree that in some cases it might not be "easy", but does that make this idea "bad"? I'm not an expert on any IL generation so I can't really tell the difficulty on implementing something like this, but I thought the idea of readonly variables is to be able to do optimizations.

[benaadams]

The generated asm for the two versions of the struct generics above showing it does what you want

https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8ABAJgEYBYAKBrIAJjyB2Ggbxvq8YGZ6BLAHYYYUAGbYwMegEkmpTtw7VuqxilmCAbhADWMABRCM9XCIAOaAcPoYIGbABsAlAG5FXAL40P9ANoAygAW2FDmADLYwAB0AEoArsL8+DDRAFL8GADiMIKi/GAGGACe5jAQYgYAEnjyzs5WwaERUXGJGMmpGdm5+YUlZRUGAHIQdc4Aur7EfExI6vQAIhABECkYQUIA5gA8ACryAHxGNpDtVgfkpPTmUBBbsLi4zr6qAO5BotKX1yCmGFB4mAMFY5FdfMo1NwxNB6CcTPx6ABeegABlcAnoO3oZ2EGP4AGoCS8VFD6JCyaoAPRU+gAISg2EEYCC9BgjnwQmwIgAJvQPrl6D8BLh6Nh/oDga8yfwxHCBuVKj9nPQAIQohVDUbjaVQimUqE0oWbUVgJyOEVsxzJLm8/mfQS2UrSfii7VXeg8+LSOxi4AQLQ+504z5gXS6g23e6PXDRGTaPSGfhWXEYNwR1TeWikg30GnLUxrGAbbZWVJbaKFqAdQRbeiwt5UmARrOZnw53j0WDYHkQQSOYoSoEmGq4eT0P5ghQd/VqW78LTc6Td3v9wfyHbGKzGQ70AD6kg6ffc2cpM3oo/kBg3W+sGF3h/4fZVSN3B+BT8dKMfx4j5+IGjxjo+jwv8MCWHetj2E4L5vj+ggGGY4FWHYDguCebantw54rn2A5DsC9Dur8sjyBCf6zIBCYgcYYEQbRqEwciu4bHcbz0Hk7GjBgMj4OYjgwCkwgwDyACiCBSOYR4IemHZZp4QA=

HasAction version

Program.DoSomething[[Program+HasAction, _]](Int32, HasAction)
    L0000: push rdi
    L0001: push rsi
    L0002: sub rsp, 0x28
    L0006: mov [rsp+0x48], rdx
    L000b: mov esi, ecx
    L000d: xor edi, edi
    L000f: test esi, esi
    L0011: jle L0028
    L0013: lea rcx, [rsp+0x48] ; loop start
    L0018: mov edx, edi
    L001a: mov r8d, esi
    L001d: call Program+HasAction.Invoke(Int32, Int32)
    L0022: inc edi
    L0024: cmp edi, esi
    L0026: jl L0013            ; loop end
    L0028: add rsp, 0x28
    L002c: pop rsi
    L002d: pop rdi
    L002e: ret

NoAction version

Program.DoSomething[[Program+NoAction, _]](Int32, NoAction)
    L0000: xor eax, eax
    L0002: test ecx, ecx
    L0004: jle L000c
    L0006: inc eax              ; loop start
    L0008: cmp eax, ecx
    L000a: jl L0006             ; loop end
    L000c: ret

[devedse]

@benaadams I like that idea very much actually :), smart way to solve this.

[mikedn]

I agree that in some cases it might not be "easy", but does that make this idea "bad"? I'm not an expert on any IL generation so I can't really tell the difficulty on implementing something like this, but I thought the idea of readonly variables is to be able to do optimizations.

It's not bad, it's just probably going to be rather difficult to get it right. readonly isn't useful here, the JIT should not have any problem figuring out that the null check is loop invariant without it (and the JIT doesn't really pay attention to readonly parameters, that's just a C# cosmetic thing).

The difficulty consists in deciding whether it's useful to clone such a large loop. Unless the application spends a lot of time in this loop, cloning it just increases the code size without any gain, quite the contrary. That's why I said that this might need runtime profiling (likely done as part of tiering), there's practically no way that the JIT will start cloning ANY loop that contains loop unswitching opportunities.

[devedse]

@mikedn , makes sense. Could we include some people in this conversation that might be able to give some valid input on that?

[devedse]

@benaadams , I was just thinking about this and was wondering if we could somehow rewrite this code to not have to include the quite big if check everywhere.

Do you know if it's possible to for example override the ? operator and be able to do something like this:

progress?.Invoke(a,b,c,d);

Where in the HasAction class we have something like:

override operator ?()
{
    return typeof(TAction) != typeof(NoAction);
}

[mikedn]

Could we include some people in this conversation that might be able to give some valid input on that?

@AndyAyersMS is likely the best person to comment on the chances of implementing loop unswitching in the JIT.