Введение

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

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

В исходной параллельной версии хэширования в классиках авторы решили реализовать безблокировочное содержит и вместо этого просто блокировать во время операций insert и remove.

Мы решили внести свой вклад в растущий объем работ, посвященных различным парадигмам синхронизации, изучив добавление блокировок чтения-записи. Мы определяем вызовы contains как операции чтения, а вызовы insert или remove — как операции записи. Блокировка чтения-записи обозначает два типа блокировок: блокировки чтения и блокировки записи. Эти блокировки допускают неограниченное количество одновременных считывателей, но ограничивают каждый сегмент наличием одного писателя. Более того, когда этот модуль записи изменяет таблицу, все другие модули чтения и записи будут заблокированы до тех пор, пока этот модуль записи не завершит работу.

Мотивация:

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

Используя блокировку чтения-записи, любое количество одновременных вызовов contains может выполняться без блокировки, но в случае одновременных вызовов contains и insert или remove больше не существует потенциально неограниченного ожидания вызовов contains. Таким образом, в типичном рабочем процессе мы ожидаем, что блокировка чтения-записи будет работать аналогично исходной реализации, но лучше в примере, подробно описанном выше. Далее следует последовательность экспериментов, в которых исследуется реализация блокировки чтения-записи в сравнении с исходной реализацией.

Что мы сделали

Для нашей параллельной реализации хеш-таблицы в классическом стиле мы использовали выделение массива сегментов, выровненное по кешу. Это позволило нам не только искать в строке кэша, но и перемещаться по таблице во время линейного зондирования. Мы инициализировали сегменты как массив блокировок, соответствующих определенным диапазонам сегментов. Для нашей реализации блокировки чтения-записи мы использовали std::shared_timed_mutex, чтобы операции contains могли выполняться одновременно. Наша функция displaceFreeRange использует дельта-метод для обхода сегментов.

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

Известные проблемы с нашей реализацией включают в себя:

  1. Иногда возможно, но с вероятностью ‹ 1%, что следующая дельта для корзины может быть установлена ​​на 0, это приводит к бесконечному циклу операции. Мы решили закрыть такую ​​таблицу и потребовать, чтобы пользователь вместо этого повторно вставлял все значения с совершенно новой хэш-функцией.
  2. Изменить размер еще предстоит реализовать.

Ограничения оригинальной бумаги

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

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

Самая серьезная проблема, которую мы обнаружили, заключалась в том, что displaceFreeRange никогда не был полностью реализован в общедоступном исходном коде. Код на их собственном веб-сайте выполняет линейный поиск только вперед и назад в пределах диапазона переходов домашней корзины, чтобы найти пустой слот. Это было прискорбно видеть, поскольку новый механизм «скачков» не был общедоступен. Кроме того, были некоторые крайние случаи в общедоступных, которые не были устранены. Например, в addKeyEndList крайний случай обработки вставки первого элемента в домашнюю корзину не рассматривается. Кроме того, в то время как наша реализация увеличивает временную метку для сегментов обоих элементов, заменяемых во время переключения в классики, их реализация увеличивает временную метку только одного. В целом, были различные несоответствия внутри и между их кодом, псевдокодом и алгоритмом, описанным на английском языке, что особенно усложняло написание нашей собственной хеш-таблицы в классиках.

Эксперименты

Чтобы эмпирически изучить различия в производительности между реализацией блокировки чтения-записи и исходной реализацией contains без блокировки, мы проведем следующие четыре эксперимента:

  1. Эталонное тестирование. Измерьте среднее время выполнения каждого типа операций в моделируемом реалистичном рабочем процессе.
  2. Сегментный анализ. Измерьте среднее количество различных сегментов, посещенных во время операции.
  3. Анализ кеша. Измерьте среднее количество посещенных строк кеша и среднее количество промахов кеша во время операции.
  4. Анализ мотивирующего примера: измерьте среднее количество раз, когда вызов contains без блокировки должен зацикливаться из-за обновления метки времени в рамках вредоносного рабочего процесса.

Сравнительное тестирование

Благодаря эталонному тестированию мы можем получить общее представление о конкретных различиях в производительности между двумя реализациями, которые затем исследуются в последующих экспериментах. Анализ сегментов основан на том факте, что, как и в исходной статье, мы блокируем только сегмент, содержащий домашнюю корзину, во время вызовов insert и remove. Хотя вполне вероятно пересечение границы сегмента и, следовательно, необходимость блокировки нескольких сегментов, чтобы полностью предотвратить условия гонки, мы делаем упрощающее предположение, что на практике подавляющее большинство операций insert и remove звонки посещают только один сегмент, что подтверждается экспериментом с сегментами. Учитывая, что авторы оригинальной статьи утверждают, что основным источником производительности хеширования в классиках является его локальность кэша, мы проводим анализ кэша, чтобы (1) эмпирически сравнить количество промахов в кэше между хешированием в классиках и другими реализациями хеш-таблиц с найти доказательства за или против качественного утверждения авторов и (2) определить, проливает ли разница в локальности кэша между реализацией чтения-записи и исходной реализацией различия во времени выполнения между ними. Наконец, для четвертого эксперимента мы сначала разрабатываем вредоносный рабочий процесс методом проб и ошибок, а затем измеряем, сколько раз contains должен зацикливаться, чтобы проверить, соответствует ли наша гипотеза, что contains на самом деле может зацикливаться на неопределенный срок на самом деле встречается на практике.

Все эксперименты выполняются с использованием набора параллельных тестов, созданного на основе набора тестов с последовательной хэш-таблицей из набора задач 5, в котором указано количество потоков, емкость таблицы, размер сегмента, диапазон переходов и доля содержит/. Можно указать вызовы insert/remove. Тестирование проводится на станфордских мифологических машинах. Как описано Херлихи и др., реалистичный рабочий процесс хеш-таблицы в основном состоит из вызовов contains, поэтому мы определяем стандартный рабочий процесс: емкость 2¹⁵, 16 потоков, 16 сегментов, диапазон переходов 32 сегмента, 64 сегмента. -байтовая строка кэша, 500 испытаний, 1000 операций на поток за испытание, 90 % вызовов содержит, 5 % вызовов insert и 5 % удаления звонки.

Для эксперимента по эталонному тестированию мы сравниваем время выполнения двух реализаций для каждого типа операций, а также варьируем начальный коэффициент загрузки от 0,15 до 0,85. Мы повторно инициализируем новую хэш-таблицу, случайным образом рисуем новую хеш-функцию из семейства хэшей и заполняем таблицу указанным коэффициентом загрузки для каждого испытания, чтобы обеспечить случайность. Результаты этого эксперимента представлены на следующих графиках, где insert и contains определяются как успешные, если ключ еще не находится в таблице и удаляется считается успешным, если ключ уже находится в таблице:

Несмотря на более строгую синхронизацию, требующую, чтобы contains получала блокировку чтения-записи, кажется, что реализация чтения-записи в целом быстрее. Успешная вставка, успешное удаление и неудачное удаление выполняются немного медленнее в реализации чтения-записи, что имеет смысл, поскольку существует дополнительная конкуренция с содержит вызовы, которые не существовали, когда содержит не блокировался. Интересно, однако, что сбой insert выполняется быстрее в реализации чтения-записи. Было неясно, действительно ли contains будет работать быстрее в реализации чтения-записи, поскольку, с одной стороны, contains теперь работает без голодания, а с другой стороны, есть накладные расходы. возникает из-за требования contains для получения блокировки. Графики выше показывают, что содержит быстрее в реализации чтения-записи, возможно, из-за отсутствия голодания или оптимизированной производительности std::shared_timed_mutex по сравнению с std ::mutex, используемый в исходной реализации для insert и remove.

Сегментный анализ:

Как указано выше, исходный документ блокирует только сегмент, содержащий домашнее ведро, во время вызовов insert и remove. Первоначально мы полагали, что эта схема блокировки будет неполной, поскольку она будет игнорировать вероятность того, что вызовы insert или remove пересекают границу сегмента (вместо этого мы предположили, что удержание блокировки нескольких сегментов требуется для полного предотвращения состояния гонки). Чтобы проверить их первоначальную гипотезу, мы инициализировали хеш-таблицу с различными коэффициентами нагрузки и подсчитали среднее количество сегментов, которые посетила каждая операция. Мы выбираем усреднение по случайным вызовам (которые включают как успешные, так и неудачные операции), поскольку благодаря конструкции хеш-таблицы мы гарантируем, что операции contains и remove найдут результат в пределах диапазон хмеля домашнего ведра. Во всех случаях это будет максимум 2 сегмента.

Наши результаты эксперимента с сегментами подтвердили это упрощающее предположение, поскольку мы видим, что подавляющее большинство операций посещают только один сегмент. Оглядываясь назад, мы видим, что это должно быть так, поскольку во всей таблице всего 16 сегментов, и, таким образом, один сегмент охватывает большое количество сегментов, что повышает вероятность того, что каждая операция будет содержаться в одном сегменте. Даже при высоких коэффициентах загрузки, таких как 0,85, более 99 % вызовов insert посещают только один сегмент. Мотивация использования только 16 сегментов заключается как в уменьшении накладных расходов на метаданные, необходимых для блокировки, так и в том факте, что на практике java.concurr.utils допускает использование только 16 сегментов. Наконец, как и ожидалось, добавление блокировки чтения-записи в параллельную хеш-таблицу не влияет на среднее количество посещенных сегментов.

Анализ кэша:

Поскольку хеширование в классическом стиле известно своей превосходной локальностью кеша, мы решили протестировать процент промахов кеша как для стандартной блокировки, так и для версии таблицы с блокировкой чтения-записи. Мы измерили частоту промахов кеша с помощью инструмента perf. Мы рассчитали средний процент промахов кеша стандартного рабочего процесса по 2500 испытаниям. Для стандартной заблокированной таблицы процент промахов кэша составил 14,78 %, тогда как для таблицы, заблокированной для чтения и записи, этот процент составил 3,99 %. Более высокий процент промахов кэша для стандартной схемы блокировки может объяснить увеличение времени выполнения, наблюдаемое в эксперименте времени выполнения.

Анализ мотивирующего примера:

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

Среди параметров, которые мы настроили, были следующие:

  1. Доля вызовов contains, insert и remove
  2. Количество сегментов
  3. Используемая хэш-функция
  4. Количество потоков
  5. Размер диапазона переходов (окрестность)

Константы в экспериментальной установке были следующие:

  1. 500 испытаний
  2. 1000 операций на поток
  3. Количество ковшей 2¹⁵

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

Мы начали с гипотезы о том, что стандартные параллельные безблокировочные contains будут хорошо работать для рабочих процессов с небольшим количеством вызовов insert/remove, но с большинством содержит вызовы, он менее оптимален для рабочих процессов с большим количеством одновременных вызовов insert/remove, которые блокируют вызовы содержит и вызвать зацикливание. Таким образом, мы проанализировали среднее значение и стандартное отклонение циклов contains без блокировки для 5 различных рабочих процессов. Каждый из этих рабочих процессов имел 16 потоков на пробу, 16 сегментов на таблицу и начальный коэффициент загрузки 0,40.

Мы заметили, что подавляющее большинство (99+%) вызовов contains зацикливаются только один раз, но между рабочими процессами есть различия, особенно в проценте вызовов contains, которые зацикливаются. . Примечательно, что первые два рабочих процесса с наибольшим количеством операций «записи» имеют немного более высокое среднее значение и стандартное отклонение, в то время как последний рабочий процесс, в котором большинство рабочих процессов содержит, имеет одно из самых низких значений среднего и Стандартное отклонение. Кроме того, в рабочем процессе с равномерно распределенными вызовами contains/insert/remove был самый высокий процент вызовов contains, которые зацикленный. Стоит отметить, что из вызовов contains, которые зацикливались более одного раза, менее 0,1 % зацикливались более двух раз, если вообще были. Несмотря на то, что различия незначительны, учитывая огромное количество выполняемых операций, нам было предложено взять один из этих рабочих процессов и двигаться дальше, исследуя изменения в других параметрах.

Еще одна гипотеза, которая у нас была, заключалась в том, что уменьшение количества сегментов ухудшит производительность contains без блокировки и увеличит среднее значение, стандартное отклонение и процентную долю вызовов contains, зацикленных еще больше. чем один раз. Причина этого в том, что алгоритм использует блокировки на уровне сегментов, поэтому меньшее количество сегментов приводит к блокировке больших областей таблицы, что увеличивает вероятность того, что вызов contains должен ждать. Например, для приведенного выше рабочего процесса 33% содержит, 33% вставляет, 33% удаляет, уменьшая количество сегментов с 16 до 1 и сохранение всех остальных параметров постоянными дало нам следующие результаты:

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

Затем мы перешли к изучению влияния производительности хеш-функции на количество циклов в contains. Мы предположили, что чем слабее хеш-функция, то есть чем менее равномерно она распределяет значения, тем больше циклов contains придется выполнять. Следующие результаты относятся к рабочему процессу, состоящему из 10 % содержит, 45 % вставляет, 45 % удаляет с 16 потоками на испытание, 16 сегментами на таблицу. , и начальный коэффициент нагрузки 0,40.

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

Теперь мы перешли к изучению влияния количества потоков на производительность contains. Мы подумали, что увеличение количества потоков может усилить конкуренцию за блокировки и увеличить показатели того, как долго contains будет ждать/зацикливаться. Мы протестировали 33% содержит, 33% вставить, 33% удалить рабочий процесс с 16 сегментами и начальным коэффициентом загрузки 0,40 с 2 потоками, 16 потоков и 128 потоков, регулируя количество операций на поток таким образом, чтобы общее количество операций, выполненных во всех потоках, составляло 16 000 для каждого эксперимента.

Каждый из этих рабочих процессов имел 16 потоков на пробу, 16 сегментов на таблицу и начальный коэффициент загрузки 0,40. Мы обнаружили, что различия в показателях были намного меньше, чем ожидалось. Например, разница в средствах была порядка 1e-3. Гораздо более важным фактором является количество сегментов, которое авторы устанавливают равным количеству потоков, а не только количеству потоков.

Наконец, мы исследовали изменение диапазона переходов (размера окрестности). Мы предположили, что увеличение диапазона переходов может увеличить скорость вызовов insert (поскольку требуется меньше операций перестановки, чтобы переместить элемент в окрестности его исходного сегмента) и, таким образом, уменьшить количество циклов для contains. . Однако, опять же, разница была очень небольшой. Возьмем пример рабочего процесса с 10% содержит, 45% вставляет, 45% удаляет с 16 потоками на испытание, 16 сегментами на таблицу, и начальный коэффициент нагрузки 0,40. Для диапазона прыжков 1024 среднее значение, стандартное отклонение и процентные значения составляли 1,007, 0,085 и 0,731% соответственно, тогда как при стандартном диапазоне прыжков 32 среднее значение и стандартное отклонение составляли 1,005, 0,073 и 0,520% соответственно. .

Наконец, из всех проведенных нами экспериментов мы не смогли наблюдать экземпляр, в котором содержит зацикливается 4 или более раз. Одной из основных причин этого является просто скорость, с которой работает contains — для диапазона переходов 32 мы проверяем не более 32 индексов, поэтому маловероятно, что эта операция не может быть выполнена. потому что он снова и снова блокируется вызовами записи. Тем не менее, было приятно видеть некоторые заметные различия, особенно в процентном соотношении вызовов contains для этого цикла, при изменении пропорций рабочего процесса, количества сегментов и хэш-функции.

Цель этого эксперимента заключалась в наблюдении за пересечением теории и практики: хотя в теории блокировка чтения-записи является улучшением, поскольку вызовы contains избавляются от голодания, на практике очень мало случаев, когда contains вообще блокируется, и еще меньше случаев, когда contains блокируется более двух раз. Наша реализация блокировки чтения-записи ограничивает вызовы contains и повышает приоритет contains, в то время как существующий механизм блокировки теоретически имел неограниченные вызовы contains и помещался последними. приоритет содержит.

Заключительные выводы и следующие шаги:

Наша основная проблема при выполнении этого проекта заключалась в том, что у нас не было надежной базовой реализации, от которой можно было бы отталкиваться, в результате чего нам пришлось кодировать некоторые из наиболее сложных операций, таких как параллельный displaceFreeRange, полностью с нуля. Несмотря на это, мы смогли получить ряд интересных результатов, например тот факт, что, хотя contains без блокировок теоретически не является свободным от голодания, невероятно сложно заставить его зацикливаться несколько раз, так что на практике это эффективно без голода. Интересно, что наша реализация блокировки чтения-записи по-прежнему превосходит исходную реализацию, но результаты нашего анализа кеша показывают, что эта производительность, вероятно, связана с оптимизацией количества промахов кеша в реализации std::shared_timed_mutex , а не чем содержит, не нужно зацикливаться несколько раз, как предполагалось. Если бы у нас было больше времени, мы хотели бы изучить другие схемы блокировки, такие как исключение блокировки, или потенциально попытаться получить прирост производительности через другой канал, например, исследовать локальность кэша, а не синхронизацию.

Использованная литература:

  1. А. А. Пазников, В. А. Смирнов и А. Р. Омельниченко, «На пути к эффективной реализации параллельных хеш-таблиц и деревьев поиска на основе транзакционной памяти программного обеспечения, Международная мультиконференция по промышленному инжинирингу и современным технологиям (FarEastCon) 2019 г., Владивосток, Россия, 2019. С. 1–5. doi: 10.1109/FarEastCon.2019.8934131.»
  2. Боуэн Альперн и Фред Б. Шнайдер. 1986.Признавая безопасность и живучесть. Технический отчет. Корнельский университет, США.
  3. «Хеширование в классики». RSS Code Capsule, codecapsule.com/2013/08/11/hopscotch-hashing/?fbclid=IwAR3YqU5qx3O9M4TnOLk7SNi57bJcvKtjIrUC6Jfmo4bM3RuV70fUR8m-47o#ref.
  4. Келли, Роберт М. и др. «Хеширование классиков без блокировки. ArXiv abs/1911.03028 (2020): н. стр.»
  5. Келли, Роберт и Перлмуттер, Барак и Магуайр, Фил. (2018). Параллельное хеширование Робин Гуда.
  6. М. Херлихи, Н. Шавит и М. Цафрир. Классическое хеширование. В DISC '08: Материалы 22-го международного симпозиума по распределенным вычислениям, стр. 350–364, Берлин, Гейдельберг, 2008 г. Springer-Verlag. doi: 10.1007/978–3–540–87779–0\_24.
  7. «Хеширование Робин Гуда». Робин Гуд Хэширование | Programming.Guide,programming.guide/robin-hood-hashing.html.

Авторы:

Сидхика Балачандар, Мишель Бао, Самакш Гоял, Дэниел Майкл

Спасибо Киту Шварцу и Антону де Леону за руководство этим проектом и за отличную четверть CS166!