Странное поведение производительности для 64-битной операции по модулю

Последние три вызова этих методов занимают прибл. вдвое больше, чем первые четыре.

Единственная разница в том, что их аргументы больше не помещаются в целое число. Но должно ли это иметь значение? Параметр объявлен длинным, поэтому для расчета в любом случае следует использовать long. Использует ли операция по модулю другой алгоритм для чисел> maxint?

Я использую amd athlon64 3200+, winxp sp3 и 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);            
    }

РЕДАКТИРОВАТЬ: Теперь я попробовал то же самое с C, и проблема здесь не возникает, все операции по модулю выполняются одинаково, в режиме выпуска и в режиме отладки с включенной оптимизацией и без нее на:

#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;
}

РЕДАКТИРОВАТЬ2:

Спасибо за отличные предложения. Я обнаружил, что и .net, и c (как в режиме отладки, так и в режиме выпуска) не используют атомарные инструкции процессора для вычисления остатка, но они вызывают функцию, которая это делает.

В программе c я мог получить ее имя - "_allrem". Он также отображал полные комментарии к источнику для этого файла, поэтому я нашел информацию, что этот алгоритм использует 32-битные делители вместо дивидендов, как это было в приложении .net.

Я также обнаружил, что на производительность программы c действительно влияет только значение делителя, но не дивиденд. Другой тест показал, что производительность функции остатка в программе .net зависит как от делимого, так и от делителя.

Кстати: даже простое сложение длинных длинных значений вычисляется последовательными инструкциями add и adc. Так что даже если мой процессор называет себя 64-битным, на самом деле это не так :(

РЕДАКТИРОВАТЬ3:

Теперь я запустил приложение c в версии Windows 7 x64, скомпилированной с помощью Visual Studio 2010. Забавно то, что поведение производительности остается прежним, хотя теперь (я проверил исходный код сборки) используются настоящие 64-битные инструкции.


c++ performance numeric 64-bit
person codymanix    schedule 21.01.2010    source источник
comment
Что касается вашего последнего наблюдения, если вы используете обычную бытовую установку Windows XP, вы почти наверняка используете свой модный 64-битный процессор в 32-битном режиме.   -  person caf    schedule 22.01.2010
comment
Ваш процессор действительно 64-битный, это ваша ОС и компилятор, которые работают в 32-битном режиме.   -  person Stephen Canon    schedule 22.01.2010

Ответы (2)


arrow_upward
4
arrow_downward

Какое любопытное наблюдение. Вот что вы можете сделать, чтобы исследовать это дальше: добавьте «паузу» в начало программы, как Console.ReadLine, но ПОСЛЕ первого вызова вашего метода. Затем соберите программу в режиме «релиза». Затем запустите программу не в отладчике. Затем на паузе подключите отладчик. Выполните отладку и взгляните на код рассматриваемого метода. Найти тело цикла должно быть довольно легко.

Было бы интересно узнать, чем сгенерированное тело цикла отличается от тела вашей программы C.

Причина, по которой все эти обручи проходят через это, заключается в том, что джиттер изменяет код, который он генерирует при срыве «отладочной» сборки или при срыве программы, к которой уже прикреплен отладчик; в таких случаях он использует код, который легче понять в отладчике. Было бы более интересно посмотреть, какой код джиттера считается «лучшим», сгенерированным для этого случая, поэтому вам придется подключать отладчик поздно, после того, как джиттер сработал.

person Eric Lippert    schedule 21.01.2010
comment
Спасибо за отличные предложения. Узнала много интересного, смотрите мои новые правки :) - person codymanix; 22.01.2010

arrow_upward
3
arrow_downward

Вы пробовали выполнять те же операции в машинном коде на своем компьютере?

Я не удивлюсь, если собственная 64-битная операция с остатком будет иметь особый случай, когда оба аргумента находятся в пределах 32-битного диапазона, в основном делегируя это 32-битной операции. (Или, возможно, это делает JIT ...) В этом случае имеет смысл оптимизировать, не так ли?

person Jon Skeet    schedule 21.01.2010
comment
Теперь я попробовал это с собственным кодом, и здесь проблема не возникает. Конечно, такая оптимизация имеет смысл, но почему иногда, а иногда нет. Но я не верю, что это JIT, потому что значение, о котором идет речь, передается в качестве аргумента, и я не думаю, что метод запускается несколько раз в одном и том же процессе. - person codymanix; 21.01.2010