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

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

Мне было интересно, можно ли использовать процессор MMU для более эффективного реализации списков путем переназначения вместо копирования памяти всякий раз, когда элемент вставлен или удален. Это означало бы, что как индексирование, так и вставка/удаление в любом месте массива должны иметь скорость O (1), лучше, чем любая другая реализация списка.

Ответы

Ответ 1

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

Да, во многих операционных системах программы имеют значительный контроль над своей виртуальной памятью, например mmap в UNIX-подобных операционных системах и аналогичные API в Windows. В частности, недавно Linux добавил несколько методы, чтобы разрешить расширенная манипуляция видимыми пользователем буферами из ядра без копирования — но один из интересных - больше не для этого мира (по крайней мере, по производительности).
Обычно нет конкретных ограничений на количество записей в таблице страниц для каждого процесса. Разумеется, вы можете столкнуться с другими ограничениями, такими как ограничения на производительность процесса, пределы физической памяти и т.д. Доступ к памяти обычно не становится медленнее с большим количеством записей. Конечно, доступ к большему количеству страниц может означать более медленный доступ (например, потому что вы превышаете размер TLB), но это не является прямой функцией большего количества страниц. Сами записи таблицы страниц просто сидят в ОЗУ, поэтому вы можете иметь миллионы из них без проблем.
Изменение записей таблицы страниц достаточно быстро на современных ОС. Например, на моем ноутбуке изменение записей в таблице страниц занимает около 120 нс на страницу (плюс некоторые фиксированные накладные расходы для системного вызова).
Да, вы можете найти примеры, но они обычно нацелены на довольно узкие сценарии. Фактически вы можете видеть, что mach 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 или что-то в этом роде.

Realloc

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

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