Ускорить программу C без использования условной компиляции - PullRequest
Новая
       48

Ускорить программу C без использования условной компиляции

3 голосов
/ 18 января 2012

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

Вот очень искусственный пример, демонстрирующий эффект: 

/* program_define */

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

#define skip 10

int main(int argc, char** argv) {
    int i, j;
    long result = 0;

    int limit = atoi(argv[1]);

    for (i = 0; i < 10000000; ++i) {
        for (j = 0; j < limit; ++j) {
            if (i + j % skip == 0) {
                continue;
            }
            result  += i + j;
        }
    }

    printf("%lu\n", result);
    return 0;
}

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

Давайте посмотрим на другую версию программы: 

/* program_variable */

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

int main(int argc, char** argv) {
    int i, j;
    long result = 0;

    int limit = atoi(argv[1]);
    int skip = atoi(argv[2]);

    for (i = 0; i < 10000000; ++i) {
        for (j = 0; j < limit; ++j) {
            if (i + j % skip == 0) {
                continue;
            }
            result  += i + j;
        }
    }

    printf("%lu\n", result);
    return 0;
}

Здесь значение для skip передается в качестве параметра командной строки. Это добавляет большую гибкость. Однако эта программа намного медленнее: 

$ time ./program_define 1000 10
50004989999950500

real 0m25.973s
user 0m25.937s
sys  0m0.019s

против 

$ time ./program_variable 1000 10
50004989999950500

real 0m50.829s
user 0m50.738s
sys  0m0.042s

То, что мы ищем, - это эффективный способ передачи значений в программу (посредством параметра командной строки или ввода файла), который никогда не изменится после этого. Есть ли способ оптимизировать код (или сообщить об этом компилятору), чтобы он работал более эффективно?

Любая помощь очень ценится!

Комментарии:

Как писал Дирк в своем комментарии 1028 *, , речь идет не о конкретном примере . Я имел в виду способ заменить if, который вычисляет переменную, которая устанавливается один раз, а затем никогда не изменяется (скажем, параметр командной строки) внутри функции, которая вызывается буквально миллиардов раз более эффективная конструкция. В настоящее время мы используем препроцессор для настройки желаемой версии функции. Было бы неплохо, если есть более хороший способ, не требующий перекомпиляции.

Ответы [ 11 ]

5 голосов
/ 18 января 2012

Вы можете взглянуть на libdivide, который работает для быстрого деления, когда делитель неизвестен до времени выполнения: http://libdivide.com/.

Если вы вычислите a % b, используя a - b * (a / b) (но с libdivide), вы можете обнаружить, что это быстрее.

2 голосов
/ 18 января 2012

Я запустил ваш program_variable код в моей системе, чтобы получить базовый показатель производительности: 

$ gcc -Wall test1.c
$ time ./a.out 1000 10
50004989999950500

real    0m55.531s
user    0m55.484s
sys     0m0.033s

Если я скомпилирую test1.c с -O3, тогда я получу: 

$ time ./a.out 1000 10
50004989999950500

real    0m54.305s
user    0m54.246s
sys     0m0.030s

В третьем тесте я вручную устанавливаю значения limit и skip: 

int limit = 1000, skip = 10;

Затем я заново запускаю тест: 

$ gcc -Wall test2.c
$ time ./a.out
50004989999950500

real    0m54.312s
user    0m54.282s
sys     0m0.019s

Извлечениеatoi() звонки не имеют большого значения.Но если я скомпилирую с включенной оптимизацией -O3, я получу увеличение скорости: 

$ gcc -Wall -O3 test2.c
$ time ./a.out
50004989999950500

real    0m26.756s
user    0m26.724s
sys     0m0.020s

Добавление макроса #define для функции ersatz atoi() немного помогло, но ничего особенного: 

#define QSaToi(iLen, zString, iOut) {int j = 1; iOut = 0; \
    for (int i = iLen - 1; i >= 0; --i) \
        { iOut += ((zString[i] - 48) * j); \
        j = j*10;}}

...
int limit, skip;
QSaToi(4, argv[1], limit);
QSaToi(2, argv[2], skip);

И тестирование: 

$ gcc -Wall -O3 -std=gnu99 test3.c
$ time ./a.out 1000 10
50004989999950500

real    0m53.514s
user    0m53.473s
sys     0m0.025s

Кажется, что дорогая часть - это atoi() вызовы, если это единственное различие между -O3

Возможно, вы могли бы написать один двоичный файл, который проходит через тесты различных значений limit и skip, что-то вроде: 

#define NUM_LIMITS 3
#define NUM_SKIPS 2
...
int limits[NUM_LIMITS] = {100, 1000, 1000};
int skips[NUM_SKIPS] = {1, 10};
int limit, skip;
...
for (int limitIdx = 0; limitIdx < NUM_LIMITS; limitIdx++)
    for (int skipIdx = 0; skipIdx < NUM_SKIPS; skipIdx++)
        /* per-limit, per-skip test */

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

1 голос
/ 19 января 2012

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

1 голос
/ 18 января 2012

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

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

Dirk

1 голос
/ 18 января 2012

Вы можете попробовать использовать встроенные функции GCC likely / unlikely (например, здесь ) или оптимизацию по профилю (например, здесь ).Кроме того, вы намереваетесь (i + j) % 10 или i + (j % 10)?Оператор % имеет более высокий приоритет, поэтому ваш код, как написано, тестирует последний.

0 голосов
/ 19 января 2012

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

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

#define MYFUNCMACRO(name, myvar) void name##doit(){/* time consuming code using myvar */}

MYFUNCMACRO(TEN,10)
MYFUNCMACRO(TWENTY,20)
MYFUNCMACRO(FOURTY,40)
MYFUNCMACRO(FIFTY,50)

Если вам нужно иметь слишком много этих макросов (сотни?), Вы можете написать генератор кода, который автоматически записывает файл cpp для диапазона значений.

Я не компилировал и не тестировал код, но, может быть, вы видите принцип.

0 голосов
/ 18 января 2012

Если это фактический код, у вас есть несколько способов его оптимизировать:

(i + j % 10==0) имеет значение true только при i==0, поэтому вы можете пропустить всю операцию мода при i>0.Кроме того, поскольку i + j увеличивается только на 1 в каждом цикле, вы можете поднять мод и просто иметь переменную, которую вы увеличиваете и сбрасываете, когда она достигает skip (как было указано в других ответах).

0 голосов
/ 18 января 2012

Другой возможностью было бы исключить использование оператора модуля: 

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

int main(int argc, char** argv) {
    int i, j;
    long result = 0;

    int limit = atoi(argv[1]);
    int skip = atoi(argv[2]);
    int current = 0;

    for (i = 0; i < 10000000; ++i) {
        for (j = 0; j < limit; ++j) {
            if (++current == skip) {
                current = 0;
                continue;
            }
            result  += i + j;
        }
    }

    printf("%lu\n", result);
    return 0;
}
0 голосов
/ 18 января 2012

Я также получил примерно двукратное замедление между program_define и program_variable, 26,2 с против 49,0 с. Я тогда попробовал 

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

int main(int argc, char** argv) {
    int i, j, r;
    long result = 0;

    int limit = atoi(argv[1]);
    int skip = atoi(argv[2]);

    for (i = 0; i < 10000000; ++i) {
        for (j = 0, r = 0; j < limit; ++j, ++r) {
            if (r == skip) r = 0;
            if (i + r == 0) {
                continue;
            }
            result  += i + j;
        }
    }

    printf("%lu\n", result);
    return 0;
}

с использованием дополнительной переменной, чтобы избежать дорогостоящего деления, и результирующее время составило 18,9 с, что значительно лучше, чем по модулю со статически известной константой. Однако этот метод вспомогательных переменных является перспективным, только если изменение легко предсказуемо.

0 голосов
/ 18 января 2012

Глупый ответ, но вы можете передать определение в командной строке gcc и выполнить все это с помощью сценария оболочки, который перекомпилирует и запускает программу на основе параметра командной строки 

#!/bin/sh
skip=$1
out=program_skip$skip
if [ ! -x $out ]; then 
    gcc -O3 -Dskip=$skip -o $out test.c
fi
time $out 1000
Страница:
...