Программирование[10]

besteady написал 9 минут назад:

Vova написал 17 минут назад:

besteady написал 34 минуты назад:

std сосет во всём

 

Смотри я делаю

 

std::unordered_set<uint16_t, std::identity> m;

m.rehash(std::numeric_limits<uint16_t>::max());

 

И теперь std::unordered_set ебет все твои графики по скорости

Окей. Тут соглы. Такой уровень аутизма я тоже не готов вывозить

Гугло бенчи подразумевают что-то реальное, используемое в работе, с нормальном размером скорость/память

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

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

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

Grohuf написал 2 минуты назад:

besteady написал 12 минут назад:

Vova написал 20 минут назад:

besteady написал 37 минут назад:

std сосет во всём

 

Смотри я делаю

 

std::unordered_set<uint16_t, std::identity> m;

m.rehash(std::numeric_limits<uint16_t>::max());

 

И теперь std::unordered_set ебет все твои графики по скорости

Окей. Тут соглы. Такой уровень аутизма я тоже не готов вывозить

Гугло бенчи подразумевают что-то реальное, используемое в работе, с нормальном размером скорость/память

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

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

 

Ахахахха что простите

Цитата

Ибо такое устройство дает практически гарантированное не попадание в кэш.

Ахахахаха чтоооооо?

Grohuf написал 5 минут назад:

Насколько я знаю, в хэштаблице unordered_map хранятся не сами элементы, а указатели на списки элементов.

Нихуясе ты че даже интерфейс unordered_map знаешь

Grohuf написал 3 минуты назад:

besteady написал 12 минут назад:

Vova написал 20 минут назад:

besteady написал 37 минут назад:

std сосет во всём

 

Смотри я делаю

 

std::unordered_set<uint16_t, std::identity> m;

m.rehash(std::numeric_limits<uint16_t>::max());

 

И теперь std::unordered_set ебет все твои графики по скорости

Окей. Тут соглы. Такой уровень аутизма я тоже не готов вывозить

Гугло бенчи подразумевают что-то реальное, используемое в работе, с нормальном размером скорость/память

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

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

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

 

Да я зря байчусь углубляться в то как именно выводы об убогости стд сделаны. Нормальные челы все предусмотрели

https://github.com/google/hashtable-benchmarks/blob/main/hashtable_benchmarks.cc тут зеро кост хэш и он всем одинаковый подаётся, чтобы именно саму имплементацию контейнеров оценить

Так что стд хэш мапы именно бай дизигн медленные

Vova написал 1 минуту назад:

Ахахахаха чтоооооо?

Действительно, тиктоковский долбоеб. Что?

Grohuf написал 1 минуту назад:

Vova написал 3 минуты назад:

Ахахахаха чтоооооо?

Действительно, тиктоковский долбоеб. Что?

У Грохуфа кэш перестал работать

Срочно помогите ему

besteady написал 2 минуты назад:

Так что стд хэш мапы именно бай дизигн медленные

Самая быстрая хаш мапа это std::vector

Гугл снова пососал у std

Vova написал 1 минуту назад:

Самая быстрая хаш мапа это std::vector

Устами младенца глаголит истина.

Один долбаеб считает что memory usage можно типо не учитывать хотя там все строится на memory vs speed trade off

У другого долбаеба кэш перестал работать - видимо он хаш мапу постоянно обходит целиком и сравнивает ее перформанс с std::vector

Эпик

Vova написал 3 минуты назад:

Самая быстрая хаш мапа это std::vector

 

Гугл снова пососал у std

Так ты скажешь в чем гугло бенчи насчет std::unordered_set не правы?

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

Vova написал Только что:

Один долбаеб считает что memory usage можно типо не учитывать хотя там все строится на memory vs speed trade off

Там всем реализациям хэш таблицы даётся одинаковый хэш

Vova написал 1 минуту назад:

У другого долбаеба кэш перестал работать - видимо он хаш мапу постоянно обходит целиком и сравнивает ее перформанс с std::vector

 

Дурачок не знает, почему списки плохо кэшируются. Обалдеть. Как такой тупой проходит собеседования? Вот реально, как тесты IQ ничего не показывают, так и собеседования инчего не показывают.

besteady написал Только что:

Vova написал 1 минуту назад:

Один долбаеб считает что memory usage можно типо не учитывать хотя там все строится на memory vs speed trade off

Там всем реализациям хэш таблицы даётся одинаковый хэш

Ладно я возможно плохо отозвался о тебе сказав что ты долбаеб

Возможно тебе просто не хватает фундаментальных знаний

Какой хэш тут не при чем

Подумай на досуге зачем нужна https://en.cppreference.com/w/cpp/container/unordered_map/load_factor

Vova написал 7 минут назад:

besteady написал 9 минут назад:

Vova написал 10 минут назад:

Один долбаеб считает что memory usage можно типо не учитывать хотя там все строится на memory vs speed trade off

Там всем реализациям хэш таблицы даётся одинаковый хэш

 

Ладно я возможно плохо отозвался о тебе сказав что ты долбаеб

 

Возможно тебе просто не хватает фундаментальных знаний

 

Какой хэш тут не при чем

 

Подумай на досуге зачем нужна https://en.cppreference.com/w/cpp/container/unordered_map/load_factor

В чем тут опровержение гугл бенченй? 

В них проверяется и большой и маленький объем

besteady написал 10 минут назад:

В чем тут опровержение гугл бенченй? 

Никаких опровержений

Гугл мапа сосет по памяти если верить графику а значит она не лучше чем std ни в скорости ни в памяти

В общем случае

Vova написал 8 минут назад:

besteady написал 20 минут назад:

В чем тут опровержение гугл бенченй? 

 

Никаких опровержений

 

Гугл мапа сосет по памяти если верить графику а значит она не лучше чем std ни в скорости ни в памяти

 

В общем случае

Причём тут гугл мапа, если речь про сами бенчи 

Даже взять сайт, с которого ты взял график std сосет во всем у остальных хэш мап https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html

Std берут как бейс лайн и заменяют, если нужно

For speed efficiency. A hash map using an open addressing scheme should be your choice and I would recommend either hopscotch hashing with tsl::hopscotch_map or linear robin hood hashing with tsl::robin_map or ska::flat_hash_map.

For memory efficiency. If you are storing small objects (< 32 bytes) with a trivial key comparator, tsl::sparse_map should be your go to hash map. Even though it is quite slow on insertions, it offers a good balance between lookup speed and memory usage, even at low load factor. It is also faster than both google::sparse_hash_map and spp::sparse_hash_map while providing more functionalities.

For strings as key. If you are using strings as key, the above recommendations still hold true but you may also want to try tsl::array_map. It offers one of the best lookup speed on large strings while having the lowest memory usage. 

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

нахуя вы берете мапу, чтобы её обходить, или чтобы за О(1) искать элементы в ней периодически?

она либо маленькая и влезет в кэш целиком на твоих 5 поисков по ключу, либо нахуй никогда в нем не будет и не должна быть, тк посчитав хэш ты сука НИКОГДА не предскажешь локальность данных

Kant написал 4 минуты назад:

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

нахуя вы берете мапу, чтобы её обходить, или чтобы за О(1) искать элементы в ней периодически?

она либо маленькая и влезет в кэш целиком на твоих 5 поисков по ключу, либо нахуй никогда в нем не будет и не должна быть, тк посчитав хэш ты сука НИКОГДА не предскажешь локальность данных

Фух

Хоть у кого-то хватает нервов отвечать на эту шизу

besteady написал 9 минут назад:

Причём тут гугл мапа, если речь про сами бенчи 

Как по твоему я должен спорить с бенчами? это как спорить с тем что Путин выйграл выборы - это просто факт

Kant написал 2 минуты назад:

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

нахуя вы берете мапу, чтобы её обходить, или чтобы за О(1) искать элементы в ней периодически?

она либо маленькая и влезет в кэш целиком на твоих 5 поисков по ключу, либо нахуй никогда в нем не будет и не должна быть, тк посчитав хэш ты сука НИКОГДА не предскажешь локальность данных

Ну возьмем вырожденный случай, предлагаемый вовой. Мы обращаемся к мэп, сначала она должна найти в таблице указатель на список. Это чтение памяти - медленная операция, ибо не в кэше (слишком большой контейнер). Затем мы должны по этому указателю найти элемент списка. Он будет единственный из-за огромного размера таблицы (перемещаться нам не придется). Это второе чтение памяти.

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

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

Все это очевидно вроде как, если быть не долбоебом как Вова.

besteady написал 11 минут назад:

Даже взять сайт, с которого ты взял график std сосет во всем у остальных хэш мап https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html

Std берут как бейс лайн и заменяют, если нужно

 

For speed efficiency. A hash map using an open addressing scheme should be your choice and I would recommend either hopscotch hashing with tsl::hopscotch_map or linear robin hood hashing with tsl::robin_map or ska::flat_hash_map.

 

For memory efficiency. If you are storing small objects (< 32 bytes) with a trivial key comparator, tsl::sparse_map should be your go to hash map. Even though it is quite slow on insertions, it offers a good balance between lookup speed and memory usage, even at low load factor. It is also faster than both google::sparse_hash_map and spp::sparse_hash_map while providing more functionalities.

 

For strings as key. If you are using strings as key, the above recommendations still hold true but you may also want to try tsl::array_map. It offers one of the best lookup speed on large strings while having the lowest memory usage. 

Класс

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

Охуеть

Vova написал 3 минуты назад:

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

Не, тебе лучше писать на питоне и не думать о производительности. Для тебя идеальный вариант.