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

Однажды мне пришлось подправить плохо написанный код для моей работы. Когда я говорю, что написано плохо, я не имею в виду что-то незначительное, например, что в нем не использовался мой предпочтительный стиль программирования или даже что он был плохо организован. Я имею в виду, что некоторые важные части кода просто делали неправильные вещи, другие части были избыточными до такой степени, что скрывали ошибки и т. Д. Я однажды заменил около семидесяти пяти строк плотного кода одной строкой кода, потому что я понял, как работает ASCII, и потому, что я смог отделить некоторые вложенные условные выражения (в частности, некоторые плохо используемые операторы switch). Прежде чем я исправил код, программа заняла несколько часов. После того, как я исправил код, программа заняла около десяти минут.

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

Во-первых, у меня была большая матрица чисел (около 10 000 строк на 100 000 столбцов, я думаю), но я всегда использовал только два столбца матрицы за раз, поэтому я избавился от большой матрицы и заменил ее просто последние два столбца. Во-вторых, у меня была еще одна большая матрица чисел того же размера, что и первая матрица, и я заметил, что числа никогда не заходили слишком далеко от 300. Фактически, я мог гарантировать, что числа будут около 10 000 в абсолютном выражении. максимум. В то время я использовал четыре байта для представления каждого из чисел, но вам нужно было всего два байта для представления чисел меньше 65536, поэтому я переключил числа с четырех байтов на два байта.

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

Закон Амдала в моей программе

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

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

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

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

Каким образом использование четвертой части памяти заставит программу работать примерно в четыре раза быстрее?

Аллегория профессора

Я не буду говорить о том, как ваш компьютер управляет памятью, но я думаю, что аллегория, которую я собираюсь рассказать, должна подтолкнуть вас к объяснению.

Прибытие профессора

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

Первый день занятий

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

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

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

Второй класс

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

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

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

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

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

Третий класс

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

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

После ее первого дня

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

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

Объясняя аллегорию

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

  • Профессор - это процессор.
  • Ее руки - это регистры.
  • Ее классы - это ее программы.
  • Ее метки и система маркировки - это адреса памяти.
  • Ее офис - оперативная память.
  • Ее рюкзак - это кэш второго уровня.
  • Магниты и корзина для маркеров - это кэш L1.
  • Ее дом - это дополнительное хранилище.

Процессор

Центральный процессор (сокращенно ЦП) - это мозг компьютера. Он решает, что делать дальше, как организовать вещи и т. Д. Я мог бы много сказать об этом, но относитесь к нему так же, как к профессору.

Регистры

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

Программ

Фактическое содержание классов определяет, что вам нужно привнести в каждый класс, так же как программа определяет, что нужно делать процессору.

Адреса памяти

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

баран

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

Самые ранние современные компьютеры имели только регистры и оперативную память для памяти. Фактически, многие компьютеры, такие как калькуляторы (по крайней мере, до TI-89 Titanium) и ранние видеоигры, просто имели оперативную память, а это означало, что вы потеряете свои данные, если выключите их. В старых играх, таких как Metroid, раньше были пароли, которые указывали на ваш прогресс, в частности, потому что они не могли сохранить данные (The Legend of Zelda была ранним исключением, потому что в ней были файлы сохранения .).

Произвольный доступ?

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

Термин произвольный доступ X просто означает, что компьютер не знает, к какому элементу X будет осуществлен доступ следующим. Оперативная память означает, что компьютер не знает, по какому адресу памяти вы собираетесь читать или писать по следующему адресу.

Тайники

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

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

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

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

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

Доступ к памяти из кэша L1 происходит быстрее, чем доступ к памяти из кэша L2, но вы не можете сохранить столько же в кэше L1. Точно так же доступ к памяти из кэша L2 происходит быстрее, чем доступ к памяти из ОЗУ, но вы не можете сохранить столько же в кэше L2. На современных компьютерах часто используется кэш L3 между кешем L2 и ОЗУ, что соответствует той же схеме наличия большего объема памяти, чем L2 Cache, но с более медленным временем доступа.

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

Вторичное хранилище

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

Зачем нужна иерархия памяти?

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

Как использовать кеш

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

Следующие два принципа известны как Принципы локальности.

Временная местность

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

Таким же образом довольно просто использовать кеш в своих интересах: как только вы получите доступ к некоторым данным, сделайте с ними все возможное, прежде чем получать новые данные.

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

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

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

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

for image in images:
    find_text(image)

for image in images:
    find_faces(image)

в конечном итоге мы загружаем каждое изображение один раз для каждого цикла for, то есть мы загружаем изображение в кеш 200 раз. С другой стороны, если бы мы написали этот код:

for image in images:
    find_text(image)
    find_faces(image)

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

Пространственная местность

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

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

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

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

В качестве примера из реальной жизни предположим, что вы программируете 2D-видеоигру и хотите выяснить, не сталкиваются ли два объекта. Например, если персонаж сталкивается со стеной, он, она или она должны перестать двигаться. Если персонаж сталкивается с вражеским снарядом, персонаж должен получить урон. Чтобы определить, сталкиваются ли два объекта, все, что вам нужно знать, - это где область столкновения или хитбокс объектов по отношению друг к другу.

Хотя вы можете хранить хитбокс внутри объекта, который он представляет (например, игрока или снаряда) вместе с другими данными, такими как здоровье, выносливость, инвентарь и т. Д., Хитбокс имеет отношение только к обнаружению столкновений. Вместо этого вы можете хранить все хитбоксы вместе. Поскольку 2D-хитбокс содержит только четыре числа для левой, правой, верхней и нижней сторон поля, и каждое число может быть сохранено в четырехбайтовом поплавке, вы можете сохранить шестнадцать хитбоксов в одной 64-байтовой строке кэша. Если бы вы сохранили хитбоксы внутри объектов столкновения, вам пришлось бы загружать намного больше памяти, поскольку все хитбоксы находятся в разных строках кеша. Однако использование такого формата данных может быть преждевременной оптимизацией, поэтому вам придется профилировать свой код, чтобы убедиться, что вы действительно ощутите некоторые преимущества.

Конечное количество памяти

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

Зная, что компьютер может разместить в кеше только определенное количество данных, уменьшение объема используемой памяти означает, что вы можете разместить в кеше больше полезной памяти, что является последним методом, который я обсудю в этой статье. . В качестве практического примера, многие видеоигры AAA часто используют float (4 байта) вместо более точного double (8 байтов), потому что дополнительная точность редко бывает полезной (если вы сохраняете расстояние в метрах с помощью float, вы можете быть точными к микрометру.), и они не хотят тратить кеш-память.

Поменять местами память

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

На вашем компьютере есть подкачка памяти, которая работает так же, как комната в доме профессора рядом с дверью. Это в значительной степени вспомогательная оперативная память, которая работает медленнее. Если вам когда-либо потребуется больше памяти, чем есть в вашей оперативной памяти, вы в конечном итоге будете использовать память подкачки. Ваш компьютер умеет использовать своп, то есть он будет помещать в своп только то, что вы почти не используете (например, вкладки в вашем браузере, которые вы не просматривали в течение недели), и он будет использовать своп только тогда, когда он закончится оперативной памяти.

Что произойдет, если у меня закончится своп?

Не надо.

Серьезно, что произойдет, если у меня закончится своп?

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

Ответ по-прежнему: «Не делайте этого», потому что вам придется намеренно попытаться исчерпать свопинг или иметь дело с такими огромными объемами памяти, которые вы можете ожидать, что подкачка закончится. Например, всему геному человека требуется около 3 ГБ памяти для хранения всех пар оснований (технически меньше, но что угодно), что означает, что вы можете загрузить весь геном человека в память и при этом даже не исчерпать ОЗУ. Единственный практический способ избавиться от подкачки - это запустить одновременно больше программ на вашем компьютере или на нескольких вкладках Google Chrome.

С точки зрения профессора, отсутствие подкачки означает, что она копит и требует вмешательства.

Другие программы

Вы можете подумать, что ваша программа не будет использовать память подкачки, потому что у современных пользователей есть как минимум 8 ГБ ОЗУ, а вы используете только 5 ГБ ОЗУ, но вы должны помнить, что это не память вашей программы - это пользовательская память. Если они хотят также запускать несколько других программ во время работы вашей программы (например, слушать музыку или искать учебник о том, как использовать вашу программу, или делать несколько вещей в Интернете), они могут предложить вам только 2 ГБ. С другой стороны, если вы ожидаете, что пользователи будут использовать вашу программу, не используя одновременно кучу разных программ (например, большинство игр AAA 3D), то вы сможете использовать гораздо больше памяти, и пользователям все равно. .

Как вы получили ускорение в 4 раза?

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

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

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

Резюме

  • В вашем компьютере есть иерархия памяти, состоящая из
  1. Регистры
  2. Кеши
  3. баран
  4. Вторичное хранилище
  • где регистры - это самый быстрый тип памяти, а вторичное хранилище - самый медленный тип памяти.
  • Чем быстрее память, тем меньше ее у вас на компьютере.
  • Иерархия памяти позволит вам смоделировать наличие большого количества быстрой памяти.
  • Компьютер будет кэшировать память, к которой вы недавно обращались, и память, которая находится поблизости.
  • Написание эффективных программ означает попытку максимально использовать вашу высокоскоростную память, делая как можно больше с данными, к которым вы уже обращались, прежде чем пытаться получить доступ к большему количеству данных, сохраняя связанные данные вместе и используя как можно меньше памяти .
  • Память подкачки существует, и вы можете исчерпать ее, только если попытаетесь.

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

Первоначально опубликовано на https://tuacm.com.