test

Писал quicksort для одной велосипедной библиотеки(про нее как-нибудь в другой раз #std), и мне стало лень писать еще и 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);
}

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