Оптимизация mmap на очень большом файле

Question

У меня очень большой файл 150 ГБ. Я использую только чтение mmap, и я выполняю двоичный поиск в файле.

В настоящее время бинарный поиск выполняется довольно медленно.

Однако я думаю о последующей оптимизации - когда я проверяю (поиск диска) какое-то значение, все значения «вокруг» этого значения уже находятся в памяти, потому что они принадлежат одному блоку диска. Вместо того, чтобы прыгать где-то еще в файл, я могу проверить «близкие» значения и перейти после этого.

Эта оптимизация стоит того?

Также, как я могу оценить, где заканчивается блок диска.

Answer 1

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

Поскольку вы используете mmap, минимальная степень доступа - это не размер блока диска, а размер «страницы» в памяти, который можно запросить с помощью sysconf(_SC_PAGESIZE). Некоторые операционные системы будут читать и заполнять большую часть памяти при произвольном доступе к файловому региону, но я не знаю какого-либо портативного способа узнать, сколько. Вы также можете получить некоторую выгоду от madvise(MADV_RANDOM).