Eu estava olhando o strlencódigo aqui e queria saber se as otimizações usadas no código são realmente necessárias? Por exemplo, por que algo como o seguinte não seria igualmente bom ou melhor?

unsigned long strlen(char s[]) {
    unsigned long i;
    for (i = 0; s[i] != '\0'; i++)
        continue;
    return i;
}

O código mais simples não é melhor e / ou mais fácil para o compilador otimizar?

O código da strlenpágina por trás do link é semelhante a este:

/* Copyright (C) 1991, 1993, 1997, 2000, 2003 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Written by Torbjorn Granlund ([email protected]),
   with help from Dan Sahlin ([email protected]);
   commentary by Jim Blandy ([email protected]).

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

#include <string.h>
#include <stdlib.h>

#undef strlen

/* Return the length of the null-terminated string STR.  Scan for
   the null terminator quickly by testing four bytes at a time.  */
size_t
strlen (str)
     const char *str;
{
  const char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, magic_bits, himagic, lomagic;

  /* Handle the first few characters by reading one character at a time.
     Do this until CHAR_PTR is aligned on a longword boundary.  */
  for (char_ptr = str; ((unsigned long int) char_ptr
            & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == '\0')
      return char_ptr - str;

  /* All these elucidatory comments refer to 4-byte longwords,
     but the theory applies equally well to 8-byte longwords.  */

  longword_ptr = (unsigned long int *) char_ptr;

  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
     the "holes."  Note that there is a hole just to the left of
     each byte, with an extra at the end:

     bits:  01111110 11111110 11111110 11111111
     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

     The 1-bits make sure that carries propagate to the next 0-bit.
     The 0-bits provide holes for carries to fall into.  */
  magic_bits = 0x7efefeffL;
  himagic = 0x80808080L;
  lomagic = 0x01010101L;
  if (sizeof (longword) > 4)
    {
      /* 64-bit version of the magic.  */
      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
      magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL;
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    abort ();

  /* Instead of the traditional loop which tests each character,
     we will test a longword at a time.  The tricky part is testing
     if *any of the four* bytes in the longword in question are zero.  */
  for (;;)
    {
      /* We tentatively exit the loop if adding MAGIC_BITS to
     LONGWORD fails to change any of the hole bits of LONGWORD.

     1) Is this safe?  Will it catch all the zero bytes?
     Suppose there is a byte with all zeros.  Any carry bits
     propagating from its left will fall into the hole at its
     least significant bit and stop.  Since there will be no
     carry from its most significant bit, the LSB of the
     byte to the left will be unchanged, and the zero will be
     detected.

     2) Is this worthwhile?  Will it ignore everything except
     zero bytes?  Suppose every byte of LONGWORD has a bit set
     somewhere.  There will be a carry into bit 8.  If bit 8
     is set, this will carry into bit 16.  If bit 8 is clear,
     one of bits 9-15 must be set, so there will be a carry
     into bit 16.  Similarly, there will be a carry into bit
     24.  If one of bits 24-30 is set, there will be a carry
     into bit 31, so all of the hole bits will be changed.

     The one misfire occurs when bits 24-30 are clear and bit
     31 is set; in this case, the hole at bit 31 is not
     changed.  If we had access to the processor carry flag,
     we could close this loophole by putting the fourth hole
     at bit 32!

     So it ignores everything except 128's, when they're aligned
     properly.  */

      longword = *longword_ptr++;

      if (
#if 0
      /* Add MAGIC_BITS to LONGWORD.  */
      (((longword + magic_bits)

        /* Set those bits that were unchanged by the addition.  */
        ^ ~longword)

       /* Look at only the hole bits.  If any of the hole bits
          are unchanged, most likely one of the bytes was a
          zero.  */
       & ~magic_bits)
#else
      ((longword - lomagic) & himagic)
#endif
      != 0)
    {
      /* Which of the bytes was the zero?  If none of them were, it was
         a misfire; continue the search.  */

      const char *cp = (const char *) (longword_ptr - 1);

      if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
        }
    }
    }
}
libc_hidden_builtin_def (strlen)

Por que esta versão é executada rapidamente?

Não está fazendo muito trabalho desnecessário?

Você não precisa e nunca deve escrever códigos como esse - especialmente se você não é um compilador C / fornecedor de biblioteca padrão. É um código usado para implementar strlencom alguns hacks e suposições de velocidade muito questionáveis ​​(que não são testados com afirmações ou mencionados nos comentários):

• unsigned long tem 4 ou 8 bytes
• bytes são 8 bits
• um ponteiro pode ser convertido unsigned long longe nãouintptr_t
• é possível alinhar o ponteiro simplesmente verificando se os 2 ou 3 bits de ordem mais baixa são zero
• pode-se acessar uma string como unsigned longs
• pode-se ler além do final da matriz, sem efeitos negativos.

Além disso, um bom compilador pode até substituir o código escrito como

size_t stupid_strlen(const char s[]) {
    size_t i;
    for (i=0; s[i] != '\0'; i++)
        ;
    return i;
}

(observe que ele deve ser do tipo compatível size_t) com uma versão embutida do compilador embutida strlenou vetorizar o código; mas é improvável que um compilador seja capaz de otimizar a versão complexa.

A strlenfunção é descrita por C11 7.24.6.3 como:

Descrição

2. A strlenfunção calcula o comprimento da string apontada por s.

Devoluções

3. A strlenfunção retorna o número de caracteres que precedem o caractere nulo final.

Agora, se a sequência apontada por sestava em uma matriz de caracteres apenas o tempo suficiente para conter a sequência e a NUL final, o comportamento será indefinido se acessarmos a sequência além do terminador nulo, por exemplo, em

char *str = "hello world";  // or
char array[] = "hello world";

Então, realmente, a única maneira de o C totalmente portátil / compatível com os padrões implementá-lo corretamente é o modo como está escrito em sua pergunta , exceto por transformações triviais - você pode fingir ser mais rápido desenrolando o loop etc., mas ainda precisa ser feito um byte de cada vez.

(Como os comentaristas apontaram, quando a portabilidade estrita é um fardo demais, tirar proveito de suposições razoáveis ​​ou seguras conhecidas nem sempre é uma coisa ruim. Especialmente no código que faz parte de uma implementação C específica. Mas você precisa entender o regras antes de saber como / quando você pode dobrá-las.)

A strlenimplementação vinculada primeiro verifica os bytes individualmente até o ponteiro apontar para o limite natural de alinhamento de 4 ou 8 bytes unsigned long. O padrão C diz que o acesso a um ponteiro que não está alinhado corretamente tem um comportamento indefinido , portanto, isso absolutamente deve ser feito para que o próximo truque sujo seja ainda mais sujo. (Na prática, em algumas arquiteturas de CPU que não sejam x86, uma palavra desalinhada ou carregamento de palavras duplas falhará. C não é uma linguagem assembly portátil, mas esse código está usando dessa maneira). É também o que possibilita a leitura do final de um objeto sem o risco de falhas nas implementações em que a proteção de memória funciona em blocos alinhados (por exemplo, páginas de memória virtual 4kiB).

Agora vem a parte suja: o código de quebra a promessa e lê 4 ou 8 bytes de 8 bits de cada vez (a long int), e usa um truque pouco com adição não assinado para descobrir rapidamente se não houvesse nenhum zero bytes dentro os 4 ou 8 bytes - usa um número especialmente criado para que o bit de transporte mude os bits capturados por uma máscara de bit. Em essência, isso descobriria se qualquer um dos 4 ou 8 bytes da máscara é zero supostamente mais rápido do que o loop de cada um desses bytes. Finalmente, há um loop no final para descobrir qual byte foi o primeiro zero, se houver, e para retornar o resultado.

O maior problema é que, em sizeof (unsigned long) - 1alguns sizeof (unsigned long)casos, ele passará do final da string - somente se o byte nulo estiver no último byte acessado (ou seja, no little-endian o mais significativo e no big-endian o menos significativo) , ele não acessa a matriz fora dos limites!

O código, mesmo usado para implementar strlenem uma biblioteca padrão C, é um código incorreto . Ele possui vários aspectos definidos e indefinidos na implementação e não deve ser usado em nenhum lugar, em vez do fornecido pelo sistema strlen- renomeei a função para the_strlenaqui e adicionei o seguinte main:

int main(void) {
    char buf[12];
    printf("%zu\n", the_strlen(fgets(buf, 12, stdin)));
}

O buffer é cuidadosamente dimensionado para que possa conter exatamente a hello worldstring e o terminador. No entanto, no meu processador de 64 bits, unsigned longsão 8 bytes; portanto, o acesso à última parte excederia esse buffer.

Se eu agora compilar com -fsanitize=undefinede -fsanitize=addresse executar o programa resultante, eu recebo:

% ./a.out
hello world
=================================================================
==8355==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffffe63a3f8 at pc 0x55fbec46ab6c bp 0x7ffffe63a350 sp 0x7ffffe63a340
READ of size 8 at 0x7ffffe63a3f8 thread T0
    #0 0x55fbec46ab6b in the_strlen (.../a.out+0x1b6b)
    #1 0x55fbec46b139 in main (.../a.out+0x2139)
    #2 0x7f4f0848fb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #3 0x55fbec46a949 in _start (.../a.out+0x1949)

Address 0x7ffffe63a3f8 is located in stack of thread T0 at offset 40 in frame
    #0 0x55fbec46b07c in main (.../a.out+0x207c)

  This frame has 1 object(s):
    [32, 44) 'buf' <== Memory access at offset 40 partially overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow (.../a.out+0x1b6b) in the_strlen
Shadow bytes around the buggy address:
  0x10007fcbf420: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf430: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf440: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf450: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10007fcbf470: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00[04]
  0x10007fcbf480: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==8355==ABORTING

isto é, coisas ruins aconteceram.

Houve muitos palpites (um pouco ou totalmente) errados nos comentários sobre alguns detalhes / antecedentes para isso.

Você está olhando para a implementação otimizada de fallback C otimizada da glibc. (Para ISAs que não possuem uma implementação ASM escrita à mão) . Ou uma versão antiga desse código, que ainda está na árvore de fontes glibc. https://code.woboq.org/userspace/glibc/string/strlen.c.html é um navegador de código baseado na árvore glibc git atual. Aparentemente, ele ainda é usado por alguns destinos principais da glibc, incluindo o MIPS. (Obrigado @zwol).

Em ISAs populares como x86 e ARM, o glibc usa asm escrito à mão

Portanto, o incentivo para alterar qualquer coisa sobre esse código é menor do que você imagina.

Esse código de bithack ( https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord ) não é o que realmente é executado no seu servidor / desktop / laptop / smartphone. É melhor do que um loop ingênuo de bytes por vez, mas mesmo esse bithack é muito ruim comparado ao asm eficiente para CPUs modernas (especialmente x86, em que o AVX2 SIMD permite verificar 32 bytes com algumas instruções, permitindo de 32 a 64 bytes por relógio circule no loop principal se os dados estiverem quentes no cache L1d em CPUs modernas com carga vetorial 2 / clock e taxa de transferência de ALU, ou seja, para cadeias de tamanho médio onde a sobrecarga de inicialização não domina.)

O glibc usa truques de vinculação dinâmica para resolver strlenpara uma versão ideal para sua CPU, portanto, mesmo no x86 há uma versão SSE2 (vetores de 16 bytes, linha de base para x86-64) e uma versão AVX2 (vetores de 32 bytes).

O x86 possui uma transferência de dados eficiente entre registros vetoriais e de uso geral, o que o torna excepcionalmente (?) bom para usar o SIMD para acelerar funções em cadeias de comprimento implícito nas quais o controle de loop depende dos dados. pcmpeqb/ pmovmskbpossibilita testar 16 bytes separados por vez.

O glibc possui uma versão do AArch64 como essa usando o AdvSIMD e uma versão para as CPUs do AArch64 em que os registradores vector-> GP interrompem o pipeline; portanto, ele realmente usa esse bithack . Mas usa contagem de zeros à esquerda para encontrar o byte-dentro-do registro, uma vez atingido, e tira proveito dos acessos desalinhados eficientes do AArch64 após a verificação do cruzamento de páginas.

Também relacionado: Por que esse código é 6.5x mais lento com as otimizações ativadas? tem mais alguns detalhes sobre o que é mais rápido ou mais lento no x86 asm, strlencom um buffer grande e uma implementação simples do asm que pode ser boa para o gcc saber como incorporar. (Algumas versões do gcc são improdutivamente inline, o rep scasbque é muito lento, ou um bithack de 4 bytes por vez como este. Portanto, a receita inline-strlen do GCC precisa ser atualizada ou desativada.)

O Asm não possui "comportamento indefinido" no estilo C ; é seguro acessar os bytes da memória da maneira que desejar e uma carga alinhada que inclua os bytes válidos não pode causar falhas. A proteção de memória ocorre com granularidade de página alinhada; acessos alinhados mais estreitos do que isso não podem cruzar o limite da página É seguro ler além do final de um buffer na mesma página em x86 e x64? O mesmo raciocínio se aplica ao código de máquina que esse C hack obtém compiladores para criar para uma implementação não-inline autônoma dessa função.

Quando um compilador emite código para chamar uma função não-inline desconhecida, ele deve assumir que a função modifica todas / todas as variáveis ​​globais e qualquer memória para a qual possa ter um ponteiro. ou seja, tudo, exceto os locais que não tiveram escape de endereço, deve estar sincronizado na memória durante a chamada. Isso se aplica a funções escritas em asm, obviamente, mas também a funções de biblioteca. Se você não ativar a otimização do tempo do link, ela se aplicará a unidades de tradução separadas (arquivos de origem).

Por que isso é seguro como parte da glibc, mas não o contrário.

O fator mais importante é que isso strlennão pode ser incorporado a mais nada. Não é seguro para isso; ele contém UB com alias estrito (leitura de chardados por meio de um unsigned long*). char*é permitido alias qualquer outra coisa, mas o inverso não é verdadeiro .

Esta é uma função de biblioteca para uma biblioteca compilada antecipadamente (glibc). Ele não será incorporado com a otimização do tempo do link nos chamadores. Isso significa que apenas é necessário compilar o código de máquina seguro para uma versão independente do strlen. Não precisa ser portátil / seguro C.

A biblioteca GNU C precisa compilar apenas com o GCC. Aparentemente, não há suporte para compilá-lo com clang ou ICC, mesmo que eles suportem extensões GNU. O GCC é um compilador antecipado que transforma um arquivo de origem C em um arquivo de objeto de código de máquina. Não é um intérprete; portanto, a menos que seja incorporado no tempo de compilação, os bytes na memória são apenas bytes na memória. ou seja, UB com alias estrito não é perigoso quando os acessos com tipos diferentes ocorrem em funções diferentes que não se alinham.

Lembre-se de que strleno comportamento é definido pelo padrão ISO C. Esse nome da função especificamente faz parte da implementação. Compiladores como o GCC até tratam o nome como uma função interna, a menos que você o use -fno-builtin-strlen, portanto strlen("foo")pode ser uma constante em tempo de compilação 3. A definição na biblioteca é usada apenas quando o gcc decide realmente emitir uma chamada para ela em vez de incluir sua própria receita ou algo assim.

Quando o UB não está visível para o compilador no momento da compilação, você obtém um código de máquina são. O código da máquina precisa funcionar para o caso no-UB e, mesmo que você queira , não há como o ASM detectar quais tipos o chamador usou para colocar dados na memória apontada.

O Glibc é compilado em uma biblioteca estática ou dinâmica autônoma que não pode ser alinhada com a otimização do tempo do link. Os scripts de construção da glibc não criam bibliotecas estáticas "gordas" que contêm código de máquina + representação interna do gcc GIMPLE para otimização do tempo de link ao incorporar em um programa. (ou seja libc.a, não participará da -fltootimização do tempo do link no programa principal.) Construir o glibc dessa maneira seria potencialmente inseguro para os alvos que realmente o usam.c .

Na verdade, como comentários @zwol, LTO não pode ser usado na construção de glibc si , por causa do código "frágil" como este, que poderia quebrar se inlining entre arquivos de origem glibc era possível. (Existem alguns usos internos de strlen, por exemplo, talvez como parte da printfimplementação)

Isso strlenfaz algumas suposições:

• CHAR_BITé um múltiplo de 8 . Verdadeiro em todos os sistemas GNU. O POSIX 2001 ainda garante CHAR_BIT == 8. (Isso parece seguro para sistemas com CHAR_BIT= 16ou 32, como alguns DSPs; o loop de prólogo desalinhado sempre executará 0 iterações se sizeof(long) = sizeof(char) = 1porque todo ponteiro está sempre alinhado e p & sizeof(long)-1sempre é zero.) Mas se você tivesse um conjunto de caracteres não ASCII em que caracteres são 9 ou 12 bits de largura, 0x8080...é o padrão errado.
• (talvez) unsigned longtem 4 ou 8 bytes. Ou talvez funcione para qualquer tamanho de unsigned longaté 8, e usa um assert()para verificar isso.

Esses dois não são possíveis UB, eles são apenas não portáveis ​​para algumas implementações em C. Esse código é (ou fazia parte ) da implementação C nas plataformas em que ele funciona, então tudo bem.

A próxima suposição é C C ​​potencial:

• Uma carga alinhada que contém bytes válidos não pode falhar e é segura desde que você ignore os bytes fora do objeto que você realmente deseja. (É verdade em todos os sistemas GNU e em todas as CPUs normais porque a proteção de memória ocorre com granularidade de página alinhada. É seguro ler além do final de um buffer na mesma página em x86 e x64? Seguro em C quando o UB não é visível no momento da compilação. Sem incluir, é o caso aqui. O compilador não pode provar que a leitura após a primeira 0é UB; pode ser uma char[]matriz C contendo, {1,2,0,3}por exemplo)

Esse último ponto é o que torna seguro ler além do final de um objeto C aqui. Isso é praticamente seguro, mesmo quando se alinha com os compiladores atuais, porque acho que atualmente eles não tratam que implicar um caminho de execução é inacessível. De qualquer forma, o aliasing estrito já é um obstáculo se você deixar isso em linha.

Em seguida, você terá problemas como a antiga memcpy macro CPP insegura do kernel do Linux que usa a conversão de ponteiros para unsigned long( gcc, alias estrito e histórias de horror ).

Isso strlenremonta à época em que você podia se dar bem com coisas assim em geral ; costumava ser bastante seguro sem a ressalva "somente quando não embutido" antes do GCC3.

UB que só é visível quando se olha através dos limites de chamada / retenção não pode nos prejudicar. (por exemplo, chamando isso em a em char buf[]vez de em uma matriz de unsigned long[]conversão para a const char*). Uma vez que o código da máquina está definido, ele está lidando com bytes na memória. Uma chamada de função não em linha deve assumir que o receptor lê toda / qualquer memória.

Escrevendo isso com segurança, sem UB com alias estrito

O atributo de tipo GCCmay_alias fornece a um tipo o mesmo tratamento de alias-everything que char*. (Sugerido por @KonradBorowsk). Atualmente, os cabeçalhos do GCC o usam para tipos de vetores SIMD x86 como __m128ivocê sempre pode fazer com segurança _mm_loadu_si128( (__m128i*)foo ). (Consulte `reinterpret_cast`ing entre o ponteiro do vetor de hardware e o tipo correspondente um comportamento indefinido? Para obter mais detalhes sobre o que isso faz e o que não significa.)

strlen(const char *char_ptr)
{
  typedef unsigned long __attribute__((may_alias)) aliasing_ulong;

  aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;
  for (;;) {
     unsigned long ulong = *longword_ptr++;  // can safely alias anything
     ...
  }
}

Você também pode usar aligned(1)para expressar um tipo com alignof(T) = 1.
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;

É uma maneira portátil de expressar uma carga de aliasing na ISOmemcpy , com a qual os compiladores modernos sabem alinhar como uma única instrução de carga. por exemplo

   unsigned long longword;
   memcpy(&longword, char_ptr, sizeof(longword));
   char_ptr += sizeof(longword);

Isso também funciona para cargas desalinhadas porque memcpyfunciona como se por charum acesso de cada vez. Mas, na prática, os compiladores modernos entendem memcpymuito bem.

O perigo aqui é que, se o GCC não souber ao certo se char_ptrestá alinhado por palavras, não o incluirá em algumas plataformas que podem não suportar cargas desalinhadas no asm. por exemplo, MIPS antes do MIPS64r6 ou ARM mais antigo. Se você recebeu uma chamada de função real memcpyapenas para carregar uma palavra (e deixá-la em outra memória), isso seria um desastre. Às vezes, o GCC pode ver quando o código alinha um ponteiro. Ou após o loop char-a-time que atinge um limite ulongo, você pode usar
p = __builtin_assume_aligned(p, sizeof(unsigned long));

Isso não evita a possível UB de leitura após o objeto, mas com o GCC atual, isso não é perigoso na prática.

Por que a fonte C otimizada à mão é necessária: os compiladores atuais não são bons o suficiente

O ASM otimizado manualmente pode ser ainda melhor quando você deseja cada última gota de desempenho para uma função de biblioteca padrão amplamente usada. Especialmente para algo como memcpy, mas também strlen. Nesse caso, não seria muito mais fácil usar C com intrínsecos x86 para aproveitar o SSE2.

Mas aqui estamos falando de uma versão C ingênua versus bithack C sem nenhum recurso específico do ISA.

(Penso que podemos considerá-lo um dado strlenamplamente usado para fazê-lo funcionar o mais rápido possível, é importante. Portanto, a questão é se podemos obter código de máquina eficiente a partir de fontes mais simples. Não, não podemos.)

O GCC e o clang atuais não são capazes de auto-vetorizar loops nos quais a contagem da iteração não é conhecida antes da primeira iteração . (por exemplo, deve ser possível verificar se o loop executará pelo menos 16 iterações antes de executar a primeira iteração). compiladores.

Isso inclui loops de pesquisa ou qualquer outro loop com um dependente de dados if()breake um contador.

O ICC (compilador da Intel para x86) pode auto-vetorizar alguns loops de pesquisa, mas ainda faz ingênuo byte de cada vez para um C simples / ingênuo, strlencomo o libc do OpenBSD usa. ( Godbolt ). (Da resposta de @ Peske ).

Uma libc otimizada manualmente strlené necessária para o desempenho dos compiladores atuais . Ir 1 byte por vez (com desenrolar talvez 2 bytes por ciclo em CPUs superescalares) é patético quando a memória principal pode acompanhar cerca de 8 bytes por ciclo, e o cache L1d pode fornecer 16 a 64 por ciclo. (2x cargas de 32 bytes por ciclo nas modernas CPUs x86 tradicionais desde Haswell e Ryzen. Sem contar o AVX512, que pode reduzir a velocidade do relógio apenas para o uso de vetores de 512 bits; é por isso que a glibc provavelmente não tem pressa em adicionar uma versão do AVX512 . Embora com vectores de 256-bit, AVX512VL + BW mascarado comparar numa máscara e ktestou kortestpoderia fazer strlenmais HyperThreading amigável por redução dos seus UOPs / iteração.)

Estou incluindo non-x86 aqui, esses são os "16 bytes". por exemplo, a maioria das CPUs AArch64 pode fazer pelo menos isso, eu acho, e algumas certamente mais. E alguns têm taxa de transferência de execução suficiente strlenpara acompanhar essa largura de banda de carga.

É claro que os programas que funcionam com cadeias grandes geralmente devem acompanhar os comprimentos para evitar a necessidade de refazer a localização frequente das cadeias C de comprimento implícito. Mas o desempenho de curto a médio porte ainda se beneficia de implementações escritas à mão, e tenho certeza que alguns programas acabam usando strlen em cadeias de comprimento médio.

É explicado nos comentários no arquivo que você vinculou:

 27 /* Return the length of the null-terminated string STR.  Scan for
 28    the null terminator quickly by testing four bytes at a time.  */

e:

 73   /* Instead of the traditional loop which tests each character,
 74      we will test a longword at a time.  The tricky part is testing
 75      if *any of the four* bytes in the longword in question are zero.  */

Em C, é possível argumentar em detalhes sobre a eficiência.

É menos eficiente iterar caracteres individuais procurando um nulo do que testar mais de um byte por vez, como esse código.

A complexidade adicional vem da necessidade de garantir que a sequência em teste esteja alinhada no lugar certo para começar a testar mais de um byte por vez (ao longo de um limite de palavras longas, conforme descrito nos comentários) e da necessidade de garantir que as suposições os tamanhos dos tipos de dados não são violados quando o código é usado.

Na maioria (mas não em todo) desenvolvimento de software moderno, essa atenção aos detalhes da eficiência não é necessária ou não vale o custo da complexidade extra do código.

Um lugar em que faz sentido prestar atenção à eficiência como esta está nas bibliotecas padrão, como no exemplo que você vinculou.

Se você quiser ler mais sobre limites de palavras, consulte esta pergunta e esta excelente página da Wikipedia

Além das ótimas respostas aqui, quero ressaltar que o código vinculado na pergunta é para a implementação do GNU no strlen .

A implementação do OpenBSDstrlen é muito semelhante ao código proposto na questão. A complexidade de uma implementação é determinada pelo autor.

...
#include <string.h>

size_t
strlen(const char *str)
{
    const char *s;

    for (s = str; *s; ++s)
        ;
    return (s - str);
}

DEF_STRONG(strlen);

EDIT : O código do OpenBSD que vinculei acima parece ser uma implementação de fallback para ISAs que não possuem uma implementação asm própria. Existem diferentes implementações strlendependendo da arquitetura. O código para amd64strlen , por exemplo, é asm. Semelhante aos comentários / resposta de PeterCordes, apontando que as implementações GNU sem fallback também são asm.

Em resumo, essa é uma otimização de desempenho que a biblioteca padrão pode fazer sabendo com qual compilador é compilado - você não deve escrever códigos como este, a menos que esteja escrevendo uma biblioteca padrão e possa depender de um compilador específico. Especificamente, ele está processando o número de bytes de alinhamento ao mesmo tempo - 4 em plataformas de 32 bits, 8 em plataformas de 64 bits. Isso significa que pode ser 4 ou 8 vezes mais rápido que a iteração de byte ingênua.

Para explicar como isso funciona, considere a seguinte imagem. Suponha aqui a plataforma de 32 bits (alinhamento de 4 bytes).

Digamos que a letra "H" de "Olá, mundo!" foi fornecida como argumento para strlen. Como a CPU gosta de alinhar as coisas na memória (idealmente,address % sizeof(size_t) == 0 ), os bytes antes do alinhamento são processados ​​byte a byte, usando o método lento.

Em seguida, para cada pedaço do tamanho de alinhamento, calculando (longbits - 0x01010101) & 0x80808080 != 0-o, verifica se algum dos bytes em um número inteiro é zero. Este cálculo tem um falso positivo quando pelo menos um dos bytes é maior que0x80 , mas na maioria das vezes deve funcionar. Se não for esse o caso (como na área amarela), o comprimento será aumentado pelo tamanho do alinhamento.

Se algum dos bytes de um número inteiro for zero (ou 0x81 ), a sequência será verificada byte a byte para determinar a posição de zero.

Isso pode fazer um acesso fora dos limites, no entanto, como está dentro de um alinhamento, é mais provável que não seja bom, as unidades de mapeamento de memória geralmente não têm precisão no nível de bytes.

Você deseja que o código seja correto, sustentável e rápido. Esses fatores têm importância diferente:

"correto" é absolutamente essencial.

"manutenível" depende de quanto você manterá o código: strlen é uma função da biblioteca Standard C há mais de 40 anos. Isso não vai mudar. A manutenção é, portanto, bastante sem importância - para esta função.

"Rápido": em muitos aplicativos, strcpy, strlen etc. usam uma quantidade significativa do tempo de execução. Para obter o mesmo ganho geral de velocidade que essa implementação complicada, mas não muito complicada, do strlen, aprimorando o compilador, seriam necessários esforços heróicos.

Ser rápido tem outra vantagem: quando os programadores descobrem que chamar "strlen" é o método mais rápido de medir o número de bytes em uma string, eles não ficam mais tentados a escrever seu próprio código para agilizar as coisas.

Portanto, para strlen, a velocidade é muito mais importante e a manutenção é muito menos importante do que para a maioria dos códigos que você escreverá.

Por que deve ser tão complicado? Digamos que você tenha uma sequência de 1.000 bytes. A implementação simples examinará 1.000 bytes. Uma implementação atual provavelmente examinaria palavras de 64 bits por vez, o que significa 125 palavras de 64 bits ou oito bytes. Pode até usar instruções vetoriais examinando, digamos, 32 bytes de cada vez, o que seria ainda mais complicado e ainda mais rápido. O uso de instruções vetoriais leva a um código um pouco mais complicado, mas bastante direto, verificar se um dos oito bytes em uma palavra de 64 bits é zero requer alguns truques inteligentes. Portanto, para cadeias médias a longas, esse código pode ser quatro vezes mais rápido. Para uma função tão importante quanto strlen, vale a pena escrever uma função mais complexa.

PS. O código não é muito portátil. Mas faz parte da biblioteca Standard C, que faz parte da implementação - não precisa ser portátil.

PPS. Alguém postou um exemplo em que uma ferramenta de depuração se queixava de acessar bytes após o final de uma string. Uma implementação pode ser projetada para garantir o seguinte: Se p for um ponteiro válido para um byte, qualquer acesso a um byte no mesmo bloco alinhado que seria um comportamento indefinido de acordo com o padrão C retornará um valor não especificado.

PPPS. A Intel adicionou instruções aos seus processadores posteriores que formam um bloco de construção para a função strstr () (localizando uma substring em uma string). A descrição deles é incompreensível, mas eles podem tornar essa função específica provavelmente 100 vezes mais rápida. (Basicamente, considerando uma matriz a contendo "Olá, mundo!" E uma matriz b começando com 16 bytes "HelloHelloHelloH" e contendo mais bytes, isso indica que a sequência a não ocorre em b antes do início no índice 15) .

Resumidamente: a verificação de uma sequência de bytes em bytes será potencialmente lenta em arquiteturas que podem buscar grandes quantidades de dados por vez.

Se a verificação de finalização nula puder ser feita com base em 32 ou 64 bits, isso reduzirá a quantidade de verificações que o compilador deve executar. É isso que o código vinculado tenta fazer, com um sistema específico em mente. Eles fazem suposições sobre endereçamento, alinhamento, uso de cache, configurações não padrão do compilador, etc.

Ler byte a byte, como no seu exemplo, seria uma abordagem sensata em uma CPU de 8 bits ou ao escrever uma biblioteca portátil escrita no padrão C.

Analisar as bibliotecas padrão C para aconselhar como escrever código rápido / bom não é uma boa ideia, porque será não portátil e dependerá de suposições não padrão ou comportamento mal definido. Se você é iniciante, a leitura desse código provavelmente será mais prejudicial do que educacional.

Uma coisa importante não mencionada pelas outras respostas é que a FSF é muito cautelosa ao garantir que o código proprietário não entre nos projetos GNU. Nos Padrões de Codificação GNU em Referindo-se a Programas Proprietários , há um aviso sobre a organização da sua implementação de uma maneira que não pode ser confundida com o código proprietário existente:

Em nenhuma circunstância, consulte o código-fonte Unix para ou durante o seu trabalho no GNU! (Ou para qualquer outro programa proprietário.)

Se você tem uma vaga lembrança dos aspectos internos de um programa Unix, isso não significa absolutamente que você não pode escrever uma imitação, mas tente organizar a imitação internamente em linhas diferentes, porque isso provavelmente fará os detalhes de a versão Unix é irrelevante e diferente dos seus resultados.

Por exemplo, os utilitários Unix geralmente eram otimizados para minimizar o uso de memória; se você optar pela velocidade , seu programa será muito diferente.

(Ênfase minha.)