Почему большая по объему память обычно работает медленнее чем маленькая

Важно не только количество. Рассказываем всё, что нужно знать о памяти смартфона

Когда речь заходит о покупке нового смартфона, обычный покупатель либо совсем не обращает внимания на характеристики, либо хочет получить все да побольше. Камера — только 200 МП, быстрая зарядка — обязательно на 120 Вт, память — ну, минимум 12/256 ГБ. Если с мегапикселями все уже давно ясно, то объем памяти смартфона многими людьми до сих пор считается объективной и самодостаточной характеристикой. Правда, в этом отношении тоже есть нюанс, о котором важно знать каждому покупателю.

Тип оперативной и постоянной памяти сильно влияет на скорость работы смартфона

Оперативная и постоянная память — отличия

Чтобы все, о чем далее пойдет речь, не вызвало у вас лишних вопросов, начнем с вводной информации, а именно — с определения памяти. Она бывает оперативной (ОЗУ) и постоянной (ПЗУ). В маркировке 12/256 ГБ первое число означает объем ОЗУ (оперативного запоминающего устройства), а второе — ПЗУ (постоянного запоминающего устройства).

⚡ Подпишись на Androidinsider в Дзене, где мы публикуем эксклюзивные материалы

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

Для хранения данных в оперативной памяти нужен постоянный ток

Чем больше внутренней памяти, тем больше данных вы можете хранить на смартфоне. А объем ОЗУ влияет на количество информации, которое устройство сможет обработать в момент времени. Если на телефоне ОЗУ малой емкости, система будет автоматически закрывать приложения, что существенно замедлит работу гаджета. Но далеко не только объем ОЗУ и ПЗУ влияет на отзывчивость и скорость смартфона. Ведь память бывает разной, и не факт, что на вашем устройстве установлен хороший накопитель.

Виды постоянной памяти смартфона

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

Скорость чтения показывает, какое количество информации память обрабатывает за секунду (например, когда вы запускаете приложение), а скорость записи — количество обрабатываемой информации при сохранении данных на устройстве (например, когда вы устанавливаете приложение).

Чем выше эти показатели, тем, в целом, быстрее работает смартфон. Наше сравнение памяти показывает, что eMMC 5.1 — устаревший тип ПЗУ. Он появился еще в 2015 году, но он до сих пор используется в дешевых устройствах. К примеру, именно такой накопитель установлен в телефоне Redmi 10A.

Дешевые смартфоны продолжают использовать старый тип постоянной памяти, из-за чего медленно запускают и устанавливают приложения

Но, если вы хотите получить в свое распоряжение шустрый аппарат, необходимо выбирать смартфон с UFS 2.2 и выше. При этом есть вероятность встретить в продаже модель с UFS 2.1 или UFS 3.0, но данные типы накопителей постепенно уходят в небытие, а UFS 4.0, представленный летом 2022 года, появится в массовом производстве не раньше следующего года.

❗ Поделись своим мнением или задай вопрос в нашем телеграм-чате

И последнее о том, что касается скорости памяти. Хотя весь сегодняшний материал посвящен развенчиванию мифа относительно важности размера, в случае с ПЗУ он имеет значение. Чем больше объем памяти, тем быстрее она работает при использовании одного и того же стандарта. Так, максимальная скорость последовательного чтения UFS 2.1 на 512 ГБ — 860 МБ/c, а тот же накопитель на 1 ТБ выдает уже 1 000 МБ/c.

Как узнать скорость памяти

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

Скорость памяти зависит от типа накопителя и его объема

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

Виды оперативной памяти на телефоне

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

Пропускная способность — это комплексный показатель, учитывающий частоту памяти, разрядность шины и количество каналов. Данная характеристика влияет на общую производительность. Теперь про напряжение. Чем оно выше, тем больше энергии потребляет ОЗУ. Это особенно важно при нахождении смартфона в спящем режиме, так как операционная система всегда занимает 2-3 ГБ оперативки вне зависимости от количества запущенных программ.

�� Загляни в телеграм-канал Сундук Али-Бабы, где мы собрали лучшие товары с АлиЭкспресс

LPDDR3 — устаревший тип оперативной памяти, проигрывающий конкурентам по всем показателям, но он, как и eMMC 5.1, продолжает встречаться в дешевых устройствах. К примеру, Samsung поставила такое ОЗУ в прошлогодний телефон Galaxy A02, хотя сам стандарт LPDDR3 появился еще в 2012 году.

Оперативка стандарта LPDDR5x была представлена в конце 2021 года, но ни один смартфон с таким типом ПЗУ еще не вышел

Сегодня чаще всего используется оперативная память стандарта LPDDR4x, LPDDR5 появляется только во флагманах, а релиз LPDDR5x в смартфоне стоит ожидать только в 2023 году. С точки зрения обработки информации 6 ГБ LPDDR5 — почти то же самое, что и 8 ГБ LPDDR4x. Поэтому смысл переплачивать за больший объем ОЗУ есть только при использовании актуального стандарта памяти. Кроме того, чем больше оперативки, тем быстрее разряжается смартфон, ведь ОЗУ, напомню, является энергозависимым, в отличие от ПЗУ.

Расширение оперативной памяти

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

Производители включают расширение памяти по умолчанию, но я рекомендую отказаться от этой функции

При этом скорость постоянной памяти намного ниже оперативной. Самый продвинутый из используемых на сегодняшний день стандартов внутреннего хранилища UFS 3.1 позволяет добиться скорости чтения 2 100 МБ/c, в то время как оперативка LPDDR5 выдает 51 200 МБ/c (не путайте эти цифры с пропускной способностью).

⚡ Подпишись на Androidinsider в Пульс Mail.ru, чтобы получать новости из мира Андроид первым

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

# факты | Преодоление ограничений компьютерной памяти

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

Рассмотреть все существующие в мире разновидности запоминающих устройств в рамках краткого обзора не представляется возможным. Поэтому мы остановимся только на тех типах памяти, которыми оснащено большинство персональных компьютеров в современном мире. Речь идет о кеш-памяти первого (L1) и второго (L2) уровней; системной оперативной памяти; виртуальной памяти и, разумеется, жестком диске. Зачем обычному компьютеру так много самой разнообразной памяти? Чтобы ответить на этот вопрос, потребуется немного рассказать о том, для чего служит каждый тип компьютерной памяти.

Медленная и дешевая виртуальная память на жестком диске

Когда промышленность только преодолела 1-гигагерцовый рубеж тактовой частоты процессора, она столкнулась с проблемой: память, которая способна справится с запросами могучего процессора стоит очень дорого. Но ни одна преграда на пути технического прогресса не способна надолго задержать его ход. Решение было найдено: небольшой объем быстрой и дорогой памяти сочетается в современных машинах с более емкими и менее затратными хранилищами информации.

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

На ступеньку выше в этой иерархии располагается оперативная память (ОЗУ, RAM). Ранее мы уже рассмотрели, как работает этот тип памяти. Но в предыдущем нашем повествовании некоторые подробности остались за кадром, которые имеют отношение не столько к оперативной памяти, сколько к процессору и его возможностям взаимодействия с ОЗУ. Сегодня мы прольем свет на эти детали.

Битность процессора указывает нам на то, к скольким битам информации, размещенной в оперативной памяти, он способен получить доступ одновременно. В качестве примера возьмем устаревшие 16-битные процессоры. Они были способны одновременно оперировать с двумя байтами данных (1 байт = 8 битам, таким образом 16 бит = 2 байта). Следовательно, современные 64-битные процессоры обращаются к 8 байтам информации в один момент времени.

В мегагерцах (МГц, миллионах герц) и гигагерцах (ГГц, миллиардах герц) измеряется скорость обработки данных процессором. То есть сколько циклов (тактов) обработки он способен выполнить за одну секунду. Чтобы не погружаться в невообразимо огромные цифры, в качестве примера возьмем старенький (а когда-то представлявшийся верхом совершенства и мощи) процессор Pentium III с тактовой частотой 800 мегагерц в секунду. Его 32-битная архитектура говорит о том, что он способен работать одновременно с четырьмя байтами информации. Не впечатляет? Но он мог проделать эту операцию 800 миллионов раз в секунду. Перед оперативной памятью стоит непростая задача: успевать за процессором, не отставать от него и вовремя предоставлять ему информацию. Иначе все поразительные возможности чипа будут простаивать в ожидании очередной порции байтов.

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

Системная оперативная память

Например: 32-битная 100-мегагерцовая шина теоретически способна одновременно передавать 4 байта информации (32 бита делить на 8 = 4 байта) 100 миллионов раз в секунду. 66-мегагерцовая 16-битная шина может одновременно передать всего 2 байта 66 миллионов раз в секунду. Простые математические вычисления показывают нам, что первая шина превосходит вторую по объему ежесекундно передаваемой процессору информации примерно втрое (400 миллионов байт против 132 миллионов байт).

Но в реальности оперативная память, разумеется, обычно не работает на пределе возможностей. И сейчас настала пора ввести еще один термин, который тоже накладывает свои ограничения на фактическую скорость передачи данных. Латентность оперативной памяти указывает на количество циклов, необходимых для чтения бита информации. К примеру, оперативная память с тактовой частотой 100 МГц, казалось бы, способна передавать бит за одну стомиллионную долю секунды. На самом же деле, пять стомиллионных долей секунды уйдет на запуск процесса чтения первого бита. Чтобы сократить влияние фактора латентности памяти, процессор использует специальную технологию, именуемую пакетно-монопольным (групповым или просто монопольным) режимом (burst mode).

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

К примеру, строка «5-1-1-1» способна поведать нам, что для чтения первого бита необходимы пять циклов и один цикл для чтения каждого последующего бита информации. Чем меньше это число, тем выше производительность памяти.

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

У читателей может возникнуть вопрос: а почему бы сразу не приобрести самую быструю память с самой высокой из возможных в современном мире пропускной способностью? Но тут вступает в силу ограничение, накладываемое системной шиной материнской платы компьютера. Вы, конечно, можете поставить 100-мегагерцовую память в материнскую плату с 66-мегагерцовой системной шиной. Но ее предельная скорость все равно будет составлять 66 МГц в секунду. И вы не получите никакого преимущества. Так и 32-битная память не соответствует 16-битной шине.

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

Кеш-память и регистр процессора

Вторичный кеш, или кеш-память второго уровня (L2), может быть технически реализована в виде расположенной рядом с процессором и напрямую с ним связанной карты. Специальная микросхема на материнской плате — L2-контроллер (контроллер кеш-памяти второго уровня) — регулирует использование этой памяти центральным процессором компьютера. В зависимости от модели процессора, размер кеш-памяти второго уровня может составлять от 256 килобайт до 2 мегабайт. Но технологии развиваются очень быстро, поэтому из данного «правила» возможны и случаются исключения. У процессора Jaguar как раз 2 мегабайта кеша L2. О причинах, по которым именно этот чип лег в основу игровой приставки PlayStation 4 еще в начале апреля 2013 года поведал ее конструктор.

Современный компьютер устроен таким образом, чтобы в 95 % случаев процессор получает данные из кеш-памяти, не нуждаясь в обращении к более медленным хранилищам информации. Некоторые дешевые системы обходятся вовсе без L2-кеша. Зато во многих высокопроизводительных процессорах кеш-память второго уровня встроена непосредственно в чип. Размер кеша второго уровня и его интегрированность непосредственно в центральный процессор являются важнейшими факторами, оказывающими влияние на производительность процессора.

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

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

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

На самой вершине иерархической пирамиды компьютерной памяти находится регистр процессора. Он встроен непосредственно в чип и содержит специальные — необходимые процессору — данные: арифметические и логические выражения. Являясь составной частью процессора, его регистр управляется непосредственно компилятором, отправляющим процессору информацию для обработки.

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

Оптимизация кода: память

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Локальность

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

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

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

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

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

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

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

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

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

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

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

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

Блокинг

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

Почему большая по объему память обычно работает медленнее чем маленькая

Уроки 41 — 45
Процессор. Память. Устройства ввода и вывода
§34. Процессор. §35. Память. §36. Устройства ввода. §37. Устройства вывода

Иерархия памяти. Кэширование. Как следует из обсуждения в § 32, невозможно создать память, которая имела бы одновременно большой объём и высокое быстродействие. Поэтому используют многоуровневую (иерархическую) систему из нескольких типов памяти. Как правило, чем больший объём имеет память, тем медленнее она работает.

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

Виртуальная память. Пользователям хочется, чтобы программное обеспечение было интеллектуальным и дружественным и чтобы в нём были предусмотрены все самые мелкие детали, которые им могут потребоваться. Программистам хочется написать программу с наименьшими затратами сил и времени, поэтому они широко используют среды быстрой разработки программ (англ. RAD — Rapid. Application Development). В результате программы всё больше увеличиваются в размере. Кроме того, объём обрабатываемых данных постоянно растёт. Поэтому компьютерам требуется все больше и больше памяти, особенно в многозадачном режиме, когда одновременно запускаются сразу несколько программ.

Следующая страница Основные характеристики памяти

Cкачать материалы урока