Saya melihat-lihat strlenkode di sini dan saya bertanya-tanya apakah optimasi yang digunakan dalam kode benar-benar diperlukan? Misalnya, mengapa hal seperti ini tidak akan berfungsi sama baiknya atau lebih baik?

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

Bukankah kode sederhana lebih baik dan / atau lebih mudah untuk dioptimalkan oleh kompiler?

Kode strlenpada halaman di belakang tautan terlihat seperti ini:

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

Mengapa versi ini berjalan cepat?

Bukankah itu melakukan banyak pekerjaan yang tidak perlu?

Anda tidak perlu dan Anda tidak boleh menulis kode seperti itu - terutama jika Anda bukan vendor C compiler / library standar. Ini adalah kode yang digunakan untuk mengimplementasikan strlendengan beberapa peretasan dan asumsi kecepatan yang sangat dipertanyakan (yang tidak diuji dengan pernyataan atau disebutkan dalam komentar):

• unsigned long adalah 4 atau 8 byte
• byte adalah 8 bit
• sebuah pointer dapat dilemparkan ke unsigned long longdan tidakuintptr_t
• seseorang dapat menyelaraskan pointer hanya dengan memeriksa bahwa 2 atau 3 bit urutan terendah adalah nol
• seseorang dapat mengakses string sebagai unsigned longs
• orang dapat membaca melewati akhir array tanpa efek buruk.

Terlebih lagi, kompiler yang baik bahkan dapat menggantikan kode yang ditulis sebagai

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

(perhatikan bahwa itu harus tipe yang kompatibel dengan size_t) dengan versi inline dari kompiler builtin strlen, atau membuat vektor kode; tetapi kompiler tidak akan mungkin dapat mengoptimalkan versi yang kompleks.

The strlenFungsi digambarkan oleh C11 7.24.6.3 sebagai:

Deskripsi

2. The strlenFungsi menghitung panjang string ditunjukkan oleh s.

Kembali

3. The strlenfungsi mengembalikan jumlah karakter yang mendahului karakter terminating null.

Sekarang, jika string yang ditunjukkan oleh sberada dalam array karakter yang cukup panjang untuk berisi string dan NUL yang mengakhiri, perilaku akan tidak terdefinisi jika kita mengakses string melewati terminator nol, misalnya dalam

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

Jadi benar-benar satu - satunya cara di sepenuhnya portabel / standar yang memenuhi C untuk mengimplementasikan ini dengan benar adalah cara itu ditulis dalam pertanyaan Anda , kecuali untuk transformasi sepele - Anda dapat berpura-pura lebih cepat dengan membuka gulungan lingkaran dll, tetapi masih perlu dilakukan satu byte pada suatu waktu.

(Seperti yang ditunjukkan oleh komentator, ketika portabilitas yang ketat terlalu membebani, mengambil keuntungan dari asumsi yang masuk akal atau dikenal-aman tidak selalu merupakan hal yang buruk. Terutama dalam kode yang merupakan bagian dari satu implementasi khusus C. Tetapi Anda harus memahami aturan sebelum mengetahui bagaimana / kapan Anda bisa menekuknya.)

strlenImplementasi yang ditautkan pertama-tama memeriksa byte secara individual sampai pointer menunjuk ke batas penyelarasan alami 4 atau 8 byte dari unsigned long. Standar C mengatakan bahwa mengakses pointer yang tidak selaras dengan benar memiliki perilaku yang tidak terdefinisi , jadi ini benar-benar harus dilakukan agar trik kotor berikutnya menjadi lebih kotor. (Dalam prakteknya pada beberapa arsitektur CPU selain x86, kata yang tidak selaras atau beban doubleword akan bermasalah. C tidak bahasa rakitan portabel, tetapi kode ini menggunakannya seperti itu). Ini juga yang memungkinkan untuk membaca melewati akhir suatu objek tanpa risiko kesalahan pada implementasi di mana perlindungan memori bekerja dalam blok yang disejajarkan (misalnya halaman memori virtual 4kiB).

Sekarang sampai pada bagian yang kotor: kode istirahat janji dan membaca 4 atau 8 8-bit byte pada waktu (a long int), dan menggunakan trik sedikit dengan penambahan unsigned untuk cepat mengetahui jika ada setiap nol byte dalam mereka 4 atau 8 byte - ini menggunakan nomor yang dibuat khusus untuk yang akan menyebabkan carry bit untuk mengubah bit yang ditangkap oleh bit mask. Pada intinya ini kemudian akan mencari tahu apakah salah satu dari 4 atau 8 byte dalam topeng adalah nol yang seharusnya lebih cepat daripada perulangan melalui masing-masing byte ini. Akhirnya ada loop di akhir untuk mengetahui byte mana yang merupakan nol pertama, jika ada, dan untuk mengembalikan hasilnya.

Masalah terbesar adalah bahwa di sizeof (unsigned long) - 1kali dari sizeof (unsigned long)kasus itu akan membaca melewati akhir string - hanya jika nol byte dalam terakhir byte Diakses (yaitu di little-endian yang paling signifikan, dan dalam big-endian yang paling signifikan) , apakah itu tidak mengakses array di luar batas!

Kode, meskipun digunakan untuk mengimplementasikan strlendalam pustaka standar C adalah kode yang buruk . Ini memiliki beberapa aspek implementasi-didefinisikan dan tidak terdefinisi di dalamnya dan tidak boleh digunakan di mana pun alih-alih sistem yang disediakan strlen- Saya mengganti nama fungsi ke the_strlensini dan menambahkan yang berikut main:

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

Buffer berukuran hati-hati sehingga dapat memegang tepat hello worldstring dan terminator. Namun pada prosesor 64-bit saya unsigned longadalah 8 byte, sehingga akses ke bagian terakhir akan melebihi buffer ini.

Jika saya sekarang mengkompilasi dengan -fsanitize=undefineddan -fsanitize=addressdan menjalankan program yang dihasilkan, saya mendapatkan:

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

yaitu hal-hal buruk terjadi.

Ada banyak tebakan yang salah (sedikit atau seluruhnya) dalam komentar tentang beberapa detail / latar belakang untuk ini.

Anda sedang melihat implementasi C fallback dioptimalkan glibc yang dioptimalkan. (Untuk SPA yang tidak memiliki implementasi asm yang ditulis tangan) . Atau versi lama dari kode itu, yang masih di pohon sumber glibc. https://code.woboq.org/userspace/glibc/string/strlen.c.html adalah kode-peramban berdasarkan pohon glibc git saat ini. Tampaknya masih digunakan oleh beberapa target glibc utama, termasuk MIPS. (Terima kasih @zwol).

Pada ISA populer seperti x86 dan ARM, glibc menggunakan asm yang ditulis tangan

Jadi insentif untuk mengubah apa pun tentang kode ini lebih rendah dari yang Anda kira.

Kode bithack ini ( https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord ) bukan yang sebenarnya berjalan di server / desktop / laptop / smartphone Anda. Ini lebih baik daripada loop byte-at-a-time yang naif, tetapi bahkan bithack ini cukup buruk dibandingkan dengan asm efisien untuk CPU modern (terutama x86 di mana AVX2 SIMD memungkinkan memeriksa 32 byte dengan beberapa instruksi, memungkinkan 32 hingga 64 byte per jam siklus di loop utama jika data panas di cache L1d pada CPU modern dengan 2 / jam beban vektor dan throughput ALU. yaitu untuk string berukuran sedang di mana overhead startup tidak mendominasi.)

glibc menggunakan trik tautan dinamis untuk menyelesaikan strlenke versi optimal untuk CPU Anda, sehingga bahkan dalam x86 ada versi SSE2 (vektor 16-byte, garis dasar untuk x86-64) dan versi AVX2 (vektor 32-byte).

x86 memiliki transfer data yang efisien antara register vektor dan keperluan umum, yang membuatnya unik (?) baik untuk menggunakan SIMD untuk mempercepat fungsi pada string panjang implisit di mana kontrol loop bergantung pada data. pcmpeqb/ pmovmskbmemungkinkan untuk menguji 16 byte terpisah sekaligus.

glibc memiliki versi AArch64 seperti itu yang menggunakan AdvSIMD , dan versi untuk CPU AArch64 di mana register vektor-> GP menghentikan jalur pipa, sehingga ia benar - benar menggunakan bithack ini . Tetapi menggunakan count-leading-zero untuk menemukan byte-dalam-register begitu mendapat hit, dan mengambil keuntungan dari akses yang tidak selaras efisien AArch64 setelah memeriksa untuk lintas halaman.

Juga terkait: Mengapa kode ini 6.5x lebih lambat dengan optimisasi diaktifkan? memiliki beberapa perincian lebih lanjut tentang apa yang cepat vs. lambat dalam as86 x86 strlendengan dengan buffer besar dan implementasi asm sederhana yang mungkin baik bagi gcc untuk mengetahui cara melakukan inline. (Beberapa versi gcc secara tidak bijaksana sebaris rep scasbyang sangat lambat, atau bithack 4-byte-at-a-time seperti ini. Jadi resep inline-strlen GCC perlu diperbarui atau dinonaktifkan.)

ASM tidak memiliki "perilaku tidak terdefinisi" gaya C ; aman untuk mengakses byte di memori sesuka Anda, dan pemuatan selaras yang menyertakan byte yang valid tidak dapat kesalahan. Perlindungan memori terjadi dengan rincian halaman selaras; akses yang selaras lebih sempit dari itu tidak dapat melintasi batas halaman. Apakah aman membaca melewati akhir buffer dalam halaman yang sama di x86 dan x64? Alasan yang sama berlaku untuk kode mesin yang membuat peretasan C ini dibuat untuk membuat implementasi mandiri dari fungsi ini.

Ketika kompiler memancarkan kode untuk memanggil fungsi non-inline yang tidak diketahui, ia harus mengasumsikan bahwa fungsi memodifikasi setiap / semua variabel global dan memori apa pun yang mungkin memiliki pointer. yaitu segala sesuatu kecuali penduduk setempat yang tidak memiliki alamat pelarian mereka harus disinkronkan dalam memori di seluruh panggilan. Ini berlaku untuk fungsi yang ditulis dalam asm, jelas, tetapi juga untuk fungsi perpustakaan. Jika Anda tidak mengaktifkan optimasi waktu-tautan, itu bahkan berlaku untuk unit terjemahan yang terpisah (file sumber).

Mengapa ini aman sebagai bagian dari glibc tetapi tidak sebaliknya.

Faktor yang paling penting adalah bahwa ini strlentidak bisa sejalan dengan hal lain. Tidak aman untuk itu; itu berisi UB alias ketat (membaca chardata melalui unsigned long*). char*diizinkan untuk alias apa pun tetapi kebalikannya tidak benar .

Ini adalah fungsi perpustakaan untuk perpustakaan yang dikompilasi sebelumnya (glibc). Itu tidak akan disejajarkan dengan optimasi tautan waktu ke penelepon. Ini berarti hanya perlu mengkompilasi ke kode mesin yang aman untuk versi yang berdiri sendiri strlen. Tidak harus portabel / aman C.

Pustaka GNU C hanya perlu dikompilasi dengan GCC. Rupanya itu tidak didukung untuk mengkompilasinya dengan dentang atau ICC, meskipun mereka mendukung ekstensi GNU. GCC adalah kompiler terdepan yang mengubah file sumber C menjadi file objek kode mesin. Bukan penerjemah, jadi kecuali itu inline pada waktu kompilasi, byte dalam memori hanyalah byte dalam memori. yaitu UB ketat-aliasing tidak berbahaya ketika akses dengan tipe yang berbeda terjadi dalam fungsi yang berbeda yang tidak sejalan satu sama lain.

Ingatlah bahwa strlenperilaku didefinisikan oleh standar ISO C. Nama fungsi itu secara khusus adalah bagian dari implementasi. Kompiler seperti GCC bahkan memperlakukan nama sebagai fungsi bawaan kecuali jika Anda menggunakannya -fno-builtin-strlen, sehingga strlen("foo")bisa berupa konstanta waktu kompilasi 3. Definisi di perpustakaan hanya digunakan ketika gcc memutuskan untuk benar-benar memancarkan panggilan ke sana alih-alih inlining resepnya sendiri atau sesuatu.

Ketika UB tidak terlihat oleh kompiler pada waktu kompilasi, Anda mendapatkan kode mesin waras. Kode mesin harus bekerja untuk case no-UB, dan bahkan jika Anda mau , tidak ada cara bagi asm untuk mendeteksi tipe apa yang digunakan oleh penelepon untuk memasukkan data ke dalam memori menunjuk-ke.

Glibc dikompilasi ke perpustakaan statis atau dinamis yang berdiri sendiri yang tidak dapat sejalan dengan optimasi waktu tautan. skrip build glibc tidak membuat pustaka statis "gemuk" yang berisi kode mesin + gcc Representasi internal GIMPLE untuk optimasi tautan-waktu ketika masuk ke dalam sebuah program. (Yaitu libc.atidak akan berpartisipasi dalam -fltooptimasi tautan-waktu ke dalam program utama.) Membangun glibc dengan cara itu akan berpotensi tidak aman pada target yang benar-benar menggunakan ini.c .

Bahkan seperti komentar @zwol, KPP tidak dapat digunakan ketika membangun glibc itu sendiri , karena kode "rapuh" seperti ini yang bisa pecah jika inlining antara file sumber glibc adalah mungkin. (Ada beberapa penggunaan internal strlen, misalnya mungkin sebagai bagian dari printfimplementasi)

Ini strlenmembuat beberapa asumsi:

• CHAR_BITadalah kelipatan dari 8 . Benar pada semua sistem GNU. POSIX 2001 bahkan menjamin CHAR_BIT == 8. (Ini terlihat aman untuk sistem dengan CHAR_BIT= 16atau 32, seperti beberapa DSP; loop unaligned-prologue akan selalu menjalankan 0 iterasi jika sizeof(long) = sizeof(char) = 1karena setiap pointer selalu sejajar dan p & sizeof(long)-1selalu nol.) Tetapi jika Anda memiliki set karakter non-ASCII di mana karakter adalah 9 atau lebar 12 bit, 0x8080...adalah pola yang salah.
• (mungkin) unsigned longadalah 4 atau 8 byte. Atau mungkin itu benar-benar berfungsi untuk ukuran unsigned longhingga 8, dan itu menggunakan assert()untuk memeriksa itu.

Keduanya tidak mungkin UB, mereka hanya non-portabilitas untuk beberapa implementasi C. Kode ini (atau dulu) adalah bagian dari implementasi C pada platform di mana ia bekerja, jadi tidak masalah.

Asumsi selanjutnya adalah potensi C UB:

• Muat selaras yang berisi byte yang valid tidak dapat kesalahan , dan aman selama Anda mengabaikan byte di luar objek yang Anda inginkan. (Benar dalam asm pada setiap sistem GNU, dan pada semua CPU normal karena perlindungan memori terjadi dengan perataan halaman selaras. Apakah aman untuk membaca melewati akhir buffer dalam halaman yang sama pada x86 dan x64? Aman di C saat UB tidak dapat dilihat pada waktu kompilasi. Tanpa inline, inilah kasusnya di sini. Kompiler tidak dapat membuktikan bahwa membaca sebelumnya 0adalah UB; bisa berupa char[]array C yang berisi {1,2,0,3}misalnya)

Poin terakhir itulah yang membuatnya aman untuk membaca melewati akhir objek C di sini. Itu cukup aman bahkan ketika menyejajarkan dengan kompiler saat ini karena saya pikir mereka saat ini tidak memperlakukan bahwa menyiratkan jalur eksekusi tidak dapat dijangkau. Tapi bagaimanapun, aliasing yang ketat sudah menjadi showstopper jika Anda membiarkan ini sejalan.

Maka Anda akan memiliki masalah seperti memcpy makro CPP kernel tua Linux yang tidak aman yang menggunakan pointer-casting ke unsigned long( gcc, aliasing ketat, dan cerita horor ).

strlenTanggal ini kembali ke era ketika Anda bisa pergi dengan hal-hal seperti itu secara umum ; dulu cukup aman tanpa peringatan "hanya ketika tidak inlining" sebelum GCC3.

UB yang hanya terlihat ketika melihat lintas batas panggilan / ret tidak dapat menyakiti kita. (mis. memanggil ini pada char buf[]bukannya array array unsigned long[]ke a const char*). Setelah kode mesin diatur dalam batu, itu hanya berurusan dengan byte dalam memori. Panggilan fungsi non-inline harus mengasumsikan bahwa callee membaca semua memori.

Menulis ini dengan aman, tanpa UB alias ketat

The jenis GCC atributmay_alias memberikan jenis perawatan alias-apa sama char*. (Disarankan oleh @KonradBorowsk). Header GCC saat ini menggunakannya untuk tipe vektor x86 SIMD seperti __m128isehingga Anda selalu dapat melakukannya dengan aman _mm_loadu_si128( (__m128i*)foo ). (Lihat Apakah `reinterpret_cast`ing antara pointer vektor perangkat keras dan tipe yang sesuai merupakan perilaku yang tidak terdefinisi? Untuk perincian lebih lanjut tentang apa artinya ini dan yang tidak berarti.)

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

Anda juga bisa menggunakan aligned(1)untuk mengekspresikan suatu tipe alignof(T) = 1.
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;

Cara portabel untuk mengekspresikan muatan aliasing dalam ISO adalah denganmemcpy , yang oleh kompiler modern benar-benar tahu bagaimana cara inline sebagai instruksi muatan tunggal. misalnya

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

Ini juga berfungsi untuk beban yang tidak selaras karena memcpyberfungsi seolah-olah dengan charakses pada waktu tertentu. Tetapi dalam praktiknya kompiler modern memcpysangat mengerti .

Bahayanya di sini adalah bahwa jika GCC tidak tahu pasti apakah char_ptritu selaras kata, itu tidak akan menyertainya pada beberapa platform yang mungkin tidak mendukung beban yang tidak selaras dalam asm. mis. MIPS sebelum MIPS64r6, atau ARM yang lebih lama. Jika Anda mendapat panggilan fungsi sebenarnya untuk memcpyhanya memuat kata (dan meninggalkannya di memori lain), itu akan menjadi bencana. GCC terkadang dapat melihat kapan kode menyelaraskan sebuah pointer. Atau setelah loop char-at-a-time yang mencapai batas ulong yang bisa Anda gunakan
p = __builtin_assume_aligned(p, sizeof(unsigned long));

Ini tidak menghindari UB baca-lampau-objek yang mungkin, tetapi dengan GCC saat ini yang tidak berbahaya dalam praktiknya.

Mengapa sumber C yang dioptimalkan dengan tangan diperlukan: kompiler saat ini tidak cukup baik

ASM yang dioptimalkan dengan tangan bisa lebih baik lagi jika Anda menginginkan setiap tetes kinerja terakhir untuk fungsi pustaka standar yang banyak digunakan. Khusus untuk sesuatu seperti memcpy, tetapi juga strlen. Dalam hal ini tidak akan lebih mudah untuk menggunakan C dengan intrinsik x86 untuk memanfaatkan SSE2.

Tapi di sini kita hanya berbicara tentang versi C naif vs bithack tanpa fitur khusus ISA.

(Saya pikir kita bisa menganggapnya sebagai suatu pemberian yang strlencukup banyak digunakan sehingga membuatnya berjalan secepat mungkin adalah penting. Jadi pertanyaannya adalah apakah kita bisa mendapatkan kode mesin yang efisien dari sumber yang lebih sederhana. Tidak, kita tidak bisa.)

GCC dan dentang saat ini tidak mampu loop auto-vektorisasi di mana jumlah iterasi tidak diketahui sebelum iterasi pertama . (misalnya itu harus mungkin untuk memeriksa apakah loop akan menjalankan setidaknya 16 iterasi sebelum menjalankan iterasi pertama.) misalnya memcpy autovectorizing mungkin (buffer panjang-eksplisit) tetapi tidak strcpy atau strlen (string panjang-implisit), diberikan saat ini kompiler.

Itu termasuk loop pencarian, atau loop lain dengan data-dependent if()breakserta counter.

ICC (kompiler Intel untuk x86) dapat secara otomatis membuat vektor beberapa loop pencarian, tetapi masih hanya membuat ASM byte-at-a-time yang naif untuk C sederhana / naif strlenseperti penggunaan libc OpenBSD. ( Godbolt ). (Dari jawaban @ Peske ).

Libc yang dioptimalkan dengan tangan strlendiperlukan untuk kinerja dengan kompiler saat ini . Melangkah 1 byte pada satu waktu (dengan membuka gulungan mungkin 2 byte per siklus pada CPU superscalar lebar) menyedihkan ketika memori utama dapat mengimbangi sekitar 8 byte per siklus, dan cache L1d dapat mengirimkan 16 hingga 64 per siklus. (Beban 2x 32-byte per siklus pada CPU mainstream x86 modern sejak Haswell dan Ryzen. Tidak termasuk AVX512 yang dapat mengurangi kecepatan clock hanya untuk menggunakan vektor 512-bit; itulah sebabnya glibc mungkin tidak terburu-buru untuk menambahkan versi AVX512 Meskipun dengan vektor 256-bit, AVX512VL + BW bertopeng dibandingkan menjadi topeng dan ktestatau kortestbisa membuat strlenlebih ramah hyperthreading dengan mengurangi uops / iterasinya.)

Saya termasuk non-x86 di sini, itulah "16 byte". misalnya kebanyakan CPU AArch64 dapat melakukan setidaknya itu, saya pikir, dan beberapa pasti lebih. Dan beberapa memiliki throughput eksekusi yang cukup untuk strlenmengimbangi beban bandwidth tersebut.

Tentu saja program yang bekerja dengan string besar biasanya harus melacak panjang untuk menghindari keharusan mengulang menemukan panjang string C panjang implisit sangat sering. Tetapi kinerja pendek hingga menengah masih mendapat manfaat dari implementasi tulisan tangan, dan saya yakin beberapa program akhirnya menggunakan strlen pada string menengah.

Itu dijelaskan dalam komentar di file yang Anda tautkan:

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

dan:

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

Dalam C, dimungkinkan untuk menjelaskan secara terperinci tentang efisiensi.

Kurang efisien untuk beralih melalui karakter individual yang mencari nol daripada menguji lebih dari satu byte pada suatu waktu, seperti yang dilakukan kode ini.

Kompleksitas tambahan berasal dari keharusan untuk memastikan bahwa string yang diuji selaras di tempat yang tepat untuk mulai menguji lebih dari satu byte pada suatu waktu (sepanjang batas kata kunci, seperti yang dijelaskan dalam komentar), dan dari kebutuhan untuk memastikan bahwa asumsi tentang ukuran tipe data tidak dilanggar ketika kode tersebut digunakan.

Dalam sebagian besar (tetapi tidak semua) pengembangan perangkat lunak modern, perhatian terhadap detail efisiensi tidak diperlukan, atau tidak sebanding dengan biaya kompleksitas kode tambahan.

Satu tempat di mana masuk akal untuk memperhatikan efisiensi seperti ini adalah di perpustakaan standar, seperti contoh yang Anda tautkan.

Jika Anda ingin membaca lebih lanjut tentang batasan kata, lihat pertanyaan ini , dan halaman wikipedia yang luar biasa ini

Selain jawaban yang bagus di sini, saya ingin menunjukkan bahwa kode yang ditautkan dalam pertanyaan adalah untuk implementasi GNU strlen.

The OpenBSD pelaksanaanstrlen sangat mirip dengan kode diusulkan dalam pertanyaan. Kompleksitas implementasi ditentukan oleh penulis.

...
#include <string.h>

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

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

DEF_STRONG(strlen);

EDIT : Kode OpenBSD yang saya tautkan di atas terlihat menjadi implementasi mundur untuk ISA yang tidak memiliki implementasi asm sendiri. Ada implementasi berbeda strlentergantung pada arsitektur. Kode untuk amd64strlen , misalnya, adalah asm. Mirip dengan komentar / jawaban PeterCordes yang menunjukkan bahwa implementasi GNU yang tidak mundur juga sama.

Singkatnya, ini adalah pengoptimalan kinerja yang dapat dilakukan oleh perpustakaan standar dengan mengetahui kompiler mana yang dikompilasi - Anda tidak boleh menulis kode seperti ini, kecuali jika Anda menulis perpustakaan standar dan dapat bergantung pada kompiler tertentu. Secara khusus, itu memproses jumlah penyelarasan byte pada saat yang sama - 4 pada platform 32-bit, 8 pada platform 64-bit. Ini berarti bisa 4 atau 8 kali lebih cepat dari iterasi byte yang naif.

Untuk menjelaskan bagaimana cara kerjanya, pertimbangkan gambar berikut. Asumsikan platform 32-bit di sini (perataan 4 byte).

Katakanlah huruf "H" dari "Halo, dunia!" string disediakan sebagai argumen untuk strlen. Karena CPU suka memiliki hal-hal yang disejajarkan dalam memori (idealnya, address % sizeof(size_t) == 0), byte sebelum perataan diproses byte-by-byte, menggunakan metode lambat.

Kemudian, untuk setiap potongan sejajar, dengan menghitung (longbits - 0x01010101) & 0x80808080 != 0memeriksa apakah ada byte dalam integer adalah nol. Perhitungan ini memiliki false positive ketika setidaknya satu byte lebih tinggi daripada 0x80, tetapi lebih sering tidak bekerja. Jika bukan itu masalahnya (seperti di daerah kuning), panjangnya bertambah dengan ukuran pelurusan.

Jika salah satu byte dalam bilangan bulat ternyata nol (atau 0x81), maka string diperiksa byte-by-byte untuk menentukan posisi nol.

Ini dapat membuat akses di luar batas, namun karena itu berada dalam penyelarasan, itu lebih mungkin daripada tidak menjadi masalah, unit pemetaan memori biasanya tidak memiliki tingkat ketepatan byte.

Anda ingin kode menjadi benar, dapat dipelihara, dan cepat. Faktor-faktor ini memiliki kepentingan yang berbeda:

"benar" sangat penting.

"maintainable" tergantung pada seberapa banyak Anda akan mempertahankan kode: strlen telah menjadi fungsi pustaka C Standar selama lebih dari 40 tahun. Itu tidak akan berubah. Oleh karena itu, pemeliharaan tidak begitu penting - untuk fungsi ini.

"Cepat": Dalam banyak aplikasi, strcpy, strlen dll. Menggunakan waktu eksekusi yang signifikan. Untuk mencapai perolehan kecepatan keseluruhan yang sama seperti ini rumit, tetapi implementasi strlen tidak terlalu rumit dengan meningkatkan compiler akan mengambil upaya heroik.

Menjadi cepat memiliki keuntungan lain: Ketika programmer mengetahui bahwa memanggil "strlen" adalah metode tercepat mereka dapat mengukur jumlah byte dalam sebuah string, mereka tidak tergoda lagi untuk menulis kode mereka sendiri untuk membuat segalanya lebih cepat.

Jadi untuk strlen, kecepatan jauh lebih penting, dan rawatan jauh lebih penting, daripada kebanyakan kode yang pernah Anda tulis.

Kenapa harus begitu rumit? Katakanlah Anda memiliki string 1.000 byte. Implementasi yang sederhana akan memeriksa 1.000 byte. Implementasi saat ini kemungkinan akan memeriksa 64 bit kata pada satu waktu, yang berarti 125 64 bit atau delapan byte kata. Bahkan mungkin menggunakan instruksi vektor memeriksa katakan 32 byte pada suatu waktu, yang akan menjadi lebih rumit dan bahkan lebih cepat. Menggunakan petunjuk vektor mengarah ke kode yang sedikit lebih rumit tetapi cukup mudah, memeriksa apakah satu dari delapan byte dalam kata 64 bit adalah nol memerlukan beberapa trik pintar. Jadi untuk string menengah ke panjang kode ini dapat diharapkan sekitar empat kali lebih cepat. Untuk fungsi yang sama pentingnya dengan strlen, itu layak untuk menulis fungsi yang lebih kompleks.

PS. Kode ini tidak terlalu portabel. Tetapi ini adalah bagian dari pustaka C Standar, yang merupakan bagian dari implementasinya - tidak harus portabel.

PPS. Seseorang memposting contoh di mana alat debugging mengeluhkan mengakses byte melewati akhir string. Implementasi dapat dirancang yang menjamin hal-hal berikut: Jika p adalah pointer yang valid ke byte, maka setiap akses ke byte dalam blok yang sama yang akan didefinisikan perilaku menurut standar C, akan mengembalikan nilai yang tidak ditentukan.

PPPS. Intel telah menambahkan instruksi ke prosesor mereka nanti yang membentuk blok penyusun untuk fungsi strstr () (menemukan substring dalam sebuah string). Deskripsi mereka membingungkan, tetapi mereka dapat membuat fungsi tertentu itu 100 kali lebih cepat. (Pada dasarnya, diberikan array yang berisi "Halo, dunia!" Dan array b dimulai dengan 16 byte "HelloHelloHelloH" dan mengandung lebih banyak byte, ini menunjukkan bahwa string a tidak muncul di b lebih awal daripada memulai pada indeks 15) .

Secara singkat: memeriksa string byte demi byte akan berpotensi lambat pada arsitektur yang dapat mengambil jumlah data yang lebih besar sekaligus.

Jika pemeriksaan untuk penghentian nol dapat dilakukan berdasarkan 32 atau 64 bit, itu mengurangi jumlah pemeriksaan yang harus dilakukan oleh kompiler. Itulah yang coba dilakukan oleh kode tertaut, dengan sistem tertentu. Mereka membuat asumsi tentang pengalamatan, perataan, penggunaan cache, pengaturan kompiler non-standar dll.

Membaca byte demi byte seperti pada contoh Anda akan menjadi pendekatan yang masuk akal pada CPU 8 bit, atau ketika menulis lib portabel yang ditulis dalam standar C.

Melihat C standar libs untuk saran cara menulis kode yang cepat / baik bukan ide yang baik, karena itu akan non-portabel dan bergantung pada asumsi non-standar atau perilaku yang tidak jelas. Jika Anda seorang pemula, membaca kode seperti itu kemungkinan akan lebih berbahaya daripada mendidik.

Satu hal penting yang tidak disebutkan oleh jawaban lain adalah bahwa FSF sangat berhati-hati dalam memastikan bahwa kode hak milik tidak membuatnya menjadi proyek-proyek GNU. Dalam Standar Pengkodean GNU dalam Rujukan ke Program Kepemilikan , ada peringatan tentang pengorganisasian implementasi Anda dengan cara yang tidak dapat dikacaukan dengan kode kepemilikan yang ada:

Jangan dalam keadaan apa pun merujuk ke kode sumber Unix untuk atau selama pekerjaan Anda di GNU! (Atau ke program berpemilik lainnya.)

Jika Anda memiliki ingatan samar-samar tentang internal dari program Unix, ini tidak berarti Anda tidak dapat menulis tiruannya, tetapi cobalah untuk mengatur imitasi secara internal di sepanjang garis yang berbeda, karena ini cenderung membuat perincian dari versi Unix tidak relevan dan berbeda dengan hasil Anda.

Sebagai contoh, utilitas Unix umumnya dioptimalkan untuk meminimalkan penggunaan memori; jika Anda memilih kecepatan , program Anda akan sangat berbeda.

(Penekanan milikku.)