>И, кстати, а если я пишу на системном уровне и ЗНАЮ, что переменная выравнена и не хочу никакого дополнительного выравнивания и мне нужно получить atomic-чтение?
Разве в новом стандарте нет явных барьеров памяти — как раз для тех, кто любит пожесче? По-моему, были.
А у volatile в С просто недоопределенная семантика. С ним не связано никаких барьеров памяти, это только барьер уровня компилятора. То есть компилятор-то в нужном месте выдаст store/load, а вот процессору ничего не помешает поспекулировать. Поэтому используя volatile вы вынуждены закладываться на детали какой-то конкретной железной (процессорной) модели памяти — например на то, что x86 использует total store order, и не переставляет записи. Гораздо лучше иметь возможность явно сказать «здесь я хочу семантику release», и чтобы компилятор сам в зависимости от target платформы подставил нужное.
Про стоимость атомарных операций — порядок-таки изменился: uncontended lock xadd на Sandy Bridge стоит 3ns/op — это где-то десяток «обычных» инструкций.
Стоимость атомарных операций действительно может скакать на порядки в зависимости от состояния кэша: если нужная строка уже в вашем кэше и в M/E-state — стоимость будет минимальной, иначе придется долго ждать либо загрузки из основной памяти/L2/L3, либо — что еще хуже — арбитрации за владение строкой с другим ядром. Но все то же самое применимо и к обычной, не-атомарной последовательности read-modify-write — любая запись требует строку в L1 в M/E-state, и поэтому бОльшая часть затрат в неудачном варианте уходит именно на то, чтобы ее туда затащить. Разница между атомарными RMW и не-атомарными RMW в основном как раз в барьерах памяти — в неатомарном варианте высокую стоимость записи в неудачном варианте процессор может (если повезет) самортизировать за счет буферизации и спекулятивного исполнения. У атомиков же, как правило, есть семантика барьера, и потому возможности спекуляции сильно ограничены — и потому большую стоимость записи (которая ничем особо не специфична для атомиков — запись сама по себе дорогая) не удается замаскировать. Я недавно писал об этих вещах (и там в комментариях привели ссылку на статью с более детальными и современными бенчмарками инструкций синхронизации)
Основная причина вовсе не security manager — final-поля (и особенно static final) очень агрессивно инлайнятся. И, согласно спецификации, компилятор вовсе не обязан следить за их последующими изменениями. То есть даже если у вас получится поле изменить — вы не можете быть уверенным, что ваш код будет видеть новое значение
Я вот уже не в первый раз и прихожу к выводу, что все-таки универсальная и быстрая хэш-таблица это миф. Нужно специализироваться под конкретные данные.
Вот например: рехэшироваться в зависимости от какой-то метрики качества текущего layout-а — это, конечно, сильная идея. Вот только по хорошему надо ориентироваться на среднее число попыток по всем ключам (а еще лучше — на среднее с весом частоты использования ключа). А его считать штука гораздо более tricky…
Я почему про максимальное число итераций пишу, что метод опасный — недавно только подбирал размер для fixed-size constant pool, и наблюдал картину, когда при среднем числе проб в 1.05 были отдельные записи, имевшие 5-7. И пропадали они только уже при совсем низком loadFactor-е, что-то вроде 0.3
Вместо него считалось число итераций, и, когда оно переваливало за некий порог (скажем, capacity ^ 1/3), таблица увеличивалась.
Не очень понял — вы считали максимальное количество проб? Разве это не опасный способ — если ситуация объективно вырожденная (кто-то записал 100 объектов с одинаковым хэшкодом), то таблица будет ресайзиться до опупения…
Мы начинаем с честного виртуального вызова call object._vtable[index].
Какое-то время собираем статистику точек назначения. Получаем профиль типа
90% — impl1
8% — impl2
2% — others+
Теперь JIT рекомпилирует код примерно в такой:
И потом ветки 1-2 уже могут быть оптимизированы еще дальше — например, методы вклеены. Все правильно?
Теперь у меня такой вопрос — после оптимизирующей рекомпиляции сбор статистики продолжается? Т.е. если профиль исполнения в какой-то момент изменится — случится ли ре-оптимизация?
JIT видит вызов THashMap.get(). Есть перегруженные версии? — нет, ок, ставим проверку-охрану и инлайним. Внутри видим TObjectHash.index() — есть перегруженные версии? — да, аж 5 штук. Насколько я знаю, сейчас JIT пытается делать девиртуализацию до 3-4, потом просто честно ставит virtual call. Но даже девиртуализация на 3-4 версии уже не очень хорошо, потому что там же будет условный переход, который тоже еще непонятно как предсказываться будет. Лучше, чтобы была только одна реализация, конечно.
Я, конечно, не уверен, это мое представление. Чтобы быть уверенным надо делать бенчмарк с одновременным использованием нескольких реализаций, греть его, и смотреть дизасм.
А вы не знаете конкретнее о порогах размеров методов, которые учитываются ГИТом ХотСпота?
Можно вывести -XX:+PrintFlagsFinal, и грепнуть там что-то вроде InlineThreshold. Но я думаю, на это не стоит закладываться.
Что при строго определенном характере ключей и строго определенном размере таблицы, будет много коллизий? Это из серии «лучше быть здоровым и богатым, чем бедным и больным». Один рехеш на новый размер — и все коллизии ушли.
Я уже сам не могу понять, чего здесь не понятного: в реальности у вас не будет идеального хэша, кроме очень частных случаев когда множество ключей заранее известно и фиксировано, и вы можете попробовать подобрать perfect hash. В остальных случаях (даже для примитивов) распределение ключей по слотам таблицы не будет равномерным никогда. В chaining небольшие неоднородности почти не сказываются на производительности вплоть до очень высокой загрузки. В ОА чувствительность к неоднородностям гораздо выше — очень высока для линейного хэширования, чуть менее но все равно высока для двойного, и очень быстро растет с увеличением загрузки. Посмотрите же таблицы в статье, там в одном из экспериментов с линейным хэшированием для заполнения 0.6, например, при равномерном распределении ключей среднее число проб 1.75, а при неравномерном урезанном гауссе — 2170. Увеличение в 1000 раз по сравнению с теорией вас не достаточно впечатляет? Что там вы говорили про 30 шагов бинарного поиска, которые вас не устраивают?..
В норме пропусков и отдельных ключей нет, но вообще может быть и случай, близкий к случайным ключам.
А вы считали среднее число проб в этом вашем случае?
Этого делать не стоит, потому что если у вас будет множество реализаций, скажем, метода index(), то JIT не сможет сделать эффективную девиртуализацию, а без девиртуализации невозможен инлайнинг, который за собой тянет возможность целого ряда оптимизаций — за счет расширения контекста.
У меня, наоборот, была идея, которую я не успел протестировать: вот сейчас в trove direct hit & probing реализованы в одном методе index(...). Я бы попробовал пробинг вынести в отдельный метод — т.е сделать типа
index(){
check direct hit
if( hit ) -> return values[index];
else -> return probingStartingWith(....);
}
Мотивация такая: уменьшая размер метода, и упрощая его структуру мы увеличиваем шансы на его инлайнинг. Инлайнинг кода для direct hit кажется очень полезным, потому что это (в нормальных условиях) тотально доминирующая ветка, при этом она очень короткая и простая, и будучи вклееной может потом быть заредуцирована дальше компилятором по самое нехочу. Инлайнинг же пробинга не особо полезен, потому что кода там сильно больше, а вероятность его исполнения сильно меньше, он сложнее, и вряд ли там что-то дальше особо наоптимизировать сильно удастся, только общий размер кода увеличится.
хеши в определенном смысле «идеальны» по определению
Именно что «в определенном» — плохой с точки зрения 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% памяти вы не можете получить какой-то особо большой прирост производительности по сравнению с отсортированным массивом как реперной точкой, ведь бесплатный сыр бывает только в мышеловке. Но проблема в том, что вы получаете непредсказуемую производительность, очень сильно зависящую от расклада ключей. На мой взгляд, большинство бизнес-приложений предпочтут в таких условиях большую стабильность призрачному выигрышу в перформансе.
Но 0,5 — действительно на глаз. Вроде не очень много, но вроде и не очень мало. Почему, например, не 0,45 или 0,55 — никакого обоснования нет.
Почему не 0.55 действительно обоснования нет. А почему не 0.8 как раз обоснование есть, и я вам его привел.
Оценка, которую вы привели — выведена в предположении (идеально) равномерной хэш-функции. Таких функций на практике не бывает. И я еще раз вам подчеркиваю особенность ОА по сравнению с цепочной таблицей — в цепочных таблицах неидеальности хэш-функции локализованы в конкретных корзинках. В ОА таблицах неидеальности хэш-функции имеют глобальный и очень паршивый эффект — они сильно ускоряют кластеризацию коллизий. Это примерно как в кристаллизации из насыщенного раствора: малые отклонения от однородности раствора резко ускоряют процесс выпадения кристаллов. Моделировать этот эффект математически довольно сложно, его проще увидеть в симуляциях.
Это одна из причин, почему j.u.HMap может себе позволить класть болт на рекомендации Кнута про простые числа, тупо иметь размер таблицы в 2^N и все еще неплохо работать даже с теми уебищными неоптимальными хэш-функциями, которые пишут в 99.9% случаев (хотя в какой-то из версий авторы-таки решили, что немного подсолить не помешает, и теперь там есть небольшой трюк чтобы сгладить-таки совсем уж плохие варианты). А trove себе такого позволить не может, и мучается с простым размером таблицы, и сопутствующим ему дорогим «честным» делением
Не забывайте, что 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, ухудшая производительность как для «своих» таблиц, так и для дефолтных.
Вы, наверное, удивитесь, но обоснование-то как раз есть — если уж вы взялись переписывать одну из известнейших библиотек коллекций, вам стоило бы хотя бы разбираться в теме хэш-таблиц на уровне повыше, чем статья из русской википедии. Собственно, я и задал этот вопрос чтобы проверить, понимаете ли вы вообще ту структуру данных, которую реализуете.
Так вот, для хэштаблиц с открытой адресацией качество хэшфункции гораздо важнее, чем для «классических», с линейными списками коллизий. Причина этого в том, что «корзинки» в таблицах с линейными списками изолированы друг от друга — если у вас хэш-функция имеет неравномерное распределение, то переполненными рискуют оказаться только отдельные, неудачные корзинки, в остальных же время поиска останется малым. Для открытой адресации это не так — у вас общий массив, и коллизия по одному индексу означает не только то, что по этому индексу 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 и выше, что считается плохим показателем.
Правильно ли я понял, что вы, используя trove-вовский алгоритм хэштаблиц, используете load-factor=0.8? Если да, то почему именно такой, и почему авторы trove сами до такого не догадались?
Ну вот в этом и состоит вопрос:
1. Понимает ли кандидат инструменты, которые использует — или для него они просто «магия»?
2. Сможет ли он понять, какой на самом деле у него получится алгоритм сортировки — если убрать условные границы абстракций? Что получится, если quicksort реализовать поверх страничной организации памяти?
3. Как следствие из 2 — как будет масштабироваться решение?
И ваши вопросы тоже любопытны. Знает ли кандидат, как зависит скорость чтения от размера прочитываемого за раз буфера? Догадался ли он когда-либо это измерить, может ли он объяснить получившуюся зависимость?
Понимает ли кандидат, чем лимитируется скорость сортировки в разных условиях? Можно ли ускориться распараллеливая задачу, и когда это может сработать?
Если мы говорим о яве — там есть свои тонкости использования отображения файлов, и всяких новомодных технологий IO…
Вот так вот из одной-единственной «справочной» задачи можно кучу всего узнать про то, кто из себя кандидат как инженер.
т.е. временно зависящем от прихоти вашего настроения человеком.
А в чем именно человек зависит от моей прихоти? Собеседования, вроде, дело добровольное, с пистолетом у виска никто не стоит. Что-то не нравится — скажи. Кажется, что тебя спрашивают не о том, что ты считаешь своей сильной стороной — скажи. Кардинально не нравятся люди и атмосфера — скажи и уходи.
Мне кажется, что вы просто перекладываете ответственность за свой комфорт на других людей. Собеседование — это обоюдный процесс. Да, есть определенные традиции — не принято, например, чтобы кандидат спрашивал собеседующих знают ли они quicksort :) — но смысл их именно в том, что компания-то покупает его навыки, поэтому имеет право товар посмотреть. А кандидат навыки продает — поэтому должен их показать, а покупает зарплату/соцпакет/возможность самореализации/общую атмосферу/т.п. — и про это он имеет полное право спрашивать, а мы стараемся отвечать.
Я могу сказать про свои ощущения от собеседований. Собеседование с умеющим думать кандидатом — это очень драйвовый процесс. Наблюдать за тем, как умный человек решает проблемы — очень приятно, и очень подхлестывает, свой собственный мозг сразу ускоряется :) А собеседование со слабым слабым кандидатом вызывает ощущение неловкости. Как будто человек просто не в том месте оказался. Наслаждения от власти нет ни там, ни там.
ваша названная позиция оказалась мягче… нежели она поставлена в статье
Ну так затем-то (среди прочего) у нас и два собеседущих — у каждого немного свой взгляд, каждый дает свою независимую оценку.
Вообще, у меня создается ощущение, что вы думаете — мы тут весь курс алгоритмики спрашиваем. Нет конечно — я сам его не помню. Мы берем 2-3 далеко не самых сложных примера, масштаба quicksort, и пляшем вокруг них. На практике этого более чем достаточно — стиль мышления уже виден, а конкретные сложные алгоритмы можно и в википедии нагуглить, это совершенно верно.
алгоритмы изобретать не надо
Я тут не соглашусь — для меня готовый ответ действительно полезен только тогда, когда я сам потратил какое-то время на попытки его изобрести. Работающий ответ должен запоминаться не сам по себе, а в комплекте с несколькими неработающими — чтобы было понятно, почему именно он рабочий, а другие — нет. Иначе никакого «формирования образа мышления» не происходит, происходит просто тренировка памяти.
Да и то, всё равно дважды накололся, изобретая самостоятельно «подсчёт площади участков диаграммы Вороного» и «интеграл по контуру для вычисления принадлежности точки полигону».
Если мне удается переизобрести какой-то алгоритм — для меня это много радости, и повод собой погордиться. Во-первых теперь его хрен забудешь, а во-вторых — значит мозг-то еще работает :)
Я с удовольствием приму такой ответ, если кандидат сумеет объяснить, как примерно работает mmap, как будет ОС кэшировать содержимое файла, как согласуется страничная организация памяти со структурой обхода данных quicksort-ом, и сколько примерно «лишних» операций доступа к диску будет сделано.
И отдельный плюс если сумеет рассказать, как все это масштабируется до файла в 1Tb при наличии памяти в 1Gb.
Во-первых, я не понимаю противопоставления «либо основы либо практика». Лично я считаю, что должны быть и твердые основы, и наличие обширной практики. Но если уж выбирать, то я категорически не согласен с тем, что наличие кучи практических знаний при давно забытом фундаменте предпочтительно — для меня все как раз наоборот, и тому есть масса причин.
Во-первых, есть вопрос собеседования как такового. На нем предпочтительнее интересоваться фундаментом, потому что это такой общий знаменатель. Про VISA и X.25 человек может знать или не знать — это ровным счетом ничего не говорит о его способностях, а только лишь об истории его карьеры (я, например, совершенно не понимаю о чем вы :). А вот с основами человек не мог не сталкиваться за годы работы — и отсутствие знаний в этих областях действительно говорит о человеке — об отсутствии любопытства, например, отсутствии дотошности и желания разбираться в деталях.
Кроме того, мне кажется очень показательным что вы называете этот фундамент «справочными данными» — т.е. чем-то статическим, что надо просто зазубрить. Для меня это вовсе не тупая информация для зазубривания, а кладезь идей, методов решения задач. «Математику уж затем учить следует, что она ум в порядок приводит» — вот примерно то же самое я могу сказать про те «справочные данные» о которых мы спрашиваем: они формируют определенный — инженерный --способ мышления. Дело ведь не в том, знает ли человек уже готовые ответы — дело в том, сможет ли он решить указываемые проблемы. Если он сможет генерировать сильные идеи сам, прямо из воздуха — отлично, может, ему и правда не нужно учить основы раз уж он такой гений. Только такие гении совсем не часто встречаются.
Еще раз — важно не то, знает ли человек готовые ответы. Важно то, как он будет решать указанные проблемы (еще лучше, если человек сам замечает эти проблемы). Мы не экзамен в вузе принимаем — мы смотрим на вполне практический навык, навык решения проблем.
Если вы шли в эту компанию потому, что увидели направление А, Б и Жо в их вакансии, а вы ищете работу как раз с этими направлениями — разве это не является ответом на вопрос «почему именно к нам»? «Я ищу такие-то вещи, у вас они — по крайней мере в вакансии — есть, вот и пришел к вам сориентироваться на месте».
Вы думаете, что от вас ждут ответа в духе «вы крупная и перспективная, динамично развивающаяся компания с твердыми лидирующими позициями на мировом рынке»? — да побойтесь бога, техническим специалистам все эти маркетинговые изыски глубоко параллельны.
Разве в новом стандарте нет явных барьеров памяти — как раз для тех, кто любит пожесче? По-моему, были.
А у volatile в С просто недоопределенная семантика. С ним не связано никаких барьеров памяти, это только барьер уровня компилятора. То есть компилятор-то в нужном месте выдаст store/load, а вот процессору ничего не помешает поспекулировать. Поэтому используя volatile вы вынуждены закладываться на детали какой-то конкретной железной (процессорной) модели памяти — например на то, что x86 использует total store order, и не переставляет записи. Гораздо лучше иметь возможность явно сказать «здесь я хочу семантику release», и чтобы компилятор сам в зависимости от target платформы подставил нужное.
Стоимость атомарных операций действительно может скакать на порядки в зависимости от состояния кэша: если нужная строка уже в вашем кэше и в M/E-state — стоимость будет минимальной, иначе придется долго ждать либо загрузки из основной памяти/L2/L3, либо — что еще хуже — арбитрации за владение строкой с другим ядром. Но все то же самое применимо и к обычной, не-атомарной последовательности read-modify-write — любая запись требует строку в L1 в M/E-state, и поэтому бОльшая часть затрат в неудачном варианте уходит именно на то, чтобы ее туда затащить. Разница между атомарными RMW и не-атомарными RMW в основном как раз в барьерах памяти — в неатомарном варианте высокую стоимость записи в неудачном варианте процессор может (если повезет) самортизировать за счет буферизации и спекулятивного исполнения. У атомиков же, как правило, есть семантика барьера, и потому возможности спекуляции сильно ограничены — и потому большую стоимость записи (которая ничем особо не специфична для атомиков — запись сама по себе дорогая) не удается замаскировать. Я недавно писал об этих вещах (и там в комментариях привели ссылку на статью с более детальными и современными бенчмарками инструкций синхронизации)
Вот например: рехэшироваться в зависимости от какой-то метрики качества текущего layout-а — это, конечно, сильная идея. Вот только по хорошему надо ориентироваться на среднее число попыток по всем ключам (а еще лучше — на среднее с весом частоты использования ключа). А его считать штука гораздо более tricky…
Я почему про максимальное число итераций пишу, что метод опасный — недавно только подбирал размер для fixed-size constant pool, и наблюдал картину, когда при среднем числе проб в 1.05 были отдельные записи, имевшие 5-7. И пропадали они только уже при совсем низком loadFactor-е, что-то вроде 0.3
Не очень понял — вы считали максимальное количество проб? Разве это не опасный способ — если ситуация объективно вырожденная (кто-то записал 100 объектов с одинаковым хэшкодом), то таблица будет ресайзиться до опупения…
Мы начинаем с честного виртуального вызова call object._vtable[index].
Какое-то время собираем статистику точек назначения. Получаем профиль типа
90% — impl1
8% — impl2
2% — others+
Теперь JIT рекомпилирует код примерно в такой:
И потом ветки 1-2 уже могут быть оптимизированы еще дальше — например, методы вклеены. Все правильно?
Теперь у меня такой вопрос — после оптимизирующей рекомпиляции сбор статистики продолжается? Т.е. если профиль исполнения в какой-то момент изменится — случится ли ре-оптимизация?
Я, конечно, не уверен, это мое представление. Чтобы быть уверенным надо делать бенчмарк с одновременным использованием нескольких реализаций, греть его, и смотреть дизасм.
Можно вывести -XX:+PrintFlagsFinal, и грепнуть там что-то вроде InlineThreshold. Но я думаю, на это не стоит закладываться.
Я уже сам не могу понять, чего здесь не понятного: в реальности у вас не будет идеального хэша, кроме очень частных случаев когда множество ключей заранее известно и фиксировано, и вы можете попробовать подобрать perfect hash. В остальных случаях (даже для примитивов) распределение ключей по слотам таблицы не будет равномерным никогда. В chaining небольшие неоднородности почти не сказываются на производительности вплоть до очень высокой загрузки. В ОА чувствительность к неоднородностям гораздо выше — очень высока для линейного хэширования, чуть менее но все равно высока для двойного, и очень быстро растет с увеличением загрузки. Посмотрите же таблицы в статье, там в одном из экспериментов с линейным хэшированием для заполнения 0.6, например, при равномерном распределении ключей среднее число проб 1.75, а при неравномерном урезанном гауссе — 2170. Увеличение в 1000 раз по сравнению с теорией вас не достаточно впечатляет? Что там вы говорили про 30 шагов бинарного поиска, которые вас не устраивают?..
А вы считали среднее число проб в этом вашем случае?
У меня, наоборот, была идея, которую я не успел протестировать: вот сейчас в trove direct hit & probing реализованы в одном методе index(...). Я бы попробовал пробинг вынести в отдельный метод — т.е сделать типа
Мотивация такая: уменьшая размер метода, и упрощая его структуру мы увеличиваем шансы на его инлайнинг. Инлайнинг кода для direct hit кажется очень полезным, потому что это (в нормальных условиях) тотально доминирующая ветка, при этом она очень короткая и простая, и будучи вклееной может потом быть заредуцирована дальше компилятором по самое нехочу. Инлайнинг же пробинга не особо полезен, потому что кода там сильно больше, а вероятность его исполнения сильно меньше, он сложнее, и вряд ли там что-то дальше особо наоптимизировать сильно удастся, только общий размер кода увеличится.
Именно что «в определенном» — плохой с точки зрения oahm хэш это не только такой, когда все ключи отображаются в 1, но и такой, когда заметная часть используемых в конкретной таблице ключей отображаются в один слот. У примитивов хэши «универсально» хорошие — все множество возможных int-ов равномерно отображается во множество хэшей, да. Но в таблицу-то вы складываете не произвольные int-ы, а какие-то конкретные. И если у вас размер таблицы 17, а кладете вы туда ключи, среди которых, скажем, преобладают ключи вида 17*i+3, то у вас и будет неравномерное распределение ключей по слотам (а не ключей по хэшам). И легко видеть, что это проблема именно конкретной схемы организации хэштаблицы, а не хэша как такового: положи вы тот же набор ключей в j.u.HM с размером 16 — все будет шоколадно.
Это вы зря. Трувовские Map<Object,Object> очень даже полезны, потому что и по занимаемой памяти (с нормальной загрузкой 1/2) делают стандартные в разы, и по производительности тоже
Я думаю, это не «историческое» решение, а именно попытка написать более-менее универсальную библиотеку, работающую не только с вылизанными до блеска хэш-функциями — потому что линейное хэширование гиперчувствительно к качеству хэша. HPPC, видимо, как раз заточено под то, что люди, которые ее пользуют, хорошо знают что делают, и готовы, если что, оплатить похороны за свой счет.
Все украдено до нас: How caching affects hashing — мой краткий пересказ статьи, из которой я взял примерно половину той мудрости, которую пытаюсь тут донести :) Ссылка на оригинал там тоже присутствует, и там как раз и есть экспериментальные цифры, как меняется средний probe count для разных алгоритмов ОА хэширования при разных загрузках и реальных, неидеальных хэш-функциях — посмотрите, расхождение с теорией там весьма заметное.
В чем же тут позитив-то? В предсказании ветвлений важна вероятность неуспешного предсказания — потому что откат выполненных спекуляций может быть весьма дорогим. Если у вас нет сильного доминирования одной ветки над другой — это значит, что либо предсказания вообще не будет (т.е. не будет и упреждающего выполнения — тупо теряем такты), либо предсказание будет часто ошибаться (с сопутствующими пенальти). Даже в ваших идеальных формулах видно, что direct hit доминирует даже над первой пробой с вероятностью только alpha=loadFactor=0.8 в вашем случае. Вряд ли это можно назвать сильным доминированием.
На самом деле надо сначала понять, чего именно вы хотите. Хотите сэкономить память проиграв в производительности? — вообще-то OA и так чуть ли не самые компактные в яве, даже с дефолтной загрузкой. Если нужное еще больше — может, вам вообще использовать, скажем, отсортированный массив?
Если нужны большие объемы, то можно делать гибридные структуры типа B-trees: дерево отсортированных массивов.
Даже с хэш-таблицами: мне кажется, для больших объемов будет эффективнее сделать таблицу таблиц: разбить множество хэшей на диапазоны, и в каждом иметь свою, независимо рехеширующуюся OA хэш-таблицу — это позволит ограничить эффект неоднородностей хэша одной конкретной таблицей
Чем мне не нравится ваше решение: очевидно, что жертвуя всего 20% памяти вы не можете получить какой-то особо большой прирост производительности по сравнению с отсортированным массивом как реперной точкой, ведь бесплатный сыр бывает только в мышеловке. Но проблема в том, что вы получаете непредсказуемую производительность, очень сильно зависящую от расклада ключей. На мой взгляд, большинство бизнес-приложений предпочтут в таких условиях большую стабильность призрачному выигрышу в перформансе.
Почему не 0.55 действительно обоснования нет. А почему не 0.8 как раз обоснование есть, и я вам его привел.
Оценка, которую вы привели — выведена в предположении (идеально) равномерной хэш-функции. Таких функций на практике не бывает. И я еще раз вам подчеркиваю особенность ОА по сравнению с цепочной таблицей — в цепочных таблицах неидеальности хэш-функции локализованы в конкретных корзинках. В ОА таблицах неидеальности хэш-функции имеют глобальный и очень паршивый эффект — они сильно ускоряют кластеризацию коллизий. Это примерно как в кристаллизации из насыщенного раствора: малые отклонения от однородности раствора резко ускоряют процесс выпадения кристаллов. Моделировать этот эффект математически довольно сложно, его проще увидеть в симуляциях.
Это одна из причин, почему j.u.HMap может себе позволить класть болт на рекомендации Кнута про простые числа, тупо иметь размер таблицы в 2^N и все еще неплохо работать даже с теми
уебищныминеоптимальными хэш-функциями, которые пишут в 99.9% случаев (хотя в какой-то из версий авторы-таки решили, что немного подсолить не помешает, и теперь там есть небольшой трюк чтобы сгладить-таки совсем уж плохие варианты). А trove себе такого позволить не может, и мучается с простым размером таблицы, и сопутствующим ему дорогим «честным» делениемНе забывайте, что кроме сравнения хэшей каждая проба требует еще и чтения — т.е. это потенциальный кэш-промах. Это не актуально для линейного хэширования, где высокая локальность, да паттерн прохода по массиву идеально предсказуем, но вполне себе актуально для двойного хэширования, которое используется в trove.
Кроме того не забывайте, что вообще переход к пробам вместо прямого попадания сам по себе не бесплатен: у вас есть fast path (direct hit), простой и хорошо предсказываемый, а пробинг — это цикл, это обвязка цикла, это скачки по памяти с каким-то шагом… Это разный код, с разными характеристиками «понятности» для процессора, с разными статистическими характеристиками предсказуемости конкретных условных переходов, и т.п. Весьма разумно стараться, чтобы у direct hit было тотальное доминирование по вероятности — собственно, на это и заточен код в trove. Если вы хотите таблицу, у которой ожидаемый («крейсерский») режим функционирования — это, скажем, 5-6 проб на поиск, то под этот режим и надо писать код. Например, нет смысла тогда как-то выделять direct hit — если у него нет доминирующей вероятности то в чем его избранность? Надо все единообразно свернуть в общий цикл пробинга.
Интересный (гипотетический) эффект здесь в том, что код (непосредственно скомпилированные JIT-ом байтики) будет общий, как для тех таблиц, где по-умолчанию load factor = 0.5, так и для ваших, с lf=0.8. При этом статистические свойства условных переходов будут сильно отличаться — а статистика предсказателя ветвлений привязана ведь к коду, а не к данным. Т.е. вы своим выбором нетривиального lf можете сбивать с толку hardware branch predictor, ухудшая производительность как для «своих» таблиц, так и для дефолтных.
Так вот, для хэштаблиц с открытой адресацией качество хэшфункции гораздо важнее, чем для «классических», с линейными списками коллизий. Причина этого в том, что «корзинки» в таблицах с линейными списками изолированы друг от друга — если у вас хэш-функция имеет неравномерное распределение, то переполненными рискуют оказаться только отдельные, неудачные корзинки, в остальных же время поиска останется малым. Для открытой адресации это не так — у вас общий массив, и коллизия по одному индексу означает не только то, что по этому индексу 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 и выше, что считается плохим показателем.
1. Понимает ли кандидат инструменты, которые использует — или для него они просто «магия»?
2. Сможет ли он понять, какой на самом деле у него получится алгоритм сортировки — если убрать условные границы абстракций? Что получится, если quicksort реализовать поверх страничной организации памяти?
3. Как следствие из 2 — как будет масштабироваться решение?
И ваши вопросы тоже любопытны. Знает ли кандидат, как зависит скорость чтения от размера прочитываемого за раз буфера? Догадался ли он когда-либо это измерить, может ли он объяснить получившуюся зависимость?
Понимает ли кандидат, чем лимитируется скорость сортировки в разных условиях? Можно ли ускориться распараллеливая задачу, и когда это может сработать?
Если мы говорим о яве — там есть свои тонкости использования отображения файлов, и всяких новомодных технологий IO…
Вот так вот из одной-единственной «справочной» задачи можно кучу всего узнать про то, кто из себя кандидат как инженер.
А в чем именно человек зависит от моей прихоти? Собеседования, вроде, дело добровольное, с пистолетом у виска никто не стоит. Что-то не нравится — скажи. Кажется, что тебя спрашивают не о том, что ты считаешь своей сильной стороной — скажи. Кардинально не нравятся люди и атмосфера — скажи и уходи.
Мне кажется, что вы просто перекладываете ответственность за свой комфорт на других людей. Собеседование — это обоюдный процесс. Да, есть определенные традиции — не принято, например, чтобы кандидат спрашивал собеседующих знают ли они quicksort :) — но смысл их именно в том, что компания-то покупает его навыки, поэтому имеет право товар посмотреть. А кандидат навыки продает — поэтому должен их показать, а покупает зарплату/соцпакет/возможность самореализации/общую атмосферу/т.п. — и про это он имеет полное право спрашивать, а мы стараемся отвечать.
Я могу сказать про свои ощущения от собеседований. Собеседование с умеющим думать кандидатом — это очень драйвовый процесс. Наблюдать за тем, как умный человек решает проблемы — очень приятно, и очень подхлестывает, свой собственный мозг сразу ускоряется :) А собеседование со слабым слабым кандидатом вызывает ощущение неловкости. Как будто человек просто не в том месте оказался. Наслаждения от власти нет ни там, ни там.
Знаете почему, кстати? Потому что у нас, программистов, власти и так хватает :)
Ну так затем-то (среди прочего) у нас и два собеседущих — у каждого немного свой взгляд, каждый дает свою независимую оценку.
Вообще, у меня создается ощущение, что вы думаете — мы тут весь курс алгоритмики спрашиваем. Нет конечно — я сам его не помню. Мы берем 2-3 далеко не самых сложных примера, масштаба quicksort, и пляшем вокруг них. На практике этого более чем достаточно — стиль мышления уже виден, а конкретные сложные алгоритмы можно и в википедии нагуглить, это совершенно верно.
Я тут не соглашусь — для меня готовый ответ действительно полезен только тогда, когда я сам потратил какое-то время на попытки его изобрести. Работающий ответ должен запоминаться не сам по себе, а в комплекте с несколькими неработающими — чтобы было понятно, почему именно он рабочий, а другие — нет. Иначе никакого «формирования образа мышления» не происходит, происходит просто тренировка памяти.
Если мне удается переизобрести какой-то алгоритм — для меня это много радости, и повод собой погордиться. Во-первых теперь его хрен забудешь, а во-вторых — значит мозг-то еще работает :)
И отдельный плюс если сумеет рассказать, как все это масштабируется до файла в 1Tb при наличии памяти в 1Gb.
Во-первых, есть вопрос собеседования как такового. На нем предпочтительнее интересоваться фундаментом, потому что это такой общий знаменатель. Про VISA и X.25 человек может знать или не знать — это ровным счетом ничего не говорит о его способностях, а только лишь об истории его карьеры (я, например, совершенно не понимаю о чем вы :). А вот с основами человек не мог не сталкиваться за годы работы — и отсутствие знаний в этих областях действительно говорит о человеке — об отсутствии любопытства, например, отсутствии дотошности и желания разбираться в деталях.
Кроме того, мне кажется очень показательным что вы называете этот фундамент «справочными данными» — т.е. чем-то статическим, что надо просто зазубрить. Для меня это вовсе не тупая информация для зазубривания, а кладезь идей, методов решения задач. «Математику уж затем учить следует, что она ум в порядок приводит» — вот примерно то же самое я могу сказать про те «справочные данные» о которых мы спрашиваем: они формируют определенный — инженерный --способ мышления. Дело ведь не в том, знает ли человек уже готовые ответы — дело в том, сможет ли он решить указываемые проблемы. Если он сможет генерировать сильные идеи сам, прямо из воздуха — отлично, может, ему и правда не нужно учить основы раз уж он такой гений. Только такие гении совсем не часто встречаются.
Еще раз — важно не то, знает ли человек готовые ответы. Важно то, как он будет решать указанные проблемы (еще лучше, если человек сам замечает эти проблемы). Мы не экзамен в вузе принимаем — мы смотрим на вполне практический навык, навык решения проблем.
Вы думаете, что от вас ждут ответа в духе «вы крупная и перспективная, динамично развивающаяся компания с твердыми лидирующими позициями на мировом рынке»? — да побойтесь бога, техническим специалистам все эти маркетинговые изыски глубоко параллельны.