Linux: большой массив int: mmap против файла поиска?

Предположим, у меня есть набор данных, представляющий собой массив из 1e12 32-битных целых (4 ТБ), который хранится в файле в файловой системе 4D HDD ext4

Учтите, что данные, скорее всего, случайны (или, по крайней мере, кажутся случайными).

// pseudo-code
for (long long i = 0; i < (1LL << 40); i++)
   SetFileIntAt(i) = GetRandInt();

Кроме того, учтите, что я хочу прочитать отдельные элементы int в непредсказуемом порядке и что алгоритм работает неопределенно долго (он продолжается).

// pseudo-code
while (true)
   UseInt(GetFileInt(GetRand(1<<40)));

Мы на Linux x86_64, gcc. Можно предположить, что система имеет 4 ГБ ОЗУ (т.е. в 1000 раз меньше, чем набор данных)

Ниже приведены два способа создания доступа:

(A) преобразовать файл в блок памяти объемом 4 ТБ и получить к нему доступ в виде массива int

(B) откройте (2) файл и используйте seek (2) и прочитайте (2), чтобы прочитать целые числа.

Из A и B, которые будут иметь лучшую производительность? И почему?

Есть ли другой дизайн, который даст лучшую производительность, чем A или B?

 bobah14 июн. 2012 г., 14:32
#C будет загружать его из сети с помощью технологии обхода ядра (например, RDMA на infiniband). Это будет где-то между А и Б.
 D. Cannone14 июн. 2012 г., 13:54
Скорость доступа к ОЗУ выше скорости доступа к HD (некоторого порядка из-за отсутствия механических частей). Если у вас нет проблем с памятью, сопоставление всех файлов в ОЗУ - лучшее решение, которое вы можете иметь. Вы также можете рассмотреть твердотельные накопители (которые очень похожи на RAM). Кроме того, если произвольный доступ означает действительно произвольный доступ, вы можете отключить кэш для улучшения некоторых характеристик (то есть, если вероятность доступа к одному и тому же элементу очень мала, поиск в кеше бесполезен).
 Benoit14 июн. 2012 г., 13:56
@D. Cannone Сохранение кэша для других целей при произвольном доступе просто здорово, спасибо!

Ответы на вопрос(4)

системы. Ext4 должен быть хорошим выбором, поскольку он используетдеревья экстента, Также, если ваш файл имеет линейное непрерывное распределение, дерево экстентов будет состоять из одной записи, что делает поиск тривиально эффективным.

memory swap в результате чего незначительныйpagefaultsпрозрачный для аппликативного. С другой стороны, у вас есть многочисленныеsystem callsс известными накладными расходами. Страница Википедии оотображенный в память файл мне кажется вполне понятным, он всесторонне просматривает плюсы и минусы.

Я думаю, что 64-битная архитектура + вызов большого файла для файлового подхода с отображением в памяти, по крайней мере, чтобы не усложнять аппликатив; Мне сказали, что сложность часто ведет к снижению производительности. тем не мениеmmap() Обычно для последовательного доступа, который не является целью здесь.

Поскольку это чисто произвольный доступ, существует небольшая вероятность того, что два доступа будут на одной и той же странице, загруженной в ОЗУ. Полная страница 4 КБ будет перенесена с жесткого диска в ОЗУ, только для 4-байтовых данных ... Это бесполезная загрузка шин и, вероятно, приведет к снижению производительности.

Надеюсь, это поможет.

 29 нояб. 2012 г., 11:59
Поскольку ни один жесткий диск не позволяет выполнять чтение или запись размером менее одного блока, на самом деле нет способа сделать чтение с диска менее 512 байт независимо от того, что вы делаете, даже если вы используете необработанный доступ / запись пользовательской ОС и т. Д. файловая система может быть выше.

Вероятно, для линейного набора данных объемом 4 ТБ вам не нужна файловая система. Я полагаю, что простой доступ к устройству может принести некоторые преимущества в производительности.

Также возможно есть способ оптимизировать запросы или структуру данных, чтобы кэширование могло использоваться более эффективно?

 Andrew Tomazos17 июн. 2012 г., 18:26
Что такое «линейный» набор данных?
 17 июн. 2012 г., 20:17
Он не был бы линейным, если бы он содержал несколько массивов, плюс несколько хеш-индексов или индексов btree, транзакций и т. Д. :)
 17 июн. 2012 г., 20:16
& Quot; линейный & Quot; в том смысле, что это один большой массив с линейной индексацией. Чтобы получить N-й элемент, вы обращаетесь к нему со смещением N * sizeof (элемента).
 17 июн. 2012 г., 20:21
также "линейный" в том смысле, что вам не нужны никакие дополнительные поиски или вычисления для извлечения N-го элемента
Решение Вопроса

что производительность должна быть одинаковой, если доступ действительно случайный. ОС будет использовать аналогичную стратегию кэширования, независимо от того, отображается ли страница данных из файла или данные файла просто кэшируются без привязки к ОЗУ.

Предполагая, что кэш неэффективен:

You can use fadvise to declare your access pattern in advance and disable readahead. Due to address space layout randomization, there might not be a contiguous block of 4 TB in your virtual address space. If your data set ever expands, the address space issue might become more pressing.

Так что я бы пошел с явным чтением.

Ваш ответ на вопрос