История изменений

Мужик двигает прогресс. Тут как с фундаментальной наукой: копошатся-копошатся – а потом ррраз! и выстрелило

Что «выстрелило»? На 10% повысилась производительность и снизилось потребление памяти? Хэш-таблица — это случайно-оптимальный способ организации ассоциативного массива для конкретной архитектуры процессора.

Случайно — потому что возможно подобрать набор данных, который положит хэш-таблицу так, что она станет хуже связанного списка с полным перебором поиска O(N). Примерно как с Quicksort, который на специально сформированных массивах данных дает stack overflow — если учитывать этот недостаток, то у него не может быть масштабируемости O(N*logN).

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

Для конкретной архитектуры процессора — потому что ориентирован на конкретную модель работы с памятью, то есть медленное чтение данных из оперативы кэш-линиями — отсюда ориентация на «уместить данные одного запроса в минимум кэш линий». Он даже умудрился привязаться к SSE2. Но он в жизни не сможет свой хэш натянуть на GPGPU, которая организована иначе. где канал оперативы и шире, и быстрее, но при этом возникает необходимости выполнять сразу несколько операций за раз. На FPGA оно уже совсем никак не налазит, потому что там уже нет никаких кэш-линий.

Ну и последний гвоздь в крышку гроба: хэш-таблица — это фундаментально однопоточный-однопользовательский алгоритм. А сейчас у нас актуальна какая проблема? Много ядер и нельзя их использовать. А чтобы их использоваться, нужно применять многоверсионную структуру данных, нужно распределять данные не по случайному хэшу, а «подобное к подобному», а отсюда ключем должна быть строка или другая семантическая единица, и тогда его безликий хэш оказывается в пролете. То есть, его презентация устарела еще до того, как вышла в публику.

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

«все плоды творчества этого чела», подозреваю, ни тебе, ни мне неизвестны

Может быть там есть здоровые склонности, но в данном случае я отвечаю не ему, а тебе. Ты восхищаешься его лекцией, а я, например, нет — и я пояснил почему. Я мог бы сделать хэши не хуже, но только за очень хорошие деньги — иначе смысла в этом нет. А «смысл» — это ускорить работу уже имеющегося в гугле кода, который в большинстве своем написан «на отлюбись» и его не хотят переписывать. Ускорять работу устаревшего говна — это совсем не «двигать прогресс». Я согласен с тем, что одними увольнениями много не наоптимизируешь, но как минимум так можно сократить количество устаревшего софта, который прямо сейчас, в 2021, плодится угрожающими темпами, он устарел еще до того, как был написан, потому что ум программистов прочно застрял где-то в 80-90-х, и уже монорепа гугла перевалила за два миллиарда строк.

Мужик двигает прогресс. Тут как с фундаментальной наукой: копошатся-копошатся – а потом ррраз! и выстрелило

Что «выстрелило»? На 10% повысилась производительность и снизилось потребление памяти? Хэш-таблица — это случайно-оптимальный способ организации ассоциативного массива для конкретной архитектуры процессора.

Случайно — потому что возможно подобрать набор данных, который положит хэш-таблицу так, что она станет хуже связанного списка с полным перебором поиска O(N). Примерно как с Quicksort, который на специально сформированных массивах данных дает stack overflow — если учитывать этот недостаток, то у него не может быть масштабируемости O(N*logN).

Для конкретной архитектуры процессора — потому что ориентирован на конкретную модель работы с памятью, то есть медленное чтение данных из оперативы кэш-линиями — отсюда ориентация на «уместить данные одного запроса в минимум кэш линий». Он даже умудрился привязаться к SSE2. Но он в жизни не сможет свой хэш натянуть на GPGPU, которая организована иначе. где канал оперативы и шире, и быстрее, но при этом возникает необходимости выполнять сразу несколько операций за раз. На FPGA оно уже совсем никак не налазит, потому что там уже нет никаких кэш-линий.

Ну и последний гвоздь в крышку гроба: хэш-таблица — это фундаментально однопоточный-однопользовательский алгоритм. А сейчас у нас актуальна какая проблема? Много ядер и нельзя их использовать. А чтобы их использоваться, нужно применять многоверсионную структуру данных, нужно распределять данные не по случайному хэшу, а «подобное к подобному», а отсюда ключем должна быть строка или другая семантическая единица, и тогда его безликий хэш оказывается в пролете. То есть, его презентация устарела еще до того, как вышла в публику.

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

«все плоды творчества этого чела», подозреваю, ни тебе, ни мне неизвестны

Может быть там есть здоровые склонности, но в данном случае я отвечаю не ему, а тебе. Ты восхищаешься его лекцией, а я, например, нет — и я пояснил почему. Я мог бы сделать хэши не хуже, но только за очень хорошие деньги — иначе смысла в этом нет. А «смысл» — это ускорить работу уже имеющегося в гугле кода, который в большинстве своем написан «на отлюбись» и его не хотят переписывать. Ускорять работу устаревшего говна — это совсем не «двигать прогресс». Я согласен с тем, что одними увольнениями много не наоптимизируешь, но как минимум так можно сократить количество устаревшего софта, который прямо сейчас, в 2021, плодится угрожающими темпами, он устарел еще до того, как был написан, потому что ум программистов прочно застрял где-то в 80-90-х, и уже монорепа гугла перевалила за два миллиарда строк.