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

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

3 голосов
/ 21 января 2010

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

Разница лишь в том, что их аргументы больше не соответствуют целому числу. Но должно ли это иметь значение? Параметр объявлен как long, поэтому он должен использовать 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);            
    }

EDIT: Теперь я попробовал то же самое с C, и проблема возникает здесь not , все операции по модулю занимают одно и то же время, в выпуске и в режиме отладки с включенной оптимизацией и без нее: 

#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:

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

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

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

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

EDIT3:

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

Ответы [ 2 ]

4 голосов
/ 21 января 2010

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

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

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

3 голосов
/ 21 января 2010

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

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

...