Member 1045828 Ответов: 3

Почему эта программа "с" медленная на win10, но быстрая на linux


Я написал небольшую тестовую программу в качестве небольшого теста для некоторых языков, которые я рассматривал. Это не говорит много о языке, но это дает мне немного опыта использования языка, а также дает небольшой тест производительности. Один и тот же алгоритм используется для всех языков. Я использовал это с C++, Rust, Go, Crystal, "V", Java, Dart, JS. На самом деле меня интересует только скомпилированный внутренний язык, но я включил некоторые другие из интереса. Эталон состоит в том, чтобы просто найти простые числа до определенного числа. Алгоритм, вероятно, не самый быстрый, но это один и тот же алгоритм для всех программ.

Чтобы вычислить простые числа до 10 миллионов на моем ПК i7 с почти всеми этими языками, требуется менее 13 секунд. Java занимает около 14 секунд.

Однако я также написал эту программу, используя "C", и это заняло около 675 секунд, и я не знаю почему. Я не программист на "Си", но у меня есть опыт работы с несколькими языками. Я хочу знать, что я сделал не так в программе. Мне крайне странно, что он работает так, как ожидалось в "C" на Linux, но не на Win10.

Я разместил код здесь:

https://controlc.com/3179b32a
/* CALCULATE PRIME NUMBERS */
/* THIS IS NOT DESIGNED TO BE SUPER-OPTIMAL, BUT AS A BENCHMARK. */

#include <stdio.h>
#include <stdlib.h>
#include "strings.h"
#include <sysinfoapi.h>
//
long fnCalcSqrt(long);
int main(void) {
    printf("\nCalculate number of prime integers from 2 to n million");
    long iMillions = 0;
    char sMillions[10];
    while (iMillions < 1 || iMillions > 100) {
        printf("\nEnter number of millions (1 to 100): ");
        fgets(sMillions, sizeof(sMillions), stdin);
        if (strlen(sMillions) < 2) {
           return 0;
        }
        iMillions = atoi(sMillions);
        if (iMillions < 1 || iMillions > 100) {
            printf("Must be from 1 to 100");
        }
    }
    long iEndVal = iMillions * 1000000;
    long iCurrent, iDiv, iSqrt, tfPrime, iPrimeTot = 0;
    printf("Started: calculating primes from 2 to %ld,000,000 .......\n", iMillions);
    long iElapsedMs = GetTickCount();
    for (iCurrent = 2; iCurrent <= iEndVal; iCurrent++) {
        if (iCurrent % 2 != 0 || iCurrent == 2) {
            iSqrt = fnCalcSqrt(iCurrent);
            tfPrime = 1;
            for (iDiv = 2; iDiv <= iSqrt; iDiv++) {
                if ((iCurrent % iDiv) == 0) {
                    if (iDiv != iCurrent) {
                        tfPrime = 0;
                    }
                    break;
                }
            }
            iPrimeTot += tfPrime;
        }
    }
  
    iElapsedMs = GetTickCount() -iElapsedMs;
    printf("Finished. prime total = %ld\n", iPrimeTot);
    printf("Elapsed = %ld.%ld seconds\n", iElapsedMs/1000, iElapsedMs % 1000);
    return 0;
}

long fnCalcSqrt(long iCurrent) /* CALC APPROXIMATE SQRT (NOT EXACT) */
{
    long iProd = 0, iPrevDiv = 0, iDiff = 0;
    long iDiv = iCurrent / 10;
    if (iDiv < 2) {
        iDiv = 2;
    }
    while (1) {
        iProd = iDiv * iDiv;
        if (iPrevDiv < iDiv) {
            iDiff = (iDiv - iPrevDiv) / 2;
        } else {
            iDiff = (iPrevDiv - iDiv) / 2;
        }

        iPrevDiv = iDiv;
        if (iProd < iCurrent) /* iDiv IS TOO LOW */ {
            if (iDiff < 1) {
                iDiff = 1;
            }
            iDiv += iDiff;
        } else {
            if (iDiff < 2) {
                return iDiv;
            }
            iDiv -= iDiff;
        }
    }
}


Что я уже пробовал:

I presumed that I had made a mistake, and I presume that I have, but I couldn't find where. So, I set up WSL2 on my PC and compiled and ran the program on Ubuntu and it took 12.5 seconds to run. This is the exact same program that I ran on Win10 that took 675 seconds - about 50 times longer. So, I presumed it must have been the compiler on Windows, so I tried different compilers on Windows - MS, GCC, Tiny C, Pelles C. The result was the same with all - 675 seconds or more. It was then that I coded it in JS in order to transpile to "C", however that did not work (did not compile), and if I modified it to work I would have ended up with essentially my own "C" program. Thinking that it may be my PC, I tried on another Win10 PC, but essentially the same problem.

Shao Voon Wong

Не забудьте включить оптимизатор и построить в режиме выпуска в VC++. Режим отладки имеет все виды проверок, которые замедляют выполнение.

3 Ответов

Рейтинг:
2

Luc Pattyn

Я не сомневаюсь, что проблема заключается в квадратном Корне, который является относительно дорогой операцией, с производительностью, которая очень сильно зависит от того, как она обрабатывается.

Теперь суть здесь в том, что вам вообще не нужен никакой квадратный корень, а не

for (iDiv = 2; iDiv <= iSqrt; iDiv++) {

делать
for (iDiv = 2; iDiv * iDiv <= iCurrent; iDiv++) {

который в основном заменяет квадратный корень умножением!

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

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

:)


Richard MacCutchan

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

Luc Pattyn

Квадратный корень внутри простого сравнения обычно может быть заменен одним умножением. Да, это приводит ко многим другим умножениям, но они очень дешевы, я никогда не видел, чтобы подход float/double был быстрее, чем чистый целочисленный подход, но не стесняйтесь доказать мне, что я ошибаюсь...

PS: большинство чисел не являются простыми; внутренний цикл чаще всего заканчивается небольшим делителем (2, 3, 5 или 7), задолго до того, как квадратный корень будет амортизирован...

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

Richard MacCutchan

Все это чистая правда.

Рейтинг:
2

Patrice T

Этот код можно упростить:

if (iPrevDiv < iDiv) {
    iDiff = (iDiv - iPrevDiv) / 2;
} else {
    iDiff = (iPrevDiv - iDiv) / 2;
}

к
iDiff = abs(iDiv - iPrevDiv) / 2;

и это делает его быстрее.

Когда речь заходит о том, чтобы найти фактор как способ сказать, является ли число простым числом.
Простое мышление говорит вам, что как только вы знаете, что 2 не является фактором, никакие другие четные числа (4, 6, 8, 10, 12 ...) так и будет. Вы можете пропустить их.
Это только удвоит скорость вашего алгоритма.

Становится еще быстрее:
- Воспользуйтесь своими знаниями: 2 и 3-простые числа, здесь только предельная оптимизация.
- Вы проверяете все числа в последовательности, подразумеваете, что следующий квадратный корень будет таким же, пока следующее число не достигнет следующего квадрата.
Как только n достигнет 16, sqrt=4 и не изменится до тех пор, пока n=25, и вы можете сделать вывод, что следующий sqrt будет 5, и то же самое до n=36 ....
На самом деле, с помощью небольшого кода можно полностью избежать квадратных корней.

Вот статья, которую я написал: Целочисленная Факторизация: Алгоритм Пробного Деления[^]


Рейтинг:
1

Richard MacCutchan

Я исправил ссылку в вашем вопросе и скачал ваш код. Проблема вызвана вычислением квадратного корня. Я изменил код следующим образом:

#include <math.h>    // added this include file

// iSqrt = fnCalcSqrt(iCurrent); remove this
iSqrt = (int)sqrt((double)iCurrent); // use the math library sqrt function

// also changed the following block
if ((iCurrent % iDiv) == 0) {
    if (iDiv != iCurrent) {
        tfPrime = 0;
        break; // move the break statement here
    }
}

Результаты таковы:
Enter number of millions (1 to 100): 10
Started: calculating primes from 2 to 10,000,000 .......
Finished. prime total = 664579
Elapsed = 6.765 seconds


Кстати, в будущем, пожалуйста, включите свой код в вопрос, а не публикуйте его в другом месте.


Member 1045828

I appreciate people taking the time to look at this. I know that I could use the sqrt function. The whole point of the exercise is not to make it faster by changing the algorithm, because the same code is used for all languages. This exact same code runs fast on Linux and is 50 times slower on Win10. If I move the break statement, it gives the wrong result. The whole point of the exercise is to use the same algorithm, not to make it a faster algorithm. I'm not using the sqrt function for the other languages, because part of the exercise is to calculate it. In addition the code on Linux is the exact same code and it doesn't use the sqrt function.

The whole point of the question is why does this "same code" run 50 times slower on Win10 than on Linux? In addition, it runs 50 times slower than Rust, Go, Dart, Java, JS on Win10. I am not a "C" programmer, so I am probably doing something wrong, but I don't know what. Using the sqrt function obviously makes it faster, but it doesn't solve the problem by answering the question as to the huge difference, and in addition the benchmark is to calculate it using that algorithm. The same compiler was used on Linux (GCC) which is one of the ones that I used on Win10. Maybe the compiler adds some smarts, but using a profiler, it appeared to me that it doesn't spend much time calculating the sqrt. However, I've never used a profiler before and I should probably check that, but it wouldn't solve the problem. I don't want to use the sqrt function because part of the exercise is to calculate it using that algorithm for all languages. Perhaps I introduced a bug, but if so why does it run fine on Linux - using the same (GCC) compiler?

Richard MacCutchan

Мы не видели Linux-версию вашего кода, поэтому не можем ее сравнить. Как я уже сказал выше, вам нужно показать весь код, на который вы ссылаетесь.

Хорошо, я просто удалил части "Windows" из вашего кода и запустил его в своей системе Ubuntu (размещенной в Windows), и это так быстро, как вы говорите. Это очень странно, но невозможно увидеть, что отличается, так как в вычислительных частях кода нет системных вызовов.

Richard MacCutchan

Похоже, что ваш расчет квадратного корня выполняется очень быстро в Linux, но медленно в Windows. Я понятия не имею, почему это должно быть, но я думаю, что это может быть полезно для команды компиляторов в Microsoft.

Richard MacCutchan

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

Member 1045828

Большое спасибо, Ричард, я ценю, что ты нашел время посмотреть на него. Да, точный код использовался в Linux. Крайне странно, что все компиляторы на WIn10 дают одинаковое медленное время выполнения. Я попытаюсь решить эту проблему с помощью MS или поставщика компилятора.