Предыдущая часть:
Где там наша куча песка?
Как мы понимаем, что это именно куча? Все её песчинки находятся в ограниченном пространстве и соприкасаются между собой, образуя как бы сплошной объект.
Тот же принцип можно перенести на память компьтера. Если одна ячейка памяти это песчинка, то куча получится, если соединить много таких ячеек вместе, чтобы они соприкасались друг с другом.
Правда, есть одно отличие.
В настоящей куче песчинки трёхмерны и могут соприкасаться друг с другом бесконечным количеством способов.
Компьютерная же память одномерна, поэтому ячейки в ней могут соприкасаться только те, у которых адрес отличается на 1:
Тем не менее, на логическом уровне различий нет. Можно выделить любой непрерывный участок памяти, и считать его кучей, а точнее, массивом.
Как осуществить доступ к элементам массива? Для этого опять посмотрим на кучу песка.
Если мы пронумеруем там каждую песчинку, тогда нам достаточно составить выражение вроде
куча[100]
Это значит – обратиться к песчинке с номером 100. Получается удобно, так как песчинки могут быть расположены где угодно, но если к каждой привязан номер, значит по номеру мы можем обратиться именно к ней.
И то же самое происходит в массиве:
массив[100]
Причём ячейки нумеровать не надо – они уже и так пронумерованы, так как имеют адреса.
Хорошо, а что если обратиться к куче по-другому? У каждой песчинки есть координаты в трёхмерном пространстве: (x, y, z). Если написать допустим так:
куча[x, y, z]
То мы опять же получим доступ к песчинке по координататам (x, y, z) – если она там есть.
Обратившись к массиву, мы заметим, что ничего не изменилось – номер ячейки одновременно является её одномерной координатой, поэтому доступ по номеру и по координате это одно и то же:
массив[x]
Но что делать с остальными координатами, если они трёхмерные, а массив одномерен?
Здесь мы сталкиваемся с фундаментальным ограничением модели памяти, а именно, память компьютера это одна непрерывная цепочка ячеек, и поменять этот факт никак нельзя (пока не придумают что-нибудь новое, модное) .
Но раз мы не можем поменять модель памяти, то можем поменять модель координат. Начнём с двумерных. Нам всего лишь надо, чтобы две координаты (x, y) транслировались в один номер внутри массива.
Для каждой координаты y есть множество координат x, которое одномерно. Мы можем взять много одномерных множеств х и просто расположить их в свободных участках нашего массива друг за другом.
Чтобы не связываться с бесконечностью, координаты (x, y) должны быть чем-то ограничены, например числом 100. Впрочем, то же касается и физической кучи: она занимает ограниченный объём пространства, вне которого просто не существует.
Значит, двумерный массив в одномерной форме можно представить так: 100 ячеек x с координатой y=0, затем 100 ячеек x с координатой y=1, и так далее до координаты y=100. Всего получится 10 000 ячеек.
Сам массив можно графически представить так:
Он стал как бы двумерным, но нужно помнить, что ничего не изменилось. Просто координаты (x, y) теперь транслируются в одномерную координату-адрес через формулу y * 100 + x.
Физическая работа
Перейдём к делу.
Вы начинаете грузить песок в тачку, набирая его лопатой. Как это сделать быстрее всего, с обычной бытовой точки зрения? Лучше набирать песок прямо там, где вы стоите, или каждую следующую лопату набирать с другой стороны кучи?
Конечно, быстрее и проще набирать песок прямо там, где стоим. Это мы понимаем сразу.
То есть, набирая песок в лопату, мы помещаем туда такой набор песчинок, который имеет определённую локальную связность. Если же мы по какой-то причине захотим добавить туда другие песчинки, нам придётся совершить лишнюю работу, и работа эта может быть очень даже большой.
Такова природа, обойти которую со своей лопатой мы не можем.
Теперь к массиву.
Перебор массива и выполнение действий с его элементами это практически самая распространённая операция в программировании.
Понимаем ли мы, как правильно это делать? Да, если мы понимаем, как правильно грузить песок.
Самые локально связанные элементы массива это ячейки, которые расположены подряд. Поэтому быстрее всего обрабатывать ячейки, идущие подряд.
Например, в нашем двумерном варианте, если мы движемся по координате x, увеличивая её на 1, мы каждый раз считываем следующую ячейку массива, расположенную вплотную к предыдущей.
Если же мы движемся по координате y, также увеличивая её на 1, то на этот раз, в силу нашей формулы преобразования координат, адрес ячейки увеличивается не на 1, а на 100. Каждая следующая ячейка по координате y отстоит от предыдущей на 100 ячеек.
Очевидно, ячейки 0 и 100 в компьтерной памяти если и связаны, то гораздо слабее, чем 0 и 1.
Но какая компьютеру разница, прибавлять 1 или 100 к адресу ячейки? Как это вообще может повлиять на скорость, если 1 и 100 это два совершенно равноправных числа?
Кеш
Мы привыкли к тому, что оперативная память компьютера работает быстро, но есть память, которая работает ещё быстрей. Это кеш-память (не путать с кешированием данных в памяти, это именно отдельная физическая память).
Наши данные хранятся в обычной памяти, и когда процессор видит, что мы к ним обращаемся, он перемещает их в кеш-память, чтобы операции с ними происходили быстрее. Но процессору нет смысла переносить в кеш одну ячейку. Вместо этого он переносит целую строку, или страницу, так как догадывается, что нам понадобятся ещё данные.
Можно сказать, что это именно процессор орудует лопатой, набирая в неё памяти, сколько поместится, и перемещая её в кеш. А набирать он может, естественно, только связанные, то есть идущие подряд, ячейки.
В нашем случае, к примеру, при обращении к ячейке 0 процессор перенесёт в кеш 100 (условно) последовательных ячеек. Поэтому когда мы будем обращаться к ячейке 1, она уже будет ждать нас в кеше, и 2, и 3, и т.д.
Но если мы обращаемся к ячейке 101, это вдвойне плохо: во-первых, в кеше её нет, а во-вторых, процессор зря переносил столько ячеек до этого. Мы тем самым заставляем процессор бегать с лопатой вокруг кучи, набирая данные с разных её сторон и совершая дополнительную работу.
Уместить в кеш
Размер кеша у процессора, в зависимости от модели, может быть разный, но всё-таки он измеряется в единицах от килобайт до мегабайт. Поэтому в нашем случае в кеш могло бы поместиться сразу много строк массива. Тогда, даже прибавляя к адресу 100, мы всё равно попадали бы в кеш.
Собственно, множество методов оптимизации связано с тем, чтобы уместить те данные, которые мы обрабатываем прямо сейчас, в кеш.
Например, изображение может состоять из пикселов, где каждый пиксел это три байта: R, G, B.
Изображение может иметь размер 1024 * 1024 пиксела, и структурно его можно представить так:
1024 * 1024 R
1024 * 1024 G
1024 * 1024 B
или так:
1024 * 1024 (R, G, B)
Какая из структур лучше? В общем случае вторая, так как мы обычно обрабатываем изображение попиксельно, и нам нужны байты RGB, идущие подряд.
Но вообще это зависит от решаемой задачи и тех операций, которые мы хотим совершить над данными. Например, если бы нам понадобилось обрабатывать только один из цветовых каналов изображения, первая структура пришлась бы как нельзя кстати.
Проверяйте!
Читайте дальше:
