Наиболее важной оптимизацией, которую вы можете сделать, является использование мультипликативного обратного с фиксированной запятой для деления на константу времени компиляции: Почему GCC использует умножение на странное число при реализации целочисленного деления? .
Любой приличный компилятор C сделает это за вас, но, очевидно, Delphi этого не сделает, поэтому есть веская причина сделать это с помощью asm.
Можете ли вы вернуть значение в EAX вместо того, чтобы хранить как частное, так и остаток в памяти? Похоже на пустую трата времени, чтобы передать 2 аргумента указателя и заставить вызывающего извлекать значение из памяти. (Обновите, да, я думаю, вы можете сделать это функцией, а не процедурой; я просто слепо модифицирую код Delphi из других ответов.)
В любом случае, к счастью, мы можем заставить компилятор C выполнить тяжелую работу по выяснению мультипликативного обратного и подсчета сдвига за нас. Мы даже можем заставить его использовать то же «соглашение о вызовах», которое выглядит так, как будто Delphi использует для встроенного asm. regparm=3 32-битное соглашение о вызовах GCC передает аргументы в EAX, EDX и ECX (в этом порядке).
Возможно, вы захотите создать отдельную версию для случаев, когда вам нужно только частное, потому что (в отличие от медленной инструкции div), вы должны вычислить остаток отдельно как x - (x/y)*y, если вы используете быстрый мультипликативный обратное. Но да, это все еще примерно в два раза быстрее, чем в современной x86.
Или же вы можете оставить вычисление остатка в чистом Delphi, если компилятор просто ужасен при оптимизации в целом.
#ifdef _MSC_VER
#define CONVENTION _fastcall // not the same, but 2 register args are better than none.
#else
#define CONVENTION __attribute__((regparm(3)))
#endif
// use gcc -Os to get it to emit code with actual div.
divmod10(unsigned x, unsigned *quot, unsigned *rem) {
unsigned tmp = x/10;
// *quot = tmp;
*rem = x%10;
return tmp;
}
Из проводника компилятора Godbolt :
# gcc8.2 -O3 -Wall -m32
div10: # simplified version without the remainder, returns in EAX
mov edx, -858993459 # 0xCCCCCCCD
mul edx # EDX:EAX = dividend * 0xCCCCCCCD
mov eax, edx
shr eax, 3
ret
# quotient in EAX
# returns quotient in EAX, stores remainder to [ECX]
# quotient pointer in EDX is unused (and destroyed).
divmod10:
mov edx, -858993459
push ebx
mov ebx, eax
mul edx # EDX:EAX = dividend * 0xCCCCCCCD
mov eax, edx
shr eax, 3
# quotient in EAX = high_half(product) >> 3 = product >> (32+3)
lea edx, [eax+eax*4] # EDX = quotient*5
add edx, edx # EDX = quot * 10
sub ebx, edx # remainder = dividend - quot*10
mov DWORD PTR [ecx], ebx # store remainder
pop ebx
ret
# quotient in EAX
Это вывод компилятора C. При необходимости адаптируйтесь к Delphi inline asm; входы в правильные регистры для Delphi, я думаю .
Если Delphi inline-asm не позволяет вам забить EDX, вы можете сохранить / восстановить его. Или вы хотите удалить неиспользуемый ввод указателя quotient, затем вы можете настроить asm или настроить C на Godbolt и посмотреть на вывод нового компилятора.
Это больше инструкций, чем с div, но div очень медленный (10 моп, и задержка 26 циклов даже на Skylake.)
Если у вас есть 64-битный целочисленный тип в Delphi, вы можете сделать это в Delphi source и избежать встроенного asm. Или, как показывает MBo, вы можете использовать $CCCD в качестве мультипликативного обратного для входов, которые находятся в диапазоне 0..2 ^ 16-1, используя только 32-битные целочисленные типы.
В остальном, циклическое сохранение / перезагрузка (от 4 до 5 циклов) имеет задержку, аналогичную фактическому вычислению на недавнем процессоре Intel с mov-elmination (3 + 1 к частному, + еще 3 для lea / add / sub = 7), поэтому использовать встроенный asm для этого довольно дерьмо. Но это все же лучше, чем div инструкция для задержки и пропускной способности. См. https://agner.org/optimize/ и другие ссылки на производительность в теге x86 вики .
Delphi версия, которую вы можете скопировать / вставить
( Если я понял это правильно, я не знаю Delphi, и просто скопировал + измененные примеры здесь на SO и этот сайт , основываясь на том, что я сделал вывод о соглашении о вызовах / синтаксис )
Я не уверен, что получил правильный аргумент для inline-asm. Эта документация RADStudio гласит: «За исключением оператора ESP и EBP, оператор asm может ничего не предполагать в отношении содержимого регистра при входе в оператор». Но я предполагаю, что аргументы в EAX и EDX.
Использование asm для 64-битного кода может быть глупым, потому что в 64-битной системе вы можете эффективно использовать чистый Паскаль для 64-битного умножения. Как реализовать эффективный 32-битный DivMod в 64-битном коде . Таким образом, в блоках {$IFDEF CPUX64} лучшим выбором может быть чистый паскаль с использованием UInt64(3435973837)*num;
function Div10(Num: Cardinal): Cardinal;
{$IFDEF PUREPASCAL}
begin
Result := Num div 10;
end;
{$ELSE !PUREPASCAL}
{$IFDEF CPUX86}
asm
MOV EDX, $CCCCCCCD
MUL EDX // EDX:EAX = Num * fixed-point inverse
MOV EAX,EDX // mov then overwrite is ideal for Intel mov-elimination
SHR EAX,3
end;
{$ENDIF CPUX86}
{$IFDEF CPUX64}
asm
// TODO: use pure pascal for this; Uint64 is efficient on x86-64
// Num in ECX, upper bits of RCX possibly contain garbage?
mov eax, ecx // zero extend Num into RAX
mov ecx, $CCCCCCCD // doesn't quite fit in a sign-extended 32-bit immediate for imul
imul rax, rcx // RAX = Num * fixed-point inverse
shr rax, 35 // quotient = eax
end;
{$ENDIF CPUX64}
{$ENDIF}
{Remainder is the function return value}
function DivMod10(Num: Cardinal; var Quotient: Cardinal): Cardinal;
{$IFDEF PUREPASCAL}
begin
Quotient := Num div 10;
Result := Num mod 10;
end;
{$ELSE !PUREPASCAL}
{$IFDEF CPUX86}
asm
// Num in EAX, @Quotient in EDX
push esi
mov ecx, edx // save @quotient
mov edx, $CCCCCCCD
mov esi, eax // save dividend for use in remainder calc
mul edx // EDX:EAX = dividend * 0xCCCCCCCD
shr edx, 3 // EDX = quotient
mov [ecx], edx // store quotient into @quotient
lea edx, [edx + 4*edx] // EDX = quot * 5
add edx, edx // EDX = quot * 10
mov eax, esi // off the critical path
sub eax, edx // Num - (Num/10)*10
pop esi
// Remainder in EAX = return value
end;
{$ENDIF CPUX86}
{$IFDEF CPUX64}
asm
// TODO: use pure pascal for this? Uint64 is efficient on x86-64
// Num in ECX, @Quotient in RDX
mov r8d, ecx // zero-extend Num into R8
mov eax, $CCCCCCCD
imul rax, r8
shr rax, 35 // quotient in eax
lea ecx, [rax + 4*rax]
add ecx, ecx // ecx = 10*(Num/10)
mov [rdx], eax // store quotient
mov eax, r8d // copy Num again
sub eax, ecx // remainder = Num - 10*(Num/10)
// we could have saved 1 mov instruction by returning the quotient
// and storing the remainder. But this balances latency better.
end;
{$ENDIF CPUX64}
{$ENDIF}
Сохранение фактора и возврат остатка означает, что оба могут быть готовы примерно в одно и то же время в вызывающей стороне, потому что дополнительная задержка вычисления остатка от коэффициента перекрывается с пересылкой хранилища. IDK, если это хорошо, или если выполнение не по порядку выполнено, начните с какой-то работы, основанной на частном, чаще лучше Я догадываюсь, что если вы позвоните в DivMod10, вам может понадобиться только остаток.
Но в цикле разбиения на десятичные цифры, который многократно делится на 10, это частное, которое формирует критический путь, поэтому версия этого, которая возвращала бы частное и сохраняла остаток, была бы намного лучше Выбор есть.
В этом случае вы сделаете частное значение возвращаемым в EAX и переименуете функцию arg в остаток.
Asm основан на выводе clang для этой версии этой функции C (https://godbolt.org/z/qu2kvV),, предназначенной для соглашения о вызовах Windows x64. Но с некоторыми настройками, чтобы сделать его более эффективным, например, убрав mov с критического пути и использование разных регистров, чтобы избежать префиксов REX. И замена одного LEA просто ADD.
unsigned divmod10(unsigned x, unsigned *quot) {
unsigned qtmp = x/10;
unsigned rtmp = x%10;
*quot = qtmp;
//*rem = rtmp;
return rtmp;
}
Я использовал версию clang вместо gcc, потому что imul r64,r64 быстрее на процессорах Intel и Ryzen (3 цикла задержки / 1 моп). mul r32 - это 3 мопа, и только 1 на 2 такта в семействе Sandybridge. Я думаю, что аппаратное умножение естественным образом дает 128-битный результат, и разбиение младших 64 из них на edx: eax требует дополнительного uop или чего-то в этом роде.