Стоимость SQRT в C

Question

Как вы определяете, какая стоимость цикла для данной функции библиотеки C?

В частности, как дорого назвать sqrt()?

Я должен уточнить здесь, я просто ищу общую идею о стоимости, связанной с вызовом определенных функций библиотеки C. Я предполагаю, что у профессиональных программистов C просто есть базовое представление о стоимости функций для этих вещей. Например, можно понимать, что sqrt() ухудшает производительность до O (n^2).

Answer 1

Во-первых, вы должны четко определить, что вы имеете в виду под «стоимость цикла». Это можно интерпретировать как алгоритмические циклы или циклы процессоров. После того, как вы это сделали, следующий шаг - поднять дзэн вашего подхода - теоретический или тест.

Во-первых, теоретические.

Если это алгоритмические циклы, я бы сделал это определение с помощью обзора кода. Эти шаги были бы

1. Определить библиотеки С, что вы используете
2. Получить исходный код для этой конкретной квадратного корня библиотеки реализации
3. Выполнить анализ исходного кода для оценки сложности (стоимость цикла алгоритма)

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

Если циклы процессора, вы бы сделать это определение подобным способом, но некоторые детали изменится:

1. Определить машинный код, который будет работать на процессоре, выполнив 1, 2, и 3 выше
2. Узнайте больше о процессорах, чем я знаю
3. Вероятно, понимают, что это бесполезно и просто проверить его (Other SO useful answer)

Для тестового подхода требуется чтобы:

1. Определить, что все окружение вы хотите эту информацию для
   1. Процессоры
   2. Операционные системы
2. Автор тестовое приложение
   1. Если выполнять все операции, которые требуется тест, включая что-либо за пределами sqrt, вам нужна эта информация (например, вход для ввода s, выходы)
   2. Если выполнить заданное число итераций в течение длительного периода времени
   3. Если выполнить одну команду и выйти и назвать определенное количество итераций длительного периода времени
   4. действительно нужно просто подумайте, определите, почему вы хотите эту информацию и как вы ее используете, и придумайте тестовое приложение, которое удалит как можно больше переменных.
3. Запустить приложение
   1. Run как близко к окружающей среде, вы заботитесь о
   2. Если вы конечное использование этой информации будет предсказанием производительности для пользователей - тест в представительном среде (если возможно запускать 10 различных окон веб-браузера во время просмотра потока фильмов netflix, проверить в этих условиях)
4. Проведите какой-то анализ набора данных, чтобы получить разумный прогноз.

Answer 2

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

Answer 3

Боюсь, что дни, когда вы могли определить стоимость вызова функции в тактовых циклах, давно прошли (для большинства платформ).

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

Стоимость зависит от многих факторов. Процессор имеет возможность переупорядочивать инструкции и выполнять инструкции вашей функции параллельно, а также параллельно с другими инструкциями даже из другого потока (если ядро ​​поддерживает одновременную многопоточность). Цели ветвей «догадываются» и выполняются до того, как условие будет полностью оценено. Если «догадка» оказывается неправильной, вычисления отбрасываются. Предположения основаны на некоторой статистике, собранной процессором. Разница во времени выполнения в случае, если код находится в кеше, а в случае, если он не может быть огромным. Даже если бы вы смогли определить, что выполнение функции в некоторых случаях выполнялось в течение x циклов, при следующем запуске кода вы можете получить y и y может отличаться от x.

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

Answer 4

С хорошим встроенным компилятором стоимость вызова sqrt() - одна сопроцессорная инструкция: FSQRT. Циклы действительно трудно определить с суперскалярными архитектурами.

Answer 5

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

Вот nice page, в котором говорится, что он рассчитан на четыре итерации для 32 бит для четырехзначной точности и пяти итераций для 64 бит.

Вот как это делается для ситуаций, когда это не делается на аппаратных средствах.

Answer 6

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

На самом деле существует код для того, что вы хотите прямо здесь! http://beige.ucs.indiana.edu/B673/node104.html

Основная идея:

#include <time.h> 
... 
int main(){ 
    time_t t0, t1; 
    t0 = time(NULL); 
    for (int i=1; i <= huge number; i++) //to hopefully make up for statistical noise 
     sqrt(i) 
    t1 = time(NULL); 
    // do the math and print 
} 

Answer 7

Чтобы измерить время в CPP, теперь вы можете использовать библиотеку Chrono, которая является частью C++ 11, и предоставляет множество функций, связанных с синхронизацией в CPP. Ссылка: http://www.cplusplus.com/reference/chrono/ Я использую часы с высоким разрешением для приблизительной оценки времени работы. Когда я выполнил 100 000 функций sqrt, это заняло ~ 0,009 секунды. Все, что ниже этого не регистрировалось, хотя я только нашел квадратный корень из числа и положил его в двойную переменную.