Комментарии 28
Удивительно, что в области настолько базовых структур данных, как хеш-таблицы, до сих пор можно изобрести что-то существенно новое
на одном из ресурсов где я иногда оказываюсь есть масса закостенелых "программистов" которые, когда я изобретаю велосипеды, например сбалансированное дерево с O(1) удалением, закатывают глаза и кидают минусы.
можно изобрести что-то существенно новое
и я вам скажу даже больше.
можно изобрести Хеш-таблицу с транзакциями, где 32-битные "указатели" легко и просто адресуют более 4 гигабайт: https://ders.by/cpp/deque/deque.html#7
Не открывая ссылку: если указывать не на 1 байт, а на N байт, то соответственно увеличится размер памяти. Другой вопрос - зачем?
Но у меня общий вопрос. Если алгоритм хорош в реальных, а не тестовых сценариях, и это легко проверяется (а должно быть легко), то почему он ещё не в составе всех основных библиотек всех языков? Или уже таки в составе?
Точно не при двойной адресации. Примерно похожими костылями сейчас в браузерах занимаются, чтобы длинные указатели поддержать в wasm. И оснонвая проблема, что оно становится сильно не очень cache friendly из-за подобных индирекций просто потому что в маленькие кэши не умещается.
Если вы про Swiss Tables, то в Go их уже имплементеровали
Другой вопрос - зачем?
В большинстве случаев нет никакой необходимости указывать на 1 байт, любые осмысленные данные занимают сильно больше) А так 32-битные указатели которые адресуют больше 4гб это баян которому лет 30 навскидку
А я вот не понял почему мы должны использовать настолько заполненные хеш таблицы и потом бороться с линейными временами на поиск свободного места??? Ведь О(1) это намного важнее чем экономия памяти. Если хеш таблица заполнена на 99.9% то она быстрой не может быть в принципе. А там +/- на несколько процент не имеет никакое значение.
Вот именно. Но сейчас кто-то вам скажет что он программирует плату со считанными килобайтами памяти и там это супер важно.
Экономия памяти тоже важна. Небрежное отношение к использованию памяти имеет тенденцию выносить процессорный кеш. А физическая память, неприкрытая кешом, очень медленная штука...
Я последний человек, кто скажет, что память не надо экономить. Но ведь, это же хеш таблица – она должна быть незаполненной, если хотим использовать ее по предназначению. Она так работает. А если мы вынуждены заполнять ее, чтобы сэкономить память, может лучше использовать другой алгоритм, ведь хеш таблица быстрой уже точно не будет. Ну, или другую хеш функцию – которая будет давать меньше коллизии. Ведь есть же и перфектные хеши – там хоть на 100% заполняй, все равно будет O(1).
так её как и не заполняют на 90% потому что она тормозить начинает! Хорошая практика сейчас держать её заполненой ~50%. Но если вдруг (не совсем вдруг, а благодаря улучшениям) она перестанет тормозить на 90%, а начнёт тормозить на 99% заполненности, то вполне можно будет её использовать на заполненности 90%, что сейчас считается плохой практикой. Улучшение с 50% до 90% - это 40% экономии памяти, что более чем замечательно.
улучшение с "не тормозит на 90% на "не тормозит на 99% уже не так интересно, хотя хорошо, потому что это 9% экономии памяти. А вот улучшение до 99.9% не представляет ничего кроме теоретического интереса для таблиц экзобайтных размеров :)
Вы читали статью? Вопрос не в том чтобы тормозило меньше или больше, а чтобы не тормозило вовсе – О(1) всегда будет быстрее всех. А коллизии в хеш таблице всегда будет означать отсутствие О(1), какие бы умные алгоритмы вы не придумали.
Нет конечно, никто так таблицы не заполняет. И поэтому хотя новые таблицы очень важны для теории, на практике никто их не собирается использовать, и сравнение с swiss tables бессмысленно.
Разве не вычисление хэш функции занимает основное время при работе с таблицами, в случае строк, например? А перебор ячеек это небольшой процент времени.
в шарпе все обьекты имеют ленивую ссылку на просчитанный хеш например.
up
походу только для классов, для строк каждый раз считает заново
Сравнение строк может быть очень длинным. А в случае открытой адресации у нас возможна ситуация, что данные лежат в "чужом" бакете и чтобы понять что это оно надо сравнивать ключи (ну или где-то рядом прикапывать полный хеш)
Интересно, сами по себе tiny pointers дают какой-либо выигрыш? Вот здесь https://www.reddit.com/r/ProgrammingLanguages/comments/7gzaas/tiny_relative_pointers/ несколько лет назад обсуждался подобный подход в Java, предлагалось использовать 32-битные относительные указатели в 64-битной системе. Бенчмарки показали заметную экономию памяти, но по скорости работа с такими указателями проигрывала, что немудрено, поскольку вместо того, чтобы взять адрес из одной ячейки и забрать данные из другой по этому адресу, приходится делать дополнительные действия. Здесь, как я понимаю, надо еще больше действий проделать, поскольку игра с отдельными битами идет. В целом, последние тенденции по общему ускорению работы компьютеров идут в сторону "не жалеем памяти - больше униформизма". Поэтому и используются 64-битные вычисления там, где можно обойтись и меньшей разрядностью, т.к. вся система на уровне самого процессора, памяти, контроллеров и прочего уже 64-разрядная, переключение на 32 бита выигрыша в лучшем случае не дает, а в худшем наоборот добавляет задержек. Поэтому и сегменты защищенного режима ушли в небытие, а память выделяется виртуальными страницами фиксированного размера (теоретически, правда, не всегда), ну и так далее. Да и сами странички пытаются расти в размерах.
предлагалось использовать 32-битные относительные указатели в 64-битной системе. Бенчмарки показали заметную экономию памяти, но по скорости работа с такими указателями проигрывала
у меня тоже 32-битные относительные "указатели", но по скорости я выигрываю.
суть проблемы была в быстром копировании хеш-таблицы: это просто memcpy()!
вот алгоритм с картинками: https://ders.by/cpp/memdb/memdb.html#4
По ссылке описание транзакционного словаря, из-за чего постоянно приходится множество копий делать, тут соглашусь, уменьшение таблицы указателей даст выигрыш. Но по моему опыту балк-операции и разовые операции обычно находятся в контре друг-к-другу по производительности. Практически невозможно оптимизировать обе - вторая проиграет.
В JVM внутри по возможности используются сжатые указатели (если адресуемая память позволяет и сборщик мусора не утилизирует дополнительные биты указателей для "раскраски"). Почитать можно тут: https://wiki.openjdk.org/display/HotSpot/CompressedOops
Производительность от этого чаще растёт, т.к. большу́ю часть времени JVM занимает перекладывание байтиков. Меньше указателей - меньше байтиков перекладывать.
Более быстрые хеш-таблицы: претенденты на место SwissTable