Вызывает ли использование таблиц ha sh фрагментацию памяти?

Question

Насколько я понимаю, таблицы ha sh состоят в том, что они используют функции ha sh, чтобы связать ключи с местами в памяти, с общим количеством «сегментов», предварительно выделенных в памяти. Цель состоит в том, чтобы было достаточно блоков, чтобы мне не приходилось использовать цепочку, замедляя мою идеальную сложность времени доступа O(1) до n/m x O(1), где n - количество уникальных ключей для хранения, а m - количество сегментов. .

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

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

Answer 1

1000 байт выделенной памяти, распределенной вокруг моей памяти

Нет, у вас есть один массив из 1000 записей (некоторого размера, который почти наверняка больше, чем 1 байт на запись).

Если каждая запись достаточно велика, чтобы обрабатывать регистр без столкновения, дополнительное динамическое распределение c не требуется, пока не произойдет столкновение. (например, возможно, вы используете объединение и 1-битный флаг, чтобы указать, является ли эта запись автономным сегментом или указателем на связанный список.)

Если нет, тогда , когда вы напишите запись , для нее должно быть выделено место и указатель хранится в самом массиве таблиц. (например, ключ-значение ha sh таблица с маленькими ключами, но большими значениями). Пустая таблица ha sh все еще может быть заполнена указателями NULL.

Возможно, вы захотите, чтобы она содержала структуры указателя и значение ha sh (для одноэлементных сегментов). Затем вы можете отклонить запросы, которые явно отсутствуют, без другого уровня косвенности, если полное значение ha sh не соответствует запросу; например, для 32 или 64-битного га sh это намного больше битов, чем 10 бит для индексации таблицы с 1024 записями.

---

Чтобы уменьшить общую фрагментацию, вы можете использовать распределитель slab или другое Техника для вырезания узлов из смежного блока, который вы получаете из глобального распределителя. Наличие в таблице ha sh собственного частного списка свободных номеров может помочь в пространственной локализации узлов связанного списка, поэтому они, по крайней мере, не разбросаны по множеству различных виртуальных страниц (пропуски TLB) и, возможно, не страницы DRAM (даже более медленный кэш пропускает)