Библиотека сайта rus-linux.net
На главную -> MyLDP -> Программирование и алгоритмические языки
| Ulrich Drepper "Как писать разделяемые библиотеки" | ||
| Назад | Оглавление | Вперед |
1.5.3. Хеш таблица в стиле GNU
Во всех вариантах оптимизации, предложенных в предыдущем разделе, существенным фактором все еще остается поиск символов. Должно быть проверено большое количество данных и загрузка всех этих данных в кэш процессора требует больших затрат. Как уже упоминалось ранее, исходная обработка хэш-таблиц ELF не обладает достаточной гибкостью, поэтому ее можно заменить любым решением. Например, тем, что предлагается при обработке хэш-таблиц в стиле GNU. Эта обработка может мирно сосуществовать с обработкой хэш-таблиц старого стиля, поскольку у нее есть своя собственная точка входа в динамическую секцию (DT GNU HASH). Обновленный динамический компоновщик будет вместо старой использовать новую хеш-таблицу, поэтому предлагается абсолютно прозрачная поддержка обратной совместимости. Новая реализация хэш-таблицы, точно также как и старая, является самодостаточной для каждого исполняемого модуля и объекта DSO, поэтому не возникнет никаких проблем, если в одном и том же процессе некоторые двоичные модули будут в с новой хэш-таблицей, а некоторые — со старой.
Основными затратами на поиск, особенно для некоторых бинарных файлов, является сравнение имен символов. Если можно уменьшить число сравнений, которые фактически должны быть выполнены, мы можем получить больше. Вторая возможная оптимизация это размещение данных. Хэш-таблица старого вида с ее связанным списком табличных записей не обязательно является хорошим решением при использовании кэша процессора. Кэш процессора работает особенно хорошо, когда используемая память располагается последовательно. В связном списке могут быть дикие переходы в любом направлении, что делает использование кэша процессора и предварительную выборку менее эффективными.
Утверждается, что с помощью хэш-таблицы в стиле GNU будут решены эти проблемы и многое другое. Т.к. совместимость с существующими средами реального времени можно обеспечить при помощи одновременного присутствия хэш-таблиц старого вида, никакие ограничения на изменения не потребовались. Поэтому новый процесс поиска слегка отличается:
- Определяем хэш-значение для имени символа.
- Для первого / следующего объекта в области поиска:
- Используем хэш-значение для определения, есть ли вообще запись с заданным хэш-значением. Это делается с помощью 2-битного фильтра Блума {Примечание 6}. Если фильтр указывает, что такого определения не существует, то происходит переход к поиску следующего объекта в области поиска.
- С помощью хеш-значения определяем хэш-группу и размер хэш-таблицы в объекте. Значение является индексом символа.
- Из цепочки массива берется запись, соответствующая индексу символа. Мы пытаемся найти местоположение при помощи сравнения значения с хэш-значением символа. Бит 0 игнорируется.
- Если хэш-значение совпадает, то берем смещение имени символа и используем его в качестве имени с завершающим значением NUL.
- Сравниваем имя символа с именем перемещения.
- Если имена совпадают, то также сравниваем имена версий. Это должно выполняться только если в ссылке и в определении используются версиями. Для этого также требуется сравнения строк. Если имена версий совпадают или если такое сравнение не производится, то мы нашли определение, которое искали.
- Если определение не совпадает и в значении, загруженном из хэш-групп, бит 0 не установлен, то переходим к следующей записи в массиве хэш-групп.
- Если бит 0 установлен, то в хэш-цепочке, которую мы обрабатываем, больше записей нет и мы продолжаем со следующим объектом в области поиска.
- Если в области поиска больше нет объектов, то поиск оказывается неудачным.
Примечание 6: http://en.wikipedia.org/wiki/Bloom_filter
Кажется, что этот новый процесс более сложный. Но это не совсем так, и он намного более быстрый. Значительно сокращается количество сравнений, которые нам на самом деле нужно выполнить. Только фильтр Блума обычно отфильтровывает 80% или более (во многих случаях — более 90%) всех поисковых ситуаций. То есть, даже в случае, когда хэш-цепочки длинные, работа не выполняется, поскольку Блум фильтр помогает определить, что соответствие найдено не будет. Это делается с помощью одного обращения к сигнальной памяти.
Во-вторых, сравнение хэш-значения с хэш-значением элемента таблицы символов позволяет, кроме того, еще и не выполнять сравнение строк. В каждой хэш-цепочке могут быть записи с разными хэш-значениями, и это простое сравнение слов может отфильтровать много дубликатов. Ситуации, когда в хэш-цепочке две записи имеют одинаковые хэш-значения, случаются редко, что означает, что неудачные сравнения строк редки. Вероятность этого также увеличивается благодаря использованию различных хэш-функций, что определено в оригинальной спецификации ELF. Новая функция намного лучше распределяет значения по всему диапазону значений 32-битных чисел.
Хеш-цепочка организована так, чтобы все записи для одной и той же хэш-группы следовали одна за другой. Нет связанного списка и, следовательно, кэш-память будет использоваться намного лучше.
Нам нужен доступ к самой таблице символов только в случае, когда использование Блум фильтра и и проверки хэш-функции оказались успешными. Все записи таблицы символов для хэш-цепочки также располагаются последовательно, так что в случае, когда нам нужно получить доступ к более чем одной записи, нам и здесь также поможет предварительная загрузка в кэш-память процессора.
Одно из последних изменений в сравнении со старым форматом состоит в том, что в хэш-таблице хранится всего лишь несколько необходимых записей для неопределенного символа. Большинство неопределенных символов не должны присутствовать в хэш-таблице. В результате этого в некоторых случаях значительно уменьшается возможность возникновения хэш-коллизий, что, безусловно, повышает вероятность успешного применения Блум фильтра и уменьшает среднюю длину хэш-цепочки. Результатом будет значительное увеличение на 50% и более скорости работы кода, который может быть независимым от предварительной компоновки [7] (предварительно скомпонованный код работает всегда быстрее).
Однако, это не означает, что методики оптимизации, описанных в предыдущем разделе, лишены смысла. Их по-прежнему следует широко применять. Использование реализации новой хэш-таблицы просто означает, что если для экспортируемых символов и символов ссылок оптимизация не применяется, то это не должно сильно сказываться на производительности, так как это было раньше.
Новый формат был введен в Fedora Core 6. Когда указывается параметр --hash-style=gnu, то вся ОС, кроме нескольких преднамеренных исключений, создается без поддержки совместимости хэш-таблиц. Это означает, что двоичные файлы не могут быть использованы в системах, в которых в динамическом компоновщике не поддерживается новый формат хэш-таблиц. Поскольку такое решение никогда не ставилось в качестве цели для какой-либо из реализаций ОС, принять такое решение было не просто. В результате все двоичные файлы меньше, чем при наличии второго набора хэш-таблиц, а во многих случаях даже меньше, чем двоичные файлы, использующие только старый формат.
Возвращаясь к примеру с OpenOffice.org, мы можем дать некоторые оценки увеличения скорости. Если Блум фильтр способен отфильтровать не менее 80% от всего числа проверок, а вероятность дублирования хэш-значений равна максимум 15% у, мы, на самом деле, должны сравнивать в среднем 72 × 0,2 × 0,15 × 1,1931 = 2,58 строк. Этот показатель лучше в 33 раза. Если к этому добавить улучшенную работу с памятью за счет аккуратного использования кэш-памяти процессора, то у нас будет даже больший выигрыш. В реальных примерах мы сможем снизить затраты на поиск так, что программы будут запускаться быстрее на 50% и более.
| Предыдущий раздел: | Следующий раздел: | |
| Назад | Оглавление | Вперед |