Hi everyone,

Before I go optimising the wrong thing, I have a question to ask.  What's the policy on platform-specific assembly language in the compiler, or any code designed to run on a specific (source) platform (and using a more generic implementation otherwise via $ifdef)?  I ask because I have a faster algorithm for "calc_divconst_magic_unsigned" in 'compiler/cgutils.pas', but it's only able to work because it can take advantage of the x86 DIV instruction using RDX:RAX (or EDX:EAX) as a double-wide dividend. It is somewhat faster than what currently exists because of the lack of a loop whose iteration count is proportional to log2(d), where d is the desired divisor (in other words, it's slower the bigger the divisor is, whereas my algorithm is constant speed).

Speaking of "calc_divconst_magic_unsigned", exactly what is the function doing? I'm guessing it's something akin to Newton-Raphson division, but there's no comments on documentation explaining which algorithm is being used (although I can appreciate what "magic_add" is just from my own experiences).  On a related note, its partner function, "calc_divconst_magic_signed", uses 'assert' rather than an internal error, which is a bit against the code guidelines, right?

Gareth aka. Kit

In general, there should be no assembly language in the compiler. Ialso don't think that's worth it in this case. Unless (or maybe "even if") your code contains nothing but divisions by constants, I doubt this code has a significant effect on the total compile time.

The theory is explained in
https://dominoweb.draco.res.ibm.com/6005bbbc96b898df852578dc005be861.html

On a related note, its partner function, "calc_divconst_magic_signed", uses 'assert' rather than an internal error, which is a bit against the code guidelines, right?

I don't think asserts are enabled in the compiler, so it indeed won't work and should be an internalerror. The code was probably translated from C.

Jonas

Division by constants has a fairly frequent occurrance in code. For example, dividing by 10000 whenever Currency is used, and 1000 often appears in timing measurements (e.g. if t is in milliseconds, then t div 1000 is seconds and t mod 1000 is the leftover milliseconds).

The existing code contains two divisions by a variable (so they can't be optimised) and a loop that has, at most, N iterations, where N is the bit size (often 32 or 64).  The loop contains only addition, subtraction and multiplication, and 3 branches to contend with (not including the repeat...until jump).  My code contains a single DIV, but also a BSR which is effectively used to get the base-2 logarithm of the divisor (also throws an internal error if the divisor is zero, since this should have been caught already).

Granted, you may be right and the saving won't be worth it, not to mention the additional complexity (and my function currently fails on certain divisors unexpectedly, so I'll have to do some deeper testing if just for my own peace of mind!) - only a lot of timing tests will determine that.  Nevertheless, thanks for providing the article to calculating the reciprocal though - that's definitely helpful in understanding what's going on.

Gareth aka. Kit

Well, I think you might be right on this one, Jonas!

I've tested my algorithm against the one used in the compiler. It's 5 times faster when used with small divisors (so loop iterations are minimal)... but that amounts to about 15 nanoseconds compared to 75 nanoseconds!  Additionally, it treats the "magic add" differently (the reason why it randomly failed).

Gareth aka. Kit

Apologies, Jonas; I hope I didn't come off as condescending or rude in that last e-mail - I was joking because while my algorithm is faster, a few nanoseconds probably isn't going to cut it in the grand scheme of things!

I got my code to work, treating "magic add" in the same way as the existing algorithm, and further testing under -O4 shows that, while still faster, it's not as pronounced for small divisors, but still much faster for large divisors.  Of course, being x86_64 assembly language, I'm not expecting it to be approved even if it's isolated to a utility function, but I have linked a patch and a test program to this e-mail for those who are curious and as a proof of concept (tests on x86_64-win64 and x86_64-linux show no regressions).

The speed can be fractionally increased with the removal of the two internal error checks and the code that checks for powers of two (it's there to prevent incorrect results, but the routine shouldn't be called at all for powers of two, since they can be translated directly into bit shifts).  For the internal errors, one checks to see if the divisor is zero (an obviously bad expression), and the other is triggered if the total shift is greater than 127, which is the base bit count (e.g. 64) plus the base 2 logarithm of the divisor, so it shouldn't ever exceed 127 unless as new 128-bit interger type is introduced.

One final thing to note is that my algorithm produces different reciprocals (magic numbers) and shifts for some divisors, but the test program I've supplied shows that they're still correct, and careful analysis of the reciprocals will reveal that one is a bit-shift of the other (the existing algorithm seems to trim off trailing zero bits and reduces the shift to compensate).  Also, for divisors greater than N-1 bits in size, my algorithm produces a 'magic add' solution while the existing one doesn't, but for divisors this size, a simple comparison is faster than doing a multiplication and shift, since the quotient will always be 0 or 1 in these instances.

Gareth aka. Kit