1. В ZSTD появился externalMatchfinder, вы теперь можете писать свои алгоритмы компрессии. Для чего?
Очень много запросов от индустрии по ускорению ZSTD, поэтому разные компании хотят построить hardware акселераторы для компрессии. Инженеры из Meta задизайнили решение. На выход вы даёте множество ZSTD_Sequence -- тройки из (litLength, matchLength, offset) -- сколько скопировать "просто так", потом сколько скопировать от уже раскодированного и откуда взять оффсет раскодированного. Далее ZSTD сам уже применит Huffman, FSE.
Полезно, в PR в репозитории не мало упоминаний людей из Intel, что-то явно хотят сделать.
2. Я недавно перечитывал статью про Borg -- система оркестрации в Google и обратил внимание на интересную деталь. Если коротко, когда приходит новое задание, Borg должен посчитать оценку, на какие машины лучше всего его положить. Я задался интересным вопросом, ведь машин сотни тысяч/миллионы, как они избавляются от квадратичного роста. Оказалось, решение достаточно интересное, надо просто смотреть в случайном порядке, и оно само сойдётся:
Это интересное решение, которое позволяет всякому batch процессингу находить сломанные машины быстрее, не сошлись чексуммы, когда должны несколько раз? Машину на свалку. Из-за случайности больше и быстрее находим.
3. Мы тут недавно списывались с людьми, которые пишут в Rust хештаблицу с открытой адресацией похожую на abseil'овский flat_hash_map, зовут их hashbrown. Нашли интересный момент:
В Abseil мы вычисляем хеши H1, H2, первый хеш для того, чтобы понять куда в таблицу с открытой адресацией положить элемент (по модулю степени двойки), второй для того, чтобы положить в отдельный массив и фильтровать элементы до того, как мы будем их сравнивать. Первому мы даём 57 бит хеша, второму лишь 7, чтобы помещался в один байт и оставался битик, чтобы пометить удалённые или несуществующие элементы.
Интересный момент, а откуда эти 7 бит брать из вычисленного хеша в 64 бита? Мы решили брать нижние 7 бит, потому что хеши на верхних битах иногда ведут себя плохо, не хватает энтропии. В итоге чтобы поддержать таблицу из 2^N элементов, нам достаточно где-то N+7 бит энтропии. В итоге можно считать не 64 битные хеши, а лишь 48, так как хеш таблицы размера 2^40 огромные.
В Rust решили брать старшие 7 бит из 64. Это даёт свои плюсы. Нам в любом случае надо сделать сдвиг (в abseil на 7, в rust на 57). А вот в Abseil нам надо ещё сделать маску на нижние 7, когда как вычисление по модулю для нахождения позиции можно брать без какой либо операции в Rust. В итоге Rust использует на 1 инструкцию меньше, зато им стоит поддерживать, что старшие биты в хеше должны иметь достаточно энтропии.
Такие трейдоффы.
Очень много запросов от индустрии по ускорению ZSTD, поэтому разные компании хотят построить hardware акселераторы для компрессии. Инженеры из Meta задизайнили решение. На выход вы даёте множество ZSTD_Sequence -- тройки из (litLength, matchLength, offset) -- сколько скопировать "просто так", потом сколько скопировать от уже раскодированного и откуда взять оффсет раскодированного. Далее ZSTD сам уже применит Huffman, FSE.
Полезно, в PR в репозитории не мало упоминаний людей из Intel, что-то явно хотят сделать.
2. Я недавно перечитывал статью про Borg -- система оркестрации в Google и обратил внимание на интересную деталь. Если коротко, когда приходит новое задание, Borg должен посчитать оценку, на какие машины лучше всего его положить. Я задался интересным вопросом, ведь машин сотни тысяч/миллионы, как они избавляются от квадратичного роста. Оказалось, решение достаточно интересное, надо просто смотреть в случайном порядке, и оно само сойдётся:
Relaxed randomization: It is wasteful to calculate feasibility and scores for all the machines in a large cell, so the scheduler examines machines in a random order until it has found “enough” feasible machines to scoreЭто интересное решение, которое позволяет всякому batch процессингу находить сломанные машины быстрее, не сошлись чексуммы, когда должны несколько раз? Машину на свалку. Из-за случайности больше и быстрее находим.
3. Мы тут недавно списывались с людьми, которые пишут в Rust хештаблицу с открытой адресацией похожую на abseil'овский flat_hash_map, зовут их hashbrown. Нашли интересный момент:
В Abseil мы вычисляем хеши H1, H2, первый хеш для того, чтобы понять куда в таблицу с открытой адресацией положить элемент (по модулю степени двойки), второй для того, чтобы положить в отдельный массив и фильтровать элементы до того, как мы будем их сравнивать. Первому мы даём 57 бит хеша, второму лишь 7, чтобы помещался в один байт и оставался битик, чтобы пометить удалённые или несуществующие элементы.
Интересный момент, а откуда эти 7 бит брать из вычисленного хеша в 64 бита? Мы решили брать нижние 7 бит, потому что хеши на верхних битах иногда ведут себя плохо, не хватает энтропии. В итоге чтобы поддержать таблицу из 2^N элементов, нам достаточно где-то N+7 бит энтропии. В итоге можно считать не 64 битные хеши, а лишь 48, так как хеш таблицы размера 2^40 огромные.
В Rust решили брать старшие 7 бит из 64. Это даёт свои плюсы. Нам в любом случае надо сделать сдвиг (в abseil на 7, в rust на 57). А вот в Abseil нам надо ещё сделать маску на нижние 7, когда как вычисление по модулю для нахождения позиции можно брать без какой либо операции в Rust. В итоге Rust использует на 1 инструкцию меньше, зато им стоит поддерживать, что старшие биты в хеше должны иметь достаточно энтропии.
Такие трейдоффы.