Использование MMU для реализации массивов с изменяемым размером

Сначала несколько конкретных ответов на ваши вопросы:

• Да, во многих ОС программы имеют значительный контроль над своей виртуальной памятью, например, mmap в UNIX-подобных ОС и аналогичные API в Windows. В частности, Linux недавно добавил несколько методы, позволяющие расширенные манипуляции с видимыми пользователю буферами из ядра без копирования только одного из интересных — больше не для этого мира (по крайней мере, с точки зрения производительности).
• Обычно не существует конкретных ограничений на количество записей в таблице страниц для каждого процесса. Конечно, вы можете столкнуться с другими ограничениями, такими как ограничения памяти для каждого процесса, ограничения физической памяти и так далее. Доступ к памяти обычно не замедляется при увеличении количества записей. Конечно, общий доступ к большему количеству страниц может означать более медленный доступ (например, из-за превышения размера TLB), но это не является прямой функцией большего количества страниц. Сами записи таблицы страниц просто находятся в ОЗУ, поэтому вы можете без проблем иметь их миллионы.
• Изменение записей в таблице страниц выполняется достаточно быстро в современных операционных системах. Например, на моем ноутбуке изменение записей в таблице страниц занимает около 120 нс на страницу (плюс некоторые фиксированные накладные расходы на системный вызов).
• Да, вы можете найти примеры, но они обычно нацелены на довольно узкие сценарии. Фактически, вы можете видеть, что libc mach пытается использовать use Трюки MMU для не менее важной процедуры чем memcpy !

Обсуждение

Основная проблема с использованием трюков MMU заключается в том, что (а) вы можете «нулевое копирование» только целых страниц, что в значительной степени означает гранулярность 4 КБ или больше, наряду с аналогичным ограничительным выравниванием (б) даже если вызовы типа mmap выполняются быстро, как и эффективные процедуры копирования памяти!

Сначала рассмотрим (а). Если я вас правильно понял, вы хотите ускорить вставку во что-то вроде std::vector, используя приемы MMU для смещения элементов, которые необходимо переместить, когда происходит вставка. Проблема в том, что вы можете сдвигать только на 0, 4096, 8192 и т. д. байт на обычных системах! Итак, если вы вставите один 4-байтовый int в vector<int>, как это поможет? Возможно, вы могли бы «разбить» базовое хранилище vector на две части в точке вставки и отследить это с надеждой снова объединить их в какой-то момент (например, если вы вставите материал размером 4096 байт) - но вы в конечном итоге с другая структура данных, с другими свойствами, и трюки с MMU в любом случае не являются здесь фундаментальными.

Это подводит нас к пункту (б). Примите как должное, что на моей машине страница может быть переназначена примерно за 120 нс (через mmap). Это кажется быстрым (это неплохо, если учесть, что это включает в себя различные блокировки ядра, возню с таблицами страниц, добавление VMA и т. д.), но копирование памяти также происходит очень быстро. На этом же компьютере я могу копировать в память (то есть в/из ОЗУ любого уровня кэша) со скоростью около 12 ГБ/с, в то время как копирование в L1 или L2 происходит со скоростью 80-100 ГБ/с. Таким образом, копирование страницы размером 4 КБ занимает где-то между 41 нс (кэширование) и 340 нс (некэширование, в ОЗУ). Таким образом, возня с таблицами страниц не является явным выигрышем, даже если это было бы возможно, особенно в случае с кэшированием (а случай с кэшированием, вероятно, является доминирующим, усредняющим большинство рабочих нагрузок).

Таким образом, эти типы приемов могут иметь смысл, но только в определенных сценариях, таких как следующие:

• У вас есть какой-то способ справиться с тем фактом, что сопоставление страниц может перемещать/копировать/перемещать элементы только в фрагментах детализации страницы, например, потому что ваши структуры кратны детализации страницы, или вы используете пакетные вставки, которые являются кратными детализации страниц и т. д.
• У вас есть способ более быстрого сопоставления страниц: например, используя страницы размером 2 МБ, а не страницы размером 4 КБ, или написав некоторый код на стороне ядра, который ускоряет ваш вариант использования.
• Вы хотите использовать даже более причудливые приемы, чем просто перемещение памяти, например. заставить одни и те же данные появляться в двух местах одновременно, реализовать структуры COW или что-то в этом роде.

Реаллок

Самый распространенный и полезный пример трюков MMU — это, вероятно, realloc. В Linux и Windows (это кажется?), realloc можно реализовать путем переназначения и расширения отображаемых страниц в памяти (так называемые приемы MMU), что позволяет избежать физической копии и необходимости временно иметь как старую выделенную область, так и новую область «живыми». " сразу (что может быть сложно, если их сумма приближается к размеру физической памяти).

В частности, последняя версия Linux, скорее всего, будет использовать mremap для realloc областей кучи, которые были mmaped в первую очередь (по умолчанию это происходит для запросов на выделение больше 128 КБ, но это также может произойти, когда пространство, доступное для sbrk, исчерпано).