Почему memcmp намного быстрее, чем проверка цикла?

Почему memcmp(a, b, size) намного быстрее, чем:

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

Является ли memcmp инструкцией процессора или что-то еще? Он должен быть довольно глубоким, потому что я получил массивное ускорение, используя memcmp по циклу.

Ответ 1

memcmp часто реализуется в сборке, чтобы воспользоваться рядом специфических для архитектуры функций, которые могут сделать его намного быстрее, чем простой цикл в C.

Как "встроенный"

GCC поддерживает memcmp (а также тонну других функций) как builtins. В некоторых версиях/конфигурациях GCC вызов memcmp будет распознаваться как __builtin_memcmp. Вместо того, чтобы излучать функцию call в библиотеку memcmp, GCC выдаст несколько инструкций, чтобы действовать как оптимизированная встроенная версия функции.

В x86 это использует использование инструкции cmpsb, которая сравнивает строку байтов в одной ячейке памяти с другой. Это связано с префиксом repe, поэтому строки сравниваются, пока они больше не равны, или счет исчерпан. (Точно, что делает memcmp).

С учетом следующего кода:

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

gcc version 3.4.4 на Cygwin генерирует следующую сборку:

; (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)

Ссылка:

cmpsb инструкция

В качестве библиотечной функции

Во многих стандартных библиотеках C существуют высоко оптимизированные версии memcmp. Они, как правило, используют специальные инструкции для работы с большим количеством данных параллельно.

В Glibc существуют версии memcmp для x86_64, которые могут использовать следующие расширения набора инструкций:

Классная часть - это то, что glibc обнаружит (во время выполнения) новейшую инструкцию, установленную вашим процессором, и выполнит оптимизированную для нее версию. См. Этот фрагмент из 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)

В ядре Linux

Linux, похоже, не имеет оптимизированной версии memcmp для x86_64, но для memcpy, arch/x86/lib/memcpy_64.S. Обратите внимание, что использует инфраструктуру альтернатив (arch/x86/kernel/alternative.c) для не только решения во время выполнения, какая версия использовать, а фактическое исправление, чтобы сделать это решение сразу при загрузке.

Ответ 2

Является ли memcmp инструкцией CPU или что-то еще?

Это, по крайней мере, очень оптимизированная встроенная функция, предоставляемая компилятором. Возможно, одна машинная инструкция или две, в зависимости от платформы, которые вы не указали.

Ответ 3

Обычно это встроенный компилятор, который преобразуется в быструю сборку со специальными инструкциями для сравнения блоков памяти.

intcinsic memcmp

Ответ 4

Да, на оборудовании Intel есть одна инструкция сборки для такого цикла. Это будет использовать среда выполнения. (Я точно не помню, это было что-то вроде rep cmps[b|w], в зависимости также от данных)