То, на чем вы сосредоточены, не имеет никакого отношения к реальному миру. Нет, я не упрекаю тебя; Я только указываю, что вы беспокоитесь о чем-то, что не имеет значения.
Самая эффективная реализация - та, которая не работает.
На практике удобство сопровождения кода гораздо важнее, чем абсолютная максимальная производительность. Мы узнаем больше о компьютерных науках каждый день, и оборудование, которое мы используем, меняется, поэтому то, что сегодня является абсолютно оптимальным, не будет завтра.
Достаточно хорошо, легко модифицировать / обновлять, стоит гораздо больше.
Когда генерируется последовательность, скорость не так важна, потому что вы запускаете ее только один раз и сохраняете результаты.
Когда вы работаете с последовательностью, вы часто не можете хранить и извлекать их (потому что либо во вселенной недостаточно вещества, либо ввод / вывод слишком медленный, чтобы быть практичным). Вместо этого вы генерируете явное значение в последовательности . Этот ответ мой, на связанный вопрос - тот, где значения в последовательности имеют уникальные цифры - показывает, как вы можете это сделать. По сути, вы используете беззнаковое целое число «index», начиная с 0, в качестве начального числа для генерации значения в последовательности.
Иногда, однако, вы просто играете с кодом или, возможно, играете в него (например, игра в гольф кода при переполнении стека). Или, может быть, у вас есть несколько разных реализаций, которые делают одно и то же, и вы хотите сравнить их справедливо.
Тогда проблема заключается в разнице между бенчмаркингом и бенчмаркингом .
Наши современные компьютеры достаточно сложны, поэтому при рассмотрении таких понятий, как скорость или эффективность , совершенно разные операции сильно влияют друг на друга. Самый распространенный механизм - через кеш. Проще говоря, если ваша сверхскоростная функция использует много кеша, она может замедлить другие операции (потому что данные, которые им нужны, больше не кэшируются, а должны загружаться из системной памяти), так что задача, являющаяся частью функции из, это замедлено в целом из-за функции!
Это означает, что для правильных тестов производительности, правильного анализа производительности программ нам необходимо использовать реальные полезные данные. Несколько разных, на самом деле. И просто попытайтесь сформировать полную картину того, как работает каждая реализация; когда они эффективны, когда они медленны и ресурсоемки и т. д.
Распространенной проблемой является масштабируемость . Некоторые функции выполняются быстрее, чем другие, когда данных много, но когда набор данных невелик, обратное может быть истинным. Это особенно характерно для функций сортировки. Некоторые функции сортировки очень медленные, если данных не так много; но быстрее, чем любая другая функция, когда у вас есть достаточно данных. (Радикальная сортировка для числовых данных является прекрасным примером: она сортирует по существу линейное время, но линейный коэффициент настолько велик, что вам нужны массивы с миллионами записей, прежде чем радикальная сортировка займет меньше времени, чем другие алгоритмы сортировки; радикальная сортировка также имеет тенденцию к быть более загруженным кешем, чем другие алгоритмы, поэтому, хотя в определенных терминах он «превосходит» его, он не часто используется.)
Мы используем термин микробенчмарк при сравнении, например. работает с синтетическими тестовыми примерами, чтобы напомнить нам людям, что такие тесты показательны и не совсем надежны по вышеуказанным причинам.
Микробенчмаркинг сам по себе - искусство делать правильно.
В частности, просто усреднение времени, затраченного на большое количество прогонов, не дает полной картины. Несвязанные события в других частях системы иногда замедляют отдельные прогоны (функции с микробенчмарками); в худшем случае вы воспринимаете их как «дрожание» при воспроизведении видео, движении мыши или анимации. Из-за таких событий и из-за того, что другие источники ошибок измерения имеют сходные характеристики, измеренные временные интервалы имеют асимметричные полосы ошибок: измеренная длительность никогда не бывает слишком низкой, но часто слишком высокой, поскольку временные характеристики включали эти посторонние события.
Эффекты кэша означают, что если вы вызываете одну и ту же функцию для данных, хранящихся в том же буфере, первый вызов будет медленнее, чем последующие вызовы, так как его время будет включать время, необходимое для «горячего» кэша; загрузить содержимое из оперативной памяти.
По этим причинам я рекомендую использовать медиану или какой-то другой процентиль вместо среднего.
Если вы думаете об этом, вас редко интересует, сколько, скажем, может потребоваться 1000 последовательных вызовов, потому что вы не выполняете эти вызовы последовательно в реальных программах. Однако, если вы знаете, что среднее время каждого вызова функции составляет T , вы знаете, что, по крайней мере, в 50% случаев с микробенчмарками, вызов функции занимал T или меньше времени.
Существует также проблема , какие часы использовать на компьютере. Мы можем измерить время настенных часов (clock_gettime(CLOCK_MONOTONIC, ×pec) в системах POSIXy) или только время ЦП (clock_gettime(CLOCK_THREAD_CPUTIME_ID, ×pec)), занятое этим конкретным потоком. Время настенных часов зависит от всего, что работает на той же машине, но лучше соответствует тому, что человек может ожидать от производительности; процессорное время лучше для математических вычислений, которые не требуют значительных объемов данных. (Я бы сказал, что процессорное время лучше для таких функций, как OP.)
Последний недостаток - оптимизация компилятора. В настоящее время компиляторы могут выполнять удивительные оптимизации на уровне машинного кода, в зависимости от контекста, в котором вызывается функция. Для реального бенчмаркинга это не проблема, но для микробенчмаркинга нам действительно нужно разделить функции на отдельные блоки, чтобы мы могли их сравнить.
(Конечно, все результаты специфичны для каждой машины и различаются в зависимости от компилятора, опций компилятора и используемых библиотек. Тот факт, что микробенчмарк X быстрее на машине А, чем на машине Б, не означает, что микробенчмарк Y также быстрее на A, чем на B. Помните: ориентировочный, а не доказательный или действительно надежный.)
Теперь, когда я утомил вас до смерти этой стеной текста, мы можем взглянуть на реализацию реального микробенчмарка для справедливого сравнения таких генераторов последовательностей.
Во-первых, узким местом будет часть ввода / вывода. Мы выбрасываем это. Вместо этого мы используем локальный буфер для хранения строки, и всякий раз, когда новое значение завершается, мы вызываем функцию обратного вызова. Таким образом, компилятор не может делать никаких действительно плохих махинаций, например, избегать вычисления значения в целом, потому что он должен предполагать, что значение используется.
void sequence(int m, int n, void (*callback)(int index, char seq[]))
{
int index[m + 1];
char buffer[m + 1];
int count = 0;
int j = 0;
buffer[m] = '\0';
A:
if (j >= m) {
callback(count, buffer);
++count;
goto C;
}
index[j] = 0;
B:
if (index[j] < n) {
++j;
goto A;
}
C:
--j;
if (j >= 0) {
++index[j];
goto B;
}
return;
}
Я также переименовал массив i в index. Описательные имена работают лучше.
Допустим, мы поместили это в fiveseven.c . Давайте также напишем небольшой Makefile , чтобы помочь нам скомпилировать этот материал:
CC := gcc
CFLAGS := -Wall -O2
LDFLAGS :=
LIBS := fiveseven.so
.PHONY: all clean
all: clean benchmark $(LIBS)
clean:
rm -f benchmark $(LIBS)
%.so: %.c
$(CC) $(CFLAGS) -fPIC -shared $^ -Wl,-soname,$@ $(LDFLAGS) -o $@
benchmark: benchmark.c
$(CC) $(CFLAGS) $^ $(LDFLAGS) -ldl -o $@
Обратите внимание, что для отступа используются Tab s, а не пробелы; но этот форум не позволяет тем, кто вставил код. Поэтому, если вы скопируете и вставите вышеперечисленное, запустите sed -e 's|^ *|\t|' -i Makefile, чтобы исправить отступ.
Компилирует реальную программу микробенчмаркинга, от benchmark.c до ./benchmark, отдельно; и функцию или функции, которые нужно сравнить, в динамически загружаемые библиотеки. Это позволяет избежать удивительной оптимизации компилятором кода.
Если вы добавляете другие реализации, просто добавьте имя их библиотеки (заканчивающееся .so в Linux) в строку LIBS. Обратите внимание, что вы также можете запустить make CC=clang или make LIBS=foo.so clean all и т. Д., Переопределяя переменные во время сборки.
Конечно, нам нужна сама программа бенчмаркинга. Вот одна реализация, benchmark.c:
#define _POSIX_C_SOURCE 200809L
// SPDX-License-Identifier: CC0-1.0
#include <stdlib.h>
#include <inttypes.h>
#include <dlfcn.h>
#include <stdio.h>
#include <time.h>
typedef void (sequence_fn)(int, int, void (*)(int, char []));
static int compare_int64(const void *ptr1, const void *ptr2)
{
const int64_t val1 = *(const uint64_t *)ptr1;
const int64_t val2 = *(const uint64_t *)ptr2;
return (val1 < val2) ? -1 :
(val1 > val2) ? +1 : 0;
}
static void nothing(int index, char value[])
{
return;
}
static double median_cpu_time(const size_t iterations,
const int length,
const int radix,
sequence_fn *sequence_function)
{
struct timespec started, stopped;
int64_t *nanosecs;
double result;
size_t i;
if (iterations < 1 || length < 1 || radix < 1 || !sequence_function)
return -1.0; /* Invalid parameters. */
nanosecs = malloc(iterations * sizeof nanosecs[0]);
if (!nanosecs)
return -1.0; /* Out of memory. */
for (i = 0; i < iterations; i++) {
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &started);
sequence_function(length, radix, nothing);
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stopped);
nanosecs[i] = (int64_t)(stopped.tv_sec - started.tv_sec) * INT64_C(1000000000)
+ (int64_t)(stopped.tv_nsec - started.tv_nsec);
}
qsort(nanosecs, iterations, sizeof (int64_t), compare_int64);
result = (double)nanosecs[iterations / 2] / 1000000000.0;
free(nanosecs);
return result;
}
int main(int argc, char *argv[])
{
size_t iterations;
int arg, length, radix;
void *handle;
sequence_fn *func;
double seconds;
char dummy;
if (argc < 5) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help | help ]\n", argv[0]);
fprintf(stderr, " %s LENGTH RADIX ITERATIONS ./library.so ...\n", argv[0]);
fprintf(stderr, "\n");
fprintf(stderr, "This program measures the median CPU time taken by\n");
fprintf(stderr, "each sequence(LENGTH, RADIX, callback) call\n");
fprintf(stderr, "over ITERATIONS iterations, as implemented in each\n");
fprintf(stderr, "listed dynamic library.\n");
fprintf(stderr, "\n");
return EXIT_FAILURE;
}
if (sscanf(argv[1], " %d %c", &length, &dummy) != 1 || length < 1) {
fprintf(stderr, "%s: Invalid length.\n", argv[1]);
return EXIT_FAILURE;
}
if (sscanf(argv[2], " %d %c", &radix, &dummy) != 1 || radix < 1) {
fprintf(stderr, "%s: Invalid radix.\n", argv[2]);
return EXIT_FAILURE;
}
if (sscanf(argv[3], " %zu %c", &iterations, &dummy) != 1 || iterations < 1) {
fprintf(stderr, "%s: Invalid number of iterations.\n", argv[3]);
return EXIT_FAILURE;
}
printf("Reporting median CPU time used over %zu iterations.\n", iterations);
printf("Length = %d, radix = %d.\n", length, radix);
fflush(stdout);
for (arg = 4; arg < argc; arg++) {
handle = dlopen(argv[arg], RTLD_NOW);
if (!handle) {
fprintf(stderr, "%s: %s.\n", argv[arg], dlerror());
continue;
}
func = dlsym(handle, "sequence");
if (!func) {
fprintf(stderr, "%s: Library does not implement sequence().\n", argv[arg]);
dlclose(handle);
continue;
}
printf(" %s: ", argv[arg]);
fflush(stdout);
seconds = median_cpu_time(iterations, length, radix, func);
printf("%.9f seconds median per call\n", seconds);
fflush(stdout);
dlclose(handle);
}
return EXIT_SUCCESS;
}
Обратите внимание, что он предоставляет функцию обратного вызова, которая ничего не делает, и что большая часть программы на самом деле просто предоставляет информацию об использовании командной строки. Это удивительно полезно на практике. Я склонен помещать каждый «проект» в отдельный каталог / папку. Когда я ищу конкретную вещь, я делаю find + grep или grep -e pattern -R base-of-directories, а затем проверяю вероятных кандидатов. Если есть исполняемый файл, который я могу запустить, чтобы увидеть использование (мое всегда есть!), Я могу увидеть цель этого конкретного каталога; и гораздо быстрее и менее утомительно читать тысячи строк кода, чтобы попытаться вспомнить, если это то, что я искал.
После сохранения вышеприведенного, запустите, например,
make clean all
./benchmark 5 4 100000 ./fiveseven.so
чтобы узнать, сколько процессорного времени (в секундах, в среднем) занимает каждый вызов функции sequence() OP, включая накладные расходы на вызов функции бездействия через указатель функции для каждого сгенерированного значения.
Обратите внимание, что этот микробенчмарк ничего не делает для проверки правильности результатов. Это то, что следует учитывать.