Откуда spurious wakeup на кондваре?
#опытным

У кондваров есть метод std::condition_variable::wait, который по документации блокирует исполнение потока до тех пор, пока не придет уведомление или не произойдет тн spurious wakeup(ложное пробуждение). Поэтому нам говорят, что нужно ставить wait в цикл while:

while (!pred()) 
    cv.wait(lock);

или использовать перегрузку, передавая в кондвар предикат:

cv.wait(lock, pred);

Но что это за такие ложные пробуждения, из-за которых на нужно крутиться в цикле?

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

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

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

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

Свежих версиях линукса такой ситуации уже не может быть и из pthread'ной функции ожидания cv управление не вернется в юзерспейс при отправке любых сигналов.

Но наследие осталось.

👉🏿 А вот тут уже реальная проблема с race condition. Поток реально получил сигнал на пробуждение, проснулся, начал выполняться и увидел, что условие ложно. Потому что по сути какой-то другой поток уже успел обработать появившееся событие. Это может произойти по многим причинам, но может быть вот такая ситуация:

1. Поток A спит на cond_wait.
2. Поток B меняет условие и вызывает notify_one.
3. Поток A просыпается, но ещё не запланирован шедулером.
4. Поток C успевает изменить условие обратно (забрал задачу из очереди, сбросил флаг).
5. Поток A наконец получает процессор, проверяет условие — оно false. Это называется stolen wakeup

или такая

1. Поток A спит на cond_wait.
2. Поток B меняет условие и вызывает notify_one.
3. Поток A просыпается, но ещё не запланирован шедулером.
4. Поток B успевает изменить условие еще раз(или несколько).
5. Поток A наконец получает процессор, проверяет условие — оно false. То есть событие было фактически потеряно.

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

Спасибо, @mike_hd, за вопрос в чате и идею для поста. И всем комментаторам, вовлекшимся в обсуждение, за предоставление фактуры по вопросу.

Don't get stolen. Stay cool.

#concurrency

​​Где-то баг...
#опытным

Вот вам код:

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;
}

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

Напишите в комментах.

Prevent bugs. Stay cool.

​​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

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

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

bool math = -1 < 1U;

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

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

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

#ЧЗХ ?

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

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

Mix things consciously. Stay cool

#cppcore

​​Что внутри 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

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

Концепция блокировок уходит далеко за пределы языковых примитивов синхронизации. Блокировки актуальны в принципе для любых систем, с которыми можно работать конкурентно. И идейно для таких систем существует 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::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

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

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

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

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

​​Кондвар - это не брокер сообщений
#новичкам

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

И кондвар не реализует практически ничего из этого. Главная ошибка в рассуждениях -

Producer: notify_one();
Consumer: wait();

думать, что notify_one() — это сигнал, который где-то лежит и ждёт, пока потребитель вызовет wait().

Если нотификация произошла до вызова wait, то она безвозвратно потеряется.

Для многих это очевидно, но этот факт смещает акценты при проектировании протокола синхронизации.

Условно: пусть рядом с вашей дверью находится ваш почтовый ящик.

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

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

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

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

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

Так и в программе. Точка синхронизации - это разделяемое состояние, которое изменяет продюсер и читает консюмер. Сам кондвар - это средство предотвращения постоянной проверки.

Он не несет в себе никакой другой полезной информации, кроме "что-то произошло, но возможно и нет". Вся полезная информация - в разделяемом состоянии.

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

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

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

✅ Остановка обработки всегда требует персистентного состояния stopping. Без него приказ об остановке может просто пройти мимо всех ушей обработчиков и нигде не зафиксироваться.

✅ Атомарный флаг события убирает data race, но без повторной проверки все равно вы имеете сломаный протокол:

std::atomic<bool> ready{false};

if (!ready) {
    cv.wait(lock);
}

Между проверкой if (!ready) и вызовом cv.wait(lock) другой поток может выставить ready = true и вызвать notify_one(). Consumer пропустит уведомление и уснёт.

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

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

Synchronize better. Stay cool.

#concurrency

​​Напишите в комментариях самые запоминающиеся/интересные/сложные вопросы/задачи по С++ с интервью, которые вы проходили.

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

Я начну. Написать потокобезопасную очередь с приоритетом.

Приоритета всего 3.

Количество тасок с 1 и 2 приоритетом в очереди ограничено, с наименьшим приоритетом - неограничено.

При попытке вставить в очередь слишком много задач 1 или 2 приоритета, этот метод блочится.

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

Practice interview. Stay cool.

Экскурсия по лабораториям YADRO: как тестируют серверы и телеком-оборудование

В ноябре и декабре YADRO проводит экскурсии по своим лабораториям в Санкт-Петербурге и Москве.

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

📍Санкт-Петербург — 12 ноября и 1 декабря
📍Москва — 17 ноября и 8 декабря
Сбор гостей в 18:30, старт в 19:00.

Экскурсия занимает до двух часов. Участие бесплатное — нужно зарегистрироваться и дождаться подтверждения от организаторов. Возраст участников — от 18 лет.

Зарегистрироваться

Реклама. ООО "КНС ГРУПП". ИНН 7701411241. erid: 2W5zFGVnpQA

​​С++26. Или все-таки 27?

Немного с опозданием, но новость все-таки на канале. Черновик С++26 не удалось утвердить с первого раза на этапе голосования национальных органов ISO. Фактически, принятие С++26 отложено на неопределенный срок.

Почему так?

Причиной скорее всего являются контракты. По сути, это возможность писать что-то вроде int divide(int a, int b) pre(b != 0) { ... }, где pre — это контракт, проверяемый во время выполнения или компиляции. В общем, это какие-то пред и/или постусловия, которым должны удовлетворять функции.

Вроде идея-то классная. Но ее дизайн в стандарте оказался не очень удачным.

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

По поводу контрактов были ожесточенные дискуссии и в драфте С++26 был скорее некий MVP контрактов, нежели полноценная функциональность.

Бьерн же сказал, что «это не минимально жизнеспособный продукт. Это не минимально и не жизнеспособно», и что контракты добавляют сложность «очень неясными способами», меняя смысл кода в зависимости от контекста.

Если кому очень интересно, то вот и вот две бумаги от Бьерна и его коллег, критикующих контракты.

Там критика и по функционалу(очень сложно, описание примерно в 56 страниц текста), и по перформансу(не zero-cost) и по процедуре внедрения в драфт стандарта.

Тем не менее Страуструп и соавторы не против идеи контрактов как таковой. Они против конкретного неудачного дизайна из черновика С++26. В качестве альтернативы они предлагают:

👉🏿 Признать контракты просто отладочным инструментом, а не функцией безопасности.

👉🏿 Использовать гораздо более простой и мощный библиотечный дизайн, который уже реализован, протестирован и совместим (ссылаются на D4324R0 / P4324R0 — "C++ Design By Contract: Minimum Language, Maximum Library").

👉🏿 Вместо огромного и неполного языкового механизма сделать ставку на hardened standard libraries (ужесточенные стандартные библиотеки) с минимальными накладными расходами (замерено ~0.3% в production у Google) и статический анализ через C++ Core Guidelines.

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

Пишите в комментариях, что думаете по поводу контрактов и ситуации вокруг провала С++26.

Ставьте ⚡️, если поддерживаете слоняру-Бьерна.
Ставьте🗿, если достали эти деды, не дают языку стать безопаснее.

See opportunities in failures. Stay cool.

​​LRU-кэш на собеседовании
#опытным

LRU (Least Recently Used) - классический вопрос на собеседованиях. Вроде не чистый литкоды, можно и ООП пописать, и помикроархитектурить. Но тем не менее задача проверяет знание алгоритмов и структур данных применительно к реально используемой штуке.

Требования к задаче:

👉🏿 Реализовать LRU-кэш с фиксированной ёмкостью, задаваемой в конструкторе.

👉🏿 Операции get(key) и put(key, value) должны работать за O(1) в среднем.

👉🏿 При переполнении удаляется самый редкоиспользованный элемент.

👉🏿 get возвращает ссылку на значение значение, если ключ есть, иначе - сигнал об отсутствии.

👉🏿 нет требований на потокобезопасность.

Типичное решение, безо всяких ухищрений: двусвязный список (std::list) для порядка использования + хеш-таблица (std::unordered_map) для доступа по ключу.

template<typename Key, typename Value>
class LRUCache {
public:
    using value_type = std::pair<Key, Value>;
    using list_type = std::list<value_type>;
    using list_iterator = typename list_type::iterator;
    using map_type = std::unordered_map<Key, list_iterator>;

    explicit LRUCache(size_t capacity) : cap_(capacity) {
        if (cap_ == 0) throw std::invalid_argument("Capacity must be > 0");
    }

    std::optional<std::reference_wrapper<const Value>> get(const Key& key) {
        auto it = idx_.find(key);
        if (it == idx_.end()) return std::nullopt;
        entries_.splice(entries_.begin(), entries_, it->second);
        return std::cref(it->second->second);
    }

    void put(const Key& key, Value value) {
        auto it = idx_.find(key);
        if (it != idx_.end()) {
            it->second->second = std::move(value);
            entries_.splice(entries_.begin(), entries_, it->second);
            return;
        }
        if (entries_.size() == cap_) {
            const Key& k_evict = entries_.back().first;
            idx_.erase(k_evict);
            entries_.pop_back();
        }
        entries_.emplace_front(key, std::move(value));
        idx_.emplace(key, entries_.begin());
    }

    bool contains(const Key& key) const {
        return idx_.find(key) != idx_.end();
    }

    size_t size() const { return entries_.size(); }
    size_t capacity() const { return cap_; }

private:
    size_t cap_;
    list_type entries_;
    std::unordered_map<Key, list_iterator> idx_;
};

Разберём ключевые моменты:

Очевидно, что нам нужен ассоциативный контейнер, работающий за O(1). Из стандартного это std::unordered_map. Получим просто key-value хранилище.

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

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

Осталось только корректно это все подружить друг с другом и получится рабочее решение. Можно поиграться на годболте.

Тут есть потенциал для оптимизаций (например кэш локалити при использовании std::list), это не продовое решение. Но для собеседования это решение базово удовлетворяет всем требованиям.

Good luck with interviews. Stay cool.

#interview #algorithms