Как оптимизировать свой процессор: изменить и включить L2 и L3 своих кэшей процессора. Делиться не всегда полезно: оптимизируем работу с кэш-памятью

С помощью Starwind RAMDisk вы можете бесплатно настроить под Windows один или несколько RAM-дисков. Единственное ограничение: размеры каждого такого RAM-диска не могут превышать 1 Гбайт.

2 Может понадобиться драйвер

3 Обзор RAM-дисков

4 Добавляем RAM-диск

5 При настройке поможет ассистент

6 Ограничение в 1 Гбайт

Увеличение производительности кэш-памяти

Формула для среднего времени доступа к памяти в системах с кэш-памятью выглядит следующим образом:

Среднее время доступа = Время обращения при попадании + Доля промахов x Потери при промахе

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

Зачем увеличивать кэш?

Первичная причина увеличения объема встроенного кэша может заключаться в том, что кэш-память в современных процессорах работает на той же скорости, что и сам процессор. Частота процессора в этом случае никак не меньше 3200 MГц. Больший объем кэша позволяет процессору держать большие части кода готовыми к выполнению. Такая архитектура процессоров сфокусирована на уменьшении задержек, связанных с простоем процессора в ожидании данных. Современные программы, в том числе игровые, используют большие части кода, который необходимо извлекать из системной памяти по первому требованию процессора. Уменьшение промежутков времени, уходящих на передачу данных от памяти к процессору, - это надежный метод увеличения производительности приложений, требующих интенсивного взаимодействия с памятью. Кэш L3 имеет немного более высокое время ожидания, чем L 1 и 2, это вполне естественно. Хоть он и медленнее, но все-таки он значительно более быстрый, чем обычная память. Не все приложения выигрывают от увеличения объема или скорости кэш-памяти. Это сильно зависит от природы приложения.

Если большой объем встроенного кэша - это хорошо, тогда что же удерживало Intel и AMD от этой стратегии ранее? Простым ответом является высокая себестоимость такого решения. Резервирование пространства для кэша очень дорого. Стандартный 3.2GHz Northwood содержит 55 миллионов транзисторов. Добавляя 2048 КБ кэша L3, Intel идет на увеличение количества транзисторов до 167 миллионов. Простой математический расчет покажет нам, что EE - один из самых дорогих процессоров.

Сайт AnandTech провел сравнительное тестирование двух систем, каждая из которых содержала два процессора - Intel Xeon 3,6 ГГц в одном случае и AMD Opteron 250 (2,4 ГГц) - в другом. Тестирование проводилось для приложений ColdFusion MX 6.1, PHP 4.3.9, и Microsoft .NET 1.1. Конфигурации выглядели следующим образом:

Dual Opteron 250;

2 ГБ DDR PC3200 (Kingston KRX3200AK2);

Системная плата Tyan K8W;

Dual Xeon 3.6 ГГц;

Материнская плата Intel SE7520AF2;

ОС Windows 2003 Server Web Edition (32 бит);

1 жесткий IDE 40 ГБ 7200 rpm, кэш 8 МБ

На приложениях ColdFusion и PHP, не оптимизированных под ту или иную архитектуру, чуть быстрее (2,5-3%) оказались Opteron"ы, зато тест с.NET продемонстрировал последовательную приверженность Microsoft платформе Intel, что позволило паре Xeon"ов вырваться вперед на 8%. Вывод вполне очевиден: используя ПО Microsoft для веб-приложений, есть смысл выбрать процессоры Intel, в других случаях несколько лучшим выбором будет AMD.

Больше - не всегда лучше

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

Один из способов обойти эти трудности -- передача логики управления кэш-памятью от аппаратного обеспечения к программному.

«Компилятор потенциально в состоянии анализировать поведение программы и генерировать команды по переносу данных между уровнями памяти», -- отметил Шен.

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

Никогда, ни при каких обстоятельствах не производите изменений в реестре и системных файлах Windows, не имея резервной копии последних. Существует множество способов резервирования системы как стандартными средствами Windows, так и при помощи специальных программ. Этот вопрос неоднократно освещался на страницах компьютерной прессы и я надеюсь, что у каждого читателя уже имеется необходимый опыт в области резервирования реестра. А тем, кто пожелает создать свою программку backup, не изучая языки программирования, предлагаю прочитать статью, где подробно описано создание командных файлов для резервирования и восстановления системы. Будем считать, что резервная копия у Вас уже имеется, и мы можем продолжить наши исследования.

Оптимизация кэша жёсткого диска.

По мнению многих специалистов в области ОС Windows, размер кэша должен быть фиксированным и полностью зависит от объема оперативной памяти, установленной на компьютере. Мол, Windows не умеет работать с кэшем и тратит на это слишком много оперативки. Предлагаются даже стандартные схемы для определения размера кэша, исходя из размера памяти. Всё это прописывают в разделе файла system.ini в виде MinFileCache = размер в кб и MaxFileCache = размер в кб. Такой подход действительно позволит сэкономить некоторый объем памяти, но может привести к общему замедлению работы системы, особенно на домашних компьютерах, где в течение дня могут выполняться десятки самых разных программ, как мультимедийных, так и офисных и каждая из них требует разного размера кэша и оперативной памяти. Вряд ли Вам доставит удовольствие редактировать system.ini и перезагружать компьютер перед каждым запуском новой программы.

Универсальный же размер дискового кэша, на мой взгляд, возможность чисто теоритическая, так как в одних случаях всё равно будет наблюдаться избыток кэша и недостаток оперативки, в других — наоборот. А завтра сынишка притащит какую-нибудь игру с нестандартным использованием ресурсов памяти и system.ini снова придется редактировать? Современные версии Windows способны выполнять код программы прямо из кэша, т.е. кэш перестал быть промежуточным звеном между винчестером и памятью, а является ни чем иным, как частью оперативной памяти. Так что же мы, в таком случае, пытаемся ограничить? Вывод: Ограничение размера кэша жёсткого диска в большинстве случаев приводит к понижению производительности системы. Исключение составляют разве что компьютеры, выполняющие сходные задачи, в основном связанные с передачей больших объемов данных. Здесь оптимизация размера кэша действительно поможет добиться максимальной производительности системы.

Виртуальная память.

Большинство советов по этому поводу появилось на свет во времена победного шествия Windows 95, когда новый графический интерфейс потребовал дополнительной и достаточно дорогой оперативной памяти. Почему же эти древние советы перетаскиваются за седую бороду на новые платформы? Ведь современные версии Windows работают с виртуальной памятью абсолютно иначе. Итак, что же нам предлагают сотворить с файлом подкачки? Да всё то же, что и для древних окон, а именно: сделать его размер фиксированным и равным 3–4 размерам оперативной памяти. Необходимость этих действий объясняется обычно тем, что OS затрачивает чуть ли не целую вечность на изменение размера файла подкачки, данные излишне фрагментируются и тем самым тормозится работа системы.

Предвижу всеобщее негодование, но всё же берусь утверждать, что подобные объяснения если не полная чепуха, то, по крайней мере, давно потеряли свою актуальность. Лишив Windows возможности самостоятельно определять необходимый размер файла подкачки, Вы рискуете получить сообщение о невозможности запуска определённых программ. Риск увеличивается, если используется многозадачность Windows. К примеру, запросто может возникнуть ситуация, когда Вам будет необходима одновременная работа с Photoshop, текстовым процессором, HTML редактором и ещё каким-нибудь аниматором. Где гарантия, что в это время Вам не понадобится открыть графический файл размером в несколько десятков Мб для последующего редактирования? Представьте себе, что в этот момент произойдёт сбой системы из за того, что Windows не сможет увеличить размер виртуальной памяти, а результаты своих трудов Вы по какой-то причине не сохранили?! Это уже не смешно. Хочу обратить внимание уважаемых читателей на следующий факт. Windows изменяет размер файла подкачки динамически и в основном тогда, когда ресурсы системы относительно свободны и обращение к диску не вызывает никаких неудобств.

После завершения текущей задачи, размер файла подкачки остаётся неизменным в течение некоторого периода времени. Если в это время Вы пойдёте приготовить себе очередную чашечку кофе, то даже не заметите никаких действий со стороны OS, ну а если предпочтёте продолжить работу, то вряд ли будете сидеть сложа руки эти 2,5 минуты, а запустите очередную программу. Кроме того, потребность в виртуальной памяти для современных программ уменьшена в несколько раз благодаря использованию так называемого принципа прямого считывания (Linear Executable). Такие программы не загружаются в память полностью, а сопоставляют свой код страницам памяти и производят загрузку необходимых библиотек по мере необходимости. Таким образом обеспечивается наиболее полное и оптимальное использование как оперативной, так и виртуальной памяти. Сомнительными являются и предположения, что фиксация размера файла подкачки позволит избежать излишней фрагментации данных. Ведь внутри самого файла данные всё равно будут фрагментированы, возможно, даже в большей степени, чем при обычном использовании. Что касается переноса файла подкачки в начало диска или на отдельный физический диск, то такие методы действительно имеют право на жизнь. Но эффект от этого Вы едва ли сможете заметить.

Для осуществления подобных мероприятий понадобятся специальные дорогостоящие утилиты вроде знаменитого пакета господина Нортона, которые неизбежно пропишут в автозагрузку свои программы, тем самым компенсируя улучшенную виртуальную память уменьшением физической. Чтобы избежать этого, придётся оптимизировать уже сами утилиты. Кроме этого, работа с утилитами требует хотя бы элементарного понимания того, что происходит при их использовании. Особенно опасны автоматизированные функции. Мне не раз приходилось восстанавливать системы после использования Norton Utilities. Причина до смешного проста - неправильные региональные настройки. Дело в том, что программа Norton Disk Doctor, входящая в состав утилит считывает код страны. И если на Вашей машине установлена русская версия Windows, а региональные настройки, скажем, США, то программа посчитает все русскоязычные имена файлов и папок за ошибку. Результат, я думаю, понятен. И это всего лишь незначительная часть возможных проблем. Вывод: Современные версии Windows не нуждаются в оптимизации виртуальной памяти. А если Вы всё же решите переместить своп файл в начало диска или на отдельный диск, то не забудьте изучить цены на лицензионные утилиты + дополнительный жёсткий диск. На мой взгляд, линейка памяти обойдётся значительно дешевле.

Интернет и модем.

Продвинутые пользователи Windows советуют добавить в раздел реестра HKEY_LOCAL_MACHINE\ System\ CurrentControlSet\ Services\ Class\ NetTrans\ 0000 (может быть 0001 и т.д.) некоторые параметры, оказывающие прямое влияние на быстродействие модема. Главным параметром является MaxMTU. Напомню, что MTU (Maximum Transmition Unit) - это максимальный размер пакета данных, который может быть передан по сети за один физический фрейм. Наиболее оптимальным считается значение MaxMTU=576. Но простите, оптимальным - то для чего? Чтобы ответить на этот вопрос, я предлагаю провести маленький эксперимент. Давайте воспользуемся гостевым подключением к сети Интернет, предоставляемым одним из самых популярных столичных провайдеров — Svit Online. Для подключения к удалённому компьютеру будем использовать порядком подзабытую программу Hyper Terminal, номер дозвона 490-0-490, логин- svit, пароль - online. И что же мы увидим после ввода пароля?

Удалённый компьютер сообщает нам присвоенный IP адрес и… MTU=1500! Теперь Вам ясно, для чего значение MaxMTU=576 является оптимальным? Не иначе, как для замедления передачи данных. Для оптимальной передачи, оказывается, нужно исходить из значения 1500. Я не буду подробно останавливаться на расчётах других параметров, таких, как MSS, TTL, так как считаю все эти мероприятия далеко не безобидными, учитывая стоимость услуг провайдеров и поминутную оплату городского телефона. Windows прекрасно справляется с задачей автоматического определения MTU сама, без нашего вмешательства. Лучше сосредоточить своё внимание на повышении качества линии связи, хотя бы в пределах собственной квартиры. Чаще причиной ухудшения связи являются разного рода скрутки, плохие контакты и множество параллельных телефонных аппаратов, а не железо и soft. Но это-тема для отдельного разговора.

Участь быть оптимизированной постигла и Windows Me. Чего тут только не предлагают: и удалить PC Health, и отключить System Restore, и избавиться от Media Player 7 с Movie Maker’ом, и заменить IE 5,5 более старой версией, и даже ввести реальный режим DOS. И всё это только для того, чтобы установить новую операционку на ПК с Pentium 133 МГц и 32 Мб ОЗУ. Но тогда что от неё останется? О какой платформе Windows Me идёт речь? Ведь даже если Вам удастся поместить двигатель от «Mersedes» в «Запорожец», он от этого «Mesredes’ом» не станет. В результате — дополнительные сбои, неудобство в работе, а чаще — format C:. Вот тут то пользователь и поверит рассказам о легендарной глючности Windows. Точнее, не поверит, а проверит на собственном горьком опыте.

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

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

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

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

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

На написание этой статьи меня вдохновила шестая глава из книги Computer Systems: A Programmer"s Perspective . В другой статье из этой серии, «Оптимизация кода: процессор» , мы также боремся за такты процессора.

Память тоже имеет значение

Рассмотрим две функции, которые суммируют элементы матрицы. Они практически одинаковы, только первая функция обходит элементы матрицы построчно, а вторая - по столбцам.

Int matrixsum1(int size, int M) { int sum = 0; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { sum += M[i][j]; // обходим построчно } } return sum; } int matrixsum2(int size, int M) { int sum = 0; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { sum += M[j][i]; // обходим по столбцам } } return sum; }

Обе функции выполняют одно и то же количество инструкций процессора. Но на машине с Core i7 Haswell первая функция выполняется в 25 раз быстрее для больших матриц. Этот пример хорошо демонстрирует, что память тоже имеет значение . Если вы будете оценивать эффективность программ только в терминах количества выполняемых инструкций, вы можете писать очень медленные программы.

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

Иерархия памяти

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

На вершине иерархии находятся регистры процессора. Доступ к ним занимает 0 тактов, но их всего несколько штук. Далее идёт несколько килобайт кэш-памяти первого уровня, доступ к которой занимает примерно 4 такта. Потом идёт пара сотен килобайт более медленной кэш-памяти второго уровня. Потом несколько мегабайт кэш-памяти третьего уровня. Она гораздо медленней, но всё равно быстрее оперативной памяти. Далее расположена относительно медленная оперативная память.

Оперативную память можно рассматривать как кэш для локального диска. Диски это рабочие лошадки среди устройств хранения. Они большие, медленные и стоят дёшево. Компьютер загружает файлы с диска в оперативную память, когда собирается над ними работать. Разрыв во времени доступа между оперативной памятью и диском колоссальный. Диск медленнее оперативной памяти в десятки тысяч раз, и медленнее кэша первого уровня в миллионы раз. Выгоднее обратиться несколько тысяч раз к оперативной памяти, чем один раз к диску. На это знание опираются такие структуры данных, как B-деревья , которые стараются разместить больше информации в оперативной памяти, пытаясь избежать обращения к диску любой ценой.

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

Современная система имеет примерно такие характеристики:

Быстрая память стоит очень дорого, а медленная очень дёшево. Это великая идея архитекторов систем совместить большие размеры медленной и дешёвой памяти с маленькими размерами быстрой и дорогой. Таким образом система может работать на скорости быстрой памяти и иметь стоимость медленной. Давайте разберёмся как это удаётся.

Допустим, ваш компьютер имеет 8 ГБ оперативной памяти и диск размером 1000 ГБ. Но подумайте, что вы не работаете со всеми данными на диске в один момент. Вы загружаете операционную систему, открываете веб-браузер, текстовый редактор, пару-тройку других приложений и работаете с ними несколько часов. Все эти приложения помещаются в оперативной памяти, поэтому вашей системе не нужно обращаться к диску. Потом, конечно, вы закрываете одно приложение и открываете другое, которое приходится загрузить с диска в оперативную память. Но это занимает пару секунд, после чего вы несколько часов работаете с этим приложением, не обращаясь к диску. Вы не особо замечаете медленный диск, потому что в один момент вы работаете только с небольшим бъёмом данных, которые кэшируются в оперативной памяти. Вам нет смысла тратить огромные деньги на установку 1024 ГБ оперативной памяти, в которую можно было бы загрузить содержимое всего диска. Если бы вы это сделали, вы бы почти не заметили никакой разницы в работе, это было бы «деньги на ветер».

Так же дело обстоит и с маленькими кэшами процессора. Допустим вам нужно выполнить вычисления над массивом, который содержит 1000 элементов типа int . Такой массив занимает 4 КБ и полностью помещается в кэше первого уровня размером 32 КБ. Система понимает, что вы начали работу с определённым куском оперативной памяти. Она копирует этот кусок в кэш, и процессор быстро выполняет действия над этим массивом, наслаждаясь скоростью кэша. Потом изменённый массив из кэша копируется назад в оперативную память. Увеличение скорости оперативной памяти до скорости кэша не дало бы ощутимого прироста в производительности, но увеличило бы стоимость системы в сотни и тысячи раз. Но всё это верно только если программы имеют хорошую локальность.

Локальность

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

Рассмотрим, программу, которая суммирует элементы массива:

Int sum(int size, int A) { int i, sum = 0; for (i = 0; i < size; i++) sum += A[i]; return sum; }

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

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

Перемещение данных между уровнями иерархии осуществляется блоками определённого размера. К примеру, процессор Core i7 Haswell перемещает данные между своими кэшами блоками размером в 64 байта. Рассмотрим конкретный пример. Мы выполняем программу на машине с вышеупомянутым процессором. У нас есть массив v , содержащий 8-байтовые элементы типа long . И мы последовательно обходим элементы этого массива в цикле. Когда мы читаем v , его нет в кэше, процессор считывает его из оперативной памяти в кэш блоком размером 64 байта. То есть в кэш отправляются элементы v –v . Далее мы обходим элементы v , v , ..., v . Все они будут в кэше и доступ к ним мы получим быстро. Потом мы читаем элемент v , которого в кэше нет. Процессор копирует элементы v –v в кэш. Мы быстро обходим эти элементы, но не находим в кэше элемента v . И так далее.

Поэтому если вы читаете какие-то байты из памяти, а потом читаете байты рядом с ними, они наверняка будут в кэше. В этом выгода от пространственной локальности. Нужно стремиться на каждом этапе вычисления работать с данными, которые расположены в памяти рядом.

Желательно обходить массив последовательно, читая его элементы один за другим. Если нужно обойти элементы матрицы, то лучше обходить матрицу построчно, а не по столбцам. Это даёт хорошую пространственную локальность. Теперь вы можете понять, почему функция matrixsum1 работала медленнее функции matrixsum2 . Двумерный массив расположен в памяти построчно: сначала расположена первая строка, сразу за ней идёт вторая и так далее. Первая функция читала элементы матрицы построчно и двигалась по памяти последовательно, будто обходила один большой одномерный массив. Эта функция в основном читала данные из кэша. Вторая функция переходила от строки к строке, читая по одному элементу. Она как бы прыгала по памяти слева-направо, потом возвращалась в начало и опять начинала прыгать слева-направо. В конце каждой итерации она забивала кэш последними строками, так что в начале следующей итерации первых строк кэше не находила. Эта функция в основном читала данные из оперативной памяти.

Дружелюбный к кэшу код

Как программисты вы должны стараться писать код, который, как говорят, дружелюбный к кэшу (cache-friendly ). Как правило, основной объём вычислений производится лишь в нескольких местах программы. Обычно это несколько ключевых функций и циклов. Если есть вложенные циклы, то внимание нужно сосредоточить на самом внутреннем из циклов, потому что код там выполняется чаще всего. Эти места программы и нужно оптимизировать, стараясь улучшить их локальность.

Вычисления над матрицами очень важны в приложениях анализа сигналов и научных вычислениях. Если перед программистами встанет задача написать функцию перемножения матриц, то 99.9% из них напишут её примерно так:

Void matrixmult1(int size, double A, double B, double C) { double sum; for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) { sum = 0.0; for (int k = 0; k < size; k++) sum += A[i][k]*B[k][j]; C[i][j] = sum; } }

Этом код дословно повторяет математическое определение перемножения матриц. Мы обходим все элементы окончательной матрицы построчно, вычисляя каждый из них один за другим. В коде есть одна неэффективность, это выражение B[k][j] в самом внутреннем цикле. Мы обходим матрицу B по стобцам. Казалось бы, ничего с этим не поделаешь и придётся смириться. Но выход есть. Можно переписать то же вычисление по другому:

Void matrixmult2(int size, double A, double B, double C) { double r; for (int i = 0; i < size; i++) for (int k = 0; k < size; k++) { r = A[i][k]; for (int j = 0; j < size; j++) C[i][j] += r*B[k][j]; } }

Теперь функция выглядит очень странно. Но она делает абсолютно то же самое. Только мы не вычисляем каждый элемент окончательной матрицы за раз, мы как бы вычисляем элементы частично на каждой итерации. Но ключевое свойство этого кода в том, что во внутреннем цикле мы обходим обе матрицы построчно. На машине с Core i7 Haswell вторая функция работает в 12 раз быстрее для больших матриц. Нужно быть действительно мудрым программистом, чтобы организовать код таким образом.

Блокинг

Существует техника, которая называется блокинг . Допустим вам надо выполнить вычисление над большим объёмом данных, которые все не помещаются в кэше высокого уровня. Вы разбиваете эти данные на блоки меньшего размера, каждый из которых помещается в кэше. Выполняете вычисления над этими блоками по отдельности и потом объёдиняете результат.

Можно продемонстрировать это на примере. Допустим у вас есть ориентированный граф, представленный в виде матрицы смежности. Это такая квадратная матрица из нулей и единиц, так что если элемент матрицы с индексом (i, j) равен единице, то существует грань от вершины графа i к вершине j. Вы хотите превратить этот ориентированный граф в неориентированный. То есть, если есть грань (i, j), то должна появиться противоположная грань (j, i). Обратите внимание, что если представить матрицу визуально, то элементы (i, j) и (j, i) являются симметричными относительно диагонали. Эту трансформацию нетрудно осуществить в коде:

Void convert1(int size, int G) { for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) G[i][j] = G[i][j] | G[j][i]; }

Блокинг появляется естественным образом. Представьте перед собой большую квадратную матрицу. Теперь иссеките эту матрицу горизонтальными и вертикальными линиями, чтобы разбить её, скажем, на 16 равных блока (четыре строки и четыре столбца). Выберите два любых симметричных блока. Обратите внимание, что все элементы в одном блоке имеют симметричные элементы в другом блоке. Это наводит на мысль, что ту же операцию можно совершать над каждым блоком поочерёдно. В этом случае на каждом этапе мы будем работать только с двумя блоками. Если блоки сделать достаточно маленького размера, то они поместятся в кэше высокого уровня. Выразим эту идею в коде:

Void convert2(int size, int G) { int block_size = size / 12; // разбить на 12*12 блоков // представим, что делится без остатка for (int ii = 0; ii < size; ii += block_size) { for (int jj = 0; jj < size; jj += block_size) { int i_start = ii; // индекс i для блока принимает значения [j] = G[i][j] | G[j][i]; } } }

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

На машине с процессором Core i7 Haswell вторая функция не выполняется быстрее. На машине с более простым процессором Pentium 2117U вторая функция выполняется в 2 раза быстрее . На машинах, которые не выполняют предвыборку, производительность улучшилась бы ещё сильнее.

Какие алгоритмы быстрее

Все знают из курсов по алгоритмам, что нужно выбирать хорошие алгоритмы с наименьшей сложностью и избегать плохих алгоритмов с высокой сложностью. Но эти сложности оценивают выполнение алгоритма на теоретической машине, созданной нашей мыслью. На реальных машинах теоретически плохой алгоритм может выполнятся быстрее теоретически хорошего. Вспомните, что получить данные из оперативной памяти занимает 200 тактов, а из кэша первого уровня 4 такта - это в 50 раз быстрее. Если хороший алгоритм часто трогает память, а плохой алгоритм размещает свои данные в кэше, хороший может выполняться медленнее плохого. Также хороший алгоритм может хуже выполняться на процессоре, чем плохой. К примеру, хороший алгоритм вносит зависимость данных и не может загрузить конвеер, а плохой лишён этой проблемы и на каждом такте отправляет в конвеер новую инструкцию. Иными словами, сложность алгоритма это ещё не всё. То, как алгоритм будем выполняться на конкретной машине с конкретными данными, имеет значение.

Представим, что вам нужно реализовать очередь целых чисел, и новые элементы могут добавляться в любую позицию очереди. Вы выбираете между двумя реализациями: массив и связный список. Чтобы добавить элемент в середину массива, нужно сдвинуть вправо половину массива, что занимает линейное время. Чтобы добавить элемент в середину списка, нужно дойти по списку до середины, что также занимает линейное время. Вы думаете, что раз сложности у них одинаковые, то лучше выбрать список. Тем более у списка есть одно хорошее свойство. Список может расти без ограничения, а массив придётся расширять, когда он заполнится. Давайте представим что длина очереди 1000 элементов и нам нужно вставить элемент в середину очереди. Элементы списка хаотично разбросаны по памяти, а получить данные из памяти занимает 200 тактов. Поэтому чтобы обойти 500 элементов, нам понадобится 500*200=100"000 тактов. Массив расположен в памяти последовательно, что позволит нам наслаждаться скоростью кэша первого уровня с временем доступа 4 такта. Используя несколько оптимизаций, мы можем двигать элементы, тратя 1-4 такта на элемент. Мы сдвинем половину массива максимум за 500*4=2000 тактов. Это быстрее в 50 раз .

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

Заключение

Система памяти организована в виде иерархии устройств хранения с маленькими и быстрыми устройствами вверху иерархии и большими и медленными устройствами внизу. Программы с хорошей локальностью работают с данными из кэшей процессора. Программы с плохой локальностью работают с данными из относительно медленной оперативной памяти.

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

• Сконцентрируйте ваше внимание на внутренних циклах. Именно там происходит наибольший объём вычислений и обращений к памяти.
• Постарайтесь максимизировать пространственную локальность, читая объекты из памяти последовательно, в том порядке, в котором они в ней расположены.
• Постарайтесь максимизировать временную локальность, используя объекты данных как можно чаще после того, как они были прочитаны из памяти.

Одна из самых раздражающих вещей в Windows - это то, что она может зависнуть на несколько секунд, судорожно делая что-то на диске. Одна из причин - работа Windows с дисковой виртуальной памятью, заложенная по умолчанию. Windows загружает драйверы и приложения в память, пока она не заполнится, а затем начинает использовать часть жесткого диска, чтобы «подкачать» информацию, освобождая оперативную память для задач более высокого приоритета. Файл, который использует Windows для этого типа «виртуальной памяти» файл подкачки pagefile.sys, - хранится в корневом каталоге диска.
Поскольку жесткий диск работает медленнее, чем физическая оперативная память, то чем больше Windows подкачивает, тем медленнее работает компьютер. Вот почему добавление оперативной памяти ускоряет работу - уменьшается необходимость в виртуальной памяти. Независимо от объема установленной физической памяти есть способ улучшить производительность виртуальной памяти. Настройки Windows по умолчанию довольно консервативны, но, к счастью, их можно изменить для улучшения производительности. Важно помнить, что эксперименты с такими настройками оправданны только для систем с объемными жесткими дисками, когда виртуальной памяти можно уделить больше дискового пространства.
Часть 1: Настройки виртуальной памяти
Одна из причин того, что настройки по умолчанию приводят к низкой производительности, - файл подкачки растет и уменьшается при использовании, быстро становясь фрагментированным. Первый шаг должен устранить эту проблему, установив фиксированный размер файла подкачки.
Заметьте, что создание фиксированного файла подкачки обеспечит более постоянный объем свободного дискового пространства. Если жесткий диск переполняется, запретите Windows использовать последний бит свободного пространства.
1. В Панели управления откройте страницу Система и нажмите ссылку Дополнительные параметры системы.
2. Под вкладкой Дополнительно в разделе Быстродействие нажмите кнопку Параметры.
3. На странице параметров быстродействия выберите вкладку Дополнительно и затем нажмите Изменить, чтобы открыть окно виртуальной памяти.
4. Выключите параметр Автоматически выбирать объем файла подкачки, чтобы получить доступ к настройкам в этом окне.
5. Настройки виртуальной памяти устанавливаются отдельно для каждого диска. Если у вас только один диск, виртуальная память уже включена для этого диска. Если вы используете больше одного диска или раздела, то виртуальная память по умолчанию будет включена только на диске с Windows. Начните с диска, который в настоящий момент содержит файл подкачки.
Другой способ запретить Windows интенсивно использовать жесткий диск - отключение виртуальной памяти. Еще лучше будет переместить файл подкачки на другой физический диск, в этом случае при работе Windows с виртуальной памятью процесс не будет высасывать все соки из основного диска компьютера,
6. Чтобы установить фиксированный размер виртуальной памяти, отметьте Указать размер, а затем введите одно и то же значение в Исходный размер и в Максимальный размер.
Объем определите сами. Если на диске есть место, то выделите место в 2-3 раза больше объема установленной оперативной памяти. Можно поэкспериментировать с различными размерами для того, чтобы определить наиболее подходящий.
7. Важно: после того как вы сделали изменения, нажмите Задать или ОК для фиксации изменений перед переходом к другому диску.
8. Нажмите ОК в каждом из трех открытых диалоговых окон.
Если вы просто изменили размеры файла подкачки, изменение сразу вступит в силу. Но если вы добавили файл подкачки на каком-либо диске, то необходимо перезапустить Windows, прежде чем вы сможете использовать новые настройки.
Часть 2: Дефрагментируйте файл подкачки
Шаги, описанные в предыдущем разделе, устраняют возможность фрагментации файла подкачки, но они не исправят его, если он уже фрагментирован. Для лучшей производительности виртуальная память должна быть дефрагментирована, но если файл подкачки имеет фиксированный размер, то это нужно сделать только один раз. Есть несколько способов дефрагментировать файл подкачки:
Используйте PerfectDisk
Используйте усовершенствованный дефрагментатор PerfectDisk. Дайте ему команду дефрагментировать системные файлы, и он запланирует дефрагментацию при следующем запуске Windows.