Why does enumerating an empty array does not allocate on the heap?

Question

Consider the following benchmark:

[MemoryDiagnoser]
public class EnumerableBenchmark
{
    private IEnumerable<string> _emptyArray = new string[0];
    private IEnumerable<string> _notEmptyArray = new string[1];

    [Benchmark]
    public IEnumerator<string> ArrayEmpty()
    {
        return _emptyArray.GetEnumerator();
    }

    [Benchmark]
    public IEnumerator<string> ArrayNotEmpty()
    {
        return _notEmptyArray.GetEnumerator();
    }
}

BenchmarkDotNet reports the following results on .net framework 4.8 and .net core 3.1:

// * Summary *

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.329 (2004/?/20H1)
Intel Core i7-9750H CPU 2.60GHz, 1 CPU, 12 logical and 6 physical cores
.NET Core SDK=3.1.301
  [Host]     : .NET Core 3.1.5 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.27001), X64 RyuJIT
  DefaultJob : .NET Core 3.1.5 (CoreCLR 4.700.20.26901, CoreFX 4.700.20.27001), X64 RyuJIT


|        Method |     Mean |     Error |    StdDev |  Gen 0 | Gen 1 | Gen 2 | Allocated |
|-------------- |---------:|----------:|----------:|-------:|------:|------:|----------:|
|    ArrayEmpty | 3.692 ns | 0.1044 ns | 0.0872 ns |      - |     - |     - |         - |
| ArrayNotEmpty | 7.235 ns | 0.2177 ns | 0.3051 ns | 0.0051 |     - |     - |      32 B |

From the result, it seems that GetEnumerator causes a heap allocation when the array is not empty, but not when the array is empty. I've rewritten the benchmark in many different ways but always got the same result, so I don't think BenchmarkDotNet is wrong.

My logical conclusion was that empty arrays have a cached enumerator. However, this code seems to contradict that theory:

var emptyArray = new string[0];

var enum1 = emptyArray.GetEnumerator();
var enum2 = emptyArray.GetEnumerator();

Console.WriteLine("Equals: " + object.ReferenceEquals(enum1, enum2));
Console.WriteLine(enum1.GetType().Name + " - " + enum1.GetType().IsValueType);

Which displays:

Equals: False
SZArrayEnumerator - False

I'm really scratching my head on this one. Does somebody know what's going on?

Noblesse

Perhaps the JIT's managed to inline it? – Infatuated

@Infatuated I considered that the JIT might be doing some magic, that's why I moved the enumerables to fields. Since they're not constants or readonly, I don't think the JIT is allowed to make decisions based on their value (I even tried marking them as public to be extra sure). Now there could be some magic inside of the GetEnumerator method, but then I believe I should get the same reference every time I call it. – Noblesse

Could be that the JIT compiler is optimising it to Array.Empty<string>() – Doubleton

Here's the thing: when you call emptyArray.GetEnumerator() in your second test you are calling the non-generic implementation. Try ((IEnumerable<string>) emptyArray).GetEnumerator() instead. (The generic implementation does employ caching for enumerators of empty arrays.) – Salado

@JeroenMostert You're right. In that case we hit this codepath instead: referencesource.microsoft.com/#mscorlib/system/array.cs,2745 which returns a cached enumerator. Well played – Noblesse

@JeroenMostert ah yes, and the the ReferenceEquals passes - you should post that as an answer – Favorite

Answer 1

Your hypothesis is correct. In the presented benchmark, a cached version of the enumerator is used. Here is the decompiled code:

internal IEnumerator<T> GetEnumerator<T>()
{
  T[] array = Unsafe.As<T[]>((object) this);
  return array.Length != 0
      ? (IEnumerator<T>) new SZGenericArrayEnumerator<T>(array)
      : (IEnumerator<T>) SZGenericArrayEnumerator<T>.Empty;
}

However, when you tried to check your hypothesis, you changed the code. In the benchmark, _emptyArray is IEnumerable<string>, but in the code snippet, it's string[]. Here is the decompiled code for the string[].GetEnumerator:

public IEnumerator GetEnumerator()
{
  int lowerBound = this.GetLowerBound(0);
  return this.Rank == 1 && lowerBound == 0
      ? (IEnumerator) new SZArrayEnumerator(this)
      : (IEnumerator) new ArrayEnumerator(this, lowerBound, this.Length);
}

Let's try to change the snippet and cast the array to IEnumerable<string>:

IEnumerable<string> emptyArray = new string[0];

var enum1 = emptyArray.GetEnumerator();
var enum2 = emptyArray.GetEnumerator();

Console.WriteLine("Equals: " + object.ReferenceEquals(enum1, enum2));
Console.WriteLine(enum1.GetType().Name + " - " + enum1.GetType().IsValueType);

Here is the updated output that correctly verifies the hypothesis about the cached enumerator:

Equals: True
SZGenericArrayEnumerator`1 - False

Coulee