Минимальный размер кода операции x86-64 реализация strlen

Для достаточно хорошей версии, мы знаем, что rdi имеет действительный адрес. Очень вероятно, что edi не является маленьким целым числом, поэтому 2 байта mov ecx, edi. Но это небезопасно, так как RDI может указывать сразу за границей 4GiB, поэтому трудно доказать, что это безопасно. Если вы не используете ILP32 ABI, такой как x32, поэтому все указатели находятся ниже отметки 4 ГБ.

Поэтому вам может понадобиться скопировать полный RDI с помощью push rdi/pop rcx, по 1 байту каждый. Но это добавляет дополнительную задержку для запуска коротких строк. Это должно быть безопасно, если у вас нет строк, длина которых превышает их начальный адрес. (Но это правдоподобно для статического хранения в .data, .bss или .rodata, если у вас есть какие-то огромные массивы; например, исполняемые файлы Linux, отличные от PIE, загружаются со скоростью около 0x401000 = 1‹‹22. )

Это замечательно, если вы просто хотите, чтобы rdi указывал на завершающий 0 байт, вместо того, чтобы фактически нуждаться в подсчете. Или, если у вас есть начальный указатель в другом регистре, вы можете сделать sub edi, edx или что-то в этом роде и таким образом получить длину вместо обработки результата rcx. (Если вы знаете, что результат умещается в 32 бита, вам не нужно sub rdi, rdx, потому что вы знаете, что старшие биты этого числа в любом случае будут равны нулю. И высокие входные биты не влияют на младшие выходные биты для добавления/подчинения; перенос распространяется влево на Правильно.)

Для строк, длина которых менее 255 байт, вы можете использовать mov cl, -1 (2 байта). Это делает rcx как минимум 0xFF и выше в зависимости от того, какой высокий мусор в нем остался. (Это имеет остановку частичной регистрации на Nehalem и ранее, когда читается RCX, в противном случае это просто зависимость от старого RCX). В любом случае, затем mov al, -2/sub al, cl, чтобы получить длину в виде 8-битного целого числа. Это может быть или не быть полезным.

В зависимости от вызывающего объекта rcx может уже содержать значение указателя, и в этом случае вы можете оставить его нетронутым, если можете использовать вычитание указателя.

Из предложенных вами вариантов

lea ecx,[rax-1] очень хорош, потому что вы только что обнулили eax с помощью xor, и это дешевая инструкция 1 uop с задержкой в ​​1 цикл и может работать на нескольких портах выполнения на всех основных процессорах.

Когда у вас уже есть другой регистр с известным значением константы, особенно с обнулением с помощью xor, 3-байтовый lea почти всегда является наиболее эффективным 3-байтовым способом создания константы, если он работает. (См. Установить все биты в регистре ЦП на 1 эффективно).

Я полностью осведомлен о том, что существуют реализации, использующие современные инструкции процессора, но этот устаревший подход кажется самым маленьким.

Да, repne scasb очень компактен. Накладные расходы на его запуск составляют около 15 циклов на типичном процессоре Intel, и, согласно Agner Fog, >=6n uops с пропускной способностью >= 2n циклов, где n — это количество (т. е. 2 цикла на байт, которые сравниваются для длинных сравнений, где начальные накладные расходы скрыты), поэтому это затмевает стоимость lea.

Что-то с ложной зависимостью от ecx может задержать его запуск, поэтому вам определенно нужен lea.

repne scasb, вероятно, достаточно быстр для того, что вы делаете, но он медленнее, чем pcmpeqb / pmovmsbk / cmp. Для коротких строк фиксированной длины целое число cmp / jne очень подходит, когда длина составляет 4 или 8 байтов (включая завершающий 0), при условии, что вы можете безопасно перечитать ваши строки, то есть вам не нужно беспокоиться о "" в конце страницы. Однако у этого метода есть накладные расходы, которые масштабируются с длиной строки. Например, для длины строки = 7 вы можете указать размеры операнда 4, 2 и 1 или выполнить два сравнения двойных слов, перекрывающихся на 1 байт. как cmp dword [rdi], first_4_bytes / jne; cmp dword [rdi+3], last_4_bytes / jne.

Подробнее о LEA

На ЦП семейства Sandybridge lea можно было отправить исполнительному блоку в том же цикле, что и xor-ноль, которые были отправлены в неисправное ядро ​​ЦП. xor-обнуление обрабатывается на этапе выдачи/переименования, поэтому uop входит в ROB в состоянии "уже выполнено". Невозможно, чтобы инструкции когда-либо приходилось ждать RAX. (Если между xor и lea не произойдет прерывание, но даже в этом случае я думаю, что после восстановления RAX и до того, как lea, будет выполняться инструкция сериализации, поэтому она не может застрять в ожидании.)

Простой lea может работать на порту 0 или порте 1 на SnB или порте 1/порте 5 на Skylake (пропускная способность 2 на такт, но иногда разные порты на разных процессорах семейства SnB). Это задержка в 1 цикл, поэтому трудно сделать намного лучше.

Маловероятно, что вы увидите ускорение от использования mov ecx, -1 (5 байт), который может работать на любом порту ALU.

На AMD Ryzen lea r32, [m] в 64-битном режиме рассматривается как «медленный» LEA, который может работать только на 2 портах и ​​имеет задержку 2c вместо 1. Хуже того, Ryzen не устраняет обнуление xor.

Проведенный вами микротест измеряет только пропускную способность для версий без ложных зависимостей, а не задержку. Часто это полезная мера, и вы получили правильный ответ, что lea — лучший выбор.

Другой вопрос, точно ли чистая пропускная способность отражает что-либо о вашем реальном сценарии использования. На самом деле вы можете зависеть от задержки, а не от пропускной способности, если сравнение строк находится на критическом пути как часть длинной или циклической цепочки зависимостей данных, не разорванной jcc, чтобы дать вам предсказание ветвления + спекулятивное выполнение. (Но код без ответвлений часто больше, так что это маловероятно).

stc / sbb ecx,ecx интересно, но только процессоры AMD рассматривают sbb как нарушение зависимости (только в зависимости от CF, а не целочисленного регистра). В Intel Haswell и более ранних версиях sbb является инструкцией из 2 операций (поскольку она имеет 3 входа: 2 целых числа GP + флаги). У него задержка 2c, поэтому он так плохо работает. (Задержка — это петлевая цепочка отложений.)

Сокращение других частей последовательности

В зависимости от того, что вы делаете, вы можете использовать strlen+2 точно так же, но компенсируя другую константу или что-то в этом роде. dec ecx занимает всего 1 байт в 32-битном коде, но в x86-64 нет сокращенных инструкций inc/dec. Так что not / dec не так крут в 64-битном коде.

После repne scas у вас есть ecx = -len - 2 (если вы начали с ecx = -1), а not дает вам -x-1 (то есть +len + 2 - 1).

 ; eax = 0
 ; ecx = -1
repne scasb      ; ecx = -len - 2
sub   eax, ecx   ; eax = +len + 2

Я сделал несколько тестов на Intel Core i7 4850HQ Haswell 2,3 ГГц, релизная сборка без отладчика. В каждом цикле я измеряю 1000 последовательностей ассемблерных инструкций и повторяю их 10 миллионов раз, чтобы усреднить результат.

Я сделал макросы для повторения ассемблерных инструкций 100 раз.

#define lea100 asm{xor   eax,eax};asm { lea ecx,[rax-1] }; // <== Copy pasted 100times
#define or100 asm{xor   eax,eax};asm { or ecx,-1 }; // <== Copy pasted 100times
#define sbb100 asm{xor   eax,eax};asm { stc };asm{sbb ecx,ecx}; // <== Copy pasted 100times
#define stack100 asm ("xor %eax,%eax;.byte 0x6A; .byte 0xFF ;pop %rcx;"); // <== Copy pasted 100times

Тестирование кода C со встроенным ассемблером для MacOS

#include <stdio.h>
#include <CoreServices/CoreServices.h>
#include <mach/mach.h>
#include <mach/mach_time.h>
int main(int argc, const char * argv[]) {
    uint64_t        start;
    uint64_t        end;
    uint64_t        elapsed;
    Nanoseconds     elapsedNano;

    uint64_t sum = 0;
    for (int i = 0; i < 10000000 ; i++) {

// this will become
// call       imp___stubs__mach_absolute_time  
// mov        r14, rax
    start = mach_absolute_time();

//10x lea100 for example for total 1000 

// call       imp___stubs__mach_absolute_time
// sub        rax, r14
    end = mach_absolute_time();

    elapsed = end - start;
    elapsedNano = AbsoluteToNanoseconds( *(AbsoluteTime *) &elapsed );
    uint64_t nano = * (uint64_t *) &elapsedNano;
        sum += nano;
    }
    printf("%f\n",sum/10000000.0);
    return 0;
}

Результаты

xor eax,eax
lea ecx,[rax-1]

205-216 ns

xor eax,eax
or ecx,-1

321-355 ns

xor eax,eax
push -1 
pop rcx 

322-359 ns

xor eax,eax
stc     
sbb ecx,ecx

612-692 ns