Время выполнения программы

[sasha-parazit]

Написал программу реализующую метод Гаусса для трехдиагональной матрицы.
В ней есть участок кода(обратный ход)

 
   d=y2[n]=f1[n]/b1[n];
   for (i=n-1; i>=0; i--)
   {
      d = (f1[i]-c[i]*d)/b1[i];
      y2[i]  = d;
   }

если деление в нем поменять на умножение:

 
   d=y2[n]=f1[n]/b1[n];
   for (i=n-1; i>=0; i--)
   {
      d = (f1[i]-c[i]*d)*b1[i];//Здесь
      y2[i]  = d;
   }

то время работы этого куска возрастает в 7-8 раз.
Посмотрел в дизассемблере

//вариант с умножением------------------------------------------------------------
.text:00401358 loc_401358:                             ; CODE XREF: _main+168j
.text:00401358                 fmul    qword ptr [eax+409550h]
.text:0040135E                 sub     eax, 8
.text:00401361                 cmp     eax, 0FFFFFCE8h
.text:00401366                 fsubr   qword ptr [eax+40A1F8h]
.text:0040136C                 fmul    qword ptr [eax+409ED0h]    //отличие 
.text:00401372                 fst     qword ptr [eax+40A520h]
.text:00401378                 jge     short loc_401358
//вариант с делением---------------------------------------------------------------
.text:00401358 loc_401358:                             ; CODE XREF: _main+168j
.text:00401358                 fmul    qword ptr [eax+409550h]
.text:0040135E                 sub     eax, 8
.text:00401361                 cmp     eax, 0FFFFFCE8h
.text:00401366                 fsubr   qword ptr [eax+40A1F8h]
.text:0040136C                 fdiv    qword ptr [eax+409ED0h]    //отличие
.text:00401372                 fst     qword ptr [eax+40A520h]
.text:00401378                 jge     short loc_401358

Подскажите, пожалуйста, почему происходит увеличение времени выполнения.

P.S. n=100 но сам цикл выполняется сотни тысяч раз.

[venco]

Потому что деление - гораздо медленнее, чем умножение.

[covax]

Деление выполняется намного медленнее, fmul выполняется 2-3 такта, fdiv около 40.
Если каждое b1[i] используется несколько раз, их можно один раз поделить (b2[i] = 1/b1[i]) и во внутренних циклах уже умножать на b2.

[Maslov]

sasha-parazit в сообщении #265546 писал(а):

В ней есть участок кода(обратный ход)
...
если деление в нем поменять на умножение:
...
то время работы этого куска возрастает в 7-8 раз.
...
Подскажите, пожалуйста, почему происходит увеличение времени выполнения.

venco в сообщении #265549 писал(а):

Потому что деление - гораздо медленнее, чем умножение.

Возможно, я что-то опять не так понял, но мне кажется у автора ровно обратная ситуация: умножение выполняется медленнее деления.

[covax]

Ого.
По идее, там куча танцев с оптимизацией, этим должен компилятор сам заниматься.

Ну и, точно также, если компилятор не хочет оптимизировать, можно вручную взять обратное и в цикле уже на него делить Но очень уж бредово звучит.

[venco]

Maslov в сообщении #265556 писал(а):

sasha-parazit в сообщении #265546 писал(а):

В ней есть участок кода(обратный ход)
...
если деление в нем поменять на умножение:
...
то время работы этого куска возрастает в 7-8 раз.
...
Подскажите, пожалуйста, почему происходит увеличение времени выполнения.

venco в сообщении #265549 писал(а):

Потому что деление - гораздо медленнее, чем умножение.

Возможно, я что-то опять не так понял, но мне кажется у автора ровно обратная ситуация: умножение выполняется медленнее деления.

Я думаю, автор перепутал, и имел в виду скорость выполнения, т.к. деление совершенно точно медленнее умножения.
Если же автор не перепутал, то возможно замена умножения делением меняет, например, количество итераций какого-нибудь цикла. При этом результат получается неправильный, но гораздо быстрее.

-- Чт ноя 26, 2009 12:09:05 --

covax в сообщении #265557 писал(а):

Ого.
По идее, там куча танцев с оптимизацией, этим должен компилятор сам заниматься.

Ну и, точно также, если компилятор не хочет оптимизировать, можно вручную взять обратное и в цикле уже на него делить Но очень уж бредово звучит.

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

[sasha-parazit]

Цитата:

Я думаю, автор перепутал, и имел в виду скорость выполнения, т.к. деление совершенно точно медленнее умножения.
Если же автор не перепутал, то возможно замена умножения делением меняет, например, количество итераций какого-нибудь цикла. При этом результат получается неправильный, но гораздо быстрее.

Нет, я не перепутал. Вариант с делением работает быстрее варианта с умножением. --- В этом-то и парадокс.

[Maslov]

sasha-parazit в сообщении #265678 писал(а):

В этом-то и парадокс.

Действительно, парадокс. А как Вы время меряли?

[gris]

А что если Вам этот кусок выделить в отдельную программу и прогнать его в цикле?
Не существует ли особых случаев, когда деление определённых чисел на определённые числа выполняется быстрее их умножения?

[Maslov]

gris в сообщении #265682 писал(а):

А что если Вам этот кусок выделить в отдельную программу и прогнать его в цикле?

Выделил. Прогнал (VS2008).
Программа:

Используется синтаксис C++

int main()
{
    int n = 100;
    double f1[100], y2[100], b1[100], c[100], d;
    int i;
    for (i = 0; i < 100; i++) {
        f1[i] = i+2;
        b1[i] = i+2;
        c[i] = i+1;
    }
    for (long m = 0; m < 5000000; m ++) {
        d=y2[n]=f1[n]/b1[n];
        for (i=n-1; i>=0; i--)
        {
            d = (f1[i]-c[i]*d)*b1[i];
            //                ^ умножение на деление меняем здесь
            y2[i]  = d;
        }
    }
    return 0;
}
 

Ключи компиляции:

/O2 /Oi /Os /GL /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MD /Gy /fp:fast /FAs /Fa"Release\\" /Fo"Release\\" /Fd"Release\vc90.pdb" /W3 /nologo /c /Zi /TP /errorReport:prompt

Результаты:

1. Intel Pentium 4 HT (Northwood) 2.8 GHz
С умножением: 16.5 сек.
С делением: 9.4 сек.
Ничего не перепутал: с делением на 75% быстрее.

2. Intel Core 2 Duo (Merom) T7700 2.40GHz
С умножением: 7.7 сек.
С делением: 8.3 сек.
Опять ничего не перепутал: с делением на 7% медленнее.

Сгенерированный код отличается, как и положено, в одной команде FMUL/FDIV.
Пока не знаю, что и думать.

[gris]

Когда компутер делит одинаковые числа, он соображает, что делает? Одно дело умножить 57486453 на 57486453, а другое разделить. Не сокращается ли драматически время деления в этом случае?

[Maslov]

gris в сообщении #265702 писал(а):

Одно дело умножить 57486453 на 57486453, а другое разделить. Не сокращается ли драматически время деления в этом случае?

Да не должно. Вряд ли он сначала сравнивает операнды деления на полное совпадение. Да и потом, у нас вроде другой случай.

[covax]

При умножении возникает переполнение, из-за этого, скорее всего.
Например, если тут 100 поменять на 1000, то умножение у меня отстает уже раз так в 50.

[venco]

Во первых, ваша программа заходит за границы массивов в первом операторе цикла по m.
Что при этом портится, и что в результате получается - трудно сказать.
Если массивы сделать на один больше, то вариант с умножением станет быстрее, чем с делением.

Ещё у вас во внутреннем цикле есть зависимость от значения, вычисляемого в предыдущей итерации.
В результате процессор не может загрузить конвейер полностью, и скорость сильно меньше максимальной. Если попробовать развязать зависимость (не знаю, можно ли так сделать с сохранением алгоритма), то умножение начинает работать на порядок быстрее.

-- Пт ноя 27, 2009 08:58:02 --

covax в сообщении #265734 писал(а):

При умножении возникает переполнение, из-за этого, скорее всего.

Согласен. Вычисление с особыми значениями, типа бесконечности или NaN, могут работать медленнее.

[nestoklon]

Ну раз пошёл мозговой штурм... Не может быть так, что какой-нибудь кэш в игру вступает? Если умножение чуть-чуть быстрее деления, так что кэш успевает закончиться (а при делении чуть медленнее, так что процу никогда не приходится ждать загрузки данных), то в принципе могло бы быть что-то похожее. Как относительная скорость выполнения зависит от $n$? Или никак не зависит?