Warum ist memcmp so viel schneller als eine For-Loop-Prüfung?

Lesezeit: 4 Minuten

Benutzeravatar von jsj
jsj

Warum ist memcmp(a, b, size) viel schneller als:

for(i = 0; i < nelements; i++) {
    if a[i] != b[i] return 0;
}
return 1;

Ist memcmp eine CPU-Anweisung oder so etwas? Es muss ziemlich tief sein, weil ich eine massive Beschleunigung mit bekommen habe memcmp über die Schleife.

  • Kompilieren Sie mit -S, um die Ausgabe in Assemblersprache anzuzeigen und herauszufinden. An x86wie andere bereits erwähnt haben, gibt es Anweisungen dafür, aber oft können diese vektorisiert werden.

    – Davislor

    21. April 2018 um 3:31 Uhr

  • Aber welche Optimierungsstufe verwenden Sie? Viele Compiler können diese Schleife aufrollen.

    – Davislor

    21. April 2018 um 3:39 Uhr

Benutzeravatar von Jonathon Reinhart
Jonathon Reinhart

memcmp wird oft in Assembly implementiert, um eine Reihe von architekturspezifischen Funktionen zu nutzen, die es machen können viel schneller als eine einfache Schleife in C.

Als „eingebaut“

GCC unterstützt memcmp (sowie eine Menge anderer Funktionen) als Einbauten. In manchen Versionen/Konfigurationen von GCC kann ein Aufruf an memcmp wird anerkannt als __builtin_memcmp. Anstatt a zu emittieren call zum memcmp Bibliotheksfunktion, gibt GCC eine Handvoll Anweisungen aus, um als optimierte Inline-Version der Funktion zu fungieren.

Auf x86 nutzt dies die Verwendung von cmpsb Anweisung, die eine Folge von Bytes an einer Speicherstelle mit einer anderen vergleicht. Dies ist gekoppelt mit der repe Präfix, sodass die Zeichenfolgen verglichen werden, bis sie nicht mehr gleich sind oder eine Anzahl erschöpft ist. (Genau was memcmp tut).

Angesichts des folgenden Codes:

int test(const void* s1, const void* s2, int count)
{
    return memcmp(s1, s2, count) == 0;
}

gcc version 3.4.4 on Cygwin generiert die folgende Assembly:

; (prologue)
mov     esi, [ebp+arg_0]    ; Move first pointer to esi
mov     edi, [ebp+arg_4]    ; Move second pointer to edi
mov     ecx, [ebp+arg_8]    ; Move length to ecx

cld                         ; Clear DF, the direction flag, so comparisons happen
                            ; at increasing addresses
cmp     ecx, ecx            ; Special case: If length parameter to memcmp is
                            ; zero, don't compare any bytes.
repe cmpsb                  ; Compare bytes at DS:ESI and ES:EDI, setting flags
                            ; Repeat this while equal ZF is set
setz    al                  ; Set al (return value) to 1 if ZF is still set
                            ; (all bytes were equal).
; (epilogue) 

Bezug:

Als Bibliotheksfunktion

Hochoptimierte Versionen von memcmp existieren in vielen C-Standardbibliotheken. Diese nutzen normalerweise architekturspezifische Anweisungen, um mit vielen Daten parallel zu arbeiten.

In Glibc gibt es Versionen von memcmp für x86_64 die die Vorteile der folgenden Befehlssatzerweiterungen nutzen können:

Der coole Teil ist, dass glibc (zur Laufzeit) den neuesten Befehlssatz Ihrer CPU erkennt und die dafür optimierte Version ausführt. Siehe diesen Ausschnitt von sysdeps/x86_64/multiarch/memcmp.S:

ENTRY(memcmp)
    .type   memcmp, @gnu_indirect_function
    LOAD_RTLD_GLOBAL_RO_RDX
    HAS_CPU_FEATURE (SSSE3)
    jnz 2f
    leaq    __memcmp_sse2(%rip), %rax
    ret 

2:  HAS_CPU_FEATURE (SSE4_1)
    jz  3f  
    leaq    __memcmp_sse4_1(%rip), %rax
    ret 

3:  leaq    __memcmp_ssse3(%rip), %rax
    ret 

END(memcmp)

Im Linux-Kernel

Linux scheint keine optimierte Version von zu haben memcmp für x86_64, aber für memcpyin arch/x86/lib/memcpy_64.S. Beachten Sie, dass verwendet wird Alternativen Infrastruktur (arch/x86/kernel/alternative.c), um nicht nur zur Laufzeit zu entscheiden, welche Version verwendet werden soll, sondern tatsächlich selber patchen diese Entscheidung nur einmal beim Booten zu treffen.

  • rep cmpsbdas ist.

    – chao

    14. Januar 2014 um 5:45 Uhr

  • Es wäre interessant, die integrierte Version mit der nicht integrierten Version zu profilieren (-fno-builtin). Irgendwann war die eingebaute Version viel langsamer. Ich weiß nicht, ob es sich verbessert hat.

    – Z-Boson

    14. Januar 2014 um 13:12 Uhr

  • IIRC-Anweisungen wie rep cmpsb sind eigentlich recht langsam. gcc generiert jetzt einen Aufruf an die libc-Version von memcmp, die (in glibc) eine optimierte asm-Implementierung hat (unter Verwendung von SIMD, nicht rep cmpsb).

    – Marc Glisse

    12. November 2014 um 15:09 Uhr


  • Das ist nicht allgemeingültig. Moderne CPUs haben eine “schnelle Zeichenfolgenoperation”-Funktion, die die rep * -Versionen wieder an die Spitze bringt. Der Linux-Kernel erkennt, ob Ihre CPU diese Funktion unterstützt, und aktualisiert den entsprechenden Code live. (Obwohl das vielleicht nur für movsb und Freunde ist)

    – Jonathon Reinhart

    12. November 2014 um 16:23 Uhr


  • Marc Glisse hat Recht; aber “schnelle Saiten” gilt nur für repnicht repz/repnz. rep movsb / rep stosb sind schnell (insbesondere mit ERMSB auf Ivybridge+), aber repz cmpsb ist nicht. Sehen agner.org/optimieren für Unterrichtstafeln: Auf Skylake, repz cmps hat eine Laufzeit von >=2n Zyklen, Einnahme >= 8n Ups. (Wo n ist die Elementanzahl, rcx wenn es bis zum Ende geht, also 1 Byte pro 2 Zyklen für cmpsb.) Aber rep movs hat einen Best-Case von 1/32B (32 Bytes pro Zyklus kopieren).

    – Peter Cordes

    27. November 2017 um 10:08 Uhr


Benutzeravatar von a_mole
ein Maulwurf

Es ist normalerweise ein intrinsischer Compiler, der in eine schnelle Assemblierung mit speziellen Anweisungen zum Vergleichen von Speicherblöcken übersetzt wird.

intrinsisches Memcmp

  • memcmp ist ein GCC eingebautnicht intrinsisch. intrinsisch bezieht sich typischerweise auf C-Level-Zugriff auf bestimmte CPU-Anweisungen.

    – Jonathon Reinhart

    14. Januar 2014 um 6:07 Uhr

  • und intrinsisch werden sie in Visual C++ genannt

    – ein Maulwurf

    14. Januar 2014 um 15:42 Uhr

Benutzeravatar von user207421
Benutzer207421

Ist memcmp eine CPU-Anweisung oder so etwas?

Es ist zumindest eine sehr stark optimierte, vom Compiler bereitgestellte intrinsische Funktion. Möglicherweise eine einzelne Maschinenanweisung oder zwei, je nach Plattform, die Sie nicht angegeben haben.

1395050cookie-checkWarum ist memcmp so viel schneller als eine For-Loop-Prüfung?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy