#c #cpp

Попалась довольно сомнительная статья на хабре про редкие возможности в С. Учитывая половину списка, не очень понятно, что такое редкие возможности в понимании автора. Не предлагаю вам её читать, чтобы не тратить время. Остановлюсь только на самых интересных моментах и прокомментирую/добавлю немного информации.

1. Конкатенация строк времени компиляции.
Думаю, вы тоже видели какой-то подобный код:

std::string very_long_string = "This is first part of long string." "And this is second";

Никаких плюсов и функций конкатенации: компилятор сделает это одной строкой сам. Используя такое поведение можно реализовать интересный макрос:

#define LOG(exp) std::cout << "Result of " #exp "=" << exp;
int x = 12;
LOG(x*5);

Результатом будет "Result of x*5=60".

2. Препроцессорная склейка строк.
Как вы думаете, будет ли инкремент в следующем коде?

int inc(int x) {
// doing increment\
x++;
return x;
}

Вопрос в том, что произойдёт раньше: конкатенация строк, разбитых через \, или замена комментария на пробельные символы? Легко можно убедиться, что x++ станет частью комментария, то есть строки конкатенируются раньше. Я как-то смотрел замечательную лекцию по тулчейну, где пояснялся этот момент и думал "ну разве можно так набагать", а недавно мне рассказали, что обнаружили подобное в проде. Забавно.

3. Функции в стиле K&R.
Не знал, что такая возможность раньше была в C. Суть заключается в том, что вы объявляете функцию следующим образом:

int foo(s, f, b)
char* s;
float f;
struct Baz * b;
{
return 5;
}

в то время как сегодня она выглядела бы более привычно:

int foo(char* s, float f, struct Baz * b) {
return 5;
}

4. tmpfile.
В статье конечно речь идёт и сишной функции, однако есть аналог std::tmpfile (который тем не менее ничем не отличается). Автор не приводит каких-то полезных применений временных файлов. Мне когда-то было полезно при написании внешней сортировки (правда, там было использование std::tmpnam, но сути не меняет), а ещё, если внимательно посмотреть на то, что делает ваш компилятор при билде программы (например --verbose для g++), то можно увидеть, что компилятор создаёт некоторое кол-во временных файлов, которые можно даже попросить его не удалять.

5. Отрицательные индексы.
Делается такое довольно просто:

int* arr = new int[100] + 50;

Теперь можно обращаться по индексу в обе стороны. Только, как и всегда, стоит быть осторожным с границами и очищением памяти : )

6. std::new_handler.
В C++ есть такое понятие как new_handler (не новый обработчик, а обработчик оператора new). В случае, если new не может выделить необходимое количество памяти, он вызывает свой обработчик в надежде, что тот разрулит ситуацию: сделает дефрагментацию, что-то освободит, переназначит обработчик или что-нибудь ещё. В случае повторного неуспеха обработчик будет вызван ещё раз, то есть такая программа вполне приводит к бесконечной рекурсии:

void f() {}

int main() {
std::set_new_handler(f);
int* p = new int[1000000000000];
}

#highload

Попытаюсь с умным видом вкинуть инфы про высоконагруженность.

Очень важной задачей при разработке высоконагруженных систем является поддержание отказоустойчивости (часто хочется удержать что-то вроде 99.99% аптайма). У нас проверка работоспособности сервисов проверяется довольно понятно: проводятся учения по отключению одного из датацентров. Такие учения бывают внешние (для всей компании) и внутренние (для конкретных сервисов и продуктов). По своему (небогатому) опыту могу сказать, что такие мероприятия очень полезны: вроде на прошлой неделе всё прошло успешно, а сегодня уже проблемы с коннектами в базе, тайминги выросли или на сервисе начинает загораться congestion control.

Но рассказать хотелось бы об инструментах Netflix: chaos monkey.
Chaos monkey является частью chaos engineering (хотя можно сказать, что стала началом):

Chaos engineering is the discipline of experimenting on a distributed system in order to build confidence in the system's capability to withstand turbulent conditions in production.

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

Обычно падения настраиваются, чтобы отключение инстанса происходило в тот момент, когда команда наиболее готова к сражению с падением. "Падать" могут лишь те машинки, которые помечены для этого доступными. Все доступные для "уранивания" машинки делятся на группы. Каждый будний день обезьяна приходит в каждую группу инстансов и бросает монетку (если точнее, то монетка взвешеная), чтобы решить, ронять ли какую-то машинку из этой самой группы. Если она решает, что надо, то шчедулит падение на случайное время в промежутке от 9:00 до 15:00. Каждое приложение/сервис определяет 2 величины, на основе которых бросается монетка: среднее время в рабочих днях между падениями и минимальное время в рабочих днях между падениями.

Из минусов можно отметить:
- для chaos monkey необходимы spinnaker (система развёртывания в нетфликсе) и mysql;
- генерирует только псевдослучайные падения конкретного инстанса приложения/сервиса, в то время как разнообразие проблем в реальной жизни гораздо шире;
- работу chaos monkey нельзя просто так прервать. Если что-то пойдёт не так, остаётся только сражаться.

В какой-то момент одного инструмента стало не хватать, потому появилась simian army (которая, тем не менее, уже не поддерживается).

Simian army включает в себя ещё три основных инструмента:
1. Janitor monkey или сегодня swabbie -- аналог сборщика мусора для облачной экосистемы.
2. Conformity monkey проверял соответствие инстансов некоторым предефайненым правилам. В случае несоблюдения правил, инстанс отключался. Сейчас это часть spinnaker.
3. Security monkey проверял инстансы на различные дыры в безопасности.

и ещё несколько, которые были депрекейтнуты сильно раньше или не опубликованы:
4. Chaos gorilla, который симулировал отключение одной из 25 зон инфраструктуры AWS (т.е. отключение огромной части всех инстансов).
5. Chaos kong -- аналог прошлого инструмента, но симулирующий отключение меньших частей инфраструктуры.
6. Latency monkey -- тулза, увеличивающая тайминги ответов некоторых ручек в сервисах.
7. Doctor monkey -- инструмент, мониторящий состояние инстансов. Если инстанс "заболел" (пятисотит, выросли тайминги или кушает много cpu), doctor убирает его из приложения.
8. 10-18 monkey (i.e. l10n-i18n) проверяет работу сервисов, которые работают в различных географических зонах. Чекаются проблемы связанные с локализацией и всем что около.

Массивная и интересная (мне показалось) статья про fork().
https://habr.com/ru/post/586604/

#common

Аллокатор как метод управления памятью впервые появился в С (речь не о std::allocator, а о самом термине, который был реализован в malloc/free), а своё, можно сказать, известное воплощение получил в C++ как std::allocator (в 1994м) и std::pmr::allocator (В C++17). Однако не одними C/C++ едины. Аллокаторы также существуют и в других языках программирования (как самостоятельный термин, так и наследие/заимствование C/C++).

В силу развития языка в какой-то момент аналоги malloc/free появились в COBOL и Fortran 90. Аналогичный метод управления памятью есть и в D (malloc, new), т.к. он появлялся как более правильный C++ и тянет за собой часть стандартных библиотек C/C++, хотя сам D имеет свой сборщик мусора.

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

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

#[global_allocator]
static GLOBAL: MyAllocator = MyAllocator;

До версии 1.28 rustc неявно линковал jemalloc в каждую свою программу. Чтобы ослабить зависимость от libc, это поведение изменили в сторону стандартного системного аллокатора.

update: В C++ тоже можно "подменить" глобальный аллокатор.
Перегрузим глобальные операторы new/delete, засунув в них соответствующие операции из готового аллокатора. Единственное что это всё-таки немного неполноценно в силу того, что используемый аллокатор может работать только с памятью (ведь вызов конструктора/деструктора не переопределяется), а интерфейс std::allocator до C++20 (пусть он и не прав идеологически, что такими вещами занимается) всё-таки хочет и это контролировать. С 20ого стандарта методы construct/destroy удаляются и заменяются на std::construct_at/std::destroy_at. В таком виде можно говорить о корректной замене глобального аллокатора.

2. Zig.
Тут нет дефолтного аллокатора. Чаще всего вы выбираете свой аллокатор согласно рекомендациям и отдаёте его как параметр. Если вы пишете свою библиотеку, авторы предлагают придерживаться подобной концепции и требовать у пользователя аллокатор, который ему нравится. А вообще он предоставляет (не сказал бы что богатый, но) зоопарк из нескольких аллокаторов, которые вам могут понадобиться: от std.heap.c_allocator (C malloc/free) и нескольких пул-аллокаторов до аллокаторов для тестирования и std.heap.GeneralPurposeAllocator, если вам ничего не подошло (так написал, будто между крайними случаями ещё солидное кол-во аллокаторов, хотя на самом деле я перечислил почти все).

#common

Сборщики мусора 1/2.

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

Есть несколько базовых алгосов, которые в разных вариациях юзаются в большинстве промышленных garbage collector'ах. В основном они делятся на трассирующие (которые отслеживают достижимость объекта) и прямые. И параллельно делятся на перемещающие и не перемещающие (в моей вольной интерпретации).

Mark-and-sweep.
Самый дефолтный алгоритм. Для каждого объекта хранится бит достижимости. Изначально он ноль. Все объекты указывают друг на друга. Есть специальные корневые объекты. На этапе mark дфсом обходим все объекты, достижимые из корневых, и устанавливаем им бит достижимости в 1. На этапе sweep обходим все объекты и проверяем, если бит достижимости 1, то просто его сбрасываем. Если же он 0, то объект помечается удалённым (обычно пихают его во freelist). Проблемой такого подхода является stop the world -- всё выполнение программы останавливается, пока сборка на закончится.
Есть ещё вариация mark-and-compact, где вместо помечания участка памяти свободным объекты в памяти как-то перемещаются, чтобы немного её дефрагментировать.

Существует улучшенная версия этого алгоритма под названием BF Mark, которая избавлена от этих недостатков.
Вместо двух "цветов" достижим/нет объект используется 3: чёрный, серый и белый. Чёрные объекты доступны из корней и не имеют исходящих ссылок на белые объекты, белые -- кандидаты на удаление, серые -- объекты доступные из корней, но пока не проверенные на наличие ссылок на белые объекты. Алгоритм состоит из трёх шагов: выбрать объект из серого множества и переместить его в чёрное; поместить все белые объекты, на которые есть ссылки из нового чёрного в серое множество; повторять прошлые два шага, пока серое множество не станет пустым. Когда серый набор пуст, сканирование завершено: черные объекты доступны из корней, в то время как белые объекты недоступны и могут быть собраны мусором. Поскольку все объекты, до которых невозможно добраться сразу из корней, добавляются к белому набору, а объекты могут перемещаться только от белого к серому и от серого к черному, алгоритм сохраняет важный инвариант - никакие черные объекты не ссылаются на белые объекты. Это гарантирует, что белые объекты могут быть освобождены после того, как серый набор станет пустым. Такой метод удобен, потому что его можно выполнять на лету.

Ещё популярна копирующая сборка (semispace/Lisp 2/алгоритм Чейни). Алгоритм основывается на том, что выделяется две области памяти одинакового размера. Все объекты создаются в одной из них, вторая при этом содержится пустой. Как и в прошлом алгоритме, есть несколько корневых объектов, которые ссылаются на другие. В некоторый момент все объекты проверяются на достижимость. В случае, если объект валиден, он дублируется во вторую пустую область памяти, иначе удаляется. В итоге все достижимые объекты скопированы в новое место. Произошла очистка ненужных объектов и уплотнение для избежания фрагментации.

#common

Сборщики мусора 2/2.

Как пример прямого сборщика мусора можно привести считающий ссылки коллектор. Проверка достижимости происходит очень просто: в случае, когда счётчик ссылок у объекта равен нулю, его можно удалять. Однако такая тривиальная реализация не учитывает компоненты связности объектов, где вся группа недоступна, но объекты указывают друг на друга. В таком случае можно усовершенствовать алгоритм и производить поиск циклов или их конденсацию в графе объектов, чтобы бороться с подобными ситуациями. Такой сборщик мусора является довольно простым в реализации, однако имеет значительный недостаток -- все операции со ссылками становятся чуть медленнее (кроме самого подсчёта могут быть проблемы с синхронизациями и подобным).

Одним из самых эффективных алгоритмов сборки мусора является сборщик мусора с поколениями. Он основан на простом утверждении: большинство объектов умирают молодыми.
Новые объекты считаются объектами первого поколения. Если эти объекты переживают n сборок мусора, их поколение становится вторым. Объекты более высокого поколения проверяются реже, т.к. подразумевается, что раз они уже долго прожили, то и далее проживут дольше молодых объектов. В случае, если они опять переживают несколько сборок мусора своего поколения, то они перемещаются в третье поколение. Количество поколений обычно ограничено каким-то небольшим числом (т.е. не растут бесконечно). Правило при обходе графа объектов простое — если нам повстречался объект из более старшего поколения, чем проверяемое в данный момент, дальше в этом направлении не идем. Однако здесь есть тонкий момент. Поскольку объекты в общем случае могут изменяться, они также могут содержать ссылки на объекты более молодого поколения. Поэтому во время выполнения программы необходимо отслеживать ситуации, когда более старый объект начинает ссылаться на более молодой и добавлять в этом случае молодой объект в «корневое множество» объектов соответствующего поколения. Иначе сборщик мусора ошибочно удалит его, как недостижимый.
Иногда полезно знать, как устроен сборщик мусора, которым пользуется разработчик, чтобы не бояться создавать этот самый мусор. Например объекты можно переиспользовать, однако для сборщика мусора с поколениями это будет означать, что объект долгоживущий, из-за чего его поколение вырастет и он будет проверяться реже. Это искуственное продлевание жизни объекта в итоге может сделать операции сборщика мусора менее эффективными.

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

#cpp

Немножко macros tricks.

Макросы в целом скорее bad practice. Они могут приводить к нечитаемому коду и неожиданному поведению. Но они всё же позволяют делать интересные вещи.

1. При использовании макросов часто совсем непонятно, во что же он раскрывается. Как вам такой код?

int x = 1;
SOME_MACROS(x)

На первый взгляд он кажется неестественным: а почему это компилится? Почему нет точки с запятой? Потому что автор макроса засунул её внутрь. Вы её не поставите и всё скомпилируется. Но кого-то позже введёт это в ступор, кто-то решит поменять ваш макрос и код перестанет компилиться из-за нехватки этой самой ; во всех местах использования. Конечно, можно договориться всегда писать её после макросов, но тогда это лишь рекомендация, которую можно и не выполнять. Лучше будет заставить пользователя макроса писать аккуратно. Например обернув всё тело макроса в do-while:

#define SOME_MACROS(x) \
do { \
++x; \
} while (false)

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

2. Об этом уже упоминалось, но повторим.
Думаю, вы тоже видели какой-то подобный код:

std::string very_long_string = "This is first part of long string." "And this is second";

Никаких плюсов и функций конкатенации: компилятор сделает это одной строкой сам. Используя такое поведение можно реализовать интересный макрос:

#define LOG(exp) std::cout << "Result of " #exp "=" << (exp);
int x = 12;
LOG(x*5);

Получаем: Result of x*5=60

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

Первые это __FILE__, __LINE__:

#define assert(expr) \
(static_cast<bool>(expr) \
? void(0) \
: assert_fail(#expr, __FILE__, \
__LINE__, __ASSERT_FUNCTION))

Или __PRETTY_FUNCTION__:

void f(int) {
std::cout << __PRETTY_FUNCTION__;
}

Получим: void f(int)

Ещё есть __FUNCTION__ и __func__.

И __COUNTER__: по мере вызова в рамках программы он выдаёт натуральные числа от нуля и выше:

std::cout << __COUNTER__ << __COUNTER__ << __COUNTER__;

Результат: 012.

Последний можно использовать для создание макроса для анонимных переменных:

#define CONCATENATE_IMPL(s1, s2) s1##s2
#define CONCATENATE(s1, s2) CONCATENATE_IMPL(s1, s2)

#ifdef __COUNTER__
#define ANONYMOUS_VARIABLE(str) CONCATENATE(str, COUNTER)
#else
#define ANONYMOUS_VARIABLE(str) CONCATENATE(str, __LINE__)
#endif

Теперь вы можете спокойно юзать этот макрос для создания анонимных переменных:

auto ANONYMOUS_VARIABLE(var) = gsl::finally([] {});

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

Тут рассказывают, как это сделать чуть более юзабельным.

Кстати бонусом вопрос: почему нам нужен промежуточный макрос CONCATENATE_IMPL?

#cpp #poll

Задача такая: выполнить какой-то код ровно один раз во время жизни нашей программы. Решение вполне понятное:

void init() {
static bool unused = [] {
std::cout << "printed once" << std::endl;
return true;
}();
}

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

printed once

А что, если я хочу вызвать какой-то код ровно n раз? Об этом и предлагаю вам подумать : )

Как обычно, если никто не пробьёт, ответ через пару дней.

UPD: хотелось бы увидеть решение руками, а не с чем-то вроде std::call_once (но ими всё равно можно поделиться :) ).

#cpp #poll

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

Вспомним, как работает этот код:

void init() {
static bool unused = [] {
std::cout << "printed once" << std::endl;
return true;
}();
}

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

If the initialization throws an exception, the variable is not considered to be initialized, and initialization will be attempted again the next time control passes through the declaration.

Возникает ужасная идея: поюзать исключения для контроля flow вашего кода (не делайте так пожалуйста). Так что можем сообразить что-то такое:

struct Throwed {};

constexpr int n = 3;

void init() {
try {
static bool unused = [] {
static int called = 0;
std::cout << "123" << std::endl;
if (++called < n) {
throw Throwed{};
}
return true;
}();
} catch (Throwed) {}
}

Как по мне, оч прикона.

Ещё можно найти такой факт:

If the initialization recursively enters the block in which the variable is being initialized, the behavior is undefined.

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

#list

Несколько рандомных фактов.

1. Посмотрим на такой код:

struct Kek { int lol; int kek; };
std::vector<Kek> keks;
for (const auto& [lol, kek] : keks) {
[=] { std::cout << lol << "\n"; }();
}

Неожиданно, он не скомпилируется. Не скомпилируется он на моменте обращения к переменной lol в лямбде. Странно, да?🤔
На самом деле переменные из structure binding не умеют захватываться в лямбды (это, стоит надеяться, временно). Немножко пояснений можно посмотреть тут.

Кстати примерно из-за этого же structure binding становится пацаном довольно неровным, потому что начинает ломать всякое NRVO. Будьте аккуратны.

2. Попался один интересный доклад на CppCon 2016 про оптимизацию вашего кода. Автор предлагал использовать принцип DRY не только в случае написания кода, но и с шаблонами:

struct B {
virtual ~B() = default;
};

template <typename T>
struct D : B {
std::vector<int> get() const { return m_v; }
std::vector<int> m_v;
};

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

struct B {
virtual ~B() = default;
virtual std::vector<int> get() const { return m_v; }
std::vector<int> m_v;
};

template <typename T>
struct D : B {};

Так сказать взгляд с другой стороны.
Посмотрите доклад. Там прикона : )

3. При использовании std::function<void(args...)> (с возвращаемым типом void) к такому объекту можно кастовать любой функтор с такими же аргументами, но любым возвращаемым типом. То есть вот такое будет компилироваться:

std::function<void()> f{[] -> int {return 1;}};

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


И ещё немного ссылочек на выходные:

0. Интересный доклад о переписывании базы данных личных сообщений в Вк.

1. Обзорный доклад про очереди в highload.

2. Статья про то, как важно уметь отказываться от уже сделанного.

3. Удобное сокращение для стандартных стримов в C++: https://github.com/vitaut/_._ (sorry).

4. Статья про некоторые отличия в реализациях частей C++ от разных компиляторов.

5. Новый формат QOI (qoiformat.org), который неплохо сжимает картинки, на уровне PNG, но при этом в десятки раз быстрее, а его спецификация -- одна страница.

#common #java (сам офигел)

G1GC 1/2.

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

Внутри Hotspot JVM (я так понял в мире жавы существует много разных vm прям как компиляторов в плюсах или интерпретаторов в питоне, но это каноничный от Sun microsystems и соответственно Oracle) есть несколько дефолтных сборщиков мусора. Сегодня по ним и пройдёмся.

SerialGC -- последовательный сборщик мусора, состоящий из DefNEW и Tenured. Первый занимается сборкой молодого поколения и является копирующим сборщиком мусора, второй же следит за взрослым поколением и является модифицированным алгоритмом mark-sweep-compact. В силу того, что на обоих этапах происходит перемещение, аллокация аналогично pooled-аллокаторам (выдали указатель, сдвинули cur в пуле).

ParallelGC (ParNEW) -- параллельный сборщик мусора, состоящий из параллельного копирующего для молодого поколения и параллельного mark-compact для взрослого поколения. Аллокация также линейная. Несмотря на параллельность, он всё ещё является stop-the-world, однако паузы в среднем меньше.

CMS -- параллельный сборщик мусора, пытающийся минимизировать паузы приложения и использовать фоновую сборку. При первой остановке приложения фиксируется граф объектов. Далее в фоновом режиме этот граф обходится. На следующей остановке учитываются изменения, которые могли произойти за время фонового обхода, после чего в фоне происходит sweep этап. Структурно используется параллельный копирующий сборщик для молодого поколения, а для взрослого поколения фоновый mark-sweep. Аллокация происходит из freelist'ов, что приводит к фрагментации. Компактификация происходит только в случае, когда памяти начинает не хватать, что приводит к полной сборке мусора (для CMS это полный stop-the-world в один поток🤢). В последних версиях джавы был удалён, т.к. авторы перестали поддерживать.

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

#common #java

G1GC 2/2.

G1 (garbage-first/G one) является сборщиком мусора общего назначения (i.e. работает со всей кучей). Он является параллельным фоновым сборщиком мусора, который пытается минимизировать паузы приложения. Основной абстракцией является сборка поколениями: существует молодое и взрослое поколение. Молодое поколение содержит три пула: основной (eden) и два дополнительных (survivors). Основной пулл содержит самые молодые объекты, два дополнительных используются для копирующей сборки мусора внутри молодого поколения (то есть внутри молодого поколения существует разделение на подпоколения: прям ну совсем молодые чуваки и объекты, пережившие хотя бы одну сборку). Когда в молодом поколении недостаточно места для новой аллокации, происходит малая сборка мусора. Она заключается в том, что все выжившие в eden объекты перемещаются в один из пулов для копирующей сборки.
Элементы из копирующего сборщика могут быть либо удалены, либо перемещены внутри копирующего сборщика, либо перенесены во взрослое поколение (если сборщик мусора примет такое решение).

Вся куча приложения делится на регионы размером от 1Мб до 32Мб. Каждый регион динамически относится в молодое/взрослое поколение (после сборок мусора регионы могут возвращаться во множество свободных и получать новую роль по необходимости).
В случае молодого регион может выполнять роль eden или survivor.

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

Во время сборки мусора выбирается множество регионов, которые будут очищаться (collection set). В него входят все регионы из молодого поколения и возможно некоторые из взрослого поколения (тут есть разделение по типу collection set'а: сборка только в молодых регионах, смешанная сборка и FullGC). Недостижимые объекты удаляются, а достижимые перемещаются в свободные регионы, которые назначаются либо регионами для взрослого поколения, либо survivor-регионами. При хорошем выборе регионов для очистки и засчёт compact новые регионы занимают меньше места, чем занимали объекты ранее (но не обязательно).

Для того, чтобы понимать, какие регионы из взрослого поколения стоит брать в очередной collection set, у каждого региона имеется remembered set, хранящий взаимосвязи объектов между регионами. То есть если объект из региона A ссылается на объект из региона B, то в rset'е B будет запись A. На основе этого ребята делают какие-то выводы.

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

Когда хорошо юзать:
+ хотите паузы <0.5-1s;
+ минимальные настройки;
+ размер кучи >5Гб;
+ вам норм чиститься только когда больше половины кучи занято;
+ скорость создания объектов сильно меняется;
+ боремся с фрагментацией.

По настройкам кстати флагов у него хватает (кстати они оч забавные: -XX:MaxGCPauseMillis). Можно не пытаться подбирать такие конфигурации размеров регионов, что время пауз станет нормальным, а указать само время, и gc сам попытается подстроиться (не обещает, но постарается).

Вообще вся инфа из доклада одного из разрабов Oracle. Дока.

В планах ещё один java gc и бегло по другиим языкам, потому что пока чего-то крутого/подробного я в них не нашёл.

На словах мб не оч понятно, потому вот очень упрощённая картиночка движений объектов при очередной сборке в G1.

#list

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

1. Уже сто раз была инфа про фичи C++20, но я опять обнаружил для себя что-то новое.
Например:
- наличие std::source_location. Такая стильно-модно-молодёжная замена __FILE__, __LINE__ и __PRETTY_FUNCTION__.
- условный explicit i.e. explicit(bool). Статья с понятными кейсами.
- std::lerp -- линейная интерполяция.
- std::midpoint -- аккуратное вычисление среднего.

2. Про вот это уже писал, но тем не менее. Немножко больше кейсов, когда typename можно явно не писать.
template <typename T>
struct A : T::x {
using type = T::type; // marked
int v{T::val};
T::type x; // marked
};
Вот такой код по идее должен компилится. И в gcc 9 его поддержали, а вот clang жмотится и не хочет: marked-строки не дадут программе заработать.

---
Если у вас есть опыт перехода/наблюдения за ним на C++20 в проде, расскажите кратенько, как это происходило (с размером команды, которую эту задевает). Учитывая, как хорошо экосистема плюсов (компиляторы, cmake) готовы на данный момент к 20ому стандарте, есть ощущение, что надо бы какой-нибудь стандарт вроде 29ого сдвинуть на годик-два вперёд, чтобы у всего вокруг были шансы догнать. А то так и сидим без модулей в cmake и без компиляторов, которые умеют в стандарт двухлетней давности.
---

3. Думаю, на @experimentalchill подписано в окрестности 100% читателей этого канала, но если вдруг нет, вот недавняя приконая статья про исправление сортировки: оригинал и перевод.

4. Прикиньте, что в C есть: VLA и flexible array member.
Первое это делать что-то вроде:
void f(int n) {
int arr[n];
}
а второе:
struct S {
int len;
double arr[];
};

5. Тестик на знание C.

6. Узнал, что чуваки в go завезли оператор A AND (NOT B), который выглядит как &^ , у которого ещё есть форма с равно: &^= . Они норм вообще))
Обычный ксор это a^b, а инвертирование тем же символом ^a. Накрутили, прям как в плюсах..
Вот кстати какая-то статья про неординарность этого языка.

7. Почему оно не находится. Андрей Аксёнов какой-то забавный чел. Прикольно рассказывает. В данном случае про то, как с нуля строить поиск.

#common #java

Java GC 1/2.

Из популярного в java ещё есть сборщик мусора Shenandoah. Как и G1, шенонда -- region based concurrent сборщик мусора.

Сначала происходит параллельная маркировка с двумя паузами до/после. В результате для каждого занятого региона становится понятно, как много живых объектов в нём содержится. Из регионов с небольшим количеством достижимых объектов формируется collection set, из которого происходит фоновое уплотнение в новый регион (concurrent evacuation).
После уплотнения нельзя считать, что регионы, из которых происходило уплотнение, можно ощищать.
На данные в них могут существовать ссылки из других регионов, потому следующим этапом производится перезапись ссылок с данных из старых регионов на данные в уплотнённом (concurrent update refs; тоже паузы до/после). После этого можно считать регионы очищенными и аллоцировать из них память.

#common #java

Java GC 2/2.

Ещё одним известным сборщиком мусора в Java является ZGC. По принципу действия он аналогичен Shenandoah с точностью до некоторых локальных оптимизаций, которые, тем не менее, иногда играют значительную роль в использовании. Важным достижением ZGC являются константные stop-the-world паузы.

А ещё есть no-op EpsilonGC.

Вообще весь движ начинается в момент реализации барьеров на чтение/запись. Там какие-то java-специфичные вещи довольно. Если интересно, можно посмотреть докладик Алексея Шипилёва (я так понял, это Полухин из мира жавы).

На картиночке условное сравнение, чтобы выбрать gc по нуждам.

[1]. Shenandoah 1.
[2]. Shenandoah 2.

P.S. На правах рекламы вкину статью про обучение очень больших моделек. Что делать, если они не помещаются на GPU, и как с этим вообще жить: link. Вдруг тут есть любители машинок : )

#list

Очередная пачка рандомной инфы.

1. Пару дней дебагал уб. Половину этого времени потратил на то, чтобы исключить false positive срабатывания санитайзеров на fmtlib и хедер stl с итераторами. Делается это при использовании блеклиста санитайзеров. Не знал, что такое есть. Кстати не отдебагал.

2. Недавно стал свидетелем дискуссии про то, как парсить плюсы (навеянной вот этим докладом). Если кратко, предлагается упростить синтаксис плюсов до некоторого достаточного множества конструкций, чтобы не парсить сложные завороты больной фантазии программиста. Умные дяди сказали, что писать самому звучит как не успех, но можно взять популярные опенсорсные проекты вроде tree-sitter.

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

typedef int (*fptr_t)();
fptr_t create() {
fptr_t fptr = [] { return 2; }
return fptr;
}
template <typename T>
T apply (T(*f)()) {
return f();
}

int main() {
fptr_t f = create();
apply(f); // компилируется
apply([] {return 3;}); // не компилируется
}

Можно явно указать шаблонный тип: apply<int>(...), но так мы убиваем автоматический вывод типов. А если там что-то более сложное? Можно сделать static_cast<fptr_t>. А можно сделать так:

apply(+[] {return 3; });

используя builtin T* operator+(T*). Как по мне магия какая-то)

4. Оказывается в большинстве файлов стандартной библиотеки go можно найти флаг debugMode, который по дефолту стоит false. Если ручками поменять его значение на true, начнётся дебаг вывод всякой служебной инфы. Например можно узнать, что даже при запуске пустой программы у вас создаётся два канала (один на сборщик мусора, один на что-то ещё). Это из доклада про устройство каналов.

5. C++ sucks.

6. Я человек простой: вижу Аксёнова -- ставлю лайк.
У него оказывается в целом много обзорных докладов про всякие сферы программирования. Вот тут он рассказывает про различные способы сжатия.
Мне оч понравился факт, что дельта-кодирование используется в жизни. Дефолтная задача звучит как что-то вроде есть 10^8 нулей и запросы добавить на отрезок [l; r] число x. После всех запросов вывести итоговый массив. Давайте в arr[l] добавлять x, а из arr[r+1] отнимать его. Во время вывода ответа держим текущую сумму и обновляем её из массива.
В докладе приводится пример про то, как использовать похожий подход при сжатии неубывающей последовательности чисел. Давайте вместо самой последовательности (например)

[12, 18, 19, 31, ..., 228227, 228228, 228229]

построим такую (первое оставляем, остальные заменяем на дельту относительно прошлого):

[12, 6, 1, 12, ..., 1, 1, 1]

Теперь все числа в абсолютных значения сильно меньше. Уникальных тоже стало меньше. Можно пробовать жать их более эффективно. Утверждается, что такой подход можно найти в любом более менее популярном поиске вроде гугла, яндеха, sphinx или lucene (про последние может расскажу чуть позже).

7. Крышесносный факт (для меня точно). Существуют не только enum-классы, а и enum-структуры:

enum struct A {asd};

Которые вообще ничем не отличаются.

#cpp #common и может #algo

Вроде как знание о векторах в плюсах довольно тривиальное, но тем не менее.

Общеизвестный факт, что вектор это по факту такая структурка:

template <typename T>
struct vector {
T* data;
int size, capacity;
}

Кажется, сделать динамический массив меньшими усилиями ну никак нельзя. В самописных версиях иногда вместо двух чиселок также хранят указатели, а size/capacity вычисляют каждый раз. Можно упороться и хранить их в одной int64 переменной: первые 4 байта на размер, вторые на вместимость. А можно вообще не хранить размер, а сделать ваш вектор нуль-терминированным и считать длину ручками каждый раз. Раз в k случаев такое тоже работает хорошо.

Стандартная библиотека предлагает для кастомизации своего вектора подсунуть свой аллокатор вторым шаблонным аргументом. И всё. Больше пользователю ничего не надо. Но ведь есть ещё такая важная характеристика как resize policy -- то, как ваш вектор изменяет свой размер. Как много выделить в первой аллокации? 1, 2, 8? С единицы начинать плохо: после первого push_back почти наверняка придёт второй. С восьми тоже плохо: может у нас вектор объектов, каждый из которых 3Мб, а юзать мы хотим всего для трёх элементов. Да и для двойки свой кейс можно придумать.

Теперь про изменение этого размера. В clang довольно дефолтная схема с умножением на 2 (с оговорками). Но есть ощущение, что умножение на 2 оч плохое решение. Точнее, умножение на любую константу плохо. Когда речь идёт о расширении 8->16, это вполне себе хорошее решение (или нет?🧐без знания размера объектов непонятно). Но когда у вас уже 1кк элементов и вы хотите положить ещё пару штук, расширение 1кк->2кк выглядит как из пушки по воробьям.

И что делать?

Как вариант не расти всегда с одинаковой скоростью. Можно смотреть на текущее кол-во элементов. Можно на занимаемую память. И после выбора какой-то границы, расти в 2 раза до неё и в 1.2 после (понятно что тут стоит покрутить и найти компромисс между занимаемой памятью и временем работы в зависимости от ваших данных и паттерна работы с ними). В go в этом плане примерно так и сделано.

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

В студвекторе из подобного есть метод shrink_to_fit, который уменьшает вместимость до размера. Прошу заметить, что метод этот non-binding, i.e. необязательный. Тут авторы вольны делать что хотят. В clang честно пытаются уменьшиться.

Учитывая, что resize policy это что-то, что нельзя описать одним числом, интересно попробовать придумать, как это могло бы выглядеть в стандартной библиотеке. Что-то такое:

template <
typename T,
typename Allocator = ... ,
template <typename T> Recap = std::twice>
class vector;

где Recap может выглядеть как что-то вроде

template <typename T>
size_t MyRecap(size_t sz, size_t cp) {
if (sz * 4 < cp) { return sz; }
if (cp * sizeof(T) > 10 * kBytesInMB) {
return cp * 1.2;
}
return cp * 2;
}

Понятно, что всё это можно делать и сейчас, вычисляя новый размер/капасити снаружи и используя resize/reserve, но менеджерить размеры не изнутри как неестественно.

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

Можно ещё писать контейнеры кусками (вроде дека), чтобы немножко получше жить с аллокациями. Или пробовать хранить мало данных на стеке, прям как sso.

Зачем это всё? А хер его знает. Почти наверняка на практике это вам не пригодится, потому что если вам не хватает std::vector, то у вас уже либо все остальные проблемы с производительностью решены, либо очень специфическая задача. Но знать полезно.

Такие дела.

#common #python

Не знаю, насколько вам заходит читать про сборщики мусора, но осталось совсем чуть-чуть : )

Собсна python GC.

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

Всего тут три поколения, для которых можно задавать границы того, сколько сборок мусора должен пережить объект, чтобы переместиться в следующее поколение.
Для разрешения циклов используется факт, что циклы могут возникнуть лишь при использовании различных контейнеров. Для каждого объекта внутри контейнера производится следующая операция: для всех объектов внутри этого контейнера, на которые ссылается зафиксированный объект, количество ссылок уменьшается на 1. Для всех объектов, счётчик ссылок которых остался больше 1, считается, что на них ссылаются объекты снаружи контейнера. Эти объекты кикаем из множества кандидатов на удаление. Также убираем из этого множества все объекты, на которые ссылаются только что убраные и т.д. Оставшиеся во множестве объекты можно удалять.

Подобный подход встречается и в других языках.
Например, в Kotlin/Native (это не обычный котлин, прошу заметить) такой выбор был сделан из-за простоты метода. Однако недавно от подсчёта ссылок решили отказаться, потому что с ним не получается достигнуть достаточной эффективности.

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

Другой интерпретатор python PyPy имеет cборщик мусора с другой моделью поведения. Incminimark -- инкрементальный трассирующий сборщик мусора с двумя поколениями. Основная настройка -- размер молодого поколения (nursery).
Большие объекты создаётся вне поколений.

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

И CPython, и PyPy предоставляют множество возможностей для полуавтоматического управления сборкой мусора. Есть возможности вручную запускать отдельные минорные/мажорные сборки, временно включать/отключать сборщик мусора,
получать подробную информацию о поведении программы при сборке и т.д.

[1]. Как Instagram отключил gc и получил профит.
[2]. Потом что-то покрутили и вернули.

#algo

Хеш-таблицы 1/2.

1. load factor.
Часто говорят, что важно следить за ним. Ведутся жоские споры (у агрошкольников) о том, какие значения норм, а какие нет. В умных книжках часто пишут, что норм 0.5-0.7. В жизни вам может зайти и 0.99, и может больше единицы, и в районе 0.005. Важно понимать, что важен не сам LF, а средняя глубина поиска. Потому что у вас есть коллизии, которые в одном бакете делают 10 элементов, когда вся таблица на 100. Вроде LF 0.1, а работает медленно. И есть удаления. Которые например при открытой адресации просто помечают элементы удалёнными, не ускоряя поиск. Короче за этим надо следить (в случае открытой адресации видимо вас ждут k костылей, в случае закрытой можно считать LF как максимальное кол-во элементов в бакете делить на размер таблицы).

2. Хеш-функция.
Легко можно выбрать хеш-функцию, посмотрев на её бенчмарки (которые где-то там делали авторы и она всё и вся разносит). Но очевидно, что не будет понятно норм/нет, пока вы не померяете на ваших данных. Ну это ладно. Это известный тезис.
А вот какую выбрать? Может я коллизий поменьше хочу. Тогда может что-то из sha-2 или md5? У них, говорят, коллизий мало. Вон они по 128+ бит хеши выдают. ... А ключи же у нас в районе 64х. Получается надо обрезать. И тут уже ничего не понятно, норм оно будет или нет. Ещё и считается долго. Долго это плохо. Надо помнить, что хеш-функция это на каждую операцию. Потому может лучше "плохо" и быстро с помощью crc32, DJB или fnv (главное чтобы не LoseLose). Хотя можно что-то среднее: SuperFastHash, Murmur, CityHash или Robin-hood (или Hopscotch). Вообще про тему скорости хеш-функций можно вспомнить SMHasher, который считает, сколько функция умеет хешировать в секунду и ещё какие-то характеристики. Но тут тоже стоит помнить, что неважно, сколько она хеширует в секунду, если вы собираетесь её юзать для восьмисимвольных строк (надо мерять).
Бывают ли идеальные хеши? Да! Но надо бы знать ключи заранее и делать предпосчёт, зато юзается быстро и без коллизий :) Тут можно взглянуть на gperf и cmph.
Можно вообще выбрать какое-то семейство функций, и время от времени брать функцию из него.

3. Размер.
Можно зафиксировать вашу таблицу на всю жизнь (и жить с открытой адресацией):

std::pair<K, V> data[1024];

Но что-то подсказывает, что такого хватит ненадолго (хотя мб и хватит). Стандартный путь это как вектор (просто элементов для открытой адресации или например листов для закрытой): реаллокация в k раз, чтобы LF получше стал. Как выбирать k смотрите два поста назад. Можно размеры только степенями двойки. Или можно делать статику снаружи и динамику внутри:

std::vector<std::pair<K, V>> data[1024];

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

4. Ключи.
Иногда нужно хранить какую-то мету, само значение (для сравнений каких-нибудь) или значение хеша. В зависимости от того, насколько много занимает ваша структурка, можно выбирать, хранить например всё в одном массивчике или может ключи/значения отдельно, чтобы в кеши хорошо попадало что надо. Тут конечно всё зависит от вашего паттерна доступа.
Кстати забавно, что если объект жирный, можно попробовать хранить первые k байт его представления и сравнивать их. Или можно вообще не сравнивать изначальные ключи с одинаковыми значениями хеша, если вы уверены в хеш-функции или готовы иногда ошибаться.

#algo

Хеш-таблицы 2/2.

5. Пробинг при открытой адресации.
Пробинг -- то, как вы двигаетесь по таблице в поиске свободного места. Очевидно можно линейный: offset[i] = i или i*k. Можно квадратический: offset[i] = i*i или даже alpha*i + beta*i*i. Или double hashing: offset[i] = i*hash2(key). Или cuckoo hashing (ну придумали конечно): для любого ключа проверяем две точки от двух хеш-функций; если есть место, вставляем, иначе выбираем одного из этих двух оккупантов и выселяем его, а на его место наш элемент; аналогично делаем с выселенным элементом; если такое повторяется некоторое количество раз, меняем хеш-функцию и рехеш. Прикольно, что такой приём гарантирует O(1) на поиск.

6. Доп. требования.
Иногда нужно хранить порядок вставки. Тогда давайте рядом хранить двусвязный лист, а в каждом бакете хранить итератор на начало подцепочки этого бакета в листе и размер подцепочки. Ещё кстати и перебор всех элементов за их количество.
А может ещё вы хотите на каком-то интервале читать значения, тогда вам не хеш-таблица нужна, но об этом попозже : )

7. И немного читов.
-- можно как в LRU-кеше при закрытой адресации найденный где-то в глубине листа элемент перемещать в самое начало, чтобы в следующий раз его поиск прошёл быстрее. В открытой адресации наверное тоже можно посвапать аккуратно с удалённым элементом например, но звучит как что-то, где легко споткнуться.
-- хешировать можно не просто пришедший элемент, а что угодно. Можете хешировать хеш от хеша от хеша. Или первые 8 байт объекта. Или для чисел сначала 228 добавить. Короче вертеть как хочешь, абы хорошо было.
-- вместо листа/вектора при закрытой адресации можете хранить что-то другое. В java например с какого-то момента лист превращается в bst.

[1]. Hash map analysis.
[2]. Extendible hashing.
[3]. Я написал самую быструю хеш-таблицу.
[4]. Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step [видео].
[5]. О хеш-таблицах в Clickhouse [видео].