Przeglądałem tutajstrlen kod i zastanawiałem się, czy optymalizacje zastosowane w kodzie są naprawdę potrzebne? Na przykład, dlaczego coś takiego nie działa równie dobrze, ani lepiej?

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

Czy prostszy kod nie jest lepszy i / lub łatwiejszy dla kompilatora do optymalizacji?

Kod strlenna stronie za linkiem wygląda następująco:

/* 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)

Dlaczego ta wersja działa szybko?

Czy to nie robi dużo niepotrzebnej pracy?

Ty nie potrzebujesz, a ty nigdy nie powinni pisać kod tak - zwłaszcza jeśli nie jesteś kompilator C / sprzedawca standardowe biblioteki. Jest to kod używany do implementacji strlenz pewnymi bardzo wątpliwymi hackami i założeniami (które nie są testowane z asercjami lub wspomniane w komentarzach):

• unsigned long ma 4 lub 8 bajtów
• bajty to 8 bitów
• wskaźnik można rzutować na unsigned long longi nieuintptr_t
• można wyrównać wskaźnik po prostu sprawdzając, czy 2 lub 3 bity najniższego rzędu są równe zero
• można uzyskać dostęp do ciągu jako unsigned longs
• można czytać poza końcem tablicy bez żadnych negatywnych skutków.

Co więcej, dobry kompilator może nawet zastąpić kod napisany jako

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

(zauważ, że musi to być typ zgodny z size_t) z wbudowaną wersją kompilatora strlenlub wektoryzuj kod; ale kompilator raczej nie byłby w stanie zoptymalizować złożonej wersji.

strlenFunkcja jest opisana C11 7.24.6.3 jako:

Opis

2. strlenFunkcja oblicza długość łańcucha wskazywanego przez s.

Zwroty

3. strlenFunkcja zwraca liczbę znaków, które poprzedzają znak kończący null.

Teraz, jeśli ciąg wskazany przez sbył w tablicy znaków wystarczająco długiej, aby pomieścić ciąg i kończącą się wartość NUL, zachowanie nie zostanie zdefiniowane, jeśli uzyskamy dostęp do ciągu poza terminatorem zerowym, na przykład w

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

Tak więc naprawdę jedynym sposobem, aby w C w pełni przenośnym / zgodnym ze standardami poprawnie to zaimplementować, jest sposób, w jaki jest napisany w twoim pytaniu , z wyjątkiem trywialnych przekształceń - możesz udawać, że jesteś szybszy, rozwijając pętlę itp., Ale wciąż trzeba to zrobić jeden bajt na raz.

(Jak zauważyli komentatorzy, kiedy ścisła przenośność jest zbyt dużym obciążeniem, korzystanie z rozsądnych lub znanych bezpiecznych założeń nie zawsze jest złą rzeczą. Zwłaszcza w kodzie, który jest częścią jednej konkretnej implementacji C. Ale musisz zrozumieć rządzi, zanim dowiesz się, jak / kiedy możesz je zgiąć.)

Połączona strlenimplementacja najpierw sprawdza bajty indywidualnie, aż wskaźnik wskaże naturalną granicę wyrównania 4 lub 8 bajtów unsigned long. Standard C mówi, że dostęp do wskaźnika, który nie jest właściwie wyrównany, ma niezdefiniowane zachowanie , więc absolutnie należy to zrobić, aby kolejna brudna sztuczka była jeszcze bardziej brudna. (W praktyce na niektórych architekturach procesorów innych niż x86 błąd ładowania wyrównanego słowa lub podwójnego słowa spowoduje błąd. C nie jest przenośnym językiem asemblera, ale ten kod używa go w ten sposób). To także pozwala na odczyt poza końcem obiektu bez ryzyka błędu w implementacjach, w których ochrona pamięci działa w wyrównanych blokach (np. Stronach pamięci wirtualnej 4kiB).

Teraz przychodzi brudny część: kod przerwy obietnicy i czyta 4 lub 8 na 8-bitowe bajty na raz (a long int) i wykorzystuje bitowy sztuczkę z unsigned Ponadto, aby szybko dowiedzieć się, czy są jakieś zero bajtów w ciągu tych 4 lub 8 bajty - używa specjalnie spreparowanej liczby, która spowodowałaby zmianę bitu przenoszenia bitów przechwyconych przez maskę bitową. W gruncie rzeczy okazałoby się, że którykolwiek z 4 lub 8 bajtów w masce jest zerami podobno szybszymi niż pętla przez każdy z tych bajtów. Na końcu jest pętla na końcu, aby dowiedzieć się, który bajt był pierwszym zerem, jeśli w ogóle, i zwrócić wynik.

Największym problemem jest to, że w sizeof (unsigned long) - 1niektórych sizeof (unsigned long)przypadkach poza czasem będzie czytać poza końcem ciągu - tylko jeśli bajt zerowy znajduje się w ostatnim dostępnym bajcie (tzn. W little-endian jest najbardziej znaczący, a w big-endian najmniej znaczący) , nie ma dostępu do tablicy poza granicami!

Kod, nawet używany do implementacji strlenw standardowej bibliotece C, jest złym kodem. Ma w sobie kilka zdefiniowanych i nieokreślonych aspektów implementacji i nie należy go nigdzie używać zamiast dostarczonego przez system strlen- zmieniłem nazwę funkcji na the_strlentutaj i dodałem następujące main:

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

Bufor jest starannie dobrany, aby mógł pomieścić dokładnie hello worldciąg i terminator. Jednak na moim 64-bitowym procesorze unsigned longjest to 8 bajtów, więc dostęp do drugiej części przekroczyłby ten bufor.

Jeśli teraz skompiluję się -fsanitize=undefinedi -fsanitize=addressuruchomię wynikowy program, otrzymam:

% ./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

tzn. wydarzyły się złe rzeczy.

W komentarzach dotyczących niektórych szczegółów / tła było wiele błędnych domysłów.

Patrzysz na zoptymalizowaną implementację C w glibc zoptymalizowaną pod kątem awarii. (Dla ISA, które nie mają odręcznej implementacji asm) . Lub stara wersja tego kodu, który wciąż znajduje się w drzewie źródeł glibc. https://code.woboq.org/userspace/glibc/string/strlen.c.html to przeglądarka kodów oparta na bieżącym drzewie git glibc. Najwyraźniej jest nadal używany przez kilka głównych celów glibc, w tym MIPS. (Dzięki @ wyzwolenie).

W popularnych programach ISA, takich jak x86 i ARM, glibc używa ręcznie napisanego asm

Motywacja do zmiany czegokolwiek w tym kodzie jest więc mniejsza niż mogłoby się wydawać.

Ten kod bithack ( https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord ) nie jest tym, co faktycznie działa na twoim serwerze / komputerze stacjonarnym / laptopie / smartfonie. Jest to lepsze niż naiwna pętla bajt po czasie, ale nawet ten bithack jest dość zły w porównaniu do wydajnego asm dla współczesnych procesorów (szczególnie x86, gdzie AVX2 SIMD pozwala na sprawdzenie 32 bajtów za pomocą kilku instrukcji, pozwalając od 32 do 64 bajtów na zegar cykl w głównej pętli, jeśli dane są gorące w pamięci podręcznej L1d na nowoczesnych procesorach z obciążeniem wektora 2 / zegar i przepustowością ALU, tj. dla średnich łańcuchów, w których nie dominuje narzut startowy.)

glibc używa dynamicznych sztuczek łączących, aby rozwiązać strlenoptymalną wersję dla twojego procesora, więc nawet w x86 jest wersja SSE2 (wektory 16-bajtowe, linia bazowa dla x86-64) i wersja AVX2 (wektory 32-bajtowe).

x86 ma wydajny transfer danych między rejestrami wektorowymi i rejestrami ogólnego przeznaczenia, co czyni go wyjątkowo (?) dobrym do użycia SIMD do przyspieszenia funkcji na ciągach o niejawnej długości, w których kontrola pętli zależy od danych. pcmpeqb/ pmovmskbumożliwia testowanie 16 oddzielnych bajtów jednocześnie.

glibc ma wersję AArch64 taką jak ta przy użyciu AdvSIMD oraz wersję dla procesorów AArch64, w których rejestr vector-> GP blokuje potok, więc faktycznie używa tego bithacka . Ale używa zer wiodących, aby znaleźć bajt w rejestrze, gdy tylko zostanie trafiony, i korzysta z efektywnego, niewyrównanego dostępu AArch64 po sprawdzeniu przejścia strony.

Powiązane również: Dlaczego ten kod jest 6.5x wolniejszy z włączonymi optymalizacjami? ma więcej szczegółów na temat tego, co jest szybkie w porównaniu z asmem x86, strlenz dużym buforem i prostą implementacją asm, które mogą być dobre dla gcc, aby wiedzieć, jak wstawić. (Niektóre wersje gcc są nierozsądnie wbudowane, rep scasbco jest bardzo powolne, lub 4-bajtowe bithack w tym czasie. Więc przepis GCC wymaga aktualizacji lub wyłączenia.)

Asm nie ma „niezdefiniowanego zachowania” w stylu C ; dostęp do bajtów w pamięci jest bezpieczny, jak chcesz, a wyrównane obciążenie, które obejmuje dowolne prawidłowe bajty, nie może winić. Ochrona pamięci ma miejsce przy uziarnieniu strony; wyrównany dostęp jest węższy niż ten, który nie może przekroczyć granicy strony. Czy bezpiecznie jest czytać poza końcem bufora na tej samej stronie na x86 i x64? To samo rozumowanie dotyczy kodu maszynowego, który ten hack C zmusza kompilatory do stworzenia dla autonomicznej, nie-wbudowanej implementacji tej funkcji.

Kiedy kompilator emituje kod w celu wywołania nieznanej funkcji nieliniowej, musi założyć, że funkcja modyfikuje dowolne / wszystkie zmienne globalne i każdą pamięć, do której może mieć wskaźnik. tzn. wszystko oprócz mieszkańców, którzy nie mieli ucieczki adresu, muszą być zsynchronizowane w pamięci podczas połączenia. Dotyczy to oczywiście funkcji napisanych w asm, ale także funkcji bibliotecznych. Jeśli nie włączysz optymalizacji czasu łącza, dotyczy to nawet oddzielnych jednostek tłumaczeniowych (plików źródłowych).

Dlaczego jest to bezpieczne w ramach glibc, ale nie inaczej.

Najważniejszym czynnikiem jest to, że strlennie może się to wiązać z niczym innym. Nie jest to do tego bezpieczne; zawiera ściśle aliasing UB (odczyt chardanych przez an unsigned long*). char*wolno aliasować cokolwiek innego, ale odwrotność nie jest prawdą .

Jest to funkcja biblioteczna dla skompilowanej biblioteki z wyprzedzeniem (glibc). Nie zostanie wprowadzony z optymalizacją czasu łącza dla dzwoniących. Oznacza to, że musi się skompilować do bezpiecznego kodu maszynowego dla autonomicznej wersji strlen. Nie musi być przenośny / bezpieczny C.

Biblioteka GNU C musi się kompilować tylko z GCC. Najwyraźniej nie jest obsługiwane kompilowanie go za pomocą clang lub ICC, nawet jeśli obsługują rozszerzenia GNU. GCC to kompilatory z wyprzedzeniem, które przekształcają plik źródłowy C w plik obiektowy kodu maszynowego. Nie interpreter, więc jeśli nie wstawi się w czasie kompilacji, bajty w pamięci są tylko bajtami w pamięci. tzn. ścisłe aliasing UB nie jest niebezpieczne, gdy dostęp do różnych typów odbywa się w różnych funkcjach, które nie są ze sobą powiązane.

Pamiętaj, że strlenjego zachowanie jest określone przez normę ISO C. Ta nazwa funkcji jest szczególnie częścią implementacji. Kompilatory takie jak GCC nawet traktują nazwę jako funkcję wbudowaną, chyba że używasz -fno-builtin-strlen, więc strlen("foo")może być stałą czasową kompilacji 3. Definicja w bibliotece jest używana tylko wtedy, gdy gcc decyduje się na faktyczne wywołanie jej zamiast wstawiania własnego przepisu lub czegoś takiego.

Kiedy UB nie jest widoczny dla kompilatora w czasie kompilacji, dostajesz rozsądny kod maszynowy. Kod maszyna musi pracować dla przypadku no-UB, a nawet jeśli chciał się, że nie ma sposobu na asm wykryć jakie rodzaje rozmówca celu wprowadzenia danych do wskazywanego w pamięci.

Glibc jest kompilowany do autonomicznej biblioteki statycznej lub dynamicznej, która nie może się równać z optymalizacją czasu łącza. Skrypty budowania glibc nie tworzą „grubych” bibliotek statycznych zawierających kod maszynowy + wewnętrzną reprezentację GIMPLE GIMP dla optymalizacji czasu łącza podczas wstawiania do programu. (tzn. libc.anie weźmie udziału w -fltooptymalizacji czasu łącza do programu głównego). Budowanie glibc w ten sposób byłoby potencjalnie niebezpieczne dla celów, które faktycznie z niego korzystają.c .

W rzeczywistości, jak komentuje @zwol, LTO nie może być użyte podczas budowania samego glibc , ponieważ taki „łamliwy” kod może się zepsuć, jeśli możliwe jest wstawianie między plikami źródłowymi glibc. (Istnieją pewne zastosowania wewnętrzne strlen, np. Może w ramach printfwdrożenia)

To strlenpowoduje pewne założenia:

• CHAR_BITjest wielokrotnością liczby 8 . Prawda na wszystkich systemach GNU. POSIX 2001 gwarantuje nawet CHAR_BIT == 8. (Wygląda to bezpiecznie na systemy z CHAR_BIT= 16lub 32, podobnie jak niektóre DSP; pętla bez sizeof(long) = sizeof(char) = 1wyrównania -prologu zawsze będzie uruchamiać 0 iteracji, ponieważ ponieważ każdy wskaźnik jest zawsze wyrównany i p & sizeof(long)-1ma zawsze zero.) Ale jeśli masz zestaw znaków spoza ASCII, gdzie znaki to 9 lub szerokość 12 bitów, 0x8080...to zły wzór.
• (być może) unsigned longma 4 lub 8 bajtów. A może to faktycznie działałoby dla dowolnego rozmiaru unsigned longdo 8 i używa tego, assert()aby to sprawdzić.

Te dwa nie są możliwe UB, są po prostu nieprzenośne na niektóre implementacje C. Ten kod jest (lub był) częścią implementacji języka C na platformach, na których działa, więc nie ma sprawy.

Kolejnym założeniem jest potencjalny C UB:

• Wyrównane ładowanie, które zawiera dowolne prawidłowe bajty, nie może powodować błędu i jest bezpieczne, dopóki zignorujesz bajty poza obiektem, którego faktycznie chcesz. (Prawda w asm na wszystkich systemach GNU i na wszystkich normalnych procesorach, ponieważ ochrona pamięci ma miejsce przy uziarnieniu strony. Czy bezpiecznie jest czytać poza końcem bufora na tej samej stronie na x86 i x64? Bezpiecznie w C, gdy UB nie jest widoczny w czasie kompilacji. Bez inliniowania tak jest w tym przypadku. Kompilator nie może udowodnić, że odczytanie pierwszego 0jest UB; może to być na przykład char[]tablica C zawierająca {1,2,0,3})

Ten ostatni punkt sprawia, że ​​można bezpiecznie czytać poza końcem obiektu C. Jest to całkiem bezpieczne, nawet jeśli korzystasz z obecnych kompilatorów, ponieważ myślę, że obecnie nie traktują tego, że sugerowanie ścieżki wykonania jest nieosiągalne. Ale tak czy inaczej, ścisłe aliasing jest już hitem, jeśli kiedykolwiek pozwolisz na to.

Miałbyś wtedy problemy, takie jak stare niebezpieczne memcpy CPP jądra Linuxa, które używało rzutowania na unsigned long( gcc, ścisłe aliasing i horrory ).

To strlensięga czasów, kiedy można było uciec od takich rzeczy w ogóle ; niegdyś było to całkiem bezpieczne bez zastrzeżenia „tylko wtedy, gdy nie jest inline” przed GCC3.

UB, który jest widoczny tylko, gdy patrzy się przez granice połączeń / połączeń, nie może nas skrzywdzić. (np. wywoływanie tego char buf[]zamiast na tablicy unsigned long[]rzutowania na a const char*). Gdy kod maszynowy jest już w kamieniu, zajmuje się tylko bajtami w pamięci. Wywołanie funkcji innej niż wbudowana musi zakładać, że odbiorca odczytuje dowolną / całą pamięć.

Pisanie tego bezpiecznie, bez ścisłego aliasingu UB

Atrybut typ GCCmay_alias daje rodzajem takiego samego traktowania alias-coś tak char*. (Sugerowane przez @KonradBorowsk). Nagłówki GCC używają go obecnie do typów wektorów SIMD x86, __m128idzięki czemu zawsze możesz to zrobić bezpiecznie _mm_loadu_si128( (__m128i*)foo ). (Zobacz Czy `reinterpret_cast`ing między sprzętowym wskaźnikiem wektorowym a odpowiednim typem jest niezdefiniowanym zachowaniem ?, aby uzyskać więcej informacji na temat tego, co to oznacza i co nie oznacza.)

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
     ...
  }
}

Możesz także użyć aligned(1)do wyrażenia typu alignof(T) = 1.
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;

Przenośnym sposobem wyrażania obciążenia aliasingowego w ISO jest to, za pomocąmemcpy którego nowoczesne kompilatory potrafią wstawiać jako instrukcję pojedynczego obciążenia. na przykład

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

Działa to również w przypadku niezaangażowanych obciążeń, ponieważ memcpydziała tak, jakby chardostęp był możliwy tylko w określonym czasie. Ale w praktyce współczesne kompilatory rozumieją memcpybardzo dobrze.

Niebezpieczeństwo polega na tym, że jeśli GCC nie wie na pewno, że char_ptrjest wyrównany do słów, nie wstawi go na niektórych platformach, które mogą nie obsługiwać niezrównanych obciążeń w asm. np. MIPS przed MIPS64r6 lub starszy ARM. Jeśli masz rzeczywiste wywołanie funkcji, aby memcpypo prostu załadować słowo (i zostawić je w innej pamięci), byłoby to katastrofą. GCC czasami widzi, kiedy kod wyrównuje wskaźnik. Lub po pętli char-at-a-time, która osiąga długą granicę, której możesz użyć
p = __builtin_assume_aligned(p, sizeof(unsigned long));

Nie omija to możliwego UB odczytu-przeszłości-obiektu, ale przy obecnym GCC nie jest to niebezpieczne w praktyce.

Dlaczego ręcznie zoptymalizowane źródło C jest konieczne: obecne kompilatory nie są wystarczająco dobre

Asm zoptymalizowany ręcznie może być jeszcze lepszy, gdy chcesz uzyskać ostatni spadek wydajności dla powszechnie używanej standardowej funkcji biblioteki. Specjalnie dla czegoś takiego memcpy, ale także strlen. W tym przypadku korzystanie z SSE2 nie byłoby znacznie łatwiejsze do użycia C z elementami x86.

Ale tutaj mówimy tylko o wersji naiwnej vs. bithack C bez funkcji specyficznych dla ISA.

(Myślę, że możemy przyjąć to jako strlenpowszechnie stosowane, dlatego ważne jest, aby działało to tak szybko, jak to możliwe. Pytanie więc brzmi, czy możemy uzyskać wydajny kod maszynowy z prostszego źródła. Nie, nie możemy.)

Obecne GCC i clang nie są zdolne do automatycznego wektoryzowania pętli, w których liczba iteracji nie jest znana przed pierwszą iteracją . (np. musi być możliwe sprawdzenie, czy pętla wykona co najmniej 16 iteracji przed uruchomieniem pierwszej iteracji). np. możliwe jest autowektoryzowanie memcpy (bufor o jawnej długości), ale nie strcpy lub strlen (ciąg o długości niejawnej), biorąc pod uwagę bieżący kompilatory.

Obejmuje to pętle wyszukiwania lub dowolne inne pętle z danymi zależnymi, if()breaka także licznik.

ICC (kompilator Intela dla x86) może automatycznie wektoryzować niektóre pętle wyszukiwania, ale nadal robi naiwny asm po bajcie tylko dla prostego / naiwnego C, strlentakiego jak użycie libc w OpenBSD. ( Godbolt ). (Z odpowiedzi @ Peske ).

Ręcznie zoptymalizowana biblioteka libc strlenjest niezbędna do działania z obecnymi kompilatorami . Przesuwanie 1 bajta na raz (z rozwijaniem może 2 bajtów na cykl na szerokich superkalarnych procesorach) jest żałosne, gdy pamięć główna może nadążyć za około 8 bajtami na cykl, a pamięć podręczna L1d może dostarczyć 16 do 64 na cykl. (2x 32-bajtowe obciążenia na cykl we współczesnych procesorach głównego nurtu x86 od Haswell i Ryzen. Nie licząc AVX512, który może zmniejszyć prędkość taktowania tylko przy użyciu wektorów 512-bitowych; dlatego glibc prawdopodobnie nie śpieszy się z dodaniem wersji AVX512 , Mimo, że 256-bitowych wektorów AVX512VL + BW maskowana porównać do maski i ktestlub kortestmogłoby strlenbardziej przyjazny hyperthreading'u poprzez redukcję UOPs / iteracji).

Podaję tutaj nie-x86, to jest „16 bajtów”. np. większość procesorów AArch64 może przynajmniej tak zrobić, a niektóre z pewnością więcej. Niektóre mają wystarczającą przepustowość wykonywania, strlenaby nadążyć za tą przepustowością obciążenia.

Oczywiście programy, które działają z dużymi łańcuchami, powinny zwykle śledzić długości, aby uniknąć konieczności powtarzania często szukania długości łańcuchów C. Jednak wydajność od krótkiej do średniej nadal korzysta z ręcznie napisanych implementacji i jestem pewien, że niektóre programy używają strlen na łańcuchach średniej długości.

Zostało to wyjaśnione w komentarzach w pliku, który podłączyłeś:

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

i:

 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.  */

W C można szczegółowo uzasadnić wydajność.

Mniej efektywne jest iterowanie pojedynczych znaków szukających wartości null niż testowanie więcej niż jednego bajtu na raz, tak jak robi to ten kod.

Dodatkowa złożoność wynika z konieczności zapewnienia, że ​​testowany ciąg jest wyrównany w odpowiednim miejscu, aby rozpocząć testowanie więcej niż jednego bajtu na raz (wzdłuż granicy długiego słowa, jak opisano w komentarzach) oraz z konieczności zapewnienia, że ​​założenia o rozmiarach typów danych nie są naruszane, gdy kod jest używany.

W większości (ale nie wszystkich) współczesnych programistów dbałość o szczegóły dotyczące wydajności nie jest konieczna ani nie jest warta kosztów dodatkowej złożoności kodu.

Jednym z miejsc, w których warto zwracać uwagę na taką wydajność, są standardowe biblioteki, takie jak przykład, który podłączyłeś.

Jeśli chcesz dowiedzieć się więcej o granicach słów, zobacz to pytanie i tę doskonałą stronę wikipedii

Oprócz świetnych odpowiedzi tutaj, chcę podkreślić, że kod powiązany z pytaniem służy do implementacji GNU strlen.

Realizacja z OpenBSDstrlen jest bardzo podobny do kodu proponowanych w pytaniu. O złożoności implementacji decyduje autor.

...
#include <string.h>

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

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

DEF_STRONG(strlen);

EDYCJA : Kod OpenBSD, który podłączyłem powyżej, wydaje się być rezerwową implementacją dla ISA, które nie mają własnej implementacji asm. Istnieją różne implementacje w strlenzależności od architektury. Na przykład kod dla amd64strlen to asm. Podobne do komentarzy / odpowiedzi PeterCordesa wskazujących, że nieusuwalne implementacje GNU są również asm.

Krótko mówiąc, jest to optymalizacja wydajności, którą standardowa biblioteka może zrobić, wiedząc z jakim kompilatorem jest skompilowana - nie powinieneś pisać takiego kodu, chyba że piszesz standardową bibliotekę i możesz polegać na konkretnym kompilatorze. W szczególności przetwarza jednocześnie liczbę wyrównania bajtów - 4 na platformach 32-bitowych, 8 na platformach 64-bitowych. Oznacza to, że może być 4 lub 8 razy szybszy niż naiwna bajtowa iteracja.

Aby wyjaśnić, jak to działa, rozważ następujący obraz. Załóżmy tutaj platformę 32-bitową (wyrównanie 4 bajtów).

Powiedzmy, że litera „H” z „Witaj, świecie!” ciąg został podany jako argument dla strlen. Ponieważ procesor lubi układać rzeczy w pamięci (idealnie address % sizeof(size_t) == 0), bajty przed wyrównaniem są przetwarzane bajt po bajcie, przy użyciu wolnej metody.

Następnie dla każdej porcji wielkości wyrównania, obliczając (longbits - 0x01010101) & 0x80808080 != 0, sprawdza, czy którykolwiek z bajtów w liczbie całkowitej jest równy zero. To obliczenie ma fałszywie dodatni wynik, gdy przynajmniej jeden z bajtów jest większy niż 0x80, ale najczęściej powinien działać. Jeśli tak nie jest (jak w żółtym obszarze), długość jest zwiększana o rozmiar wyrównania.

Jeśli którykolwiek z bajtów w liczbie całkowitej okaże się zerowy (lub 0x81), to łańcuch jest sprawdzany bajt po bajcie w celu ustalenia pozycji zero.

Może to zapewnić dostęp poza granicami, jednak ponieważ jest w ramach wyrównania, bardziej prawdopodobne jest, że nie będzie dobrze, jednostki mapowania pamięci zwykle nie mają precyzji na poziomie bajtów.

Chcesz, aby kod był poprawny, łatwy w utrzymaniu i szybki. Czynniki te mają różne znaczenie:

„prawidłowe” jest absolutnie niezbędne.

„utrzymywalny” zależy od tego, ile zamierzasz zachować kod: strlen jest funkcją biblioteki Standard C od ponad 40 lat. To się nie zmieni. Utrzymanie jest zatem dość nieistotne - dla tej funkcji.

„Szybki”: W wielu aplikacjach strcpy, strlen itp. Zajmują znaczną część czasu wykonania. Osiągnięcie takiego samego ogólnego przyrostu prędkości, jak to skomplikowane, ale niezbyt skomplikowane wdrożenie strlen przez ulepszenie kompilatora, wymagałoby heroicznych wysiłków.

Szybkość ma jeszcze jedną zaletę: gdy programiści dowiadują się, że wywołanie „strlen” jest najszybszą metodą, mogą zmierzyć liczbę bajtów w ciągu, nie mają już ochoty pisać własnego kodu, aby przyspieszyć działanie.

Tak więc w przypadku strlen szybkość jest o wiele ważniejsza, a łatwość konserwacji znacznie mniej ważna niż w przypadku większości kodu, który kiedykolwiek napiszesz.

Dlaczego to musi być takie skomplikowane? Załóżmy, że masz ciąg 1000 bajtów. Prosta implementacja sprawdzi 1000 bajtów. Obecna implementacja prawdopodobnie zbadałaby 64-bitowe słowa na raz, co oznacza 125 64-bitowych lub ośmiobajtowych słów. Może nawet używać instrukcji wektorowych analizujących powiedzmy 32 bajty naraz, co byłoby jeszcze bardziej skomplikowane i jeszcze szybsze. Korzystanie z instrukcji wektorowych prowadzi do kodu, który jest nieco bardziej skomplikowany, ale dość prosty, sprawdzenie, czy jeden z ośmiu bajtów w 64-bitowym słowie ma wartość zero, wymaga pewnych sprytnych sztuczek. Tak więc dla średnich i długich łańcuchów można oczekiwać, że kod ten będzie około cztery razy szybszy. Dla funkcji tak ważnej jak strlen warto napisać bardziej złożoną funkcję.

PS. Kod nie jest zbyt przenośny. Ale jest częścią biblioteki Standard C, która jest częścią implementacji - nie musi być przenośna.

PPS. Ktoś opublikował przykład, w którym narzędzie do debugowania skarżyło się na dostęp do bajtów poza końcem ciągu. Można zaprojektować implementację, która zagwarantuje, że: Jeśli p jest poprawnym wskaźnikiem do bajtu, to każdy dostęp do bajtu w tym samym wyrównanym bloku, który byłby niezdefiniowanym zachowaniem zgodnie ze standardem C, zwróci nieokreśloną wartość.

PPPS. Intel dodał instrukcje do swoich późniejszych procesorów, które tworzą blok konstrukcyjny dla funkcji strstr () (znajdowanie podłańcucha w łańcuchu). Ich opis jest zadziwiający, ale mogą sprawić, że ta konkretna funkcja będzie prawdopodobnie 100 razy szybsza. (Zasadniczo, biorąc pod uwagę tablicę zawierającą „Hello, world!” I tablicę b zaczynającą się od 16 bajtów „HelloHelloHelloH” i zawierającą więcej bajtów, okazuje się, że łańcuch a nie występuje wb wcześniej niż od indeksu 15) .

W skrócie: sprawdzanie ciągu bajt po bajcie może być powolne na architekturach, które mogą pobierać większe ilości danych na raz.

Jeśli sprawdzenie zakończenia zerowego może być wykonane w wersji 32- lub 64-bitowej, zmniejsza to liczbę kontroli, które musi wykonać kompilator. To właśnie próbuje zrobić połączony kod, mając na uwadze konkretny system. Przyjmują założenia dotyczące adresowania, wyrównywania, użycia pamięci podręcznej, niestandardowych ustawień kompilatora itp.

Czytanie bajtu po bajcie, jak w twoim przykładzie, byłoby rozsądnym podejściem na 8-bitowym procesorze lub podczas pisania przenośnej biblioteki lib napisanej w standardowym C.

Spojrzenie na standardowe biblioteki C w celu uzyskania porady, jak pisać szybki / dobry kod, nie jest dobrym pomysłem, ponieważ będzie on nieprzenośny i będzie polegał na niestandardowych założeniach lub źle zdefiniowanym zachowaniu. Jeśli jesteś początkujący, czytanie takiego kodu będzie prawdopodobnie bardziej szkodliwe niż edukacyjne.

Jedną ważną rzeczą, o której nie wspominają inne odpowiedzi, jest to, że FSF bardzo ostrożnie upewnia się, że zastrzeżony kod nie trafia do projektów GNU. W standardach kodowania GNU w części Odnosząc się do programów własnościowych jest ostrzeżenie o zorganizowaniu implementacji w taki sposób, aby nie można jej było pomylić z istniejącym kodem własności:

W żadnym wypadku nie odwołuj się do kodu źródłowego Uniksa dla lub w trakcie pracy nad GNU! (Lub do jakichkolwiek innych programów prawnie zastrzeżonych.)

Jeśli masz niejasne skojarzenie z elementami wewnętrznymi programu uniksowego, nie oznacza to absolutnie, że nie możesz napisać imitacji, ale spróbuj zorganizować imitację wewnętrznie według różnych linii, ponieważ może to doprowadzić do szczegółów wersja uniksowa nieistotna i niepodobna do twoich wyników.

Na przykład narzędzia uniksowe zostały ogólnie zoptymalizowane, aby zminimalizować zużycie pamięci; jeśli zamiast tego wybierzesz prędkość , twój program będzie zupełnie inny.

(Podkreśl moje.)