Хэш-таблицы чрезвычайно активно используются в ядре Linux, чтобы увеличить скорость доступа к различным объектам. Хэш-таблицы намного увеличивают скорость доступа по сравнению с обычным линейным поиском. Но всегда остаётся возможность для оптимизации. В последние годы немало сделано для этого. В частности, реализован метод read-copy-update (RCU), позволяющий добавлять и удалять ячейки из хэш-таблицы без блокировки доступа к ней.

Ещё один метод улучшения производительности — изменение размера хэш-таблицы. Скорость поиска объекта напрямую зависит от размера таблицы. Поэтому, если у нас есть большая таблица с малым количеством элементов, то мы впустую расходуем память и жертвуем производительностью. Но ничего не поделаешь: ядро Linux до сих пор не позволяло изменить размер таблицы после её первоначального создания.

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

Уникальная особенность релятивистских хэш-таблиц — изменение размера без блокировки доступа к ним. В процессе многоступенчатого перестроения таблицы (сжатия или расширения) сохраняется совместный доступ ко всем ячейкам. Название «релятивистский» объясняется тем, что при совместном доступе разные CPU «видят» разное состояние хэш-таблицы, которая в этот момент осуществляет своё перестроение.

Прошло три года, и в ядре Linux 3.17 наконец-то появятся релятивистские хэш-таблицы. Разработчик Томас Граф (Thomas Graf) предложил патч для сетевой подсистемы управления сокетами netlink. Это только начало. Поскольку соответствующий алгоритм уже проник в ядро Linux, то в будущем его можно использовать для управления и другими хэш-таблицами. Всё это позволит высвободить память и увеличить производительность ядра Linux.

Что ж, лучше поздно, чем никогда.

Алгоритм сжатия таблицы

003

Алгоритм расширения таблицы

004



4 комментария

  1. 26.09.2014 at 15:03

    А почему поздно? В других системах эти алгоритмы уже вовсю используются?

  2. 26.09.2014 at 15:50

    «ячейки из хэш-таблицу» — снова орфография.

  3. 28.09.2014 at 15:09

    Я к своему стыду ничего не понял из этой статьи. Может ли кто-нибудь мне доходчиво объяснить профит от этих особых таблиц? Ну вот появились они и работают. Что дальше? Линукс станет на 0.15% быстрее? Новый виток развития поисковых систем всех мастей? Может в космос можно будет полететь?

    • 29.09.2014 at 10:09

      Ну, например, хэш-таблицы используются в некоторых файловых системах, соотвественно, ускорение работы с ними приведёт к увеличению быстродействия этих FS. Вообще же, хэш-таблицы используют практически везде, где обрабатываются текстовые данные, в том же bash. Учитывая заточенность Линукса на повсеместное использование скриптов, какой-никакой выигрыш должен быть.

Оставить мнение