Блог

Я пишу некоторый критически важный для производительности код (т. Е. в очень узком цикле и обозначается профилированием), логика которого в основном ( the_key является параметром и mmap_base является базовым адресом файла, отображенного в памяти):

 while (current_item amp;amp; (struct my_struct *)(mmap_base   current_item) -> key < the_key){
    /* Do something less performance critical */
    current_item = (struct my_struct *)(mmap_base   current_item) -> next;
}
  

Профилирование указывает, что этот фрагмент кода ограничен диском при разыменовании (mmap_base current_item) , что имеет смысл, поскольку произвольный ввод-вывод с диска выполняется значительно медленно.

Невозможно загрузить соответствующую часть в mmap в память, поскольку файл огромен — около 100 ГБ. Я подумываю об использовании чего-то вроде __builtin_prefetch() :

 while (current_item amp;amp; (struct my_struct *)(mmap_base   current_item) -> key < the_key){
    __builtin_prefetch(mmap_base   ((struct my_struct *)(mmap_base   current_item) -> next), 0, 0);
    /* Do something less performance critical */
    current_item = (struct my_struct *)(mmap_base   current_item) -> next;
}
  

Однако это не сработает. Похоже, что __builtin_prefetch() это в любом случае бесполезно в памяти с поддержкой mmap.
Затем я попытался madvise() :

 while (current_item amp;amp; (struct my_struct *)(mmap_base   current_item) -> key < the_key){
    madvise(mmap_base   ((struct my_struct *)(mmap_base   current_item) -> next), sizeof(struct my_struct), MADV_WILLNEED);
    /* Do something less performance critical */
    current_item = (struct my_struct *)(mmap_base   current_item) -> next;
}
  

Однако это даже снизило производительность, а профилирование показало, что madvise() вызов теперь становится основной нагрузкой.

Существуют ли какие-либо встроенные компиляторы (x86_64, GCC) или другие способы сообщить ядру (linux) о предварительной выборке данных с диска в кэш памяти / процессора?

Редактировать 1:
Некоторые предположили, что это просто невозможно без улучшения локализации данных. Однако в таком случае я задаюсь вопросом, почему невозможно выполнить асинхронное чтение с диска при переходе к «менее критичной к производительности» части, которая должна обеспечивать более быстрый доступ; это больше связано с тем, что ядро не реализует это или просто теоретические / физические ограничения?

Редактировать 2:
Некоторые рекомендуют использовать отдельный поток для предварительного доступа к памяти, чтобы позволить ядру выполнять предварительную выборку. Однако я думаю, что потоки могут быть дорогими. Действительно ли полезно запускать поток для каждой предварительной выборки? Код находится в замкнутом цикле, так что это может означать, что потребуется запустить / объединить множество потоков. С другой стороны, если я использую только один поток, как я должен сообщить ему о том, что нужно предварительно выбрать?

Этот тип шаблона доступа всегда будет медленным, потому что он потенциально перемещается без какого-либо разумного способа предсказать шаблон.

Подход, который я бы попробовал, заключается в создании отдельного файла индекса ключей, отображенного в памяти, только со значениями ключей и смещением соответствующей записи; с ключами, отсортированными в порядке возрастания. Таким образом, для поиска определенного ключа требуется примерно O (log N) времени сложности (в зависимости от того, как вы работаете с дубликатами ключей), используя очень простой двоичный поиск.

Если ключи в файле объемом 100 ГБ изменяются во время работы, отдельный плоский файл не подходит для описания данных.

Если вы можете справиться со сложностью кода, разделенные двоичные деревья поиска в форме массива обладают еще большей производительностью. В этом случае вы разбиваете индексный файл на части фиксированного размера, скажем, 64 Кб (4096 пар ключ-смещение), содержащие в виде массива прямоугольную часть идеально сбалансированного двоичного дерева поиска. Например, самый первый раздел содержит средние клавиши, клавиши 1/4 и 3/4, клавиши 1/8, 3/8, 5/8 и 7/8 и так далее. Кроме того, вы включаете ключи только в первичный индексный файл и используете вторичный индексный файл для смещений записей. (Если у вас есть дубликаты ключей, сделайте так, чтобы вторичный индексный файл ссылался на первый, при этом каждая дублирующаяся запись второго индексного файла ссылалась на следующую, чтобы вы могли отслеживать цепочку напрямую с небольшими затратами времени, но без дополнительных затрат места.)

Это обеспечивает гораздо лучшую локальность, чем двоичный поиск в отсортированном массиве, но сложность кода и логики немного пугает.