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

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

• Да, во многих ОС программы имеют значительный контроль над своей виртуальной памятью, например, mmap в UNIX-подобных ОС и похожие API на винде. Linux, в частности, недавно добавил несколько методы чтобы разрешить расширенные манипуляции с видимыми пользователем буферами из ядра без копирования — но один из интересных больше не для этого мира (по крайней мере, с точки зрения производительности).
• Обычно нет конкретных ограничений на количество записей в таблице страниц для каждого процесса. Конечно, вы можете столкнуться с Другой ограничения, такие как ограничения памяти для каждого процесса, ограничения физической памяти и так далее. Доступ к памяти обычно не замедляется при увеличении количества записей. Конечно, доступ к более страницы в целом это может означать более медленный доступ (например, из-за того, что вы превышаете размер TLB), но это не является функцией большего количества страниц. Сами записи таблицы страниц просто находятся в оперативной памяти, поэтому вы можете иметь миллионы из них без проблем.
• Изменение записей таблицы страниц разумно быстро на современных ОС. Например, на моем ноутбуке изменение записей в таблице страниц, кажется, занимает около 120 нс на страницу (плюс некоторые фиксированные накладные расходы для системного вызова).
• Да, вы можете найти Примеры там, но они обычно нацелены на довольно узкие сценарии. На самом деле, вы можете видеть, что libc Маха пытается использовать 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 ГБ / с. Таким образом, копирование страницы 4K занимает где-то между 41 нс (кэшировано) и 340 нс (не кэшировано, в ОЗУ). Так что возиться с таблицами страниц не является очевидной победой, даже если бы возможный, особенно в кэшированном случае (и кэшированный случай, вероятно, является доминирующим, усредненным по большинству рабочих нагрузок).

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

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

перераспределить

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

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