Оптимизация производительности при развертывании цикла C - PullRequest
Новая
       26

Оптимизация производительности при развертывании цикла C

0 голосов
/ 19 октября 2018

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

Я создал средство проверки простых чисел, которое вызывает по модулю каждый номер от 2 до n -1, поэтому никаких алгоритмических оптимизаций.

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

Затем я создал нормальную и оптимизированную версию: 

#include <stdlib.h>
#include <stdio.h>

typedef unsigned long long natural;

int is_prime(natural n){
    int is_not_prime = 0;

    for(natural i = 2; i < n; i += 1){
        is_not_prime |= !!!(n % i);
    }

    if(is_not_prime){
        return 0;
    }else{
        return 1;
    }
}

//__attribute__((noinline))
int is_prime_opt(natural n){
    int is_not_prime = 0;

    for(natural i = 2; i < n; i += 8){
        is_not_prime |= !!(
                !(n % i) |
                !(n % i + 1) |
                !(n % i + 2) |
                !(n % i + 3) |
                !(n % i + 4) |
                !(n % i + 5) |
                !(n % i + 6) |
                !(n % i + 7));
    }

    if(is_not_prime){
        return 0;
    }else{
        return 1;
    }
}

int main(int argc, char *argv[])
{
    if(argc != 2)
        return 1;

    natural check = atoi(argv[1]);

    if(is_prime(check)){
        printf("%llu is prime\n", check);
    }

    return 0;
}

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

Я проверил циклы с помощью valgrind --tool=callgrind ./prime 100000000 со следующими выходными данными:

unoptimized: 

==983== Callgrind, a call-graph generating cache profiler
==983== Copyright (C) 2002-2015, and GNU GPL'd, by Josef Weidendorfer et al.
==983== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==983== Command: ./prime 100000000
==983== 
==983== For interactive control, run 'callgrind_control -h'.
==983== 
==983== Events    : Ir
==983== Collected : 1000098047
==983== 
==983== I   refs:      1,000,098,047

оптимизировано: 

==2307== Callgrind, a call-graph generating cache profiler
==2307== Copyright (C) 2002-2015, and GNU GPL'd, by Josef Weidendorfer et al.
==2307== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==2307== Command: ./prime 100000000
==2307== 
==2307== For interactive control, run 'callgrind_control -h'.
==2307== 
==2307== Events    : Ir
==2307== Collected : 137598072
==2307== 
==2307== I   refs:      137,598,072

Я ожидал, что цикл будет на 10-20% быстрее, поскольку я сохраняю 1/8 прыжков и проверок.Кроме того, предсказание ветвления должно уже ускорить первую версию, поскольку все, кроме последнего прыжка, идут в одном направлении.

Что мне не понятно, почему он быстрее в 7 раз?Так как я назвал его с 100M, я ожидал бы, что он будет выполнять по крайней мере 100M - 3 (w / o 0, 1, n) по модулю или операции отрицания, но для этого ему нужно всего 1,37 цикла на элемент (а afaik по модулю недешевая операция).

Ответы [ 2 ]

0 голосов
/ 25 октября 2018

этот отправленный код: 

int is_prime(natural n){
    int is_not_prime = 0;

    for(natural i = 2; i < n; i += 1){
        is_not_prime |= !!!(n % i);
    }

    if(is_not_prime){
        return 0;
    }else{
        return 1;
    }
}

выполняет много циклов после нахождения ответа и предлагает 

int is_prime(natural n)
{
    for(natural i = 2; i < n; i += 1)
    {
        if( !(n&i) )
            return 0;
    }
    return 1
}
0 голосов
/ 19 октября 2018

!(n % i + 1) кажется нечетным, n%i приведет к 0 или положительному числу, добавление 1 приведет к положительному числу, вычисление ! на нем приведет к 0.Таким образом, каждый !(n % i + XX) может быть оптимизирован.

Это должно быть !(n % (i + 1)).

...