В прошлый выпуск был был поднят вопрос - почему слабое знание низкоуровневых особенностей работы процессора приводит к написанию посредственных приложений? Многие искреннее удивляются почему в 21 веке при огромных достижениях в информационных технологий нельзя расслабиться и отдаться высокоуровневым языкам программирования? Самый главный аргумент - "а что, пилоты Формулы-1 разбираются в своей технике досконально? Не думаю. Нужно просто пользоваться абстракциями и не думать о шестеренках".
Немного про устройство кэша
Назначение этой памяти это ускорение работы с инструкциями и данными минимум по двум причинам:
- нахождение памяти в чипе на минимальной дистанции от других узлов процессора,
- выборка из кэша происходит линиями по 16 - 64 байта за один раз.
На рисунке выше желтым маркером обведена шина данных, по которой машинные инструкции следуют к декодеру. Если кто не рассмотрел, то ширина этой шины 128 бит. Это означает передачу 16 байт за раз.
Тут же обращаем внимание на ширину шины данных, идущей от процессора к оперативной памяти (на самом деле к чипсету, но не суть). Это место обведено красным карандашом. 32 бита (D[31:0]) это передача 4 байт за раз. При заполнении одной линии кэша приходится 4 раза обращаться к RAM памяти.
Схематично кэш память изображают в следующем виде:
В процессоре Intel 80486DX2 размер общего кэша равен 8 кб, что при размере одной линии в 16 байт дает количество этих линий всего 512 штук. На рисунке выше индекс у кэш памяти это порядковый номер линии. Тэг это адрес, по которому содержимое линии хранится в оперативной памяти. Именно совпадение выставленного на память адреса с содержимым тэга является условием выдачи данных линии (16 байт).
При несовпадении адреса со всеми тэгами линий происходит исключение, обработка которого направлена на подгрузку данных из оперативной памяти или накопителя данных. Разумеется, подгрузка линий кэша, как мы ранее выяснили, это очень медленная операция.
Теперь про устройство массива
Массивом называют упорядоченное множество однотипных элементов, расположенных в памяти друг за другом.
Доступ к элементам массива обеспечивается взаимодействием двух регистров, один из которых хранит адрес нулевого элемента, второй регистр хранит смещение от нулевого элемента. При сложении содержимого этих регистров получается адрес необходимого элемента. Это очень удобно для организации доступа к элементам по их индексу (array[2]=7).
Двумерный массив это просто одна из многочисленных абстракций, за которой прячется одномерный массив.
Почему программы теряют производительность?
Настало время вернуться к той задаче, из-за которой все и началось. Очень часто математические модели предметов из реальной жизни представляют собой массивы чисел.
При нахождении угла наклона касательной к поверхности тела (пример) необходимо проходить двумерный массив как по строкам, так и по столбцам. Причем, следуя по строкам, мы следуем по последовательности данных, находящихся в одной линии кэша. При окончании одной линии обращение будет к следующей. Только отсутствие очередной линии в кэше приведет к простою работы процессора для подгрузки новых данных.
Теперь, собственно, ответ к задаче из прошлой публикации... Следуя по столбцам в двумерных массивах большого размера программа выставляет все новый и новый адрес следующего элемента, который находится совсем не в смежной ячейке памяти. Соответственно, новое обращение к элементу массива вызывает исключение из-за отсутствия нужной линии в кэше (при больших матрицах линий кэша не хватит). При этом, в каждой новой подгруженной линии нам будет необходим только один элемент. Все это выглядит контрпродуктивно и приводит к катастрофическому падению производительности приложения.
Решение проблемы
Как можно устранить этот досадный эффект? Да очень просто! Создать транспонированную матрицу, в которой строки станут столбцами:
Теперь для движения по строкам мы используем левую матрицу, а при движении по столбцам правую. Такой подход увеличит объем занимаемой памяти, зато сократит число ситуаций с подкачкой в кэш новых линий. Как итог - приложение взлетает как ракета по сравнению со своей предыдущей версией.
Неправильно было бы рассуждать, что именно кэш обрушивает производительность. Скорее это нежелание "пилота Формулы-1 знать о существовании узлов и механизмов в недрах своей техники".
Подытожим:
как вы не абстрагируйтесь высокоуровневыми фреймворками - придет Вася, подправит пару строк и как всегда оставит вас сидеть в недоумении где была ошибка.
Поддержите статью лайком если понравилось и подпишитесь чтобы ничего не пропускать.
Также не обойдите вниманием канал на YouTube. Подписки и лайки будут приятным ответом от аудитории.
