Минимальный размер кода операции x86-64 strlen реализация
Я исследую реализацию минимального размера кода операции x86-64 strlen для моего исполняемого кода / исполняемого двоичного кода, размер которого не должен превышать некоторый размер (для простоты рассмотрим демосцену).
Общая идея исходит отсюда, идеи оптимизации размера здесь и здесь.
Адрес входной строки находится в rdi максимальная длина не должна превышать Int32
xor eax,eax ; 2 bytes
or ecx,-1 ; 3 bytes
repne scasb ; 2 bytes
not ecx ; 2 bytes
dec ecx ; 2 bytes
Конечный результат в ecx всего 11 байтов.
Вопрос по настройке ecx в -1
Вариант 1 уже заявлен
or ecx,-1 ; 3 bytes
Вариант 2
lea ecx,[rax-1] ; 3 bytes
Вариант 3
stc ; 1 byte
sbb ecx,ecx ; 2 bytes
Вариант 4, вероятно, самый медленный
push -1 ; 2 bytes
pop rcx ; 1 byte
Я это понимаю:
Вариант 1 зависит от предыдущего ecx значение
Вариант 2 зависит от предыдущего rax значение
Вариант 3 Я не уверен, имеет ли он зависимость от предыдущего ecx значение?
Вариант 4 самый медленный?
Здесь есть явный победитель?
Критерий заключается в том, чтобы размер кода операции был как можно меньшим, и выбирайте наилучший вариант с точки зрения производительности.
Я полностью осознаю, что есть реализации, использующие современные инструкции процессора, но этот устаревший подход кажется самым маленьким.
2 ответа
Для взломанной достаточно хорошей версии мы знаем rdi имеет действительный адрес. Очень вероятно, что edi не маленькое целое число, таким образом, 2 байта mov ecx, edi, Убедитесь, что это безопасно для всех call-сайтов перед использованием!
Это здорово, если вы просто хотите, чтобы rdi указывал на окончание 0 байт, вместо того, чтобы фактически нуждаться в подсчете. Или, если у вас есть стартовый указатель в другом регистре, так что вы можете сделать sub edi, edx или что-то и получить длину таким образом, вместо обработки rcx результат. (Если вы знаете, что результат умещается в 32 бита, вам не нужно sub rdi, rdx потому что вы знаете, что старшие биты в любом случае будут равны нулю. И высокие входные биты не влияют на низкие выходные биты для add/sub; нести распространяется слева направо.)
Для строк размером менее 255 байт можно использовать mov cl, -1 (2 байта). Что делает rcx по крайней мере 0xFF, и выше, в зависимости от того, какой высокий мусор был оставлен в нем. (Это приводит к частичной остановке на Nehalem и более ранних версиях при чтении RCX, в противном случае это просто зависимость от старого RCX). Во всяком случае, тогда mov al, -2 / sub al, cl чтобы получить длину в виде 8-битного целого числа. Это может или не может быть полезным.
В зависимости от абонента, rcx возможно, уже содержал значение указателя, и в этом случае вы могли бы оставить его нетронутым, если вы можете использовать вычитание указателя.
Из предложенных вами вариантов
lea ecx,[rax-1] это очень хорошо, потому что вы просто обнулены eax и это дешевая инструкция на 1 моп с задержкой в 1 цикл, которая может выполняться на нескольких портах исполнения на всех основных процессорах.
Если у вас уже есть другой регистр с известным постоянным значением, особенно с нулевым значением, 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 размера операнда, или вы можете сделать два сравнения dword, перекрывающихся на 1 байт. лайк cmp dword [rdi], first_4_bytes / jne; cmp dword [rdi+3], last_4_bytes / jne,
Подробнее о LEA
На процессоре семейства Sandybridge lea может быть отправлен в исполнительный блок в том же цикле, что и xor -зеро были введены в ядро процессора вышедшего из строя. xor Обнуление обрабатывается на этапе выдачи / переименования, поэтому моп входит в ROB в "уже выполненном" состоянии. Для инструкции невозможно когда-либо ждать RAX. (Если не произойдет прерывание между XOR и lea, но даже тогда я думаю, что будет инструкция по сериализации после восстановления RAX и до lea мог выполнить, поэтому он не мог застрять в ожидании.)
просто lea может работать на port0 или port1 на SnB, или port1 / port5 на Skylake (2 на тактовую пропускную способность, но иногда разные порты на разных CPU семейства SnB). Это задержка 1 цикла, поэтому трудно сделать намного лучше.
Вряд ли вы увидите какое-либо ускорение от использования mov ecx, -1 (5 байт), который может работать на любом порту ALU.
На AMD Ризен, lea r32, [m] в 64-битном режиме рассматривается как "медленный" LEA, который может работать только на 2 портах, и имеет задержку 2 c вместо 1. Хуже того, Ryzen не устраняет обнуление xor.
Тест микробенчмарка, который вы провели, измеряет пропускную способность только для версий без ложных зависимостей, без задержки. Это часто полезная мера, и вы случайно получили правильный ответ, который lea это лучший выбор.
Вопрос о том, точно ли чистая пропускная способность отражает что-либо в вашем реальном случае, - это другой вопрос. На самом деле вы можете зависеть от задержки, а не от пропускной способности, если сравнение строк находится на критическом пути как часть длинной или переносимой циклом цепочки зависимостей данных, не нарушенной jcc чтобы дать вам предсказание ветвления + умозрительное исполнение. (Но код без ответвлений часто больше, поэтому это маловероятно).
stc / sbb ecx,ecx интересно, но лечат только процессоры AMD sbb как нарушение зависимости (только в зависимости от CF, а не целочисленного регистра). На Intel Haswell и ранее, sbb это инструкция 2 uop (потому что она имеет 3 входа: 2 целых числа GP + флаги). У него задержка 2с, поэтому он так плохо работает. (Задержка представляет собой депонированную цепочку.)
Укорочение других частей последовательности
В зависимости от того, что вы делаете, вы можете использовать strlen+2 точно так же, но смещая другую константу или что-то. dec ecx только 32 байта в коде, но x86-64 не имеет краткой формы inc/dec инструкции. Так что не / dec не так круто в 64-битном коде.
После repne scas, у тебя есть ecx = -len - 2 (если вы начали с ecx = -1), and не gives you -x-1 (i.e. + лен + 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 последовательностей инструкций asm и повторяю их 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 нс
xor eax,eax
or ecx,-1
321-355 нс
xor eax,eax
push -1
pop rcx
322-359 нс
xor eax,eax
stc
sbb ecx,ecx
612-692 нс