source

glibc의 stren은 왜 이렇게 복잡해야 빨리 실행할 수 있나요?

goodcode 2022. 9. 1. 23:14
반응형

glibc의 stren은 왜 이렇게 복잡해야 빨리 실행할 수 있나요?

strlen코드에 사용되는 최적화가 정말 필요한가요?예를 들어, 왜 다음과 같은 것이 똑같이 좋거나 더 낫지 않을까?

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

컴파일러가 최적화하기 위해서는 단순한 코드가 더 낫거나 더 간단하지 않습니까?

★★★의 strlen링크 뒤에 있는 페이지의 내용은 다음과 같습니다.

/* Copyright (C) 1991, 1993, 1997, 2000, 2003 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Written by Torbjorn Granlund (tege@sics.se),
   with help from Dan Sahlin (dan@sics.se);
   commentary by Jim Blandy (jimb@ai.mit.edu).

   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)

이 버전이 빨리 실행되는 이유는 무엇입니까?

불필요한 일을 많이 하고 있지 않나요?

특히 C 컴파일러/표준 라이브러리 벤더가 아닌 경우에는 이러한 코드를 작성할 필요가 없습니다.구현에 사용되는 코드입니다.strlen매우 의심스러운 속도 해크와 가정(주장을 사용하여 테스트하거나 코멘트에 언급되지 않음):

  • unsigned long 4 bytes 4 입니다.
  • 바이트는 8비트입니다.
  • unsigned long long anduintptr_t
  • 2 또는 3의 최하위 비트가 0인지 확인하는 것만으로 포인터를 정렬할 수 있습니다.
  • 에 할 수 unsigned longs
  • 배열의 끝을 읽어도 악영향은 없습니다.

게다가 좋은 컴파일러는 다음과 같이 기술된 코드를 대체할 수도 있습니다.

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

.size_tstrlen또는 코드를 벡터화하지만 컴파일러는 복잡한 버전을 최적화할 수 없습니다.

strlenC11 7.24.6.3에서는, 다음과 같이 기술되고 있습니다.

묘사

  1. strlen함수는 가 가리키는 문자열의 길이를 계산합니다.

돌아온다

  1. strlen기능하다

이 ''로 '''로 수 있습니다.s문자열과 종단 NUL을 포함할 수 있을 정도의 길이의 문자 배열에 있었습니다.예를 들어 다음과 같이 null 터미네이터를 통해 문자열에 액세스하면 동작은 정의되지 않습니다.

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

따라서 완전 포터블/표준 준거 C에서 이를 올바르게 구현하려면 간단한 변환을 제외하고 질문에 기재된 방법밖에 없습니다.루프를 풀어서 더 빠른 척 할 수 있지만, 그래도 한 번에 한 바이트씩 해야 합니다.

(평론가들이 지적한 바와 같이 엄격한 휴대성이 너무 부담스러운 경우 합리적이거나 이미 알려진 안전한 가정을 이용하는 것이 항상 나쁜 것은 아닙니다.특히 코드에서는 특정 C 구현의 일부입니다.그러나 규칙을 어떻게/언제 구부릴 수 있는지 알기 전에 규칙을 이해해야 합니다.)

된 " " "strlen합니다.unsigned longC 표준에서는 올바르게 정렬되지 않은 포인터에 액세스하는 것은 동작을 정의하지 않았기 때문에 다음 더러운 트릭을 위해 반드시 수행해야 합니다.(x86 이외의 일부 CPU 아키텍처에서는 잘못 정렬된 워드 또는 더블 워드 로드에 장애가 발생합니다.C는 휴대용 어셈블리 언어가 아니지만 이 코드는 이 방법으로 사용합니다).또한 메모리 보호가 정렬된 블록으로 작동하는 구현(예: 4kiB 가상 메모리 페이지)에서 장애 위험 없이 개체의 끝을 읽을 수 있습니다.

다음은 더러운 부분입니다.코드는 약속을 어기고 한 번에4 또는 8비트의 8비트를 읽습니다.long int부호 없는 추가가 포함된 비트트릭을 사용하여 이들 4바이트 또는8바이트 내에 0바이트가 존재하는지 여부를 빠르게 판별할 수 있습니다.이것에 의해, 비트 마스크에 의해서 캐리어 비트가 잡히는 비트가 변경되도록 특별히 세공된 숫자가 사용됩니다.기본적으로 마스크 내의 4바이트 또는8바이트 중 하나가 이들 각 바이트를 루핑하는 것보다 아마도 더 빠른 제로인지 아닌지를 알 수 있습니다.마지막으로 어떤 바이트가 첫 번째 0(있는 경우)인지 확인하고 결과를 반환하기 위한 루프가 끝부분에 있습니다.

큰 는 '어디서나 하다'에.sizeof (unsigned long) - 1 아웃 ★★★★★★★★★★★★★★★★★★★★」sizeof (unsigned long)대소문자는 문자열의 끝을 지나 읽습니다.- null 바이트가 마지막으로 액세스한 바이트(리틀 엔디안에서는 가장 중요하며 빅 엔디안에서는 가장 중요하지 않음)에 있는 경우에만 경계를 벗어난 배열에 액세스하지 않습니다.

「」를 실장하기 만,strlenC 표준 라이브러리는 악성 코드입니다.여기에는 구현 정의 및 정의되지 않은 여러 측면이 있습니다.시스템이 제공하는 것이 아니라 어디서도 사용할 수 없습니다.strlen을 '·········································로 바꿨습니다.the_strlen.main:

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

하게 「」를 할 수 .hello world 및 string을 합니다., 에서는, 「」, 「64」가 사용되고 있습니다.unsigned long는 8바이트이기 때문에 후자 부분에 대한 액세스는 이 버퍼를 초과합니다.

제제로 컴파일하면-fsanitize=undefined ★★★★★★★★★★★★★★★★★」-fsanitize=address프로그램을 실행하면 다음과 같은 결과가 나옵니다.

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

즉, 나쁜 일이 일어났다.

이에 대한 몇 가지 세부사항/배경에 대한 댓글에서 (약간 또는 전체적으로) 잘못된 추측이 많이 있었습니다.

glibc의 최적화된 C 폴백 최적화 구현을 검토하고 있습니다(수기 ASM 구현이 없는 ISA의 경우).또는 glibc 소스 트리에 남아 있는 이전 버전의 코드일 수도 있습니다.https://code.woboq.org/userspace/glibc/string/strlen.c.html은 현재 glibc git 트리에 기반한 코드 스위칭입니다.MIPS를 포함한 몇몇 주요 glibc 타깃에서 여전히 사용되고 있는 것 같습니다.(Thanks @zwol)

x86이나 ARM 등의 일반적인 ISA에서는 glibc는 손으로 쓴ASM을 사용합니다.

따라서 이 코드에 대한 변경 동기는 생각보다 낮습니다.

이 bitack 코드(https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord)는 실제 서버/하드웨어/스마트폰에서 실행되는 코드가 아닙니다.단순한 바이트 단위 루프보다 낫지만, 이 bitack도 현대의 CPU에 대한 효율적인 asm에 비하면 매우 나쁩니다(특히 x86에서는 AVX2 SIMD를 사용하면 메인 루프의 클럭 사이클당 32~64바이트를 체크할 수 있으며, 2클럭의 부하를 가진 최신 CPU의 L1d 캐시에서 데이터가 핫할 경우 32~64바이트가 허용됩니다).put. 즉, 시작 오버헤드가 지배적이지 않은 중간 크기 문자열의 경우)

하여 glibc를 해결합니다.strlen따라서 x86 내에서도 SSE2 버전(16바이트 벡터, x86-64 베이스라인)과 AVX2 버전(32바이트 벡터)이 있습니다.

x86은 벡터와 범용 레지스터 간의 효율적인 데이터 전송이 가능하기 때문에 SIMD를 사용하여 루프 제어가 데이터에 의존하는 암묵적인 길이의 문자열에서 함수를 고속화하는 데 고유(?)합니다. pcmpeqbpmovmskb그럼 한번에 16개의 개별 바이트를 테스트할 수 있습니다.

glibc에는 AdvSIMD를 사용한 것과 같은 AArch64 버전이 있습니다.또한 AArch64 CPU 버전에서는 vector->GP가 파이프라인을 등록하기 때문에 실제로는 이 바이택을 사용합니다.단, count-leading-zero를 사용하여 히트한 후 레지스터 내의 바이트를 찾고 페이지 크로스 체크 후 AArch64의 효율적인 비정렬 액세스를 활용합니다.

관련 정보:최적화를 유효하게 하면, 이 코드가 6.5배 늦어지는 이유는 무엇입니까?x86 asm의 빠른 것과 느린 것의 자세한 내용은 다음과 같습니다.strlenasm asm asm asm 가가gcc 、 gcc の （ cccc un ( ( ( ( ( ( un un un un un un un un un un un un un un un un un un un un un un un un un un un un un un un un un un un ） 。rep scasb한 번에 4바이트짜리 빗장처럼 느린 속도입니다.따라서 GCC의 인라인 스트렌 레시피는 업데이트 또는 비활성화가 필요합니다.)

Asm에는 C 스타일의 "정의되지 않은 동작"이 없습니다.메모리의 바이트에 자유롭게 액세스 할 수 있으며, 유효한 바이트를 포함한 정렬된 로드는 문제가 없습니다.메모리 보호는 페이지의 세밀한 정렬을 통해 이루어집니다. 페이지 경계를 넘지 않는 좁은 정렬된 액세스입니다.x86과 x64의 같은 페이지 내에서 버퍼의 끝을 지나 읽어도 안전한가?이 기능의 독립 실행형 비인라인 구현을 위해 이 C 해킹이 컴파일러를 생성하여 작성하는 머신 코드에도 동일한 논리가 적용됩니다.

컴파일러가 알 수 없는 비인라인 함수를 호출하기 위해 코드를 방출할 때 함수는 모든 글로벌 변수와 포인터가 있을 수 있는 메모리를 수정한다고 가정해야 합니다.즉, 주소 이스케이프를 하지 않은 로컬을 제외한 모든 것이 콜 전체에서 메모리에 동기화되어야 합니다.이는 분명히 asm으로 작성된 함수에도 적용되지만 라이브러리 함수에도 적용됩니다.링크 시간 최적화를 활성화하지 않으면 개별 변환 단위(소스 파일)에도 적용됩니다.

왜 이것이 glibc의 일부로서 안전하지만 다른 부분에서는 안전하지 않은가.

가장 중요한 요소는 이것이 다른 어떤 것에도 인라인화할 수 없다는 것입니다.안전하지 않습니다. 엄밀한 에일리어싱의 UB(읽기)가 포함되어 있습니다.char를 unsigned long*char*에일리어스는 허용되지만 그 반대는 사실이 아닙니다.

이는 사전 컴파일 라이브러리(glibc)의 라이브러리 기능입니다.발신자에의 링크 타임 최적화에서는, 인라인이 되지 않습니다.즉, 독립 실행형 버전의 경우 안전한 머신 코드를 컴파일하면 됩니다.strlen· 대안 / 일일일일일 · · · · · · · · · · 。

GNU C 라이브러리는 GCC만을 사용하여 컴파일해야 합니다.GNU 확장을 지원하지만 clang이나 ICC를 사용하여 컴파일하는 것은 지원되지 않는 것 같습니다.GCC는 C 소스 파일을 머신 코드의 오브젝트 파일로 변환하는 선행 컴파일러입니다.인터프리터가 아니기 때문에 컴파일 시에 인라인을 하지 않는 한 메모리의 바이트는 메모리의 바이트에 불과합니다.즉, 서로 다른 타입의 액세스가 서로 인라인화되지 않는 다른 함수에서 발생해도 엄밀한 에일리어싱 UB는 위험하지 않습니다.

하세요.strlen의 동작은 ISO C 표준에 의해 정의됩니다.이 함수명은 특히 구현의 일부입니다.GCC와 같은 컴파일러는 이 이름을 빌트인 함수로 취급하기도 합니다.-fno-builtin-strlen, (그래서)strlen("foo")입니다.3라이브러리의 정의는 gcc가 자신의 레시피를 삽입하거나 하지 않고 실제로 호출을 발신하기로 결정한 경우에만 사용됩니다.

컴파일 시 UB가 컴파일러에 표시되지 않으면 정상적인 머신 코드를 얻을 수 있습니다.머신 코드는 no-UB 케이스에 대해 기능해야 하며, 만약 당신이 원하더라도 asm은 발신자가 가리키는 메모리에 어떤 종류의 데이터를 넣었는지를 검출할 방법이 없습니다.

타임라이닝에서 + 하는 "작성하지 libc.a하지 않다-flto링크 타임 최적화를 메인 프로그램으로 실시합니다.)이러한 방법으로 glibc를 구축하면 실제로 이를 사용하는 타겟에서는 안전하지 않을 수 있습니다.

사실 @zwall 코멘트처럼 LTO는 glibc 자체를 빌드할 때 사용할 수 없습니다.glibc 소스 파일 간의 인라인화가 가능하면 이와 같은 "britle" 코드가 깨질 수 있기 때문입니다.(내부 용도가 몇 가지 있습니다.strlen 「」의로서 「」라고 하는 경우가 .printf□□□□□□□□★

★★★★★★★★★★★★★★★★★.strlen는 다음과 같은을 합니다.

  • CHAR_BIT 는 8의 배수입니다.모든 GNU 시스템에 해당됩니다.POSIX 2001은 동등하게 보증합니다.CHAR_BIT == 8 ( ( )이 있는 됩니다.CHAR_BIT= 16 ★★★★★★★★★★★★★★★★★」32는 "DSP" "unaligned-prolog" "0" 의 경우 sizeof(long) = sizeof(char) = 1 포인터는 정렬되어 있고, '모든 포인터는 항상 정렬되어 있기 때문입니다.p & sizeof(long)-1는 항상 제로입니다). ASC가 ASC가 가 9비트, "9비트", "12비트", "II",0x8080...잘못된 패턴입니다.
  • (아마도)unsigned long4 또는 8 바이트입니다.아니면 실제로 어떤 크기의 제품에도 효과가 있을 수 있습니다.unsigned long최대 8개의 IP 주소를 사용합니다.assert()확인하러 왔습니다.

이 두 가지는 UB가 아니라 일부 C 구현에서는 이식성이 없습니다.이 코드는 동작하는 플랫폼에서의 C 실장의 일부이므로 괜찮습니다.

다음 전제조건은 CUB입니다.

  • 유효한 바이트를 포함하는 정렬된 로드는 장애가 발생하지 않으며 실제로 원하는 오브젝트 외부의 바이트를 무시하는 한 안전합니다.(메모리 보호는 정렬된 페이지의 세밀함으로 이루어지기 때문에 모든 GNU 시스템 및 모든 일반 CPU에서 asm에서 해당됩니다.컴파일 시에 UB가 표시되지 않는 경우, x86과 x64의 같은 페이지내의 버퍼의 끝을 읽어도 안전한가?C 에서는 안전합니다.인라이닝이 없으면 이 경우가 됩니다.컴파일러는 첫 번째를 지나 읽었다는 것을 증명할 수 없습니다.0UB, C일 수 있습니다.char[]포함하는 배열{1,2,0,3}예를 들어)

이 마지막 포인트는 C 객체의 끝을 지나 읽어도 안전하다는 것입니다.현재 컴파일러가 실행 경로가 도달 불가능하다고 생각하지 않기 때문에 현재 컴파일러와 연동되어도 매우 안전합니다.하지만 어쨌든 엄밀한 에일리어스는 이것을 인라인화하면 이미 쇼스토퍼입니다.

그러면 Linux 커널의 오래된 안전하지 않은 문제가 발생합니다.memcpy 포인터 캐스팅을 사용한CPP 매크로unsigned long(gcc, 엄밀한 별칭, 공포 이야기).(현대판 Linux는-fno-strict-aliasing조심하는 대신may_alias어트리뷰트)를 참조해 주세요.

이것은 일반적으로 이러한 문제를 해결할 수 있었던 시대로 거슬러 올라갑니다.GCC3 이전에는 "인라인에 넣지 않을 때만" 경고가 없어도 매우 안전했습니다.

콜/레트 경계를 넘나들 때만 볼 수 있는 UB는 우리에게 해를 끼치지 않습니다(예:char buf[]일렬로 늘어선 것이 아니라unsigned long[]에 던지다.const char*). 일단 기계 코드가 스톤으로 설정되면 메모리의 바이트만 처리됩니다.비인라인 함수 호출은 착신측이 임의의 메모리 또는 모든 메모리를 읽는 것으로 가정해야 합니다.

엄밀한 에일리어스 UB 없이 안전하게 작성

GCC 타입의 Atribut은 타입에 대해서, 다음과 같은 에일리어스(임의)를 취급합니다.char*(@KonradBorowsk 추천).GCC 헤더는 현재 다음과 같은 x86 SIMD 벡터 타입에 사용합니다.__m128i항상 안전하게 할 수 있도록_mm_loadu_si128( (__m128i*)foo )('reinterpret_casting'은 하드웨어 SIMD 벡터포인터와 대응하는 타입의 동작이 정의되어 있지 않은지 여부를 참조해 주십시오.이것이 무엇을 의미하는지 또는 의미하지 않는지에 대한 자세한 내용은 참조하십시오.)

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

  // handle unaligned startup somehow, e.g. check for page crossing then check an unaligned word
  // else check single bytes until an alignment boundary.
  aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;

  for (;;) {
     // alignment still required, but can safely alias anything including a char[]
     unsigned long ulong = *longword_ptr++;

     ...
  }
}

사용할 수 있습니다.aligned(1)활자를 표현하다alignof(T) = 1.
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong;첫 번째 얼라인먼트 경계까지 한 번에 char-at-a-time을 실행하지 않으면 strlen의 얼라인먼트되지 않은 스타트업 부분에 도움이 될 수 있습니다.(터미네이터가 매핑 해제된 페이지 바로 앞에 있어도 문제가 발생하지 않도록 메인 루프가 정렬되어야 합니다.)

ISO에서 앨리어싱 로드를 표현하는 휴대용 방법은 를 사용하는 것입니다. 최신 컴파일러는 단일 로드 명령으로 인라인하는 방법을 알고 있습니다.

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

이는 정렬되지 않은 부하에도 유효합니다.memcpy에 준거하여 기능하다char-한 번에 접속할 수 있습니다.하지만 실제로 현대 컴파일러들은memcpy좋네요.

여기서의 위험은 GCC가 확실히 알지 못한다면char_ptr는 워드 얼라인먼트에 대응하고 있기 때문에, MIPS64r6 이전의 MIPS나 오래된 ARM 등, asm내의 비얼라인 부하를 서포트하지 않는 플랫폼에서는 인라인으로 하지 않습니다.실제 함수 호출을 받은 경우memcpy한 마디만 로드하면(다른 기억 속에 남겨두면) 큰일이 납니다.GCC는 코드가 포인터를 정렬하는 것을 확인할 수 있습니다.또는 char-at-a-time 루프가 울롱 경계에 도달한 후
p = __builtin_assume_aligned(p, sizeof(unsigned long));

이는 객체 판독이 가능한 UB를 회피하는 것이 아니라 현재의 GCC에서는 실제로는 위험하지 않습니다.

수작업으로 최적화된 C 소스가 필요한 이유: 현재 컴파일러로는 충분하지 않습니다.

수작업으로 최적화된 ASM은 널리 사용되는 표준 라이브러리 기능을 위해 마지막 한 방울의 퍼포먼스를 원할 때 더욱 우수합니다.특히 이런 거에 대해서memcpy,하지만 또한strlen이 경우 SSE2를 활용하기 위해 x86 내장 함수를 사용하는 C를 사용하는 것은 그다지 쉽지 않습니다.

여기서는 단순한 버전과 ISA 고유의 기능이 없는 bitack C 버전에 대해 설명하겠습니다.

(기정사실이라고 생각하면 될 것 같습니다.strlen충분히 널리 사용되고 있기 때문에 가능한 한 빨리 실행하는 것이 중요합니다.따라서 문제는 보다 단순한 소스에서 효율적인 기계 코드를 얻을 수 있는가 하는 것입니다.아니요, 할 수 없습니다.)

현재 GCC 및 clang에서는 첫 번째 반복 전에 반복 횟수를 알 수 없는 루프를 자동 벡터화할 수 없습니다.(예를 들어, 첫 번째 반복을 실행하기 전에 루프가 적어도 16회 반복을 실행할 수 있는지 확인할 수 있어야 합니다). 예를 들어 memcpy 자동 벡터라이징은 가능하지만 현재 컴파일러에서 strcpy 또는 strlen(표준 길이 문자열)은 불가능합니다.

여기에는 검색 루프 또는 데이터에 의존하는 다른 루프가 포함됩니다.if()break카운터도 있습니다.

ICC(인텔의 x86 컴파일러)는 일부 검색 루프를 자동 벡터화할 수 있지만 단순/순진한 C의 경우 한 번에 바이트 단위로 asm만 만듭니다.strlenOpenB처럼SD의 libc 용도. (Godbolt)(@Peske의 답변에서).

현재 컴파일러에서 성능을 발휘하려면 수작업으로 최적화된 libc가 필요합니다.메인 메모리가 사이클당 약 8바이트를 유지할 수 있고 L1d 캐시가 사이클당 16~64바이트의 부하를 제공할 수 있는 경우(Haswell 및 Ryzen 이후 최신 메인스트림 x86 CPU에서는 사이클당 32바이트의 부하 2배).512비트 벡터를 사용하는 것만으로 클럭 속도를 줄일 수 있는 AVX512는 카운트되지 않습니다.그래서 glibc는 AVX512 버전을 서둘러 추가하지 않을 것입니다.256비트 벡터의 경우 AVX512VL + BW 마스크는 마스크와ktest또는kortest할 수 있다strlenuops/repeating을 줄임으로써 하이퍼스레딩이 용이해집니다.)

여기에는 비 x86을 포함하면 "16바이트"가 포함됩니다. 예를 들어 대부분의 AArch64 CPU는 적어도 그 이상의 기능을 수행할 수 있습니다.또, 일부의 스루풋은,strlen부하 대역폭에 대응할 수 있습니다.

물론 큰 문자열로 동작하는 프로그램에서는 일반적으로 길이를 추적하여 암묵적인 길이의 C 문자열을 자주 다시 찾을 필요가 없습니다.단, 단시간에서 중간 길이의 퍼포먼스는 수기 실장에서는 여전히 이점이 있으며, 중간 길이의 문자열에서는 strlen을 사용하게 되는 프로그램도 있을 것입니다.

링크한 파일의 코멘트에 설명되어 있습니다.

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

또, 다음과 같이 합니다.

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

C에서는 효율에 대해 상세하게 추론할 수 있다.

Null을 찾는 개별 문자를 반복하는 것은 이 코드처럼 한 번에 여러 바이트를 테스트하는 것보다 효율적이지 않습니다.

테스트 대상 문자열이 한 번에 1바이트 이상 테스트를 시작하기 위해 올바른 위치에 정렬되어 있는지(댓글에서 설명한 바와 같이 긴 단어 경계에 따라), 코드를 사용할 때 데이터 유형의 크기에 대한 가정이 위반되지 않는지 확인해야 하는 경우에서 복잡성이 증가합니다.

현대의 소프트웨어 개발에서는 대부분(전부는 아니지만) 효율의 상세 내용에 주의를 기울일 필요는 없습니다.또, 코드의 복잡성에 수반하는 코스트의 코스트도 불필요합니다.

이와 같이 효율성에 주의를 기울이는 것이 타당하다고 생각되는 것은 링크한 예시와 같은 표준 라이브러리입니다.

단어 경계에 대해 더 읽고 싶다면, 이 질문과 이 훌륭한 위키피디아 페이지를 보세요.

나는 또한 위의 답변이 훨씬 더 명확하고 상세한 논의라고 생각한다.

여기에 훌륭한 답변 외에도, 질문에서 링크된 코드는 GNU의 구현에 대한 것입니다.strlen.

오픈비의 SD 실장은 질문에서 제안된 코드와 매우 유사합니다.구현의 복잡성은 작성자에 의해 결정됩니다.

...
#include <string.h>

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

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

DEF_STRONG(strlen);

편집: OpenB위에서 링크한 SD 코드는 자체 ASM 구현이 없는 ISA를 위한 폴백 구현인 것 같습니다.에는 다양한 구현이 있습니다.strlen아키텍처에 따라 달라집니다.예를 들어 amd64의 코드는 asm입니다.폴백 이외의 GNU 실장도 asm이라고 지적한 PeterCordes의 코멘트/답변과 유사합니다.

즉, 이것은 표준 라이브러리가 컴파일러를 사용하여 컴파일된 컴파일러를 인식함으로써 실행할 수 있는 퍼포먼스 최적화입니다.표준 라이브러리를 작성하고 특정 컴파일러에 의존할 수 있는 경우를 제외하고, 이와 같이 코드를 작성해서는 안 됩니다.특히 32비트 플랫폼에서는 4바이트, 64비트 플랫폼에서는 8바이트의 얼라인먼트 수를 동시에 처리합니다.즉, 순진 바이트의 반복보다 4배 또는8배 빠를 수 있습니다.

이 동작의 구조를 설명하려면 , 다음의 이미지를 참조해 주세요.여기서 32비트 플랫폼(4바이트 얼라인먼트)을 가정합니다.

예를 들어, "Hello, world!" 문자열의 문자 "H"가 다음에 대한 인수로 제공되었다고 합시다.strlenCPU는 메모리 내에 정렬된 것을 좋아하기 때문에 (이상적으로는)address % sizeof(size_t) == 0), 얼라인먼트 전의 바이트는 느린 방법으로 바이트 단위로 처리됩니다.

그런 다음 각 선형 크기 청크에 대해(longbits - 0x01010101) & 0x80808080 != 0정수 내의 바이트 중 하나가 제로인지 여부를 확인합니다.이 계산은 적어도1개의 바이트가 다음 값보다 클 때 false positive가 됩니다.0x80하지만 대부분의 경우 효과가 있을 것입니다.그렇지 않은 경우(노란색 영역과 같이) 길이가 정렬 크기만큼 증가합니다.

정수 내의 바이트 중 하나가 0으로 판명된 경우(또는)0x81그런 다음 문자열을 바이트 단위로 체크하여 0의 위치를 결정합니다.

이렇게 하면 범위를 벗어난 액세스가 가능하지만, 정렬 내에 있기 때문에 문제가 발생할 가능성이 높기 때문에 메모리 매핑 유닛은 보통 바이트 수준의 정밀도가 떨어집니다.

코드가 정확하고 유지보수가 용이하며 신속해야 합니다.이들 요인의 중요도는 다릅니다.

"올바른"은 절대적으로 중요합니다.

"유지관리 가능"은 코드를 얼마나 유지하느냐에 따라 달라집니다. strlen은 40년 이상 표준 C 라이브러리 함수였습니다.그건 변하지 않을 거야.따라서 이 함수의 경우 유지보수가 매우 중요하지 않습니다.

"고속": 많은 애플리케이션, strcpy, strlen 등상당한 양의 실행 시간을 사용합니다.컴파일러를 개선함으로써 이 복잡하지만 그다지 복잡하지 않은 strlen의 구현과 같은 전체적인 속도 향상을 달성하려면 영웅적인 노력이 필요합니다.

빠른 속도에는 또 다른 장점이 있습니다.프로그래머가 스트렌을 호출하는 것이 문자열의 바이트 수를 측정할 수 있는 가장 빠른 방법이라는 것을 알게 되면, 그들은 더 이상 일을 더 빨리 하기 위해 그들만의 코드를 쓰려는 유혹을 받지 않게 된다.

따라서 strlen의 경우 속도는 훨씬 더 중요하며 유지보수는 이제까지 작성해야 할 대부분의 코드보다 훨씬 덜 중요합니다.

왜 그렇게 복잡해야 하죠?1,000 바이트 문자열이 있다고 가정합니다.간단한 실장에서는 1,000바이트가 검사됩니다.현재 구현에서는 64비트 워드를 한 번에 검사합니다.즉, 64비트 또는8바이트 워드는 125개입니다.한 번에 32바이트를 검사하는 벡터 명령어를 사용할 수도 있습니다.이는 훨씬 더 복잡하고 더 빠릅니다.벡터 명령어를 사용하면 좀 더 복잡하지만 매우 간단한 코드로 이어집니다.64비트 워드의 8바이트 중 하나가 제로인지 여부를 확인하는 데는 몇 가지 영리한 트릭이 필요합니다.따라서 중간에서 긴 문자열의 경우 이 코드가 약 4배 더 빠를 것으로 예상됩니다.strlen만큼 중요한 함수는 더 복잡한 함수를 작성할 가치가 있습니다.

추신. 코드가 잘 휴대되지 않습니다.그러나 이것은 구현의 일부인 Standard C 라이브러리의 일부이므로 휴대할 필요가 없습니다.

PPS. 디버깅툴이 문자열의 끝을 지나 바이트에 액세스 하는 것에 대해 불만을 제기하는 예를 게재했습니다.실장은 다음 사항을 보증하도록 설계할 수 있습니다.p가 바이트에 대한 유효한 포인터일 경우 C 표준에 따라 정의되지 않은 동일한 정렬 블록 내의 바이트에 대한 접근은 지정되지 않은 값을 반환합니다.

PPPS. 인텔은 strstr() 함수의 구성 요소를 구성하는 최신 프로세서에 명령을 추가했습니다(문자열 내의 하위 문자열 검색).설명에 놀라기는 하지만 특정 함수를 100배 더 빠르게 만들 수 있습니다.(기본적으로 "Hello, world!"로 시작하는 배열 a와 16바이트 "HelloHelloH"로 시작하는 배열 b와 더 많은 바이트를 포함하는 배열 b가 지정되면 문자열 a는 인덱스에서 시작하는 것보다 b에서 먼저 발생하지 않습니다.)

간단히: 한 번에 더 많은 양의 데이터를 가져올 수 있는 아키텍처에서는 문자열 바이트를 바이트 단위로 확인하는 속도가 느려질 수 있습니다.

32비트 또는 64비트 단위로 null 종료를 체크할 수 있는 경우 컴파일러가 수행해야 하는 체크의 양이 줄어듭니다.특정 시스템을 염두에 두고 링크된 코드가 이를 시도합니다.어드레싱, 얼라인먼트, 캐시 사용, 비표준 컴파일러 셋업 등에 관한 가정을 합니다.

예시와 같이 바이트 단위로 읽는 것은 8비트 CPU에서 또는 표준 C로 작성된 휴대용 lib를 쓸 때 합리적인 방법입니다.

C standard libs에서 빠른 코드/좋은 코드 작성 방법을 알아보는 것은 좋은 생각이 아닙니다.이는 포터블이 아니기 때문에 비표준적인 가정이나 부적절한 동작에 의존하기 때문입니다.만약 당신이 초보자라면, 그러한 코드를 읽는 것은 교육적인 것보다 더 해로울 것이다.

왜 다음과 같은 것이 똑같이 좋거나 더 낫지 않을까?

// OP's code - what is needed to portably function correctly?
unsigned long strlen(char s[]) {
    unsigned long i;
    for (i = 0; s[i] != '\0'; i++)
        continue;
    return i;
}

OP의 코드에 기능 오류가 있습니다.

하지만 수정하기에 충분히 쉽다.

휴대용 코드를 작성할 때는 먼저 기능을 올바르게 설정한 후 성능 향상에 주의를 기울여야 합니다.

매우 단순하고 정확해 보이는 코드도 기능적으로 결함이 있을 수 있습니다.

유형

문자열 길이는 다음 범위 내에 있습니다.size_t와는 다를 수 있다unsigned long일치하지 않는 기능 시그니처의 문제size_t (*f)() = strlen. 일반적이지 않은 플랫폼에서의 문제:ULONG_MAX < SIZE_MAX현악기 길이도 엄청나고요.

const

s그래야 한다const char *.

비2의 보충

(이 문제는 오늘날 극히 소수의 프로세서에 영향을 미치기 때문에 실제로는 현학적 관심사일 뿐입니다.Non-2의 보완은 다음 C(C23?)에서 spec'd가 됩니다.

그s[i] != '\0'다음 경우 -0에서 트리거될 수 있습니다.char2의 보완이 아니라 서명되어 있습니다.그러면 안 돼요. str...()문자에 액세스 하는 것처럼 기능하다unsigned char.

이 하위 절의 모든 기능에 대해 각 문자는 다음과 같은 형식을 가진 것으로 해석해야 한다.unsigned char(따라서 가능한 모든 오브젝트 표현은 유효하며 값이 다릅니다).

OP의 단순 코드의 이러한 측면을 복구하려면

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

더 나은 휴대성으로 무장strlen()후보자는 "유효한" 대안과 비교할 수 있습니다.

다른 답변에서 언급되지 않은 한 가지 중요한 것은 FSF가 독점 코드가 GNU 프로젝트에 포함되지 않도록 하는 데 매우 신중하다는 것입니다.「Referencing to Proprietary Programs(독자 프로그램 참조)」의 GNU 코딩 규격에는, 기존의 독점 코드와 혼동하지 않는 방법으로 실장을 정리하는 것에 관한 경고가 기재되어 있습니다.

어떠한 경우에도 GNU에 관한 작업 중 또는 작업 중에 Unix 소스 코드를 참조하지 마십시오.

Unix 프로그램의 내부가 어렴풋이 기억난다고 해서 모조품을 쓸 수 없는 것은 아니지만, 모조품을 다른 행에 따라 내부적으로 정리하려고 하면 Unix 버전의 세부사항이 부적절하고 결과와 다를 수 있기 때문입니다.

예를 들어, Unix 유틸리티는 일반적으로 메모리 사용을 최소화하도록 최적화되어 있습니다.대신 속도를 추구한다면 프로그램은 크게 달라질 것입니다.

(내 것을 강조합니다.)

언급URL : https://stackoverflow.com/questions/57650895/why-does-glibcs-strlen-need-to-be-so-complicated-to-run-quickly

반응형

'source' 카테고리의 다른 글

컴파일러와 링커의 차이점은 무엇입니까?  (0) 2022.09.01
초기화, Guava UnmutableMap  (0) 2022.09.01
치명적인 오류: mpi.h: 해당 파일 또는 디렉토리 #이(가) 없습니다.  (0) 2022.09.01
Vuex를 사용한 비동기 콜 발신  (0) 2022.09.01
전체 새로 고침 후 항목이 표시되지 않는 Vuetify v-select  (0) 2022.09.01

'source'의 다른글

  • 현재글glibc의 stren은 왜 이렇게 복잡해야 빨리 실행할 수 있나요?

관련글

댓글

티스토리툴바