Ссылка на файл: >>>>>> http://file-portal.ru/Методы борьбы м коллизиями в хеш таблицах/
Универсальное хеширование
Методы разрешения коллизий
Хеширование
В конце концов я должен был к этому прийти. Теперь я завершил работу над самой быстрой хеш-таблицей. И под этим я подразумеваю, что реализовал самый быстрый поиск по сравнению со всеми хеш-таблицами, какие мне только удалось найти. При этом операции вставки и удаления также работают очень быстро хотя и не быстрее конкурентов. Я использовал хеширование по алгоритму Robin Hood с ограничением максимального количества наборов. Если элемент должен быть на расстоянии больше Х позиций от своей идеальной позиции, то увеличиваем таблицу и надеемся, что в этом случае каждый элемент сможет быть ближе к своей желаемой позиции. Похоже, такой подход действительно хорошо работает. Величина Х может быть относительно невелика, что позволяет реализовать некоторые оптимизации внутреннего цикла поиска по хеш-таблице. Если вы хотите только попробовать её в работе, то можете скачать отсюда. Хотите подробностей — читайте дальше. Я считаю, что последний пункт — новинка в сфере хеш-таблиц. Это главная причина высокой производительности моего решения. Но сначала я хотел бы рассказать о предыдущих пунктах. Открытая адресация означает, что хеш-таблица использует в качестве хранилища данных непрерывный массив. Это не аналог std:: Линейное размещение означает, что если вы пытаетесь вставить элемент в массив, а текущий слот уже заполнен, то вы просто переходите к следующему слоту. Если и он тоже заполнен, то берётся следующий слот, и так далее. У этого простого подхода есть известные недостатки, но я считаю, что они исправляются с помощью ограничения максимального количества наборов. Хеширование Robin Hood означает, что при линейном размещении вы пытаетесь расположить каждый элемент как можно ближе к его идеальной позиции. Это делается с помощью перемещения окружающих элементов при вставке или удалении какого-то элемента. Отсюда и взялось название Robin Hood. Богатым называется элемент, получивший слот поблизости от своей идеальной точки вставки insertion point. Бедный элемент находится далеко от идеальной точки вставки. Вставляя новый элемент, вы отсчитываете, насколько далеко он находится от идеальной позиции. Если дальше, чем текущий элемент, то вы ставите новый на место текущего, а затем уже для него пытаетесь найти новое место. Количество слотов — простое число: Это означает, что он может вырасти, например, с 5 слотов до 11, затем до 23, до 47 и так далее. Когда нужно найти точку вставки, то для присваивания слоту значения хеша элемента используется оператор по модулю modulo operator. Другой вариант — делать размер массива равным степени двойки. Ниже мы поговорим о том, почему по умолчанию я использую простые числа и когда целесообразно применять оба варианта. C основами разобрались, давайте теперь обсудим моё решение: Сначала идея была в том, чтобы сделать это количество очень небольшим, например равным 4. То есть при вставке я сначала пробую идеальный слот, если не получается — то обращаюсь к следующему, затем к следующему, затем к следующему, и если все они оказываются заполнены, то я увеличиваю таблицу и снова пытаюсь вставить элемент. Это прекрасно работает на маленьких таблицах. Но при вставке случайного значения в большую таблицу я всё время буду терпеть неудачу с этими четырьмя наборами, мне придётся увеличивать размер таблицы, даже если она по большей части пустая. Это при вставке случайного значения. А если вставлять последовательные значения, то можно заполнить таблицу целиком, и только тогда она будет перераспределена. Я сделал это для того, чтобы вы могли доверить таблице перераспределение, когда вы действительно увеличиваете её размер: У меня нет точной статистики, но я прогнал простой тест, в котором построил тысячи таблиц всевозможных размеров и заполнил их случайными числами. Так что вы можете доверять такому механизму: Без опаски ставьте вплоть до 0,9: Но не присваивайте значение 1,0: Например, все слоты, в которых хочет быть последний элемент, уже заняты, за исключением последнего пустого. Тогда вы вставляете элемент в первый слот, в котором он хочет находиться, но тот уже занят. Вам придётся переместить существующий элемент во второй слот, оттуда выселить элемент в третий, и так по цепочке до конца таблицы. В результате вы получите таблицу, в которой все элементы, за исключением самого первого, находятся в одном слоте от своих идеальных позиций. Поиск всё ещё будет выполняться быстро, но последняя вставка займёт много времени. Если же у вас окажется несколько свободных слотов поблизости, то вставляемый элемент передвинет не так много соседей. Благодаря этому ограничению можно реализовать тонкую оптимизацию: В моём случае таблица вырастет до , это ближайшее простое число. Двоичный логарифм округлённо равен 10, так что я ограничиваю количество наборов десятью. Но все остальные операции хеширования будут считать, что у нас всего слотов. Теперь, если два элемента хешируются в индекс , то я могу перейти в конец и вставить в индекс Мне не нужно проверять диапазон изменения индексов bounds checking , потому что ограничение количества наборов не даст мне выйти за индекс Если же у меня будет 11 элементов, которые хотят попасть в последний слот, то таблица увеличится и все эти элементы захешируются в разные слоты. Благодаря отсутствию граничной проверки у меня получаются компактные внутренние циклы. Вот как выглядит функция поиска:. По сути, это линейный поиск. Код прекрасно преобразуется в ассемблер. Такой подход лучше простого линейного размещения по двум причинам:. Мои накладные расходы по памяти — 1 байт на элемент. То есть при выравнивании типа alignment of the type вставляемого элемента будет плюсоваться padded out 1 байт. Так что если вы вставляете целочисленные значения, то 1 байт получит ещё 3 байта паддинга, в результате выйдет 4 байта накладных расходов на каждый элемент. Если вы вставляете указатели, то паддинг будет уже 7 байтов, получаем 8 байтов накладных расходов. Для решения этой проблемы я рассматриваю вариант с изменением схемы использования памяти, но опасаюсь, что тогда у меня на каждый поиск будет два промаха кеша cache misses вместо одного. Не так-то просто выяснить производительность хеш-таблиц. Как минимум нужно измерять скорость в таких ситуациях:. И каждую из этих ситуаций нужно прогонять с разными ключами и значениями разных размеров. В качестве ключа я использую целочисленное или строковое значение, а типы-значения размером 4, 32 и Предпочитаю целочисленные значения, потому что со строковыми вы по большей части измеряете накладные расходы хеш-функции и оператора сравнения, одинаковые для всех хеш-таблиц. Нужно тестировать поиск как при наличии элемента в таблице, так и при его отсутствии, потому что в этих случаях производительность может кардинально различаться. Например, я столкнулся с непростой ситуацией, когда вставил все числа от 0 до в google:: Неожиданно оказалось, что хеш-таблица работает в раз медленнее, чем обычно. Это крайний случай — использование степени двойки для задания размера таблицы. Вероятно, нужно было проводить измерения со случайными числами и с последовательными, но тогда получилось бы слишком много графиков. Так что я ограничусь только случайными числами, они избавляют от возникновения неудачных ситуаций с производительностью из-за специфических паттернов. Графики расположены довольно плотно. Как видите, второй вариант заметно быстрее, причину я объясню потом. К моему конфузу, она показала посредственные результаты… std:: Немного обсудим этот график. Ось Y — количество наносекунд, затраченных на поиск одного элемента. Я использовал Google Benchmark, который за полсекунды раз за разом вызывает функцию table. Общая длительность итераций делится на их количество, получаются наносекунды. Все искомые ключи присутствуют в таблице. Для оси Х я взял логарифмическую шкалу, потому что она хорошо описывает изменение производительности. К тому же такая шкала позволяет оценить производительность для таблиц разных размеров: Сразу бросается в глаза зубчатость графиков. Дело в том, что все таблицы имеют разную производительность в зависимости от текущего коэффициента заполнения load factor , то есть степени заполнения. Стоимость поиска растёт, и в какой-то момент таблица решает, что она заполнилась слишком сильно и пора перераспределяться, что снова приводит к ускорению поиска. Это было бы очевидно, если бы я вывел графики коэффициента заполнения для каждой таблицы. Были бы, но очень незначительно. Далее мы рассмотрим эту ситуацию более развёрнуто. На приведённом графике видно, что нижняя точка верхних графиков, когда таблицы только что перераспределились и имеют коэффициент заполнения чуть больше 0,5, расположена гораздо выше верхней точки нижних графиков прямо перед перераспределением, из-за того что их коэффициент заполнения приближается к 0,5. Также вы видите, что в левой части все графики относительно плоские. Причина в том, что таблицы полностью отправляются в кеш. Только когда данные перестают помещаться в кеше L3, графики заметно расходятся. Я считаю это большой проблемой. На мой взгляд, правая часть графиков гораздо точнее отражает ситуацию, чем левая: Поэтому я попытался придумать тест, который показал бы скорость работы таблицы, не находящейся в кеше. Я создал столько таблиц, чтобы они не помещались в L3, и использовал разные таблицы для каждого искомого элемента. Допустим, я хочу измерить скорость работы таблицы, содержащей 32 элемента по 8 байтов. Размер моего кеша L3 — 6 Мб, так что в него помещается примерно 25 тыс. Чтобы удостовериться, что таблицы в кеше отсутствуют, я создал их с запасом — 75 тыс. И каждый поиск выполнялся в отдельной таблице. Я убрал пару линий, потому что они были малоинформативны. Теперь у нас остались: В новом бенчмарке графики сразу начали сильно различаться. Паттерн, который проявился на графике первого бенчмарка, на графике второго бенчмарка стал заметен очень рано, начиная с 10 элементов. Зубчатость проявляется ещё сильнее, коэффициент заполнения играет заметную роль. Чем сильнее заполнена таблица, тем больше элементов приходится просматривать, прежде чем система решит, что элемент отсутствует. Но мне очень нравятся результаты моей таблицы: Моя таблица демонстрирует более стабильную производительность, чем другие. Эти графики убедили меня, что моя новая таблица — большой шаг вперёд. При этом моя таблица не уступает по скорости даже при использовании простых чисел для определения размера таблицы. Давайте поговорим об этом подробнее. Этап 1 может быть дёшев, если ключ — целое число: Но при ключах других типов, например строковых, этап будет дороже. Этап 3 — разыменование указателя. В случае с std:: Может показаться, что если у вас не слишком медленная хеш-функция, то этап 3 получается самым дорогим из всех. Но если у вас нет промахов кеша при каждом одиночном поиске, то, скорее всего, самым дорогим этапом окажется второй. Целое число по модулю обрабатывается медленно даже на мощном железе. Согласно данным Intel , это требует от 80 до 95 циклов. Это главная причина, по которой действительно быстрые хеш-таблицы обычно используют степень двойки для определения размера массива. Потому что потом вам будет достаточно убирать старшие биты, что можно делать в один цикл. Но у степени двойки есть большой недостаток: Вот график второго бенчмарка, но в этот раз я не использовал случайные числа:. Для этого достаточно было дать ей набор чисел по порядку: Если сделать это и поискать ключ, которого нет в таблице, то поиск будет крайне медленным. Если ключ есть, то всё нормально, работает быстро. При этом разница в производительности между удачным и неудачным поиском может достигать тысячи крат. Ещё один пример проблемы из-за степени двойки: Так что использование степени двойки может привести к неприятным сюрпризам. Так произошло, что моя таблица избежала всех этих проблем благодаря ограничению количества наборов. Не было даже ненужных перераспределений. Но это не означает, что моя таблица неуязвима для побочных эффектов использования степени двойки. Например, как-то я столкнулся с тем, что при вставке указателей в такую таблицу некоторые слоты постоянно пустовали. Из-за этого в таблице использовалась лишь одна шестнадцатая всех слотов. Вы можете столкнуться с той же проблемой при использовании степени двойки в моей хеш-таблице. Все эти проблемы решаемы, если вы позаботитесь о выборе хеш-функции, которая подходит для вводимых вами данных. Но это не слишком удобно: Иногда с этим нет проблем, но иногда не хочется заморачиваться. Хочется, чтобы просто работало, и без неожиданных тормозов. Поэтому я решил в своей таблице по умолчанию использовать размер на основе простых чисел а степень двойки задаётся опционально. Почему с простыми числами нет проблем? Не могу объяснить с точки зрения математики, но интуиция подсказывает, что у них нет общих делителей с другими числами, всегда будут разные остатки. Допустим, я использую степень двойки, в моей таблице 32 слота, и я пытаюсь вставить указатели с байтным выравниванием то есть все мои числа кратны Теперь при поиске слота в таблице с помощью целого числа по модулю я получу только два возможных слота: Поскольку 32 кратно 16, вы просто не можете получить других значений. Если же взять размер на основе простого числа, то этой проблемы не возникнет. Допустим, у меня 37 слотов, тогда при всех делениях с кратностью 16 я смогу использовать все 37 слотов. Как можно решить проблему низкой производительности вычисления целого числа по модулю? Я позаимствовал трюк из boost:: Я не разрешаю брать в качестве размера таблицы любые возможные простые числа. Я сделал специальную подборку чисел, которая и применяется при увеличении таблиц. Также я сохраняю индекс числа из вашей таблицы. Когда для присвоения слоту хеш-значения нужно вычислить целое число по модулю, выполняется вот что:. Каждый из вариантов — целое число по модулю на основе статической константы. Если использовать константу, то компилятор применит кучу оптимизаций для ускорения вычисления. Для каждого из вариантов вы получаете кастомный ассемблерный код, который будет работать гораздо быстрее, чем целое число по модулю. Выглядит несколько безумно, но даёт огромный прирост скорости. Вы можете наблюдать разницу на вышеприведённом графике: Конечно, это не панацея. Если вас сильно это беспокоит, то можете прибегнуть к std:: Однако дело в том, что при использовании степени двойки риск куда выше, и приходится проявлять осторожность. В случае же с простыми числами вы нарвётесь на проблему, только если специально создадите ключи с подвохом. Это подводит нас к вопросу о безопасности. На хеш-таблицу можно провести умную атаку с помощью ключей, которые все конфликтуют друг с другом. Если вы знаете, что веб-сайт использует во внутренних кешах хеш-таблицу, то можете составить такие запросы к сайту, которые все будут конфликтовать в этой таблице. Таким образом можно сильно замедлить работу внутреннего кеша веб-сервера с вероятностью положить сайт. Надо сказать, что настройка максимального количества наборов в моей таблице не даёт злоумышленникам заполнить её плохими ключами. Но тут возникает новый источник угрозы: Это приведёт к исчерпанию памяти на сервере. Уязвимость закрывается с помощью кастомной хеш-функции, но я не буду советовать, что вам искать. Могу лишь сказать, что если используете хеш-таблицу в окружении, где пользователи могут вставлять ключи, то откажитесь от std:: С другой стороны, если вы не думаете, что среди ваших пользователей будут злоумышленники, то спокойно используйте мою таблицу в версии с простыми числами. Но, допустим, вы знаете, что ваша хеш-функция возвращает хорошо распределённые числа, и у вас редко могут возникать коллизии даже при использовании степени двойки. Тогда пускайте в дело вторую версию моей таблицы. Я решил поместить эту настройку в объект, потому что именно здесь можно выяснить качество возвращаемых ключей. Если в данном случае вам подходит std:: В любом случае вы можете получить ещё более быструю хеш-таблицу, если знаете, что у вас будет мало коллизий. После такого отвлечения на теорию давайте вернёмся обратно к производительности моей таблицы. Ниже приведён график, на котором отражена производительность при вставке элемента. Я измерял, сколько времени уходит на вставку N элементов, и делил время на их количество. График отражает скорость работы таблицы без вызова reserve перед вставкой элемента:. Зубцы ярко выражены, но направлены в другую сторону. Средняя стоимость подскакивает каждый раз, когда нужно перераспределить таблицу. Затем она снижается, пока снова не приходит время перераспределять. Опять же, в левой части графика отражена ситуация, когда таблицы целиком умещаются в кеш L3. В этот раз я решил не писать текст с инициализацией промаха кеша, потому что это требует времени, да к тому же мы уже знаем, что правая часть графика — хорошая аппроксимация для промаха. В этом бенчмарке google:: Она просто ищет пустой слот и вставляет туда элемент. Это компромисс между стоимостью вставки и скоростью поиска. Но я рад, что у меня небольшое падение производительности. Не знаю, что происходит в конце с контейнерами на базе узлов. Интересно было бы разобраться, но я этого не сделал. Подозреваю, что дело в вызове malloc в моей стандартной библиотеке Linux gcc. Во время измерений для этого и других графиков я столкнулся с несколькими проблемами, потому что некоторые операции по непонятным причинам занимали много времени. Но в целом график выглядит аналогичным предыдущему, за исключением меньшей зубчатости из-за того, что reserve избавляет от необходимости перераспределять. Моя таблица выполняет вставку быстро, но не так, как google:: Теперь посмотрим, сколько времени уходит на удаление элементов. Для этого я построил массив из N элементов и замерил длительность удаления каждого из них в случайном порядке. Затем поделил общее время на N:. Контейнеры на базе узлов снова показали плохие результаты, остальные идут ноздря в ноздрю. В целом обе работают очень быстро. Но между ними есть одно большое различие: Оно будет убрано только в том случае, если вы вставили в слот новый элемент. При хешировании Robin Hood с его линейным размещением нет никаких трудностей с поиском элемента, который может занять опустевший слот: А при квадратичных наборах может потребоваться элемент, расположенный через четыре слота. И при его перемещении снова придётся решать проблему поиска узла для вставки в свежеосвободившийся слот. Они будут заменены при следующей операции вставки. Оценить это влияние довольно трудно, но мне кажется, что я нашёл подходящий тест: Сначала генерирую миллион случайных целых чисел. Затем вставляю их в хеш-таблицу, стираю, снова вставляю. Причём делаю это в случайном порядке. Скажем, у меня есть только четыре числа: Каждый элемент вставляется, стирается и снова вставляется, но в случайном порядке. На графике показана длительность вставки одного элемента в зависимости от общего количества вставок. Первая контрольная точка — просто вставка миллиона элементов. Вторая — вставка миллиона элементов, их удаление и снова вставка в случайном порядке. Третья контрольная точка — вставка, удаление, вставка, удаление, вставка. То есть всего три вставки. На второй контрольной точке моя таблица её догнала, а на третьей — обогнала. После 6 миллионов вставок версия моей таблицы с простыми числами даже вышла на второе место. Мои таблицы становились всё быстрее, потому что чем больше удалений, тем ниже должен быть коэффициент заполнения. Если достаточно часто вставлять и удалять миллион элементов, то в таблице постоянно будет одномоментно находиться около тыс. И чем дольше прогонять цикл вставка-удаление-вставка, тем ниже будет средняя одномоментная заполненность. Эта таблица работает гораздо быстрее любых других контейнеров на базе узлов. Но всё же линейное размещение Robin Hood обеспечивает более элегантный способ удаления элементов: Это будет преимуществом для страниц, где часто приходится удалять и вставлять элементы. Давайте посмотрим, как можно решить проблему использования таблицами std:: А затем провёл замеры перед самыми перераспределениями таблиц. Если вернётесь к самому первому графику, то представьте, что я просто соединил прямыми линиями пики зубцов. Но всё же главной задачей этого бенчмарка было сравнение boost:: Как видите, при одинаковом значении flat-таблицы работают быстрее. Результат ожидаемый, но я считаю, что его нужно было подтвердить экспериментально. По ощущениям, это наиболее честный тест производительности хеш-таблиц, потому что здесь они сконфигурированы одинаково и имеют одинаковый коэффициент заполнения. И в тех же реальных ситуациях вы будете наблюдать зубчатый график производительности, как на первой иллюстрации, когда одинаковые таблицы работают по-разному в зависимости от количества коллизий. И коэффициент заполнения — лишь один из факторов. Также этот график скрывает одно из преимуществ моей таблицы: До сих пор я измерял производительность при сопоставлении целочисленного ключа и целочисленного значения map from int to int. Но при разных ключах или более крупных значениях результаты могут быть иными. Для начала — вот графики удачных и неудачных поисков при использовании в качестве ключей строковых значений:. Это версия графика для таблиц, которые помещаются в кеш. Как видите, использование строковых значений лишь незначительно приподняло графики. Это было ожидаемо, потому что основные затраты связаны с изменением хеш-функции и более дорогим сравнением. Взглянем на неудачные поиски:. Я использовал, соответственно, std:: Но это означает, что таблица должна сравнить строковые значения, чтобы увидеть, что слот пуст. Все остальные таблицы для этого сравнивают целочисленные значения. Тем не менее если нам нужно сравнить лишь одиночные символы, то сравнение строковых значений остаётся недорогим. И действительно, накладные расходы не так уж велики. Они только выглядят такими на предыдущем графике, потому что при каждом поиске у нас было попадание в кеш. А вот при промахах кеша ситуация иная:. Я не выяснял причину. Затем я поиграл с размером значения. А если у меня сопоставлены не целочисленные ключ и значение map from int to int , а целочисленный ключ и байтная структура? Или целочисленный ключ и байтная структура? Причина в том, что при неудачном поиске приходится выполнять максимальное количество поисков, а при таком огромном типе-значении ваш prefetcher должен работать очень напряжённо. Моя таблица ещё удерживается в лидерах, но при байтах превращается в контейнер на базе узлов. Графики для всех остальных поисков выглядят одинаково, потому что в случае с контейнерами на базе узлов вам не нужно беспокоиться о размере значения: В случае с flat-контейнерами можно ожидать увеличения количества промахов кеша. Чаще всего выполняется только один поиск: Два обхода набора тоже бывают довольно часто, но три — уже редко. В моей таблице поиск выполняется линейно, потому что при линейном поиске процессоры прекрасно делают предварительную выборку prefetch следующего элемента вне зависимости от его размера. Так что процедуры поиска по большей части не зависят от размера типа size of the type , хотя графики вставок и удалений сильно отличаются. Вот график вставки с использованием целочисленного ключа и байтной структуры в качестве значения:. Все линии немного поднялись, но больше всего это проявилось у flat-таблиц, зубчатость у них тоже стала ярко выраженной: Но на контейнеры на базе узлов это не влияет, и boost:: Давайте посмотрим, какая будет ситуация с байтной структурой:. В данном случае главную роль играет стоимость перераспределения. Тут есть одна странность: Причина в том, что эта таблица сначала распределяет 32 слота и заполняет их сконструированным по умолчанию типом-значением default constructed value type. А поскольку размер моего типа-значения — байта, то таблице приходится обнулять 32 килобайта данных. Вероятно, на вас это не повлияет, но я должен был объяснить странность графика. Я не разбирался с причиной, но предположу, что всё дело опять в заполнении каждого слота сконструированным по умолчанию типом-значением, так что перераспределение получается ещё дороже из-за необходимости инициализации слотов, даже тех, что никогда не будут использоваться. Если перераспределение дорого, то, чтобы его не делать, можно заранее вызывать применительно к контейнеру функцию reserve. Посмотрим, что будет, когда мы вставим те же элементы, но с предварительным вызовом reserve:. Сначала мой контейнер работает быстрее контейнеров на базе узлов, но в какой-то момент boost:: В бенчмарке можно потестировать поведение контейнеров при вставке таких больших значений, но в реальной жизни вы можете никогда с этим не столкнуться. Мои контейнеры остаются быстрее, пока не увеличиваются в размерах: С 16 элементами всё ещё работает быстро. Поскольку каждый элемент имеет размер байтов, то, когда контейнер становится больше 16 Мб, его скорость резко падает. Сначала я думал, что причина в случайном перераспределении из-за достижения ограничения по количеству наборов. Это было бы досадно, потому что выше я рассказывал о том, что вероятность такого события очень невелика. Но, к счастью, причина оказалась в другом: По какой-то причине именно в этой контрольной точке ОС начинает гораздо дольше предоставлять очищенные страницы памяти. Вас это может и не коснуться, в зависимости от диспетчера памяти и используемой ОС. Хотя это также означает, что речь идёт о единовременном росте стоимости. После увеличения контейнера вы уже не столкнётесь с этим пиком на графике. Если контейнер живёт долго, всплеск стоимости будет сглажен. Дело в том, что использованная мной версия этой таблицы поставляется с Ubuntu На этом графике мы будем по большей части сравнивать мою таблицу с контейнерами на базе узлов, и результат окажется не в пользу моей таблицы. Я снова виню более высокую стоимость перераспределения. Давайте попробуем сначала запускать reserve:. Честно говоря, я не знаю, какие тут можно сделать выводы. Здесь преобладает стоимость копирования строкового ключа, и все таблицы ведут себя схоже. При использовании строкового ключа с большим типом-значением мы будем наблюдать ту же картину:. Другие таблицы идут кучно в связи с ключевой ролью стоимости копирования. Контейнеры на базе узлов оказываются гораздо более конкурентными решениями при использовании больших типов, чем маленьких. Теперь измерим скорость удаления элементов. Я прогнал три теста для целочисленных ключей и три теста для строковых ключей: Выше был представлен график для 4-байтного значения. На 32 байтах результаты те же, так что я этот график не привожу. А с байтами ситуация такая:. Проблема всё та же: При этом его линия существенно поднялась, то есть на этой операции таблица оказалась почти такой же медленной, как и контейнеры на базе узлов. Графики удаления строковых ключей выглядят достаточно похожими на графики удаления целочисленных, так что нет смысла их показывать. Вот один из них:. Количество элементов я уменьшил до 10 тыс. К тому же при 10 тыс. Начнём с типа-значения размером 32 байта:. Причём с ростом размера значения разрыв между ними увеличивается. Вначале она проигрывает контейнерам на базе узлов, но со временем нагоняет их. Причина в том, что я не вызывал предварительно функцию reserve , поэтому при первой вставке таблица была вынуждена несколько раз перераспределиться. Для flat-контейнеров это очень дорого, а для контейнеров на базе узлов — дешевле. На самом деле я такого не ожидал, ведь даже с учётом резервирования моему контейнеру приходится перемещать больше элементов, что для байтов данных должно быть очень недёшево. Так что у меня есть лишь одно объяснение, почему мой контейнер оказался быстрее: Другие графики вставки строковых ключей выглядят очень похоже на предыдущий. С байтным типом-значением получается один в один. А если взять тип-значение размером байта, то графики получатся аналогичными тем, где ключ был целочисленным, как с резервированием, так и без. Проведя немало измерений, могу сказать, что тестировать хеш-таблицы на удивление сложно. Я не уверен, надо ли было тестировать все таблицы с одинаковым коэффициентом заполнения или с настройками по умолчанию. Я выбрал второй вариант. К тому же пришлось тестировать в разных условиях: Тестов тоже пришлось сделать немало. Я мог бы вывалить в эту статью тысячи графиков, но это лишнее, так что подытожу:. При использовании моей таблицы можете без опаски бросать исключения в свой конструктор, в конструктор копий, в хеш-функцию, в функцию проверки равенства equality function и в аллокатор. Нельзя бросать исключения в конструктор перемещений move constructor или в деструктор. Дело в том, что моя таблица должна перемещать элементы и поддерживать инварианты. Но она не сможет этого делать, если вы будете бросать исключения в конструктор перемещений. Можете скачать исходный код с Github. Он распространяется под Boost-лицензией. Под общим заголовком вы найдёте ska:: Интерфейс такой же, как в std:: Есть одна сложность с использованием версии таблицы, в которой размер массива определяется степенью двойки. Я выше это объяснял, ищите по ska:: Можете спокойно задавать ему значения вплоть до 0,9. Только имейте в виду, что есть вероятность перераспределения таблицы до достижения этого ограничения. Думаю, я написал самую быструю хеш-таблицу. Она определённо быстрее всех выполняет поиск и очень быстро выполняет вставки и удаления. Главное — задайте ограничение максимального количества наборов. Его можно вычислить как log2 n , что в худшем случае даст временную сложность операции поиска на уровне O log n вместо O n. Ограничение количества наборов прекрасно сочетается с хешированием Robin Hood и позволяет выполнять ряд тонких оптимизаций внутреннего цикла. Я бы только сократил это до одной строки на case и, возможно, использовал макрос вида P i, prime case i: Вот почему конкретно divq медленная я не знаю, но сделать даже целочисленное деление в микропроцессорах всегда было сложно. Я так понимаю, тут утверждается, что операция получения остатка от деления долгая, и в случае с константой компилятор сможет заменить деление на что-нибудь более быстрое. Что деление через умножение выгоднее, если деление на выбранный делитель делается хотя бы раза, известно достаточно давно с тех пор, как появилось O 1 умножение. Выбирая делитель размер таблицы у ТС , можно вычислить необходимые параметры в простейшем случае — множитель, величину финального сдвига и направление округления и запомнить их до следующей смены размера. Библиотека по ссылке значительно более продвинута, и может оказаться оверкиллом. Только полноправные пользователи могут оставлять комментарии. TM Feed Хабрахабр Geektimes Тостер Мой круг Фрилансим. Хабрахабр Публикации Пользователи Хабы Компании Песочница. Ru Group ,39 Строим Интернет. Тип хеш-таблицы Существует много типов хеш-таблиц. Для своей я выбрал: Количество слотов — простое число но я реализовал возможность использовать для этой цели числа, являющиеся степенями двойки. Ограничение максимального количества наборов. Ограничение максимального количества наборов C основами разобрались, давайте теперь обсудим моё решение: Вот как выглядит функция поиска: Такой подход лучше простого линейного размещения по двум причинам: Нет проверки диапазона изменения индексов. В цикле выполняется не больше log2 n итераций. Обычно при поиске в хеш-таблицах худшая временная сложность равна O n. В моей таблице — O log n. Особенно с учётом того, что при линейном размещении предпочтительнее худший вариант, поскольку элементы склонны к группированию. Производительность поиска Не так-то просто выяснить производительность хеш-таблиц. Как минимум нужно измерять скорость в таких ситуациях: Поиск элемента, находящегося в таблице. Поиск элемента, отсутствующего в таблице. Вставка группы случайных чисел. Вставка группы случайных чисел после вызова reserve. Первый график — поиск элемента, присутствующего в таблице: Давайте посмотрим графики неудачного поиска — то есть поиска элемента, отсутствующего в таблице. Простые числа или степень двойки Поиск элемента в таблице проходит через три дорогостоящих этапа: Размещение ключа в слоте. Получение памяти для этого слота. Этап 2 — целое число по модулю integer modulo. Вот график второго бенчмарка, но в этот раз я не использовал случайные числа: Когда для присвоения слоту хеш-значения нужно вычислить целое число по модулю, выполняется вот что: Итак, вы поместили typedef в свой объект кастомной хеш-функции: Производительность вставки и удаления После такого отвлечения на теорию давайте вернёмся обратно к производительности моей таблицы. График отражает скорость работы таблицы без вызова reserve перед вставкой элемента: Теперь измерим, как будет вставляться элемент, если сначала вызвать reserve: Затем поделил общее время на N: Разные ключи и значения До сих пор я измерял производительность при сопоставлении целочисленного ключа и целочисленного значения map from int to int. Для начала — вот графики удачных и неудачных поисков при использовании в качестве ключей строковых значений: Взглянем на неудачные поиски: А вот при промахах кеша ситуация иная: Вот график вставки с использованием целочисленного ключа и байтной структуры в качестве значения: Давайте посмотрим, какая будет ситуация с байтной структурой: Посмотрим, что будет, когда мы вставим те же элементы, но с предварительным вызовом reserve: Измерим теперь скорость вставки строковых ключей: Давайте попробуем сначала запускать reserve: При использовании строкового ключа с большим типом-значением мы будем наблюдать ту же картину: А с байтами ситуация такая: Вот один из них: Если сделать размер значения байта, то график будет очень похож на один из вышеприведённых. Начнём с типа-значения размером 32 байта: Итоги по производительности Проведя немало измерений, могу сказать, что тестировать хеш-таблицы на удивление сложно. Я мог бы вывалить в эту статью тысячи графиков, но это лишнее, так что подытожу: Моя новая таблица выполняет поиск быстрее всех остальных таблиц, которые я смог найти. Также она очень быстро выполняет вставки и удаления. Особенно если воспользоваться предварительным резервированием. Контейнеры на базе узлов могут быть быстрее при работе с большими типами, если вы не знаете заранее, сколько элементов у вас будет. Стоимость перераспределения губит производительность flat-контейнеров. Без перераспределений мой flat-контейнер оказывается самым быстрым во всех бенчмарках с использованием больших типов. Ключевым фактором при вставке строковых ключей является стоимость хеширования строковых значений, сравнения и копирования. Поэтому выбор хеш-таблицы не играет особой роли. У неё очень высокая производительность для контейнера на базе узлов. Если вы знаете, что ваша хеш-функция возвращает хорошее распределение значений, то вы можете значительно увеличить скорость работы, воспользовавшись моей хеш-таблицей, в которой размер массива определяется степенью двойки. Исключения При использовании моей таблицы можете без опаски бросать исключения в свой конструктор, в конструктор копий, в хеш-функцию, в функцию проверки равенства equality function и в аллокатор. Исходный код и использование Можете скачать исходный код с Github. Итог Думаю, я написал самую быструю хеш-таблицу. Добавить в закладки Ru Group рейтинг , Метки лучше разделять запятой. Огромное спасибо за перевод. Собирался переводить эту статью для хабра, но вы опередили. Что касается темы, то удивительно, что в этой области ещё столько простора для исследований и оптимизаций. Казалось бы структура данных, старая как мир, уже не может быть улучшена. Не сказал бы, что использованные в статье техники очень сложные или тянут на докторскую. Просто оптимизации, а значит есть куда расти дальше. Можно и тут сделать по аналогии. А массив вместо этого использовать нельзя? А не подскажете почему switch быстрее? Интуитивно вроде бы должно быть наоборот… Если есть пример генерируемого кода — вообще было бы отлично, но как руки дойдут попробую сам проверить. Интуитивно — не всегда точно. Switch может развернуться в последовательность direct mov и один jmp если компилятор достаточно умный , что даст пару промахов конвеера в худшем случае. Чтение же из таблицы которая скорее всего упадёт в read-only data section даст один mov, но из memory, что подороже регистрового. Потому и написал, что проверю как смогу. Да уж что может быть быстрее, чем взятие элемента массива? Компилятор себе наверняка составит массив меток и будет по ним переходить, в результате будет две операции вместо одной. Я ради интереса скомпилировал тот кусок кода с gcc и посмотрел, что получилось. Не стоит считать производительность по количеству инструкций. Одна инструкция div divq требует десятки тактов, тогда как большинство битовых — 1 такт. Есть даже такое чудо как https: Обычное деление выполняется со скоростью 1 бит за такт. Поскольку ALU сейчас работает на удвоенной частоте, в итоге имеем 2 бита за такт. Но в битном режиме делимое имеет размер 64 бита edx: For dividend value greater than bits, the latency can range from cycles. Если же деление происходит на константу, то обычно компилятор может заменить его на умножение п. Хотя вот этот момент было бы интересно увидеть на практике — насколько быстрее, стоит ли это того. Почему с указателями будет паддинг 7байтов? Размер указателя на сколько помню 4байта для 32х и 8байтов для 64х. Товарищу конечно надо было брать не список простых чисел, а просто перехешировать хэш полиномом на простом числе. Сейчас он делает h mod p, что блин дорого. При этом они взаимно простые размазывание по таблице будет равномерным , и очень сложно представить данные с периодом При росте таблицы можно брать более длинные простые числа в качестве полиномов. По сути таблица растёт пока максимальный список коллизий не будет размещён практически линейно. Конечно это будет быстро… если хватит памяти. Робин Гуд помогает, но незначительно. Ну то есть вот есть какое-то распределение, получаем коллизию, локальное уплотнение занятых слотов превышает максимальный lookup range, таблица растёт. При росте получаем совершенно новое распределение и никто не гарантирует что в нём не получится нового плотного места которое в свою очередь приведёт к новому росту и т. Даже коллизий много не надо, потому что рост таблицы происходит не просто из-за коллизии а из-за неукладывания в lookup range. Таблица имеет тенденцию к росту если в ней есть хоть один непрерывно занятый диапазон, длина которого превышает lookup range. Вероятность того, что слот будет иметь тенденцию к росту всегда ненулевая если число занятых слотов превышает диапазон поиска. Можно её даже посчитать, — если рассматривать свободные слоты как случайную выборку на диапазоне, это вероятность того, что максимальное расстояние между соседними элементами в ней будет больше чем lookup range. Комбинаторика, берем число сочетаний из N по K, вычитаем число сочетаний из N-R по K, соотносим. В общем там куча восклицательных знаков, ну да это и неважно. Интуитивно понятно что она инвариант при масштабировании. Но диапазон рассчитывается как логарифм от размера таблицы, то есть имеет арифметическую прогрессию при геометрической прогрессии роста таблицы. Поэтому с ростом таблицы вероятность попасть на слот с тенденцией к росту растет. Кстати, в этой таблице rehash рекурсивный. В таком случае будет медленнее работать на тех данных, которые потенциально сожрут всю оперативку, и примерно так же для более-менее равномерно распределенных величин. Перераспределение связано с увеличением lookup range, это ограничение поиска. Ну и вставка не произойдет пока перераспределение не приведёт к тому что место вставки не окажется в пределах lookup range от начального слота. А данные и так хорошо распределены, большая часть без коллизий вообще ну и допустим меньше процента с глубиной списка коллизий до 6. Но вот этот самый один процент при большом количестве данных всегда ведёт к росту. Дата основания 15 октября Локация Москва Россия Сайт corp. В Облаке для Android появилась наглядная статистика по количеству фото 7 июля GeekBrains — обучающий портал для программистов geekbrains. Официальное почтовое приложение Mail. Ru, Yandex, Google, Yahoo, AOL ; — удобный и быстрый интерфейс; — аватарки и иконки в списке писем; — моментальные уведомления о письмах. ВКонтакте — это социальная сеть для быстрой и удобной коммуникации между людьми по всему миру. Маршрут по Вестеросу и Эссосу: Отчет с Science Slam Digital 7 июля 96 0. Интересные публикации Хабрахабр Geektimes. Британские спутниковые снимки 2: Как все было на самом деле. Мониторинг работы производства веб-студии. Необходимость регулирования интернета вещей. Movidius Neural Compute Stick — искуственный разум на флешке GT. Дизайн для пальцев, касаний и людей. Наука над земным шаром, часть 2 GT. Разделы Публикации Хабы Компании Пользователи Песочница. Информация О сайте Правила Помощь Соглашение Конфиденциальность. Услуги Реклама Тарифы Контент Семинары.
Как пожарить сочную горбушу на сковороде
Ростовые куклы на дне рождения
Виртуальный музей справочник отечественная радиотехника 20 века
Разрешение коллизий
Таможенное оформление мпо
Украшение школьного двора своими руками
Политика и право в задачах
Хеширование это:
Тату надпись на руке про детей
Сколько можно хранить вареную грудку
Алгоритмы хеширования данных
Жарят ли грибы вешенки
Части речи в составе предложения
Идея 74 магнитогорск
Алгоритмы хеширования данных
Как сшить подстилку для кошки своими руками