Por que memcpy () e memmove () são mais rápidos do que incrementos de ponteiro?

Estou copiando N bytes de pSrcpara pDest. Isso pode ser feito em um único loop:

for (int i = 0; i < N; i++)
    *pDest++ = *pSrc++

Por que isso é mais lento do que memcpyou memmove? Que truques eles usam para acelerar?

Como o memcpy usa ponteiros de palavras em vez de ponteiros de bytes, também as implementações de memcpy são frequentemente escritas com SIMD instruções o que torna possível embaralhar 128 bits por vez.

As instruções SIMD são instruções de montagem que podem realizar a mesma operação em cada elemento em um vetor de até 16 bytes de comprimento. Isso inclui instruções para carregar e armazenar.

As rotinas de cópia de memória podem ser muito mais complicadas e rápidas do que uma simples cópia de memória por meio de indicadores como:

void simple_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;
  for (int i = 0; i < bytes; ++i)
    *b_dst++ = *b_src++;
}

Melhorias

A primeira melhoria que se pode fazer é alinhar um dos ponteiros em um limite de palavra (por palavra, quero dizer tamanho inteiro nativo, geralmente 32 bits / 4 bytes, mas pode ser 64 bits / 8 bytes em arquiteturas mais recentes) e usar o movimento de tamanho de palavra / copiar instruções. Isso requer o uso de uma cópia de byte a byte até que um ponteiro esteja alinhado.

void aligned_memory_copy(void* dst, void* src, unsigned int bytes)
{
  unsigned char* b_dst = (unsigned char*)dst;
  unsigned char* b_src = (unsigned char*)src;

  // Copy bytes to align source pointer
  while ((b_src & 0x3) != 0)
  {
    *b_dst++ = *b_src++;
    bytes--;
  }

  unsigned int* w_dst = (unsigned int*)b_dst;
  unsigned int* w_src = (unsigned int*)b_src;
  while (bytes >= 4)
  {
    *w_dst++ = *w_src++;
    bytes -= 4;
  }

  // Copy trailing bytes
  if (bytes > 0)
  {
    b_dst = (unsigned char*)w_dst;
    b_src = (unsigned char*)w_src;
    while (bytes > 0)
    {
      *b_dst++ = *b_src++;
      bytes--;
    }
  }
}

Diferentes arquiteturas terão um desempenho diferente com base no alinhamento apropriado da origem ou do ponteiro de destino. Por exemplo, em um processador XScale, obtive melhor desempenho alinhando o ponteiro de destino em vez do ponteiro de origem.

Para melhorar ainda mais o desempenho, pode ser feito algum desenrolamento de loop, de modo que mais registros do processador sejam carregados com dados e isso significa que as instruções de carga / armazenamento podem ser intercaladas e ter sua latência oculta por instruções adicionais (como contagem de loop, etc.). O benefício que isso traz varia um pouco de acordo com o processador, uma vez que as latências de instrução de carga / armazenamento podem ser bem diferentes.

Nesse estágio, o código acaba sendo escrito em Assembly em vez de C (ou C ++), pois você precisa colocar manualmente as instruções de carregamento e armazenamento para obter o máximo benefício de ocultação de latência e rendimento.

Geralmente, toda uma linha de cache de dados deve ser copiada em uma iteração do loop desenrolado.

O que me leva à próxima melhoria, adicionando pré-busca. Estas são instruções especiais que dizem ao sistema de cache do processador para carregar partes específicas da memória em seu cache. Como existe um atraso entre a emissão da instrução e o preenchimento da linha do cache, as instruções precisam ser colocadas de forma que os dados estejam disponíveis no momento exato em que devem ser copiados, e não antes ou depois.

Isso significa colocar as instruções de pré-busca no início da função, bem como dentro do loop de cópia principal. Com as instruções de pré-busca no meio do loop de cópia, busca dados que serão copiados em várias iterações.

Não me lembro, mas também pode ser útil buscar antecipadamente os endereços de destino e também os de origem.

Fatores

Os principais fatores que afetam a rapidez com que a memória pode ser copiada são:

• A latência entre o processador, seus caches e a memória principal.
• O tamanho e a estrutura das linhas de cache do processador.
• As instruções para mover / copiar a memória do processador (latência, taxa de transferência, tamanho do registro, etc.).

Portanto, se você quiser escrever uma rotina eficiente e rápida para lidar com a memória, precisará saber bastante sobre o processador e a arquitetura para os quais está escrevendo. Basta dizer que, a menos que você esteja escrevendo em alguma plataforma embarcada, seria muito mais fácil usar apenas as rotinas de cópia de memória integradas.

memcpypode copiar mais de um byte de uma vez, dependendo da arquitetura do computador. A maioria dos computadores modernos pode trabalhar com 32 bits ou mais em uma única instrução de processador.

De um exemplo de implementação :

    00026 * Para cópias rápidas, otimize o caso comum em que ambos os indicadores
    00027 * e o comprimento são alinhados por palavra e, em vez disso, copiam palavra por vez
    00028 * de byte por vez. Caso contrário, copie por bytes.

Você pode implementar memcpy()usando qualquer uma das seguintes técnicas, algumas dependentes de sua arquitetura para ganhos de desempenho, e todas serão muito mais rápidas do que seu código:

1. Use unidades maiores, como palavras de 32 bits em vez de bytes. Você também pode (ou pode ter que) lidar com o alinhamento aqui também. Você não pode ler / escrever uma palavra de 32 bits em um local de memória estranho, por exemplo, em algumas plataformas, e em outras plataformas você paga uma penalidade enorme de desempenho. Para corrigir isso, o endereço deve ser uma unidade divisível por 4. Você pode levar isso para 64 bits para CPUs de 64 bits, ou até mais usando instruções SIMD (instrução única, dados múltiplos) ( MMX , SSE , etc.)

2. Você pode usar instruções especiais da CPU que seu compilador pode não conseguir otimizar a partir de C. Por exemplo, em um 80386, você pode usar a instrução de prefixo "rep" + instrução "movsb" para mover N bytes ditados pela colocação de N na contagem registro. Bons compiladores farão isso por você, mas você pode estar em uma plataforma que carece de um bom compilador. Observe que esse exemplo tende a ser uma demonstração ruim de velocidade, mas combinado com alinhamento + instruções de unidade maiores, pode ser mais rápido do que quase tudo em certas CPUs.

3. Loop unrolling - branches pode ser bastante caro em algumas CPUs, então o desdobramento dos loops pode diminuir o número de branches. Essa também é uma boa técnica para combinar com instruções SIMD e unidades de tamanho muito grande.

Por exemplo, http://www.agner.org/optimize/#asmlib tem uma memcpyimplementação que supera a maioria (por uma quantidade muito pequena). Se você ler o código-fonte, ele estará cheio de toneladas de código assembly embutido que extrai todas as três técnicas acima, escolhendo qual dessas técnicas com base em qual CPU você está executando.

Observe que também existem otimizações semelhantes que podem ser feitas para localizar bytes em um buffer. strchr()e amigos muitas vezes passarão mais rápido do que seu equivalente enrolado à mão. Isso é especialmente verdadeiro para .NET e Java . Por exemplo, em .NET, o embutido String.IndexOf()é muito mais rápido do que até mesmo uma pesquisa de string Boyer-Moore , porque usa as técnicas de otimização acima.

Resposta curta:

• preenchimento de cache
• transferências de tamanho de palavras em vez de bytes, quando possível
• Magia SIMD

Não sei se é realmente usado em qualquer implementação do mundo real do memcpy, mas acho que o Dispositivo de Duff merece uma menção aqui.

Da Wikipedia :

send(to, from, count)
register short *to, *from;
register count;
{
        register n = (count + 7) / 8;
        switch(count % 8) {
        case 0:      do {     *to = *from++;
        case 7:              *to = *from++;
        case 6:              *to = *from++;
        case 5:              *to = *from++;
        case 4:              *to = *from++;
        case 3:              *to = *from++;
        case 2:              *to = *from++;
        case 1:              *to = *from++;
                } while(--n > 0);
        }
}

Observe que o acima não é um, memcpypois deliberadamente não incrementa o toponteiro. Ele implementa uma operação ligeiramente diferente: a gravação em um registro mapeado na memória. Veja o artigo da Wikipedia para detalhes.

Como outros, dizem que o memcpy copia mais do que blocos de 1 byte. Copiar em blocos de tamanho de palavra é muito mais rápido. No entanto, a maioria das implementações dá um passo adiante e executa várias instruções MOV (palavra) antes de fazer o loop. A vantagem de copiar, digamos, 8 blocos de palavras por loop é que o próprio loop é caro. Essa técnica reduz o número de ramificações condicionais por um fator de 8, otimizando a cópia para blocos gigantes.

As respostas são grandes, mas se você ainda deseja implementar um rápido memcpymesmo, há um post interessante sobre memcpy rápido, memcpy rápido no C .

void *memcpy(void* dest, const void* src, size_t count)
{
    char* dst8 = (char*)dest;
    char* src8 = (char*)src;

    if (count & 1) {
        dst8[0] = src8[0];
        dst8 += 1;
        src8 += 1;
    }

    count /= 2;
    while (count--) {
        dst8[0] = src8[0];
        dst8[1] = src8[1];

        dst8 += 2;
        src8 += 2;
    }
    return dest;
}

Ainda, pode ser melhor com a otimização de acessos à memória.

Porque, como muitas rotinas de biblioteca, ela foi otimizada para a arquitetura na qual você está executando. Outros postaram várias técnicas que podem ser usadas.

Se tiver escolha, use rotinas de biblioteca em vez de criar suas próprias rotinas. Esta é uma variação do DRY que chamo de DRO (Don't Repeat Others). Além disso, é menos provável que as rotinas da biblioteca estejam erradas do que a sua própria implementação.

Já vi verificadores de acesso à memória reclamarem de leituras fora dos limites na memória ou nos buffers de string que não eram múltiplos do tamanho da palavra. Isso é resultado da otimização que está sendo usada.

Você pode observar a implementação do MacOS de memset, memcpy e memmove.

No momento da inicialização, o sistema operacional determina em qual processador está sendo executado. Ele foi construído em um código especificamente otimizado para cada processador suportado e, no momento da inicialização, armazena uma instrução jmp para o código correto em um local fixo de leitura / somente.

As implementações C memset, memcpy e memmove são apenas um salto para esse local fixo.

As implementações usam código diferente dependendo do alinhamento da origem e do destino para memcpy e memmove. Eles obviamente usam todos os recursos vetoriais disponíveis. Eles também usam variantes sem armazenamento em cache quando você copia grandes quantidades de dados e têm instruções para minimizar as esperas por tabelas de página. Não é apenas código assembler, é código assembler escrito por alguém com um conhecimento extremamente bom de cada arquitetura de processador.

A Intel também adicionou instruções de montagem que podem tornar as operações de string mais rápidas. Por exemplo, com uma instrução para suportar strstr que faz comparações de 256 bytes em um ciclo.