Телеграм канал «Грокаем C++»

​​Какая память быстрее: стек или куча?
#новичкам

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

Работа с памятью начинается с ее выделения. Вот у нас ничего не было и мы захотели создать объект на стеке и в куче. Что будет быстрее?

int main() {
std::vector<int> vec;
std::unique_ptr<std::vector<int>> p_vec = new std::vector<int>{};
return 0;
}

Тут ответ более менее однозначный.

Выделение/освобождение памяти происходит быстрее на стеке.

Аллокация на стеке - это просто сдвиг указателя стека на какое-то количество байт.

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

Но!

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

Стек просто заранее предвыделяется при создании потока/процесса. Он уже готовенький для использования и изолирован. Но память, которую мы получаем через new, может быть доступна другим потокам/процессам, поэтому ее надо запрашивать в общем случае через ОС, чтобы нечаянно(или чаянно) чего не натворить.

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

Be faster. Stay cool.

#base

Доступные по цене AI-подписки, да ещё и с гарантией на весь срок? В AI Market это норма

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

🤖AI Market решает эти проблемы разом. Магазин подключает официальные AI-подписки прямо на ВАШ личный аккаунт — никаких общих и «левых» аккаунтов.
☺️ Гарантия не на «первые сутки, а потом как повезёт» — на весь оплаченный срок: восстановят, заменят или вернут деньги.

💡 В магазине есть подписки на ChatGPT, Claude, Gemini, Grok, Midjourney
💳 Оплата российской картой или через СБП
⏰ Активация на ваш личный аккаунт за 5–20 минут
🆓 Нет аккаунта? Создадим бесплатно
⭐️ Не первый год на рынке подписок, знаем все нюансы

⚙️ На связи живой менеджер, а не бот: поможем, если появятся вопросы.

👉 Выбрать подписку в AI Market

​​std::atomic::wait под капотом
#опытным

В C++20 у атомиков появились wait и notify_one/all.

void atomic::wait( T old, std::memory_order order =
std::memory_order_seq_cst ) const noexcept;
void atomic::notify_one() noexcept;
void atomic::notify_all() noexcept;

Обычно атомики - это про спинлоки и горячие циклы, а тут какой-то интерфейс аля кондвар. В доке написано, что метод wait блокируется , пока не изменится значение атомика с old на новое. Но как это реализовано? Сегодня будем разбираться.

Будем смотреть на реализацию внутри линукса, на других платформах принципы схожи.

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

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

Но немного спинлока перед сном нам все равно не помешает.

И что же за такой сискол, который относительно быстро блокает тред до нотификации?

Конечно, наш уже знакомый и любимый futex. Именно этот примитив - основа для "атомарного" ожидания.

Реализация определяет примерно такую функцию ожидания и нотификации:

template<typename _Tp>
__platform_wait(const _Tp* __addr, __platform_wait_t __val) noexcept
{
auto __e = syscall (SYS_futex, static_cast<const void*>(__addr),
static_cast<int>(__futex_wait_flags::__wait_private),
__val, nullptr);
if (!__e || errno == EAGAIN)
return;
if (errno != EINTR)
__throw_system_error(errno);
}

template<typename _Tp>
void
__platform_notify(const _Tp* __addr, bool __all) noexcept
{
syscall (SYS_futex, static_cast<const void*>(__addr),
static_cast<int>(__futex_wait_flags::__wake_private),
__all ? INT_MAX : 1);
}

Если мы поверх фьютекса накрутим несколько раундов проверки в горячем цикле, то вуаля, получили std::atomic::wait

Но как всегда есть нюансы.

1️⃣ Фьютекс ассоциирован с 32-битной атомарной переменной. И конечно, такие атомики бывают, но не все они имеют такой размер.

Ну то есть в кейсе с 32-битной целочисленной атомарной переменной можно внутри ядра навесить именно на нее функции "опорной переменной" для фьютекса. Но для атомиков другой размерности нужен другой подход.

Можно было бы в каждый атомик класть 4 байта данных, с которыми будет ассоциироваться мьютекс. Но это будет слишком раздувать размер типа.

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

2️⃣ Есть же версии платформы, на которых нет futex'а. В этом случае в глобальной хэш мапе хранится мьютекс и кондвар и атомарное ожидание вырождается в ожидание на кондваре.

Итак, алгоритм ожидания выглядит так:

1. Загружаем текущее значение атомика и сравниваем с old. Если уже не равно — выходим, ждать нечего.
2. Крутимся в спин-цикле фиксированное число итераций, на каждой проверяя значение. Если изменилось — выходим. Это спасает от дорогого сискола, когда ожидание короткое.
3. Если тип атомика — скаляр размером ровно с __platform_wait_t (32 бита на Linux) и с правильным выравниванием, то futex можно повесить прямо на адрес атомика:

if constexpr (__platform_wait_uses_type<_Tp>)
__platform_wait(__addr, __old); // futex_wait на самом атомике
4. Иначе — идём в глобальную хэш-таблицу __waiter_pool, которая отображает адрес атомика на один из 16 пулов. Внутри каждого пула есть своё 32-битное слово _M_ver, на котором и будет висеть futex:

auto& __w = __waiter_pool::_S_for(__addr);
__w._M_do_wait(&__w._M_ver, __w._M_ver); // futex_wait на версии пула
5. Если платформенного wait нет вообще (экзотические платформы), в том же пуле лежат mutex и condition_variable, и ожидание вырождается в классический cv.wait(lock, pred) на версии пула.

Be efficient. Stay cool.

#concurrency #cppcore

Оптимистичные и пессимистичные блокировки
#опытным

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

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

Пусть для примера у нас будет какая-то ассоциативная структура с кучей записей. И приходит очередной запрос на изменение одной конкретной записи.

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

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

Реализацией пессимистичной блокировки в С++ является всем известный мьютекс. Он обеспечивает эксклюзивный доступ к данным:

struct Record {
int value = 0;
std::mutex mtx;
};
void update_record(Record& rec, int new_value) {
std::lock_guard<std::mutex> lock(rec.mtx);
rec.value = new_value;
}

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

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

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

Идея проста: мы не блокируем запись. Мы читаем её, запоминаем версию (или timestamp), работаем, а перед записью проверяем — не изменил ли кто-то запись, пока мы думали. Если не изменил - записываем. Если изменил - откатываемся и повторяем.

Для С++ нет отдельного примитива под это дело, потому что оптимистическая блокировка - это скорее паттерн, который надо отдельно внедрять в логику работы с данными. Но его легко собрать из std::atomic и CAS (compare-exchange):

bool try_update(Record& rec, uint64_t& old, int new_value) {
uint32_t version = uint32_t(old >> 32);
uint64_t desired = (uint64_t(version + 1) << 32)
| uint32_t(new_value);
return rec.state.compare_exchange_weak(
old, desired,
std::memory_order_relaxed, std::memory_order_relaxed);
}

void update_with_retry(Record& rec) {
uint64_t old = rec.state.load(std::memory_order_relaxed); // читаем
while (!try_update(rec, old, uint32_t(old) + 1)) { // при неудаче old уже свежий
}
}

Здесь state - это счётчик версии, который увеличивается при каждом успешном обновлении, + само значение value. Если между нашим чтением и попыткой записи кто-то другой уже обновил запись, первая часть state изменится, и compare_exchange_strong вернёт false. Тогда просто повторяем попытку.

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

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

Give guarantees. Stay cool.

#concurrency

​​Что внутри std::condition_variable?
#опытным

Более менее все знакомы с примитивом синхронизации "условная переменная". При наличии мьютекса она может погрузить поток в сон до тех пор, пока не поступит уведомлении и условие пробуждение не будет истинным. Сильно упрощая, в консюмере ждем события на wait, а в продюсере уведомляем через notify о возникновении события.

std::mutex mtx;
std::condition_variable cv;
bool ready = false;

void consumer() {
std::unique_lock lock(mtx);
cv.wait(lock, []{ return ready; }); // Wait until 'ready' is true
// Proceed with work
}
void producer() {
{
std::lock_guard<std::mutex> lock(mtx);
ready = true;
}
cv.notify_one(); // Wake up one waiting thread
}

Но как это работает под катопом?

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

Так может у кондваров и мьютексов/семафоров есть общие инструменты реализации?

Бинго!

На линуксе есть такая штука - futex. Fast Userspace muTEX. Это низкоуровневый примитив синхронизации в ядре. Главная идея: быстрый путь (захват/освобождение без конкуренции) делается в userspace обычными атомарными операциями. Ядро вызывается только когда нужно усыпить или разбудить поток.

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

Так вот кондвары и реализованы на основе такой очереди.

Конечно, нужно довольно много всего построить вокруг помещения потока в ожидание, но принцип такой.

При вызове wait поток освобождает переданный мьютекс и засыпает(вызывается условный futex_wait), помещаясь в очередь ожидания. При уведомлении (вызов futex_wake) о наступлении условия поток достается из очереди, будится и конкурирует за захват мьютекса, чтобы честно проверить верность условия(может быть stolen wakeup и поток обратно уйдет спать).

Прямым аналогом futex в Windows является семейство функций WaitOnAddress и WakeByAddressSingle/WakeByAddressAll.

Don't busy wait. Stay cool.

#concurrency #OS

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

Как вы думаете, результат выражения:

bool math = -1 < 1U;

будет правдой или ложью?

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

Но С++ выкидывает ее в мусор и по итогу math == false.

#ЧЗХ ?

Вместо того, чтобы приводить беззнаковое число к знаковому, С++ делает наоборот. В итоге -1 должен конвертироваться в неотрицательное число. В дополненном коде -1 это 0xFFFFFFFF ака все единички, поэтому при касте к беззнаковому числу оно просто становится UINT32_MAX. И оно конечно больше 1.

Выход тут один. Не сравнивать знаковые и беззнаковые числа в одном выражении. Включайте -Wall -Werror и получите ошибку компиляции. После исправления арифметика будет работать как ожидается.

Mix things consciously. Stay cool

#cppcore

​​Strict weak ordering
#опытным

На первый взгляд, всё выглядит рабочим: мы создаём 40 заказов с одинаковой ценой 100 и уникальными id, затем сортируем по возрастанию цены, используя <=. Программа компилируется и даже выполняется без ошибок… пока не достигнет определённого размера. Тогда она падает с segmentation fault.

struct Order {
int price;
int id;
};

int main() {
std::vector<Order> book;
for (int i = 0; i < 40; ++i) {
book.push_back({100, i});
}
std::sort(book.begin(), book.end(),
[](const Order& a, const Order& b) {
return a.price <= b.price;
});
std::cout << "book.size() = " << book.size() << '\n';

return 0;
}

Но почему так? Мы же вообще ничего криминального не делали, а получили UB.

Баг на самом деле в том, что компаратор не удовлетворяет требованию strict weak ordering. Конкретно проблема в иррефлексивности компаратора. Для любых двух элементов с одинаковой ценой (в нашем случае все цены равны 100) компаратор возвращает true в обе стороны:

- comp(a, b) = 100 <= 100 → true
- comp(b, a) = 100 <= 100 → true


Это означает, что comp(a,a) тоже true (так как 100 <= 100). Согласно стандарту, компаратор должен возвращать false для сравнения объекта с самим собой. Это и есть требование иррефлексивности. Нарушение этого правила приводит к тому, что алгоритм сортировки некорректно сравнивает одинаковые элементы и по итогу входит за границы последовательности

Ну окей. "А почему эффекты проявляются только после определенного размера последовательности?"

Потому что реализация std::sort в стандартной библиотеке обычно использует интроспективную сортировку (introsort), которая выбирает стратегию в зависимости от размера диапазона:

1️⃣ Для малых подмассивов (обычно < 16 элементов) используется сортировка вставками (insertion sort). На каждом шаге работы эта сортировка проходится по всем предыдущим элементам и меняет текущий, если компаратор возвращает true. Есть четкая граница остановки - первый элемент. Поэтому даже если компаратор будет возвращать true для одинаковых элементов, то это приведет лишь к лишним обменам элементов.

2️⃣ Для больших диапазонов introsort переключается на быструю сортировку (quicksort) с разбиением (partitioning) вокруг опорного элемента (pivot).

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

while (comp(*left, pivot)) ++left; // пока левый < pivot
while (comp(pivot, *right)) --right; // пока pivot < правый

Если comp использует <=, то для равных элементов оба условия вернут true:

- comp(*left, pivot) вернёт true (если *left == pivot, то pivot <= pivot → true)
- comp(pivot, *right) тоже true (если *right == pivot).

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

Решение тут простое и даже есть соответствующая мемная паста на кодфосес. "Компаратор в С++ должен возвращать false, если аргументы равны". Или в нашем примере:

std::sort(book.begin(), book.end(),
[](const Order& a, const Order& b) {
return a.price < b.price;
});

Reflect on your life. Stay cool.

#STL