Recentemente, eu respondi a uma pergunta sobre a otimização de um provável método paralelizável para gerar toda permutação de números de base arbitrários. Eu postei uma resposta semelhante àImplementação paralela e ruim lista de bloqueio de código, e alguém quase imediatamente apontou isso:

Isso garante que você tenha um compartilhamento falso e provavelmente será muitas vezes mais lento. (crédito paragjvdkamp)

e eles estavam certos, foimorte lento. Dito isto, pesquisei o tópico e encontrei algumasmaterial interessante e sugestões (apenas na revista MSDN arquivada,Assuntos do .NET: compartilhamento falso) para combatê-lo. Se eu entendi direito, quando os threads acessam a memória contígua (por exemplo, a matriz que provavelmente está apoiando essaConcurrentStack), o compartilhamento falso provavelmente ocorre.

Para código abaixo da regra horizontal, umBytes é:

struct Bytes {
  public byte A; public byte B; public byte C; public byte D;
  public byte E; public byte F; public byte G; public byte H;
}

Para meus próprios testes, eu queria obter uma versão paralela dessa execução e ser genuinamente mais rápida, então criei um exemplo simples com base no código original.6 Comolimits[0] foi uma escolha preguiçosa da minha parte - meu computador tem 6 núcleos.

Bloco de rosca única Tempo médio de execução: 10s0059ms

  var data = new List<Bytes>();
  var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

  for (byte a = 0; a < limits[0]; a++)
  for (byte b = 0; b < limits[1]; b++)
  for (byte c = 0; c < limits[2]; c++)
  for (byte d = 0; d < limits[3]; d++)
  for (byte e = 0; e < limits[4]; e++)
  for (byte f = 0; f < limits[5]; f++)
  for (byte g = 0; g < limits[6]; g++)
  for (byte h = 0; h < limits[7]; h++)
    data.Add(new Bytes {
      A = a, B = b, C = c, D = d, 
      E = e, F = f, G = g, H = h
    });

Implementação paralela e ruim Tempo médio de execução: 81s729ms, ~ 8700 contenções

  var data = new ConcurrentStack<Bytes>();
  var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

  Parallel.For(0, limits[0], (a) => {
    for (byte b = 0; b < limits[1]; b++)
    for (byte c = 0; c < limits[2]; c++)
    for (byte d = 0; d < limits[3]; d++)
    for (byte e = 0; e < limits[4]; e++)
    for (byte f = 0; f < limits[5]; f++)
    for (byte g = 0; g < limits[6]; g++)
    for (byte h = 0; h < limits[7]; h++)
      data.Push(new Bytes {
        A = (byte)a,B = b,C = c,D = d,
        E = e,F = f,G = g,H = h
      });
  }); 

Paralelamente, ?? implementação Tempo médio de execução: 5s833ms, 92 contenções

  var data = new ConcurrentStack<List<Bytes>>();
  var limits = new byte[] { 6, 16, 16, 16, 32, 8, 8, 8 };

  Parallel.For (0, limits[0], () => new List<Bytes>(), 
    (a, loop, localList) => { 
      for (byte b = 0; b < limits[1]; b++)
      for (byte c = 0; c < limits[2]; c++)
      for (byte d = 0; d < limits[3]; d++)
      for (byte e = 0; e < limits[4]; e++)
      for (byte f = 0; f < limits[5]; f++)
      for (byte g = 0; g < limits[6]; g++)
      for (byte h = 0; h < limits[7]; h++)
        localList.Add(new Bytes {
          A = (byte)a, B = b, C = c, D = d,
          E = e, F = f, G = g, H = h
        });
      return localList;
  }, x => {
    data.Push(x);
  });

Fico feliz por ter recebido uma implementação mais rápida que a versão single threaded. Eu esperava um resultado próximo de 10s / 6, ou cerca de 1,6 segundos, mas essa é provavelmente uma expectativa ingênua.

Minha pergunta épara a implementação paralelizada que é realmente mais rápida que a versão de thread único, existem otimizações adicionais que podem ser aplicadas à operação? Estou me perguntando sobre otimizações relacionadas à paralelização, não melhorias no algoritmo usado para calcular os valores. Especificamente:

Conheço a otimização para armazenar e preencher como umstruct ao invés debyte[], mas não está relacionado à paralelização (ou é?)Eu sei que um valor desejado pode ser avaliado preguiçosamente com um somador de transporte de ondulação, mas o mesmo que ostruct otimização.