CODEWITHSUNDEEP
c#.net.net-coreclr
Luxant
Luxant

Reputation: 201

Is numbers comparisons as uint faster than normal int in c#

I was looking how some of the .Net core libraries were implemented and one of many things that caught my eye was that in Dictionary<TKey, TValue> class some numeric comparisons where done doing a casting to (uint) even though at my naive eyes this didn't impacted the logic.

For example on

do { // some magic } while (collisionCount <= (uint)entries.Length);

collisionCount was initialized at 0 and always incremented (collisionCount++) and thus entries being an array its length will not be negative either see source code

as opposed to

if ((uint)i >= (uint)entries.Length) { // some code }

source code line

where i could become negative in some occasions when doing the following, see debug img

i = entry.next;

and thus using it as positive would change the program flow (due to two's complement)

See an extract of the class code:

// Some code and black magic

uint hashCode = (uint)key.GetHashCode();
int i = GetBucket(hashCode);
Entry[]? entries = _entries;
uint collisionCount = 0;
if (typeof(TKey).IsValueType)
{
    i--;
    do
    {
        if ((uint)i >= (uint)entries.Length) // <--- Workflow impact
        {
            goto ReturnNotFound;
        }

        entry = ref entries[i];
        if (entry.hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entry.key, key))
        {
            goto ReturnFound;
        }

        i = entry.next;

        collisionCount++;
    } while (collisionCount <= (uint)entries.Length);
}

// More cool stuffs

Is there any performace gain or what is the reason for this?

Upvotes: 2

Views: 244

Answers (1)

Jeremy Lakeman
Jeremy Lakeman

Reputation: 11090

The linked Dictionary source contains this comment;

// Should be a while loop https://github.com/dotnet/runtime/issues/9422
// Test in if to drop range check for following array access
if ((uint)i >= (uint)entries.Length)
{
    goto ReturnNotFound;
}
 
entry = ref entries[i];

The uint comparison here isn't faster, but it helps speed up the array access. The linked github issue talks about a limitation in the runtime compiler, and how this loop structure allows further optimisations. Since this uint comparison has been performed explicitly, the compiler can prove that 0 <= i < entries.Length. This allows the compiler to leave out the array boundary test and throw of IndexOutOfRangeException that would otherwise be required.

In other words, at the time this code was written, and performance profiling was performed. The compiler wasn't smart enough to make simpler, more readable code, run as fast as possible. So someone with a deep understanding of the limitations of the compiler tweaked the code to make it better.

Upvotes: 2

Related Questions