#creepy

Alternative operator representations (диграфы)

Когда-то давным-давно на свете существовали странные кодировки, в которых не существовало базовых символов.

Например, кодировка для немецкого языка DIN 66003, бывшая в использовании с 1974 по 1999 годы. Она была создана прямой заменой символов [\]{|}~ на ÄÖÜäöüß, которых нет в ASCII. Получилось очень круто - никому не нужные скобочки заменили на буквы алфавита.

Чтобы юзеры кодировки смогли программировать на C++, была реализована гениальная схема - в языке вместо {, }, [, ], # можно писать соответственно <%, %>, <:, :>, %:, %:%:.

Вместе с заменой && на and, != на not_eq, etc. получился код, который можно скомпилировать и сейчас:

int main(int argc, char* argv<::>) 
<%
    // lambda with reference-capture:
    auto greet = <:bitand:>(const char* name)
    <%
        std::cout << "Hello " << name
                  << " from " << argv<:0:> << '\n';
    %>;
 
    if (argc > 1 and argv<:1:> not_eq nullptr) <%
        greet(argv<:1:>);
    %> else <%
        greet("Anon");
    %>
%>

Также для прикола были сделаны триграфы - можно вместо { писать ??<, вместо [ писать ??(, и так далее.

#compiler

Как в компиляторе реализуют NRVO?
(и почему он не всегда работает)

Для подробной информации о явлении можно прочитать на cppreference.

NRVO (Named Return Value Optimization) - это оптимизация из класса copy elision. Copy elision это отсутствие вызова конструкторов копирования/мува за счёт того, что объект изначально создается в целевом месте.

Оптимизация RVO (Return Value Optimization) выглядит чуть проще:

std::string foo1() {
    return std::string("bar");
}
std::string f = foo1();

Компилятор может понять, что никакой нужды в вызове copy/move нет - надо заранее выделить место на стеке под std::string f и создать строку туда.

Даже если copy/move ctors имеют побочные эффекты, их все равно не вызовут. Эти конструкторы можно объявить = delete, или объявить без определения, или сделать private - это ни на что не повлияет.

Эта оптимизация старая, все компиляторы ее делают, а с C++17 она стала обязательной при определенных условиях.

Оптимизация NRVO сложнее, но она не обязательная (в отличие от RVO) - компилятор может сгенерировать суб-оптимальный код.
Условие здесь похожее - если у нас все return xxx; внутри метода возвращают один и тот же xxx;, то в таком случае тоже не происходит copy/move:

std::string foo2() {
    std::string y = "I'm a redundant string";
    std::string x = "sample text";
    if (x.size() % 2 == 0) {
        return x;
    }
    x += "xxx";
    return x;
}
std::string f = foo2(); // без копирования

Как мы видим, все return возвращают одно и то же, поэтому NRVO сработает. Если бы у нас где-нибудь был return y; или return std::move(x);, то NRVO бы не сработал.

Как вычисление NRVO происходит в компиляторе Clang?

Во время парсинга файла Clang держит стек scope (думаю +- понятно для чего нужны скоупы). Одни scope вложены в другие scope, и образуют дерево из scope.
Свой scope создается для каждого метода, каждого класса, каждого if-выражения, каждого for-loop, и так далее. Самый "высокоуровневый" scope это scope Translation Unit-а.

#compiler

Как в компиляторе реализуют NRVO? (продолжение)

Во время парсинга у каждого scope функций и их потомков есть три возможных состояния насчет nrvo:
(1) нет переменной-кандидата на nrvo
(2) есть 1 переменная-кандидат на nrvo (хранится ссылка на нее)
(3) кандидатов на nrvo больше 1 -> nrvo запрещен

Когда scope полностью распарсен, он уведомляет scope-родителя о своем nrvo-состоянии. Если после парсинга scope функции оказалось, что nrvo-кандидат ровно один, то оптимизация сработает. Если кандидатов несколько, то nrvo не будет работать.

В C++17 ввели конструкцию if constexpr, и с тех пор вычисление nrvo в некоторых случаях дает субоптимальный результат.
Для такого примера NRVO работает, потому что тело if-а полностью дискардится из-за false вычисленного в compile-time:

template<bool B>
std::string foo() {
    std::string y = "y";
    std::string x = "x";
    if constexpr (1 + 2 == 4) {
        return y;
    }
    return x;
}

Для такого примера NRVO не работает, потому что тело не дискардится, true тоже вычисляется не отходя от кассы

template<bool B>
std::string foo() {
    std::string y = "y";
    std::string x = "x";
    if constexpr (1 + 2 == 3) {
        return y;
    }
    return x;
}

А для такого примера NRVO будет работать лишь для некоторых инстанциаций:

template<bool B>
std::string foo() {
    std::string y = "y";
    std::string x = "x";
    if constexpr (B) {
        return y;
    }
    return x;
}

Так как NRVO вычисляется через анализ scope, а не для отдельных инстанциацию, то Clang-у приходится "неизвестный заранее" результат if constexpr обрабатывать как если бы тело не дискардилось. В итоге для foo<true> код генерируется оптимальный, а для foo<false> - субоптимальный.

https://godbolt.org/z/fMfcYf75W (автор кода - Антон Полухин, 2021 год)

С другой стороны, переписать вычисление NRVO с анализа scope на анализ AST - это прямо гипер сложно, и такие усилия лучше потратить на более полезные вещи. Все-таки NRVO - это не обязательная оптимизация, поэтому никто не парится насчет if constexpr.

#advice

Иммутабельные классы для объектов API
(Практический совет)

Допустим, что вы программируете показ рекламы фастфуда 🍟🍔🍕🥤 на сайтах. Надо показать топ-5 наиболее подходящих блюд. Формула оценки довольно сложная: зависит от региона юзера, доступности блюд в ближайшей точке, маркетинговых акций, текущего времени, etc.

Запросы приходят в API вашего сервиса. Пусть все данные для оценки представлены классами/структурами на C++.

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

struct Restaurant {
    double Distance; // расстояние
    double Occupancy; // загруженность
    std::vector<Meal*> Meals; // доступные блюда
    std::vector<Promo*> Promos; // акции
    std::vector<Visit> VisitHistory; // история посещений
};

Некоторыми данными объект "владеет" (как историей посещения), а на некоторые просто ссылается, потому что они общие для всех.

Здесь получаем проблему - пусть у нас где-то в программе лежат объекты блюд std::vector<Meal> Meals. Если мы создадим Restaurant-ы, а потом добавим какое-то новое блюдо, то можно попасть на переаллокацию вектора, и в таком случае все ссылки Meal* станут висячими.

Можно обернуть объекты в умный указатель std::vector<std::shared_ptr<Meal>> Meals, но это не бесплатно и некрасиво.

Есть способ, который решает несколько проблем - все API-классы нужно объявить non-copyable И non-movable. Какие будут плюсы:

(1) Объекты невозможно случайно передать по значению/скопировать
(2) Указатели на объекты живут столько же, сколько контейнер, где содержится объект.

Компилятор C++ не даст заиспользовать контейнер как std::vector, который потенциально сможет инвалидировать ссылки. Скомпилируется использование безопасного контейнера, например std::list.

#madskillz

Указатели-коммуналки

Пусть мы хотим из метода вернуть какой-то объект вместе с булевыми флагами. Флаги это свойства, которые объект имеет. Тогда мы должны возвращать что-то вроде этого:

template<typename Ty> class ActionResult {
    bool Invalid = false;
    Ty T;
    // некие методы...
};

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

В этом случае флаги можно отселить... прямо вовнутрь ссылки:

template<typename PtrTy> class ActionResult {
    uintptr_t PtrWithInvalid; // можно считать что sizeof(uintptr_t) == sizeof(PtrTy*)
};

Как это должно работать? Ссылочный тип в 64-бит архитектуре имеет размер 8 байт, и мог бы напрямую адресовать оперативку до объемом до 16 млн ТБ.
Отсюда получается, что некоторые биты из этих 8 байт (старшие) вообще не используются, потому что они заведомо равны нулю.

Можно отселить флаг Invalid в нулевой бит:

     bool isInvalid() const { return PtrWithInvalid & 0x01; }
     bool isUsable() const { return PtrWithInvalid > 0x01; }
     bool isUnset() const { return PtrWithInvalid == 0; }

А сам указатель сдвинуть на один бит, освобождая место флагу:

     PtrTy get() const {
       return reinterpret_cast<PtrTy *>((PtrWithInvalid & ~0x01) >> 1);
     }

В Clang разрешено встраивать в указатель до трёх флагов (трёх битов): class PointerIntPair

Один из самых прикольных способов использования - класс QualType. Он содержит ссылку на чистый тип (Type*) и флаги-наличие квалификаторов (const, restrict, volatile).
Из-за вышеописанной техники этот класс совершенно бесплатен по памяти!

#video

NEED FOR SPEED

Если сравнивать C++ с другими популярными языками (Python, Java, C#, etc.), то адекватно написанные программы на нем будут почти наверняка быстрее аналогичных программ на других языках.

Однако и внутри C++ есть своя сегрегация по скорости.

(1) В стандартных проектах мало кого может удивлять использование std::shared_ptr вместо голых указателей, постоянные аллокации памяти, забытый где-то std::move. Скорее всего, фикс такого это действительно "экономия на спичках" и только будет потом мешать разработке.

(2) В не очень стандартных проектах (браузеры, компиляция) уже немного сходят с ума - используют small vector (часть вектора на стеке), статический полиморфизм (юзают CRTP вместо виртуальных функций), вместо std::string делают непонятно куда указывающие std::string_view и т.д. Это встречали многие.

(3) Но в реалтаймовых программах своя вселенная. Нельзя делать системные вызовы, блокировать поток, использовать алгоритмы сложности > O(1), и еще куча ограничений. Это обработка сигналов, звука, HFT-системы...

Про программы из класса (3) рассказывает Тимур Думлер:
https://youtu.be/8GlwkWxf3hk?t=3504
Использование стандартной библиотеки С++ для обработки сигналов в real-time

Это выступление было мне интересно, как человеку, никогда не сталкивавшимся с такими жесткими рамками 👍

#madskillz

Garbage Collector

На C++ есть проекты, где реализована сборка мусора.

Например, браузерный движок Blink (часть Chromium). Это такой монолит, где зависимости между разными объектами настолько сложные, что понимание общей картины - нереально для человека. И там есть МНОГО циклических зависимостей, потому что в какой-то момент архитектура бронзовеет и ее не переделать. Чтобы циклов не было, писали примерно так:

class A {
    RefPtr<B> m_b;
};
class B {
    A* m_a;
};

В какой-то момент всё было настолько плохо, что память протекала в 10% тестов. Решили проблему, добавив сборщик мусора. Это не особо повлияло на перф, но убрало многие протекания и краши - win!

https://docs.google.com/presentation/d/1YtfurcyKFS0hxPOnC3U6JJroM8aRP49Yf0QWznZ9jrk/edit

#advice

В любой непонятной ситуации делай шаблон

Это совет от Капитана Очевидности. Нередко в разных проектах встречаются две проблемы, которые решаются одним способом.

Пусть у нас есть метод, который принимает...

(1) Очень длинный тип, который вручную пишут полностью или через typedef.

using TBazArray = ::google::protobuf::RepeatedPtrField<Namespace::Foo::Bar::Baz>;
bool AllShallFall(const TBazArray& bazArray) { ... };

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

template<typename T>
bool AllShallFall(const T& bazArray) { ... };

(2) Передача лямбды в функцию. Вряд ли кто-то передает их как "ссылку на функцию" (а я их без Интернета не напишу), поэтому могут заиспользовать std::function. Он плох тем, что аллоцирует память в стеке, и вообще лишнее звено.

bool AllShallFall(std::function<int(void)> callback) { ... };
// ...
AllShallFall([]() { return 4; });

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

template<typename T> AllShallFall(T callback) { ... };
// ...
AllShallFall([]() { return 4; });

Нужно быть осторожным, если не хотите копирования больших объектов. Лямбды это объекты closure type, размер в байтах которого зависит от размера за-capture-нных данных (ссылка/указатель - 8 байт, объекты по значению - их sizeof). В примере выше именно копирование объекта closure type, хотя на это забиваем из-за того что размер 0 байт (ничего не capture-им).

Поэтому код выше можно сломать, если сделать capture некопируемого объекта

std::unique_ptr i = std::make_unique<int>(3);
auto l = [i = std::move(i)]() { return 4; };
AllShallFall(l);

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

template<typename T> AllShallFall(T&& callback) { ... };

#video

Рефлексия в C++

C++ отличается от многих языков отсутствием рефлексии. Рефлексия это способность программы "понимать" свою собственную структуру. Например - получить имя класса, список методов, добавлять методы, и так далее.

Рефлексии в run-time не будет никогда, потому что ~95% информации из исходников после компиляции просто испаряется, и полноценная рефлексия невозможна.

Развитие рефлексии в compile-time тормозилось несовершенством compile-time вычислений, поэтому эта фича войдет не ранее C++26.

О рефлексии рассказывает её разработчик Andrew Sutton - https://youtu.be/60ECEc-URP8
Интересно, что это уже второй подход к реализации рефлексии (на основе constexpr), был еще первый вариант - на основе шаблонов.

На основе этого видео и прочих источников я писал январьскую статью про рефлексию в C++Next, которую можно почитать, если тема покажется интересной 🙂 https://habr.com/ru/post/598981/

(text below)

#compiler

Как пропатчить Clang под FreeBSD

На прошлой неделе я решил попробовать починить что-нибудь в Clang, чтобы посмотреть, как это делается. Я нашел на гитхабе несколько issue, связанных с consteval-методами, и по вечерам отправлял на ревью микрофиксы.

Всего я сделал четыре патча (каждый не более нескольких строк), их можно увидеть на скриншоте
(второй снизу патч - "пробный шар" в clang-tidy, он не считается)

Один из них за неделю успели апрувнуть, другие пока висят и будут висеть много лет их судьба неясна. Какие есть впечатления и общие факты:

(1) Открытые гитхаб-issue реально могут висеть годами, пока их кто-нибудь не починит. Этот срок, наверное, коррелирует с важностью бага, но какого-то KPI на уменьшение тикетов Clang/LLVM не держит.

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

(3) Ревьюеры (в моих патчах отписалось 5-6 людей) - ОЧЕНЬ опытные в C++. Погрепав их имена, можно обнаружить их среди авторов многочисленных пропозалов в стандарт, докладчиков CppCon, членов комитета по плюсам, и так далее.

(4) Тусовка контрибьюторов довольно невелика, везде ревью и обсуждения проводят по сути одни и те же люди. Если искать по какому-то конкретному направлению (например consteval), то это вообще ~2 человека, которые запиливали эту фичу в соло и кроме них никто посмотреть ревью не сможет.

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

#creepy

Reference Lifetime Extension

Сегодняшнее "стрёмное правило стандарта": если вы инициализируете константную ссылку (const T&) "временным объектом" (скорее всего rvalue), то этот временный объект не уничтожается как ему было положено, а продолжает жить ровно столько, сколько живет ссылка.

Пример в двух строках:

std::string Foo::GetName();
const std::string& name = obj.GetName(); // легально и не сломается

Наверное, самое популярное использование этого правила - дефолтные значения ссылочных аргументов

void foo(const std::string& s = "default_text");

Это правило супер легко сломать - как только вызовете метод у временного объекта (obj.GetName().data()), или если будет сделан неявный каст, и так далее.
Abseil Tip of the Week показывает больше примеров успеха и фейла.

В моем примере наличие этого правила допустило лютый баг:

class A { ... };
class B : public A { ... };

void foo(const A& a) { ... }
void foo(const B& b) {
    // ...
    foo(static_cast<A>(b));
}

Я сделал неправильный каст, который скопировал объект, а не скастил к базовому классу. Правильный каст - static_cast<const A&>(b).

Выстрел в ногу произошел, когда foo(const A& a) стал сохранять ссылку на a, чтобы потом её переиспользовать. Пока вызывался foo, ссылка была рабочей, а вот потом объект разрушился и ссылка стала висячей. Дебаг занял достаточно много времени...

#longread

Я давно ничего не писал в этот блог, поэтому решил исправиться 🐸

Сегодня я дописал на habr статью про неклассические контейнеры в C++:
https://habr.com/ru/post/664044/

Из нее вы узнаете о таких контейнерах, как static_vector, small_vector, dynamic_bitset и многих других. Рекомендую к прочтению!

#creepy

Heterogeneous Lookup

Что будет, если попытаться вызвать .find()/.contains()/etc. у ассоциативных контейнеров (std::set/std::map/unordered-версии) с ключом, который не совпадает по типу? 🤔

std::map<std::string, int> m;
// ...
if (m.contains("foobar")) { ... }

У std::map есть дефолтный компаратор третьим аргументом в шаблоне - std::less<Key>. Компаратор нужен для поиска в контейнере.

Компаратор это структура, у которой должен быть определен bool operator(); выглядит оно примерно так:

constexpr bool operator()(const Key &lhs, const Key &rhs) const {
    return lhs < rhs;
}

То есть тип аргумента должен совпадать с типом ключа. Возвращаясь к примеру в начале: "foobar" имеет тип const char[7]. Он может "разложиться" в тип const char*, быть преобразован в тип std::string_view или std::string. Поэтому, к сожалению, по overload resolution создается временной объект std::string. 💩

Проверить, что это именно так, можно через строку с кастомным аллокатором (см. определение std::string), который логирует запрос на аллокации.

using traceable_string = std::basic_string<char, std::char_traits<char>, trace_allocator<char>>;

Проверяемые строки должны быть достаточно длинными, чтобы обойти Small String Optimization и вызвать аллокацию, в моем окружении это от 16 символов - код на godbolt.

Но зачем создавать std::string, если разные строковые типы сравниваемы между собой? В C++14 проблему решили лютым костылем 🩼: сделали std::less<> = std::less<void> и переопределили std::less<void> кастомно так:

template <class Key1, class Key2>
constexpr auto operator()(Key1&& lhs, Key2&& rhs) const
    return static_cast<Key1&&>(lhs) < static_cast<Key2&&>(rhs);
}

Теперь для перфоманса нужно помнить этот хак и делать

std::map<std::string, int, std::less<>> m;

тогда лишних аллокаций не будет - код на godbolt. Это называется громким словом heterogeneous lookup.

Я не смог найти причину, почему это не сделали поведением по умолчанию. Я порылся в библиотеках с кастомными контейнерами и вижу два подхода к вопросу:
(1) homogenous lookup по умолчанию (как в STL) - пример boost::container::map
(2) heterogeneous lookup по умолчанию - пример хэш таблицы в Abseil (от Google), аналог std::unordered_map/set

Перф неплохо улучшается, пример расследования для unordered контейнеров - там цифры от 20% до 35%.

#longread

У std::unique_ptr есть минус - он аллоцирует память в куче. А что, если разработать его аналог с памятью на стеке?.. Об этом можно прочитать тут!

https://habr.com/ru/post/665632/

#madskillz

Fast Pimpl

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

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

PImpl используется, чтобы скрыть детали реализации и/или ускорить компиляцию. До его использования код в хидере выглядит так:

#include <third_party/json.hpp>
struct Value {
    third_party::Json data_;
};

Стандартный подход заключается в замене T на std::unique_ptr<T>, потому что он разрешает использовать incomplete class:

namespace third_party { struct Json; }
struct Value {
    std::unique_ptr<third_party::Json> data_;
};

Проблема, которая из-за этого возникает - аллокация объекта в куче, это замедляет рантайм PImpl-ового варианта ⏱ Поэтому используется подход Fast Pimpl:

struct Value {
    std::aligned_storage<sizeof(T), alignof(T)> data_;
};

(вместо sizeof(T) и alignof(T) надо руками ввести нужную цифру)

То есть вместо самого объекта в структуре лежит буфер памяти под этот объект, и рулят именно им.

В интернете есть много реализаций этой идиомы (по гуглежу "Fast Pimpl"), и есть обёртки, которые хороши собой 🍬

#compiler

extern "C" - на что в действительности это влияет?

Примерно 9 лет назад я пробовал писать игры на C++. Для скриптов я использовал Lua. Он поставлялся в виде статической библиотеки (lua.lib для Windows) и header-файлов. Так как Lua написан на C и lua.lib собран компилятором C, то чтобы все слинковалось, надо было подключать хидеры так:

extern "C" {
#include <lua.h>
#include <lualib.h>
#include <lauxlib.h>
}

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

В языке C перегрузки методов нет, и в объектный файл попадает "чистое" название метода. В C++ попадает "запутанное", это называется name mangling:

void hello(int, char) -> hello (в С)
void hello(int, char) -> _Z1helloic (в C++)

extern "C" нужен как раз для того, чтобы методы и переменные, объявленные внутри него, имели "чистое" имя (код на godbolt)

Однако что в остальном? Сам код внутри extern "C" компилируется как C++ или как C? Мнение "C это подмножество C++" ошибочно: два языка развиваются независимо. В C есть то, чего нет в C++, например VLA.

Сам Стандарт показывает примеры, из которых видно, что код скомпилируется по правилам C++: [dcl.link] (там есть классы).

Погрепав исходники компилятора, можно точно сказать, что компиляция внутри extern "C" происходит по правилам C++, и аффектится только условие "надо манглить или нет": исходник Clang.

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

#books

Обзор книги "Advanced C and C++ Compiling" 📚

(можно скачать тут - https://www.tgoop.com/progbook/6109)

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

Эта книга, которую я читал в прошлом году, имеет очень большую редкость.
В ней описаны роли линкера (linker) и загрузчика (loader) и их работа в очень глубоких деталях (а также компилятора (compiler), но в меньшей степени). Есть много картинок, описаний форматов, команд Linux и Windows, и прочего.

Книга подробная вплоть до того, что объясняет, по какой схеме надо правильно версионировать свои динамические библиотеки! 🤯 (понятно, что это очень специфическое занятие)
Я бы рекомендовал для чтения первые несколько глав, а также главы 12 и 13 (для Linux-разработчиков)

#story

Как готовятся задачи к олимпиадам по программированию? (Часть 1/2)

Наверное, много кто пробовал решать задачки: на codeforces.com, школьных олимпиадах, ACM ICPC, и в других местах. Большинство людей использует C++ для решения.

Я раньше очень увлекался этим занятием (называется "проблемсеттинг"), и даже эпизодически готовил задачи для codeforces и школьных олимпиад (подготовил примерно 15-20 задач).

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

Покажу на примере одной задачи, как происходит подготовка: Codeforces Round #704 - E. Почти отказоустойчивая база данных
(Эта задача самая сложная в том раунде, но у нее простое описание)

Как готовятся задачи к олимпиадам по программированию? (Часть 2/2)

Подготовка задачи ведется на сайте polygon.codeforces.com. Это самая продвинутая платформа, долгое время была практически единственной. Другие платформы (Яндекс.Контест, CodeChef, etc.) со временем потырили у нее фичи - валидацию, встроенную систему контроля версий, и прочее.

Для программок (генераторы, чекеры, etc.) используется библиотека testlib.h.

Процесс подготовки задачи состоит из этих пунктов (могут идти в произвольном порядке, кроме п.1):

(1) Придумывается не-баянистая идея для задачи в краткой формулировке.

(2) Создается художественное описание задачи в LaTeX - пример, это называется "легенда".

(3) Пишутся генераторы тестов, таких программок может быть несколько - пример 1, пример 2. Они могут запускаться с разными параметрами.

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

(5) Список тестов создается через движок шаблонов Freemarker. Можно написать скрипт, который потом преобразуется в список запусков генераторов - пример из документации. В нашей задаче 100 тестов - список.

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

(7) Чекер проверяет решение участника на правильность. На polygon есть дефолтные чекеры для простых задач, но если в задаче может быть несколько правильных ответов, то нужен свой чекер - пример.

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

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

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

(1) Много участников додумались до решения проще авторского и реальная сложность задачи преувеличена
(2) Задача имеет слабые тесты, из-за чего проходит много "плохих" решений.
(3) Авторское решение неправильное.

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