Откуда такая скорость у mold?
#опытным

На графиках с предыдущего поста видно, что mold работает чуть ли не на порядок быстрее, чем ld или gold. За счет чего они так сильно ускорили линковщик?

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

⚡️Самая мякотка - работа в параллель. C единицами трансляции мы интуитивно понимаем как параллелить: каждому вычислительному юниту даем обрабатывать свою TU. С линковкой конечно сложнее, но тоже решаемо. Линкерам на вход подается большое число однотипных данных, которые нужно обработать, и между которыми не так уж и много связей. Поэтому эту гору данных можно разбить на поток задачек, которые независимо можно выполнять на большом количестве потоков.

Однако рано или поздно наступит этап reduce, когда нужно собирать данные воедино. Для этого они используют потокобезопасную мапу, которая хранит отображение названия символа на сам объект символа. В качестве такой мапы mold использует Intel TBB's tbb::concurrent_hash_map. Крутая либа на самом деле, одно из лучших решений для высокопроизводительных потокобезопасных вычислений.

⚡️В качестве аллокатора используют mimaloc. Cтандартный malloc из glibc плохо масштабируется на большом количестве ядер, поэтому они решили попробовать сторонние решения. Среди jemalloc, tbbmalloc, tcmalloc и mimalloc - mimalloc от Microsoft
показал наилучшую производительность.

⚡️Маппинг файлов в адресное пространство процесса. Операции ввода-вывода всегда долгие. Но в mold'е сделали ход конем: Они просто отображают содержимое файла в память программы и могут его читать быстрее.

⚡️Если им и нужно записывать данные в файл, то они используют уже существующие файлы для перезаписи данных в них, нежели чем создают новые файлы. Данные намного быстрее записываются в файл, который уже находится в кэше буфера файловой системы.

Молодцы, ребята. Комплексно подошли к проблеме, работали по всем фронтам и применили интересные технические решения.

Be faster. Stay cool.

#tools

​​Несколько советов по написанию быстрого кода от разрабов mold
#новичкам

Чтобы стать самым быстрым опенсорс-линковщиком, нужно постараться. В результате этих стараний вырабатываются некоторые подходы к написанию производительных приложений, которым разрабочики mold хотели бы с вами поделиться.

✅ Не угадывай, а измеряй

Предположения и отрешенные размышления обычно оказываются неверными, поэтому не тратьте время на оптимизацию кода, который не имеет значения. Оптимизируйте самые важные и узкие части. А чтобы их найти, используйте профилировщики, например perf.

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

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

✅ Реализуй несколько алгоритмов и выбери самый быстрый

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


✅ Напиши одну и ту же программу несколько раз

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

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

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

А какие вы советы дадите по написанию быстрых программ?

Be faster. Stay cool.

#tool #goodpractice

include what you use
#опытным

Еще один способ уменьшить время сборки.

Ваша программа может содержать все хэдэры стандартной библиотеки и прекрасно собираться. В чем проблема? Неиспользуемые шаблоны же не компилируются.

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

Чтобы избежать лишнего анализа, есть такая практика в программировании на С/С++ - include what you use. Включайте в код только те заголовочники, где определены сущности, которые вы используете в коде. Тогда не будет тратится время на анализ ненужного кода.

У этого подхода есть еще одно преимущество. Если мы полагаемся на неявное включение одних хэдэров через другие, то могут возникнуть проблемы при рефакторинге. Вы вроде был убрали только ненужный функционал вместе с объявлениями соответствующих сущностей, а билд сломался с непонятной ошибкой. Потому что вы убрали источник тех неявно подключаемых заголовков и компилятору теперь их недостает. А мы знаем, какие он "шедевры" может выдавать, если ему чего-то не хватает(тот же пример с std::ranges::less)

Как использовать этот подход в проекте?

Я знаю пару способов:

1️⃣ Утилита iwyu. Установив ее и прописав зависимости в симейке, на этапе компиляции вам будут выдаваться варнинги, которые нужно будет постепенно фиксить:

# установка

sudo apt-get install iwyu

# интеграция с cmake

option(ENABLE_IWYU "Enable Include What You Use" OFF)

if(ENABLE_IWYU)
    find_program(IWYU_PATH NAMES include-what-you-use iwyu)
    if(IWYU_PATH)
        message(STATUS "Found IWYU: ${IWYU_PATH}")
        set(CMAKE_CXX_INCLUDE_WHAT_YOU_USE "${IWYU_PATH}")
    else()
        message(WARNING "IWYU not found, disabling")
    endif()
endif()

# запуск

mkdir -p build && cd build
cmake -DENABLE_IWYU=ON ..
make 2> iwyu_initial.out

# Анализ результатов
wc -l iwyu_initial.out  # Общее количество предупреждений
grep -c "should add" iwyu_initial.out  # Пропущенные includes
grep -c "should remove" iwyu_initial.out  # Лишние includes

Там есть еще нюансы с 3rd-party, которые мы вынесем за рамки обсуждения.

2️⃣ clang-tidy. Если у вас настроены проверки clang-tidy, то вам ничего не стоит подключить include what you use. Достаточно к проверкам добавить пункт misc-include-cleaner. В конфиге также можно настроить различные исключения, что мы также выносим за скобки обсуждения.

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

Include what you use. Stay cool.

#tools #goodpractice

​​shared libraries
#опытным

И еще один способ уменьшить время сборки проекта. А точнее линковки.

Идея такая: вы разбиваете свой проект на отдельные, независимые модули и компилируете их как разделяемые библиотеки. Дальше динамически линкуете эти библиотеки к своему исполняемому файлу.

Почему в этом случае линковка быстрее?

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

1️⃣ Разрешение символов - для каждого неопределенного символа ищется определение.

2️⃣ Создание единого адресного пространства - линковщик определяет окончательные адреса для всех сегментов кода и данных и объединяет однотипные секции из разных объектных файлов.

3️⃣ Применение релокаций - в объектных файлах и статических либах адреса указаны относительно и линковщик пересчитывает все адреса в абсолютные значения.

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

Плюс при изменениях в библиотеке, которые не затрагивают API и ABI, можно вообще не перелинковывать исполняемый файл - все изменения подтянутся в рантайме.

Линковка-то на самом деле происходит быстрее, но у разделяемых библиотек есть свои недостатки:

👉🏿 оверхэд на инициализацию программы за счет загрузки библиотек

👉🏿 оверхэд на первый вызов каждой функции. Но последующий вызовы уже не имеют заметного оверхэда за счет записей конкретных адресов в таблицу для каждого символа

👉🏿 более сложный деплой. Нужно вместе с бинарником распространять все разделяемые библиотеки. Если используется какой-нибудь докер, то головная боль относительно минимальна А если нет, то есть риски получить конфликты разных версий библиотеки для разных исполняемых файлов(так как все программы, слинкованные с одной шареной либой, обращаются в одному файлу) и увеличение coupling'а между разными программами, использующими одну либу.

А вы используете компиляцию модулей своих проектов, как разделяемых библиотек?

Share resources. Stay cool.

#tools

​​Как анализировать процесс компиляции?
#опытным

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

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

Здесь будет только gcc и clang, с виндой у нас опыта особо нет. Знающие могут подсказать в комментах. Поехали.

GCC

Есть определенный набор опций компиляции, которые говорят компилятору выводить подробную информацию о внутренних процессах, происходящих при обработке цппшников и хэдэров. Для гцц это:

g++ -fstats  -fstack-usage  -ftime-report  -ftime-report-details -c large_file.cpp -o large_file.o

// или в CMakeLists.txt прописать

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fstats -fstack-usage -ftime-report -ftime-report-details")

при компиляции вам выдастся что-то такое:

******
time in header files (total): 0.259532 (22%)
time in main file (total): 0.884263 (76%)
ratio = 0.293501 : 1

******
time in <path_to_header_1>: 0.000444 (0%)
time in <path_to_header_2>: 0.008682 (1%)
time in <path_to_header_3>: 0.885595 (76%)
/.../

Time variable                                  wall           GGC
 phase setup                        :   0.05 (  4%)  1813k (  3%)
 phase parsing                      :   1.11 ( 94%)    55M ( 97%)
 phase lang. deferred               :   0.01 (  1%)   128k (  0%)
// other metrics
 TOTAL                              :   1.18           57M

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

И такая портянка генерируется для каждого цппшника. Будьте осторожнее при сборке, используйте make в один поток, иначе не поймете, что куда относится.

Clang

Чтобы получить подобный репорт для шланга нужна опция:

clang++ -ftime-trace -c large_file.cpp -o large_file.o

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -ftime-trace")

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

// обязательно собрать проект с опцией -ftime-trace

ClangBuildAnalyzer --all build/ build_analysis.json
ClangBuildAnalyzer --analyze build_analysis.json

Вывод будет примерно такой:

**** Files that took longest to codegen (compiler backend):
 // files list

**** Templates that took longest to instantiate:
// templates list

**** Functions that took longest to compile:
// functions list

etc...

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

В любом случае, измерение - залог качественного результата.

Look before you leap. Stay cool.

#tools

Идиома IILE
#опытным

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

const int myParam = inputParam * 10 + 5;
// or
const int myParam = bCondition ? inputParam * 2 : inputParam + 10;

Но что делать, если переменная по сути своей константа, но у нее громоздская инициализация на несколько строк?

int myVariable = 0; // this should be const...

if (bFirstCondition)
    myVariable = bSecondCindition ? computeFunc(inputParam) : 0;
else
    myVariable = inputParam * 2;

// more code of the current function...
// and we assume 'myVariable` is const now

По-хорошему это уносится в какую-нибудь отдельную функцию. Но тогда теряется контекст и нужно будет прыгать по коду.

Хочется и const сделать, и в отдельную функцию не выносить. Кажется, что на двух стульях не усидишь, но благодаря лямбдам мы можем это сделать!

Есть такая идиома IILE(Immediately Invoked Lambda Expression). Вы определяете лямбду и тут же ее вызываете. И контекст сохраняется, и единовременность инициализации присутствует:

const int myVariable = [&] {
    if (bFirstContidion)
        return bSecondCondition ? computeFunc(inputParam) : 0;
    else
       return inputParam * 2;
}(); // call!

Пара лишних символов, зато проблема решена.

Тут есть одно "но". Вроде все хорошо, но немного напрягает, что все это можно спутать с простым определением лямбды, если не увидеть скобки вызова в конце.

Тоже не беда! Используем std::invoke:

const int myVariable = std::invoke([&] {
    if (bFirstContidion)
        return bSecondCondition ? computeFunc(inputParam) : 0;
    else
       return inputParam * 2;
});

Теперь мы четко и ясно видим, что лямбда вызывается. В таком виде прям кайф.

Эту же технику можно использовать например в списке инициализации конструктора, например, если нужно константное поле определить(его нельзя определять в теле конструктора).

Be expressive. Stay cool.

#cpp11 #cpp17 #goodpractice

Квиз
#новичкам

Сегодня короткий, но от того не менее интересный #quiz, . Можно было бы разобрать вопрос: "а что случится, если я мувну константную ссылку?", но так не очень интересно. Поэтому давайте проверим ваше знание мув-семантики.

У меня к вам всего один вопрос: Какой результат попытки компиляции и запуска следующего кода:

#include <iostream>

struct Test {
    Test() = default;
    Test(const Test &other) {
        std::cout << "copy ctor " << std::endl;
    }
    Test(Test &&other) {
        std::cout << "move ctor " << std::endl;
    }
    Test &operator=(const Test &other) = default;
    Test &operator=(Test &&other) = default;
    ~Test() = default;
};

int main() {
    Test test;
    const Test &ref = test;
    (void)std::move(ref);
    auto enigma = std::move(ref);
}

Challenge yourself. Stay cool.

​​Ответ
#новичкам

Многие из вас подумали, что будет ошибка компиляции. В целом, логичная цепочка мыслей: ну как же можно мувнуть данные из константной ссылки? Она же неизменяема.

Но она все же неверная. Правильный ответ: на консоль выведется "copy ctor".

Копия? Мы же муваем!

Сейчас разберемся. Но для начало вспомним сам пример:

#include <iostream>

struct Test {
    Test() = default;
    Test(const Test &other) {
        std::cout << "copy ctor" << std::endl;
    }
    Test(Test &&other) {
        std::cout << "move ctor" << std::endl;
    }
    Test &operator=(const Test &other) = default;
    Test &operator=(Test &&other) = default;
    ~Test() = default;
};

int main() {
    Test test;
    const Test &ref = test;
    (void)std::move(ref);
    auto emigma = std::move(ref);
}

На самом деле проблема в нейминге. Все вопросы к комитету. Это они имена всему плюсовому раздают.

std::move ничего не мувает. Она делает всего лишь static_cast. Но не просто каст к правой ссылке, это не совсем корректно. Посмотрим на реализацию std::move:

template <class T>  
constexpr typename std::remove_reference<T>::type&& move(T&& t) noexcept {  
  return static_cast<typename std::remove_reference<T>::type&&>(t);  
}

Обратите внимание, что от типа отрезается любая ссылочность и только затем добавляется правоссылочность. Но константность-то никуда не уходит. По сути результирующий тип выражения std::move({константная левая ссылка}) это константная правая ссылка.

Чтобы это проверить, перейдем на cppinsights:

Test test;
const Test &ref = test;
using ExprType = decltype(std::move(ref));

// под капотом ExprType вот чему равен

using ExprType = const Test &&;

Так как мы просто кастуем к валидному типу, мув успешно отрабатывает, но строчка (void)std::move(ref); не дает в консоли никакого вывода, потому что никаких новых объектов мы не создаем.

Теперь про копирование. Вспомним правила приведения типов. const T&& может приводится только к const T&. То есть единственный конструктор, который может вызваться - это копирующий конструктор.

Интересная ситуация, конечно, что "перемещение" может приводить к копированию в плюсах. Но имеем, что имеем. Терпим и продолжаем грызть гранит С++.

Give a proper name. Stay cool.

#cppcore #template

​​Гарантии безопасности исключений
#новичкам

Программа на С++ - очень интересное явление. Вроде мощный, подкаченный, умный и скоростной парень. Но вот проблема. Ходить не умеет нормально. То в ноги себе стреляет, то падает периодически. В общем, беда у него с ходьбой. У этого могут быть разные причины. Все из них даже трудно в голове удержать. Но сегодня обсудим, какие есть гипсы, лангеты и костыли, которые помогут этому парню нормально ходить при работе с исключениями.

Даже не зная, что вы работаете с исключениями - вы уже работаете с ними. Даже обычный, казалось бы, безобидный new может кинуть std::bad_alloc. И это core языка. Стандартная библиотека пронизана исключениями.

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

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

Итак, существует 3 гарантии безопасности исключений:

Базовая гарантия. Формулировка разнится, но более общая звучит так: "после возникновения исключения и его обработки программа должна остаться в согласованном состоянии". Теперь на рабоче-крестьянском: не должно быть утечек ресурсов и должны сохраняться все инварианты классов. С утечками, думаю, все понятно. Инвариант - некое логически согласованное состояние системы. Если класс владеет массивом и содержит поле для его размера, то инвариантом этого класса будет совпадение реального размера массива со значением поля-размера. Для класса "легковая машина" инвариантом будет количество колес - 4. Обычная машина без одного или нескольких колес просто не едет. И для того, чтобы машина корректно работала, количество колес должно быть одинаково - 4. Или например, нельзя, чтобы дата создания чего-то была больше текущего дня, ну никак. Вот такие штуки должны сохраняться.

Строгая гарантия. Если при выполнении операции возникает исключение, операция не должна оказать на систему никакого влияния. То есть пан или пропал. Либо вся операция выполняется успешно и ее результат применяется, либо система откатывается в состояние до выполнения операции. Это свойство программы называется транзакционностью.

Гарантия отсутствия исключений. Ни при каких обстоятельствах не будет брошено исключение. Легко сказать, но тяжело сделать. С++ и его стандартная библиотека разрабатывались с учетом использования исключений. И это накладывает свои ограничения на отсутствие исключений. Мы все-таки не на Go пишем.

Ну и есть еще одна гарантия - отсутствие каких-либо гарантий. Мама - анархия, во всей красе.

Тема важная, будем потихоньку ее разбирать с примерами по каждой гарантии.

Be a guarantor. Stay cool.

#cppcore

​​Базовая гарантия исключений
#новичкам

Вспомним свойства базовой гарантии: после возникновения исключения в программе не должно быть утечек ресурсов и должны сохраняться все инварианты классов.

И не всегда базовой гарантии легко удовлетворить. Поскольку исключения добавляют в программу дополнительные пути выполнения кода, крайне важно учитывать последствия работы кода по таким путям и избегать любых нежелательных эффектов, которые в противном случае могут возникнуть. Давайте посмотрим на примере:

class IntArray {
    int *array;
    std::size_t nElems;

public:
    // ...

    ~IntArray() { delete[] array; }

    IntArray(const IntArray &that);  // nontrivial copy constructor
    IntArray &operator=(const IntArray &rhs) {
        if (this != &rhs) {
            delete[] array;
            array = nullptr;
            nElems = rhs.nElems;
            if (nElems) {
                array = new int[nElems];
                std::memcpy(array, rhs.array, nElems * sizeof(*array));
            }
        }
        return *this;
    }

    // ...
};

Внутренний инвариант класса IntArray - член array является валидным (возможно, нулевым) указателем, а член nElems хранит количество элементов в массиве. В операторе присваивания освобождается память текущего array'я и присваивается значение счётчику элементов nElems до выделения нового блока памяти для копии. В результате, если из new вылетит исключение, то array будет нулевым, а размер массива нет. Это нарушение инварианта и таким объектом просто небезопасно пользоваться. Метод size потенциально вернет ненулевой размер, а закономерное использование следом оператора[] приведет к неопределенному поведению.

Код, который избегает подобных нежелательных эффектов, называется exception safe. То есть предоставление базовой гарантии уже говорит о том, что ваш код "exception safe".

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

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

И это главное. Вся магия с раскруткой стека и вызовом деструктором локальных объектов работает только если деструкторы вызываются безопасно. А для этого объект должен быть в валидном, но необязательно определенном, состоянии. То есть вы в принципе не можете восстановить работоспособность приложения, если ваши инструменты не предоставляют хотя бы базовую гарантию.

Здесь кстати можно провести параллель с мувнутыми объектами: ими тоже особо не попользуешься и по хорошему их надо просто удалить.

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

auto db = std::make_shared<DBConnection>(credentials);
try {
  auto result = db->Execute("UPDATE ...");
  process(result);
} catch (std::exception& ex) {
  std::cout << "We can cannot rely on table state and must retry with that in mind" << std::endl;
  // retry
}

Поэтому мы должны иметь ввиду это неопределенное состояние коннекшена и базы при выполнении ретраев.

Provide guarantees. Stay cool.

#cppcore

​​Строгая гарантия исключений
#новичкам

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

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

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

Давайте перепишем оператор присваивания класс IntArray из предыдущего поста так, чтобы он предоставлял строгую гарантию:

class IntArray {
    int *array;
    std::size_t nElems;

public:
    // ...

    ~IntArray() { delete[] array; }

    IntArray(const IntArray &that);  // nontrivial copy constructor

    IntArray &operator=(const IntArray &rhs) {
        int *tmp = nullptr;
        if (rhs.nElems) {
            tmp = new int[rhs.nElems];
            std::memcpy(tmp, rhs.array, rhs.nElems * sizeof(*array));
        }
        delete[] array;
        array = tmp;
        nElems = rhs.nElems;
        return *this;
    }

    // ...
};

В этот раз мы ничего не изменяем в самом объекте до тех пор, пока не выделим новый буфер и не скопируем туда элементы rhs. И только после этого выполняем обновление самого объекта с помощью небросающих инструкций.

Хрестоматийный пример из стандартной библиотеки - вектор с его методом push_back. Если у типа есть небросающий перемещающий конструктор, то метод предоставляет строгую гарантию. Вот примерно как это работает:

template <typename T>
class vector {
private:
    T *data = nullptr;
    size_t size = 0;
    size_t capacity = 0;

    void reallocate(size_t new_capacity) {
        // allocate memory
        T *new_data =
            static_cast<T *>(::operator new(new_capacity * sizeof(T)));
        size_t new_size = 0;

        try {
            // Move or copy elements 
            for (size_t i = 0; i < size; ++i) {
                new (new_data + new_size) T(std::move_if_noexcept(data[i]));
                ++new_size;
            }
        } catch (...) {
            // Rollback in case of exception
            for (size_t i = 0; i < new_size; ++i) {
                new_data[i].~T();
            }
            ::operator delete(new_data);
            throw;
        }

        // cleanup
        // ...
    }

public:
    void push_back(const T &value) {
        if (size >= capacity) {
            size_t new_capacity = capacity == 0 ? 1 : capacity * 2;

            // save for rollback
            T *old_data = data;
            size_t old_size = size;
            size_t old_capacity = capacity;

            try {
                reallocate(new_capacity);
            } catch (...) {
                // restore
                data = old_data;
                size = old_size;
                capacity = old_capacity;
                throw;
            }
        }

        // actually insert element
        // ...
    }

};

в хэлпере reallocate используется std::move_if_noexcept, который условно кастит в rvalue ссылке, если мув конструктор noexcept. И только в этом случае можно предоставить строгую гарантию: если вы уже повредили один из исходных объектов, его уже никак не восстановить. А безопасное перемещение элементов гарантирует готовый к использованию новый расширенный буфер.

Be strong. Stay cool.

#cppcore

​​Гарантия отсутствия исключений
#новичкам

Переходим к самой сильной гарантии - отсутствие исключений.

В сам язык С++(new, dynamic_cast), и в его стандартную библиотеку в базе встроены исключения. Поэтому писать код без исключений в использованием стандартных инструментов практически невозможно. Вы конечно можете использовать nothrow new и написать свой вариант стандартной библиотеки и других сторонних решений. И кто-то наверняка так делал. Но в этом случае разработка как минимум затянется, а как максимум вы бросите это гиблое дело.

Поэтому повсеместно предоставлять nothow гарантии с использованием стандартных инструментов не всегда реалистично.

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

Но для начала проясним термины.

Под гарантией отсутствия исключений подразумевается обычно 2 понятия: nothrow и nofail.

nothrow подразумевает отсутствие исключений, но не отсутствие ошибок. Говорится, что ошибки репортятся другими средствами(в основном через глобальное состояние, потому что деструктор ничего не возвращает) или полностью скрываются и игнорируются.

Примером сущностей с nothrow гарантией является деструкторы. С С++11 они по-умолчанию помечены noexcept. В основном это сделано для того, чтобы при раскрутке стека не получить double exception.
Но деструкторы могу фейлиться. Просто никаких средств, кроме глобальных переменных для репорта ошибок невозможно использовать. Они ведь ничего не возвращают, а исполняются скрытно от нас(если вы используете RAII конечно).

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

Например в swap-идиоме std::swap и мув-конструкторы используются для определения небросающего оператора присваивания.

nofail гарантиями также должны обладать функторы-коллбэки модифицирующих алгоритмов. std::sort не предоставляет никаких гарантий на состояние системы, если компаратор бросит эксепшн.

В языке в целом эти гарантии обеспечиваются ключевым словом noexcept. При появлении этой нотации компилятор понимает, что для этой функций не нужно генерировать дополнительный код, необходимый для обработки исключений. Но у этого есть своя цена: если из noexcept функции вылетит исключение, то сразу же без разговоров вызовется std::terminate.

Provide guarantees. Stay cool.

#cppcore #cpp11

​​WAT
#опытным

Спасибо, @Ivaneo, за любезно предоставленный примерчик в рамках рубрики #ЧЗХ.

"Век живи - век учись" - сказал Луций Сенека.

"Век живи - век учи С++" - реалии нашей жизни.

Просто посмотрите на следующий код:

struct Foo
{
  void Bar();
};

void Foo::Foo::Foo::Foo::Foo::Foo::Foo::Foo::Foo::Foo::Foo::Foo::Bar()
{
    printf("Foofoo!");
}

int main()
{
    Foo f;
    f.Bar();
    return 0;
}

И он компилируется.

WAT?

Это называется injected class name. Имя класса доступно из скоупа этого же класса. Так сделано для того, чтобы поиск имени X внутри класса X всегда разрешался именно в этот класс.

Такое поведение может быть полезно в таком сценарии:

void X() { }
class X {
public:
  static X Сreate() { return X(); }
};

injected class name гарантирует, что из метода Сreate будет возвращен именно инстанс класса Х, а не результат вызова функции Х.

Это также полезно внутри шаблонов классов, где имя класса можно использовать без списка аргументов шаблона, например, используя просто Foo вместо полного идентификатора шаблона Foo<blah, blah, blah>.

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

Так что это не у вас в глазах двоится, это плюсы такие шебутные)

Find yourself within. Stay cool.

#cppcore

​​data race
#новичкам

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

Начнем с data race. Это по сути единственная категория, которая четко определена в стандарте С++.

Скажем, что два обращения к памяти конфликтуют, если:

- они обращаются к одной и той же ячейке памяти.
- по крайней мере одно из обращений - запись.

Так вот гонкой данных называется 2 конфликтующих обращения к неатомарной переменной, между которыми не возникло отношение порядка "Произошло-Раньше".

Если не вдаваться в семантику отношений порядков, то отсутствие синхронизации с помощью примитивов(мьютексов и атомиков) при доступе к неатомикам карается гонкой данных и неопределененным поведением.

Простой пример:

int a = 0;

void thread_1() {
  for (int i = 0; i < 10000; ++i) {
    ++a;
  }
}

void thread_2() {
  for (int i = 0; i < 10000; ++i) {
    ++a;
  }
}

std::jthread thr1{thread_1};
std::jthread thr1{thread_2};
std::cout << a << std::endl;

В двух потоках пытаемся инкрементировать a. Проблема в том, что при выводе на консоль a не будет равна 20000, а скорее всего чуть меньшему числу. Инкремент инта - это неатомарная операция над неатомиком, поэтому 2 потока за счет отсутствия синхронизации кэшей будут читать и записывать неактуальные данные.

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

Have an order. Stay cool.

#cppcore #concurrency

race condition
#новичкам

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

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

Но нам и не важно это предсказание, потому что имеет значение поведение всей программы целиком.

Проблемы возникают, когда такие спорадические эффекты приводят к некорректным результатам. И именно эти ситуации обычно называют состоянием гонки. Мне кажется важным проговорить, что потоки всегда в состоянии гонки за чем-то и в этом отражение недетерминированности многопоточной среды. Но далее буду употреблять "состояние гонки" в негативном контексте.

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

Например:

std::atomic<int> x = 2;

void thread_1() {
  x = 3;
}

void thread_2() {
  if (x % 2 == 0) {
    std::cout << x << std::endl;
  }
}

Может так произойти, что поток 1 выполнится в промежутке между условием и выводом x на консоль. Это очень маловероятная ситуация, однако на консоль может вывестись нечетное число 3 с учетом того, что перед выводом мы проверили на четность. Как минимум удивительный результат, хотя с программе нет гонки данных.

Состояние гонки - это в основном ошибка проектирования в условиях многопоточности. Знаменитая проблема наличия метода size() у многопоточной очереди - состояние гонки:

template <typename T>
class ThreadSafeQueue {
...
  size_t size() {
    std::lock_guard lg{mtx_};
    return queue_.size();
  }
private:
  std::deque<T> queue_;
  ...
};


ThreadSafeQueue<int> queue;
...
if (queue.size() > 0) {
  auto item = std::move(queue.front());
  queue.pop();
  // process item
}

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

Основные черты состояния гонки:

🙈 Наличие логической ошибки при проектировании системы

🙈 Зависимость от планирования потоков

🙈 Зависимость от времени выполнения операции. Вчера в чате скинули мем, иллюстрирующий эту зависимость.

Многие путают или не понимают разницы между race condition и data race. Это даже частый вопрос на собеседованиях, на который 50% кандидатов отвечают что-то вообще невнятное. Но теперь вы подготовлены и вооружены правильным словарным аппаратом.

Be independent of other's schedule. Stay cool.

#design #concurrency #interview

​​Deadlock
#новичкам

Еще одна частая проблема из мира многопоточки. На канале уже много материалов про нее есть:

Определение и демонстрация

Начало серии статей про блокировку нескольких мьютексов, что часто приводит к дедлоку

Сколько нужно мьютексов, чтобы задедлокать 2 потока?

Что будет, если 2 раза подряд залочить мьютекс?

Но это все для чуть более опытных ребят. Что если вы совсем не понимаете эти потоки и мьютексы на практике, но очень хотите понять, что такое дедлок?

Есть знаменитая проблема обедающих философов. Формулируется она так:

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

Каждый философ может либо есть, либо размышлять. Приём пищи не ограничен количеством оставшихся спагетти — подразумевается бесконечный запас. Тем не менее, философ может есть только тогда, когда держит две вилки — взятую справа и слева.

Каждый философ может взять ближайшую вилку (если она доступна) или положить — если он уже держит её. Взятие каждой вилки и возвращение её на стол являются раздельными действиями, которые должны выполняться одно за другим.

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

В рамках этой проблемы можно продемонстрировать много проблем многопоточки, но сегодня о deadlock.

Представьте 5 философов по кругу. И у них стратегия - брать всегда первой левую вилку, а затем правую.

Что получится, если все философы одновременно возьмут левую вилку?

Никто из них никогда не поест. Для еды нужны обе вилки, а у всех по одной, все ждут освобождения правой вилки и никто никому не будет уступать. В конце концов они все дружно и помрут.

Это классический deadlock и наглядная его демонстрация. Вот так просто.

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

Как будто бы про дедлоки больше и не о чем писать. Если хотите разобрать какой-то их аспект - черканите в комментах.

Be unblockable. Stay cool.

#concurrency

Лайвлок
#новичкам

Лайвлок(livelock) — это ситуация в многопоточном программировании, когда потоки не блокируются полностью, как при дедлоке, а продолжают выполняться, но не могут продвинуться в решении задачи из-за постоянной реакции на действия друг друга.

Потоки находятся в состоянии "живой блокировки" — они активны, cpu жжется, но их работа не приводит ни к какому прогрессу.

Лайвлоки не всегда приводят к вечной блокировке потоков. Просто в какие-то рандомные моменты времени условный rps может неконтролируемо вырасти в разы, а то и на порядки.

И так как ситуация сильно зависит от планирования потоков, то воспроизвести ее будет сложно.

Однако у этой проблемы есть характерные черты, облегчающие ее поиск:

🔍 Активное ожидание — потоки постоянно проверяют какие-то условия и крутятся в циклах.
🔍 Взаимозависимость — действия одного потока влияют на условия выполнения другого.
🔍 Неблокирующие алгоритмы - активное ожидание обычно идет за ручку с lockfree алгоритмами.
🔍 Поддавки - при потенциальном конфликте интересов стороны предпочитают уступать.

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

К лайвлоку может привести и использование стандартных инструментов. Например, std::scoped_lock, который предназначен для безопасной блокировки нескольких мьютексов. Стандарт требует, чтобы его реализация не приводила к дедлоку. Они используют неопределенную последовательность вызовов методов lock(), try_lock() и unlock(), которая гарантирует отсутствие дедлока. Но не гарантирует отсутствия лайвлока. Алгоритм там примерно такой: попробуй заблокировать столько мьютексов, сколько можешь, а если не получилось, то освободи их и попробуй сначала. Тут есть и циклы, и активное ожидание, и взаимозависимость, и поддавки.

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

Вот более "надежный" пример:

std::atomic<bool> lock1 = false;
std::atomic<bool> lock2 = false;

void thread1_work() {
    while (true) {
        // lock lock1
        while (lock1.exchange(true))
            ;
        std::cout << "Thread 1 has acquired lock1, try to acquire lock2..."
                  << std::endl;
        // try to lock lock2
        if (!lock2.exchange(true)) {
            std::cout << "Thread 1 has acquired both locks!" << std::endl;
            lock2 = false;
            lock1 = false;
            break;
        } else {
            // Failed, release lock1 and try again
            std::cout << "Thread 1 failed to acquire lock2, release lock1..."
                      << std::endl;
            lock1 = false;
        }
    }
}

void thread2_work() {
    while (true) {
        // lock lock2
        while (lock2.exchange(true))
            ;
        std::cout << "Thread 2 has acquired lock2, try to acquire lock1..."
                  << std::endl;
        // try to lock lock1
        if (!lock1.exchange(true)) {
            std::cout << "Thread 2 has acquired both locks!" << std::endl;
            lock1 = false;
            lock2 = false;
            break;
        } else {
            // Failed, release lock2 and try again
            std::cout << "Thread 2 failed to acquire lock1, release lock2..."
                      << std::endl;
            lock2 = false;
        }
    }
}

int main() {
    std::jthread t1(thread1_work);
    std::jthread t2(thread2_work);
}

По сути это костыльная и наивная демонстрация принципа работы std::lock с помощью атомарных замков. Каждый поток пытается в своем порядке захватить замки и отпускает захваченный, если не получилось, и идет на следующую попытку. Можете позапускать этот код у себя и посмотреть, как много попыток захвата потоки будут делать от запуска к запуску.

Unlock your life. Stay cool.

#concurrency

Contention
#опытным

Thread Contention (соревнование потоков) — это ситуация в многопоточном программировании, когда несколько потоков одновременно пытаются получить доступ к одному и тому же разделяемому ресурсу, но только один поток может использовать его в данный момент времени.

Это нормальная ситуация, на любом мьютексе потоки соревнуются. Но иногда это выходит за грани нормальности.

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

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

template <Key, Value>
class ThreadSafeMap {
    mutable std::mutex mtx;
    std::map<Key, Value> map;

public:
    void Insert(const Key &key, const Value &value) {
        std::lock_guard lg{mtx};
        map.insert(key, value);
    }
    Value &Get(const Key &key) const {
        std::lock_guard lg{mtx};
        return map.at(key);
    }
};

Если к такой мапе одновременно будет получать доступ куча потоков, то все кроме одного будут простаивать. А если таких потоков 10 или 20? Неприятненько.

Как можно снизить Contention?

👉🏿 Read-Write Lock. Если у вас много читателе и мало писателей, то можно разрешить нескольким читателям одновременно получать доступ к данным с помощью std::shared_mutex:

template <Key, Value>
class ThreadSafeMap {
    mutable std::shared_mutex mtx;
    std::map<Key, Value> map;

public:
    void Insert(const Key &key, const Value &value) {
        std::unique_lock ul{mtx};
        map.insert(key, value);
    }
    Value &Get(const Key &key) const {
        std::shared_lock sl{mtx};
        return map.at(key);
    }
};

👉🏿 Thread-Local Storage. Потоки пишут данные в свои локальные буферы, которые централизованно синхронизируют данные друг с другом, чтобы как можно меньше блокировать потоки.

👉🏿 Можно организовать свою структуру данных так, чтобы у нее была ячеистая структура и к каждой ячейке был отдельный замок. Теперь потребители данных распределятся по разным ячейкам и не будут толкаться.

template <Key, Value>
class FineGrainedMap {
    struct Node {
        std::mutex mtx;
        std::map<Key, Value> data;
    };
    std::vector<Node> buckets{16};  // Много мелких блокировок
    
public:
    Value& Get(const Key& key) const {
        auto& bucket = buckets[std::hash<Key>{}(key) % buckets.size()];
        std::lock_guard lock(bucket.mtx);
        return bucket.data.at(key);
    }
};

👉🏿 Используйте lock-free структуры данных. Ну как бы тут логично: нет мьютексов, нет и сontention. Не в каждой задаче это реально применить, но иногда все же можно.

Compete and win. Stay cool.

#concurrency

​​Гайзенбаг
#новичкам

Человечеству свойственно все категоризировать и обзывать особенными именами. И конкретные виды багов не исключение.

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

И Гайзенбаг примерно из той же серии.

Создатель впервые употребил этот термин в значении «ты смотришь на него — и он исчезает». Видимо он находил параллели с принципом неопределенности Гейзенберга, который говорит о том, что мы не можем одинаково хорошо измерить две любые характеристики частицы(например скорость и положение). Простыми словами: «чем более пристально вы глядите на один предмет, тем меньше внимания вы уделяете чему-то ещё».
Корректность параллелей вызывает большие сомнения.

Но это все лирика.

Что такой гейзенбаг?

На проде или в CI обнаружили багу. А она, собака, исчезает, как только мы пытаемся ее задетектировать, чтобы исправить.

Гайзенбаги возникают потому, что обычные попытки отладки программы, такие как добавление операторов вывода или запуск под отладчиком, обычно имеют побочный эффект — они изменяют поведение программы незаметными способами.

Например.

Один из распространенных примеров гейзенбага — ошибка, которая проявляется при компиляции программы с оптимизацией, но не проявляется при компиляции той же программы без оптимизации (что часто делается для исследования под отладчиком). При отладке значения, которые оптимизированная программа обычно хранит в регистрах, часто выталкиваются в основную память, что может изменить поведение программы. Да и даже просто компилятор может выкинуть кусок кода под оптимизациями, а под дебажной сборкой - оставить его.

Последнее может произойти не только с дебажной сборкой. Например, бесконечный цикл без сайдэффектов - это UB в С++, поэтому компилятор может его выкинуть. А если вы туда вставите принт, то сайдэффект появится и код попадет в бинарь.

Попытка отследить состояние программы может повлиять на тайминги исполнения, что может привести к видимому сокрытию состояния гонки и соответственно пропаже баги. И конкурентный код часто просто пронизан такими багами. В более привычном словаре их называют плавающими ошибками или спорадиками. В общем случае, это результат race condition, а конкретную причину можно находить долго и больно.

Люди часто винят в появление Гейзенбагов фазы Луны и космические лучи. Это конечно шутки, но подобное нельзя исключать.

Все же лучше качественно тестировать свое ПО, тогда тараканов в коде станет намного меньше.

Don't disappear. Stay cool

#fun

​​Еще несколько именных багов

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

🤓Борбаг(Bohrbug) — ошибка, которая, в противоположность гейзенбагу, не исчезает и не меняет своих свойств при попытке её обнаружения, аналогично стабильности модели электронных орбиталей Нильса Бора. Всегда воспроизводится при определенных условиях. Образцово-показательный баг. Не требует сил на воспроизведение.

🫠Мандельбаг(Mandelbug) — баг, названный в честь "отца" фрактальной математики Мендельброта. Типа эти баги очень сложные, непредсказуемые, вызваны нюансами взамодействия множества компонент программ и часто зависят от начальных условий. И этими характеристиками они похожи на фракталы. Есть конечно вопросики к неймингу, ну да ладно.
Такие баги имеют интересное свойство: их можно копать очень долго и в какой-то момент понимаешь, что проще переписать всю систему.

🤡Шрединбаг(Schrödinbug) — баг, существующий в суперпозиции. Код стабильно работает ровно до момента, когда вы читаете его и понимаете, что он не должен работать. После этого код начинает падать именно в этом месте. Сам факт осознания убивает функциональность. Наблюдатель заставляет волновую функцию коллапсировать в баг.

🤯Гинденбаг (Hindenbug) — катастрофический отказ. Не просто ломает функциональность, а делает это с огнем и спецэффектами. Назван в честь печально известного дирижабля "Гиндербург".
В современном мире докеров и кубернетисов Гинденбаги практически невозможны, потому что все приложения изолированы от исполняющей машины.

🧐Багсон Хиггса(Higgs-bugson) — теоретически предсказанный баг. Его существование доказано логами и пользовательскими reports, но воспроизвести в контролируемых условиях невозможно. Все знают, что он есть, но никто его не видел.
К этим багам можно отнести например UB, которое только в теории UB, а в реальности на конкретной архитектуре все нормально работает.

Give a proper name. Stay cool.

#fun