Что находится в оперативной памяти когда исполняется программный код

Оперативная память. Строение и устройство (RAM, ОЗУ)

Оперативная память это важная часть любой компьютерной системы и сейчас я объясню, почему это так.

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

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

Физически, оперативная память представляет собой набор микросхем припаянных к плате.

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

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

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

Таких конденсаторов в чипе, очень много но считать заряд с одной конкретной ячейки нельзя, считывается вся страница целиком.

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

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

Задержки между этими операциями называют «Латенстностью» или в народе «Таймингами», чем они меньше тем более быстрая будет вся система в целом

Помимо самих чипов памяти, на модуль распаиваются SMD-компоненты резисторы и конденсаторы обеспечивающие развязку сигнальных цепей и питание чипов, а также Микросхема SPD – это специальная микросхема, в которой хранятся данные о параметрах всего модуля (ёмкость, рабочее напряжение, тайминги, число банков и так далее). Это нужно чтобы во время запуска системы, BIOS на материнской плате выставил оптимальные настройки согласно информации, отображенной в микросхеме.

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

Например в старых модулях Simm контакты с двух сторон были замкнуты и они могли передать только 32 бита информации за такт, в то время как dimm могут передавать 64 бита.

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

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

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

Ещё немного расскажу о типах памяти, так как в современных компьютерах используется синхронная динамическая память с произвольным доступом и удвоенной скоростью передачи данных DDR SDRAM 4-го поколения и скоро будет распространено пятое.

Память типа DDR пришла на смену памяти типа SDR. SDR SDRAM работает синхронно с контроллером. В ней внутренняя и внешняя шина данных работает на одной и той же частоте. При подаче сигнала на микросхему происходит синхронное считывание информации и передача её в выходной буфер. Передача каждого бита из буфера происходит с каждым тактом работы ядра памяти. В SDR памяти синхронизация обмена данными происходит по фронту тактового импульса.

При подаче сигнала на микросхему происходит синхронное считывание информации и передача её в выходной буфер. Передача каждого бита из буфера происходит с каждым тактом работы ядра памяти. В SDR памяти синхронизация обмена данными происходит по фронту тактового импульса.

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

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

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

Ниже оставлю видео версию статьи, может кому будет интересно посмотреть на 3D анимацию планок памяти. На этом у меня всё, всем пока.

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

Можно ли запустить код в Python, который будет сформирован в оперативной памяти? Есть зашифрованный мной python код и я не хочу чтобы любой мог увидеть реализацию, есть второй файл файл, который при вводе пароля должен расшифровать первый файл в оперативную память и запустить его. В итоге промежуточный расшифрованный файл не будет храниться на диске и при завершении работы второго файла просто «исчезнет». Можно ли такое реализовать? Другие языки не предлагать, библиотеки можно.

Отслеживать
задан 16 мар 2021 в 20:17
39 4 4 бронзовых знака

Да, реализовать такое можно. И в подобных вопросах неплохо бы указывать ОС, потому что в Юниксах такое куда проще реализуется.

16 мар 2021 в 20:22
ОС Windows 10. Я думал решение будет универсальным для все ОС
16 мар 2021 в 20:27
Расшифрованный файл можно будет без проблем вытащить из оперативной памяти
16 мар 2021 в 22:29

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

17 мар 2021 в 8:08

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

17 мар 2021 в 9:25

3 ответа 3

Сортировка: Сброс на вариант по умолчанию

Самый простой способ — через eval :

eval(decrypt(secret, password).decode()) 

Есть ещё загрузчик кода, может кто напомнит как его там. Потом можно записать свой загрузчик модулей, который примет шифрованный код.

Но самое простое прогнать через cython и шифрование не нужно будет.

Отслеживать
ответ дан 16 мар 2021 в 22:22
33.9k 3 3 золотых знака 26 26 серебряных знаков 60 60 бронзовых знаков

Eval очень ограничен, если не ошибаюсь. В нем нет возможности запустить циклы, про что-то сложнее я уже молчу

17 мар 2021 в 7:35
Ваш ответ натолкнул на правильное решение, спасибо. Это был exec
17 мар 2021 в 8:58
@RubiniuM неспалось, писал с телефона. Вот вертелось на языке — не вспомнил как его.
17 мар 2021 в 13:22

К чему был вопрос насчёт ОС. На Юниксах (MacOSX, Linux) вместо eval и exec можно легко записать массив данных в оперативку по пути /tmp/*, а потом использовать importlib для загрузки и выполнения кода из множества взаимосвязанных нормальных Питонячих файлов, после чего их удалить. В принципе, на Винде можно сделать аналогично просто в какой-то скрытой локации на диске, от безопасности не сильно убудет: как высказывались другие участники, все упомянутые способы – такая себе защита от реальных злоумышленников и просто айтишников, но в целом варианты рабочие.

Отслеживать
ответ дан 17 мар 2021 в 11:58
9,818 5 5 золотых знаков 28 28 серебряных знаков 58 58 бронзовых знаков

Такого ответа я как раз и ждал. Про безопасность не думайте. Я привёл лишь пример кода, который не связан с реальным проектом. Пусть будет хоть самодополняющийся код в оперативке, хоть scratch на python. Мое главное условие не сохранять файл на диск перед выполнением. Спасибо

17 мар 2021 в 13:17

Все решилось банально: Дешифруем файл в переменную и запускаем через exec. Всё.

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

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

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

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

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

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

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

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

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

int matrixsum1(int size, int M[][size]) < 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[][size]) < 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, сохраняют большие объёмы данных на ленточных носителях, которые хранятся где-то на складах, и когда понадобятся, должны быть присоеденены вручную или роботом.

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

Тип кэша	Время доступа (тактов)	Размер кэша
Регистры	0	десятки штук
L1 кэш	4	32 KB
L2 кэш	10	256 KB
L3 кэш	50	8 MB
Оперативная память	200	8 GB
Буфер диска	100’000	64 MB
Локальный диск	10’000’000	1000 GB
Удалённые сервера	1’000’000’000	∞

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

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

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

Локальность

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

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

int sum(int size, int A[])

В этой программе обращение к переменным 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% из них напишут её примерно так:

void matrixmult1(int size, double A[][size], double B[][size], double C[][size]) < 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[][size], double B[][size], double C[][size]) < 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[][size])

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

void convert2(int size, int G[][size]) < 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 для блока принимает значения [ii, ii + block_size) int i_end = ii + block_size; int j_start = jj; // индекс j для блока принимает значения [jj, jj + block_size) int j_end = jj + block_size; // обходим блок for (int i = i_start; i < i_end; i++) for (int j = j_start; j < j_end; j++) G[i][j] = G[i][j] | G[j][i]; >> > 

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

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

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

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

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

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

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

Заключение

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

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

В частности, рекомендуются следующие техники:

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

• оптимизация программ
• производительность
• язык c
• процессор
• компилятор оптимизация

Разбираемся с управлением памятью в современных языках программирования

Привет, Хабр! Представляю вашему вниманию перевод статьи «Demystifying memory management in modern programming languages» за авторством Deepu K Sasidharan.

В данной серии статей мне бы хотелось развеять завесу мистики над управлением памятью в программном обеспечении (далее по тексту — ПО) и подробно рассмотреть возможности, предоставляемые современными языками программирования. Надеюсь, что мои статьи помогут читателю заглянуть под капот этих языков и узнать для себя нечто новое.

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

Часть 1: Введение в управление памятью

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

Для чего используется оперативная память?

Когда программа выполняется в операционный системе компьютера, она нуждается в доступе к оперативной памяти (RAM) для того, чтобы:

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

Стек

Стек используется для статичного выделения памяти. Он организован по принципу «последним пришёл — первым вышел» (LIFO). Можно представить стек как стопку книг — разрешено взаимодействовать только с самой верхней книгой: прочитать её или положить на неё новую.

• благодаря упомянутому принципу, стек позволяет очень быстро выполнять операции с данными — все манипуляции производятся с «верхней книгой в стопке». Книга добавляется в самый верх, если нужно сохранить данные, либо берётся сверху, если данные требуется прочитать;
• существует ограничение в том, что данные, которые предполагается хранить в стеке, обязаны быть конечными и статичными — их размер должен быть известен ещё на этапе компиляции;
• в стековой памяти хранится стек вызовов — информация о ходе выполнения цепочек вызовов функций в виде стековых кадров. Каждый стековый кадр это набор блоков данных, в которых хранится информация, необходимая для работы функции на определённом шаге — её локальные переменные и аргументы, с которыми её вызывали. Например, каждый раз, когда функция объявляет новую переменную, она добавляет её в верхний блок стека. Затем, когда функция завершает свою работу, очищаются все блоки памяти в стеке, которые функция использовала — иными словами, очищаются все блоки ее стекового кадра;
• каждый поток многопоточного приложения имеет доступ к своему собственному стеку;
• управление стековой памятью простое и прямолинейное; оно выполняется операционной системой;
• в стеке обычно хранятся данные вроде локальных переменных и указателей;
• при работе со стеком есть вероятность получать ошибки переполнения стека (stack overflow), так как максимальный его размер строго ограничен. Например, ошибка при составлении граничного условия в рекурсивной функции совершенно точно приведёт к переполнению стека;
• в большинстве языков существует ограничение на размер значений, которые можно сохранить в стек;

Использование стека в JavaScript. Объекты хранятся в куче и доступны по ссылкам, которые хранятся в стеке. Тут можно посмотреть в видеоформате

Куча

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

• операции на куче производятся несколько медленнее, чем на стеке, так как требуют дополнительного этапа для поиска данных;
• в куче хранятся данные динамических размеров, например, список, в который можно добавлять произвольное количество элементов;
• куча общая для всех потоков приложения;
• вследствие динамической природы, куча нетривиальна в управлении и с ней возникает большинство всех проблем и ошибок, связанных с памятью. Способы решения этих проблем предоставляются языками программирования;
• типичные структуры данных, которые хранятся в куче — это глобальные переменные (они должны быть доступны для разных потоков приложения, а куча как раз общая для всех потоков), ссылочные типы, такие как строки или ассоциативные массивы, а так же другие сложные структуры данных;
• при работе с кучей можно получить ошибки выхода за пределы памяти (out of memory), если приложение пытается использовать больше памяти, чем ему доступно;
• размер значений, которые могут храниться в куче, ограничен лишь общим объёмом памяти, который был выделен операционной системой для программы.

Почему эффективное управление памятью важно?

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

Различные подходы

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

Ручное управление памятью

Язык не предоставляет механизмов для автоматического управления памятью. Выделение и освобождение памяти для создаваемых объектов остаётся полностью на совести разработчика. Пример такого языка — C. Он предоставляет ряд методов (malloc, realloc, calloc и free) для управления памятью — разработчик должен использовать их для выделения и освобождения памяти в своей программе. Этот подход требует большой аккуратности и внимательности. Так же он является в особенности сложным для новичков.

Сборщик мусора

Сборка мусора — это процесс автоматического управления памятью в куче, который заключается в поиске неиспользующихся участков памяти, которые ранее были заняты под нужды программы. Это один из наиболее популярных вариантов механизма для управления памятью в современных языках программирования. Подпрограмма сборки мусора обычно запускается в заранее определённые интервалы времени и бывает, что её запуск совпадает с ресурсозатратными процессами, в результате чего происходит задержка в работе приложения. JVM (Java/Scala/Groovy/Kotlin), JavaScript, Python, C#, Golang, OCaml и Ruby — вот примеры популярных языков, в которых используется сборщик мусора.

Сборщик мусора на основе алгоритма пометок (Mark & Sweep): Это алгоритм, работа которого происходит в две фазы: первым делом он помечает объекты в памяти, на которые имеются ссылки, а затем освобождает память от объектов, которые пометки не получили. Этот подход используется, например, в JVM, C#, Ruby, JavaScript и Golang. В JVM существует на выбор несколько разных алгоритмов сборки мусора, а JavaScript-движки, такие как V8, используют алгоритм пометок в дополнение к подсчёту ссылок. Такой сборщик мусора можно подключить в C и C++ в виде внешней библиотеки.

Получение ресурса есть инициализация (RAII)

RAII — это программная идиома в ООП, смысл которой заключается в том, что выделяемая для объекта область памяти строго привязывается к его времени существования. Память выделяется в конструкторе и освобождается в деструкторе. Данный подход был впервые реализован в C++, а так же используется в Ada и Rust.

Автоматический подсчёт ссылок (ARC)

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

Автоматический подсчёт ссылок всё так же не позволяет обрабатывать циклические ссылки и требует от разработчика использования специальных ключевых слов для дополнительной обработки таких ситуаций. ARC является одной из особенностей транслятора Clang, поэтому присутствует в языках Objective-C и Swift. Так же автоматический подсчет ссылок доступен для использования в Rust и новых стандартах C++ при помощи умных указателей.

Владение

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

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

Читайте так же другие части серии:

• > Часть 1: Введение в управление памятью
• Part 2: Memory management in JVM(Java, Kotlin, Scala, Groovy)
• Part 3: Memory management in V8(JavaScript/WebAssembly)
• Part 4: Memory management in Go (in progress)
• Part 5: Memory management in Rust (in progress)
• Part 6: Memory management in Python (in progress)
• Part 7: Memory management in C++ (in progress)
• Part 8: Memory management in C# (in progress)

Ссылки

• http://homepages.inf.ed.ac.uk
• https://javarevisited.blogspot.com
• http://net-informations.com
• https://gribblelab.org
• https://medium.com/computed-comparisons
• https://en.wikipedia.org/wiki/Garbage*collection*(computer_science)
• https://en.wikipedia.org/wiki/Automatic_Reference_Counting
• https://blog.sessionstack.com

Вы можете подписаться на автора статьи в Twitter и на LinkedIn.

За вычитку перевода отдельное спасибо Александру Максимовскому и Катерине Шибаковой