Haskell

28 Apr 2024 09:24

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

Haskell

28 Apr 2024 06:56

Как у тебя интмап медленне ордмапы получился?

Haskell

28 Apr 2024 01:38

Вот для сравнения что было в 0.1.1.4, там хешмапа еще хорошо держалась. (Там приходится заменить VH.lookup' на fromMaybe 0 <$> VH.lookup, потому что первое внезапно аллоцирует)

Haskell

28 Apr 2024 01:24

\g f -> f (g f)

Haskell

27 Apr 2024 19:41

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

Haskell

27 Apr 2024 19:39

Ну я не обязательно про полные коллизии когда хеши совпали, а про "hash mod size" коллизии

Haskell

27 Apr 2024 19:37

так-то есть одна таблица, там дела ещё лучше чем у vht

Haskell

27 Apr 2024 19:36

Ну я ж не говорю что v-h плохи, просто делать вывод что очень хороши на основании только этого бенча имхо ошибочно. Если агдисты поменяли и у них на реальном коде хорошо -- то и прекрасно

Haskell

27 Apr 2024 19:36

ну и с коллизиями проблемы с производительностью у хешмапа будут токо жуже

Haskell

27 Apr 2024 19:31

Нет; доберусь до компа попробую свой откопать. (И тут не то чтобы прямо жесткие требования, этот бенчмарк что-то то меряет, просто кмк реальные юз кейсы это не особо покрывает)

Haskell

27 Apr 2024 19:29

у тебя есть ссылка на бенчмарк, который удовлетворяет требованиям?

Haskell

27 Apr 2024 19:16

вчера релиз был у vh

Haskell

03 Apr 2024 20:35

Есть stan. Ничего за него не скажу так как не пользуюсь. Есть альтернативные Prelude без частичных функций. Пользуюсь Universum. Норм.

Haskell

03 Apr 2024 20:32

Хорошо. Но -Weverything

Haskell

03 Apr 2024 20:31

-werror=incomplete-patterns?

Haskell

28 Apr 2024 09:16

вылезание из кеша процессора прост превращает бенчмарк таблицы в бенчмарк памяти, на результаты которого довольно сложно повлиять меняя че-то в имплементации таблицы

Haskell

28 Apr 2024 02:10

И вот разница между последовательными и рандомными ключами и поиском в порядке вставки и случайном. Это все vector-hashtables unboxed (0.1.2.0), но разные данные.

На небольших размерах разница небольшая, вероятно в бранч предикторе — при последовательных ключах разницы в порядке поиска нет (все в кешах; любой поиск завершается после ровно одной итерации пробинга), при рандомных ключах поиск в рандомном порядке не дает бранч предиктору выучить паттерн пробинга.

На средних размерах все кроме seq/unshuffled начинает страдать, вероятно потому что приходится ходить все в более далекие кеши, хардварный префетчинг ни с чем кроме seq/unshuffled (где доступ последовательный) не справляется.

На больших размерах ходить при кешмисах приходится уже в память, поэтому разница становится огромной, 40+ (!!!) раз между seq/unshuffled и random/shuffled на миллионах элементов (на моем железе, это все по идее должно сильно зависеть от памяти и кешей)

(https://gist.github.com/aadaa-fgtaa/12ad7c5828cdf00b9734d0d0b035b8e7)

Haskell

28 Apr 2024 01:26

Так, вот моя попытка в более-менее нормальный бенчмарк: https://gist.github.com/aadaa-fgtaa/114620ab45c69a042f9996a6e7c4cf8a. И vector-hashtables == 0.1.2.0 наконец-то обходит всю иммутабельщину даже на крошечных размерах на этом бенче 🎉

Haskell

28 Apr 2024 01:24

неправда, у него слишком длинное определение. Правильный ответ: owl — у него лучшее соотношение размер/прикольность

Haskell

27 Apr 2024 19:39

(это на это должн был быть ответ)

Haskell

27 Apr 2024 19:38

https://github.com/1Jajen1/Brokkr/tree/main/brokkr-hashtables

Haskell

27 Apr 2024 19:37

ну, понятно, нужно больше бенчмарков

Haskell

27 Apr 2024 19:36

всеж ходить по массиву быстрее, чем по списку

Haskell

27 Apr 2024 19:34

да с коллизиями-то понятно, что плохо будет. но емнип в этом апексе выше ключи будут такие же, 1,2,3...

Haskell

27 Apr 2024 19:30

пример типа, хэша и shuffle или что-то более подходящее

Haskell

27 Apr 2024 19:27

Бенчмарк в vector-hashtables у вас кстати имхо очень сомнительный, если я правильно смотрю (я с телефона, мог что-то проглядеть):
- Ключи 1..n, hash @Int = id, поэтому вообще нет коллизий
- Ключи 1..n именно в этом порядке. hash @Int = id, поэтому доступ к buckets происходит строго последовательный, что весьма cache-friendly
- Поиск идёт в том же порядке что и вставка (то есть аллокация поэтому Entry), поэтому доступ к fhashCode, fkey и fvalue строго последовательный, опять же cache-friendly
- (это сейчас не влияет потому что коллизий нет, но для полноты) поиск/вставка всегда одинаковых ключей в одинаковом порядке, на не слишком больших размерах бранч предиктор должен между итерациями бенча выучить probe sequences, то есть не миспредиктить в этой ли ентри ключ или нужно искать дальше

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

Haskell

03 Apr 2024 21:23

Но тоже иногда порет, но его хотя бы настроить можно. Stan вообще без руля рулит..

Haskell

03 Apr 2024 20:34

Кто такие maybe-функции? Не head с tail-ом случайно?

Haskell

03 Apr 2024 20:32

Дайте человеку нормально вопрос задать!

Haskell

03 Apr 2024 20:30

Что забыли учесть? Что такое maybe-функция?