Линейные алгоритмы и структуры

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

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

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

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