Hi everyone,

During my exploration of FPC, I noticed that the 'mod' operator is not optimized in the same way 'div' is. Though not deeply tested on other platforms yet, I have developed a patch for 3.1.1 that implements the algorithm that calculates a reciprocal constant for unsigned 'mod' operations with a constant denominator. Just my little contribution to the compiler - I hope it is sound.

https://bugs.freepascal.org/view.php?id=32945

I attached a couple of test projects that contain numerous 32-bit constants (testfile2.pp) and 64-bit constants (testfile3.pp) and a means to output timing metrics. A sample of such is shown in the bug report.

Note that I unfortunately made a slight mistake that I only noticed after uploading the patch. The line:

m := qword(-aint(d)); { Two's complement of d }

...should be...

m := aword(-aint(d)); { Two's complement of d }

NOTE: One of the optimised algorithms, specifically for 32-bit divisors greater than $80000000, makes use of CMOV to avoid jumps. If CMOV is not available (it checks "CPUX86_HAS_CMOV in cpu_capabilities[current_settings.cputype]"), then the code will fall back to the default 'mod' implementation that was already present.

I should note that there's still a lot of room for improvement. For example, code such as this:

Minutes := t div 60;
Seconds := t mod 60;

... is badly optimised, because the division is calculated twice (without the patch, 't div 60' uses a reciprocal constant, while 't mod 60' just uses 'DIV'), whereas, ideally, it should only be calculated once since the numerator and denominator are the same... either a single call to DIV, or calculating the quotient via the reciprocal multiplication method, then obtaining the remainder by multiplying the quotient by the original denominator (60 in this case) and subtracting the product from the original numerator.

Gareth aka. Kit

Hi,

I haven't done the check if already implemented, but there are some interesting optimisations possible like: if a is a non-negative integer and t is a non-negative integer power of two, then a mod t
can be translated at compile time to
a and (t-1)

Cheers, Ched'

Le 05.01.2018 à 04:32, J. Gareth Moreton a écrit :

J. Gareth Moreton:

Or not at all.

How about a compound DivMod() procedure that will return both quotient and remainder:

procedure DivMod (* or QuotRem ? *)
(  const dividend, divisor:   integer;
   var   quotient, remainder: integer
);
begin
   quotient  := dividend div divisor;
   remainder := dividend - quotient*divisor;
end;

Similar optimisation is already available in Math.SinCos().

I've used DivMod myself before, akin to something like this under Windows:

{$ASMMODE Intel}
function DivMod(N, D: QWord; var R: QWord): QWord; assembler; nostackframe; asm
MOV R9, RDX
MOV RAX, RCX
XOR RDX, RDX { Zero RDX because the DIV operation uses RDX:RAX as the numerator } DIV R9 { Quotient is in RAX and remainder is in RDX } MOV [R8], RDX
end;

The drawback is the overhead of calling a procedure, and the fact it uses DIV, which can take upwards of 50 cycles to execute for 64-bit operands. It's a very slow command, hence the 9-nanosecond metric that I measured compared to times under 2 nanoseconds if converted into a multiplication. True, you could write a Pascal variant and inline the function to avoid the expensive procedure call, but you're still using DIV.

If you know the divisor is a constant, then you can change the division into a multiplication by calculating a reciprocal value (along with an addition and bit shift to correct rounding errors), which is far faster to execute. Also, most programmers won't think to use something like DivMod, or may not want to for sake of convenience, especially with something like the following:

WriteLn(Format('Time taken: %d:%.02d', [Seconds div 60, Seconds mod 60]));

Kit

Hi Ched,

That optimisation actually already exists,
as does changing unsigned division by a
power of two into SHR.

Another optimisation I put in... if you're
doing x mod a, where a is greater than
half the maximum value for the word size
(e.g. $80000000 for 32-bit), then it can
be changed into what effectively amounts
to a comparison and a subtraction,
although I used CMOV to avoid branching.

It also seems that Florian was happy with
the patch, albeit with a couple of changes
regarding coding style and an issue with
register allocation. So a happy ending, I
think!

Kit

On Fri 05/01/18 10:16 , Ched

m sent:

implemented, but there are some

interesting optimisations possible like: if a is a non-negative integer and t is

a non-negative integer power of

a écrit :

noticed that the

'mod' operator is not optimized in the

same way 'div' is.

> Though not deeply tested on other

platforms yet,

I have developed a patch for 3.1.1 that

implements the

> algorithm that calculates a reciprocal

constant

for unsigned 'mod' operations with a

constant denominator.

> Just my little contribution to the

compiler - I

hope it is sound. > > https://bugs.freepascal.org/view.php?

id=32945

> > I attached a couple of test projects

that

contain numerous 32-bit constants

(testfile2.pp) and 64-bit

> constants (testfile3.pp) and a means

to output

timing metrics. A sample of such is

shown in the bug report.

> > Note that I unfortunately made a

slight mistake

that I only noticed after uploading the

patch. The line:

> > m := qword(-aint(d)); { Two's

complement of d }

complement of d }

than $80000000, makes use of

> CMOV to avoid jumps. If CMOV is not

available

(it checks "CPUX86_HAS_CMOV in >

cpu_capabilities[current_settings.cputype]
"), then the code will fall

back to the default 'mod' > implementation that was already

present.

> > I should note that there's still a lot

of room

for improvement. For example, code such

as this:

division is

calculated twice (without the patch, 't

div 60' uses a

> reciprocal constant, while 't mod 60'

just uses

'DIV'), whereas, ideally, it should only

be calculated once

> since the numerator and denominator

are the

same... either a single call to DIV, or

calculating the quotient

> via the reciprocal multiplication

method, then

obtaining the remainder by multiplying

the quotient by the

> original denominator (60 in this case)

and

subtracting the product from the

original numerator.