Грокаем C++

new vs malloc

Чем отличаются new и malloc? Один из популярных вопросов на собеседованиях, которые проверяет, насколько хорошо вы знакомы с тонкостями работы с памятью в С/С++. Поэтому давайте сегодня это обсудим.

Не совсем корректно, наверное сравнивать фичи двух разных языков с разными доминантными парадигмами программирования. Но раз в стандарте есть std::malloc, а new тоже выделяет память, то можно попробовать.

👉🏿 new expression помимо аллокации памяти вызывает конструктор объекта. std::malloc только выделяет память.

👉🏿 std::malloc - совсем не типобезопасный. Он возвращает void * без какого-либо признака типа. Придется явно кастовать результат к нужному типу. new в свою очередь возвращает типизированный указатель.

👉🏿 При ошибке выделения памяти new бросает исключение std::bad_alloc, в то время как std::malloc возвращает NULL. Соответственно нужны разные способы обработки ошибочных ситуаций.

👉🏿 Поведение new может быть переопределено внутри кастомных классов, поведение std::malloc - неизменно.

👉🏿 Если вам не нужно конструирование объекта, то просто вызывайте operator new. Он делает то же самое, что и std::malloc(потенциально вызывает его внутри себя).

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

👉🏿 new плохо работает с реаллокациями. Нужно выделить новый сторадж, скопировать туда данные и вызвать delete. В то время, как malloc имеет функцию-партнера realloc, которая может изменить размер существующего куска памяти более эффективно, чем последовательность new-memcpy-delete.

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

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

Control your memory. Stay cool.

#cppcore #interview #memory

Все грани new
#опытным

Не каждый знает, что в плюсах new - это как медаль, только лучше. У медали 2 стороны, а у new целых 3!

Сейчас со всем разберемся.

То, что наиболее часто используется, называется new expression. Это выражение делает 2 вещи последовательно: пытается в начале выделить подходящий объем памяти, а потом пытается сконструировать либо один объект, либо массив объектов в уже аллоцированной памяти. Возвращает либо указатель на объект, либо указатель на начало массива.

Выглядит оно так:

 // creates dynamic object of type int with value equal to 42
int* p_triv = new int(42);
 // created an array of 42 dynamic objects of type int with values equal to zero
int* p_triv_arr = new int[42];

struct String {std::string str};

 // creates dynamic object of custom type String using aggregate initialization
String* p_obj = new String{"qwerty"};
 // created an array of 5 dynamic objects of custom type String with default initialization
String* p_obj = new String[5];

Эта штука делает 2 дела одновременно. А что, если мне не нужно выполнять сразу 2 этапа? Что, если мне нужна только аллокация памяти?

За это отвечает operator new. Это оператор делает примерно то же самое, что и malloc. То есть выделяет кусок памяти заданного размера. Выражение new именно этот оператор и вызывает, когда ему нужно выделить память. Но его можно вызвать и как обычную функцию, а также перегружать для конкретного класса:

// class-specific allocation functions
struct X
{
    static void* operator new(std::size_t count)
    {
        std::cout << "custom new for size " << count << '\n';
        // explicit call to operator new
        return ::operator new(count);
    }
 
    static void* operator new[](std::size_t count)
    {
        std::cout << "custom new[] for size " << count << '\n';
        return ::operator new;
    }
};
 
int main()
{
    X* p1 = new X;
    delete p1;
    X* p2 = new X[10];
    delete[] p2;
}

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

Для этого есть placement new. Это тот же самый new expression, только для этого есть свой синтаксис. Сразу после new в скобках вы передаете указатель на область памяти, достаточной для создания объекта.

alignas(T) unsigned char buf[sizeof(T)];
// after new in parentheses we specified location of future object
T* tptr = new(buf) T; 
// You must manually call the object's destructor
tptr->~T(); 

В этом случае кстати вызывается специальная перегрузка operator new:

void* operator new  (std::size_t count, void* ptr);

Однако она не делает ничего полезного и просто возвращает второй аргумент наружу.

Вот так по разному в С++ можно использовать new. Главное - не запутаться!

Have a lot of sides. Stay cool.

#cppcore #memory

​​Неинициализированные переменные

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

Кейс из ревью.

Вот у вас есть примерно такая функция и примерно так ее можно вызвать:

std::optional<SomeType> WaitForSomething(bool& success) {
  SomeType result;
  if (!SomeOperation()) {
    // error
    return std::nullopt;
  }
  if (condition) {
    //fill result
  }
  success = (condition == 1);
  return result;
}

bool success;
auto obj = WaitForSomething(success);
if (!obj) {
  // handle error
}
if (success) {
  // do something
}

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

Здесь success заполняется всегда вне зависимости, наступит условие или нет. И вроде как очень безопасно туда передать неинициализированный bool. Какая же разница? success в любом случае инициализируется в функции.

А вот приходит другой программист и изменяет эту функцию примерно так:

std::optional<SomeType> WaitForSomething(bool& success) {
  SomeType result;
  if (!SomeOperation()) {
    // error
    return std::nullopt;
  }
  while (condition1 && condition2) {
    //fill result
    if (condition3)
      success = true;
  }
  return result;
}

По логике реального кода было все четко. Кроме того, что теперь в ветке, где не выполняются одновременно condition1, condition2 и condition3 success остается тем же, что и передали в функцию.

Так конечно не нужно делать. Это хоть чуть-чуть, но изменяет логику поведения функции. Но я хочу тут другой момент затронуть.

Теперь при передаче неинициализированной success результат функции может быть дефолтовым, а success == true, так как в него изначально был записан true.

В реальности привело к довольно долгому дебагу.

Но если бы изначально мы создавали бы инициализированную в ложь переменную

bool success = false;

то этой боли можно было бы избежать. А изменение функциональности самой функции выявят тесты.

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

Define your value. Stay cool.

#cppcore #goodpractice

​​Почему приватные методы находятся в описании класса?

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

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

Ну а приватные-то методы зачем раскрывать? Зачем их помещать внутрь класса и делать видимыми для клиентского кода?

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

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

А во-вторых, оказывается в С++ приватные методы участвуют в разрешении перегрузок(внезапно). В целом, так оно и должно быть. Никто не мешает вам определить публичный метод и перегрузить его приватным методом. Проблема(или фича) в том, что этап разрешения перегрузок стоит перед проверкой модификатора доступа. То есть даже если метод приватный и его никто не должен увидеть, он все равно участвует в разрешении перегрузок наряду со всеми остальными методами. Поэтому каждый клиент должен видеть полный набор приватных методов. Об этом мы уже говорили в контексте pimpl идиомы.

В чем прикол того, что приватные методы участвуют в разрешении перегрузок?

Давайте снова представим, что такого правила нет. И вот у нас есть две перегрузки, одна приватная для double, другая публичная для int. И перегрузка с double всегда отбрасывалась бы только лишь по причине того, что она приватная. Тогда мы легко можем вызвать публичную функцию с дробным числом 1.5 и нам ничего не будет. Оно просто неявно приведется к int и все на этом.

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

Однако, такой протокол поведения влечет за собой различные сайд-эффекты.

struct DumbClass {
    void DumbFunction(int param) {
        // i do nothing because i’m dumb
    }
private:
    void DumbFunction(double param) = delete;
};

int main() {
    DumbClass{}.DumbFunction(1.0);
}
// error: use of deleted function ‘void DumbClass::DumbFunction(double)’

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

Stay aware. Stay cool.
#design #howitworks #cppcore #hardcore

​​Как вызвать методы класса напрямую через vtable?
#опытным

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

Полиморфизм - там штука, которая сделала ООП и ОО дизайн такими мощными и широкоиспользуемыми инструментами. За счет чего он реализован в С++?

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

struct Base {
    virtual void func1() {
        std::cout << i+1<< std::endl;
    }
    virtual void func2() {
        std::cout << i+2 << std::endl;
    }
};

struct Derived: Base {
    void func1() override {
        std::cout << i+3 << std::endl;
    }
    void func2() override {
        std::cout << i+4 << std::endl;
    }
};

int main() {
    auto basePtr = std::unique_ptr<Base>(new Derived);
    uint64_t ** pVtable = (uint64_t **)basePtr.get();
    printf("Vtable: %p\n", pVtable);
    printf("First Entry of VTable: %p\n", (void*)pVtable[0][0]);
    printf("Second Entry of VTable: %p\n", (void*)pVtable[0][1]);

    using VoidFunc = void (*) (void*);
    VoidFunc firstMethod = (VoidFunc) pVtable[0][0];
    firstMethod(basePtr.get());
    VoidFunc secondMethod = (VoidFunc) pVtable[0][1];
    secondMethod(basePtr.get());
}

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

Далее нужно найти указатель на vtable. Обычно он всегда лежит в первых 8 байтах объектов полиморфных классов. Так как у нас двухуровневая косвенность (указатель на объект, а в нем указатель на таблицу), мы объявляем двойной указатель на 8-мибайтный инт и он и будет нашим vtable_ptr. Почему uint64_t? Да на самом деле косвенность трехуровненая, потому что в ячейках vtable лежат указатели на методы, а указатель легко представить в виде 8-байтного числа.

Самое сложное позади, мы нашли все, что нужно. Осталось только кастануть инты, лежащие в ячейках vtable к указателям на функцию правильного типа. И вуаля. Готово. Возможный вывод:

Vtable: 0x5a7841237eb0
First Entry of VTable: 0x5a781fd28ae2
Second Entry of VTable: 0x5a781fd28b22
3
4

Где это знание нужно?

Ну вообще в принципе неплохо разбираться в том, как работает полиморфизм в С++. У всего есть свои особенности и в какой-то необычной ситуации эти знания вам могут помочь пофиксить багу.

Знание внутреннего устройства инструмента позволить вам понимать его преимущества и недостатки. Возможно в проектах с высокими требованиями к производительности(слабое железо как в embedded или супер-ультра-гипер low latency как в hft), вам предстоит выбирать между динамическим полиморфизмом и статическим полиморфизмом aka шаблонами. Чтобы сделать выбор качественно и аргументировать его, нужно знание базы.

А как говорится, пока сам не потрогаешь ручками - не поймешь.

Только не нужно так писать в продовом коде! А то будет, как на картинке внизу.

Stay hardwared. Stay cool.

​​No new line

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

Небольшой пример:

Файлик foo.hpp:

// I love code
// I love C++<no newline>

Файлик bar.cpp:

#include "foo.hpp"
#include "baz.hpp"

А теперь вспоминаем, что препроцессор вставляет все содержимое хэдера на место инклюда И(!) не вставляет после него символ конца строки. То есть спокойно может получится следующее:

// I love code
// I love C++#include "baz.hpp"

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

Стандарт нам говорит:

... If a source file that is not empty does not end in a new-line character,
 or ends in a new-line character immediately preceded by a backslash
 character before any such splicing takes place, the behavior is undefined.

Так что ub без кода - вполне существующая вещь.

Или уже нет?

На самом деле приведенная цитата была из стандарта 2003 года.

С++11 пофиксил эту проблему и обязал препроцессоры вставлять new line в конце подключаемых файлов:

A source file that is not empty and that does not end in a new-line character, 
or that ends in a new-line character immediately preceded by a backslash 
character before any such splicing takes place, shall be processed 
as if an additional new-line character were appended to the file.

Так что теперь проблемы нет.

Решил написать об этом, просто потому что очень весело, что в плюсах можно было такими неочевидными способами отстрелить себе конечность.

Ну и хорошо, что стандарт все-таки не только новую функциональность вводит, а фиксит вот такие вот недоразумения.

Fix your flaws. Stay cool.

#compiler

​​Дедлокаем один поток
#опытным

Мы привыкли, что для дедлоков нужно несколько потоков. Не удивительно. Давайте прочитаем определение дедлока по Коффману. Там речь про процессы, но если поменять слово "процесс" на "поток" ничего не изменится. Ну и перевод будет вольный.

Дедлок - это ситуация в коде, когда одновременно выполняются все следующие условия:

А ну, мальчики, играем поочереди. Только один поток может получить доступ к ресурсу в один момент времени.

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

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

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

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

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

Определение оперирует общим термином ресурс. И не учитывает поведение конкретного ресурса и деталей его реализации. А они важны!

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

std::mutex mtx;
mtx.lock();
mtx.lock();

Стандарт говорит, что будет UB. То есть поведение программы неопределено, возможно она заставит Ким Чен Ира спеть гангам стайл.

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

1️⃣ Компилятор имплементировал умный мьютекс, который может задетектить double lock и, например, кинуть в этом случае исключение.

2️⃣ Мьютекс у нас обычный, подтуповатый и он делает ровно то, что ему говорят. А именно пытается залочить мьютекс. Конечно у него ничего не получится и он вечно будет ждать его освобождения. Результат такого сценария - дедлок одного потока одним мьютексом!

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

Be self-sufficient. Stay cool.

#concurrency #cppcore #compiler

Ответ
#опытным

Правильный ответ на квиз из предыдущего поста- 0. Вообще ни одного мьютекса не нужно.
Много можно вариантов придумать. И даже в комментах написали несколько рабочих способов.

Вообще говоря, в определении дедлока не звучит слово "мьютекс". Потоки должны ждать освобождения ресурсов. А этими ресурсами может быть что угодно.
Для организации дедлока достаточно просто, чтобы 2 потока запустились в попытке присоединить друг друга. Естественно, что они будут бесконечно ждать окончания работы своего визави.

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

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

std::thread * t_ptr = nullptr;

void func1() {
  std::this_thread::sleep_for(std::chrono::seconds(1));
  t_ptr->join();
  std::cout << "Never reached this point1" << std::endl;
}

void func2(std::thread& t) {
  t.join();
  std::cout << "Never reached this point2" << std::endl;
}

int main() {
  std::thread t1{func1};
  t_ptr = new std::thread(func2, std::ref(t1));
  while(true) {
    std::this_thread::sleep_for(std::chrono::seconds(1));
  }
}

Все просто. Вводим глобальный указатель на поток. В функции первого потока мы даем время инициализировать указатель и присоединяем поток по указателю. А тем временем в main создаем динамический объект потока и записываем его по указателю t_ptr. Таким образом первый поток получает доступ ко второму. В функцию второго потока передаем объект первого потока по ссылке и присоединяем его. Обе функции после инструкции join выводят на консоль запись.

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

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

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

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

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

Stay surprised. Stay cool.

#concurrency #cppcore

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

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

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

А что если мы не будем ориентироваться на общую универсальную для всех языков теорию многопоточного программирования и сфокусируется чисто на С++ и средствах, которые он предоставляет?

Какой тогда будет ответ?

#quiz

​​Бросаем число
#новичкам

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

А что если мы попытаемся бросить что-то совсем несвязанное с иcключениями? Например, какой-нибудь тривиальный тип вроде int. Это вообще законно?

Абсолютно законно. В С++ можно бросать все, что угодно, кроме объектов неполных типов, абстрактных классов и указателей на неполный тип. Даже указатель на void можно.

Как и число.

Поймать число примерно также просто, как его бросить:

void foo() {
  throw 1;
}

int main() {
  try {
    foo();
  }
  catch(int i) {
    std::cout << i << std::endl;
  }
}

// OUTPUT: 1

Это кстати один из любимых вопросов у интервьюеров.

"А можно ли кидать число вместо исключения?"

Теперь вы с полной уверенностью ответите "можно".

Но вот зачем это может быть нужно? Оставьте ваши мысли в комментариях

Make sense. Stay cool.

#interview #cppcore

Сколько вам было лет, когда вы узнали, что название бинарного файла, который по умолчанию генерирует GCC - a.out - это сокращение от assembler output(вывод ассемблера)? 🤯

Я вот узнал в толькочтогодиков.

​​Потокобезопасный интерфейс
#новичкам

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

Возьмем максимально простую реализацию самой простой очереди:

struct Queue {
    void push(int value) {
        storage.push_back(value);
    }
    void pop() {
        storage.pop_front();
    }
    bool empty() {
        return storage.empty();
    }
    int& front() {
        return storage.front();
    }
private:
    std::deque<int> storage;
};

Она конечно потокоНЕбезопасная. То есть ей можно адекватно пользоваться только в рамках одного потока.

Как может выглядеть код простого консьюмера этой очереди?

while(condition)
    if (!queue.empty()) {
        auto & elem = queue.front();
        process_elem(elem);
        queue.pop();
    }

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

Бабахаем везде лок гард на один мьютекс и дело в шляпе!

struct Queue {
    void push(int value) {
        std::lock_guard lg{m};
        storage.push_back(value);
    }
    void pop() {
        std::lock_guard lg{m};
        storage.pop_front();
    }
    bool empty() {
        std::lock_guard lg{m};
        return storage.empty();
    }
    int& front() {
        std::lock_guard lg{m};
        return storage.front();
    }
private:
    std::deque<int> storage;
    std::mutex m;
};

Все доступы к очереди защищены. Но спасло ли реально это нас?

Вернемся к коду консюмера:

while(true)
    if (!queue.empty()) {
        auto & elem = queue.front();
        process_elem(elem);
        queue.pop();
  }

А вдруг у нас появится еще один консюмер? Тогда в первом из них мы можем войти условие, а в это время второй достанет последний элемент. Получается, что мы получим доступ к неинициализированной памяти в методе front.

То есть по факту в многопоточном приложении полученный стейт сущности сразу же утрачивает свою актуальность.

Что делать? Не только сами методы класса должны быть потокобезопасными. Но еще и комбинации использования этих методов тоже должны обладать таким свойством. И с данным интерфейсом это сделать просто невозможно.

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

struct ThreadSafeQueue {
    void push(int value) {
        std::lock_guard lg{m};
        storage.push_back(value);
    }
    std::optional<int> pop() {
        std::lock_guard lg{m};
        if (!storage.empty()) {
            int elem = storage.front();
            storage.pop_front();
            return elem;
        }
        return nullopt;
    }
private:
    std::deque<int> storage;
    std::mutex m;
};

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

Теперь консюмер выглядит так:

while(true) {
    auto elem = queue.pop();
    if (elem)
        process_elem(elem.value());
}

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

Stay safe. Stay cool.

#concurrency #design #goodpractice

Смешиваем std::visit и std::apply
#опытным

Подумал об интересном сочетании функций std::visit и std::apply. В прошлом посте про паттерн overload мы в цикле проходились по вектору вариантов и к каждому элементу применяли std::visit. Но прикольно было бы просто взять и за раз ко всем элементам коллекции применить std::visit. Ну как за раз. Без явного цикла.

И такую штуку можно сделать для tuple-like объектов, среди которых std::pair, std::tuple и std::array. Функция std::applyможет распаковать нам элементы этих коллекций и вызвать для них функцию, которая принимает в качестве аргументов все эти элементы по отдельности. Это же то, что нам нужно!

Давайте попробуем на примере std::array запихать все его элементы в функтор и лаконично вызвать std::visit.

template<typename ... Lambdas>
struct Visitor : Lambdas...
{
  Visitor(Lambdas... lambdas) : Lambdas(std::forward<Lambdas>(lambdas))... {}
  using Lambdas::operator()...;
};

using var_t = std::variant<int, double, std::string>;

int main(){
  std::array<var_t, 3> arr = {1.5, 42, "Hello"};
  Visitor vis{[](int arg) { std::cout << arg << ' '; },
        [](double arg) { std::cout << std::fixed << arg << ' '; },
        [](const std::string& arg) { std::cout << std::quoted(arg) << ' '; } };
  
  std::apply([&](auto&&... args){(std::visit(vis, std::forward<decltype(args)>(args)), ...);}, arr);
}

Начало в целом такое же, только теперь у нас std::array. Нам интересна последняя строчка.

В std::apply мы должны передать функтор, который может принимать любое количество параметров. Благо у нас есть вариадик лямбды, которые позволяют сделать именно это. Компилятор сам сгенерирует структуру, которая сможет принимать ровно столько аргументов, сколько элементов в массиве arr.

Дальше мы все эти аргументы распаковываем в серию вызовов std::visit так, чтобы каждый элемент массива передавался в отдельный std::visit. Естественно, все делаем по-красоте, с perfect forwarding и fold-expression на операторе запятая.

В общем, делаем себе укол пары кубиков метапрограммирования.

Выглядит клёво!

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

Look cool. Stay cool.

#template #cpp17

​​Как header only либы обходят ODR
#новичкам

В С++ есть одно очень важное правило, которое действует при компиляции и линковке программы. Это правило одного определения. Или One Definition Rule(ODR). Оно говорит о том, что во всей программе среди всех ее единиц трансляции должно быть всего одно определение сущности.

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

Тогда встает вопрос: А как тогда header-only библиотеки обходят это требование? Сами посудите, подключаем какую-нибудь json заголовочную либу, везде ее используем, линкуем программу и все как-то работает. Хотя во многих единицах трансляции есть определение одних и тех же сущностей.

В чем подвох?

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

Сами посмотрите на некоторые примеры: cereal для сериализации, nlohmann для json'ов, почти весь Boost. Там все жестко шаблонами и измазано.

А там, где шаблоны неприменимы можно использовать inline|static функции и поля класса, а также анонимные пространства имен .

В общем, в С++ есть много средств обхода ODR и ими всеми активно пользуются header-only библиотеки.

Bypass the rules. Stay cool.

#compiler #design

​​Header only либы. Pros and cons
#новичкам

Мы живем в мире С++, где почти нет ничего общепринятого. Часто даже не для очень специфичной задачи, типа сериализации, приходится искать какие-то сторонние решения и сравнивать их. Давайте отложим в сторону вопросы о качестве кода и дизайне и сконцентрируемся вот на чем. Какую библиотеку выбрать: уже скомпилированную или полностью header-only? Будем рассматривать вопрос с точки зрения header-only либ. Какие у них преимущества и недостатки?

Преимущества:

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

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

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

✅ Бо'льшая переносимость. Не все компиляторы одинаково компилируют одни и те же сущности даже на одной и той же платформе. Ваша ддлка или сошник может просто по ABI вам не подходить. Хэдэр-онли либы приходится компилировать вместе с проектом, что убирает проблему несовместимости ABI.

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

Недостатки:

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

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

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

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

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

Make the right choice. Stay cool.

int count_ones(unsigned num)
{
    num = (num & 0x5555555555555555 ) + ((num >>  1) & 0x5555555555555555 );
    num = (num & 0x3333333333333333 ) + ((num >>  2) & 0x3333333333333333 );
    num = (num & 0x0f0f0f0f0f0f0f0f ) + ((num >>  4) & 0x0f0f0f0f0f0f0f0f );
    num = (num & 0x00ff00ff00ff00ff ) + ((num >>  8) & 0x00ff00ff00ff00ff );
    num = (num & 0x0000ffff0000ffff ) + ((num >> 16) & 0x0000ffff0000ffff);
    return num;
}

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

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

Honorable mentions:
Питонисты часто в этой задаче упоминают, что они одной левой могут превратить число в бинарное представление, потом в строку и просто посчитать одной функцией количество вхождений единички. А мы вообще-то ничем не хуже! И даже лучше! Нам не нужно конвертировать бинарное представление в строку. Достаточно std::bitset и его метода count:

int count_ones(unsigned num) {
  return std::bitset<32>{num}.count();
}

Solve your problems. Stay cool.

Считаем единички. Решения

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

int count_ones(unsigned num) {
  int result = 0;
  while(num > 0) {
    result += num & 1;
    num >>= 1;
  }
  return result;
}

Алгоритмическая сложность этого решения - О(log(num)).
Что может быть интереснее? Например, знали ли вы, что выражение num & (num - 1) лишает число его самой правой единички? Посмотрите сами:

10 = 1010
1010 & (1010 - 1) = 1010 & 1001 = 1000

118 = 111011
111011 & (111011 - 1) = 111011 & 111010 = 111010

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

int count_ones(unsigned num) {
  int result = 0;
  for(; num > 0; num &= (num - 1), ++result);
  return result;
}

А что насчет самого короткого решения? Зачем писать велосипед, если можно просто воспользоваться встроенной функцией компилятора(или С++20 фичей):

int count_ones(unsigned num) {
  return std::popcount(num); 
  // or compiler extension 
  // return __builtin_popcount(num);
}

А что, если мы хотим константную сложность? Такое вообще возможно?

Конечно. Нам потребуется всего sizeof(num)* 8 итераций цикла и проверки последнего бита, чтобы найти нужное число. Константа? Да. Эффективно ли это? Это даже медленнее, чем самое первое решение.

Однако давайте подумаем еще чуть-чуть. Комбинаций битов в инте на самом деле не такой уж и и много. Всего 2^32. Можно создать массив байтов на 2^32 элементов и в каждой ячейке хранить количество единичек для числа равного индексу этой ячейки. Мы это как-то можем заранее нагенерить(или при первом вызове функции) и потом все вызовы функции count_ones будут занимать константное время. Правда памяти сожрется на это предостаточно.

static std::array<uint8_t, std::numeric_limit<uint32_t>::max()> ones;
// somehow fill array
int count_ones(unsigned num) {
  return ones[num];
}

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

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

Но чтобы было прям наглядно понятна логика, то массив можно сделать еще меньше, если брать по 4 бита(тетрад). Различных тетрадов всего 16 штук, поэтому и нужно будет всего 16 байт доп памяти и 8 итераций цикла. Спасибо, @tutralex, за решение)

int count_ones(unsigned num)
{
  static unsigned char c[16]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
  int count=0;
  while (num)
  {
    count+=c[num&0x0F];
    num>>=4;
  }
  return count;
};

В общем, вы поняли. Чем меньше массив, тем больше итераций цикла и наоборот. Выбирайте, что вам больше подходит.

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

Считаем единички
#задачки

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

Вроде бы простая и популярная задача: посчитать количество единиц в битовом представлении числа. Уверен, что большинство из вас решали эту задачу.

Однако популярный подход - не самый эффективный, элегантный и интересный.

Благо существует множество непопулярных, но очень интересных решений! О них я расскажу в завтра в ответном посте.

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

А чтобы умудренным опытом людям было немного интереснее, давайте ограничим условия. Задачу надо решить либо за константное время(в среднем), либо за наименьшее количество строчек. Выражения вне цикла for разделенные символом ; считаются разными строчками.

int count_ones(unsigned num) {
  // Here your code
}

Challenge yourself. Stay cool.