4.4 Оперативная память и кэш *¶
В первых двух разделах этой главы мы разобрали массивы и связные списки - две фундаментальные и важные структуры данных, которые соответственно представляют две физические структуры хранения: "непрерывное хранение" и "разрозненное хранение".
На практике физическая структура во многом определяет, насколько эффективно программа использует память и кэш, а это, в свою очередь, влияет на общую производительность алгоритмической программы.
4.4.1 Устройства хранения данных в компьютере¶
В компьютере есть три типа устройств хранения данных: жесткий диск (hard disk) , оперативная память (random-access memory, RAM) и кэш-память (cache memory) . В таблице 4-2 показаны их различные роли и характеристики производительности в компьютерной системе.
Таблица 4-2 Устройства хранения данных в компьютере
| Жесткий диск | Оперативная память | Кэш | |
|---|---|---|---|
| Назначение | Долговременное хранение данных, включая ОС, программы, файлы и т.д. | Временное хранение выполняемых программ и обрабатываемых данных | Хранение часто используемых данных и инструкций, уменьшающее число обращений CPU к памяти |
| Энергозависимость | Данные не теряются после отключения питания | Данные теряются после отключения питания | Данные теряются после отключения питания |
| Емкость | Большая, уровень TB | Меньшая, уровень GB | Очень малая, уровень MB |
| Скорость | Низкая, от сотен до тысяч MB/s | Высокая, десятки GB/s | Очень высокая, десятки и сотни GB/s |
| Цена (юани) | Дешевый, от долей юаня до нескольких юаней за GB | Дорогая, десятки и сотни юаней за GB | Очень дорогой, входит в стоимость упаковки CPU |
Компьютерную систему хранения можно представить в виде пирамиды, показанной на рисунке 4-9. Чем ближе устройство хранения к вершине пирамиды, тем оно быстрее, тем меньше его емкость и тем выше его стоимость. Такая многоуровневая конструкция возникла не случайно, а стала результатом тщательных инженерных компромиссов.
- Жесткий диск трудно заменить оперативной памятью. Во-первых, данные в оперативной памяти исчезают после отключения питания, поэтому она не подходит для долговременного хранения. Во-вторых, память стоит в десятки раз дороже жесткого диска, что мешает ее широкому применению в потребительском сегменте.
- Кэш не может одновременно быть и очень большим, и очень быстрым. По мере роста емкости кэшей L1, L2 и L3 их физический размер увеличивается, расстояние до ядра CPU становится больше, время передачи данных растет, а задержка доступа к элементам увеличивается. При текущем уровне технологий многоуровневая структура кэша является лучшим балансом между емкостью, скоростью и стоимостью.
Рисунок 4-9 Система хранения данных компьютера
Tip
Иерархия памяти компьютера отражает тонкий баланс между скоростью, емкостью и стоимостью. На самом деле подобные компромиссы встречаются почти во всех отраслях инженерии: приходится искать оптимальный баланс между преимуществами и ограничениями.
В итоге жесткий диск используется для долговременного хранения больших объемов данных, оперативная память - для временного хранения данных, с которыми программа работает прямо сейчас, а кэш - для хранения часто используемых данных и инструкций, чтобы ускорять выполнение программ. Все три уровня работают совместно и обеспечивают эффективную работу компьютерной системы.
Как показано на рисунке 4-10, во время выполнения программы данные читаются с жесткого диска в оперативную память, а затем используются CPU в вычислениях. Кэш можно рассматривать как часть CPU: он интеллектуально подгружает данные из оперативной памяти, обеспечивая CPU высокоскоростной доступ и тем самым значительно ускоряя выполнение программы и уменьшая зависимость от более медленной RAM.
Рисунок 4-10 Поток данных между жестким диском, RAM и кэшем
4.4.2 Эффективность использования памяти структурами данных¶
С точки зрения использования пространства памяти массивы и связные списки имеют свои преимущества и ограничения.
С одной стороны, память ограничена, и один и тот же участок памяти не может совместно использоваться несколькими программами, поэтому нам хочется, чтобы структуры данных использовали пространство как можно эффективнее. Элементы массива расположены плотно и не требуют дополнительного места для хранения ссылок (указателей) между узлами списка, поэтому массивы эффективнее по памяти. Однако массиву нужно сразу выделить достаточно большой непрерывный участок памяти, что может приводить к потерям пространства, а его расширение требует дополнительных затрат времени и памяти. Напротив, связные списки выполняют динамическое выделение и освобождение памяти "по узлам", что дает большую гибкость.
С другой стороны, во время выполнения программы при многократном выделении и освобождении памяти фрагментация свободной памяти становится все более серьезной, что снижает эффективность ее использования. Массивы из-за непрерывного хранения относительно менее подвержены фрагментации. Напротив, элементы связного списка распределены по памяти, и частые операции вставки и удаления легче приводят к фрагментации.
4.4.3 Эффективность использования кэша структурами данных¶
Хотя по объему кэш намного меньше оперативной памяти, он значительно быстрее и играет критически важную роль в скорости выполнения программ. Поскольку объем кэша ограничен и в нем можно хранить только небольшую долю часто используемых данных, когда CPU пытается обратиться к данным, которых в кэше нет, происходит промах кэша (cache miss) , и CPU вынужден загружать нужные данные из более медленной памяти.
Очевидно, что чем меньше "промахов кэша", тем выше эффективность чтения и записи данных CPU, а значит, тем лучше производительность программы. Долю обращений, при которых CPU успешно получает данные из кэша, называют коэффициентом попадания в кэш (cache hit rate) ; этот показатель обычно используют для оценки эффективности кэша.
Чтобы добиться как можно большей эффективности, кэш использует следующие механизмы загрузки данных.
- Строки кэша: кэш хранит и загружает данные не по одному байту, а строками кэша. По сравнению с передачей по байтам это гораздо эффективнее.
- Механизм предвыборки: процессор старается предсказать шаблон доступа к данным (например последовательный доступ, доступ с фиксированным шагом и т.д.) и на основе этого шаблона заранее загружает данные в кэш, повышая вероятность попадания.
- Пространственная локальность: если к некоторым данным уже обратились, то велика вероятность, что в ближайшее время понадобятся и соседние данные. Поэтому, загружая некоторые данные, кэш часто подгружает и окружающие их данные.
- Временная локальность: если к данным уже обратились, то высока вероятность, что к ним снова обратятся в ближайшем будущем. Кэш использует это свойство, сохраняя недавно использованные данные.
На практике массивы и связные списки по-разному используют кэш, и это проявляется в нескольких аспектах.
- Занимаемое пространство: элементы связного списка занимают больше места, чем элементы массива, поэтому в кэше помещается меньше полезных данных.
- Строки кэша: данные списка разбросаны по памяти, а кэш загружает данные "строками", поэтому доля бесполезно загружаемых данных оказывается выше.
- Механизм предвыборки: шаблон доступа к данным у массивов более "предсказуем", чем у списков, то есть системе легче угадать, какие данные понадобятся следующими.
- Пространственная локальность: массив хранится в компактной области памяти, поэтому данные рядом с уже загруженными с большей вероятностью скоро будут использованы.
В целом массивы имеют более высокий коэффициент попадания в кэш, поэтому по эффективности операций они обычно превосходят связные списки. Именно поэтому при решении алгоритмических задач структуры данных на основе массивов часто оказываются предпочтительнее.
Важно понимать, что высокая эффективность кэша не означает, что массивы во всех случаях лучше связных списков. В реальных приложениях выбор структуры данных должен определяться конкретными требованиями. Например, и массивы, и списки могут использоваться для реализации "стека" (подробнее об этом будет рассказано в следующей главе), но подходят они для разных сценариев.
- При решении алгоритмических задач мы обычно предпочитаем стек на основе массива, потому что он дает более высокую эффективность операций и поддерживает произвольный доступ, а цена за это - необходимость заранее выделить некоторый объем памяти под массив.
- Если объем данных очень велик, структура сильно динамична, а ожидаемый размер стека трудно оценить заранее, то более уместен стек на основе связного списка. Список позволяет распределить большой объем данных по разным участкам памяти и избегает накладных расходов, связанных с расширением массива.