Оставляю для себя потом прочитать, довольно важная тема оптимизации программ на Rust в одном единственном посте. Старый пост Achieving warp speed with Rust, 2017-го аж года, но при этом вроде бы актуальный. Единственное но, разные штуки, вроде test::black_hole пока доступны только в nightly и для них нужно включать #![feature(test)].

Podlodka #209 – Операционные системы

Долго представлять эту тему не нужно, ведь выпуск входит в «золотой фонд фундаментальных выпусков» Podlodka и занимает место рядышком с "базами данных". Все, как вы любите – погружение в историю, разбор базовых компонентов и детские вопросы «а как загружается ОС?» с подробнейшими ответами на них. Под конец немного философских размышлений об упадке архитектуры ОС и стагнирующем настоящем, а также вероятности наступления светлого будущего. Осторожно, выпуск щедро приправлен байками!

Managed Kubernetes от Selectel для современных проектов: https://slc.tl/Gz62X, промокод Podlodka дает 1000 рублей на услугу. Вводить сюда: https://my.selectel.ru/vpc/

Сайт: https://podlodka.io/209
Soundcloud: https://bit.ly/podlodka-209
iTunes: https://apple.co/2vCBRcs 
Я.Музыка: https://bit.ly/32lGgNC

Поддержи лучший подкаст про IT: https://www.patreon.com/podlodka

Я сейчас изучаю проектирование распределённых асинхронных систем. В рамках этого проекта посмотрел доклад «Алгоритмы консенсуса. При чем тут Node.is?» В нём Андрей Печкуров рассказывает про проблематику распределённых систем, CAP-теорему, алгоритмы консенсуса и подробно разбирает один из них.

Посмотрите доклад — распределенные системы сейчас повсюду, полезно понимать, какие сложности возникают при их создании и эксплуатации.

#проектирование

Software Engineering at Google

In March, 2020, we published a book titled “Software Engineering at Google” curated by Titus Winters, Tom Manshreck and Hyrum Wright.

The Software Engineering at Google book (“SWE Book”) is not about programming, per se, but about the engineering practices utilized at Google to make their codebase sustainable and healthy. (These practices are paramount for common infrastructural code such as Abseil.)

We are happy to announce that we are providing a PDF digital copy of this book free of charge. Of course, we encourage you to get yourself a hard copy from O’Reilly if you wish.

https://abseil.io/resources/swe-book

Книга https://abseil.io/resources/swe_at_google.2.pdf

Досмотрел наконец-то Crust of Rust: Dispatch and Fat Pointers.

Jon, как обычно достаточно подробно, рассказывает о жирных указателях, unsized типах, диспатчинге и смежных темах.

Если вы не понимаете что-то из описанных тем и у вас есть достаточно времени на просмотр — рекомендую.

Птичка на хвосте принесла 😉 отличный репозиторий с книжками по Software Design https://github.com/mhadidg/software-architecture-books #books

Вполне себе известный Dan Luu запостил (обновил?) список важных и нужных блогов. Налетайте.

https://danluu.com/programming-blogs/

Дочитал Практическую криптографию Шнайера.

Вкусно и грустно. Насколько я правильно помню, ни одна проблема из упомянутых в книге 2004-го года так и не решена

Команда Telegram отдала ресурсы проекта TON сообществу сторонних разработчиков

Telegram передал домен ton.org и репозиторий проекта на GitHub сообществу разработчиков, которые теперь работают над TON.

«Мы рады видеть высокий уровень постоянного интереса сообщества к поддержке и развитию технологии TON. Поскольку сам Telegram больше не участвует в проекте и мы больше не используем связанные ресурсы, мы готовы рассмотреть возможность их передачи представителю сообщества для дальнейшего использования», — написала команда TON.

Теперь на сайте ton.org лежит уже новая информация от команды The Open Network (она же Newton). Этот ресурс больше не имеет ничего общего с Telegram.

Наконец написал статью о том как я пишу программы в самом широком смысле: как организовываю себя, как планирую структуру в самом начале, как планирую добавление сложной фичи.

Рассмотрел это на конкретном примере недавно реализованной программы для изучения слов.

После этой статьи вы будете использовать туду-пункты через соответствующее расширение вашего текстового редактора (я надеюсь хаха).

А даже если вы и умете самоорганизовываться, то надеюсь статья даст вам много полезных идей.

https://optozorax.github.io/how-i-write-programs

Занимательная статья об оптимизации CRDT (Conflict-free replicated data type, один из многих вариантов реализации конкурентного редактирования).

5000x faster CRDTs: An Adventure in Optimization

Там есть немного раста, много js-а и всякие занимательные штуки, рекомендую к прочтению :p

https://matklad.github.io/2021/09/04/fast-rust-builds.html

matklad как обычно дело говорит, на этот раз про скорость компиляции

#prog #rust #моё #article

Здрасьте. Сегодня поста не будет — но только потому, что я решил написать статью для Хабра. Собственно, вот она.

И напоминаю: если вам это понравилось — поддержите копеечкой автора, я вам благодарен буду: 4274 3200 5402 8520.

Нередко в базах данных и вообще любой работы с массивами возникают сложения чисел с плавающей точкой. С ними вроде всё хорошо, IEEE 754 стандарт давно устоялся, но чем больше вы складываете чисел, тем больше накапливается ошибка. Ещё хуже, если вы суммируйте в разных потоках или машинах, результаты могут быть разные и надо писать отдельные проверки на сравнения. Ошибка, конечно же, идёт из округлений.

Кейс: вы работаете с данными и считайте порог для их удаления. Доверять только одному процессу с удалением строго нельзя, поэтому часто делают кворумные джобы, где запускают много одинаковых бинарей, которые обязаны договориться о том, что данные можно удалять. Это позволяет выкладывать новый код на staging, не боясь, что данные удалятся (например, кворум не наберётся, если из 3 реплик мы выложим новый плохой код только на одну). Нередкие проблемы, которые я видел в проде своими глазами были связаны с тем, что удаления не могли договориться из-за того, что вокруг порога X одни джобы считали X - eps, другие X + eps. В итоге данные не удалялись и репортились в алёрт о том, что всё разъехалось, не страшно для людей, но бесит разработчиков.

Я настоятельно рекомендую, конечно же, сравнивать с eps в общем случае, но если уж не получается, то наука приготовила для нас интересные алгоритмы, которые позволяют уменьшить ошибку очень сильно. В наивном сложении после сложения n чисел будет ошибка ~machine_eps * n * сумму_модулей, где machine_eps — машинная точность, для float это примерно 6*10^-8, для double это примерно 10^-16.

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

Другой способ это использовать алгоритм от Shewchuk, который просто сохраняет все ошибки в массив и их складывает, пока не договорится, что ошибка после всех округлений нулевая, тоже использует O(n) памяти. Прелесть этого алгоритма, что он работает за линейное время в отличие от сортировки.

Часто забывают об алгоритме Кахана, который не требует ни дополнительной памяти, ни почти не зависит от порядка сложения, зато достигает намного более серьёзной точности, а именно ~(2 * machine_eps + n * machine_eps^2)*сумму_модулей. Самый сок идёт от квадрата машинной точности, что перебить количеством элементов становится уже сложнее (надо 10^16 и 10^32 элементов соответственно).

Сам алгоритм выглядит как переливание значений, но основная идея в том, что в наивном алгоритме большинство проблем происходят из-за сложения больших чисел с маленькими, надо подвигать мантиссу достаточно сильно и ошибка накапливается.

float Naive(const std::vector<float>& v) {
float sum = 0;
for (const float f : v) {
sum += f; // Problem that 'sum' can be big and 'f' is small.
}
return f;
}

float KahanSum(const std::vector<float>& v) {
float sum = 0.0; // Final sum
float err = 0.0; // Error compensation
float y; // v[i] - C
float t; // Temporary for sum
for (const float f : v) {
y = f - err; // Magic is here, error is compensated from input.
t = sum + y;
err = t - sum - y;
sum = t;
}
return sum;
}

Алгоритм требует в 4 раза больше float операций, но всё ещё векторизируется. Доказательство ошибки я выношу за рамки одного поста, оно сложное и даже написано в Кнуте. Плюсы от этого алгоритма в том, что теперь сравнивать можно с машинным epsilon, а не с достаточно большим как это было в обычном суммировании. Можно меньше боятся расхождений и делать более мягкие пороги на оценку с миллиардами элементов.

[1] Kahan summation wikipedia
[2] Лекция в Hamburg University про округления и KahanSummation доказательства
[3] Rust Kahan Summation crate
[4] ClickHouse KahanSum и документация по функции sumKahan
[5] Schewchuk algorithm for exact floating sum
[6] Theory behind floating point comparison
[7] What Every Computer Scientist Should Know About Floating-Point Arithmetic

#prog #rust #article

Статья о распространённых плохих практиках новичков в Rust