[Freeciv-Dev] Re: (PR#1180) [PATCH] cleanup to canvas_pos_to_map_pos

["rwetmore@xxxxxxxxxxxx via RT" <rt@xxxxxxxxxxxxxx>]

At 08:00 AM 02/11/24 -0800, Gregory Berkolaiko via RT wrote:
>
>
>On Sat, 23 Nov 2002, Ross W. Wetmore wrote:
>
>> It at least recognizes the positive denominator :-).
>> 
>> But try this as a way to overcome the "%" anti-pattern bias ...
>> 
>> /*
>>  * DIVIDE() divide and round down (== more negative), rather than just
>>  *   divide (round toward 0).  It is assumed the divisor is positive.
>>  *   Arguments are used multiple times, so must not have side effects.
>>  * The full case would be ...
>>  * DIVIDE_GENERIC(n, d)  ( (d) < 0 ? DIVIDE(-(n), -(d)) : DIVIDE((n),
(d)) )
>>  */
>> #define DIVIDE(n, d) \
>>   ( (n) < 0 ? ((n) - (d) + 1) / (d) : (n) / (d) )
>>   -- or --
>>   ( (n) < 0 ? ((n) + 1) / (d) - 1 : (n) / (d) )
>
>
>Stupid me!  I knew there is a way to do it without a % b !!

The next trick is to eliminate the condition branch. But I can't
quite figure that one out.

  ((n < 0)*(1 - d) + (n)) / (d)

has a multiply that I think is going to be as bad.

  (((-(n < 0) & (1 - d)) + (n)) / (d)

probably just has too many single cycle arithmentic ops to work 
either.

  ((n < 0 ? (1 - d) : 0) + (n)) / (d)

is effectively the original comparison example, but if the 
compiler was smarter about loading (n) or an offset value
with things presented to it with an add "0" term to attack, 
it might be interesting.

>However, it doesn' make much difference in terms of time:
>
>with 
>#define DIVIDE_G1(a, b) ( a/b - ( a<0 && (a%b != 0) ) )

It took me a minute to figure out just how the % fixed the 1 pixel
error you get without it. In practical terms the one pixel error is
not significant though. Jason, of course doesn't subscribe to such
a "practical" approach :-).

If it turns out that a "%"-less version is actually the fastest,
then it is likely that most real uses will be positive, and thus
the "%" clause would not normally be executed. That would be a 
reasonable argument for using this form with a comment that the
"%" fixes <blort> and is from a performance standpoint not often
used. Checking the "%"-less version should be done to prove this.

Otherwise this does seem a bit less intuitive, and if there is a 
savings, it somehow always seemed counter intuitive to me to take 
the worst one when the savings is small. But I admit this seems to
be the common argument used by others and for most of the past 
choices of this type :-).

>test code takes
>2.150u 0.000s 0:02.14 100.4%    0+0k 0+0io 75pf+0w
>
>and with 
>
>#define DIVIDE_R(n, d) ( n < 0 ? (n - d + 1) / d : n / d )
>
>takes
>2.060u 0.000s 0:02.04 100.9%    0+0k 0+0io 75pf+0w

Given that the bulk of this loop's time is probably in the rand()
and even the loop overhead is probably comparable to the DIVIDE times,
the differences (%5) you see could mean a factor of 2 or three on the
DIVIDE itself. "%"s can easily give you such factors.

If one method is 3 times more expensive than the other, that should
mean something.

>The test code:
>
>  for( i = 0; i < 10000000; i++) {
>    int v, d = (rand() - RAND_MAX/2);
>    v = DIVIDE(d, 7);
>  }

Do you have the assembly output to show just what is being executed
vs optimized away?

Cheers,
RossW
=====