Давайте попробуем продвинуть вчерашнюю на Hacker News: https://news.ycombinator.com/item?id=34312306. Плевать, если не зачтёт
Ещё вчера спрашивали зачем это, скинули репозиторий, где находили с помощью проверок достаточно большое количество багов в софте: https://github.com/yugr/sortcheck#what-are-current-results
1. Сегодня я проснулся, и мы лишь нашли ещё один corruption в zstd. https://github.com/facebook/zstd/issues/3416
2. Вообще мне недавно понравился пост про "Things they didn't teach you about Software Engineering": https://vadimkravcenko.com/shorts/things-they-didnt-teach-you/
Там есть пункт про "Assume everything has bugs" и "You work with uncertainty most of the time".
В software самые важные уроки, которые я освоил
* Всё всегда разломано. Держится всё буквально на соплях
* Если что-то не разломано, время это разломает
* Куда ни посмотри, везде можно сделать лучше
* Нулевая job security, все очень быстро меняется, язык, который учил через 3 года может быть уже нерелевантным. В бекенде чуть получше и тут хотя бы вкладываться в алгоритмы/науку о распределённых системах/старый МЛ, но всегда ощущение, что если я не почитаю статей за месяц, я деградирую.
* Самый сильный рост как инженера был это находить certainty из uncertainty. Для этого надо было очень хорошо освоить свои тулзы, поиск по коду, IDE, vim и тд.
3. Я тут писал про fleetbench недавно (https://xn--r1a.website/experimentalchill/178), это репрезентативные бенчмарки гугла. Мы теперь им пользуемся, чтобы смотреть на изменения! И люди им тожепользуются пытаются. Пример:
https://github.com/protocolbuffers/protobuf/pull/11102#issuecomment-1374878279. Микробенчмарки исправились на 50%, а макробенчмарк за 1-1.5%, что тоже очень круто!
Ещё вчера спрашивали зачем это, скинули репозиторий, где находили с помощью проверок достаточно большое количество багов в софте: https://github.com/yugr/sortcheck#what-are-current-results
1. Сегодня я проснулся, и мы лишь нашли ещё один corruption в zstd. https://github.com/facebook/zstd/issues/3416
2. Вообще мне недавно понравился пост про "Things they didn't teach you about Software Engineering": https://vadimkravcenko.com/shorts/things-they-didnt-teach-you/
Там есть пункт про "Assume everything has bugs" и "You work with uncertainty most of the time".
В software самые важные уроки, которые я освоил
* Всё всегда разломано. Держится всё буквально на соплях
* Если что-то не разломано, время это разломает
* Куда ни посмотри, везде можно сделать лучше
* Нулевая job security, все очень быстро меняется, язык, который учил через 3 года может быть уже нерелевантным. В бекенде чуть получше и тут хотя бы вкладываться в алгоритмы/науку о распределённых системах/старый МЛ, но всегда ощущение, что если я не почитаю статей за месяц, я деградирую.
* Самый сильный рост как инженера был это находить certainty из uncertainty. Для этого надо было очень хорошо освоить свои тулзы, поиск по коду, IDE, vim и тд.
3. Я тут писал про fleetbench недавно (https://xn--r1a.website/experimentalchill/178), это репрезентативные бенчмарки гугла. Мы теперь им пользуемся, чтобы смотреть на изменения! И люди им тоже
https://github.com/protocolbuffers/protobuf/pull/11102#issuecomment-1374878279. Микробенчмарки исправились на 50%, а макробенчмарк за 1-1.5%, что тоже очень круто!
GitHub
GitHub - yugr/sortcheck: Tool for detecting violations of ordering axioms in qsort/bsearch callbacks.
Tool for detecting violations of ordering axioms in qsort/bsearch callbacks. - yugr/sortcheck
🔥34👍23❤6🤩1
В панике, что после недели не о чем писать
Я до занятием перформанса и MapReduce в Google работал над файловыми системами. Не очень большая, но и не очень маленькая. Было пространство сделать хорошо, заниматься интересными распределёнными системами и не сломать слишком много.
Мне вспомнилось как мы сильно, очень сильно старались отделить сервер метаданных, который хранит как расположены чанки данных, решает в каком порядке всё применять через Paxos и сервер, который читает и создаёт чанки с данными. Метаданные легче, они менее требовательны к security, но самое главное, что сервисы почти независимы. При записи файла вы можете создать чанк, пойти с id этого чанка и положить его в метаданные. Если что-то происходит с сервисом метаданных, всё то, что вы пишете будет куда-то записано, и мы хоть и попотеем, если будет беда, но данные не потеряем.
Помогло раз, когда при релизе был баг, мы смогли восстановить все данные и как-то мануально их отдать. Это был хороший урок, что когда вы пишете storage систему, делаете что угодно, но главное не теряете данные. Удаляйте только с TTL в несколько дней, чтобы можно было отревертить, делайте read only modes и так далее. Проверяйте консистентность раз в день, всё это достаточно полезно находить сюрпризы раньше, чем позже.
По поводу этого мне нравится, что Ceph (при всех его проблемах с расширением) делался с этим умом
https://docs.ceph.com/en/latest/architecture/
В SQLite тоже много написано о том, что очень сложно поцарапать базу https://www.sqlite.org/lockingv3.html
Эти уроки я усвоил на всю жизнь и на собесах, если спрашиваю что-то такое, то не важно даже как мне задизайнят систему, главное, чтобы были цели -- не потерять данные ни в коем случае.
Бывали инциденты, когда все файлы удалялись и в базах висели только дескрипторы, бывали байки, что данные были только в памяти и их приходилось вытаскивать gdb. Много всякого интересного было.
Завтра что-то более содержательное напишу, сегодня как-то так
Я до занятием перформанса и MapReduce в Google работал над файловыми системами. Не очень большая, но и не очень маленькая. Было пространство сделать хорошо, заниматься интересными распределёнными системами и не сломать слишком много.
Мне вспомнилось как мы сильно, очень сильно старались отделить сервер метаданных, который хранит как расположены чанки данных, решает в каком порядке всё применять через Paxos и сервер, который читает и создаёт чанки с данными. Метаданные легче, они менее требовательны к security, но самое главное, что сервисы почти независимы. При записи файла вы можете создать чанк, пойти с id этого чанка и положить его в метаданные. Если что-то происходит с сервисом метаданных, всё то, что вы пишете будет куда-то записано, и мы хоть и попотеем, если будет беда, но данные не потеряем.
Помогло раз, когда при релизе был баг, мы смогли восстановить все данные и как-то мануально их отдать. Это был хороший урок, что когда вы пишете storage систему, делаете что угодно, но главное не теряете данные. Удаляйте только с TTL в несколько дней, чтобы можно было отревертить, делайте read only modes и так далее. Проверяйте консистентность раз в день, всё это достаточно полезно находить сюрпризы раньше, чем позже.
По поводу этого мне нравится, что Ceph (при всех его проблемах с расширением) делался с этим умом
https://docs.ceph.com/en/latest/architecture/
В SQLite тоже много написано о том, что очень сложно поцарапать базу https://www.sqlite.org/lockingv3.html
Эти уроки я усвоил на всю жизнь и на собесах, если спрашиваю что-то такое, то не важно даже как мне задизайнят систему, главное, чтобы были цели -- не потерять данные ни в коем случае.
Бывали инциденты, когда все файлы удалялись и в базах висели только дескрипторы, бывали байки, что данные были только в памяти и их приходилось вытаскивать gdb. Много всякого интересного было.
Завтра что-то более содержательное напишу, сегодня как-то так
👍95🔥16❤13
Сегодня поздний пост, но как есть.
Одна из оптимизаций, которая мне пришла в голову, и к которой у меня было не так много open source решений это просмотр коротких циклов. Почему это интересно?
Проблема в том, что хоть вы и доверяете компилятору, не всегда ему получается векторизовать какие-то циклы, например,
К сожалению, тут есть проблема, что data и other_data могут пересекаться и такая проблема называется aliasing. Компилятору порой просто нет информации, чтобы это предотвратить. Иногда это вырождается во что-то страшное как просто побайтовый цикл или что-нибудь ещё неприятное.
Компиляторы С/C++ стараются создавать SIMD блоки, если указатели не пересекаются (см внизу https://gcc.godbolt.org/z/o7xhadsMq). Проблема в том, что так происходит не всегда, и векторизация просто не самый надёжный способ, оно растит бинарь достаточно мощно.
Скажем есть большой бинарь ClickHouse. Проблема, с которой я столкнулся -- я хочу увидеть в большом бинаре и после всех performance тестов (их тысячи) короткие hot циклы, скажем, 5-6 инструкций, они скорее всего не очень векторизованы из-за каких-то таких проблем. Мы видели кейсы, когда мы находили случайно такие пропущенные оптимизации
https://github.com/ClickHouse/ClickHouse/pull/9442
https://github.com/ClickHouse/ClickHouse/pull/9304
Единственная проблема в том, что я не понимаю как это сделать без открывания питона и парсинга objdump. Я хочу задать какой-нибудь SQL запрос с функцией LAG, где каждый ряд это инструкция, и есть какое-то количество колонок с адресами и прыжками, каунтерами, сколько раз мы посемплили ту или иную инструкцию.
В итоге я использую что-то вроде
И смотрю _напрямую_
И всё равно надо открывать питон и потратить день, чтобы написать колоночный формат disasm'а. Иногда даже проработав годы в индустрии, попросту не хватает тулинга. Я вообще думаю, что надо этим намного больше заниматься, чем самим перформансом
Одна из оптимизаций, которая мне пришла в голову, и к которой у меня было не так много open source решений это просмотр коротких циклов. Почему это интересно?
Проблема в том, что хоть вы и доверяете компилятору, не всегда ему получается векторизовать какие-то циклы, например,
for (int i = 0; i < n; ++i) {
data[i] ^= other_data[i];
}
К сожалению, тут есть проблема, что data и other_data могут пересекаться и такая проблема называется aliasing. Компилятору порой просто нет информации, чтобы это предотвратить. Иногда это вырождается во что-то страшное как просто побайтовый цикл или что-нибудь ещё неприятное.
Компиляторы С/C++ стараются создавать SIMD блоки, если указатели не пересекаются (см внизу https://gcc.godbolt.org/z/o7xhadsMq). Проблема в том, что так происходит не всегда, и векторизация просто не самый надёжный способ, оно растит бинарь достаточно мощно.
Скажем есть большой бинарь ClickHouse. Проблема, с которой я столкнулся -- я хочу увидеть в большом бинаре и после всех performance тестов (их тысячи) короткие hot циклы, скажем, 5-6 инструкций, они скорее всего не очень векторизованы из-за каких-то таких проблем. Мы видели кейсы, когда мы находили случайно такие пропущенные оптимизации
https://github.com/ClickHouse/ClickHouse/pull/9442
https://github.com/ClickHouse/ClickHouse/pull/9304
Единственная проблема в том, что я не понимаю как это сделать без открывания питона и парсинга objdump. Я хочу задать какой-нибудь SQL запрос с функцией LAG, где каждый ряд это инструкция, и есть какое-то количество колонок с адресами и прыжками, каунтерами, сколько раз мы посемплили ту или иную инструкцию.
В итоге я использую что-то вроде
objdump -Mintel -ldSrwC --no-show-raw-insn --visualize-jumps=extended-color
И смотрю _напрямую_
И всё равно надо открывать питон и потратить день, чтобы написать колоночный формат disasm'а. Иногда даже проработав годы в индустрии, попросту не хватает тулинга. Я вообще думаю, что надо этим намного больше заниматься, чем самим перформансом
gcc.godbolt.org
Compiler Explorer - C++ (x86-64 clang (trunk))
void XorDataWith(std::string_view s, std::string& data) {
const int s_size = s.size();
if (s_size > data.size()) {
data.resize(s.size());
}
char* data_it = &data[0];
const char* s_it = s.data();
for (int i = 0; i < s_size; ++i) {
data_it[i]…
const int s_size = s.size();
if (s_size > data.size()) {
data.resize(s.size());
}
char* data_it = &data[0];
const char* s_it = s.data();
for (int i = 0; i < s_size; ++i) {
data_it[i]…
👍73🤡4❤2🔥2
https://arxiv.org/pdf/2301.02432.pdf
Myths and Legends in High-Performance Computing
Статья хоть немного странно выглядит в качестве научной статьи, но достаточно интересно описывает то, какие мифы и легенды в High Performance Computing существуют.
Миф 1: Квантовые вычисления вытеснят HPC!
Миф 2: Мир захватит deep learning!
Миф 3: Сугубо точная специализация железа, как в смартфонах, позволит выйти за рамки закона Мура!
Миф 4: Все будет работать на каком-то ускорителе! (FPGA)
Миф 5: Программируемые железки дадут вам 100-кратное ускорение!
Миф 6: Скоро мы будем работать на Zettascale!
Миф 7: Системам следующего поколения нужно больше памяти на ядро!
Миф 8: Мы будем разъединять ресурсы из материнской платы (a.k.a стойки только с памятью, только с дисками и тд)
Миф 9: Приложения продолжают улучшаться. Даже на старом оборудовании!
Миф 10: Фортран мертв, да здравствует DSL!
Миф 11: HPC перейдет к низкой или смешанной точности!
Миф 12: Все высокопроизводительные вычисления будут поглощены Clouds!
Я со многим здесь согласен, и аргументы там очень хорошие. Наверное, я больше всего не согласен с пунктами 5, 9. Всё таки я считаю, что следующий скачок вычислений за изменением модели вычислений и за оптимизациями в софте -- другие алгоритмы и тд. Но всё ещё думаю, что до квантовых вычислений на огромных масштабах нам далеко. А вот то, где я заблуждался, пока не проникся темой, так это пункт 7.
Много приводят аргумент, что код как-то переписывать не ахти люди хотят. В целом я не вижу, что это правда, важные куски, если на них кто-то смотрит, постоянно оптимизруются. Важные куски в трейдинге тоже на FPGA и пока у нас нет совсем плохой истории софта важных систем, мы будем их улучшать. Новые алгоритмы выходят и даже их аргумент
выглядит недостаточно происследованным. Негативные результаты в алгоритмической теории очень сложны. И если мы сможем положить много задач на SIMD или избавиться от перекладываний данных, чтобы не упираться в memory wall, изменения будут происходить и происходят -- SIMDJSON, лучшие базы данных, лучше компрессоры, лучше кеши и так далее. Ускорений в 1024x я не жду, но честно верю, что любой текущий софт можно раз в 5-6 ускорить, к сожалению, что-то оптимальное не очень человечное -- SIMDJSON невозможно читать, например.
Myths and Legends in High-Performance Computing
Статья хоть немного странно выглядит в качестве научной статьи, но достаточно интересно описывает то, какие мифы и легенды в High Performance Computing существуют.
Миф 1: Квантовые вычисления вытеснят HPC!
Миф 2: Мир захватит deep learning!
Миф 3: Сугубо точная специализация железа, как в смартфонах, позволит выйти за рамки закона Мура!
Миф 4: Все будет работать на каком-то ускорителе! (FPGA)
Миф 5: Программируемые железки дадут вам 100-кратное ускорение!
Миф 6: Скоро мы будем работать на Zettascale!
Миф 7: Системам следующего поколения нужно больше памяти на ядро!
Миф 8: Мы будем разъединять ресурсы из материнской платы (a.k.a стойки только с памятью, только с дисками и тд)
Миф 9: Приложения продолжают улучшаться. Даже на старом оборудовании!
Миф 10: Фортран мертв, да здравствует DSL!
Миф 11: HPC перейдет к низкой или смешанной точности!
Миф 12: Все высокопроизводительные вычисления будут поглощены Clouds!
Я со многим здесь согласен, и аргументы там очень хорошие. Наверное, я больше всего не согласен с пунктами 5, 9. Всё таки я считаю, что следующий скачок вычислений за изменением модели вычислений и за оптимизациями в софте -- другие алгоритмы и тд. Но всё ещё думаю, что до квантовых вычислений на огромных масштабах нам далеко. А вот то, где я заблуждался, пока не проникся темой, так это пункт 7.
Много приводят аргумент, что код как-то переписывать не ахти люди хотят. В целом я не вижу, что это правда, важные куски, если на них кто-то смотрит, постоянно оптимизруются. Важные куски в трейдинге тоже на FPGA и пока у нас нет совсем плохой истории софта важных систем, мы будем их улучшать. Новые алгоритмы выходят и даже их аргумент
However, we have to be cautious that—
just as hardware improvements have physics and engineering
limits—the “Algorithmic Moore’s Law” also has its own
limits: numerical stability, hitting asymptotic limits, etc. That
being said, those limits might not be as clear and quantifiable
as the limits on hardware. That is since even if one numerical
method hits its limit, domain experts can often reduce/precondition their problem to another numerical method that is
more efficient.
выглядит недостаточно происследованным. Негативные результаты в алгоритмической теории очень сложны. И если мы сможем положить много задач на SIMD или избавиться от перекладываний данных, чтобы не упираться в memory wall, изменения будут происходить и происходят -- SIMDJSON, лучшие базы данных, лучше компрессоры, лучше кеши и так далее. Ускорений в 1024x я не жду, но честно верю, что любой текущий софт можно раз в 5-6 ускорить, к сожалению, что-то оптимальное не очень человечное -- SIMDJSON невозможно читать, например.
❤38👍27🤔6🤡2🔥1👌1
В модели памяти x86_64 чтения/записи на кешлинии с помощью инструкций MOV всегда атомарны, тем самым достигается хороший многопоточный перформанс. Это гарантируется спецификацией. Работает чудесно, все довольны. С выпуском Core 2 спецификация хотя бы появилась, которая об этом говорит.
Тем не менее даже простые вопросы:
"А 16 байтные записи на кешлинии атомарны?"
Сложные.
В спецификации архитектур это одно из немногих многопоточных различий Intel и AMD. В итоге атомарность гарантируется для процессоров Intel с поддержкой AVX, а AMD вообще не гарантируется (см фото). Напомню, что AVX добавила уже 32 байтные load/store.
Проводили независимые тесты и результаты забавные:
Intel с Core 2 даже не по спецификации имеет атомарное поведение, а вот старый AMD Athlon II падает проверку.
В результате в компиляторах используют CMPXCHG16B (Compare and Exchange 16b). За такую историю платим 5-7 наносек, не критично, но удивляет. uint128 уже начинает быть более популярным.
Спецификация AMD, Intel, CMPXCHG16B
Тем не менее даже простые вопросы:
"А 16 байтные записи на кешлинии атомарны?"
Сложные.
В спецификации архитектур это одно из немногих многопоточных различий Intel и AMD. В итоге атомарность гарантируется для процессоров Intel с поддержкой AVX, а AMD вообще не гарантируется (см фото). Напомню, что AVX добавила уже 32 байтные load/store.
Проводили независимые тесты и результаты забавные:
Intel с Core 2 даже не по спецификации имеет атомарное поведение, а вот старый AMD Athlon II падает проверку.
В результате в компиляторах используют CMPXCHG16B (Compare and Exchange 16b). За такую историю платим 5-7 наносек, не критично, но удивляет. uint128 уже начинает быть более популярным.
Спецификация AMD, Intel, CMPXCHG16B
👍33🤯17🤔12🔥7👏2❤1😁1😢1
Я тут писал, что свой рост инженера я видел, когда из неопределенности появлялась определенность благодаря моим усилиям, меня попросили раскрыть тему.
Вообще это достаточно метафизическая фраза, которая сработала на меня. Не факт, что работает у других, и историй я слышал много.
Вещи, без которых я не могу жить в рабочем дне:
1. Понятное дело, Google
2. Поиск по коду. Пользуйтесь IDE, пользуйтесь cs.github.com, возможно пользуйтесь copilot. Когда у вас есть API, какая-то мелкая задача, все эти вещи дают быструю скорость просмотра, быстрое обучение мыслительному процессу как устроен тот или иной фреймворк. В один момент вы начинаете понимать от корки до корки как устроены библиотеки, языки, концепты. Примеры, понимание дизайна помогают привыкать. Чем быстрее ваши методы нахождения информации, тем быстрее вы выучите. В какой-то степени IDE даже хуже, потому что кодовая база проекта имеет малую видимость, а поиск по коду гитхаба имеет все репозитории мира.
Пример: я учу https://github.com/3b1b/manim для рисовалки анимаций для математики. Документация не оч, зато тысячи примеров https://github.com/3b1b/videos. Придумал себе задачу, пошел учить, за день учишь прилично, за месяц уже плаваешь в этом. За 3 находишь баги, репортишь, за год пишешь свое (шутка) :)
3. Люди, без них вообще не понимаю как. Мой САМЫЙ сильный рост был, когда я смотрел как мой босс пишет код, ищет информацию, пользуется своими тулзами, фактически скринкаст рабочего дня. Мыслительный процесс профессионала просто невероятно важен. Я всегда с джунами включаю свой экран и показываю как решать их проблемы систематично через тулзы. Постоянно смотрю на других и учусь у них.
4. Понимать тулзы. Я почти уверен, что очень много, кто не знает как работает git, shell, vim, системы сборки и тд. Это безумно глубокие темы, идти смотреть в код, попробовать все команды сильно позволяет расти с точки зрения осознания, а что вообще можно сделать за пару минут.
5. Читать статьи, следить за релизами. Кто-то сделал лучше? Почему вас это останавливает сделать? Принципы/философия/лицензии/бюрократия?
Тулзы, люди и т.д. как раз создают ощущение определенности, когда у вас задачи не получаются. Понятное дело можно ещё тут много говорить про математику, алгоритмы, теорию про P/NP для всяких отрицательных результатов, но такие вещи пригождаются меньше в software engineering.
Помните, что как индустрия Software Engineering существует лет 50 максимум. Мы едва начинаем понимать, что работает, а что нет. Все очень быстро меняется, понимать как решать неопределенность и постоянно учиться позволило мне достаточно быстро вырасти. Возможно это неплохая стратегия, возможно я ошибаюсь.
Ещё была идея, что вероятно в этом и суть хорошего универа -- неважно чему учить, главное, чтобы оно не было слишком простым (стагнация), слишком сложным (разочарование), а чтобы было сложнее на немного (посильный рост). 25 пар в неделю вас убьет, на 7 будет скучно, на 12 с дз будет сложно, но посильно. Так же со спортом и любым обучением. В софте надо постоянно учиться
Вот такое мое мнение. Срач не разводите в комментах, пожалуйста. Такие посты всегда вызывают эмоции на такую большую аудиторию. Будьте любопытны (curious), а не осуждающими (judgemental).
Вообще это достаточно метафизическая фраза, которая сработала на меня. Не факт, что работает у других, и историй я слышал много.
Вещи, без которых я не могу жить в рабочем дне:
1. Понятное дело, Google
2. Поиск по коду. Пользуйтесь IDE, пользуйтесь cs.github.com, возможно пользуйтесь copilot. Когда у вас есть API, какая-то мелкая задача, все эти вещи дают быструю скорость просмотра, быстрое обучение мыслительному процессу как устроен тот или иной фреймворк. В один момент вы начинаете понимать от корки до корки как устроены библиотеки, языки, концепты. Примеры, понимание дизайна помогают привыкать. Чем быстрее ваши методы нахождения информации, тем быстрее вы выучите. В какой-то степени IDE даже хуже, потому что кодовая база проекта имеет малую видимость, а поиск по коду гитхаба имеет все репозитории мира.
Пример: я учу https://github.com/3b1b/manim для рисовалки анимаций для математики. Документация не оч, зато тысячи примеров https://github.com/3b1b/videos. Придумал себе задачу, пошел учить, за день учишь прилично, за месяц уже плаваешь в этом. За 3 находишь баги, репортишь, за год пишешь свое (шутка) :)
3. Люди, без них вообще не понимаю как. Мой САМЫЙ сильный рост был, когда я смотрел как мой босс пишет код, ищет информацию, пользуется своими тулзами, фактически скринкаст рабочего дня. Мыслительный процесс профессионала просто невероятно важен. Я всегда с джунами включаю свой экран и показываю как решать их проблемы систематично через тулзы. Постоянно смотрю на других и учусь у них.
4. Понимать тулзы. Я почти уверен, что очень много, кто не знает как работает git, shell, vim, системы сборки и тд. Это безумно глубокие темы, идти смотреть в код, попробовать все команды сильно позволяет расти с точки зрения осознания, а что вообще можно сделать за пару минут.
5. Читать статьи, следить за релизами. Кто-то сделал лучше? Почему вас это останавливает сделать? Принципы/философия/лицензии/бюрократия?
Тулзы, люди и т.д. как раз создают ощущение определенности, когда у вас задачи не получаются. Понятное дело можно ещё тут много говорить про математику, алгоритмы, теорию про P/NP для всяких отрицательных результатов, но такие вещи пригождаются меньше в software engineering.
Помните, что как индустрия Software Engineering существует лет 50 максимум. Мы едва начинаем понимать, что работает, а что нет. Все очень быстро меняется, понимать как решать неопределенность и постоянно учиться позволило мне достаточно быстро вырасти. Возможно это неплохая стратегия, возможно я ошибаюсь.
Ещё была идея, что вероятно в этом и суть хорошего универа -- неважно чему учить, главное, чтобы оно не было слишком простым (стагнация), слишком сложным (разочарование), а чтобы было сложнее на немного (посильный рост). 25 пар в неделю вас убьет, на 7 будет скучно, на 12 с дз будет сложно, но посильно. Так же со спортом и любым обучением. В софте надо постоянно учиться
Вот такое мое мнение. Срач не разводите в комментах, пожалуйста. Такие посты всегда вызывают эмоции на такую большую аудиторию. Будьте любопытны (curious), а не осуждающими (judgemental).
GitHub
GitHub - 3b1b/manim: Animation engine for explanatory math videos
Animation engine for explanatory math videos. Contribute to 3b1b/manim development by creating an account on GitHub.
👍175🔥31❤22🌚2👏1🤔1🤡1
Мы тут выложили Protobuf Table-Driven Parser.
Основная идея, что для каждого отдельного типа Protobuf мы генерировали огромный кусок кода, и он рос линейно/супер линейно с количеством полей в протобуфе.
Рост происходил из-за того, что компилятору мы давали код в духе
И так далее. В итоге был огромный кусок кода и компилятор уставал аллоцировать регистры, делать push, pop регистров при входе/выходе из вложенных функций, компиляция росла. Я писал об этом аж 1.5 года назад https://xn--r1a.website/experimentalchill/95 про аттрибут
Так как формат фиксированный, мы можем просто брать функцию из значения тега и вызывать её, сохраняя все регистры и заставив компилятор не делать push/pop. 6 параметров регистров мы спрятали PR
Пример можно посмотреть здесь.
Плюсы, которые мы получили:
1. Мы сильно уменьшили размер генерируемого кода и время компиляции. Теперь нам нужна только таблица с инструкциями что делать для того или иного поля
2. У нас нет переполнения стека из-за отсутствия push/pop, теперь мы поддерживаем сообщения любой вложенности
3. По перфу нейтрально -- выиграли в push/pop, проиграли в статичности функций
4. Легче понимать профили бинарей, что они парсят на уровне сообщений
5. Только 1 имплементация парсинга на всех
6. Мы сможем менять формат протобуфов даже на ходу
Как мы сможем его менять? Скажем, при типе int32 мы пишем varint. Если число отрицательное, мы пишем 5 байт из-за того, что отрицательные числа наполнены единицами. А что если мы хотим написать его в типе sint32, чтобы писать меньше? В прошлые разы мы генерировали парсинг на основании типа и формата поля, то есть цикл парсинга мог воспринимать тип только строго.
Теперь мы можем писать int32, скажем, как
1. Если положительное, просто в varint
2. Если отрицательное, в отрицательном varint
3. Цикл парсинга всё поймёт, так как привязки к типу нет, и число в память напишется как напишется
4. Мы сэкономили байты и не проиграли в парсинге
Такие оптимизации можно делать даже на ходу -- алгоритм сериализации можно подменить так же.
Проблема в том, что очень много старых версий протобуфов, где логика парсинга строго привязана к типу. Она была привязана к типу из-за перфа, не очень хотелось писать код, который парсит int32 в зависимости от потенциально разных wire formats, теперь -- это не важно и по дизайну не медленнее старого подхода.
Пройдёт 3-5 лет, и мы сможем так делать по дефолту (build horizon). Пока -- под опцией.
Основная идея, что для каждого отдельного типа Protobuf мы генерировали огромный кусок кода, и он рос линейно/супер линейно с количеством полей в протобуфе.
Рост происходил из-за того, что компилятору мы давали код в духе
auto [tag, wire_format] = ReadTag(ptr);
if (tag == kMessageProtoTagNumber) {
ptr = ParseMessage(ptr);
}
if (tag == kIntProtoTagNumber) {
ptr = ParseVarInt32(ptr);
}
И так далее. В итоге был огромный кусок кода и компилятор уставал аллоцировать регистры, делать push, pop регистров при входе/выходе из вложенных функций, компиляция росла. Я писал об этом аж 1.5 года назад https://xn--r1a.website/experimentalchill/95 про аттрибут
[[musttail]]. И теперь то самое начало давать свои плоды.Так как формат фиксированный, мы можем просто брать функцию из значения тега и вызывать её, сохраняя все регистры и заставив компилятор не делать push/pop. 6 параметров регистров мы спрятали PR
OTOBUF_TC_PARAM_DECL.
#define PROTOBUF_TC_PARAM_DECL \
::proto2::MessageLite *msg, const char *ptr, \
::proto2::internal::ParseContext *ctx, \
::proto2::internal::TcFieldData data, \
const ::proto2::internal::TcParseTableBase *table, uint64_t hasbits
В итоге оно выглядит как
data.read_tag<type>();
data.read_data<type>();
ptr += size_read;
SetField(data.offset(), ptr);
has_bits |= 1 << data.index_idx();
ReadInstruction()
dispatch to next Instruction from table
Пример можно посмотреть здесь.
Плюсы, которые мы получили:
1. Мы сильно уменьшили размер генерируемого кода и время компиляции. Теперь нам нужна только таблица с инструкциями что делать для того или иного поля
2. У нас нет переполнения стека из-за отсутствия push/pop, теперь мы поддерживаем сообщения любой вложенности
3. По перфу нейтрально -- выиграли в push/pop, проиграли в статичности функций
4. Легче понимать профили бинарей, что они парсят на уровне сообщений
5. Только 1 имплементация парсинга на всех
6. Мы сможем менять формат протобуфов даже на ходу
Как мы сможем его менять? Скажем, при типе int32 мы пишем varint. Если число отрицательное, мы пишем 5 байт из-за того, что отрицательные числа наполнены единицами. А что если мы хотим написать его в типе sint32, чтобы писать меньше? В прошлые разы мы генерировали парсинг на основании типа и формата поля, то есть цикл парсинга мог воспринимать тип только строго.
Теперь мы можем писать int32, скажем, как
1. Если положительное, просто в varint
2. Если отрицательное, в отрицательном varint
3. Цикл парсинга всё поймёт, так как привязки к типу нет, и число в память напишется как напишется
4. Мы сэкономили байты и не проиграли в парсинге
Такие оптимизации можно делать даже на ходу -- алгоритм сериализации можно подменить так же.
Проблема в том, что очень много старых версий протобуфов, где логика парсинга строго привязана к типу. Она была привязана к типу из-за перфа, не очень хотелось писать код, который парсит int32 в зависимости от потенциально разных wire formats, теперь -- это не важно и по дизайну не медленнее старого подхода.
Пройдёт 3-5 лет, и мы сможем так делать по дефолту (build horizon). Пока -- под опцией.
GitHub
protobuf/src/google/protobuf/generated_message_tctable_impl.h at e842f3fe3ccb96f35478a218808d360300cf3552 · protocolbuffers/protobuf
Protocol Buffers - Google's data interchange format - protocolbuffers/protobuf
🔥48👍18❤3🤮2🤡2🤯1
Что ж, подходит мой 14й день постов. Пропустил я два дня, и мне честно было просто тяжело публиковать каждый день. В итоге это вылилось в несколько осознаний:
* Я больше ошибался в русском языке и меньше проводил времени вычитывая
* Терялся фокус, по крайней мере для себя. Публикация раз в неделю чувствуется важнее и насыщеннее, чем каждый день
* Я обнаружил, что начал писать просто про то, что думаю ежедневно, меньше времени на то, чтобы глубоко обдумать утверждения
* Писать стало легче, разблокировал пару тем, о которых думал, но не мог их сформулировать
* Забавно было писать каждый день, чтобы ощутить новое для себя
Писать продолжу чуть чаще, чем в старом формате -- полтора-два раза в неделю с такими забегами раз в полгода.
Ну а вот вам интересный факт: если вы отключите L1/L2 префетчеры для кешей, то вероятно для своих серверных или жёстких по памяти процессов вы получите прирост производительности
https://www.reddit.com/r/pcmasterrace/comments/usoko0/disabling_hardware_prefetcher_l1_and_l2_led_to_a/
Почему? Потому что мы все больше упираемся в память, а префетчеры могут ошибаться и занимать вообще место для работы с памятью. Результаты будут скорее всего смешанными, то есть вероятно вы увидите прирост, но некоторые части кода сильно замедлятся. Особенно те, которые работают с большими кусками памяти.
В таких частях кода можно вставить software prefetching с помощью __builtin_prefetch. Скорее всего больше полезной работы будет выполнено, так как в среднем какие-то серверные процессы больше пытаются достать что-то из памяти, чем что-то посчитать. Память не растет по скорости, чем больше вы позволите ей делать то, что нужно, тем будет лучше.
Если вы работаете в HFT и у вас AMD машинки, я думаю, такую тему можно попробовать.
* Я больше ошибался в русском языке и меньше проводил времени вычитывая
* Терялся фокус, по крайней мере для себя. Публикация раз в неделю чувствуется важнее и насыщеннее, чем каждый день
* Я обнаружил, что начал писать просто про то, что думаю ежедневно, меньше времени на то, чтобы глубоко обдумать утверждения
* Писать стало легче, разблокировал пару тем, о которых думал, но не мог их сформулировать
* Забавно было писать каждый день, чтобы ощутить новое для себя
Писать продолжу чуть чаще, чем в старом формате -- полтора-два раза в неделю с такими забегами раз в полгода.
Ну а вот вам интересный факт: если вы отключите L1/L2 префетчеры для кешей, то вероятно для своих серверных или жёстких по памяти процессов вы получите прирост производительности
https://www.reddit.com/r/pcmasterrace/comments/usoko0/disabling_hardware_prefetcher_l1_and_l2_led_to_a/
Почему? Потому что мы все больше упираемся в память, а префетчеры могут ошибаться и занимать вообще место для работы с памятью. Результаты будут скорее всего смешанными, то есть вероятно вы увидите прирост, но некоторые части кода сильно замедлятся. Особенно те, которые работают с большими кусками памяти.
В таких частях кода можно вставить software prefetching с помощью __builtin_prefetch. Скорее всего больше полезной работы будет выполнено, так как в среднем какие-то серверные процессы больше пытаются достать что-то из памяти, чем что-то посчитать. Память не растет по скорости, чем больше вы позволите ей делать то, что нужно, тем будет лучше.
Если вы работаете в HFT и у вас AMD машинки, я думаю, такую тему можно попробовать.
Reddit
From the pcmasterrace community on Reddit
Explore this post and more from the pcmasterrace community
🔥36👍17❤7
https://twitter.com/jorgbrown/status/1616711913106444289
Это один из моих коллег. Наверное, он лучше всех разбирается в микро и макро компиляторных оптимизациях в мире. Он мне рассказывал про m68k, как важно следить за компилятором и просто я читал много его тредов. В прошлом году он сэкономил несколько миллионов долларов Гуглу. После 18 лет работы его уволили. Вообще никто не понимает, почему.
Я пока остался, но для Европы процесс увольнений в Гугле затянется на несколько месяцев. Что будет, то будет. Но проживать такие события интересно
Это один из моих коллег. Наверное, он лучше всех разбирается в микро и макро компиляторных оптимизациях в мире. Он мне рассказывал про m68k, как важно следить за компилятором и просто я читал много его тредов. В прошлом году он сэкономил несколько миллионов долларов Гуглу. После 18 лет работы его уволили. Вообще никто не понимает, почему.
Я пока остался, но для Европы процесс увольнений в Гугле затянется на несколько месяцев. Что будет, то будет. Но проживать такие события интересно
X (formerly Twitter)
Jorg Brown (@jorgbrown) on X
#googlelayoffs ended an amazing 18 years at Google. Honored they hired me all those years ago, grateful for the amazing people I worked with. If I could go back in time 18 years, I would absolutely join Google again. Where else could I https://t.co/yFrxkTGu1x…
😱138😢40🫡21🤯8🤔6❤4👍3🤬1
Донаты
Итак, этот момент настал. Я понял, что пара фондов читающих мой блог заработали несколько миллионов долларов за прошлый год.
В идеале я бы работал только на себя, может, это приблизит меня к этой цели. Без отдачи аудитории сложно вычитывать каждое слово, а с ростом аудитории растёт ответственность. Я верю, что это поможет мне увеличить качество блога в разы и реализовать амбициозные идеи.
Донаты:
https://www.patreon.com/danlark/ -- Patreon
https://boosty.to/danlark -- Patreon, но для русских читателей
https://www.paypal.com/donate/?hosted_button_id=UNZQYV2YP2RBE -- Paypal, если вы хотите остаться незаметным
ETH:
Маленькие суммы позволят получать доступ к постам на 1 день раньше (в итоге качество написанного текста будет расти). Большие донаты дадут возможность проводить регулярные 1:1 (менторство, обучение, консультации) со мной. Рекламы в канале пока ещё долго не будет.
Итак, этот момент настал. Я понял, что пара фондов читающих мой блог заработали несколько миллионов долларов за прошлый год.
В идеале я бы работал только на себя, может, это приблизит меня к этой цели. Без отдачи аудитории сложно вычитывать каждое слово, а с ростом аудитории растёт ответственность. Я верю, что это поможет мне увеличить качество блога в разы и реализовать амбициозные идеи.
Донаты:
https://www.patreon.com/danlark/ -- Patreon
https://boosty.to/danlark -- Patreon, но для русских читателей
https://www.paypal.com/donate/?hosted_button_id=UNZQYV2YP2RBE -- Paypal, если вы хотите остаться незаметным
ETH:
0xDD1b1927dF4533Dcc8975496670228fbC303F941 -- крипта для совсем незаметныхМаленькие суммы позволят получать доступ к постам на 1 день раньше (в итоге качество написанного текста будет расти). Большие донаты дадут возможность проводить регулярные 1:1 (менторство, обучение, консультации) со мной. Рекламы в канале пока ещё долго не будет.
Patreon
Get more from Danlark on Patreon
creating software, performance optimizations
🔥165👍57🤡25💅15❤14🗿13😁8😱3😢2🥴2😭1
Илья Токарь, мой сокомандник, засветился на Phoronix https://www.phoronix.com/news/LLVM-Google-Light-AVX-Option
Я писал про то, что поддерживать зоопарк железа достаточно трудно и из-за этого сложнее использовать новые инструкции процессоров. После 12 лет (AVX вышел в 2011) на таком разнообразии стало возможным делать шаги в сторону включения AVX по умолчанию, но есть несколько нюансов:
1. Герцовость процессора понижается, если использовать сложные инструкции из AVX/AVX2 на процессорах года до 2016. Для простоты можете считать, что если есть операция умножения или работа с float, то понизится, если нет, то нет
2. Стандартные инструкции вида загрузить/положить в память/сделать shuffle байт не понижают герцовость
3. В компиляторах есть флаги -mavx -mavx2 и так далее, которые не очень учитывают герцовость. В итоге, чтобы таких эффектов не было, можно было только разрешить работать с 16 байтными регистрами xmm семейства
В итоге Илья решил добавить так называемый LightAVX флаг, чтобы можно было использовать 32 байтные инструкции, которые не вредят окружению и не понижают герцовость. Доступно с LLVM 16.
Тем не менее хочу сказать, что просто включение AVX не даст много преимуществ, да, всякие копирования памяти может быть улучшатся, но самые большие ускорения вы скорее всего увидите из-за Bit Manipulation Instruction Set. Они умеют занулять младщий единичный бит, делать операции AND NOT (~x & y) и больше используются компиляторами. Сейчас включить BMI и не включить AVX невозможно, зато станет возможным включить LightAVX и BMI и насладиться большинством ускорений. Такое только подходит для пользователей, кто должен работать с большим разнообразием процессоров -- базы данных, большие cloud компании и тд. Если у вас есть контроль за железом, пользуйтесь всем, чем можно.
Я писал про то, что поддерживать зоопарк железа достаточно трудно и из-за этого сложнее использовать новые инструкции процессоров. После 12 лет (AVX вышел в 2011) на таком разнообразии стало возможным делать шаги в сторону включения AVX по умолчанию, но есть несколько нюансов:
1. Герцовость процессора понижается, если использовать сложные инструкции из AVX/AVX2 на процессорах года до 2016. Для простоты можете считать, что если есть операция умножения или работа с float, то понизится, если нет, то нет
2. Стандартные инструкции вида загрузить/положить в память/сделать shuffle байт не понижают герцовость
3. В компиляторах есть флаги -mavx -mavx2 и так далее, которые не очень учитывают герцовость. В итоге, чтобы таких эффектов не было, можно было только разрешить работать с 16 байтными регистрами xmm семейства
В итоге Илья решил добавить так называемый LightAVX флаг, чтобы можно было использовать 32 байтные инструкции, которые не вредят окружению и не понижают герцовость. Доступно с LLVM 16.
Тем не менее хочу сказать, что просто включение AVX не даст много преимуществ, да, всякие копирования памяти может быть улучшатся, но самые большие ускорения вы скорее всего увидите из-за Bit Manipulation Instruction Set. Они умеют занулять младщий единичный бит, делать операции AND NOT (~x & y) и больше используются компиляторами. Сейчас включить BMI и не включить AVX невозможно, зато станет возможным включить LightAVX и BMI и насладиться большинством ускорений. Такое только подходит для пользователей, кто должен работать с большим разнообразием процессоров -- базы данных, большие cloud компании и тд. Если у вас есть контроль за железом, пользуйтесь всем, чем можно.
Phoronix
Google Engineer Introduces "Light AVX" Support Within LLVM
Google engineer Ilya Tocar has introduced the notion of 'light' AVX support within the LLVM compiler infrastructure for utilizing some benefits of Advanced Vector Extensions (AVX) but trying to avoid the power/frequency impact that AVX-512 use has on older…
👍61🔥12🤡3❤1
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 инструкцию меньше, зато им стоит поддерживать, что старшие биты в хеше должны иметь достаточно энтропии.
Такие трейдоффы.
👍73🔥10🤡4❤3
На этой неделе была тьма анонсов про поиски. Вышел новый Bing, в Google анонсировали Bard.
Они интересны и холиварны, поэтому о них я рассказывать не буду, потому что техническая часть там не в моей компетенции :)
А зато мне хочется сильно похвалить команду GitHub за то, что теперь cs.github.com индексирует 45 миллионов репозиториев с 115 млрд файлов.
У обратных индексов по всему, что связано с кодом история достаточно давняя и не сильно заисследованная: Russ Cox рассказывал про то, что обратная индексация по триграмам и токенизация запроса по им работает достаточно хорошо, но на масштабах GitHub они признались, что такой подход работает только до поры до времени. Почему? Потому что мы любим писать всякие циклы через последовательности
Если вы будете использовать 4, 5 граммы, то есть индексировать 4-5 подряд символов в document_id и позицию, то индекс сильно вырастет, поэтому это как-то непрактично, а 2-граммы не сильно хорошо фильтруют. Но хочется добавить и подстроки побольше, чтобы быстрее фильтровать. Чтобы запрос хорошо фильтровал, надо чтобы разбивка n-grams у подстроки запроса была подмножеством разбивки документа (то есть если есть подстрока s в запросе, то любая надстрока S в документе должна иметь n-grams от s), иначе будет некорректный поиск. В итоге придумали схему, которая в среднем увеличивает индекс в пару раз и добавляет приличное количество подстрок бОльшей длины:
На каждую биграму посчитать хэш, поставить на позиции значения хешей. Взять только те подстроки, в которых все значения хешей внутри строго меньше, чем на краях. Так как хеши не зависят от подстрок, свойство о разбивки подстрок выполняется. С другой стороны количество строк увеличится в среднем в константу раз, так как количество подстрок попавших в индекс при переходе с длины n на n+1 уменьшается в среднем в экспоненциальное количество раз. Если аккуратно выписать все выражения, количество строк в индексе будет примерно в 2 раза больше, а по размеру в большую, но удобную константу, когда индексация происходит построчная. Инженерно можно ещё запретить слишком большие n-grams, хорошо пожать с алгоритмом и положить на SSD. В итоге будет индекс GitHub, который хорошо расширяется. Интересные задачи у них скорее всего связаны с метаданными, метаданные на 115млрд растут всё таки линейно, но об этом они ничего не написали :(
В итоге если вы ищете какое-нибудь выражения с очень частой подстрокой типа
В добавочку:
Пригласили на LLVM Code Generation and Optimization Symposium, буду рассказывать с коллегами про то как мы меняли std::sort в LLVM и в Google. Спойлер: у истории есть продолжение, а именно хоть огня и не было, а вот ускорений в проде по сравнению с микробенчмарками мы не увидели
https://llvm.org/devmtg/2023-02-25/
Если мне, конечно, одобрят визу в Канаду к концу февраля :)
Они интересны и холиварны, поэтому о них я рассказывать не буду, потому что техническая часть там не в моей компетенции :)
А зато мне хочется сильно похвалить команду GitHub за то, что теперь cs.github.com индексирует 45 миллионов репозиториев с 115 млрд файлов.
У обратных индексов по всему, что связано с кодом история достаточно давняя и не сильно заисследованная: Russ Cox рассказывал про то, что обратная индексация по триграмам и токенизация запроса по им работает достаточно хорошо, но на масштабах GitHub они признались, что такой подход работает только до поры до времени. Почему? Потому что мы любим писать всякие циклы через последовательности
for ( и поэтому они плохо фильтруют документ, если в запросе есть триграма for. В Google мы рассказывали, что долго использовали суффиксные структуры, но в итоге решили использовать решение о sparse n-grams, которое хорошо заработало, и в статье GitHub упоминается. Немного истории:Если вы будете использовать 4, 5 граммы, то есть индексировать 4-5 подряд символов в document_id и позицию, то индекс сильно вырастет, поэтому это как-то непрактично, а 2-граммы не сильно хорошо фильтруют. Но хочется добавить и подстроки побольше, чтобы быстрее фильтровать. Чтобы запрос хорошо фильтровал, надо чтобы разбивка n-grams у подстроки запроса была подмножеством разбивки документа (то есть если есть подстрока s в запросе, то любая надстрока S в документе должна иметь n-grams от s), иначе будет некорректный поиск. В итоге придумали схему, которая в среднем увеличивает индекс в пару раз и добавляет приличное количество подстрок бОльшей длины:
На каждую биграму посчитать хэш, поставить на позиции значения хешей. Взять только те подстроки, в которых все значения хешей внутри строго меньше, чем на краях. Так как хеши не зависят от подстрок, свойство о разбивки подстрок выполняется. С другой стороны количество строк увеличится в среднем в константу раз, так как количество подстрок попавших в индекс при переходе с длины n на n+1 уменьшается в среднем в экспоненциальное количество раз. Если аккуратно выписать все выражения, количество строк в индексе будет примерно в 2 раза больше, а по размеру в большую, но удобную константу, когда индексация происходит построчная. Инженерно можно ещё запретить слишком большие n-grams, хорошо пожать с алгоритмом и положить на SSD. В итоге будет индекс GitHub, который хорошо расширяется. Интересные задачи у них скорее всего связаны с метаданными, метаданные на 115млрд растут всё таки линейно, но об этом они ничего не написали :(
В итоге если вы ищете какое-нибудь выражения с очень частой подстрокой типа
for (int i = 42, то вы не будете искать пересечения триграм с for, которая находится в каждом файле, а будете искать в том числе какую-нибудь большую подстроку вида i = 42, что встречается реже. В итоге меньше проверок на вхождение, лучше фильтрация. А если вы ищете то, что находится в миллионах документов, скажем, вы просто ввели запрос for, то там не так важно что вернуть, непонятно что вы и хотите, если спрашиваете такое, и документов скорее всего будет много.В добавочку:
Пригласили на LLVM Code Generation and Optimization Symposium, буду рассказывать с коллегами про то как мы меняли std::sort в LLVM и в Google. Спойлер: у истории есть продолжение, а именно хоть огня и не было, а вот ускорений в проде по сравнению с микробенчмарками мы не увидели
https://llvm.org/devmtg/2023-02-25/
Если мне, конечно, одобрят визу в Канаду к концу февраля :)
Microsoft
Microsoft Bing | Get to know Bing
Enhance your search experience with Microsoft Bing, the fast, secure, AI-powered search engine. Discover world-class performance, built-in security, and advanced tools to help you find what you need quickly and securely.
🔥59👍24🤔1
SIMDProto
Я убил приличное количество времени думая о проблемах с памятью в последнее время. Одна из них -- можно ли как-то быстрее парсить protobufs. Хочу здесь поделиться, с какими проблемами я столкнулся, и почему это сложнее, чем кажется.
Самая главная проблема, что практически невозможно парсить varints быстро. Попробую дать интуицию:
В JSON вы можете найти символы ", {, }, [, ], : достаточно быстро, они будут в какой-то степени разделителями, показывая где начало и где конец поля. После этого вам надо найти все позиции и на каждый найденный символ найти второй соответствующий, например, на открывающую скобку -- закрывающую. Это зависимость (цепочка) длины 1, остальные байты легко пропускаются, итерации по битам делать не надо.
У протобуфов числа устроены таким образом, что мы должны смотреть на старший бит байта, чтобы понять, какой следующий -- что это продолжение числа или начало нового поля? В итоге, чтобы понять разделители и их индексы, нужно решать достаточно длинные цепочки, и в итоге парсер прыгает как-то по одному-двум байтам. Если хочется выйти из лимита, как 1 cycle на байт для чисел, тегов и тд, нужно уметь обрабатывать varints пачками, притом пачками в том смысле, чтобы varint спокойно могли находиться между других полей, в том числе широкие вектора могут состоять из такого ужаса:
1. [строка][tag][varint][tag][size][строка]
2. [varint][tag][varint][tag][varint]
И так далее. В итоге если вы посчитаете огромное количество различных конфигураций, будет не так красиво и в итоге нужна ветвистая логика для всех случаев, сложные инструкции как tzcnt, чтобы считать пропускные биты и итерации по битам с 2 cycle на байт.
Тем не менее у нас есть кандидаты для парсинга varint с помощью SIMD.
Любые попытки написать даже простой код заканчиваются неудачно. В итоге сейчас SIMDJSON быстрее и популярнее протобуфов. Даже по скорости на 1 бит информации (JSON обычно весит больше, чем прото).
Менять формат абсолютно другая история. Но пробить гигабайты в секунду у протобуфов становится какой-то непосильной задачей, которую я скоро перестану решать.
Я убил приличное количество времени думая о проблемах с памятью в последнее время. Одна из них -- можно ли как-то быстрее парсить protobufs. Хочу здесь поделиться, с какими проблемами я столкнулся, и почему это сложнее, чем кажется.
Самая главная проблема, что практически невозможно парсить varints быстро. Попробую дать интуицию:
В JSON вы можете найти символы ", {, }, [, ], : достаточно быстро, они будут в какой-то степени разделителями, показывая где начало и где конец поля. После этого вам надо найти все позиции и на каждый найденный символ найти второй соответствующий, например, на открывающую скобку -- закрывающую. Это зависимость (цепочка) длины 1, остальные байты легко пропускаются, итерации по битам делать не надо.
У протобуфов числа устроены таким образом, что мы должны смотреть на старший бит байта, чтобы понять, какой следующий -- что это продолжение числа или начало нового поля? В итоге, чтобы понять разделители и их индексы, нужно решать достаточно длинные цепочки, и в итоге парсер прыгает как-то по одному-двум байтам. Если хочется выйти из лимита, как 1 cycle на байт для чисел, тегов и тд, нужно уметь обрабатывать varints пачками, притом пачками в том смысле, чтобы varint спокойно могли находиться между других полей, в том числе широкие вектора могут состоять из такого ужаса:
1. [строка][tag][varint][tag][size][строка]
2. [varint][tag][varint][tag][varint]
И так далее. В итоге если вы посчитаете огромное количество различных конфигураций, будет не так красиво и в итоге нужна ветвистая логика для всех случаев, сложные инструкции как tzcnt, чтобы считать пропускные биты и итерации по битам с 2 cycle на байт.
Тем не менее у нас есть кандидаты для парсинга varint с помощью SIMD.
Любые попытки написать даже простой код заканчиваются неудачно. В итоге сейчас SIMDJSON быстрее и популярнее протобуфов. Даже по скорости на 1 бит информации (JSON обычно весит больше, чем прото).
Менять формат абсолютно другая история. Но пробить гигабайты в секунду у протобуфов становится какой-то непосильной задачей, которую я скоро перестану решать.
😭57👍15👀5🤡4❤3🔥1
О таких вещах хочется писать почти сразу :)
https://github.com/facebook/zstd/pull/3517
Нашли ещё поцарапанные данные в ZSTD. Удивительный факт в том, что этому багу 2 года.
На этот раз никакое тестирование, фаззинг, который 2 года фаззил этот код, не помог. Нашли случайно, а баг ещё одна манифестация Silent Data Corruption. Из хорошего это замечательный кейс для фаззера, почему не нашел, что можно сделать, чтобы фаззинг такое находил хотя бы за недели.
Пишите чексуммы даже в таких примитивах, любые библиотеки, ядро, процессоры содержат баги корректности.
Советую обновиться тем, кто использует. Проблемы были в ZSTD level 13-22. decompress(compress) (редко) возвращал другие данные.
https://github.com/facebook/zstd/pull/3517
Нашли ещё поцарапанные данные в ZSTD. Удивительный факт в том, что этому багу 2 года.
На этот раз никакое тестирование, фаззинг, который 2 года фаззил этот код, не помог. Нашли случайно, а баг ещё одна манифестация Silent Data Corruption. Из хорошего это замечательный кейс для фаззера, почему не нашел, что можно сделать, чтобы фаззинг такое находил хотя бы за недели.
Пишите чексуммы даже в таких примитивах, любые библиотеки, ядро, процессоры содержат баги корректности.
Советую обновиться тем, кто использует. Проблемы были в ZSTD level 13-22. decompress(compress) (редко) возвращал другие данные.
GitHub
[bug-fix] Fix rare corruption bug affecting the block splitter by terrelln · Pull Request #3517 · facebook/zstd
TLDR: This is a very rare bug affecting the block splitter. Only levels using the optimal parser (levels 13 and above depending on the source size), or users who explicitly enable the block splitte...
👍64😐24👏13😱7❤6🔥6🥱2
C++17 -> C++20
По традиции, рассказываю, что может пойти не так, когда вы хотите переехать с C++17 на C++20. В среднем вы не должны ничего заметить, но различий достаточно, чтобы заглянуть в страшные уголки плюсов.
От самых страшных до не самых страшных
1. Spaceship operator<=>
Единственная фича, которая уменьшила количество слов в стандарте и добавила головной боли компиляторным инженерам. Сломаться может интересно: если у типа есть implicit оператор вида
Тогда <=> оператор в первую очередь применит оператор меньше к кастуемому типу, в итоге
вернёт 1 в C++17, 0 в C++20.
Достаточно опасно, так как сильно меняет семантику. Как чинить? Писать explicit operator. Пример падения в проде.
2. operator== ambiguity
На самом деле та же проблема. Бьярне и компания написали целую статью про это тут. Если коротко, то в C++20 написали правила, чтобы операторы == и != вели себя логичным образом, что !(a == b) это a != b. С другой стороны это создаёт проблему в духе
И в итоге operator== и operator!= считаются одними и те же функциями. Это поломало много проектов, поэтому компиляторы быстро взяли фикс из C++23, и проблем больше нет https://godbolt.org/z/7e4E6qhbM.
3. Всякие проблемы с std::string_view против std::vector<std::string*like> и тд
Конструкция
Теперь создаёт палёный string_view из локации, где "a" -- начало, потом где "b" -- конец, а в C++17 создавало 2 строки. Санитайзеры не ловят. https://gcc.godbolt.org/z/jboa5rbfa. Самое ядро заключается в том, что
Зато можно всякого интересного придумать.
Например, можно добавить в libc++ код в духе
И он будет падать в рантайме, в санитайзерах, орать warningами и быть ещё standard compliant. Выстрел в ногу, но всё таки элегантно чинится.
4. Всё остальное кажется достаточно минорным, атомики перестали быть trivially constructible, поэтому их в union не очень стоит класть, добавили слова concept, requires, добавились constexpr контейнеры, поэтому все шаблоны вектора должны быть полными типами. Стали делать std::move на начальное значение в std::accumulate, поэтому функция аккумулирования перестала принимать lvalue references. Aggregates теперь не компилируются, если есть конструкторы. Всё это чинится проходом по всему и достаточно прямолинейно.
Я думаю по сложности C++14 -> C++17 был проще, чем C++17 -> C++20, но тоже со своими интересными решениями, как noexcept как часть типа и тд. Всё равно суммарно набирается работы, хоть и не так много.
Самая интересная часть, которую пока никто не знает наверняка, насколько дольше стали компилироваться проекты.
По традиции, рассказываю, что может пойти не так, когда вы хотите переехать с C++17 на C++20. В среднем вы не должны ничего заметить, но различий достаточно, чтобы заглянуть в страшные уголки плюсов.
От самых страшных до не самых страшных
1. Spaceship operator<=>
Единственная фича, которая уменьшила количество слов в стандарте и добавила головной боли компиляторным инженерам. Сломаться может интересно: если у типа есть implicit оператор вида
struct Int {
int i;
operator bool() const {
// Returns true if not 0, false if 0.
return i;
}
};
Тогда <=> оператор в первую очередь применит оператор меньше к кастуемому типу, в итоге
std::pair{Int{1}, Int{2}} < std::pair{Int{3}, Int{4}}вернёт 1 в C++17, 0 в C++20.
Достаточно опасно, так как сильно меняет семантику. Как чинить? Писать explicit operator. Пример падения в проде.
2. operator== ambiguity
struct B {};
struct D : B {
bool operator==(const B& other);
};
D d;
bool eq = d == d; // работает в C++17, но не в C++20
На самом деле та же проблема. Бьярне и компания написали целую статью про это тут. Если коротко, то в C++20 написали правила, чтобы операторы == и != вели себя логичным образом, что !(a == b) это a != b. С другой стороны это создаёт проблему в духе
struct S {
friend bool f(S, const S&) { ... }
friend bool f(const S&, S) { ... }
};
bool b = f(S{}, S{});
И в итоге operator== и operator!= считаются одними и те же функциями. Это поломало много проектов, поэтому компиляторы быстро взяли фикс из C++23, и проблем больше нет https://godbolt.org/z/7e4E6qhbM.
3. Всякие проблемы с std::string_view против std::vector<std::string*like> и тд
Конструкция
{"a", "b"} вызывает лёгкий ужас, так как в C++20 в string_view добавили конструктор от 2 итераторов и "a" и "b" являются const char* start и const char* end, что очень плохо заканчивается: вы читаете чёрт пойми какую память.std::vector<std::string_view>{{"a", "b"}}Теперь создаёт палёный string_view из локации, где "a" -- начало, потом где "b" -- конец, а в C++17 создавало 2 строки. Санитайзеры не ловят. https://gcc.godbolt.org/z/jboa5rbfa. Самое ядро заключается в том, что
{"a", "b"} создают не initializer_list, а обычную string_viewЗато можно всякого интересного придумать.
Например, можно добавить в libc++ код в духе
template <int M, int N>
constexpr basic_string_view(char_type (&a)[M], char_type (&b)[N]) : basic_string_view() {
_LIBCPP_ASSERT(&a == &b);
}
И он будет падать в рантайме, в санитайзерах, орать warningами и быть ещё standard compliant. Выстрел в ногу, но всё таки элегантно чинится.
4. Всё остальное кажется достаточно минорным, атомики перестали быть trivially constructible, поэтому их в union не очень стоит класть, добавили слова concept, requires, добавились constexpr контейнеры, поэтому все шаблоны вектора должны быть полными типами. Стали делать std::move на начальное значение в std::accumulate, поэтому функция аккумулирования перестала принимать lvalue references. Aggregates теперь не компилируются, если есть конструкторы. Всё это чинится проходом по всему и достаточно прямолинейно.
Я думаю по сложности C++14 -> C++17 был проще, чем C++17 -> C++20, но тоже со своими интересными решениями, как noexcept как часть типа и тд. Всё равно суммарно набирается работы, хоть и не так много.
Самая интересная часть, которую пока никто не знает наверняка, насколько дольше стали компилироваться проекты.
GitHub
Fix word boundary assertions under C++20 by BigRedEye · Pull Request #345 · intel/hyperscan
In C++20 with P1614R2 implemented, zero-width assertions \b and \B do not work. For example, the following code fails with "Pattern can never match":
#include <hyperscan/sr...
#include <hyperscan/sr...
👍62🤯38🥴9🤡6❤4🔥4❤🔥2😁2🤮2👏1
Google Performance Tips of the Week
Мои коллеги выложили https://abseil.io/fast/. Я очень надеюсь там публиковаться, думаю, один эпизод в следующие месяцы будет под моим авторством.
Это похожий на сборник C++ Tips of the Week https://abseil.io/tips/ от Google. Хоть каждую неделю мы не выкладываем эпизоды, но сохранилась традиция часто писать про одну идею, чтобы рассказать что-то интересное и полезное, особенно тем, кто задается вопросом, а можно ли что-то улучшить в их приложениях.
Это хорошие, понятные, промодерированные, проверенные временем эпизоды с 6-7 ревью от топ экспертов в Google.
Такие моменты мне лично сложно не ценить, почти ни в какой другой компании так открыто говорить о том, что мы увидели на масштабе флота датацентров нельзя.
Мои коллеги выложили https://abseil.io/fast/. Я очень надеюсь там публиковаться, думаю, один эпизод в следующие месяцы будет под моим авторством.
Это похожий на сборник C++ Tips of the Week https://abseil.io/tips/ от Google. Хоть каждую неделю мы не выкладываем эпизоды, но сохранилась традиция часто писать про одну идею, чтобы рассказать что-то интересное и полезное, особенно тем, кто задается вопросом, а можно ли что-то улучшить в их приложениях.
Это хорошие, понятные, промодерированные, проверенные временем эпизоды с 6-7 ревью от топ экспертов в Google.
Такие моменты мне лично сложно не ценить, почти ни в какой другой компании так открыто говорить о том, что мы увидели на масштабе флота датацентров нельзя.
abseil.io
abseil / Performance Guide
An open-source collection of core C++ library code
🔥73👍14🗿5
Paxos, Raft и тд
Моё отношение к консенсусным протоколам менялось. В универе я их понял на уровне, что консенсусы возможны, потом на практике я видел как баги в Paxos/Raft есть и будут всегда, но последние 1-2 года багов стало как-то сильно меньше, и привыкнув к алгоритмам, потихоньку приходит осознание в их детальных различиях, в том числе полученные горьким опытом.
Мне захотелось ещё раз прочитать разницу между Paxos и Raft и как они живут вместе с FLP теоремой.
Последняя гласит, что детерминированный консенсус невозможен в полностью асинхронной сети, когда сообщения могут не доставляться или доставляться с задержкой. Выбор лидера в Raft может никогда не завершиться, на практике борются с этим с помощью случайных таймаутов. У Paxos два proposer могут никогда не договориться о решении, что тоже на практике лечат случайными таймаутами. Это отличный вопрос на собеседовании, чтобы отсечь тех, кто видит в Raft ответы на все вопросы, о негативных результатах надо тоже знать.
По моему мнению на практике самая большая разница в том, что при потере лидера Paxos может медленнее восстанавливаться:
1. Paxos выбирает лидера исходя из id узла, и если он отстает на немного от закоммиченных значений, то ему надо их применить, поэтому если сервер с большим id выигрывает, бывают проблемы и спайки в ожидании запросов. Случайный id не всегда хорошо коррелирует с живностью. На практике в больших системах много работы надо доделать, например, всякие обновления метаданных, и это начинает быть заметно.
2. В Raft узлы с бОльшим количеством закоммиченных чаще выигрывают, но зато у Raft больше шансов получить ситуацию, когда много проголосовали за 2 кандидата и надо переизбрать ещё раз. Вторая ситуация происходит реже, поэтому Raft более практичен.
Другое отличие, что так как алгоритмы достаточно сложные для программиста и хотелось бы едва понять любую из статей, происходит следующее
1. Raft и Paxos имплементируются по статьям.
2. В Raft есть проблемы с network partitioning, если узлы видят разные подмножества, может быть бабах (Cloudflare). Подробный разбор и как сконфигурировать etcd и всё сломать можно прочитать в статье.
Дальше происходит, что написание нового кода приводит к багам, которые чинятся годами. Тем не менее, ситуация намного улучшилась, в etcd 3.4 добавили Raft Prevotes, чтобы избежать проблем с сетью. Но потом чинить баги всё равно пришлось. Вещи становятся лучше со временем в таких примитивах, это не может не радовать.
Самое удивительное в этой индустрии, насколько она наполнена людьми, которые, мол, думают, что поняли консенсус. Из-за того, что консенсусы нетривиальны, редки, я вижу много от людей в виде: "выучи TLA+", "напиши автоматическое доказательство", "а ты слышал про EPaxos, он лучше, чем Paxos". Ребят, мне бы понять первую статью. И не врать себе, что задача просто сложная.
Я очевидно во всем не разобрался, но спустя годы оно стало лучше. Поэтому если вам кажется, что вы не можете это понять, дайте себе время. За несколько месяцев и лет, из-за важности свойств, сложность осядет, и вы поймете, что к чему. Читайте потихоньку, пытайтесь понять примитивы, читайте имплементации (хороших много на github), не бойтесь спрашивать.
[1] Различия Paxos и Raft
[2] Вообще читайте всё, что написано от Heidi Howard, она топ эксперт в мире по консенсусным протоколам
[3] etcd network partitioning failure, инцидент от Cloudflare
[4] Имплементации Raft
[5] Ещё более простое объяснение Raft с иммутабельными цепочками. Чем больше иммутабельности, тем легче нам понимаются перезаписи и тд
Моё отношение к консенсусным протоколам менялось. В универе я их понял на уровне, что консенсусы возможны, потом на практике я видел как баги в Paxos/Raft есть и будут всегда, но последние 1-2 года багов стало как-то сильно меньше, и привыкнув к алгоритмам, потихоньку приходит осознание в их детальных различиях, в том числе полученные горьким опытом.
Мне захотелось ещё раз прочитать разницу между Paxos и Raft и как они живут вместе с FLP теоремой.
Последняя гласит, что детерминированный консенсус невозможен в полностью асинхронной сети, когда сообщения могут не доставляться или доставляться с задержкой. Выбор лидера в Raft может никогда не завершиться, на практике борются с этим с помощью случайных таймаутов. У Paxos два proposer могут никогда не договориться о решении, что тоже на практике лечат случайными таймаутами. Это отличный вопрос на собеседовании, чтобы отсечь тех, кто видит в Raft ответы на все вопросы, о негативных результатах надо тоже знать.
По моему мнению на практике самая большая разница в том, что при потере лидера Paxos может медленнее восстанавливаться:
1. Paxos выбирает лидера исходя из id узла, и если он отстает на немного от закоммиченных значений, то ему надо их применить, поэтому если сервер с большим id выигрывает, бывают проблемы и спайки в ожидании запросов. Случайный id не всегда хорошо коррелирует с живностью. На практике в больших системах много работы надо доделать, например, всякие обновления метаданных, и это начинает быть заметно.
2. В Raft узлы с бОльшим количеством закоммиченных чаще выигрывают, но зато у Raft больше шансов получить ситуацию, когда много проголосовали за 2 кандидата и надо переизбрать ещё раз. Вторая ситуация происходит реже, поэтому Raft более практичен.
Другое отличие, что так как алгоритмы достаточно сложные для программиста и хотелось бы едва понять любую из статей, происходит следующее
1. Raft и Paxos имплементируются по статьям.
2. В Raft есть проблемы с network partitioning, если узлы видят разные подмножества, может быть бабах (Cloudflare). Подробный разбор и как сконфигурировать etcd и всё сломать можно прочитать в статье.
Дальше происходит, что написание нового кода приводит к багам, которые чинятся годами. Тем не менее, ситуация намного улучшилась, в etcd 3.4 добавили Raft Prevotes, чтобы избежать проблем с сетью. Но потом чинить баги всё равно пришлось. Вещи становятся лучше со временем в таких примитивах, это не может не радовать.
Самое удивительное в этой индустрии, насколько она наполнена людьми, которые, мол, думают, что поняли консенсус. Из-за того, что консенсусы нетривиальны, редки, я вижу много от людей в виде: "выучи TLA+", "напиши автоматическое доказательство", "а ты слышал про EPaxos, он лучше, чем Paxos". Ребят, мне бы понять первую статью. И не врать себе, что задача просто сложная.
Я очевидно во всем не разобрался, но спустя годы оно стало лучше. Поэтому если вам кажется, что вы не можете это понять, дайте себе время. За несколько месяцев и лет, из-за важности свойств, сложность осядет, и вы поймете, что к чему. Читайте потихоньку, пытайтесь понять примитивы, читайте имплементации (хороших много на github), не бойтесь спрашивать.
[1] Различия Paxos и Raft
[2] Вообще читайте всё, что написано от Heidi Howard, она топ эксперт в мире по консенсусным протоколам
[3] etcd network partitioning failure, инцидент от Cloudflare
[4] Имплементации Raft
[5] Ещё более простое объяснение Raft с иммутабельными цепочками. Чем больше иммутабельности, тем легче нам понимаются перезаписи и тд
The Cloudflare Blog
A Byzantine failure in the real world
When we review design documents at Cloudflare, we are always on the lookout for Single Points of Failure (SPOFs). But is redundancy enough? In this post we present a timeline of a real world incident, and how an interesting failure mode known as a Byzantine…
👍97🔥30❤11👏2
Sparse Ngrams Devlog. Part 1
Следующие несколько постов, дней, недель я буду много постить о сайд проекте, а именно о GitHub Indexing Codesearch, а именно Sparse Ngrams solutions. Мне надоели Russ Cox trigram индекс и Zoekt. Посмотрим куда приведёт:
https://github.com/danlark1/sparse_ngrams
Основную идею я уже писал в блоге выше, а именно мы должны взять все ngrams, хеши биграм которых на концах больше, чем в середине. Так как хеши не зависят от input, то подстроки будут иметь подмножество такого разбиения. А всего таких ngram не более 2n.
Понятно, что при запросе не надо разбивать таким алгоритмом и в статье GitHub сказано, что
У меня в тесте для
А covering ngrams меньше, они более репрезентативны и должны быстрее отвечать на запрос из-за ngram
Как строятся такие ngrams и coverage? Сначала добавляем все триграмы как мельчайшие единицы. Потом алгоритм в точности является sliding min/max window (LeetCode полезно решать вообще). Когда мы добавляем следующий хеш в стек, надо выкинуть все элементы, которые меньше по хешу из конца. В итоге в первом случае мы когда убираем из стека, мы добавляем этот range ngrams, а во втором случае добавляем все убывающие последовательности. На картинке в статье, к сожалению, ошибка (пропущена "ste"). Covering ngrams в строке "chester " (с пробелом) в этом случае будут "chester ". Потому что пока все значение после девятки меньше девяти, то мы будем добавлять в стек (один раз уберем из стека по ходу, но эту ngram не добавим пока не дойдём до конца), а когда наткнёмся на 7, надо будет всё убрать до начала и в итоге мы найдём очень большую ngram. А для подстроки "chester" (без пробела) covering ngrams будут "che", "hes", "este", "ter". Потому что когда мы дойдём до нулевого хеша, у нас sliding window закончится, и надо обработать хвост. Единственная возрастающая последовательность это "1 2", поэтому добавляем "este", остальное -- обычные триграмы как мельчайшие единицы. Асимптотика -- линейная, потому что добавляем и убираем из стека каждый элемент суммарно не более двух раз.
Алгоритм весь получился на 70 строк кода.
Понятное дело дальше будет интересно, потому что надо будет доводить до инженерного решения. А там шардирование, большие ngram не нужны, фаззинг, тестирование и тд. 70 строк ещё можно математически доказать, дальше не очень.
Мораль: за 70 строк кода написали ядро, нашли ошибку в статье github (не все подстроки имеют разбиение, что все ngrams содержатся в надстроках -- забыли рассказать о деталях), и алгоритмы тоже пригождаются.
Следующие несколько постов, дней, недель я буду много постить о сайд проекте, а именно о GitHub Indexing Codesearch, а именно Sparse Ngrams solutions. Мне надоели Russ Cox trigram индекс и Zoekt. Посмотрим куда приведёт:
https://github.com/danlark1/sparse_ngrams
Основную идею я уже писал в блоге выше, а именно мы должны взять все ngrams, хеши биграм которых на концах больше, чем в середине. Так как хеши не зависят от input, то подстроки будут иметь подмножество такого разбиения. А всего таких ngram не более 2n.
Понятно, что при запросе не надо разбивать таким алгоритмом и в статье GitHub сказано, что
At query time, we use the exact same algorithm, but keep only the covering ngrams, as the others are redundant. Covering ngrams -- такой же алгоритм, только надо удостовериться, нет никакой подстроки другой в множестве.У меня в тесте для
for(int i=42 как раз получается интересная история: всяких ngram много:
"for", "or(", "for(", "r(i", "for(i", "(in", "int", "(int", "nt ", "t i", " i=", "t i=", "i=4", "t i=4", "nt i=4", "(int i=4", "=42"А covering ngrams меньше, они более репрезентативны и должны быстрее отвечать на запрос из-за ngram
=42 и (int i=4."for(i", "(int i=4", "=42"Как строятся такие ngrams и coverage? Сначала добавляем все триграмы как мельчайшие единицы. Потом алгоритм в точности является sliding min/max window (LeetCode полезно решать вообще). Когда мы добавляем следующий хеш в стек, надо выкинуть все элементы, которые меньше по хешу из конца. В итоге в первом случае мы когда убираем из стека, мы добавляем этот range ngrams, а во втором случае добавляем все убывающие последовательности. На картинке в статье, к сожалению, ошибка (пропущена "ste"). Covering ngrams в строке "chester " (с пробелом) в этом случае будут "chester ". Потому что пока все значение после девятки меньше девяти, то мы будем добавлять в стек (один раз уберем из стека по ходу, но эту ngram не добавим пока не дойдём до конца), а когда наткнёмся на 7, надо будет всё убрать до начала и в итоге мы найдём очень большую ngram. А для подстроки "chester" (без пробела) covering ngrams будут "che", "hes", "este", "ter". Потому что когда мы дойдём до нулевого хеша, у нас sliding window закончится, и надо обработать хвост. Единственная возрастающая последовательность это "1 2", поэтому добавляем "este", остальное -- обычные триграмы как мельчайшие единицы. Асимптотика -- линейная, потому что добавляем и убираем из стека каждый элемент суммарно не более двух раз.
Алгоритм весь получился на 70 строк кода.
Понятное дело дальше будет интересно, потому что надо будет доводить до инженерного решения. А там шардирование, большие ngram не нужны, фаззинг, тестирование и тд. 70 строк ещё можно математически доказать, дальше не очень.
Мораль: за 70 строк кода написали ядро, нашли ошибку в статье github (не все подстроки имеют разбиение, что все ngrams содержатся в надстроках -- забыли рассказать о деталях), и алгоритмы тоже пригождаются.
The GitHub Blog
The technology behind GitHub’s new code search
A look at what went into building the world's largest public code search index.
👍37❤5🔥2👎1