Cache местность с большими структурами в C

Question

Если у меня есть сшитая структура, как это:

struct phonebook { 
    char LastName[16]; 
    char FirstName[16]; 
    char Email[16]; 
    char PhoneNumber1[10]; 
    char PhoneNumber2[10]; 
    char Addr1[16]; 
    char Addr2[16]; 
    char City[10]; 
    char Country[12]; 
    char State[2]; 
    struct phonebook *pNext; 
} 

, когда я хочу, чтобы найти кого-то сопрягать фамилию,
я могу использовать

while (pHead != NULL) { 
    if (strcasecmp(lastname, pHead->LastName) == 0) 
      return pHead; 
    pHead = pHead->pNext; 
} 

return NULL; 

что-то например, но каждый раз, когда я получаю узел телефонной книги, кеш загружает всю структуру, а кеш пропускает много.
Итак, как я могу увеличить скорость попадания в кеш?
Как получить сгруппированный LastName s в кеше?

Без горячего/холодного или перерыв связанного списка в цепочку хеш-таблицы.

Answer 1

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

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

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

TCMalloc также может обеспечить улучшение скорости попадания в кеш, поскольку он достаточно эффективен для использования в небольших объемах. Он также пытается сохранить последовательные небольшие выделения на одной странице памяти 4K.

Как улучшить способ поиска

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

Answer 2

каждый раз, когда я получаю узел телефонной книги, кеш загружает всю структуру, а кеш пропускает много. Итак, как я могу увеличить скорость попадания в кеш? Как получить сгруппированные LastNames в кеше?

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

Вы можете, однако, создать индекс, состоящий из динамического массива мелких структур, таких как

struct pb_index { 
    char LastName[16]; 
    struct phonebook *entry; 
} 

В LastName массивы будут более плотными внутри этого динамического массива, чем в массиве phonebook с, так сканирование через такой массив позволит более эффективно использовать кеш, чем сканирование через ваш связанный список.

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