How to optimize DivMod for a constant divisor of 10

  • A+
Category:Languages

In Delphi math.pas unit there is a procedure DivMod that i want to convert it into inline and optimize it for divisor to be always 10 . But I dont know details of Pentagon ASM . What is the conversion of bellow procedure

 procedure DivMod(Dividend: Integer; Divisor: Word;   var Result, Remainder: Word); asm         PUSH    EBX         MOV     EBX,EDX         MOV     EDX,EAX         SHR     EDX,16         DIV     BX         MOV     EBX,Remainder         MOV     [ECX],AX         MOV     [EBX],DX         POP     EBX end; 

 


By far the most important optimization you can do is use a fixed-point multiplicative inverse for division by a compile-time constant: Why does GCC use multiplication by a strange number in implementing integer division?.

Any decent C compiler will do that for you, but apparently Delphi won't, so there is a valid reason for doing it with asm.

Can you return a value in EAX instead of storing both the quotient and remainder to memory? Seems like a waste to pass 2 pointer args, and force the caller to retrieve the value from memory. (Update, yes I think you can by making it a function instead of a procedure; I'm just blindly modifying Delphi code from other answers, though.)

Anyway, fortunately we can get a C compiler to do the hard work of figuring out the multiplicative inverse and the shift counts for us. We can even get it to use the same "calling convention" that it looks like Delphi is using for inline asm. GCC's regparm=3 32-bit calling convention passes args in EAX, EDX, and ECX (in that order).

You might want to make a separate version for cases where you only need the quotient, because (unlike the slow div instruction), you have to compute the remainder separately as x - (x/y)*y if you're using a fast multiplicative inverse. But yes that's still about twice to 4x as fast on modern x86.

Or you could leave the remainder calculation to be done in pure Delphi, unless the compiler is just terrible at optimizing in general.

#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; } 

From the Godbolt compiler explorer:

# 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 

This is C compiler output. Adapt as necessary to Delphi inline asm; the inputs are in the right registers for Delphi, I think.

If Delphi inline-asm doesn't let you clobber EDX, you can save/restore it. Or you want to remove the unused quotient pointer input, then you can adjust the asm, or adjust the C on Godbolt and look at the new compiler output.

This is more instructions than with div, but div is very slow (10 uops, and 26 cycle latency even on Skylake.)

If you have a 64-bit integer type in Delphi, you can do this in Delphi source and avoid inline asm. Or as MBo shows, you can use $CCCD as a multiplicative inverse for inputs that are in the 0..2^16-1 range using only 32-bit integer types.

For the remainder, the store/reload round trip (4 to 5 cycles) has similar latency to the actual calculation on a recent Intel CPU with mov-elimination (3 + 1 to quotient, + another 3 for the lea/add/sub = 7), so having to use inline asm for this is pretty crap. But it's still better than a div instruction for latency and throughput. See https://agner.org/optimize/ and other performance links in the x86 tag wiki.


Delphi version you can copy/paste

(If I got this right, I don't know Delphi, and just copied+modified examples here on SO and this site, based on what I infer about the calling-convention / syntax)

I'm not sure I got the arg-passing right for inline-asm. This RADStudio documentation says "Except for ESP and EBP, an asm statement can assume nothing about register contents on entry to the statement." But I'm assuming args are in EAX and EDX.

Using asm for 64-bit code might be silly, because in 64-bit you can efficiently use pure Pascal for 64-bit multiplication. How do I implement an efficient 32 bit DivMod in 64 bit code. So in the {$IFDEF CPUX64} blocks, the best choice might be pure pascal using 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, ecx            // 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} 

Storing the quotient and returning the remainder means that both might be ready at about the same time in the caller, because the extra latency of computing the remainder from the quotient overlaps with the store-forwarding. IDK if that's good, or if having out-of-order execution get started on some work based on the quotient is more often better. I'm going to guess that if you call DivMod10, you might only want the remainder.

But in a split-into-decimal-digits loop that repeatedly divides by 10, it's the quotient that forms the critical path, so a version of this that returned the quotient and stored the remainder would be a much better choice there.

In that case you'd make the quotient the return value in EAX, and rename the function arg to the remainder.


The asm is based on clang output for this version of this C function (https://godbolt.org/z/qu2kvV), targeting the Windows x64 calling convention. But with some tweaks to make it more efficient, e.g. taking mov off the critical path, and using different registers to avoid REX prefixes. And replacing one LEA with just an ADD.

unsigned divmod10(unsigned x, unsigned *quot) {     unsigned qtmp = x/10;     unsigned rtmp = x%10;      *quot = qtmp;      //*rem = rtmp;     return rtmp; } 

I used clang's version instead of gcc's because imul r64,r64 is faster on Intel CPUs and Ryzen (3 cycle latency / 1 uop). mul r32 is 3 uops, and only 1 per 2 clocks throughput on Sandybridge-family. I think the multiply hardware naturally produces a 128-bit result, and splitting the low 64 of that into edx:eax takes an extra uop, or something like that.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: