Aqui está uma rápida olhada nos recursos de vetorização de algoritmos no .NET Framework e .NET Core. Este artigo é para aqueles que não sabem nada sobre essas técnicas. Também mostrarei que o .NET não fica para trás das linguagens "reais compiladas" para o desenvolvimento nativo.
Estou apenas começando a aprender técnicas de vetorização. Portanto, aprecio se os membros da comunidade encontrarem erros claros ou sugerirem melhorias nos algoritmos descritos.
Alguma história
O SIMD apareceu no .NET Framework 4.6 em 2015. Foi quando os tipos Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 e Vector4 foram adicionados. Eles permitiram cálculos vetorizados. Em seguida, foi o tipo Vector <T> que deu mais oportunidades para vetorizar algoritmos. No entanto, muitos programadores ainda estavam insatisfeitos, pois esses tipos restringiam o fluxo de idéias dos codificadores e não deixavam usar toda a capacidade das instruções SIMD nos processadores modernos. Agora, no .NET Core 3.0 Preview, temos o espaço para nome System.Runtime.Intrinsics, que oferece muita liberdade na escolha das instruções. Para obter o máximo de velocidade, você precisa usar o RyuJit e recorrer à montagem x64 ou desativar o Prefer 32 bits e escolher AnyCPU assembly. Eu executei todos os benchmarks no computador com CPU Intel Core i7-6700 3.40 GHz (Skylake).
Somando elementos da matriz
Decidi começar com uma tarefa clássica que geralmente vem primeiro se houver vetorização envolvida. Ele trata de encontrar a soma dos elementos da matriz. Vamos escrever quatro implementações desta tarefa para somar os elementos da matriz.
A implementação mais óbvia:
public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }
Implementação baseada em LINQ:
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
A implementação baseada em vetores do System.Numerics:
public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
A implementação baseada no código do espaço para nome System.Runtime.Intrinsics:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
Comparei esses quatro métodos no meu computador e obtive os seguintes resultados:
É claro que as soluções com Vectors e Intrinsics são muito mais rápidas que as soluções óbvias e baseadas em LINQ. Agora precisamos descobrir o que acontece nesses dois métodos.
Vamos considerar o método Vectors mais de perto:
Vetores public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
- int vectorSize = Vetor <int> .Count; - a quantidade de números de 4 bytes que podemos colocar em um vetor. Se a aceleração de hardware for usada, esse valor mostra quantos números de 4 bytes podemos colocar em um registro SIMD. De fato, mostra quantos elementos desse tipo podem ser manipulados simultaneamente;
- accVector é um vetor que acumula o resultado da função;
- var v = novo vetor <int> (matriz, i); - os dados da matriz são carregados em um novo vetor v, iniciando no índice i. O vetor Tamanho dos dados será carregado exatamente;
- accVector = Vector.Add (accVector, v); - dois vetores são somados.
Por exemplo, existem 8 números na matriz: {0, 1, 2, 3, 4, 5, 6, 7} e vectorSize == 4.
Então, durante a iteração do primeiro ciclo accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3} e após a adição o accVector manterá: {0, 0, 0, 0} + {0, 1 , 2, 3} = {0, 1, 2, 3}.
Durante a segunda iteração v = {4, 5, 6, 7} e após a adição accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}. - Agora só precisamos obter a soma de todos os elementos do vetor. Para fazer isso, podemos usar a multiplicação escalar por um vetor preenchido por esses: int result = Vector.Dot (accVector, Vector <int> .One);
Então temos: {4, 6, 8, 10} * {1, 1, 1, 1} = 4 * 1 + 6 * 1 + 8 * 1 + 10 * 1 = 28. - Se necessário, os números que não se encaixam no último vetor serão somados no final.
Vamos analisar o código intrínseco:
Intrínseca public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
Podemos ver que é como Vetores com uma exceção:
Comparando duas matrizes
Precisamos comparar duas matrizes de bytes. Foi exatamente essa tarefa que me levou a estudar o SIMD no .NET. Novamente, vamos escrever vários métodos para fazer benchmarking e comparar duas matrizes: ArrayA e ArrayB.
A solução mais óbvia:
public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
Solução baseada em LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
A solução baseada na função MemCmp:
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)] static extern int memcmp(byte[] b1, byte[] b2, long count); public bool MemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0;
A solução baseada em vetores do System.Numerics:
public bool Vectors() { int vectorSize = Vector<byte>.Count; int i = 0; for (; i <= ArrayA.Length - vectorSize; i += vectorSize) { var va = new Vector<byte>(ArrayA, i); var vb = new Vector<byte>(ArrayB, i); if (!Vector.EqualsAll(va, vb)) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
Solução baseada em intrínseca:
public unsafe bool Intrinsics() { int vectorSize = 256 / 8; int i = 0; const int equalsMask = unchecked((int) (0b1111_1111_1111_1111_1111_1111_1111_1111)); fixed (byte* ptrA = ArrayA) fixed (byte* ptrB = ArrayB) { for (; i <= ArrayA.Length - vectorSize; i += vectorSize) { var va = Avx2.LoadVector256(ptrA + i); var vb = Avx2.LoadVector256(ptrB + i); var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } }
Os resultados da execução do benchmark no meu computador:
Eu acho que o código desses métodos é claro, exceto por duas linhas no Intrinsics:
var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }
Na primeira linha, dois vetores são comparados em termos de igualdade e o resultado é salvo no vetor areEqual, no qual todos os bits do elemento em uma posição específica são definidos como 1 se os elementos correspondentes em va e vb forem iguais. Portanto, se os vetores de bytes va e vb forem iguais, todos os elementos em areEquals devem ser 255 (11111111b). Como o Avx2.CompareEqual é um invólucro sobre _mm256_cmpeq_epi8, podemos acessar o site da Intel e ver o pseudocódigo desta operação:
O método MoveMask cria um número de 32 bits a partir de um vetor. Os bits superiores de cada elemento de 32 bytes em um vetor são os valores dos bits no resultado MoveMask. O pseudocódigo está disponível aqui .
Portanto, se alguns bytes em va e vb não corresponderem, os bytes correspondentes em areEqual serão 0. Portanto, os bits superiores desses bytes também serão 0. Isso significa que os bits correspondentes na resposta Avx2.MoveMask também serão 0 e areEqual não será igual a equalsMask.
Vejamos um exemplo, assumindo que o comprimento do vetor seja 8 bytes (para escrever menos):
- Seja va = {100, 10, 20, 30, 100, 40, 50, 100} e vb = {100, 20, 10, 30, 100, 40, 80, 90}.
- Então areEquals serão {255, 0, 0, 255, 255, 255, 0, 0}.
- O método MoveMask retornará 10011100b que deve ser comparado à máscara 11111111b. Como essas máscaras não são iguais, os vetores va e vb também não são iguais.
Contando as vezes que um elemento ocorre em uma coleção.
Às vezes, você precisa contar as ocorrências de um elemento específico, por exemplo, números inteiros, em uma coleção. Também podemos acelerar esse algoritmo. Para comparação, vamos escrever vários métodos para pesquisar o elemento Item na matriz.
O mais óbvio:
public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; }
Usando LINQ:
public int LINQ() => Array.Count(i => i == Item);
Usando vetores de System.Numerics.Vectors:
public int Vectors() { var mask = new Vector<int>(Item); int vectorSize = Vector<int>.Count; var accResult = new Vector<int>(); int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); var areEqual = Vector.Equals(v, mask); accResult = Vector.Subtract(accResult, areEqual); } int result = 0; for (; i < array.Length; i++) { if (array[i] == Item) { result++; } } result += Vector.Dot(accResult, Vector<int>.One); return result; }
Usando Intrinsics:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var temp = stackalloc int[vectorSize]; for (int j = 0; j < vectorSize; j++) { temp[j] = Item; } var mask = Avx2.LoadVector256(temp); var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); var areEqual = Avx2.CompareEqual(v, mask); accVector = Avx2.Subtract(accVector, areEqual); } } int result = 0; Avx2.Store(temp, accVector); for(int j = 0; j < vectorSize; j++) { result += temp[j]; } for(; i < array.Length; i++) { if (array[i] == Item) { result++; } } return result; }
Os resultados da execução do benchmark no meu computador:
Os métodos de vetores e intrínsecos coincidem completamente na lógica, mas diferem na implementação de operações específicas. A ideia é a seguinte:
- criar vetor de máscara no qual um número necessário é armazenado em cada elemento;
- carregue a parte de uma matriz no vetor v e compare essa parte com uma máscara. Como resultado, todos os bits serão definidos em elementos iguais de areEqual. Como areEqual é uma matriz de números inteiros, se definirmos todos os bits de um elemento, obteremos -1 nesse elemento ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
- subtrair areEqual vector de accVector. Então, accVector manterá a contagem de quantas vezes o elemento do item ocorreu em todos os v vetores para cada posição (menos por menos é um mais).
Todo o código do artigo está no GitHub .
Conclusão
Descrevi apenas uma pequena parte dos recursos do .NET para vetorização de computação. Para ver a lista atualizada completa de todas as intrínsecas disponíveis no .NET Core em x86, vá para o código-fonte . É conveniente que o resumo de cada intrínseco nos arquivos C # contenha seu nome no mundo C. Isso ajuda a entender o objetivo deste intrínseco e a transferência dos algoritmos C ++ / C existentes para o .NET. A documentação do System.Numerics.Vector está disponível no msdn .
Eu acho que o .NET tem uma grande vantagem sobre o C ++. Como a compilação JIT já ocorre em uma máquina cliente, um compilador pode otimizar o código para um processador de cliente específico, oferecendo desempenho máximo. Ao mesmo tempo, um programador pode permanecer em um idioma e nas mesmas tecnologias para escrever código rápido.