Haskell

29 Apr 2024 08:14

Привет, @Dmitry_21_12! Пройди анти-спам проверку за 1 мин.

Haskell

28 Apr 2024 12:57

спрошу тебя как до картинок доберусь

Haskell

28 Apr 2024 12:56

само собой, бенч буду пускать с той же машины, что и остальные бенчи

Haskell

28 Apr 2024 12:55

Не возражаю, но желательно проsanity-checkайте это слегка сначала. The software is provided "as is", without any warranty короче

Haskell

28 Apr 2024 12:54

ну да, если есть на что менять

Haskell

28 Apr 2024 12:53

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

Haskell

28 Apr 2024 12:50

@aadaa_fgtaa не возражаешь, если бенчмарк с картинками перенесём к нам?

Haskell

28 Apr 2024 12:46

надо попробовать тогда в таких условиях посравнивать с другими таблицами из коллинзовской либы

Haskell

28 Apr 2024 12:45

реальное приложение все время чет аллоцировать будет и даже если дерево вовсе не трогать приложение будет тормозить этим деревом об гц

Haskell

28 Apr 2024 11:53

vht медленные на операциях union, intersect. там еще есть пространство для оптимизации

Haskell

28 Apr 2024 11:45

вызывает, но один раз перед началом измерения пачки прогонов, а не после каждого прогона, просто чтобы все стартовали в равных условиях. так что сборка мусора будет учтена, но только сборка своего мусора, а не чужого ;)

Haskell

28 Apr 2024 10:23

Так тут же лукапы, никаких гц нет, 0 B allocated, 0 B copied на всех бенчах

Haskell

28 Apr 2024 10:21

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

Haskell

28 Apr 2024 09:30

Надо спросить @Bodigrim

Haskell

28 Apr 2024 09:29

Который просто меряет цпу тайм

Haskell

28 Apr 2024 15:18

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

Haskell

28 Apr 2024 12:56

На картинках кстати ось y неправильно подписана, должно быть average time per lookup

Haskell

28 Apr 2024 12:55

бывает также трейдоф между ростом и прочим, т.е. есть таблицы которые быстрее растить

Haskell

28 Apr 2024 12:55

У аады есть заготовка опен адрессинг

Haskell

28 Apr 2024 12:54

Кажется, замена реализации от роста размера это полностью ризонабл решение?

Haskell

28 Apr 2024 12:51

ну и это такая деталь реализации, что нужно в принципе другую реализацию делать

Haskell

28 Apr 2024 12:49

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

Haskell

28 Apr 2024 12:46

@swamp_agr хорошо бы и бенчмарк, и картинки утащить в vector-hashtables в README

Haskell

28 Apr 2024 11:54

сравнить vht и IntMap можно хотя

Haskell

28 Apr 2024 11:49

Возможно чтобы делать на ней не только лукапы? Из доки:

This data structure performs especially well on binary operations like union and intersection. Additionally, benchmarks show that it is also (much) faster on insertions and deletions when compared to a generic size-balanced map implementation (see Data.Map).

Haskell

28 Apr 2024 11:37

А нахрен она вообще нужна тогда, если на своей специализации сливает общему решению из соседнего же модуля.

Haskell

28 Apr 2024 10:22

Не, тут я не спорю ни секунды, пытаться обгонять хештаблицу деревом где-нибудь на 100000+ бесполезно (ну кроме каких-то жестких коллизий может быть, и то не уверен)

Haskell

28 Apr 2024 10:19

А почему бы ему не быть медленнее?

Haskell

28 Apr 2024 09:29

а гц между тестами не вызывает?

Haskell

28 Apr 2024 09:28

В бенче выше используется тести бенч