Введение
До подобного момента надо ещё дожить, но однажды случается и такое. В один прекрасный день мне понадобилась БД с 1 триллионом записей. Причём, понадобилась на домашнем компьютере, где свободного места 700 гигабайт на двух дисках.
По счастью, моя БД не совсем обычная: размер записи всего 1 бит. В базе должны храниться данные о простых числах. Соответственно, вместо того, чтобы хранить сами числа, проще хранить один бит (1 - простое число, 0 - композитное). И тогда, чтобы хранить один триллион битов, нужно всего 116 ГБайт.
Однако сделав такой файл, мы получили только лишь хранилище, но не собственно БД. Нам нужен код, который будет записывать и считывать данные. Традиционный FileStream был отброшен сразу, по причине его медленности. Постоянное чередование Seek и чтения/записи по 1 байту даёт результат примерно в 100 раз худший, чем отображаемых на память файлы, опытом использования которых я и хочу поделиться в этой статье.
Отображаемые на память файлы
Отображаемые на память файлы (ОПФ) работают за счёт аппарата виртуальной памяти. По принципу работы они аналогичны файлу подкачки Windows (pagefile.sys) с той разницей, что доступ к последнему есть только у самой ОС, а ОПФ доступен владельцу и может разделяться между процессами.
Отображаемые на память файлы реализованы: в WinAPI – функцией MapViewOfFile, а в .NET – классами MemoryMappedFile, MemoryMappedViewAccessor и MemoryMappedViewStream.
Работают эти классы так. MemoryMappedFile открывает СПФ, подключая его к адресному пространству приложения. Для этого у него есть методы CreateFromFile, CreateNew, CreateOrOpen, OpenExisting. Открытие СПФ не влечёт значимых расходов памяти, т.к. распределяется виртуальная, а не физическая память.
Чтобы получить доступ к содержимому файла, необходимо использовать один из двух классов, которые его предоставляют. Прямой доступ предоставляется классом MemoryMappedViewAccessor, а последовательный – классом MemoryMappedViewStream.
Для своего приложения я использовал прямой доступ, соответственно основная часть этой статьи посвящена особенностям MemoryMappedViewAccessor, главным образом, выбору между затратами памяти или времени.
Этот выбор стал для меня критическим, когда я занялся заполнением БД при помощи алгоритма, известного как решето Эратосфена. Это крайне простой алгоритм. Исходный код приводится для того, чтобы показать, в каком окружении работает ОПФ и в каком месте делается выбор между расходом памяти или времени.
public void FindPrimes(long start, long interval, ref bool quit)
{
long upper = (long)Math.Sqrt(Registry.Header.Length);
long l = 0;
Console.WriteLine($"Eratosthenes Primer: iterating {start} to {upper}...");
for (long i = start; i <= upper; i ++)
if (Registry.Contains(i)) // если i - простое число
for (long n = i * i; n <= Registry.Header.Length; n += i)
{
// все числа кратные i - не простые
Registry.SetState(n, false);
l ++;
if (0 != l % interval)
continue;
// выбор между расходом памяти и времени
Registry.Flush(); // расход времени
// Registry.Flush(); расход памяти
if(quit)
goto quit;
}
quit: ;
}Функция FindPrimes реализует решето Эратосфена. Она устанавливает, что числа, кратные простым, сами простыми не являются, и последовательно исключает их.
В данном фрагменте Registry – это собственно БД на основе MemoryMappedViewAccessor. Её методы: Contains() – проверяет, является ли число простым; SetState() – устанавливает признак простого (True) или композитного (False) числа.
Метод Flush() сбрасывает сделанные изменения на диск (MemoryMappedViewAccessor.Flush()), избавляется от аксессора (MemoryMappedViewAccessor.Dispose()) и создаёт вместо него новый. Использование или неиспользование этого метода и определяет, что будет расходоваться сильнее – память или время.
Параметр interval (в моём случае 100 млн.) подобран таким, чтобы периодический отчёт о прогрессе (в коде выше отсутствует) происходил примерно раз в 5 секунд. Будучи запущенной, программа показала следующее поведение.
Изначально вызоваRegistry.Flush()в программе не было. В диспетчере задач программа занимает не более 3 МБ, но общий расход памяти очень быстро доходит до 99%. При этом, время отклика компьютера значимо не растёт, новые приложения запускаются, из чего можно сделать вывод, что Windows отдаёт моему СПФ всю доступную память, но не в ущерб другим приложениям.
Насколько быстро работает ОПФ? 100 млн. вызовов Registry.SetState()занимает примерно 4,5 - 5 секунд, таким образом, первая итерация по i=3 занимает в общей сложности 4 часа. Мой СПФ расположен на HDD, видимо, на SSD затраты времени были бы меньше.
Можно заметить, что с ростом i вложенный цикл выполняется всё быстрее и быстрее, т.к. как шагаем всё более длинными шагами. При i=3он занимает 4 часа, для i=5 3 часа, для i=72 часа с хвостом и т.д. (в данный момент ещё работает). Медлительный вначале, к концу алгоритм Эратосфена разгоняется как ракета.
Дальнейшая работа над программой была направлена на снижение расхода памяти. Для этого в конце интервала был добавлен вызов Registry.Flush(). Этот вызов возымел нужное действие, расход памяти растёт во вложенном цикле, но при вызове Flush() падает до исходного уровня. Таким образом, задача казалась решённой.
Начиная с i=3, вызов Flush()добавлял около 700 мс к 4,5 - 5 секундам, что казалось приемлемой ценой за экономию памяти. Однако, это время начало быстро расти с ростом i: при i=5 850 мс, при i=7 1 сек и так далее. При i=823 время на Flush()было уже порядка 40 секунд! В результате, рост скорости алгоритма был полностью съеден увеличивающимися затратами времени на Flush().
Этот результат показывает, что при отработке Flush(), MemoryMappedViewAccessor пишет на диск весь диапазон между собственно изменёнными байтами. И, поскольку с ростом i, мы "шагаем всё шире", этот диапазон становится больше.
Данная особенность MemoryMappedViewAccessor заставила отказаться от сброса аксессора и экономии памяти. К сожалению, упомянутые в статье классы не имеют каких-либо опций настройки использования памяти.
Выводы
Как следует из документации MSDN, класс MemoryMappedFile предназначен специально для работы с очень большими объёмами данных: "Memory-mapped files enable programmers to work with extremely large files". При использовании MemoryMappedViewAccessor прямой доступ к данным через ОПФ работает значительно быстрее, чем FileStream.
В то же время, при использовании описанных классов нужно помнить, что скорость записи данных на диск при использовании MemoryMappedViewAccessor зависит не только от объёма изменённых данных, но и от расстояния между ними.
Комментарии (33)
emaxx
27.03.2022 22:47+1Не будет ли гораздо эффективнее разбить просеиваемые числа на блоки по, скажем, миллиарду бит в каждом? Тогда мы не будем пробегать по диску много раз, да и вообще весь текущий блок будет помещаться в ОЗУ, и сбросить его на диск надо будет лишь один раз простой одноразовой записью (а вообще, не зная вашей задачи, трудно сказать, нужно ли вообще будет хранилище на диске).
Чтобы выполнить просеивание в отдельно взятом блоке, достаточно знать простые до квадратного корня из верхней границы (т. е. в вашем случае нужны будут простые до миллиона).
P.S. На всякий случай - решето Эратосфена, особенно в такой "лобовой" реализации, как в статье - не самый лучший способ поиска всех простых.
Ramayasket Автор
28.03.2022 01:38Спасибо за внимание к материалу. Идея сделать по блокам, используя имеющиеся в наличии простые до миллиона, отличная. Конечно у меня они есть, т.к. предварительно прогнал эту программу на 16 ГБ (это примерно до 137 миллиардов). Но переписывать программу не хочу (да и времени нет, это всё на досуге). Пусть уже лошадка доработает.
Далее, на диске иметь их нужно, да, т.к. список простых это исходный материал для другого исследования. Я про него напишу отдельно, после того как триллион посчитается и покажет свои результаты.
А поподробнее про более эффективное решето что можете сказать?
emaxx
28.03.2022 01:52+2Решето Эратосфена можно дальше улучшить, например, только рассматривая и храня нечётные числа - это ускоряет примерно вдвое. (Аналогично, можно было бы отсечь и кратные трём, пяти, и т. д., но это уже сделает код более муторным. Отсечение чётных же делается буквально парой изменений в границах цикла и обращениях к массивам.)
Также есть модификации этого решета, которые совершают лишь линейное число модификаций: http://e-maxx.ru/algo/prime_sieve_linear.
Но при ваших объёмах попробовать сделать блочное решето точно имеет смысл, потому что вместо прыжков по почти терабайтным файлам будет работа чисто в ОЗУ с периодическим сбросом результатов очередного блока на диск. Реализация там не сильно сложнее - по сути, вы сначала делаете обычное решето до 10^6, а затем идёте по блокам. Каждый блок обрабатывается почти стандартным алгоритмом, только внешний цикл идёт по предпосчитанным выше простым, а внутренний - по кратным им числам, лежащим внутри блока.
А вообще обычно ссылаются на решето Аткина как на самое быстрое. Я не знаю, как оно будет вести при вашем профиле нагрузки, так как я его самостоятельно никогда не "щупал".
Ramayasket Автор
28.03.2022 08:55Так ведь чётные числа отсекаются в строке где проверка на простоту числа, в
if (Registry.Contains(i))между внешним и внутренним циклами. Поэтому и нет никакого ускорения вдвое.
mayorovp
28.03.2022 11:29+3Вам, как минимум, приходится хранить их. Если не хранить признаки простоты чётных чисел — вам понадобится в два раза меньше памяти. А это уже приведёт к ускорению.
emaxx
28.03.2022 13:30Помимо того, что отметил mayorovp, при игнорировании чётных внутренний цикл будет делать вдвое меньше итераций. Например, при вычеркивании кратных числу 3 мы будем только итерироваться по числам 9, 15, 21, и т. п., и не будем тратить нисколько времени на вычеркивание заведомо бесполезных 12, 18, 24.
Tzimie
27.03.2022 22:53+2Мне кажется чем дальше, тем реже встречаются простые числа, и по памяти все это можно ужать. Правда за счёт скорости. А что вы такое делаете? Опровергаете Римана?)
Ramayasket Автор
28.03.2022 10:17Нет-нет, никого не опровергаю. Нашёл интересную декомпозицию натурального числа на суммируемые простые числа, исследую её свойства.
ARad
28.03.2022 00:01Использование MMF накладывает слишком много накладных расходов по сравнению с массивом.
Поэтому, думаю намного быстрее было бы продвигаться блоками определенного разумного размера и просеивать рабочий блок на все простые числа сразу. После уже скидывать готовый блок в результирующий файл. Рабочий блок будет всего один и будет целиком помешаться в память при выборе разумного размера.
Это позволит выполнять только последовательные чтения и записи, что является самым быстрым доступом к файлам. А также позволяет продолжать работу с любого места где программа остановилась прошлый раз. Так как в файл будут записываться только полностью готовые блоки.
Таким образом можно обработать все простые пока не надоест по времени или не закончится место на диске или не закончится диапозон uint64 например.
Daddy_Cool
28.03.2022 01:25Очень интересно, но что такое "Сопоставленные в памяти файлы" я так и не понял, а жаль. Впрочем спасибо за новое понятие - можно погуглить и разобраться, возможно окажется полезным.
Ramayasket Автор
28.03.2022 01:39-1Это прямой русский перевод "memory mapped files". Так в русском MSDN написано, оттуда и взял.
aegoroff
28.03.2022 08:36+2Так MSDN в основном с помощью машинного перевода делается. В русском техническом языке более употребим термин - отображаемые в память файлы
aegoroff
28.03.2022 08:34Немного оффтоп - в последнем примере кода вместо goto quit, лучше сделать простой return
Ramayasket Автор
28.03.2022 08:51Это просто потому что в исходной программе после цикла ещё код есть
ARad
28.03.2022 09:00Почему нет оптимизации на четные числа? Это уже экономия по памяти в 2 раза.
Ramayasket Автор
28.03.2022 09:02Лень было делать. А память всё равно была бы занята вся, это ж ОС делает.
ARad
28.03.2022 11:56У вас скорее всего скорость расчета упирается в скорость записи на диск. Таким образом сократив файл вы автоматически ускорите скорость расчета примерно в два раза.
Ramayasket Автор
28.03.2022 21:58Улучшение в два раза мне не поможет, я буду переделывать программу ради ускорения на порядок или больше, как Вы и написали, по блокам, туда и воткну сокращение в два раза.
miga
28.03.2022 12:13Ну что ж вы так, простые числа можно было бы хранить поинтереснее, чем просто в битовом массиве. Например, как в MPEG, выбрать сколько-то "опорных" чисел и закодировать их как есть, а между - хранить только расстояния до следующего простого числа, они все относительно небольшие, максимально известное расстояние в 1550 уместилось бы в 11 бит (см. Prime gap)
lightln2
29.03.2022 13:38Спасибо за статью, я раньше думал, что memory-mapped файлы не очень хорошо работают на Windows.
База на диске — хороший компромисс между скоростью работы и простотой реализации, но для некоторых задач она не нужна:
— Если у вас в основном последовательный доступ, то есть, вам надо перебрать простые числа на интервале [X… Y], то имеет смысл их каждый раз заново просеивать: достаточно заранее в памяти просчитать и держать список простых чисел до sqrt(N), в вашем случае — до миллиона.
— Если у вас полностью рандомный доступ, то выгоднее воспользоваться критерием простоты чисел: en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases. Аккуратно написанный, он дает скорость 20 микросекунд на число (в отличие от 2 миллисекунд на seek на HDD): ceur-ws.org/Vol-1326/020-Forisek.pdf
Альтернативно, базу можно сократить в два раза, если хранить биты только на каждое нечетное число, или даже в три раза, если хранить только числа, дающие при делении на 6 остатки 1 или 5 (остальные не могут быть простыми, кроме чисел 2 и 3). А можно вообще упороться, и хранить только числа, дающие один из восьми остатков от деления на 30, что как раз занимает один байт. Я это все описывал в habr.com/ru/post/526924, там есть код на C#, который можно использовать для этого.
barloc
А потом вы бы узнали про разряженные битовые поля, и все ужалось бы еще сильнее.
Daddy_Cool
Таки "разреженные". Погуглил - термина "разреженные битовые поля" не нашел. Распространите пожалуйста.
mayorovp
А что тут распространять? Битовое поле строится над массивом. Массивы бывают разреженными. Разреженное битовое поле — это битовое поле, построенное над разреженным массивом.
MrSmith33
Можно гуглить по термину
Sparse bit set