Hi everyone,

So I'm looking to improve some of the mathematical routines.  However, not all of them are internal functions and are stored in the Math unit..  Some of them are written in assembly language but use the old floating-point stack, or use a slow hack when there's a good alternative available in SSE 4.1, for example, and I would like to see about rewriting some of these functions for x86_64.  However, while I can safely assume the presence of SSE2 on this architecture, what's the best way to detect if "-iCOREAVX" etc are specified?  Also, if "-iCOREAVX", does it automatically set "-fAVX" as well?  I rather make sure I'm not making incorrect assumptions before I start writing assembly language routines.

As an example of a function that can benefit from a speed-up under x86_64... the floor() and floor64() functions:
function floor64(x: float): Int64;
  begin
    Result:=Trunc(x)-ord(Frac(x)

Am So., 3. Feb. 2019, 07:28 hat J. Gareth Moreton
geschrieben:

Please keep in mind that for non-Win64 x86_64 targets the default floating point type is Extended and thus you can't simply use SSE functions for many of the Math routines as that would reduce their precision (the x87 is used there by design). Only if some SSE version supports 128-bit floating point that could be used (I did not check, so I can't tell).

Regards,
Sven

I might be totaly wrong here, but wouldn't that (rounding towards negative infinity) produce wrong results for negative floating point numbers?

J. Gareth Moreton wrote

And similarly with AVX.  Even if we're stuck with just SSE2, assembler improvements can be made over the Pascal code just by removing the call to Trunc and replacing it with its single assembler command: "cvttsd2si %xmm0,%rax".

The compiler already does that when the appropriate instruction set is selected.

Jonas

Better make it inline, detect the node pattern and then generate the right instructions depending on the fpu switches. While this is still a "micro" optimization, it has its maximum benefit and does not clutter rtl units with assembler and user code using similar sequences benefit from it as well.

It's certainly possible, but feels a little finnicky, since floor64 is not an internal function unlike, say, the trigonometric functions.  It will also break if the original code is changed.  It feels like a kludge, especially if another programmer down the line tries to rewrite the function and is suddenly confused when the execution speed turns out slower because the node pattern is no longer identical.

The intention though was to put the improved code, with pre-processor directives to detect the FPU switches, in the platform-specific include file and wrap the original procedure in a "{$ifndef FPC_MATH_HAS_FLOOR64}", similar to how other functions in the Math unit are programmed (e.g. DivMod).

To reassure, I'm aware that "float" is normally "extended" outside of x86_64, and I would keep my changes constrained to that platform.

Regarding Trunc, I'm aware that it's just "cvttsd2si %xmm0,%rax", but being assembly language, it's currently impossible to inline. Admittedly this is something I would like to develop and implement at some point, the ability to inline at least simple assembler routines where temporary registers can be replaced with virtual registers and the compiler can detect registers that map onto parameters and return values - very platform-specific though, but since "inline" is just ignored if it can't be used, it won't be an erroneous situation.

Gareth aka. Kit
P.S. Documentation specifically states that the Floor function round towards negative infinity, unlike Trunc that rounds towards zero.

On Sun 03/02/19 13:11 , Florian Klämpfl sent:

SSE4.1,

this could be optimised to something like the following:

Better make it inline, detect the node pattern and then generate the right instructions depending on the fpu switches. While this is still a "micro" optimization, it has its maximum benefit and does not clutter rtl units with assembler and user code using similar sequences benefit from it as well.

I would like to improve more of the mathematical functions, but unless some of them are promoted to internal functions, having micro-optimisations in the code feels very bloated and will be a maintenance nightmare due to the amount of interdependency - for example, things like the floor function can be easily inlined in SSE 4.1 and AVX because it collapses into just a couple of lines of assembly, but a general-purpose Pascal version doesn't have that luxury.

Still, I would like to put a proof of concept together for the x86_64 version of floor and floor64, possibly one using a platform-specific implementation and another using a specific node optimisation.  If either one is too messy, the patch can be rejected.
One thing that I should ask though... if a unit like Math is compiled with -fAVX, then another project that uses it is built without any special floating-point types, is Math recompiled or will it use the code already built, thereby possibly putting AVX code into a non-AVX project?

Gareth aka. Kit

On Sun 03/02/19 16:27 , "J. Gareth Moreton"
sent:
It's certainly possible, but feels a little finnicky, since floor64 is not an internal function unlike, say, the trigonometric functions.  It will also break if the original code is changed.  It feels like a kludge, especially if another programmer down the line tries to rewrite the function and is suddenly confused when the execution speed turns out slower because the node pattern is no longer identical.

The intention though was to put the improved code, with pre-processor directives to detect the FPU switches, in the platform-specific include file and wrap the original procedure in a "{$ifndef FPC_MATH_HAS_FLOOR64}", similar to how other functions in the Math unit are programmed (e.g. DivMod).

To reassure, I'm aware that "float" is normally "extended" outside of x86_64, and I would keep my changes constrained to that platform.

Regarding Trunc, I'm aware that it's just "cvttsd2si %xmm0,%rax", but being assembly language, it's currently impossible to inline. Admittedly this is something I would like to develop and implement at some point, the ability to inline at least simple assembler routines where temporary registers can be replaced with virtual registers and the compiler can detect registers that map onto parameters and return values - very platform-specific though, but since "inline" is just ignored if it can't be used, it won't be an erroneous situation.

Gareth aka. Kit
P.S. Documentation specifically states that the Floor function round towards negative infinity, unlike Trunc that rounds towards zero.

On Sun 03/02/19 13:11 , Florian Klämpfl sent:

SSE4.1,

this could be optimised to something like the following:

Better make it inline, detect the node pattern and then generate the right instructions depending on the fpu switches. While this is still a "micro" optimization, it has its maximum benefit and does not clutter rtl units with assembler and user code using similar sequences benefit from it as well.

Aah, now I see how it can be a little problematic and why node optimisation is a better approach.  Hmmm, this might take some thought.

Gareth aka. Kit

On Sun 03/02/19 21:29 , Jonas Maebe sent:

The latter.

Jonas

It just seems highly dependent on the source code and can easily break if it's changed... and not just the Floor function, but also possibly if Trunc and Frac are modified in some way.  The code does boil down to two instructions in SSE 4.1 and AVX, but it depends on many different nodes with an exact arrangement, and if something is changed (but still functionally equivalent), the optimisation will break.

Adding a platform-specific internal function and having floor() point to it on said platform is probably out of the question, although will help alleviate some of the dependencies.  This is actually an interesting conundrum.
Gareth aka. Kit

On Sun 03/02/19 21:44 , Florian Klämpfl sent:

This is why I proposed to use inlining, especially as it seems to boil down to two instructions.

J. Gareth Moreton wrote

One thing that I should ask though... if a unit like Math is compiled with -fAVX, then another project that uses it is built without any special floating-point types, is Math recompiled or will it use the code already built, thereby possibly putting AVX code into a non-AVX project?

The latter.

Jonas

This is why I proposed to use inlining, especially as it seems to boil down to two instructions.

On Sun, February 3, 2019 17:27, J. Gareth Moreton wrote: .
.

To reassure, I'm aware that "float" is normally "extended" outside of x86_64, and I would keep my changes constrained to that platform.

.
.

Just to make sure - did you notice that even on x86_64, Extended is still used for Win64? Just asking because your comment above doesn't seem to confirm that...

Tomas

I'll see what I can put together.  Personally I'd prefer it if the source code contained something that says "call this internal procedure" or "insert this special node", although that would require some careful design.
Gareth aka. Kit

On Sun 03/02/19 22:05 , Florian Klämpfl sent:

J. Gareth Moreton wrote

It just seems highly dependent on the source code and can easily break if it's changed... and not just the Floor function, but also possibly if Trunc and Frac are modified in some way.  The code does boil down to

two

instructions in SSE 4.1 and AVX, but it depends on many different nodes with an exact arrangement, and if something is changed (but still functionally equivalent), the optimisation will break.

Well, yes. But maybe its possible to create a reasonable test and take care of most imaginable situations.

Well, yes. But maybe its possible to create a reasonable test and take care of most imaginable situations.

Am So., 3. Feb. 2019, 18:29 hat J. Gareth Moreton
geschrieben:

To reassure, I'm aware that "float" is normally "extended" outside of x86_64, and I would keep my changes constrained to that platform.

This statement is not correct: the default floating point type for nearly all of FPC's platforms is Double except for the x86 targets (and maybe also m68k) where the type is Extended. And on x86_64 there is one oddball with Win64 for which the default floating point type is Double as well.

Regards,
Sven

Am Mo., 4. Feb. 2019, 14:15 hat J. Gareth Moreton
geschrieben:

Oh right, okay, so x86_64-win64 is Double (even though Extended is supported), but other x86_64 platforms are Extended, right? A little bit odd, but I'll keep an eye out in that case.

Correct. Though Extended is not considered supported on Win64 by Microsoft themselves and they warn against usage if the x87 (you need to explicitly compile FPC with a specific define to enable Extended on Win64).

Regards,
Sven

PS: you didn't answer to the list

Oh whoops, sorry about that and not replying to the list.

I'll try not to screw up.  Generally I think Double is preferred because then everything uses SSE2 and no awkward ferrying of data between it and the floating-point stack is required (come to think of it, only Win64 actually requires the presence of SSE2 and refuses to install if it's not present).
Given that Florian prefers a node micro-optimisation for functions like floor, it should be easy enough to check if the input is of type Single or Double, and drop out if it's Extended (falling back to the actual source code).

I've managed to program a cosine function that is about 8 times faster than FCOS (FCOS is still faster if the input is integral, but other than 0, this is unrealistic since the angle is in radians), but it uses SSE2 rather then x87.  It could probably be ported to x87, but will be slower on account that more terms in the Maclaurin Series of cosine will be required for the precision of Extended, among other things (by adjusting the input to be between 0 and pi, I only need 11 terms for Double, and using Horner's Method to factorise the series, the calculation becomes relatively simple, since each step involves subtracting the working value from a reciprocal factorial (a constant) then multiplying by x², something that is easily precomputed ).  Also, since I'm using SSE2 and each XMM register can hold 2 Doubles, I can easily adapt the function to compute the sine at the same time (i.e. the sincos function, or a verson in a custom library that takes advantage of "vectorcall" and the System V ABI by having both return values in XMM0).

I figure that offering speed boosts for mathematical functions are a worthwhile investment, especially in writing a game engine, or example (which is my ambition!).  sin and cos are certainly easier because they're intrinsics pointing to internal functions, whereas floor is an actual function in a supplementary unit.
Gareth aka. Kit

On Mon 04/02/19 13:19 , "Sven Barth" sent:
Am Mo., 4. Feb. 2019, 14:15 hat J. Gareth Moreton geschrieben: Oh right, okay, so x86_64-win64 is Double (even though Extended is supported), but other x86_64 platforms are Extended, right? A little bit odd, but I'll keep an eye out in that case.
Correct. Though Extended is not considered supported on Win64 by Microsoft themselves and they warn against usage if the x87 (you need to explicitly compile FPC with a specific define to enable Extended on Win64).  Regards, Sven
PS: you didn't answer to the list 

I might hold on this for a little bit until I get more out of my node outputting feature, since I need to study the nodes produced by an inlined Floor function carefully.  For example, Floor's formal parameter is further passed separately into Trunc and Frac - normally it's not a problem, but if the actual parameter is a complex expression (i.e. isn't a simple constant or variable), then it may produce even more nodes as it's calculated twice, once for Trunc and once for Frac... or it's computed beforehand and put into a temporary store that's hidden from the programmer.  I won't know for sure until I study the nodes and make a good contingency.

I'll likely make 3 versions of the floor function (not including the Pascal version that already exists, which the compiler can fall back on if it's dealing with the "Extended" type, for example), one that uses SSE2, one that uses SSE4.1 (which introduces the ROUNDSD instruction) and one that uses AVX (which is effectively identical to the SSE4.1 one, albeit using the AVX functions).
The node optimisation is definitely the better choice, thinking about it now, also because if the compiler determines that the parameters are of type Single, it can use the single-precision SSE instructions rather than converting from Single to Double and back again.  I just feel like this is possibly a little bloated because it's the kind of optimisation that belongs to an internal function rather than one in a supplementary unit... unless you want to promote "floor" and similar functions from the Math unit into internal functions through the System unit.

This is proving to be a fascinating learning experience, not just of coding but also of design and discussion!

Gareth aka. Kit

On Mon 04/02/19 20:04 , "Florian Klämpfl" sent:

J. Gareth Moreton wrote

Oh whoops, sorry about that and not replying to the list. I'll try not to screw up.  Generally I think Double is preferred

because

Well, in case of a node optimization in combination with inline I do not see it as a real micro optimization as it results in the best code which is not the case if it is ifdef'ed assembler code in a unit which is most of the time not used (fpc x86-64 rtl is build with -Cfsse2 normally).

Well, in case of a node optimization in combination with inline I do not see it as a real micro optimization as it results in the best code which is not the case if it is ifdef'ed assembler code in a unit which is most of the time not used (fpc x86-64 rtl is build with -Cfsse2 normally).

This might prove quite complicated to implement.  Writing a similar test function and modifying my node dump to get what I need (the node dump tool does its work before the second pass, so inlined functions aren't expanded), I get a very complicated node tree for a single inlined function call to "floor" with a parameter of type Single:

----

...
......
.........2
.........SmallInt
.........$000000005E511570
.........
......
...
...
......
.........8
.........Double
.........$000000005E5114F0
.........
......
...
...
......
.........
............Double
............$000000005E5114F0
............ti_may_be_in_reg
.........
......
......
.........
............
...............TESTSINGLES
............
.........
.........
............
...............X
............
.........
......
...
...
......
.........
............
...............SmallInt
...............$000000005E511570
...............ti_may_be_in_reg
............
.........
......
......
.........
............
...............
..................Double
..................$000000005E5114F0
..................ti_may_be_in_reg
...............
............
.........
.........
............
...............
..................
.....................

$fpc_frac_real(Double):Double;
.....................
........................
........................
...........................Double
...........................$000000005E5114F0
...........................ti_may_be_in_reg
........................
.....................
..................
...............
...............
.................. 0.0000000000000000E+000
...............
............
.........
......
...
...
......
.........FALSE
.........Double
.........tt_persistent
.........$000000005E5114F0
......
...
...
......
.........TRUE
.........SmallInt
.........tt_persistent
.........$000000005E511570
......
...
...
......
.........SmallInt
.........$000000005E511570
.........ti_may_be_in_reg
......
...

----

Because it's a test function, the result type is SmalInt rather than LongInt due to the compiler options, but the effect is the same.  Most of the attributes and flags I can ignore, but it's going to be a mammoth task to check all of these nodes and confirm that the function is what it's meant to be.  Don't get me wrong, it can be done, but I'm worried it will take the compiler a disproportionately long time doing so.

Still, at the same time, this is an example where the node dump is useful, if still needing some work.

Gareth aka. Kit

On Mon 04/02/19 19:28 , "J. Gareth Moreton"
sent:
I might hold on this for a little bit until I get more out of my node outputting feature, since I need to study the nodes produced by an inlined Floor function carefully.  For example, Floor's formal parameter is further passed separately into Trunc and Frac - normally it's not a problem, but if the actual parameter is a complex expression (i.e. isn't a simple constant or variable), then it may produce even more nodes as it's calculated twice, once for Trunc and once for Frac... or it's computed beforehand and put into a temporary store that's hidden from the programmer.  I won't know for sure until I study the nodes and make a good contingency.

I'll likely make 3 versions of the floor function (not including the Pascal version that already exists, which the compiler can fall back on if it's dealing with the "Extended" type, for example), one that uses SSE2, one that uses SSE4.1 (which introduces the ROUNDSD instruction) and one that uses AVX (which is effectively identical to the SSE4.1 one, albeit using the AVX functions).
The node optimisation is definitely the better choice, thinking about it now, also because if the compiler determines that the parameters are of type Single, it can use the single-precision SSE instructions rather than converting from Single to Double and back again.  I just feel like this is possibly a little bloated because it's the kind of optimisation that belongs to an internal function rather than one in a supplementary unit... unless you want to promote "floor" and similar functions from the Math unit into internal functions through the System unit.

This is proving to be a fascinating learning experience, not just of coding but also of design and discussion!

Gareth aka. Kit

On Mon 04/02/19 20:04 , "Florian Klämpfl" sent:

J. Gareth Moreton wrote

Oh whoops, sorry about that and not replying to the list. I'll try not to screw up.  Generally I think Double is preferred

because

Well, in case of a node optimization in combination with inline I do not see it as a real micro optimization as it results in the best code which is not the case if it is ifdef'ed assembler code in a unit which is most of the time not used (fpc x86-64 rtl is build with -Cfsse2 normally).