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

вступление

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

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

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

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

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

Эксперимент

Как это выглядит на практике? Давайте сделаем простой тест, напишем крошечную программу на C++ с одним простым глупым связанным списком, запишем туда несколько целых чисел и посмотрим, что произойдет с локальностью.

Угадайте, что: узлы распределяются непрерывно! Или вроде. Обратите внимание, что a sizeof(Node)==16, так что распределение на самом деле имеет дополнительный резерв. Это все еще достаточно локально.

Несмотря на то, что структура данных не требует этого, мы не навязываем локальность, и мы даже не просили об этом, мы все равно ее получаем! Насколько нам повезло?? Как это вообще возможно? Бог программист??

Обсуждение

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

Раньше я думал, что когда вы запускаете malloc(), вы получаете какой-то случайный свободный блок памяти, как манна, падающая с небес операционной системы. Однако это не так. Есть библиотеки, работающие с этой памятью, запускающие алгоритмы и многое другое. Эта память, используемая вашей голой программой C++, на самом деле управляется для вас библиотеками, такими как glibc. Это не сборщик мусора — к сожалению, могут сказать некоторые. Но создатели этих библиотек очень хорошо осведомлены о таких принципах, как локальность памяти, и делают все возможное, чтобы предоставить вам разумное распределение памяти.

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

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

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

Вывод

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

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

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

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

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

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

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

Удачи всем вам.