компилятор cc и кеш

Question

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

$ cc number_v1.c

для компиляции первого и a:

$ cc number_v2.c

для второгоисходный код.Я на Mac OS X Дарвин Ядро Версия 18.7.0: Вт 20 августа 16:57:14 PDT 2019;root: xnu-4903.271.2 ~ 2 / RELEASE_X86_64 x86_64.

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

Затем я выключаю все и пытаюсь снова на следующий день.К моему удивлению, я наконец-то вижу различия: второй исходный код завершен в гораздо более короткие сроки, чем первый.Кажется, что в первый раз компилятор не скомпилировал код листинга и, возможно, все еще считал старую версию;Учтите, что я несколько раз пытался модифицировать исходный код с помощью относительной компиляции, но в результате всегда был один и тот же.

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

Кто-нибудь может объяснить, почему это произошло?Есть ли в этих случаях тип кеша для сброса?

Ниже приведены их соответствующие исходные коды;речь идет о поиске простых чисел от 2 до 1000000.

/* cc number_v1.c */    

#include <stdio.h>

int main(void) {
    int i, j, n = 1000000;

    for(i = 2; i <= n; i++) {
        for(j = 2; j < i && i % j != 0; j++)
            ;

        if(j >= i) printf("%d ", j);    
    }           
    return 0;
}



/* cc number_v2.c */

#include <stdio.h>

int main(void) {
    int i, j, n = 1000000;

    for(i = 2; i <= n; i++) {
        for(j = 2; j * j <= i && i % j != 0; j++)
            ;

        if(j * j > i) printf("%d ", i); 
    }   
    return 0;
}

Answer 1

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

Я выполнил следующий тест, модифицированный для использования uint64_t, чтобы предотвратить арифметическое переполнение в alg1(), а также заменил printf()выход с энергозависимым приемником:

{volatile uint64_t x = i ;}

Измерение производительности алгоритма, содержащего ввод / вывод, может вводить в заблуждение - вы можете измерять производительность ввода / вывода вашей системы.

#include <stdio.h>
#include <time.h>
#include <stdint.h>

#define MAX 1000000 ;
void alg1( void )
{
    uint64_t i, j, n = MAX;

    for( i = 2; i <= n; i++ )
    {
        for( j = 2; j < i && i % j != 0; j++ )
            ;

        if( j >= i ){volatile uint64_t x = i ;}
    }
}


void alg2( void )
{
    uint64_t i, j, n = MAX;

    for( i = 2; i <= n; i++ )
    {
        for( j = 2; j * j <= i && i % j != 0; j++ )
            ;

        if( j * j > i ){volatile uint64_t x = i ;}
    }
}


int main()
{
    clock_t start = clock() ;
    alg1() ;
    int alg1_clocks = clock() - start ;

    start = clock() ;
    alg2() ;
    int alg2_clocks = clock() - start ;

    printf( "\nalg1() took %f seconds", (double)(alg1_clocks) / CLOCKS_PER_SEC ) ;
    printf( "\nalg2() took %f seconds", (double)(alg2_clocks) / CLOCKS_PER_SEC ) ;

    return 0 ;
}

Результат:

alg1() took 336.681000 seconds
alg2() took 0.621000 seconds

Таким образом, ваши результаты не могут быть воспроизведены, поэтому я сомневаюсь в их целостности.

Answer 2

Прежде всего вывод кодов, скорее всего, не идентичен, но вы не проверяли.j * j не вписывается в 32-битное целое число с номерами, превышающими 46340, поэтому возможно неопределенное поведение, но я не верю, что причина в этом.

Первый код выполняет внутренний цикл O (i) раз, тогда как 2-й выполняет внутренний цикл O (i ^1/2 ) раз, следовательно, это разница между O ( ^n² ) и O ( ^{3n / 2} ) , что при 1000000 означает 316-кратное время выполнения для первого (мой компьютер дает 89 спротив 0,20, что составляет ~ 446 кратную разницу (что достаточно близко), и это с -O3.

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