Experimental chill

1. Не так часто в основной курс алгоритмов и структур данных можно включить новый не очень сложный алгоритм. Его Кнут назвал CVM алгоритмом для подсчёта количества различных элементов в потоке элементов. Действительно очень простой алгоритм https://arxiv.org/pdf/2301.10191 . Кнут написал целую статью про него https://cs.stanford.edu/~knuth/papers/cvm-note.pdf . Удивительно как я всё реже занимающийся такими вещами даже смог осилить доказательство. К сожалению или к счастью он не лучше по оценкам, чем HyperLogLog, но зато не использует никакого хеширования. Из хорошего, я думаю единицы в мире умеют доказывать оценку HyperLogLog, а тут получается, что можно даже доказать что-то за лекцию.

2. Тут вышли очередные бенчмарки хештаблиц. Скажу, что как обычно побенчмаркали какие-то огромные таблицы, которые в реальной жизни не так часты. Может быть для баз данных бывает такое, но для обычной бизнес логики большинство хеш таблиц десятки, максимум сотни элементов. absl::flat_hash_* был задизайнен именно для небольшого количества элементов. Мы кстати тут недавно поддержали Small Object Optimization.

3. Наконец-то std::pair станет тривиально копируемой, если оба элемента тривиально копируемы (правда под флагом другого ABI в libcxx). Не думал, что этот день настанет. Как раз 4 года назад у меня был блог об этом.

4. Блогу практически 5 лет. Я рад, что легаси блога живёт и даже вот вчера он появился на hacker news снова.

Признаться, 5 лет назад совсем другие мысли в голове были. Тогда я был юным, смелым, писал через силу и хотел, чтобы меня заметили. Взросление даёт о себе знать, да и мотивации поменялись.

5 лет назад хотелось делать большие распределенные системы, сейчас хочется заниматься в основном перформансом и обучением людей, так как очень сильно заинтересовали темы как экономика компаний, capacity engineering. В целом оптимизации, идеи, инновации в перформансе сильно хорошо окупаются (особенно в эпоху бесконечных трат на AI). Распутывать клубки, например, откуда пришли те или иные траты интересно как никогда.

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

www.group-telegram.com/us/experimentalchill.com/273

15.4K viewsedited  Jun 5, 2024 at 08:23

1. Не так часто в основной курс алгоритмов и структур данных можно включить новый не очень сложный алгоритм. Его Кнут назвал CVM алгоритмом для подсчёта количества различных элементов в потоке элементов. Действительно очень простой алгоритм https://arxiv.org/pdf/2301.10191 . Кнут написал целую статью про него https://cs.stanford.edu/~knuth/papers/cvm-note.pdf . Удивительно как я всё реже занимающийся такими вещами даже смог осилить доказательство. К сожалению или к счастью он не лучше по оценкам, чем HyperLogLog, но зато не использует никакого хеширования. Из хорошего, я думаю единицы в мире умеют доказывать оценку HyperLogLog, а тут получается, что можно даже доказать что-то за лекцию.

2. Тут вышли очередные бенчмарки хештаблиц. Скажу, что как обычно побенчмаркали какие-то огромные таблицы, которые в реальной жизни не так часты. Может быть для баз данных бывает такое, но для обычной бизнес логики большинство хеш таблиц десятки, максимум сотни элементов. absl::flat_hash_* был задизайнен именно для небольшого количества элементов. Мы кстати тут недавно поддержали Small Object Optimization.

3. Наконец-то std::pair станет тривиально копируемой, если оба элемента тривиально копируемы (правда под флагом другого ABI в libcxx). Не думал, что этот день настанет. Как раз 4 года назад у меня был блог об этом.

4. Блогу практически 5 лет. Я рад, что легаси блога живёт и даже вот вчера он появился на hacker news снова.

Признаться, 5 лет назад совсем другие мысли в голове были. Тогда я был юным, смелым, писал через силу и хотел, чтобы меня заметили. Взросление даёт о себе знать, да и мотивации поменялись.

5 лет назад хотелось делать большие распределенные системы, сейчас хочется заниматься в основном перформансом и обучением людей, так как очень сильно заинтересовали темы как экономика компаний, capacity engineering. В целом оптимизации, идеи, инновации в перформансе сильно хорошо окупаются (особенно в эпоху бесконечных трат на AI). Распутывать клубки, например, откуда пришли те или иные траты интересно как никогда.

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

BY Experimental chill