test

Писал quicksort для одной велосипедной библиотеки(про нее как-нибудь в другой раз), и мне стало лень писать еще и heapsort для последних шагов. Поэтому просто выбрал в качестве pivot случайный элемент массива. Стало интересно, насколько такое решение защищает от worst case. Интересное:

We will prove that for any given array input array I of n elements, the expected time of this algorithm E[T(I)] is O(n log n). Notice that this is better than an average-case bound because we are no longer assuming any special properties of the input. It is a little peculiar: making the algorithm probabilistic gives us more control over the running time.

https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0906.pdf

Никогда раньше не сталкивался с анализом вероятностных алгоритмов, интересное чтение.

И, чтобы уж закрыть (на данный момент) тему сортировок, еще 2 факта:

1) Очень интересный хак, про который я не знал. Обычно, на последних стадиях quicksort, применяют более простой, но квадратичный алгоритм. Например, insertion sort. Потому что:
* он проще, для одного его шага нужно выполнить меньше инструкций, и не нужно поддерживать структуру стека вызовов
* insertion sort работает за O(n) для уже почти отсортированных массивов

Так вот, хак заключается в том, что inertion sort применяется не на отдельные кусочки, а на весь k-sorted(то есть, каждый элемент стоит на расстоянии не больше k от своей реальной позиции после сортировки) массив. Это позволяет компилятору сгенерить более хороший(компактный) код для основного цикла quicksort. А еще позволяет нивелировать некоторые недочеты в реализации основного алгоритма. Например, я в первой реализации partition всегда оставлял первый элемент неотсортированным, потому что для реализации "в лоб" для этого требовался указатель на элемент до начала массива. Последний шаг в виде глобального insertion sort пробулькивал неотсортированные элементы на свое место.

2) По идее, heapsort, в среднем, всегда медленнее, чем quicksort. Потому что он всегда перепахивает весь массив, делая nlogn операций, а quicksort адаптивно стремится ничего не делать для уже отсортированных подмассивов. И heapsort скачет по массиву практически рандомно, без всякой cache locality. quicksort же идет по памяти линейно(либо в одну сторону, как в схеме Ломуто, либо навстречу друг другу, как у Хоара). Но я наблюдаю очень консистентное поведение, что heapsort побеждал на некоторых диапазонах размеров входных данных(и не только, когда данные целиком влезали в кеш). Это интересно, и я пока с этим не разобрался.

Сегодня short story, небольшой, но полезный, хак.

(Наверняка его знает половина аудитории, но я уверен, что другая не знает)

Если у вас есть HashTable<String, V>, то замените ее на HashTable<u64, V>. В качестве ключа используйте хорошую хеш-функцию, типа CityHash64(кстати, пользуясь случаем, заявлю, что, несмотря на то, что всякие farm hash и xxhash хвастаются, что они побеждаю старичка city hash, не ведитесь, все мои измерения говорят, что это не так(ну или покажите мне benchmark, который я смогу сам воспроизвести)). Да, есть вероятность коллизии. И да, для очень большого числа задач этой вероятностью можно пренебречь. При этом, что мы получаем:

1) размер элемента хеш таблицы уменьшается. Это хорошо для cache locality, это хорошо для плоских таблиц.
2) часто элемент становится примитивным типом, и вместо циклов с вызовами конструкторов-деструкторов, случается крупноблочный memcpy, что всегда хорошо
3) для некоторых реализаций хеш-таблиц будет меньше вычислений хеш-функции в сумме(например, если таблица не включает в хранимый элемент хеш от ключа).

#bug12309

Apple делает лучшее оборудование, у нее совершенно гениальные процессоры, отличные юзабилисты, но вот качество самой OS - ну такое. На самом деле, с пользовательской точки зрения вполне ОК(процессы шедулятся нормально, FS на 4-, система не фризится, когда копируешь на флешку, в отличие от(https://web.archive.org/web/20200206024633/https://bugzilla.kernel.org/show_bug.cgi?id=12309)), но вот для программирования не очень. Плохо документированные внутренности, довольно плохие способности контейнеризации(sandboxing - ну такое), почти полностью перекрыты возможности интроспекции(dtruss(аналог strace) неработоспособен от слова вообще).

Поэтому я пристально слежу за проектом https://asahilinux.org/

Интересный цикл заметок про реверс инжиниринг графического процессора Apple M1, от одного из разработчиков Asahi.

Красивое:
https://rosenzweig.io/blog/asahi-gpu-part-1.html
https://rosenzweig.io/blog/asahi-gpu-part-2.html
https://rosenzweig.io/blog/asahi-gpu-part-3.html
https://rosenzweig.io/blog/asahi-gpu-part-4.html

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

Оно было

_Z3fooIiEvN3Std4Meta7Private8EnableIfIXgtstT_Li0EES4_E1RE

, хотя я ожидал увидеть что-то попроще, типа _Z3fooi(+ указание на то, что функция - шаблон от какого-то параметра, я с ходу, из головы, правильное название не напишу). Видно, что в сигнатуру функции попал enable_if одного из ее аргументов. Полез гуглить, нашел ответ на stackoverflow:

https://stackoverflow.com/questions/40157489/in-the-itanium-c-abi-why-does-the-mangled-name-for-template-functions-not-res

long story short - в mangled name в Itanium ABI попадают полные названия dependend types ее аргументов. Не могу для себя решить, это правильно, или нет. Больше похоже на какой-то хак, когда древний компилятор не имел нужного контекста в месте выведения mangled name, и положили то, что было под рукой.

Вообще, мне кажется, делать ABI-compatible изменения С++ кода - нерешаемая задача на практике. Еще одна очень годная статья в тему - https://thephd.dev/binary-banshees-digital-demons-abi-c-c++-help-me-god-please

У меня зреет большой текст про состояние современного С++, и когда он свернул совершенно не в ту сторону.

Пока он зреет, простая задачка для современного языка С++(мы с коллегами пока не придумали, как ее решать).

Есть класс А, который, с точки зрения внешнего наблюдателя, хочет притвориться классом B. Для этого, как минимум, нужно, чтобы объекты класса A умели эффективно притворяться const/mut-&/&& на объекты класса B. При этом, делать это относительно эффективно(operator B() не подходит).

Вот godbolt: https://godbolt.org/z/9fTcna4dK

Помогите девочке Даше не сойти с ума :)

https://habr.com/ru/company/otus/blog/580164/

С точки зрения разбора performance статья совершенно бессмысленная, но вот факт, что format string разбирается через регулярки, это жесть. True story?

Про shell.

1) Недавно мне понадобился бьютифаер для sh файлов(не спрашивайте). Во первых, в интернетах нашлось даже это, во вторых, шелл оно парсит практически только регулярками(https://github.com/lovesegfault/beautysh/blob/master/src/beautysh.py), и делает это хорошо. Лемма о накачке, говорили они...

2) Вчера прилетело прекрасное - jit compiler для shell, с автовекторизацией! https://www.opennet.ru/opennews/art.shtml?num=55877 Мне кажется, в этой новости прекрасно все, и не надо больше ничего писать.

Хозяйке на заметку.

Изучал, как реализуется хвостовая рекурсия. Например, по https://github.com/justinethier/cyclone/raw/master/docs/research-papers/CheneyMTA.pdf

По результатам написал коротенькую портабельную программу, без ассемблерных вставок, которая должна бы выходить по Segmentation Fault, но не выходит:

#include <alloca.h>

#include <util/stream/output.h>

void F(char* sb, unsigned int n) {
    if (n % 1000 == 0) {
        char ch;

        alloca(sb - &ch);
    }

    if (n % 1000000 == 0) {
        Cerr << n << Endl;
    }

    F(sb, n + 1);
}

int main() {
    char ch;

    F(&ch, 0);
}

Где применить, пока не придумал, но выглядит зело хорошо!

Компания Red Hat является главным разрабтчиком gcc. До настоящего времени Red Hat запрещала сборку проектов через clang в Fedora(кроме тех случаев, когда проект просто не собирается gcc). Эти правила совсем недавно поменялись - теперь maintainer проекта может выбирать, каким компилятором будет собираться его проект - https://fedoraproject.org/wiki/Changes/CompilerPolicy. Это незаметное, но очень серьезное изменение.

Я большой фанат clang/llvm(а так же хейтер FSF, GNU, и всего, что они делают), и очень рад наблюдать, что clang начинает теснить gcc и в его традиционном оплоте.

Кстати, интересный еженедельный дайджест про llvm - https://llvmweekly.org/. Clang 13 is coming!

В догонку к предыдущему посту. В мире GNU наблюдается какое-то бурление:

https://sourceware.org/pipermail/libc-alpha/2021-July/129577.html
https://gcc.gnu.org/pipermail/gcc/2021-June/236182.html

Я очень надеюсь, что это не связано с нападками SJW на Столлмана, а связано исключительно с technical merits и политикой FSF.

>Clang 13 is coming!

Тем временем, в стане конкурента: https://twitter.com/ryan_levick/status/1443202538099073027

#cplpl_doomed

В С++ есть фича, которая описана не совсем так, как описаны большинство фич С++(с помощью понятия "наблюдаемое поведение"), а с помощью описания трансформации AST. Речь идет про range-based for loop.

Вот преобразование AST: #abi

{
    auto && __range = range-expression ;
    auto __begin = begin_expr ;
    auto __end = end_expr ;
    for ( ; __begin != __end; ++__begin) {
        range-declaration = *__begin;
        loop-statement
    }
}

Это приводит к очень печальным проблемам, например, вот в таком случае:

for (auto& v : return_temporary().return_reference_to_temporary_subobject())

Коллеги из комитета по стандартизации сегодня рассказали, что С++ комитет отказался чинить эту фичу, потому что нет общего решения для С++, его надо придумать до C++26, но придумать никто не может.

Теперь и в твитторе: https://twitter.com/NicoJosuttis/status/1443267749854208000?s=19

С++ doomed. С этими старперами из IBM/Google/Microsoft, которые заинтересованы лишь в том, как бы ничего не сломать, у руля, C++ скоро превратится в Cobol.

Лично я об этом не жалею, для души буду писать на Rust, зато безбедная старость и образование для детей обеспечено.

Кстати, про M1.

Хороший текст про то, как в цикле заменять деление умножением(компиляторы давно это делают в compile-time, но в runtime, понятное дело, приходится руками). https://ridiculousfish.com/blog/posts/benchmarking-libdivide-m1-avx512.html

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

"The M1 is 10x faster than the Xeon at 64 bit divides. It’s…just wow."

M1 - какое-то совершенно невероятное железо.

PS: текст про то, как заменить остаток от деления на умножение в хеш-таблицах: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

Серия статей про peg parser от Гвидо. https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60

#fast_python

От "смотрите, какую клевую штуку я вчера прочитал в википедии", через "а вы знаете, я вдруг понял, что парсер в Питоне сосет"(а то это не было очевидно и до?), до "я переписал парсер Питона!".

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

1) Потому что есть PyPy
2) Потому что jit сделает интерпретатор нечитаемым
3) Со скоростью и так все норм
4) Потому что нельзя менять API модулей

Чтобы не быть голословным, Гвидо on tail recursion:
http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

jit-компиляторы Питона можно найти в большом количестве, но до mainline CPython не дошло ничего.

И тут, ВНЕЗАПНО, после перехода в Microsoft, Гвидо решает заняться скоростью Питона, и обещает ускорить его в несколько раз. (https://github.com/faster-cpython/ideas, https://thenewstack.io/guido-van-rossums-ambitious-plans-for-improving-python-performance/) Конечно, сколько лет сам этому мешал, там непаханое поле, в несколько раз - это даже не начать приближаться к javascript(https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/python.html)

И ускорит, будьте уверены. И напишет еще 10 клевых постов. А вот то, что это могло сделать 2 - 3 хорошо мотивированных студента, просто возможности не было, никто и не вспомнит.

https://www.opennet.ru/opennews/art.shtml?num=55897 #openssl

Никогда такого не было, и вот опять. Блеск и нищета open source. Вы смотрели на исходники openssl? Я смотрел, больше не хочу.

"Проблемы также затронули библиотеку LibreSSL, разработчики которой не учли прошлый опыт, связанный со сбоями, возникшими после устаревания корневого сертификата AddTrust удостоверяющего центра Sectigo (Comodo)."

"Суть ошибки в том, что старые версии OpenSSL и GnuTLS разбирали сертификат как линейную цепочку, в то время как в соответствии с RFC 4158 сертификат может представлять ориентированный распределённый циклический граф с несколькими якорями доверия, которые нужно учитывать."

PS: а вот все эти удостоверяющие центры действительно несут пользу для web(я не говорю про банковские транзакции)? Насколько сложно получить сертификат у того же Let's Encrypt?

PPS: в современно мире я бы использовал или libtomcrypt(low-level), или mbedtls, или wolfssl(там, кстати, работает разработчик curl, и она сильно совместима с openssl по API)

PPPS: про качество кода openssl от конкурента(автора libtom*): https://www.libtom.net/about/
"For some reason, folk like the GPG and OpenSSL folk assume that completely abhorrent and messy source code is ok, so long as it works."

Long read. #bootstrap

Я думаю, не секрет, что мне очень интересны системы сборки, в самом разнообразном виде. Настолько, что у меня есть:

1) Своя система сборки для С++ кода
* https://github.com/pg83/zm
* https://github.com/pg83/zm/blob/master/tp/libs/python/src/z.make

2) И своя система сборки OSS пакетов. Для Darwin и для Linux, для последнего это не только система пакетов, но и полноценный дистрибутив:
* https://github.com/pg83/mix
* https://github.com/pg83/mix/blob/main/pkgs/dev/lang/python3/package.sh (самый большой сборочный пакет, потому что собрать статически слинкованный Питон - совершенно нетривиальная задача)

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

Сегодня я хочу поговорить про задачу бутстрапа.

Что это такое? Представьте себе, что вы попали на необитаемый остров, у вас есть пустой компьютер(без ОС), и компакт-диск с исходниками программ. Нужно из этого получить рабочую ОС, чтобы на необитаемом острове было не так скучно(стюардесса на необитаемый остров с нами не попала).

Эта задача имеет следующие аспекты:

1) Исторический. Как вообще проходил путь от компьютера с перфокартами до современных рабочих станций и планшетов?
2) Сугубо практический - как развернуть дистрибутив, имея максимально малый возможный бинарный seed. Вот очень интересное исследование, как проложить путь от минимального гипервизора в 200 инструкций до современного дистрибутива Linux - https://github.com/fosslinux/live-bootstrap/blob/master/parts.rst
3) Безопасность. Воспроизводимая сборка с минимальным бинарным seed нужна, чтобы быть уверенным, что в софте нет закладок. Например, небезызвестная атака Томпсона: https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf . Очень смешной вариант - https://www.quora.com/What-is-a-coders-worst-nightmare/answer/Mick-Stute?share=1 Да и просто понимать, что твоя сборка Alacritty собрана из исходников с github, и не содержит в себе трояна или какой другой жести, очень ценно.

Я стараюсь не держать у себя софта, для которого нельзя протянуть вот такую вот цепочку from ground truth.

В интернетах есть несколько community, которых эта задача тоже беспокоит:

1) https://bootstrappable.org/
2) https://guix.gnu.org/ (очень сильно упарываются по bootstrap)
3) https://nixos.org/ (в меньшей степени, не стесняются использовать бинарные сборки Rust, например)

Товарищи из Guix даже разработали пару специализированных языков для первоначального bootstrap(https://www.gnu.org/software/mes/, https://guix.gnu.org/blog/2019/guix-reduces-bootstrap-seed-by-50/) У guix, правда, есть другие свои заморочки, поэтому не могу его рекомендовать для повседневного использования. Nix в этом отношении интереснее, я его использовал как пакетный менеджер для любого Linux, Darwin, пока не завершил задачу bootstrap своего дистрибутива.

Что стоит еще рассказать про тему bootstrap:
* Далеко не все языки можно bootstrap. Это значит, что для некоторых языков нужен большой изначальный blob неизвестного качества. Я такие языки стараюсь не использовать(https://elephly.net/posts/2017-01-09-bootstrapping-haskell-part-1.html).
* Java бутстрапнули совсем недавно(https://bootstrappable.org/projects/jvm-languages.html). Систему сборки для нее(gradle) до сих пор не.
* Rust, с моей точки зрения, с натяжкой bootstrapable. Потому что: #mrustc
1) Для сборки n-ой версии нужна n-1 версия. Это очень сильно увеличивает длину цепочки bootstrap. Порядка 20 сборок на текущий момент?
2) Исходники первых версий на standard ml лежат неизвестно где. Bootstrap возможен только с сиспользованием стороннего продукта(https://github.com/thepowersgang/mrustc)
3) На Apple M1 цепочку пока повторить не получается
* У Go с bootstrap все хорошо, авторы поддерживают версию 1.4, последнюю на С. С ее помощью можно собрать современный Go. Так же существует gccgo.
* У Lisp все тоже очень хорошо. Скажем, цепочку от интерпретируемого ECL до компилируемого SBCL на Apple M1 я протянул за час.