Início / coding / Perguntas / 78998264
Accepted
Ivan Petrov
Asked: 2024-09-18 20:43:05 +0800 CST

Quando a iteração no intervalo de uma matriz se tornou mais rápida do que a iteração na própria matriz?

  • 772

Neste vídeo recente de Nick Chapsas, no final ele comentou que o Findmétodo on List<T>era "não otimizado" porque o código não itera no Span do array, mas no próprio array:

public T? Find(Predicate<T> match) {
    if (match == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
    }

    for (int i = 0; i < _size; i++) {
        if (match(_items[i])) {
            return _items[i];
        }
    }
    return default;
}

Achei que a iteração em spans poderia ser feita tão rápido quanto em arrays (mas não mais rápido) a partir deste parágrafo da postagem do blog (atualizada?) de Stephen Toub sobre Spans:

O código assembly é tão similar em parte por causa da eliminação de verificações de limites. Mas também é relevante o reconhecimento do JIT do indexador span como um intrínseco, o que significa que o JIT gera código especial para o indexador, em vez de traduzir seu código IL real para assembly.

Tudo isso serve para ilustrar que o tempo de execução pode aplicar aos spans os mesmos tipos de otimizações que aplica aos arrays , tornando os spans um mecanismo eficiente para acessar dados.

Quando se tornou evidente que iterar no Span de um array seria tão rápido e talvez mais rápido do que apenas iterar no próprio array? Qual versão do .NET introduziu essas otimizações de JIT Span que não podiam ser usadas para arrays?

c#

1 respostas

  1. Best Answer

    A iteração em um intervalo tem duas vantagens aqui:

    1. evita uma indireção para um campo (em vez de um local) para a matriz
    2. o comprimento do vão é conhecido de forma previsível

    Se não estivesse _size também em jogo, seria possível consertar o código; por exemplo:

    for(int i = 0 ; i < _arr.Length ; i++)
{
    DoSomething(_arr[i]);
}

    simplesmente elevar _arrpara um local permite que o JIT elimine as verificações de limites, porque a matriz não pode ser reatribuída :

    var arr = _arr;
for(int i = 0 ; i < arr.Length ; i++)
{
    DoSomething(arr[i]);
}

    Note também que ambos foreach (var x in _arr)e foreach (var x in arr)seriam bons e permitiriam que as verificações de limites fossem elididas. No entanto, o chato _sizesignifica que as verificações de limites não podem ser elididas, e se o _sizenão corresponder _arr.Length(buffers superdimensionados), não podemos usar simples foreach. Span corrige isso indiretamente, porque o intervalo é limitado; criar um intervalo de comprimento _sizesignifica que, uma vez que o intervalo tenha sido construído (com validação de limites no construtor), o JIT pode confiar nele e elidir as verificações de limites.

    • 2

relate perguntas