Strange performance behaviour for 64 bit modulo operation
- by codymanix
The last three of these method calls take approx. double the time than the first four.
The only difference is that their arguments doesn't fit in integer anymore. But should this matter? The parameter is declared to be long, so it should use long for calculation anyway. Does the modulo operation use another algorithm for numbersmaxint?
I am using amd athlon64 3200+, winxp sp3 and vs2008.
Stopwatch sw = new Stopwatch();
TestLong(sw, int.MaxValue - 3l);
TestLong(sw, int.MaxValue - 2l);
TestLong(sw, int.MaxValue - 1l);
TestLong(sw, int.MaxValue);
TestLong(sw, int.MaxValue + 1l);
TestLong(sw, int.MaxValue + 2l);
TestLong(sw, int.MaxValue + 3l);
Console.ReadLine();
static void TestLong(Stopwatch sw, long num)
{
long n = 0;
sw.Reset();
sw.Start();
for (long i = 3; i < 20000000; i++)
{
n += num % i;
}
sw.Stop();
Console.WriteLine(sw.Elapsed);
}
EDIT:
I now tried the same with C and the issue does not occur here, all modulo operations take the same time, in release and in debug mode with and without optimizations turned on:
#include "stdafx.h"
#include "time.h"
#include "limits.h"
static void TestLong(long long num)
{
long long n = 0;
clock_t t = clock();
for (long long i = 3; i < 20000000LL*100; i++)
{
n += num % i;
}
printf("%d - %lld\n", clock()-t, n);
}
int main()
{
printf("%i %i %i %i\n\n", sizeof (int), sizeof(long), sizeof(long long), sizeof(void*));
TestLong(3);
TestLong(10);
TestLong(131);
TestLong(INT_MAX - 1L);
TestLong(UINT_MAX +1LL);
TestLong(INT_MAX + 1LL);
TestLong(LLONG_MAX-1LL);
getchar();
return 0;
}
EDIT2:
Thanks for the great suggestions. I found that both .net and c (in debug as well as in release mode) does't not use atomically cpu instructions to calculate the remainder but they call a function that does.
In the c program I could get the name of it which is "_allrem". It also displayed full source comments for this file so I found the information that this algorithm special cases the 32bit divisors instead of dividends which was the case in the .net application.
I also found out that the performance of the c program really is only affected by the value of the divisor but not the dividend. Another test showed that the performance of the remainder function in the .net program depends on both the dividend and divisor.
BTW: Even simple additions of long long values are calculated by a consecutive add and adc instructions. So even if my processor calls itself 64bit, it really isn't :(
EDIT3:
I now ran the c app on a windows 7 x64 edition, compiled with visual studio 2010. The funny thing is, the performance behavior stays the same, although now (I checked the assembly source) true 64 bit instructions are used.
