Hi everyone,

This is mainly to Florian, but also to anyone else who can answer the question - at which point did a complex LEA instruction (using all three input operands and some other specific circumstances) get slow?  Preliminary research suggests the 486 was when it gained extra latency, and then Sandy Bridge when it got particularly bad.  Icy Lake seems to be the architecture where faster LEA instructions are reintroduced, but I'm not sure about AMD processors.

Should I introduce a new x86 subprocessor named "ICYLAKE" or is there a better name or does it fall under one of our categories already (CORE_AVX2 or ZEN3)?

Kit

(And I meant "Ice Lake", not "Icy Lake")

On October 3, 2023 03:32:34 +0200, "J. Gareth Moreton via fpc-devel" wrote:

Hii Kit,

This is mainly to Florian, but also to anyone else who can answer the question - at which point did a complex LEA instruction (using all three input operands and some other specific circumstances) get slow?  Preliminary research suggests the 486 was when it gained extra latency, and then Sandy Bridge when it got particularly bad.  Icy Lake seems to be the architecture where faster LEA instructions are reintroduced, but I'm not sure about AMD processors.

I cannot answer your question, but if you prepare a test program, I can run it on an Intel 486 DX2 100 Mhz and AMD Athlon 1 GHz machines if it helps you in any way (at least I hope the 486 DX2 machine should be still able to start ;-) ).

Tomas

Hmmm, could be fun to attempt to test - I'll see what I can set up.

Kit

Maybe check Agner’s list?

Preliminary research suggests the 486 was when it gained extra latency, and then Sandy Bridge when it got particularly bad. Icy Lake seems to be the architecture where faster LEA instructions are reintroduced, but I'm not sure about AMD processors. Should I introduce a new x86 subprocessor named "ICYLAKE" or is there a better name or does it fall under one of our categories already (CORE_AVX2 or ZEN3)?

If it doesn’t fit in the existing ones, you can always add new ones

I don't think any of them currently fit, although Zen 3 is later than Ice Lake, but I'm not sure if it has a faster LEA or not. I'll do some investigation.  I'll take up Tomas' offer on the 486 test though.  Personally I think the best test might actually be one of the recently-optimised cryptographic functions.

Kit

What should I call a new sub-CPU option?  Should it be "ICELAKE" or is there a better name like "CORE10" or "COREX" (X being the Roman numeral for 10, standing in for the 10th generation of Intel Core)?

Kit

Hi Tomas,

Do you think this should suffice? Originally it ran for 1,000,000 repetitions but I fear that will take way too long on a 486, so I reduced it to 10,000.

Kit

On 2023-10-07 03:57, J. Gareth Moreton via fpc-devel wrote:

Hi Kit,

Do you think this should suffice? Originally it ran for 1,000,000 repetitions but I fear that will take way too long on a 486, so I reduced it to 10,000.

OK, I tried it now. First of all, after turning on the old machine, I realized that it wasn't Intel but AMD 486 DX4 - sorry for my bad memory. :-( I compiled and ran the test under OS/2 there (I was too lazy to boot it to DOS ;-) ), but I assume that it shouldn't make any substantial difference. The ADD and LEA results were basically the same there, both around 100 ns / call. The Pascal result was around twice as long. Interestingly, the Pascal result for FPC 3.2.2 was around 10% longer than the same source compiled with FPC 2.0.3 (the assembler versions were obviously the same for both FPC versions; I tried compiling it also with FPC 1.0.10 and the assembler versions were more than three times slower due to missing support for the nostackframe directive).

I tested it under the AMD Athlon 1 GHz machine as well and again, the results for LEA and ADD are basically equal (both 3.1 ns/call) and the result for Pascal slightly more than twice (7.3 ns/call). However, rather surprisingly for me, the overall test run was _much_ longer there?! Finally, I tried compiling the test on a 64-bit machine (AMD A9-9425) with Linux (compiled for 64-bits with FPC 3.2.3 compiled from a fresh 3.2 branch). The Pascal version shows about 4 ns/call, but the assembler version runs forever - well, certainly much longer than my patience lasts. I haven't tried to analyze the reasons, but that's what I get.

Tomas

That's interesting; I am interested to see the assembly output for the Pascal control cases.  As for the 64-bit version, that was my fault since the assembly language is for Microsoft's ABI rather than the System V ABI, so it was checking a register with an undefined value.  Find attached the fixed test.

Kit

P.S. Results on my Intel(R) Core(TM) i7-10750H

   Pascal control case: 2.0 ns/call
 Using LEA instruction: 1.7 ns/call
Using ADD instructions: 1.3 ns/call

OK. My results for the AMD A9 CPU mentioned previously and 32-bit trunk compiler (Linux) are:

Pascal control case: 2.3 ns/call
Using LEA instruction: 1.2 ns/call
Using ADD instructions: 1.5 ns/call

The same machine, the same operating environment, but a 64-bit trunk compiler:

Pascal control case: 3.6 ns/call
Using LEA instruction: 0.9 ns/call
Using ADD instructions: 1.3 ns/call

I tried compiling and running the test with all of FPC 2.0.4, 2.2.4, 2.4.4, 2.6.4, 3.0.4 and 3.2.2 on my Athlon machine and realized that all results (for both the assembler and Pascal versions) compiled with anything older than 3.2.2 are an order of magnitude faster than with 3.2.2 (i.e. less than 1 ns/call for the older versions compared to 8 ns/call with Pascal / 4 ns/call with assembler versions). This means that the comparison is obviously spoiled with something unrelated. Moreover, I noticed that when compiling with the highest level of optimizations, the Pascal version compiled for i386 is as fast or even little bit faster than the assembler version. I didn't do that previously, thus the longer time for the older compiler version probably isn't relevant. From this point of view, it probably doesn't make sense to spend time on comparing the generated code.

Tomas

I'm still slightly curious, but if full optimisations make better code, then indeed it's probably not worth the effort.

Your timings are incredibly helpful - thank you!  If I understand, AMD A9 is the Excavator architecture, which implies that AMD processors don't suffer from the same latency with complex LEA instructions as Intel processors do.

Looking at Agner Fog's tables, it looks like the slow LEA instructions only came about at Sandy Bridge, which for Free Pascal I think lines up with COREAVX.  Even the Pentium-era processors have a 1-cycle LEA, and your testing on an AMD 486 shows it is at least as fast as two ADDs in a dependency chain. That should be all the information I need - thanks again!

Kit

Sorry, I got careless and was in a rush, as both the Pascal code is wrong and I didn't store the result of the benchmark test, hence the error check at the end returned a false negative.

The benchmark code was from Rika's SHA-1 test code, which I didn't properly check, although I assumed the logic was to avoid counting the time of the internal loop as much as possible.  I should have gone with my gut instinct and realised that wasn't the best method.

I've attached the updated test (now called "blea" as it's a benchmark test) with your suggestions implemented, and an improved benchmarking system.  I'm not used to specifying parameters in place of registers - I'm too used to needing total control!

Your results from experiments with adding additional ADD instructions is expected, as LEA uses an AGU for computation, leaving the ALUs free for other tasks (like ADD), so LEA is better even if speed is equal.

Kit

Sorry, ignore last attachment - I forgot to change a line of assembly (it was correct for x86_64-win64!!). Here is the corrected version.

Kit

Hi

~]$ fpc ttt.pas
Free Pascal Compiler version 3.2.2 [2023/07/04] for x86_64 Copyright (c) 1993-2021 by Florian Klaempfl and others Target OS: DragonFly for x86-64
Compiling ttt.pas
Linking ttt
/usr/local/bin/ld.bfd: warning:
/usr/local/lib/fpc/3.2.2/units/x86_64-dragonfly/rtl/prt0.o: missing .note.GNU-stack section implies executable stack
/usr/local/bin/ld.bfd: NOTE: This behaviour is deprecated and will be removed in a future version of the linker
121 lines compiled, 14.9 sec
~]$ ./ttt
Pascal control case: 6.7 ns/call
Using LEA instruction: 4.2 ns/call
Using ADD instructions: 4.0 ns/call

Nataraj S Narayan
Synergy Info Systems
Software & Technology Consultants
Ettumanoor, INDIA
Ph:+91 9443211326

On Sat, Oct 7, 2023 at 9:39 PM J. Gareth Moreton via fpc-devel <

Hi Nataraj

Which processor is that run on? (although too close to call, it implies LEA has a latency of 2 in that case)

Kit

In the meantime, here's the merge request for the feature based on user tests and studying of Agner Fog's instruction tables: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/502

Kit

Did some checking of the test I copied the code from, and I forgot that Rika's original code only exited once a certain time period had elapsed (e.g. 0.5 seconds).  I had changed it to a standard iteration count since I was concerned about fairness and accuracy, but I only changed the loop condition and nothing else.

Kit

J. Gareth Moreton wrote

Sorry, ignore last attachment - I forgot to change a line of assembly (it was correct for x86_64-win64!!). Here is the corrected version.

Alright, results for this version for AMD A9 9425 under Linux (the same trunk compiler as used yesterday):

64-bit version:

Pascal control case: 5.1 ns/call
Using LEA instruction: 0.5 ns/call
Using ADD instructions: 0.9 ns/call

32-bit version:

Pascal control case: 0.9 ns/call
Using LEA instruction: 0.5 ns/call
Using ADD instructions: 0.9 ns/call

Tomas

Hi Gareth

model name : Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz

Regards

Nataraj S Narayan
Synergy Info Systems
Software & Technology Consultants
Ettumanoor, INDIA
Ph:+91 9443211326

On Sun, Oct 8, 2023 at 6:40 PM J. Gareth Moreton via fpc-devel <

Thank you for the report.

According to Agner Fog's table, complex LEA instructions should have a 3-cycle latency on that architecture (Haswell). Optimisations with this instruction are proving interesting because there's such a variety between processor architectures. There are some that are fine with 3 components, but slows right down if a scale factor is used.

Kit

My results:
cat /proc/cpuinfo | grep "model name"
model name    : AMD A6-7480 Radeon R5, 8 Compute Cores 2C+6G /usr/bin/fpc blea.pp
Free Pascal Compiler version 3.2.2 [2021/07/09] for x86_64 Copyright (c) 1993-2021 by Florian Klaempfl and others Target OS: Linux for x86-64
Compiling blea.pp
Linking blea
95 lines compiled, 0.2 sec
./blea
   Pascal control case: 5.1 ns/call
 Using LEA instruction: 0.5 ns/call
Using ADD instructions: 0.8 ns/call

Thank you very much!  That processor is built on the Excavator architecture and lines up with the flag I put in the merge request (i.e. it has the "fast LEA" hint).

I honestly didn't expect this much testing feedback, so thank you all!

Gareth aka. Kit

P.S. I'm tempted to extend the test slightly to actually name the CPU automatically.

I updated the "blea" test in the merge request so it now displays the processor brand name on x86_64; however, it is not fetched under i386 because CPUID was not introduced until later 486 processors.  I've attached it to this e-mail if anyone wants to take a look to ensure I haven't broken something.

Kit

My results on Windows :

E:\temp>C:\lazarus\fpc\3.2.2\bin\x86_64-win64\fpc.exe -MObjFPC -Scghi -O1 -g -gl -l -vewnhibq -Fu. -FUlib\x86_64-win64 -FE. -oblea.exe blea.pp Hint: (11030) Start of reading config file
C:\lazarus\fpc\3.2.2\bin\x86_64-win64\fpc.cfg
Hint: (11031) End of reading config file
C:\lazarus\fpc\3.2.2\bin\x86_64-win64\fpc.cfg
Free Pascal Compiler version 3.2.2 [2022/09/24] for x86_64 Copyright (c) 1993-2021 by Florian Klaempfl and others (1002) Target OS: Win64 for x64
(3104) Compiling blea.pp
(9015) Linking .\blea.exe
(1008) 150 lines compiled, 0.2 sec, 87840 bytes code, 5364 bytes data (1022) 2 hint(s) issued

E:\temp>blea
CPU = Intel(R) Core(TM) i5-8500 CPU @ 3.00GHz
---------------------------------------------
   Pascal control case: 1.9 ns/call
 Using LEA instruction: 1.2 ns/call
Using ADD instructions: 0.9 ns/call

E:\temp>

On 2023-10-09 20:51, J. Gareth Moreton via fpc-devel wrote:

Hi Kit,

I don't know what's broken, but the results vary so much on a fast machine that they are unusable for any measurement from my point of view (standard 3.2.2 compiler, compiled with -O4 and running under MS Windows this time). Sometimes the ADD version shows 0.0 ns/call, sometimes the LEA version shows 0.0 ns/call (32-bits) or 0.1 ns/call (64-bits). See the attached results (the CPU is only displayed for the 64-bit compilation, but it's obviously the same CPU).

Tomas

Thanks Tomas,

Nothing is broken, but the timing measurement isn't precise enough.

Normally I have a much higher iteration count (e.g. 1,000,000), but I had reduced it to 10,000 because, coupled with the 1,000 iterations in the subroutines themselves, would have led to 1,000,000,000 passes and hence would take in the region of five to ten minutes to complete for a 16 MHz 386, for example.  Rika's suggestion of running as many iterations as needed until, say, 5 seconds elapses, would help but the timing measurements would cause a lot of latency and will be imprecise on very slow routines.  Still, let's see if 100,000 gives better results for you.

Kit

Looking at the text log, the results are a bit strange and I can't easily explain it.  Normally a system interrupt would increase the time taken.

Let me know if increasing the iteration count fixes it or not.

Kit

Be my guest making https://github.com/spring4d/benchmark compatible for all platforms you need it for.

Ooo, that might be just what we need.  Thank you Stefan.

Kit

Op 10-10-2023 om 11:13 schreef J. Gareth Moreton via fpc-devel:

I had the same problem, and now it is stable  Ryzen 5700X (ZEN3)

   Pascal control case: 0.7 ns/call
 Using LEA instruction: 0.4 ns/call
Using ADD instructions: 0.7 ns/call

Indeed, it's much more consistent now, attached a new log for both 32-bit and 64-bit versions from the Intel machine with Windows. Apparently, ADD is still somewhat faster on such "newer" Intel machines (at least if not considering the potential parallelism of LEA discussed previously). I can try this version on my AMD machines later tonight if considered useful - please, let me know which results would be relevant for you in that case (out of the ancient AMD DX4, only slightly less ancient AMD Athlon 1 GHz and the still rather reasonable AMD A9).

Tomas

I'm all for receiving results for all kinds of processor, as it helps me to make more informed choices on flags as well as confirming that Agner Fog''s instruction tables are correct. Also, results for older processors can be hard to come by sometimes.

Currently, most architectures have a fast LEA, and the default "Athlon" option lines up with this.  Of the Intel architectures, the speed slows down on COREAVX onwards (COREI is fine), so I added a new COREX (for 10th generation Core) option between ZEN2 and ZEN3 to mark the point where LEA is fast again (its 16-bit version is also fast, unlike Zen 3).

In the meantime I'll be looking at the benchmarking code that Stefan provided to see if it can and should be integrated.

Thanks again everyone for the results you're giving.

Kit

P.S. In regards to parallelisation in having LEA instructions running alongside other arithmetic/logical operations, that will be an interesting field of research.  At the very least, the post-peephole stage can change ADD or SUB into a LEA if using an AGU over an ALU appears to give a micro-optimisation.  It also benefits hyperthreading, as the ALUs tend to be very heavily used, while AGUs tend to be used one at a time.

Alright, fine (I modified your test to include the CPU name as well if possible and added an IFDEFed distinction of 32-bits versus 64-bits):

32-bits:
CPU = AMD A9-9425 RADEON R5, 5 COMPUTE CORES 2C+3G ----------------------------------------------------- Pascal control case: 0.85 ns/call
Using LEA instruction: 0.56 ns/call
Using ADD instructions: 0.84 ns/call

64-bits:
CPU = AMD A9-9425 RADEON R5, 5 COMPUTE CORES 2C+3G ----------------------------------------------------- Pascal control case: 0.85 ns/call
Using LEA instruction: 0.56 ns/call
Using ADD instructions: 0.85 ns/call

32-bits:
CPU = AMD Athlon(tm) Processor
------------------------------
Pascal control case: 6.10 ns/call
Using LEA instruction: 3.40 ns/call
Using ADD instructions: 3.40 ns/call

32-bits:
(AMD DX4 100 MHz - no CPUID name)
Pascal control case: 123 ns/call
Using LEA instruction: 72 ns/call
Using ADD instructions: 73 ns/call

Tomas

Sweet, thank you.  Would you be willing to share your modified test's source? I was worried that if CPUID wasn't present it would cause a SIGILL.

Kit

Results on a modest CPU:

CPU = Intel(R) Celeron(R) CPU N3050 @ 1.60GHz ----------------------------------------------------- Pascal control case: 6.71 ns/call
Using LEA instruction: 2.09 ns/call
Using ADD instructions: 2.05 ns/call

32 bits:
Pascal control case: 6.78 ns/call
Using LEA instruction: 2.16 ns/call
Using ADD instructions: 2.09 ns/call

Results show a bit of variance, above numbers are more or less typical.

Christo

The LEA and ADD times are close enough that I can consider them identical.  And Braswell (the architecture behind that brand of Celeron) doesn't support AVX, I don't think, so that lines up with COREI having a fast LEA instruction but not COREAVX.

Given the many different x86-compatible CPUs, I wonder if we need to document the best compiler parameters for end users in some way (e.g. so it can be coded in a device driver installer so the most optimised binary can be installed for a given CPU architecture).

Kit

J. Gareth Moreton wrote

Sweet, thank you.  Would you be willing to share your modified test's source? I was worried that if CPUID wasn't present it would cause a SIGILL.

Sure, attached, but I didn't do anything special - I modified it in a way allowing easy disabling of this detection for x86 by disabling definition of a conditional symbol added to the source and I was prepared to recompile with the functionality disabled on the old AMD DX4 if needed. However, I didn't need to do so - the AMD DX4 machine simply ignored it and chose the branch used in case of missing support for the particular CPUID function. I have no idea if this might be due to some protection in OS/2 Warp 4 (used for compiling and running the test on that machine) potentially masking that exception, or what was the reason. Apparently, it should be possible to detect CPUID availability (albeit not 100% reliably), see https://wiki.osdev.org/CPUID, but I didn't use that.

Tomas

So an update.

I've added Spring.Benchmark to "tests/bench/spring" on my local branch, along with its readme and licence file.  It seems to work quite well even if it feels a bit like overkill for this small a benchmark.  Still, I've attached the version with Stefan's translated Google Benchmark unit to see what people think.  A couple of things to note:

* Time metrics are now in thousands of nanoseconds because the 1,000 repetitions of the internal loop (used to drown out the overhead of the function call) are no longer divided out.
* Requires the fcl-base, rtl-objpas and regexpr packages.

I also made a mistake with the compiler flags.  I had added CPUX86_HINT_FAST_3COMP_ADDR_16 to indicate that a LEA instruction with 16-bit operands is fast, since the timing is often different to the 32/64-bit versions.  However, under i386 and x86_64, the assembler doesn't accept 16-bit operands!  I have therefore removed it for i386 and x86_64, although I left it in for i8086 (even though it probably won't be used) because the Pentium 4 has a slow 16-bit LEA instruction.

However, the proposed COREX CPU option now has the exact same flags as ZEN3.  Should it be removed, or kept for clarity and future expansion?

Kit

P.S. Sorry for the size of the ZIP.

J. Gareth Moreton wrote

So an update.

.
.

The latest version of blea.pp doesn't compile with a 32-bit compiler - line 76 contains an unconditional reference to R8 register, which obviously doesn't for the 32-bit mode.

Tomas

BTW, the line shouldn't be necessary at all, because global variables should be initialized to 0 on program start anyway as far as I know.

When fixing the problem above, compiling to 32-bit mode and running it, the test fails with an error in GetLogicalProcessorInformation (it states "8" in place of the error information; I wonder if it isn't misinterpreted, because 8 is number of logical CPUs on the machine used for running the test).

Tomas

Oops - that was a silly mistake of mine with R8.  As for the other error, that sounds like it's in the third party benchmark suite.  I'll do some investigating on my virtual machine.

In the meantime, here's the fixed test with the stray R8 call properly filtered out on i386 (it's replaced with "CPUName" on 32-bit).  I wasn't sure if global variables were initialised or not, hence me playing safe.

Kit

GetLogicalProcessorInformation returns a Boolean - if false, an error occurred, and is handled as follows:

DiagnoseAndExit('Failed during call to GetLogicalProcessorInformation: '
+ GetLastError.ToString);

GetLastError = 8 indicates "out of memory", which I will say is odd.

Nevertheless, because of such teething problems with the framework, I'm going to remove it from "blea" for now.  As it stands, please find attached the test that appears in the merge request: https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/502

Kit

The attached version still contained reference to the framework.

The problem with 32-bit compilation of the framework was due to a missing stdcall calling convention in the GetLogicalProcessorInformation declaration.

Tomas

Interesting!  That's a bug report to send to the maintainers of the framework.  I'll need to have them fix it before I'd be willing to try again with its use in FPC.

Removed the reference.  Apologies - I'm rushing a bit.

Kit

This one's for you Stefan!

https://github.com/spring4d/benchmark/issues/4

Kit

BTW, it's IMHO questionable whether a benchmark framework restricted to just a subset of targets supported for the given architecture should be really used within FPC source codes (if that's your potential intention anyway). If it was intended for the testsuite, it would immediately fail at compile time when checking the testsuite under some other target, because the test doesn't specify that its use should be restricted to certain targets (it's only restricted for i386 and x86_64 regardless of the operating system - that's fine for the original version, but not for the benchmark framework).

Tomas

It was a thought that crossed my mind when Stefan pointed out the translated Google Benchmark, but given that it hasn't yet been adapted to work outside of i386 and x86_64, you are right that it probably shouldn't be used for the time being.  The framework uses CPU timings to decide how many iterations to run, so obtaining such metrics is essential for its operation.  While I can probably get it to work for aarch64-linux, I don't know the first thing about polling CPUs on platforms I don't have access to!  It was a nice experiment in the meantime.

In regards to "blea" being in the test suite, i haven't yet put it into the normal test suite (using an include wrapper like I did with "tests/bench/bcase.pp") since it's primarily to evalutate LEA timings rather than testing compiler efficiency.  It's more of a 'utility' test.  The feedback from others has proven useful in determining the correctness of the new optimisation hint, which I intend to use to make the i386/x86_64 peephole optimizer smarter in regards to using LEA statements.

Kit

There's CPUID support detection code in the Free Pascal RTL for i8086 and i386. It's in unit cpu:

function cpuid_support: boolean;

Nikolay

I should have figured.  Thank you!

Kit