 |
23. Способы измерения времени. Применение рекурсии. Примеры.
|
|
|
|
23. Способы измерения времени. Применение рекурсии. Примеры.
3 способа получения текущего времени в C:
§ Функция clock()
clock_t clock( void ); (< time. h> )
§ API функции
В процессоре есть спец. датчик, который отсчитывает такты, начиная с некоторого момента. Можно запрашивать значение этого датчика – команда rdtsc.
§ Ассемблерные вставки
clock_t start, finish;
double d;
unsigned long i = 6000000;
start = clock();
while (i--);
finish = clock();
d = (double)(finish - start)/CLOCKS_PER_SEC;
printf(" %2. 1lf seconds\n", d);
Под рекурсией понимается метод программирования, связанный с последовательным разбиением задачи на подзадачи меньшего размера до тех пор, пока подзадачи не станут элементарными. Если функция вызывает себя непосредственно – прямая рекурсия. Если функция вызывает себя через другую функцию – косвенная рекурсия.
Задача: нужно выкопать траншею. Обычный порядок мысли: последовательно копаем от начала до конца. Рекурсивный порядок мысли: сначала копаем левую половину, потом правую. При этом при раскопках левой половины вновь копаем ее левую половину, потом правую...
24. Программная оптимизация: связь с архитектурой процессора, приемы оптимизации, векторизация, оптимизация циклов.
Программная оптимизация вступает в дело, когда алгоритм выбран, реализован и отлажен. Без понимания принципов работы архитектуры программная оптимизация сильно затруднена.
Для того, чтобы программа работала быстро, она должна обеспечивать:
§ Отсутствие лишних вычислений.
§ Хороший прогноз ветвлений.
§ Быструю работу с памятью.
§ Производительность вещественных операций.
§ Использование SIMD-команд (векторизация).
§ Удачную смесь инструкций.
Размещайте наиболее часто реализующиеся ветвления в начале цепочки вложенных проверок.
|
|
|
Разворачивайте цикл
– удачная смесь инструкций (параллельность)
– сокращение числа итераций – ветвлений
Убирайте зависимость по данным внутри итерации.
Перестраивайте алгоритм, чтобы не работать с очень малыми числами (avoid denormals).
По возможности понизьте точность используемых типов данных (float вместо double).
Выравнивание: избегаем невыравненного доступа к данным – избегаем штрафов.
Располагаем в структурах поля от большего к меньшему. Дополняем до 16, 32...
Локальность: стремимся программировать так, чтобы нужные данные находились в кэш-памяти.
– разбиваем циклы на 2 (работа с разными массивами);
– перестановка циклов;
– блочные алгоритмы (умножение матриц);
– массивы структур и структуры массивов – в зависимости от задачи.
Если у вас:
– простой внутренний цикл;
– вы обрабатываете массивы;
– нет зависимости между итерациями и внутри итерации;
– нет смеси типов данных;
– правильный компилятор, включены опции;
то: Ваш внутренний цикл будет векторизован (использование SIMD)!
|
|
|
