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)!