Zoptymalizowana implementacja strcmp

Question

Ta funkcja została znaleziona here. Jest to realizacja strcmp:

int strcmp(const char* s1, const char* s2) 
{ 
    while (*s1 && (*s1 == *s2)) 
     s1++, s2++; 
    return *(const unsigned char*)s1 - *(const unsigned char*)s2; 
} 

Rozumiem wszystko, ale w ostatnim wierszu, w skrócie, co dzieje się w ostatnim wierszu?

Answer 1

return *(const unsigned char*)s1-*(const unsigned char*)s2; 

OP: w skrócie, co dzieje się w ostatniej linii?

A: Porównywana jest pierwsza potencjalna różnica między łańcuchami. Zarówno chars są określane jako unsigned char zgodnie z wymaganiami specyfikacji. Te 2 są promowane na int, a różnica jest zwracana.

---

Uwagi:

1 znak wartości zwracanej za (< 0, 0> 0) jest najbardziej znaczącym elementem. Jest to jedyna część określona przez specyfikację C.

2 W niektórych systemach char jest signed (bardziej powszechne). Na innych numer char to unsigned. Określenie "znaku" ostatniego porównania promuje przenośność. Zauważ, że fgetc() uzyskuje znaki jako unsigned char.

3 Poza tym, że ciąg kończy się na \0, kodowanie użytych znaków (podobnie jak w ASCII - najczęściej), nie robi różnicy na poziomie binarnym. Jeśli pierwsze char s, które różnią się 2 ciągami mają wartości 65 i 97, pierwszy ciąg będzie mniejszy niż drugi, nawet jeśli kodowanie znaków nie jest ASCII.OTOH, strcmp("A", "a") zwróci liczbę ujemną, gdy kodowanie znaków ASCII, ale może wrócić liczbę dodatnią w innym kodowaniu znaków do ich wartości bazowych i porządku nie są zdefiniowane przez C.

Answer 2

strcmp zwraca łańcuch, który jest większy niż drugi, nie tylko to, czy są one równe.

Ostatni wiersz odejmuje pierwszy niezgodny znak, aby zobaczyć, który jest większy. Jeśli cały ciąg pasuje, to będzie to 0-0=0, co daje wynik "równy".

Ta implementacja nie jest bardzo dobrze zoptymalizowany, jako, że weźmie kod montaż i wiedzy cache linii, wielkości wsadu itp

Answer 3

Ta implementacja nie jest zdecydowanie optymalizacji wbudowanej strcmp, jest po prostu inna wdrożenie i uważam, że najprawdopodobniej będzie działać gorzej niż wersja wbudowana.

Funkcja porównania ma zwrócić 0, jeśli porównywane wartości są równe, dowolna liczba ujemna, jeśli pierwsza wartość jest mniejsza, a dowolna liczba dodatnia, jeśli pierwsza wartość jest większa. I to właśnie dzieje się na ostatniej linii.

Ideą ostatniej linii jest rzucanie znaków na niepodpisane znaki i uważam, że autor miał na celu posortowanie niestandardowych znaków po znakach standardowych (kody ASCII 0-127).

EDYCJA: nie ma błędu w kodzie i może zwracać wartości ujemne, jeśli wartość wskazywana przez s1 jest mniejsza niż wartość wskazywana przez s2 zamawianie znaków standardowych przed znakami o kodzie 128 i wyższym.

Answer 4

jestem preferujących ten kod:

int strcmp(const char *str1, const char *str2) 
{ 
    int s1; 
    int s2; 
    do { 
     s1 = *str1++; 
     s2 = *str2++; 
     if (s1 == 0) 
      break; 
    } while (s1 == s2); 
    return (s1 < s2) ? -1 : (s1 > s2); 
} 

dla ARMv4 to skompilowane jako:

strcmp: 
    ldrsb r3, [r0], #1 ;r3 = *r0++ 
    ldrsb r2, [r1], #1 ;r2 = *r1++ 
    cmp  r3, #0  ;compare r3 and 0 
    beq  @1   ;if r3 == 0 goto @1 
    cmp  r3, r2  ;compare r3 and r2 
    beq  strcmp  ;if r3 == r2 goto strcmp 
;loop is ended 
@1: 
    cmp  r3, r2  ;compare r3 and r2 
    blt  @2   ;if r3 < r2 goto @2 
    movgt r0, #1  ;if r3 > r2 r0 = 1 
    movle r0, #0  ;if r3 <= r2 r0 = 0 
    bx  lr   ;return r0 
@2: 
    mov  r0, #-1 ;r0 = -1 
    bx  lr   ;return r0 

jak widać jest tylko 6 instrukcje poniżej pętli + atmost 5 instrukcje na końcu. Tak więc złożoność wynosi 6 * (strlen + 1) + 5.

Przenoszenie (s1 == 0) do warunku while powoduje gorszy kod maszynowy dla ARM (nie wiem dlaczego).

Answer 5

Ta implementacja może być dalej zoptymalizowany, goląc kilka porównań:

int strcmp(const char *s1, const char *s2) { 
    unsigned char c1, c2; 
    while ((c1 = *s1++) == (c2 = *s2++)) { 
     if (c1 == '\0') 
      return 0; 
    } 
    return c1 - c2; 
} 

wartość Zwrot jest 0 jeśli ciąg są identyczne włącznie kończącego zerowy bajt. Znakiem zwracanej wartości jest różnica między pierwszymi różniącymi się znakami, przekształconymi na unsigned char zgodnie ze standardem C.

• Jeśli char jest mniejszy niż int, co jest prawdą na wszystkich, ale niektórych rzadkich systemów wbudowanych, różnica ta może być obliczany za pomocą prostego odejmowania, zarówno c1 i c2 awansować int a różnica ta jest zagwarantowana w celu dopasowania w zakresie typu int.

• W systemach gdzie sizeof(int) == 1, zwracana wartość powinna być obliczona w następujący sposób:

  return (c1 < c2) ? -1 : 1;