Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 31
Причина, почему в Trove не используются стандартные интерфейсы, проста — с ними постоянно будет происходить boxing/unboxing примитивов. Если куда-то нужно передать именно как стандартную коллекцию — есть TDecorators.
1) Специализированные методы никуда не деваются,
2) Как правило, «вне» коллекций идет работа как раз с примитивами, которые вынужденно боксятся при засовывании в j.u.HashMap. Если там мапа будет представлять новый интерфейс, за счет оверлоадинга вызовутся примитивные методы, придется поменять 1 строчку — объявление мапы.
3) Вы не поверите, я уже там внутри, имея примитив, иду на один боксинг/анбоксинг в отдельных местах, чтобы вместо этого не читать/писать в поле. Мне кажется, HotSpot все разрулит, как надо.
4) В любом случае, цена боксинга мала по сравнению с 100 нс на то, чтобы положить double в хеш. Целочисленное деление и прыжки по массиву в разы дороже.
get(char), put(float, long) — все это есть2) Как правило, «вне» коллекций идет работа как раз с примитивами, которые вынужденно боксятся при засовывании в j.u.HashMap. Если там мапа будет представлять новый интерфейс, за счет оверлоадинга вызовутся примитивные методы, придется поменять 1 строчку — объявление мапы.
3) Вы не поверите, я уже там внутри, имея примитив, иду на один боксинг/анбоксинг в отдельных местах, чтобы вместо этого не читать/писать в поле. Мне кажется, HotSpot все разрулит, как надо.
4) В любом случае, цена боксинга мала по сравнению с 100 нс на то, чтобы положить double в хеш. Целочисленное деление и прыжки по массиву в разы дороже.
Правильно ли я понял, что вы, используя trove-вовский алгоритм хэштаблиц, используете load-factor=0.8? Если да, то почему именно такой, и почему авторы trove сами до такого не догадались?
Использую, то есть передаю с конструктором в своем коде. Дефолтный 0,5 не менял. 0,8 — точно так же на глаз, как и 0,5, никакого математического обоснования и даже прикидки под этими числами нет. Хотя, хочу через некоторое время поиграться с коэффициентами и написать об этом.
Вы, наверное, удивитесь, но обоснование-то как раз есть — если уж вы взялись переписывать одну из известнейших библиотек коллекций, вам стоило бы хотя бы разбираться в теме хэш-таблиц на уровне повыше, чем статья из русской википедии. Собственно, я и задал этот вопрос чтобы проверить, понимаете ли вы вообще ту структуру данных, которую реализуете.
Так вот, для хэштаблиц с открытой адресацией качество хэшфункции гораздо важнее, чем для «классических», с линейными списками коллизий. Причина этого в том, что «корзинки» в таблицах с линейными списками изолированы друг от друга — если у вас хэш-функция имеет неравномерное распределение, то переполненными рискуют оказаться только отдельные, неудачные корзинки, в остальных же время поиска останется малым. Для открытой адресации это не так — у вас общий массив, и коллизия по одному индексу означает не только то, что по этому индексу probe count=2, но и по другому индексу, место которого вы заняли, тоже probe count становится 2. Если вы помоделируете в голове эту ситуацию дальше, с большим количеством элементов, вы поймете в чем тонкость таблиц с открытой адресацией — они страдают от кластеризации коллизий.
Поэтому-то умолчательная загрузка для chaining maps=0.75, а для open-addessing maps=0.5 — это не «на глаз», как вам показалось, а просто выше 0.5 для oohm количество попыток (probe count) начинает быстро и нелинейно расти, и уже для 0.7-0.8 probe count достигает 5 и выше, что считается плохим показателем.
Так вот, для хэштаблиц с открытой адресацией качество хэшфункции гораздо важнее, чем для «классических», с линейными списками коллизий. Причина этого в том, что «корзинки» в таблицах с линейными списками изолированы друг от друга — если у вас хэш-функция имеет неравномерное распределение, то переполненными рискуют оказаться только отдельные, неудачные корзинки, в остальных же время поиска останется малым. Для открытой адресации это не так — у вас общий массив, и коллизия по одному индексу означает не только то, что по этому индексу probe count=2, но и по другому индексу, место которого вы заняли, тоже probe count становится 2. Если вы помоделируете в голове эту ситуацию дальше, с большим количеством элементов, вы поймете в чем тонкость таблиц с открытой адресацией — они страдают от кластеризации коллизий.
Поэтому-то умолчательная загрузка для chaining maps=0.75, а для open-addessing maps=0.5 — это не «на глаз», как вам показалось, а просто выше 0.5 для oohm количество попыток (probe count) начинает быстро и нелинейно расти, и уже для 0.7-0.8 probe count достигает 5 и выше, что считается плохим показателем.
Вы зря обвиняете меня в невежестве, все, что вы написали, я прекрасно знаю. Я выводил конкретные вероятности кол-ва проб в случае успешного поиска при опред. коэффициенте, которые нигде в готовом виде не нашел: cs.stackexchange.com/a/13447/9350. Строил модель ускоренного исчезновения «удаленных» ячеек при вставке в таблицу: bitbucket.org/leventov/trove/src/61bcef705413/src/gnu/trove/impl/hash/DHash.java#cl-148. Вот это —
Но 0,5 — действительно на глаз. Вроде не очень много, но вроде и не очень мало. Почему, например, не 0,45 или 0,55 — никакого обоснования нет.
0,8 — из той же серии: вроде лишней свободной памяти уже «почти» не расходуется, с другой стороны, среднее кол-во проб еще божеское. Не забывайте, что 3-я и последующие пробы в 2-3 раза дешевле, чем первые 2, потому что для них не надо нацело делить хеш на размер таблицы.
при попеременных удалениях и вставках разных случайных элементов — k заполненных и (1 — k) ^2 — свободных (все величины — в долях от 1).— тоже взято не с потолка.
Но 0,5 — действительно на глаз. Вроде не очень много, но вроде и не очень мало. Почему, например, не 0,45 или 0,55 — никакого обоснования нет.
0,8 — из той же серии: вроде лишней свободной памяти уже «почти» не расходуется, с другой стороны, среднее кол-во проб еще божеское. Не забывайте, что 3-я и последующие пробы в 2-3 раза дешевле, чем первые 2, потому что для них не надо нацело делить хеш на размер таблицы.
Но 0,5 — действительно на глаз. Вроде не очень много, но вроде и не очень мало. Почему, например, не 0,45 или 0,55 — никакого обоснования нет.
Почему не 0.55 действительно обоснования нет. А почему не 0.8 как раз обоснование есть, и я вам его привел.
Оценка, которую вы привели — выведена в предположении (идеально) равномерной хэш-функции. Таких функций на практике не бывает. И я еще раз вам подчеркиваю особенность ОА по сравнению с цепочной таблицей — в цепочных таблицах неидеальности хэш-функции локализованы в конкретных корзинках. В ОА таблицах неидеальности хэш-функции имеют глобальный и очень паршивый эффект — они сильно ускоряют кластеризацию коллизий. Это примерно как в кристаллизации из насыщенного раствора: малые отклонения от однородности раствора резко ускоряют процесс выпадения кристаллов. Моделировать этот эффект математически довольно сложно, его проще увидеть в симуляциях.
Это одна из причин, почему j.u.HMap может себе позволить класть болт на рекомендации Кнута про простые числа, тупо иметь размер таблицы в 2^N и все еще неплохо работать даже с теми
Не забывайте, что 3-я и последующие пробы в 2-3 раза дешевле, чем первые 2, потому что для них не надо нацело делить хеш на размер таблицы.
Не забывайте, что кроме сравнения хэшей каждая проба требует еще и чтения — т.е. это потенциальный кэш-промах. Это не актуально для линейного хэширования, где высокая локальность, да паттерн прохода по массиву идеально предсказуем, но вполне себе актуально для двойного хэширования, которое используется в trove.
Кроме того не забывайте, что вообще переход к пробам вместо прямого попадания сам по себе не бесплатен: у вас есть fast path (direct hit), простой и хорошо предсказываемый, а пробинг — это цикл, это обвязка цикла, это скачки по памяти с каким-то шагом… Это разный код, с разными характеристиками «понятности» для процессора, с разными статистическими характеристиками предсказуемости конкретных условных переходов, и т.п. Весьма разумно стараться, чтобы у direct hit было тотальное доминирование по вероятности — собственно, на это и заточен код в trove. Если вы хотите таблицу, у которой ожидаемый («крейсерский») режим функционирования — это, скажем, 5-6 проб на поиск, то под этот режим и надо писать код. Например, нет смысла тогда как-то выделять direct hit — если у него нет доминирующей вероятности то в чем его избранность? Надо все единообразно свернуть в общий цикл пробинга.
Интересный (гипотетический) эффект здесь в том, что код (непосредственно скомпилированные JIT-ом байтики) будет общий, как для тех таблиц, где по-умолчанию load factor = 0.5, так и для ваших, с lf=0.8. При этом статистические свойства условных переходов будут сильно отличаться — а статистика предсказателя ветвлений привязана ведь к коду, а не к данным. Т.е. вы своим выбором нетривиального lf можете сбивать с толку hardware branch predictor, ухудшая производительность как для «своих» таблиц, так и для дефолтных.
Это одна из причин, почему j.u.HMap может себе позволить класть болт на рекомендации Кнута про простые числа, тупо иметь размер таблицы в 2^N и все еще неплохо работать даже с теми уебищными неоптимальными хэш-функциями, которые пишут в 99.9% случаев (хотя в какой-то из версий авторы-таки решили, что немного подсолить не помешает, и теперь там есть небольшой трюк чтобы сгладить-таки совсем уж плохие варианты). А trove себе такого позволить не может, и мучается с простым размером таблицы, и сопутствующим ему дорогим «честным» делением
Нет, в Trove простой размер не из-за плохих хешей. Если обратиться к практике, понятно, что основное предназначение Trove — все-таки хэши с примитивными ключами/элементами. У int, float, char, short, byte хеши в определенном смысле «идеальны» по определению, также нет никаких причин сомневаться в качестве хешей long и double. Множества объектов и мапы объект — примитив/объект все-таки в основном «до кучи» в библиотеке, что называется.
По поводу линейного исследования vs. двойное — действительно, двойное менее чувствительно к качеству хеша. Но сказать, какой из вариантов лучше, невозможно. Я об этом вообще не задумывался, потому что если бы я еще и двойное поменял на линейное, это было бы уже не переписывание библиотеки, а, по сути, написание новой с нуля. Можно считать, что это «историческое» решение в Trove. Линейное, кажется, в HPPC.
По поводу выбора линейное — двойное, рекомендую (не сомневаюсь, что вы все читали, это, так сказать, для остальных читателей диалога):
www.slideshare.net/elizarov/ss-13204837
github.com/elizarov/fasthash/tree/master/src/fasthash/impl
(И еще зайдите на elizarov.lj.ru, который сейчас не открывается, поэтому ссылку на пост дать не могу)
Не забывайте, что кроме сравнения хэшей каждая проба требует еще и чтения — т.е. это потенциальный кэш-промах. Это не актуально для линейного хэширования, где высокая локальность, да паттерн прохода по массиву идеально предсказуем, но вполне себе актуально для двойного хэширования, которое используется в trove.
Именно это меня интересует применительно к коеффициенту. Я хочу посмотреть, как соотносятся эффекты большего числа промахов при меньшем коэффициенте, если в целом размер заполенных ячеек где-то с L1, или L2, или L3, с тем, что при меньшем коеффициенте меньше проб.
Для масштаба, опять же остальным читателям, сообщу, что в Sandy Bridge, latency чтения: из L1 — 3-4 такта, из L2 — 11, из L3 — 14-38 (источник), целочисленное деление — 20-28 тактов (источник).
Весьма разумно стараться, чтобы у direct hit было тотальное доминирование по вероятности — собственно, на это и заточен код в trove.
Нет, Trove не был под это заточен. Я тут с вами полностью согласен, не понимаю, в чем спор. Вот цитата из поста:
При этом ищут элемент в хеш-таблице, либо для того, чтобы его туда потом вставить, либо чтобы взять значение из параллельного массива (map.get() или set.contains()). В первом случае можно считать, что элемента в таблице, скорее всего, еще нет, а во втором — что он, скорее всего, уже там лежит. В предыдущей реализации Trove в обоих вариантах поиска в первую очередь проверяется, не пуста ли ячейка, и потом, не лежит ли там то, что мы ищем. Хотя при поиске «на взятие» надо в первую очередь проверять, не равен ли текущий элемент искомому (да так и есть).
5-6 проб на поиск, то под этот режим и надо писать код.
Ручной unroll цикла пробинга? Интересно, не думал об этом, правда на вскидку не уверен, что что-то даст :)
Интересный (гипотетический) эффект здесь в том, что код (непосредственно скомпилированные JIT-ом байтики) будет общий, как для тех таблиц, где по-умолчанию load factor = 0.5, так и для ваших, с lf=0.8. При этом статистические свойства условных переходов будут сильно отличаться — а статистика предсказателя ветвлений привязана ведь к коду, а не к данным. Т.е. вы своим выбором нетривиального lf можете сбивать с толку hardware branch predictor, ухудшая производительность как для «своих» таблиц, так и для дефолтных.
Позитивный момент в том, что порядок веток по вероятности не зависит ни от коэффициента, ни от номера пробы. При неуспешном поиске в любой момент наиболее вероятно попадание на пустую ячейку, при успешном — на полную ячейку именно с тем элементом, который ищем. Это доказывается как раз формулами из ссылки, которую приводил выше. Почему при вставке я ожидаю неуспех, при set.contains и map.get — успех, объяснял выше.
порядок веток по вероятности не зависит ни от коэффициента,
Тут нужна оговорка: все-таки, при коэффициенте >=0.5 это выполняется. Если коэффициент меньше, таки в случае неуспешного поиска в первую очередь надо ожидать пустую ячейку, а при >= 0.5 — заполненную, но чем-то не тем, что нам надо.
Хотя нет, это совсем не так, cheremin прав. В случае успешного поиска порядок веток зависит и от номера пробы, и от коэффициента
хеши в определенном смысле «идеальны» по определению
Именно что «в определенном» — плохой с точки зрения oahm хэш это не только такой, когда все ключи отображаются в 1, но и такой, когда заметная часть используемых в конкретной таблице ключей отображаются в один слот. У примитивов хэши «универсально» хорошие — все множество возможных int-ов равномерно отображается во множество хэшей, да. Но в таблицу-то вы складываете не произвольные int-ы, а какие-то конкретные. И если у вас размер таблицы 17, а кладете вы туда ключи, среди которых, скажем, преобладают ключи вида 17*i+3, то у вас и будет неравномерное распределение ключей по слотам (а не ключей по хэшам). И легко видеть, что это проблема именно конкретной схемы организации хэштаблицы, а не хэша как такового: положи вы тот же набор ключей в j.u.HM с размером 16 — все будет шоколадно.
Множества объектов и мапы объект — примитив/объект все-таки в основном «до кучи» в библиотеке, что называется.
Это вы зря. Трувовские Map<Object,Object> очень даже полезны, потому что и по занимаемой памяти (с нормальной загрузкой 1/2) делают стандартные в разы, и по производительности тоже
Можно считать, что это «историческое» решение в Trove
Я думаю, это не «историческое» решение, а именно попытка написать более-менее универсальную библиотеку, работающую не только с вылизанными до блеска хэш-функциями — потому что линейное хэширование гиперчувствительно к качеству хэша. HPPC, видимо, как раз заточено под то, что люди, которые ее пользуют, хорошо знают что делают, и готовы, если что, оплатить похороны за свой счет.
Я хочу посмотреть, как соотносятся эффекты большего числа промахов при меньшем коэффициенте
Все украдено до нас: How caching affects hashing — мой краткий пересказ статьи, из которой я взял примерно половину той мудрости, которую пытаюсь тут донести :) Ссылка на оригинал там тоже присутствует, и там как раз и есть экспериментальные цифры, как меняется средний probe count для разных алгоритмов ОА хэширования при разных загрузках и реальных, неидеальных хэш-функциях — посмотрите, расхождение с теорией там весьма заметное.
Позитивный момент в том, что порядок веток по вероятности не зависит ни от коэффициента, ни от номера пробы
В чем же тут позитив-то? В предсказании ветвлений важна вероятность неуспешного предсказания — потому что откат выполненных спекуляций может быть весьма дорогим. Если у вас нет сильного доминирования одной ветки над другой — это значит, что либо предсказания вообще не будет (т.е. не будет и упреждающего выполнения — тупо теряем такты), либо предсказание будет часто ошибаться (с сопутствующими пенальти). Даже в ваших идеальных формулах видно, что direct hit доминирует даже над первой пробой с вероятностью только alpha=loadFactor=0.8 в вашем случае. Вряд ли это можно назвать сильным доминированием.
Ручной unroll цикла пробинга? Интересно, не думал об этом, правда на вскидку не уверен, что что-то даст :)
На самом деле надо сначала понять, чего именно вы хотите. Хотите сэкономить память проиграв в производительности? — вообще-то OA и так чуть ли не самые компактные в яве, даже с дефолтной загрузкой. Если нужное еще больше — может, вам вообще использовать, скажем, отсортированный массив?
Если нужны большие объемы, то можно делать гибридные структуры типа B-trees: дерево отсортированных массивов.
Даже с хэш-таблицами: мне кажется, для больших объемов будет эффективнее сделать таблицу таблиц: разбить множество хэшей на диапазоны, и в каждом иметь свою, независимо рехеширующуюся OA хэш-таблицу — это позволит ограничить эффект неоднородностей хэша одной конкретной таблицей
Чем мне не нравится ваше решение: очевидно, что жертвуя всего 20% памяти вы не можете получить какой-то особо большой прирост производительности по сравнению с отсортированным массивом как реперной точкой, ведь бесплатный сыр бывает только в мышеловке. Но проблема в том, что вы получаете непредсказуемую производительность, очень сильно зависящую от расклада ключей. На мой взгляд, большинство бизнес-приложений предпочтут в таких условиях большую стабильность призрачному выигрышу в перформансе.
Именно что «в определенном» — плохой с точки зрения oahm хэш это не только такой, когда все ключи отображаются в 1, но и такой, когда заметная часть используемых в конкретной таблице ключей отображаются в один слот. У примитивов хэши «универсально» хорошие — все множество возможных int-ов равномерно отображается во множество хэшей, да. Но в таблицу-то вы складываете не произвольные int-ы, а какие-то конкретные. И если у вас размер таблицы 17, а кладете вы туда ключи, среди которых, скажем, преобладают ключи вида 17*i+3, то у вас и будет неравномерное распределение ключей по слотам (а не ключей по хэшам). И легко видеть, что это проблема именно конкретной схемы организации хэштаблицы, а не хэша как такового: положи вы тот же набор ключей в j.u.HM с размером 16 — все будет шоколадно.
Что мы обсуждаем? Что при строго определенном характере ключей и строго определенном размере таблицы, будет много коллизий? Это из серии «лучше быть здоровым и богатым, чем бедным и больным». Один рехеш на новый размер — и все коллизии ушли.
How caching affects hashing
Спасибо за ссылочку, не видел раньше. Но все-таки это про линейное vs. двойное, а я хочу посмотреть разные коэффициенты на двойном. Кстати, не смог найти год статьи, последняя ссылка на источник там 2004 года — если статья скажем 2005-го, то чисто практически ее результаты как минимум надо перепроверить. Скажем, в Pentium 4 модуль стоил 53 такта, кеш-промахи — ?..
В чем же тут позитив-то? В предсказании ветвлений важна вероятность неуспешного предсказания — потому что откат выполненных спекуляций может быть весьма дорогим. Если у вас нет сильного доминирования одной ветки над другой — это значит, что либо предсказания вообще не будет (т.е. не будет и упреждающего выполнения — тупо теряем такты), либо предсказание будет часто ошибаться (с сопутствующими пенальти). Даже в ваших идеальных формулах видно, что direct hit доминирует даже над первой пробой с вероятностью только alpha=loadFactor=0.8 в вашем случае. Вряд ли это можно назвать сильным доминированием.
Ничего лучшего, кроме расположения веток в порядке вероятности, нельзя сделать принципиально. Да, промахи, откаты, но мы уже сделали все, что могли. Позитив в том, что этот порядок веток — один и тот же для коэффициента от 0,5 до 1,0, то есть не надо заниматься каким-то динамическим переупорядочиванием веток. (Принимая, что коэффициент меньше 0,5 — это несколько маргинальная ситуация. Если кто-то и меняет коэфф., то в большую сторону от дефолтного, как мне кажется.)
Чем мне не нравится ваше решение: очевидно, что жертвуя всего 20% памяти вы не можете получить какой-то особо большой прирост производительности по сравнению с отсортированным массивом как реперной точкой, ведь бесплатный сыр бывает только в мышеловке. Но проблема в том, что вы получаете непредсказуемую производительность, очень сильно зависящую от расклада ключей. На мой взгляд, большинство бизнес-приложений предпочтут в таких условиях большую стабильность призрачному выигрышу в перформансе.
Конкретная ситуация, в которой я завел этот хеш, если вам интересно: миллиард ключей, от 1 по порядку. В норме пропусков и отдельных ключей нет, но вообще может быть и случай, близкий к случайным ключам. Упорядоченный массив тут не вариант — 30 проб при любом поиске и дико долгие вставки-удаления. По-хорошему, нужна деградация с чего-то типа самописного ArrayList, где вместо одного массива по массиву на каждые сколько-то элементов, на этот хеш, но пока стоит просто этот хеш.
Что при строго определенном характере ключей и строго определенном размере таблицы, будет много коллизий? Это из серии «лучше быть здоровым и богатым, чем бедным и больным». Один рехеш на новый размер — и все коллизии ушли.
Я уже сам не могу понять, чего здесь не понятного: в реальности у вас не будет идеального хэша, кроме очень частных случаев когда множество ключей заранее известно и фиксировано, и вы можете попробовать подобрать perfect hash. В остальных случаях (даже для примитивов) распределение ключей по слотам таблицы не будет равномерным никогда. В chaining небольшие неоднородности почти не сказываются на производительности вплоть до очень высокой загрузки. В ОА чувствительность к неоднородностям гораздо выше — очень высока для линейного хэширования, чуть менее но все равно высока для двойного, и очень быстро растет с увеличением загрузки. Посмотрите же таблицы в статье, там в одном из экспериментов с линейным хэшированием для заполнения 0.6, например, при равномерном распределении ключей среднее число проб 1.75, а при неравномерном урезанном гауссе — 2170. Увеличение в 1000 раз по сравнению с теорией вас не достаточно впечатляет? Что там вы говорили про 30 шагов бинарного поиска, которые вас не устраивают?..
В норме пропусков и отдельных ключей нет, но вообще может быть и случай, близкий к случайным ключам.
А вы считали среднее число проб в этом вашем случае?
Посмотрите же таблицы в статье, там в одном из экспериментов с линейным хэшированием для заполнения 0.6, например, при равномерном распределении ключей среднее число проб 1.75, а при неравномерном урезанном гауссе — 2170. Увеличение в 1000 раз по сравнению с теорией вас не достаточно впечатляет?
Смотрите, там усеченное гауссово со средним = размер таблицы / 2 и отклонением размер таблицы / 4. Значит 68,2 % чисел, которые они пробовали вставлять, лежали в диапазоне от четверти до трех четвертей размера таблицы. Размер диапазона — полтаблицы, соответствует коэффициенту 0,5. Пока они достигли коэффа 0,6, заполнили эту середину уже плотно. Простой размер не играл роли — все числа меньше него. А это очень важно. Поэтому они там намеряли свойства кластеризации линейного, а не качество хешей уж точно.
В конце вообще какая-то лажа — как может быть 127 тыс. проб в раблице размера 100 тыс.? Ну да ладно.
А вы считали среднее число проб в этом вашем случае?
В нормальном случае кол-во проб всегда 1 — ведь все ключи подряд заполняют начало таблицы, коллизий нет, в конце 20% свободного места, и все. Оверхед по большому счету на одно ненужное целочисленное деление только.
В той же табличке, кстати, справа цифры для «универсального» хеширования (т. е. 2 хеш функции), вполне приличные. Не смог понять, как они его моделировали, но вообще двойное считается почти универсальномым по качеству. Хотя бы потому, что для двойного берут формулы, рассчитанные для универсального в принципе.
Это цитата из моего пред. комментария, к которой вы, вероятно, придеретесь:
В конце концов, можно убрать параметр loadFactor из всех публичных конструкторов хешей, а взамен сделать билдеры, которые на основании loadFactor будут возвращать инстансы приватных подклассов с ветками в нужном порядке.
Эти билдеры я в любом случае подумывал сделать, потому что слишком много у хешей параметров: начальный размер, коэффициент, элементы из существующей коллекции, примитив, выступающий в качестве null, простой хеш/только добавления/неизменяемый, и т. д.
(Принимая, что коэффициент меньше 0,5 — это несколько маргинальная ситуация. Если кто-то и меняет коэфф., то в большую сторону от дефолтного, как мне кажется.)
В конце концов, можно убрать параметр loadFactor из всех публичных конструкторов хешей, а взамен сделать билдеры, которые на основании loadFactor будут возвращать инстансы приватных подклассов с ветками в нужном порядке.
Эти билдеры я в любом случае подумывал сделать, потому что слишком много у хешей параметров: начальный размер, коэффициент, элементы из существующей коллекции, примитив, выступающий в качестве null, простой хеш/только добавления/неизменяемый, и т. д.
Этого делать не стоит, потому что если у вас будет множество реализаций, скажем, метода index(), то JIT не сможет сделать эффективную девиртуализацию, а без девиртуализации невозможен инлайнинг, который за собой тянет возможность целого ряда оптимизаций — за счет расширения контекста.
У меня, наоборот, была идея, которую я не успел протестировать: вот сейчас в trove direct hit & probing реализованы в одном методе index(...). Я бы попробовал пробинг вынести в отдельный метод — т.е сделать типа
Мотивация такая: уменьшая размер метода, и упрощая его структуру мы увеличиваем шансы на его инлайнинг. Инлайнинг кода для direct hit кажется очень полезным, потому что это (в нормальных условиях) тотально доминирующая ветка, при этом она очень короткая и простая, и будучи вклееной может потом быть заредуцирована дальше компилятором по самое нехочу. Инлайнинг же пробинга не особо полезен, потому что кода там сильно больше, а вероятность его исполнения сильно меньше, он сложнее, и вряд ли там что-то дальше особо наоптимизировать сильно удастся, только общий размер кода увеличится.
У меня, наоборот, была идея, которую я не успел протестировать: вот сейчас в trove direct hit & probing реализованы в одном методе index(...). Я бы попробовал пробинг вынести в отдельный метод — т.е сделать типа
index(){
check direct hit
if( hit ) -> return values[index];
else -> return probingStartingWith(....);
}
Мотивация такая: уменьшая размер метода, и упрощая его структуру мы увеличиваем шансы на его инлайнинг. Инлайнинг кода для direct hit кажется очень полезным, потому что это (в нормальных условиях) тотально доминирующая ветка, при этом она очень короткая и простая, и будучи вклееной может потом быть заредуцирована дальше компилятором по самое нехочу. Инлайнинг же пробинга не особо полезен, потому что кода там сильно больше, а вероятность его исполнения сильно меньше, он сложнее, и вряд ли там что-то дальше особо наоптимизировать сильно удастся, только общий размер кода увеличится.
множество реализаций, скажем, метода index(), то JIT не сможет сделать эффективную девиртуализацию
Вы уверены? Вот JIT видит, что идет работа с абстрактным классом, и там везде одна и та же реализация — почему бы не девиртуализировать с деградацией на случай несовпадения класса. Я думал, что это делается.
Мысль с методом index при сравнительно маленьком коэффициенте мне нравится. А вы не знаете конкретнее о порогах размеров методов, которые учитываются ГИТом ХотСпота?
JIT видит вызов THashMap.get(). Есть перегруженные версии? — нет, ок, ставим проверку-охрану и инлайним. Внутри видим TObjectHash.index() — есть перегруженные версии? — да, аж 5 штук. Насколько я знаю, сейчас JIT пытается делать девиртуализацию до 3-4, потом просто честно ставит virtual call. Но даже девиртуализация на 3-4 версии уже не очень хорошо, потому что там же будет условный переход, который тоже еще непонятно как предсказываться будет. Лучше, чтобы была только одна реализация, конечно.
Я, конечно, не уверен, это мое представление. Чтобы быть уверенным надо делать бенчмарк с одновременным использованием нескольких реализаций, греть его, и смотреть дизасм.
Я, конечно, не уверен, это мое представление. Чтобы быть уверенным надо делать бенчмарк с одновременным использованием нескольких реализаций, греть его, и смотреть дизасм.
А вы не знаете конкретнее о порогах размеров методов, которые учитываются ГИТом ХотСпота?Можно вывести -XX:+PrintFlagsFinal, и грепнуть там что-то вроде InlineThreshold. Но я думаю, на это не стоит закладываться.
Низкий порог, правда.
MaxInlineSize maximum bytecode size of a method to be inlined 35
MaxBCEAEstimateSize Maximum bytecode size of a method to be analyzed by BC EA. 150
MaxInlineLevel maximum number of nested calls that are inlined 9
cheremin, опять я фигню написал :(
stackoverflow.com/a/18741113/648955
В общем, мораль — можно дробить на какие угодно мелкие методы, все заинайнится.
stackoverflow.com/a/18741113/648955
FreqInlineSize Maximum bytecode size of a frequently executed method to be inlined. 325
В общем, мораль — можно дробить на какие угодно мелкие методы, все заинайнится.
Девиртуализация работает не так. Учитывается динамический профиль конкретного сценария. Может быть хоть 100 реализаций виртуального метода, но если в конкретном месте конкретного приложения используется преимущественно одна и или две реализации, то данный вызов все равно будет девиртуализован и заинлайнен.
Т.е. правильно ли я понял:
Мы начинаем с честного виртуального вызова call object._vtable[index].
Какое-то время собираем статистику точек назначения. Получаем профиль типа
90% — impl1
8% — impl2
2% — others+
Теперь JIT рекомпилирует код примерно в такой:
И потом ветки 1-2 уже могут быть оптимизированы еще дальше — например, методы вклеены. Все правильно?
Теперь у меня такой вопрос — после оптимизирующей рекомпиляции сбор статистики продолжается? Т.е. если профиль исполнения в какой-то момент изменится — случится ли ре-оптимизация?
Мы начинаем с честного виртуального вызова call object._vtable[index].
Какое-то время собираем статистику точек назначения. Получаем профиль типа
90% — impl1
8% — impl2
2% — others+
Теперь JIT рекомпилирует код примерно в такой:
if( object.klass == impl1.klass )
call impl1.method
else if( object.klass == impl2.klass )
call impl2.method
else
call _vtable[index]
И потом ветки 1-2 уже могут быть оптимизированы еще дальше — например, методы вклеены. Все правильно?
Теперь у меня такой вопрос — после оптимизирующей рекомпиляции сбор статистики продолжается? Т.е. если профиль исполнения в какой-то момент изменится — случится ли ре-оптимизация?
Да, все правильно.
Полностью соптимизированный код статистику более не собирает и, если вдруг посреди исполнения программы профиль резко поменяется, столкнемся с деградацией производительности.
Это в том случае, если метод все время продолжает исполняться.
Метод, который какое-то время не исполняется, может быть выкинут из CodeCache во время GC и при последующих вызовах будет компилироваться заново.
Полностью соптимизированный код статистику более не собирает и, если вдруг посреди исполнения программы профиль резко поменяется, столкнемся с деградацией производительности.
Это в том случае, если метод все время продолжает исполняться.
Метод, который какое-то время не исполняется, может быть выкинут из CodeCache во время GC и при последующих вызовах будет компилироваться заново.
Что вы думаете в целом по поводу идеи? Сделать от 2 до 6 специализаций в зависимости от коэффициента. Менять порядок условий и unroll (среднее кол-во итераций около 5 может быть).
Потенциальный профит — 2-3-5 нс навскидку, и то не факт, особенно если JIT сам разберется с порядком веток. Допустим, профит будет. А сейчас эти методы выполняются 30-100 нс. То есть еще 5-10% ускорения.
С другой стороны — вот, деградация возможна. Если 1) в приложении сравнительно активно используются хэши одного типа, но с разными коэффициентами; 2) метод, например map.get, оптимизируется, но сам уже не инлайнится.
Что весомее, на ваш взгляд?
Потенциальный профит — 2-3-5 нс навскидку, и то не факт, особенно если JIT сам разберется с порядком веток. Допустим, профит будет. А сейчас эти методы выполняются 30-100 нс. То есть еще 5-10% ускорения.
С другой стороны — вот, деградация возможна. Если 1) в приложении сравнительно активно используются хэши одного типа, но с разными коэффициентами; 2) метод, например map.get, оптимизируется, но сам уже не инлайнится.
Что весомее, на ваш взгляд?
Заниматься мелочёвкой вроде перестановки условий и ручного разворачивания циклов я бы не стал, тем более, что JIT в определённой степени это сам делает. Много на этом не сэкономить: один единственный cache miss будет стоить сотни тактов и перекроет всю выгоду от микрооптимизаций.
Я в свое время экспериментировал с разными алгоритмами open-address hashing и остановился на одной хеш-функции с вариацией quadratic probing (с увеличивающимися шагами: 1, 2, 3...). Такой вариант на порядок лучше linear probing по среднему числу итераций, и, в отличие от двойного хеширования, обладает хоть каким-то cache locality.
К loadFactor'у у меня был другой подход: полное отсутствие loadFactor как такового :) Вместо него считалось число итераций, и, когда оно переваливало за некий порог (скажем, capacity ^ 1/3), таблица увеличивалась.
Я в свое время экспериментировал с разными алгоритмами open-address hashing и остановился на одной хеш-функции с вариацией quadratic probing (с увеличивающимися шагами: 1, 2, 3...). Такой вариант на порядок лучше linear probing по среднему числу итераций, и, в отличие от двойного хеширования, обладает хоть каким-то cache locality.
К loadFactor'у у меня был другой подход: полное отсутствие loadFactor как такового :) Вместо него считалось число итераций, и, когда оно переваливало за некий порог (скажем, capacity ^ 1/3), таблица увеличивалась.
Вместо него считалось число итераций, и, когда оно переваливало за некий порог (скажем, capacity ^ 1/3), таблица увеличивалась.
Не очень понял — вы считали максимальное количество проб? Разве это не опасный способ — если ситуация объективно вырожденная (кто-то записал 100 объектов с одинаковым хэшкодом), то таблица будет ресайзиться до опупения…
Да: когда очередной put() делал слишком много проб, таблица ресайзилась. Критерий «слишком много» каждый может определить сам — идея лишь в том, чтобы поддерживать производительность мапы на приемлемом уровне. Понятно, что с произвольными данными со стороны такой фокус не пройдет. Но в нашем случае, например, порог достигался при более чем 90% заполненности таблицы.
Я вот уже не в первый раз и прихожу к выводу, что все-таки универсальная и быстрая хэш-таблица это миф. Нужно специализироваться под конкретные данные.
Вот например: рехэшироваться в зависимости от какой-то метрики качества текущего layout-а — это, конечно, сильная идея. Вот только по хорошему надо ориентироваться на среднее число попыток по всем ключам (а еще лучше — на среднее с весом частоты использования ключа). А его считать штука гораздо более tricky…
Я почему про максимальное число итераций пишу, что метод опасный — недавно только подбирал размер для fixed-size constant pool, и наблюдал картину, когда при среднем числе проб в 1.05 были отдельные записи, имевшие 5-7. И пропадали они только уже при совсем низком loadFactor-е, что-то вроде 0.3
Вот например: рехэшироваться в зависимости от какой-то метрики качества текущего layout-а — это, конечно, сильная идея. Вот только по хорошему надо ориентироваться на среднее число попыток по всем ключам (а еще лучше — на среднее с весом частоты использования ключа). А его считать штука гораздо более tricky…
Я почему про максимальное число итераций пишу, что метод опасный — недавно только подбирал размер для fixed-size constant pool, и наблюдал картину, когда при среднем числе проб в 1.05 были отдельные записи, имевшие 5-7. И пропадали они только уже при совсем низком loadFactor-е, что-то вроде 0.3
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Trove 4.0? Примитивы в стандартном каркасе коллекций из Java 8