Эффективное изменение порядка большого набора данных для максимальной эффективности кеш-памяти

Question

Я работаю над проблемой, которая, как мне показалось, людям может показаться интересной (и, возможно, кто-то знает о ранее существовавшем решении).

У меня большой набор данных, состоящий из длинного списка пар указателей на объекты, что-то вроде этого:

[
  (a8576, b3295), 
  (a7856, b2365), 
  (a3566, b5464),
  ...
]

Существует слишком много объектов, чтобы хранить их в памяти одновременно (возможно, сотни гигабайт), поэтому они должны храниться на диске, но могут кэшироваться в памяти (возможно, с использованием кэша LRU).

Мне нужно пройти через этот список, обрабатывая каждую пару, для чего требуется, чтобы оба объекта в паре были загружены в память (если они там еще не кэшированы).

Итак, вопрос: есть ли способ переупорядочить пары в списке, чтобы максимизировать эффективность кэша в памяти (другими словами: минимизировать количество пропусков кэша)?

Примечания

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

2. Если бы мы имели дело с отдельными объектами, а не парами, то простым ответом было бы отсортировать их. Это, очевидно, не сработает в этой ситуации, потому что вам нужно учитывать оба элемента в паре.

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

4. Я предполагаю, что эвристик будет передавать данные с диска и записывать их порциями в лучшем порядке. Возможно, придется повторить это несколько раз.

5. На самом деле это могут быть не просто пары, это могут быть триплеты, четверки или больше. Я надеюсь, что алгоритм, который делает это для пар, может быть легко обобщен.

Answer 1

Ваша проблема связана с аналогичной проблемой для компьютерной графики:

При рендеринге индексированных вершин в треугольной сетке, как правило, аппаратное обеспечение имеет кэш самых последних преобразованных вершин (~ 128 в последний раз, когда мне приходилось беспокоиться об этом, но подозреваю, что число в эти дни больше). Для вершин без кэширования требуется относительно дорогая операция преобразования для вычисления. «Оптимизация ячеек» для реструктуризации треугольных ячеек с целью оптимизации использования кеша была довольно горячей темой исследования. погуглить оптимизация вершинного кэша (или оптимизация: ^) может найти интересный материал для вашей проблемы. Как предполагают другие авторы, я подозреваю, что эффективное выполнение этого будет зависеть от использования какой-либо внутренней последовательности в ваших данных.

Еще одна вещь, которую следует иметь в виду: поскольку кэш LRU становится перегруженным, может быть целесообразно перейти на стратегию замены MRU, чтобы хотя бы удерживать некоторые элементы в памяти (вместо того, чтобы переворачивать весь кэш при каждом проходе). Кажется, я помню, что Джон Кармак написал хороший материал на эту тему в связи со стратегиями кэширования текстур Direct3D.

Answer 2

Для начала вы можете mmap список. Это работает, если есть достаточно адресного пространства, а не памяти, например на 64-битных процессорах. Это облегчает доступ к элементам по порядку.

Вы можете отсортировать этот список по минимальному расстоянию в кэше, которое учитывает оба элемента, что хорошо работает, если объекты находятся в смежном пространстве. Функция сортировки может выглядеть примерно так: сравнить (a, b) с (c, d) = (a - c) + (b - d) (что похоже на расстояние Хэмминга). Затем вы извлекаете фрагменты хранилища объектов и обрабатываете их согласно списку.

РЕДАКТИРОВАТЬ: исправлена ​​ошибка на расстоянии.

Answer 3

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

Answer 4

Я думаю, что ответ на этот вопрос будет очень сильно зависеть от именно схемы доступа пары объектов. Как вы сказали, простая сортировка указателей будет лучше в простом непарном случае. В более сложном случае может иметь смысл отсортировать по одной из половин пары, если шаблон таков, что локальность для этих значений более важна (если, например, это пары ключ / значение и вы много поисков, локальность для ключей бесконечно важнее, чем для значений).

Итак, действительно, мой ответ таков: на этот вопрос нельзя ответить в общем случае.

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