Написание IEnumerator с производительностью, сравнимой с массивом foreach - PullRequest
Новая
       10

Написание IEnumerator с производительностью, сравнимой с массивом foreach

0 голосов
/ 23 февраля 2019

Чтобы добавить поддержку foreach в пользовательскую коллекцию, необходимо реализовать IEnumerable.Массивы, тем не менее, отличаются тем, что по существу они компилируются в цикл for на основе диапазона, который на намного быстрее, чем при использовании IEnumerable.Простой тест подтверждает, что: 

                number of elements: 20,000,000
                            byte[]:  6.860ms
       byte[] as IEnumerable<byte>: 89.444ms
CustomCollection.IEnumerator<byte>: 89.667ms

Тест: 

private byte[] byteArray = new byte[20000000];
private CustomCollection<byte> collection = new CustomCollection<T>( 20000000 );

[Benchmark]
public void enumerateByteArray()
{
  var counter = 0;
  foreach( var item in byteArray )
     counter += item;
}

[Benchmark]
public void enumerateByteArrayAsIEnumerable()
{
  var counter = 0;
  var casted = (IEnumerable<byte>) byteArray;
  foreach( var item in casted )
     counter += item;
}

[Benchmark]
public void enumerateCollection()
{
  var counter = 0;
  foreach( var item in collection )
     counter += item;
}

И реализация: 

public class CustomCollectionEnumerator : IEnumerable<T> where T : unmanaged
{
    private CustomCollection<T> _collection;
    private int _index;
    private int _endIndex;

    public CustomCollectionEnumerator( CustomCollection<T> collection )
    {
      _collection = collection;
      _index = -1;
      _endIndex = collection.Length;
    }

    public bool MoveNext()
    {
      if ( _index < _endIndex )
      {
        _index++;
        return ( _index < _endIndex );
      }
      return false;
    }

    public T Current => _collection[ _index ];
    object IEnumerator.Current => _collection[ _index ];
    public void Reset()  { _index = -1; }
    public void Dispose() {  }
}

public class CustomCollection<T> : IEnumerable<T> where T : unmanaged
{
  private T* _ptr;

  public int Length { get; private set; }

  public T this[ int index ]
  {
    [MethodImpl( MethodImplOptions.AggressiveInlining )]
    get => *_ptr[ index ];
    [MethodImpl( MethodImplOptions.AggressiveInlining )]
    set => *_ptr[ index ] = value;
  }

  public IEnumerator<T> GetEnumerator()
  {
    return new CustomCollectionEnumerator<T>( this );
  }
}

Поскольку массивы получают специальную обработку от компилятора, ониоставьте IEnumerable коллекции в пыли.Поскольку C # в значительной степени фокусируется на безопасности типов, я могу понять, почему это так, но это все еще несет абсурдное количество накладных расходов, особенно для моей пользовательской коллекции, которая перечисляет в точно так же, как , как массив,Фактически, моя пользовательская коллекция работает быстрее, чем байтовый массив в диапазоне, основанном на цикле for, поскольку она использует арифметику указателей для пропуска проверок диапазона массива CLR.

Так что мой вопрос: Есть ли способнастроить поведение цикла foreach так, чтобы я мог достичь производительности, сопоставимой с массивом? Может быть, с помощью встроенных функций компилятора или ручной компиляции делегата с помощью IL?

Конечно, я всегда могу вместо этого использовать диапазон, основанный на цикле. Мне просто любопытно, есть ли какой-нибудь возможный способ настроить низкоуровневое поведение цикла foreach аналогично тому, как компилятор обрабатывает массивы.

1 Ответ

0 голосов
/ 24 февраля 2019

Тип фактически не должен реализовывать IEnumerable / IEnumerable<T> для использования в операторе foreach.Оператор foreach типизирован по утке, это означает, что компилятор сначала ищет открытые методы с правильными сигнатурами (GetEnumerator(), MoveNext() и Current) независимо от того, являются ли они реализациями этих интерфейсов, и отступает толькок интерфейсам, если это необходимо.

Это открывает возможности для некоторых оптимизаций, которые могут существенно изменить жесткую петлю: GetEnumerator() может возвращать конкретный тип вместо IEnumerator<T>, что затем позволяет foreach цикл должен быть построен с не виртуальными и потенциально встроенными вызовами, а также делает перечислитель struct, чтобы избежать накладных расходов GC.Некоторые коллекции Framework, такие как List<T>, также используют это преимущество.

Вместе с парой других оптимизаций этот перечислитель, основанный на вашем CustomCollection, довольно близко подходит к циклу необработанного массива в микробенчмарке: 

public Enumerator GetEnumerator() => new Enumerator(this);

// Being a ref struct makes it less likely to mess up the pointer usage,
// but doesn't affect the foreach loop
// There is no technical reason why this couldn't implement IEnumerator
// as long as lifetime issues are considered
public unsafe ref struct Enumerator
{
    // Storing the pointer directly instead of the collection reference to reduce indirection
    // Assuming it's immutable for the lifetime of the enumerator
    private readonly T* _ptr;
    private uint _index;
    private readonly uint _endIndex;

    public T Current
    {
        get
        {
            // This check could be omitted at the cost of safety if consumers are
            // expected to never manually use the enumerator in an incorrect order
            if (_index >= _endIndex)
                ThrowInvalidOp();

            // Without the (int) cast Desktop x86 generates much worse code,
            // but only if _ptr is generic. Not sure why.
            return _ptr[(int)_index];
        }
    }

    internal Enumerator(CustomCollection<T> collection)
    {
        _ptr = collection._ptr;
        _index = UInt32.MaxValue;
        _endIndex = (uint)collection.Length;
    }

    // Technically this could unexpectedly reset the enumerator if someone were to
    // manually call MoveNext() countless times after it returns false for some reason
    public bool MoveNext() => unchecked(++_index) < _endIndex;

    // Pulling this out of the getter improves inlining of Current
    private static void ThrowInvalidOp() => throw new InvalidOperationException();
}
...