Как работает dynamic_cast? RTTI!
#опытным #fun

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

Как мы видели ранее, для полиморфных объектов существует специальный оператор dynamic_cast. Стандарт не регламентирует его реализацию, но чаще всего, для работы требуется дополнительная информация о типе полиморфного объекта RTTI (Run Time Type Information). Посмотреть эту структуру можно с помощью оператора typeid:

cpp
const auto &RTTI = typeid(object);

Обратите внимание, typeid возвращает read-only ссылку на объект std::type_info, т.к. эту область памяти нельзя изменять — она была сгенерирована компилятором на этапе компиляции.

Содержимое RTTI зависит от компилятора, но как минимум там хранится hash полиморфного класса и его имя, которые доступны из std::type_info. Маловероятно, что вам на этом потребуется построить какую-то логику приложения, но эта штука могла бы быть вам полезна при отладке / подсчёте статистики и т.д.

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

Как же нам найти начало объекта RTTI? Не боги горшки обжигают, есть просто специальный указатель, который расположен прямо перед началом таблицы виртуальных методов. Он и ведёт к объекту RTTI:

┌-─|   ptr to RTTI  |   vtable pointer
|  |----------------| <-  looks here
|  | vtable methods |
|  |----------------|
└─>|   RTTI object  |

Получив доступ к дополнительной информации остаётся выполнить приведение типа: upcast, downcast, sidecast/crosscast. Эта задача требует совершить поиск в ориентированном ациклическом графе (DAG, directed acyclic graph), что в рамках этой операции может быть трудоёмким, но необходимым для обработки общего случая. Теперь мы можем даже ответить, почему dynamic_cast такой медленный.

Можем ли мы как-то ускорить работу? Мы можем просто запретить использовать dynamic_cast 😄 Это можно сделать, отключив RTTI с помощью флага компиляции:

-fno-rtti

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

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

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

#cppcore #howitworks

​Еще одна проблема при разрушении статиков
#опытным

Идею для поста подкинул Михаил в этом комменте

Суть в чем. Все глобальные переменные, не помеченные thread_local, создаются и уничтожаются в главном потоке, в котором выполняется main(). Но использовать мы их можем и в других потоках, адресное пространство-то одно. И вот здесь скрывается опасность: мы можем использовать в другом потоке глобальную переменную, которая уже была уничтожена!

Вы просите объяснений? Их есть у меня.

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

По пунктам

1️⃣ Статические переменные удаляются при вызове std::exit, что происходит после завершения main(). Значит, нам нужно выйти из main'а.

2️⃣ Получается, что второй поток должен продолжать выполняться даже после завершения main. Тут только один вариант: отделить тред от его объекта, чтобы его не нужно было джойнить. Делается это с помощью метода detach().

3️⃣ Использование переменной вторым потоком должно быть между разрушением глобальной переменной и завершением std::exit, потому что эта функция завершает процесс. И естественно, что после завершения процесса уже никакие потоки выполняться не могут.

Вот такие незамысловатые условия. Давайте посмотрим на примере.

struct A {
  ~A() {  
    std::this_thread::sleep_for(std::chrono::seconds(5));
  }
};

struct B {
  std::string str = "Use me";
  ~B() {
    std::cout << "B dtor" << std::endl;;
  }
};

A global_for_waiting_inside_globals_dectruction;
B violated_global;

void Func() {
  for (int i = 0; i < 20; ++i) {
    std::cout << violated_global.str << std::endl;
    std::this_thread::sleep_for(std::chrono::seconds(1));
  }
}

int main() {
  std::thread th{Func};
  th.detach();
  std::this_thread::sleep_for(std::chrono::seconds(3)); // aka some usefull work
}

Быстренькое пояснение. Создал 2 простеньких класса, которые позволят наглядно показать процесс удаления переменной и использования ее после удаления. Деструктор первого класса заставляет главный тред уснуть на 5 секунд, что помещает программу в опасное состояние как раз между ее завершением и разрушением статиков. Второй класс мы как раз и будем использовать для создания шаренного объекта, который использует второй тред. У него в деструкторе выводится сообщение-индикатор удаления. Давайте посмотрим на вывод:

Use me
Use me
Use me
B dtor
Use me
Use me
Use me
Use me
Use me

Поймана за хвост, паршивка! Мы используем поле удаленного объекта, что чистой воды UB!

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

Если я что-то упустил, то пусть Михаил меня поправит в комментах.

Avoid dangerous practices. Stay cool.

#cppcore #cpp11 #concurrency

Задача

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

Снова у нас главный герой - царь. Деспотом был этот царь и любил издеваться над своими подданными. В этот раз он решил поиздеваться над самыми светлыми умами в царстве - мудрецами. Собрал царь 20 мудрецов и сказал им следующее: "Я хочу проверить и протестировать вашу мудрость, мои мудрецы. Вы будете выстроены в одну колонну друг за другом лицом к затылку, да так, чтобы никто не смел оборачиваться назад. А то казню! Каждый сможет видеть только впереди стоящих мудрецов. Первый не видит никого. Последний видит всех, крое себя. На каждом из вас будет шляпа одного из двух цветов: черного и белого, которую вы не сможете увидеть. Каждый из вас должен будет угадать цвет своей шляпы. То есть каждый должен будет сказать всего одно монотонное слово: либо "белая", либо "черная". Если не угадаете - голову с плеч! Но Я хочу протестировать вашу мудрость - Я даю вам возможность посовещаться и выбрать стратегию ответов, а также кто и в каком порядке будет давать ответ. Во время нашей забавы вы сможете услышать ответы своих товарищей, но трогать вы никого не можете. Посмотрим, так ли вы мудры, как о вас молвят люди."

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

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

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

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

Вечером выйдет пост с ответом, где уже все могут обсуждать, что угодно.

В целом, это все условия и правила.

Раз, два, три - мудрецам ты помоги! Погнали решать!

Challenge yourself. Stay cool.

Решение задачи с мудрецами

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

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

И такая стратегия есть)

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

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

И все последующие мудрецы на основе ответов своих предыдущих коллег смогут дать правильный ответ. Приведу сразу пример для наглядности.

Рассмотрим колонну из 5 мудрецов. Для большей длины все будет аналогично. Б - мудрец с белой шляпой, Ч - с черной. Поставили их вот так:
1 2 3 4 5
Б<-Ч<-Ч<-Б<-Ч

Справа - последний, он видит четверых предыдущих. Слева первый, который никого не видит.

Последний сосчитал количество белых шляп впереди - 2. 2 - четное число, поэтому он говорит, что у него белая шляпа. Ему отрубают голову(R.I.P).

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

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

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

1-ый знает, что белых шляп все еще нечетное число, поэтому говорит: "белая". И оказывается в стане спасенных.

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

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

Такая задачка. Делитесь эмоциями от ее решения в комментах. И не скупитесь на лайки!

Solve your problems. Stay cool.

Девиртуализация вызовов. Ч2
#опытным

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

Получается, что нам достаточно ограничить внешнее связывание? Рассмотрим в примерах дальше 😊

Запрет на внешнее связывание 1
Итак, мы ведь знаем, что для конкретной функции можно запретить внешнее связывание, например, с помощью static. Из живого примера:

// direct call!
static void bar(Base &da, Base &db)
{
                // push  rbx
                // mov   rax, [rdi]
                // mov   rbx, rsi
  da.vmethod(); // call  DerivedA::vmethod()
                // mov   rdi, rbx
                // pop   rbx
  db.vmethod(); // jmp   DerivedB::vmethod()
}

Вызов функции bar - единственный в данной единице трансляции, с конкретными наследниками Base. Следовательно, мы можем доказать П.2, П.4, П.3 (терминология из первой части).

Кстати, П.2 может быть доказан лишь частично! Например, bar можно вызывать с разными аргументами, тогда оптимизация будет совершена лишь частично:

// indirect + direct call
static void bar(Base &da, Base &db)
{
                // push  rbx
                // mov   rax, [rdi]
                // mov   rbx, rsi
  da.vmethod(); // call  [[rax]]
                // mov   rdi, rbx
                // pop   rbx
  db.vmethod(); // jmp   DerivedB::vmethod()
}

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

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

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

-flto -fwhole-program-vtables -fvisibility=hidden

В GCC можно вообще указать, что компилируемая единица и есть вся программа с помощью флага:

-fwhole-program

Он буквально разрешает считать, что компилятор знает ВСЕ известные перегрузки и их вызовы. Короче, отметит все функции ключевым словом static: живой пример.

Запрет на внешнее связывание 3
Еще один способ показать компилятору, что новых полиморфных перегрузок не появится. Можно использовать unnamed namespace:

namespace
{
  struct Base
  {
    virtual void vmethod();
  };
  
  struct Derived : public Base
  {
    void vmethod() override;
  };
}

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

Вот такими несложными действиями можно сократить количество обращений к таблице виртуальных методов и ускорить выполнение вашего приложения 😉

#cppcore #hardcore #howitworks

C-style cast
#новичкам

Как уже неоднократно было нами отмечено, что язык C++ разрабатывался с поддержкой обратной совместимости языка C. В частности, в C++ поддерживается приведение в стиле C:

int value = (int)arg;

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

Вот давайте вспомним все операторы приведения, про которые мы успели рассказать? У нас были посты про:
- static_cast
- reinterpret_cast
- const_cast
- dynamic_cast

У каждого из них есть своя область применения и соответствующий алгоритм приведения, а так же наборы проверок! Т.к. C-style cast сочетает в себе все вышеперечисленные операторы, то большая часть проверок просто отсутствует... Они не проверяют конкретный случай, что является очень опасным моментом.

В случае невозможности желаемого приведения, C-style cast совершит другое подходящее. Рассмотрим ошибку из живого примера:

cpp
using PPrintableValue = PrintableValue *;
...
auto data = (PPrintableValue)value;

Мы хотели привести value к типу PrintableValue (int64_t -> int32_t). Но в результате неудачного нейминга псевдонима мы ошиблись. Вдруг клавиша P залипла просто? Вдруг рефакторинг неудачно прошел? В итоге мы собрали программу, смогли её запустить и привели int64_t к int32_t*, а дальше его попытались разыменовать. На первый взгляд, ошибка непонятна: мы ожидали static_cast, а получили reinterpret_cast. В больших продуктах такие ошибки могут оставаться незамеченными, пока не будет проведено полное тестирование продукта (вами или клиентом).

Давайте вспомним про приведение между ветками ромбовидного наследования из статьи про dynamic_cast. Использование C-style приведения бездумно выполнит то, что от него попросили и вляпается в ошибку, хоть красненьким и не подчеркивается :) На самом деле он выполнит reinterpret_cast, но это логическая ошибка! Нам очевидно, что этот оператор не подходит по смыслу, но может подойти static_cast. Если мы попробуем это сделать, будет ошибка компиляции:

error: invalid 'static_cast' from type 'Mother*' to type 'Father*':
Father *switched_son_of_father = static_cast<Father*>(son_of_mother);

Опустим тему с const_cast, думаю, тут и так все понятно.

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

Оператор C-style cast скрывает в себе достаточно неочевидное поведение в некоторых ситуациях. Его сложно заметить, его сложно отлаживать. Возможно, что будет проще отказаться от него вовсе, чем помнить о всех подводных камнях. Предупреждения вам в помощь! Добавляйте опцию компилятора:

-Wold-style-cast

#cppcore #goodpractice

​Double-Checked Locking Pattern. Мотивация
#новичкам

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

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

...
If control enters the declaration concurrently 
while the variable is being initialized, 
the concurrent execution shall wait for 
completion of the initialization.

Поэтому раньше люди не могли писать такой простой код:

Singleton& GetInstance() {
  static Singleton inst{};
  return inst;
}

и надеяться на то, что объект будет создаваться потокобезопасно.

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

class Singleton {
public:
    static Singleton* instance() {
        Lock lock; 
      if (inst_ptr == NULL) {
          inst_ptr = new Singleton;
      }
        return inst_ptr;
    }
private:
    Singleton() = default;
    static Singleton* inst_ptr;
};

У нас есть какая-то своя RAII обертка Lock над каким-то мьютексом(до С++11 ни std::mutex, ни std::lock_guard не существовало, приходилось велосипедить(ну или бустовать, кому как удобнее)).

Обратите внимание, как это работает. Статические указатели автоматически zero-инициализируются нулем, поэтому в начале inst_ptr равен NULL. Дальше нужно проверить, если указатель еще нулевой, то значит мы ничего не проинициализировали и нужно создать объект. И делать это должен один тред. Но куда поставить лок? На весь скоуп или только внутри условия на создание объекта?

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

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

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

Здесь-то и приходит на помощь шаблон блокировки с двойной проверкой, о котором подробнее поговорим в следующих статьях.

Solve your problems. Stay cool.

#multitasking #cppcore #cpp11

​Double-Checked Locking Pattern Classic
#опытным

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

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

static Singleton* Singleton::instance() {
  if (inst_ptr == NULL) {
    Lock lock;
    if (inst_ptr == NULL) {
      inst_ptr = new Singleton;
    }
  }
  return inst_ptr;
}

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

Это классическая реализация, многие подписчики, думаю, видели ее. Однако от того, что она классическая, не следует, что она корректная.

Давайте посмотрим на вот эту строчку поближе:

inst_ptr = new Singleton;

Что здесь происходит? На самом деле происходят 3 шага:

1️⃣ Аллокация памяти под объект.

2️⃣ Вызов его конструктора на аллоцированной памяти.

3️⃣ Присваивание inst_ptr'у нового значения.

И вот мы, как наивные чукотские мальчики, думаем, что все эти 3 шага происходят в этом конкретном порядке. А вот фигушки! Компилятор, мать его ети. Иногда он может просто взять и переставить шаги 2 и 3 местами! И вот к чему это может привести.

Давайте посмотрим эквивалентный плюсовый код, когда компилятор переставил шаги:

static Singleton* Singleton::instance() {
  if (inst_ptr == NULL) {
    Lock lock;
    if (inst_ptr == NULL) {
      inst_ptr = // step 3
      operator new(sizeof(Singleton)); // step 1
      new(inst_ptr) Singleton; // step 2
    }
  }
  return inst_ptr;
}

Че здесь происходит. Здесь просто явно показаны шаги. С помощью operator new мы выделяем память(1 шаг), дальше присваиваем указатель на эту память inst_ptr'у(шаг 3). И в конце конструируем объект. И напомню, это не программист так пишет. Это эквивалентный код тому, что может сгенерировать компилятор.

И этот код совсем не эквивалентен тому, что было изначально. Потому что конструктор Singleton может кинуть исключение и очень важно, чтобы есть он это сделает, то inst_ptr останется нетронутым. А он как бы изменяется. Поэтому, в большинстве случаев, компилятору нельзя генерировать такой код. Но при определенных условиях, он может это сделать. Например, если докажет сам себе, что конструктор не может кинуть исключение. И вот тогда происходит magic.

Тред №1 входит в первое условие, берет лок и выполняет шаги 1 и 3 и потом засыпает по воле планировщика. И мы имеем состояние, когда указатель проинициализирован, а объекта на этой памяти еще нет(шаг 2 не выполнен).

Тред №2 входит в функцию, видит, что указатель ненулевой и возвращает его наружу. А внешний код потом берет и разыименовывает указатель с непроинициализированной памятью. Уупс. UB.

Что можно сделать? Вообще говоря, ничего. Если сам язык не подразумевает многопоточности, то компилятор даже не думает о таких штуках и с его точки зрения все валидно. Даже volatile предотвращает реордеринг инструкций в рамках только одного потока. Но мы же в многоядерной среде и там существуют совершенно другие эффекты, о которых "безпоточные" С и С++ в душе не знают. Напоминаю, что мы до сих пор в эре до С++11. Завтра чуть ближе посмотрим на конкретные проблемы, при которых мы сталкиваемся, находясь в многопоточном окружении.

Criticize your solutions. Stay cool.

#concurrency #cppcore #compiler #cpp11

Что опасного в многопоточке?
#новичкам

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

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

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

struct Class {
  Class(int a, int b, int c) : x{a}, y{b}, z{c} {}
  int x;
  int y;
  int z;
};

Class * shared;

void fun() {
  shared = new Class{1, 2, 3};
}

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

if (shared) 
  // do smt with object

И код войдет в условие, потому что указатель ненулевой. Но память по этому указателю будет еще не инициализирована. А это, друзья, наше любимое UB.

И это в точности то, что может происходить с нашим беднягой синглтоном! Если вы думаете, что lock на мьютексе вас спасет, то нет, не спасет!

Да, лок подразумевает барьеры памяти и при unlock'e изменения флашатся. Но на незащищенном чтении-то они подтягиваются без барьеров! Это был небольшой спойлер для шарящих за барьеры. О них не сегодня.

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

Завтра как раз об этом и поговорим.

Be able to work in multitasking mode. Stay cool.

#concurrency #cppcore

​Рабочий Double-Checked Locking Pattern
#опытным

Мы уже довольно много говорим о нем и его проблемах. Давайте же сегодня обсудим решение.

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

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

Singleton* Singleton::getInstance() {
    Singleton* tmp = m_instance;
    ...                     // insert acquire memory barrier
    if (tmp == NULL) {
        Lock lock;
        tmp = m_instance;
        if (tmp == NULL) {
            tmp = new Singleton;
            ...             // insert release memory barrier
            m_instance = tmp;
        }
    }
    return tmp;
}

Вот как выглядела бы более менее работающая реализация паттерна блокировки с двойной проверкой до нашей эры(до С++11). Так как в то время в языке и стандартной библиотеке не было ничего, что связано с потоками, то для барьеров приходилось использовать platform-specific инструкции, часто с ассемблерными вставками.

Acquire барьер предотвращает переупорядочивание любого чтения, которое находится сверху от него, с любыми чтением/записью, которые следуют после барьера. Одна из проблем кода без барьеров: мы можем считать ненулевой указатель в tmp, но при этом результат операции инициализации объекта к нам еще не подтянется. Мы вернем из геттера неинициализированный указатель, что UB. Именно для предотвращения такого эффекта, в данном случае такой барьер нужен сверху для того, чтобы мы подтянули инициализированный объект из кэша другого ядра в случае, если мы все-таки считали ненулевой указатель.

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

Release барьер предотвращает переупорядочивание любого чтения/записи, которое находится сверху от него, с любой записью, которые следуют после барьера. Здесь также 2 составляющие. Первая: предотвращает переупорядочивание иницализации синглтона с присваиванием его указателя к m_instance. Это дает четкий порядок: в начале создаем объект, а потом m_instance указываем на него. Вторая гарантирует нам правильный порядок "отправки" изменений из текущего треда в точки назначения.

Объяснения не самые подробные и точные, но опять же, не было такой цели. Кто понимает - поймет, а кто не понимает - ждите статьи по модели памяти)

И вот как выглядела бы реализация этого паттерна на современном С++, если бы статические локальные переменные не гарантировали бы потокобезопасной инициализации:

std::atomic<Singleton*> Singleton::m_instance;
std::mutex Singleton::m_mutex;

Singleton* Singleton::getInstance() {
    Singleton* tmp = m_instance.load(std::memory_order_relaxed);
    std::atomic_thread_fence(std::memory_order_acquire);
    if (tmp == nullptr) {
        std::lock_guard lock(m_mutex);
        tmp = m_instance.load(std::memory_order_relaxed);
        if (tmp == nullptr) {
            tmp = new Singleton;
            std::atomic_thread_fence(std::memory_order_release);
            m_instance.store(tmp, std::memory_order_relaxed);
        }
    }
    return tmp;
}

Здесь мы только на всякий случай обернули указатель синглтона в атомик указатель, чтобы полностью быть так сказать в lock-free контексте. Барьеры на своих местах, а для залочивания мьютекса используем стандартный std::lock_guard с CTAD из 17-х плюсов.

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

Establish your barriers. Stay cool.

#concurrency #cpp11 #cpp17

Ассемблер инициализации статических локальных переменных
#опытным

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

Singleton& Singleton::getInstance() {
    static Singleton instance;
    return instance;
}

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

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

Singleton::getInstance():
1   movzbl guard variable for Singleton::getInstance()::instance(%rip), %eax
2  testb %al, %al
3  je .L19
4  movl $Singleton::getInstance()::instance, %eax
5  ret
.L19:
  ...
6  call __cxa_guard_acquire
7  testl %eax, %eax
8  jne .L20
.L9:
9  movl $Singleton::getInstance()::instance, %eax
10  popq %rbx
11  ret
.L20:
12  movl $Singleton::getInstance()::instance, %esi
  {Constructor}
13  movl $guard variable for Singleton::getInstance()::instance, %edi
14  call __cxa_guard_release
  {safe instance and return}

Так как код оперирует объектом, а не указателем, то и в ассемблере это отражено. Но да не особо это важно. Сейчас все поймете. Для удобства обращения к коду, пометил строчки номерами.

Итак, мы входим в функцию. И тут же на первой строчке у нас появляется строжевая гвардия для переменной instance. Гвардия защищена барьером памяти и она показывает, инициализирована уже instance или нет. Так как мы без указателей, то вместо загрузки указателя и установки барьера памяти тут просто происходит загрузка гард-переменной для instance в регистр eax. Дальше на второй строчке мы проверяем, была ли инициализирована instance. al - это младший байт регистра eax. Соотвественно, если al - ноль, то инструкция testb выставляет zero-flag и в условном прыжке на 3-ей строчке мы прыгаем по метке. Если al - не ноль, то наш синглтон уже инициализирован и мы можем вернуть его из функции. Получается, что это наша первая проверка на ноль.

На метке .L19 мы берем лок с помощью вызова __cxa_guard_acquire, которая используется для залочивания мьютексов. И снова проверяем переменную-гард на пустоту(напоминаем себе, что она в eax загружена), если до сих пор она нулевая, то прыгаем в .L20. Если уже не ноль, то есть переменная инициализирована, то проваливаемся в .L9, где кладем созданную переменную в регистр возврата значения на 9-й строчке и выходим из функции(10 и 11). Это была вторая проверка

На метке .L20 мы на 12-й строчке кладем наш неинициализированный синглтон в регистр для последующей обработки, а именно для конструирования объекта. На 13-й строчке кладем адрес гарда в регистр, чтобы чуть позже записать туда ненулевое значение aka синглтон инициализирован. Далее мы отпускаем лок с помощью __cxa_guard_release, делаем все необходимые завершающие действия и выходим из функции.

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

Стоит еще раз обратить внимание на то, что __cxa_guard_acquire и __cxa_guard_release - это не барьеры памяти! Это захват мьютекса. Барьеры памяти напрямую здесь не нужны. Нам важно только защитить гард-переменную для синглтона, потому что проверяется только она.

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

Dig deeper. Stay cool.

#concurrency #cppcore

​Named Constructor Idiom

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

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

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

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

Допустим, что с фиговиной помогут справиться strong typedefs. Но со сложностью различий конструкторов для пользователя они не помогут. А вот что может помочь.

Named Constructor Idiom. Давайте дадим имена конструкторам!

Точнее мы немного схитрим. Добавим именные статические функции-фабрики, которые и будут конструировать наши объекты, и переместим все конструкторы в private секцию.

Покажу на примере фиговины, чтобы было по-проще и по-короче

struct HeavyThing {
  static HeavyThing ConstructFromKilos(float kilos) {
    return HeavyThing(kilos);
  }
  static HeavyThing ConstructFromPounds(float pounds) {
    return HeavyThing(0,453592 * pounds);
  }
private:
  HeavyThing(float kilos) : kilos_{kilos} {}

  float kilos_;
};

int main() {
  HeavyThing a = HeavyThing::ConstructFromKilos(100500.0);
  HeavyThing b = HeavyThing::ConstructFromPounds(12345678.0);
}

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

Make convenient interfaces. Stay cool.

#design

​Невероятные вероятности

Зачастую, когда мы пишем какие-то условия, то предполагаем, что какая-то ветка будет выполняться чаще другой. Самый простой пример - проверка чего-то на корректность. И если это что-то некорректно, то мы делаем какие-то действия, сигнализирующие о проблеме. И логично предположить, что наша программа хорошо написана (по крайней мере мы в это охотно верим). Поэтому ошибка - некая экстренная ситуация, которая не должна появляться часто. В принципе, любой не happy path может рассматриваться, как пример такой ситуации.

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

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

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

Потому что в С++20 появились стандартные аттрибуты [[likely]] и [[unlikely]]!

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

int MyVector::at(size_t index) {
  if (index >= this->size) [[unlikely]] {
    throw std::out_of_range ("MyVector index is out of range");
  }
  return this->data[index];
}

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

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

Predict people's actions. Stay cool.

#cpp20 #compiler #performance

​XOR Swap

Есть такая интересная техника для свопинга содержимого двух переменных без надобности во временной третьей! Стандартный подход выглядит примерно так:

template <class T>
void swap(T& lhs, T& rhs) {
  T tmp = std::move(lhs);
  lhs = std::move(rhs);
  rhs = std::move(tmp);
}

Все мы с программистких пеленок уже выучили это. И примерно так и реализована функция std::swap из стандартной библиотеки. Однако вот вам задали на собесе вопрос: "вот у вас есть 2 числа, но я хочу, чтобы вы обменяли их значения без временной переменной?". Какие мысли? Подумайте пару секунд.

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

template <class T, typename std::enable_if_t<std::is_integral_v<T>> = 0>
void swap(T& x, T& y) {
  if (&x == &y)
    return;
  x = x ^ y;
  y = x ^ y;
  x = x ^ y;
}

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

Тут есть один интересный момент, что в случае подачи на вход функции одной и той же переменной, то произойдет эффект зануления. Первый же xor занулит x, а значит и y. Поэтому в самом начале стоит условие на проверку одинакового адреса.

При подаче на вход просто одинаковых значений, все работает и без условия.

Ну и работает это дело только с целочисленными параметрами.

Но предостерегаю вас - не используйте эту технику в современных программах! Результаты этих трех ксоров напрямую зависят друг от друга по цепочке. А значит параллелизма на уровне инструкций можно не ждать.

Современные компиляторы вполне могут и соптимизировать третью переменную и вы ее вовсе не увидите в ассемблере. Да и еще и вариант с доп переменной тупо быстрее работает. Всего 2 store'а и 2 load'а, которые еще и распараллелить можно, против 3 затратных ксоров. Да и даже довольно тяжеловесная XCHG работает быстрее, чем 3 xor'а.

Зачем я это все рассказываю тогда, если эта техника уже никому не уперлась? Для ретроспективы событий. Дело в том, что раньше люди писали программы без компиляторов, напрямую на ассемблере. Плюс в то время компьютеры имели такое маленькое количество памяти, что биться приходилось буквально за каждый байт. А используя операции xor, мы экономим 33% памяти на эту операцию. Довольно неплохо. В стародавние времена как только не извращались люди, чтобы выжимать все из железа. Эх, были времена...

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

Learn technics from the past. Stay cool.

#cppcore #fun #algorithms

Задача

Продолжаем рубрику #задачки, где мы разбираем интересные задачи из мира программирования и не только. Сегодня на очереди довольно интересная задачка, которая сформулирована очень просто и просто решается большинством из нас. Однако в ней зарыт демон - и он заберет у вас пальцы, если вы не решите ее за линейное время и константную сложность по памяти. Как вы тогда код писать будете? То-то же. Придется решать.

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

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

Всем удачи и погнали решать!

Challenge your life. Stay cool.

​Решение задачи

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

Можно чуть получше - догадаться, но в отсортированном массиве одинаковые элементы будут стоять рядом и нам нужно лишь найти тот, у которого нет пары. Время - O(nlogn), память - константная.

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

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

Математика!

Не зря вчерашний пост был про операцию xor. Это была подводка к этой задаче.

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

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

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

3 3 2 2 7 7 5
int res = 0;
res ^= 3; // res == 3
res ^= 3; // res == 0
res ^= 2; // res == 2
res ^= 2; // res == 0
res ^= 7; // res == 7
res ^= 7; // res == 0
res ^= 5; // res == 5

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

"Но это же фигня какая-то. Порядок совсем не такой! Он может быть любым!"

Все верно. Однако мы добавляем в этот коктейль пару щепоточек свойства коммутативности xor и пару столовых ложек его ассоциативности (aka от перемены мест слагаемых сумма не меняется) и получим вкуснейшее решение. Как угодно переставляйте местами числа в массиве - результат будет ровно тот же по свойствам операции xor.

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

-3 + 1 + 5 + (-4) + 3 + (-1) + (-5)

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

Ровно то же самое происходит и в нашей сегодняшней задаче.

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

Solve your problems. Stay cool.

Порядок вызовов конструкторов и деструкторов дочерних классов
#новичкам

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

Вот есть у вас какая-то иерархия классов.

struct Base1 {
  Base1() {std::cout << "Base1" << std::endl;}
  ~Base1() {std::cout << "~Base1" << std::endl;}
};

struct Derived1 : Base1 {
  Derived1() {std::cout << "Derived1" << std::endl;}
  ~Derived1() {std::cout << "~Derived1" << std::endl;}
};

struct Base2 {
  Base2() {std::cout << "Base2" << std::endl;}
  ~Base2() {std::cout << "~Base2" << std::endl;}
};

struct Derived2 : Base2 {
  Derived2() {std::cout << "Derived2" << std::endl;}
  ~Derived2() {std::cout << "~Derived2" << std::endl;}
};

struct MostDerived: Derived2, Derived1 {
  MostDerived() {std::cout << "MostDerived" << std::endl;}
  ~MostDerived() {std::cout << "~MostDerived" << std::endl;}
};

MostDerived{};

Что мы увидим в консоли, если запустим этот код? Вот это:

Base2
Derived2
Base1
Derived1
MostDerived
~MostDerived
~Derived1
~Base1
~Derived2
~Base2

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

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

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

Казалось бы, тривиальное знание для программиста. Но очень важно осознавать эти вещи для того, чтобы понять более сложные концепции или отвечать на более сложные вопросы. Например: "Зачем нужен виртуальный деструктор?", "В какой момент инициализируется указатель на виртуальную таблицу?", "Какой конкретно метод вызовется, если позвать виртуальный метод из констуруктора базового класса?". Без четкого понимания базы создания объектов, на эти вопросы конечно можно заучить ответы, но понимания никакого не будет. А программирование - это только про понимание, как и любая другая техническая дисциплина.

Поэтому

Understand essence of basic concepts. Stay cool.

#OOP #cppcore

Усложняем задачу

Пока мы далеко не уехали от прошлой #задачки, предлагаю порешать ее усложненную версию, предложенную нашим подписчиком Антоном в этом комменте. В чате было вялое обсуждение, но прям конкретного решения не было предложено. Да и с тех пор в чате примерно 2к сообщений написали(за 2 дня!), поэтому вы вряд ли что-то найдете) Кстати, пользуясь моментом, призываю вас вступить в наш чат https://t.me/+qJ8-vWd97nExZGIy. Там ребята постоянно обсуждают код, фреймворки, метапрограммирование. Да и вообще просто веселятся и играют в шахматы)

А условие обновленной задачи такое: дан непустой массив интов. Каждый элемент массива встречается ровно 2 раза, кроме ДВУХ, которые встречаются 1 раз. Необходимо найти эти элементы за линейную временную сложность и константные затраты по памяти.

Всего один аспект условия изменили, и как сразу непонятнее все стало)

Знающим решение - просьба не отбирать хлеб у пытливых умов. Вечером выйдет ответ.

Challenge your life. Stay cool.

​Ответ

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

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

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

Так как для одинаковых чисел xor будет давать ноль, то для разных чисел он будет давать какой-то ненулевой результат. Ненулевой - значит в бинарном представлении это значение будет иметь хотя бы единичку в каком-то из битов. Именно в этом бите N и будут различаться наши числа. А раз мы знаем, в каком бите различаются числа, то во время второго прохода мы можем отдельно ксорить числа с выставленным N битом и с невыставленным. По условию, только два числа непарные, а все остальные - парные. Пары чисел будут попадать в одну из групп и при ксоре будут занулять друг друга. Тогда у нас будут две суммы по модулю 2, которые и будут равняться нашим искомым a и b.

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

Solve your problems. Stay cool.

​Виртуальный деструктор
#новичкам

Возможно САМЫЙ популярный вопрос на собеседованиях на джунов и мидлов. Оно и справедливо в принципе: очень простой и понятный вопрос, но ответ на него требует хорошего уровня понимания ООП в принципе и как оно конкретно работает в плюсах. Динамический полиморфизм, наследование, порядок вызовов конструкторов и деструкторов - да, это база. Но именно ее и нужно проверить у начинающих и продолжающих разработчиков.

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

struct Resource {
  Resource() { std::cout << "Resourse has been acquired\n";}
  ~Resource() { std::cout << "Resource has been released\n";}
};

struct Base {
  Base() { std::cout << "Base Constructor Called\n";}
  ~Base() { std::cout << "Base Destructor called\n";}
};

struct Derived1: Base {
  Derived1() { 
    ptr = std::make_unique<Resource>(); 
    std::cout << "Derived constructor called\n";
  }
  ~Derived1() {std::cout << "Derived destructor called\n";}
private:
  std::unique_ptr<Resource> ptr;
};

int main() {
  Base *b = new Derived1();
  delete b;
}

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

В коде вроде все хорошо написано и невнимательный кандидат может выдать вот это:

Base Constructor Called
Resourse has been acquired
Derived constructor called
Derived destructor called
Resource has been released
Base Destructor called

Вот тут-то его и подловили! На самом деле никакого деструктора наследника вызвано не будет и соответственно ресурсы не освободятся. Интервьюер дает наводку посмотреть на деструктор базового класса. И кандидат с красным лицом кричит: "Деструктор - невиртуальный! По указателю на базовый класс вызовется сразу деструктор базового класса, а деструктор дочернего не вызовется. Будет утечка памяти". Его так на курсах научили говорить. И дальше он выдает правильный вывод программы.

И тут интервьюер говорит: "А что будет, если наследник не будет содержать никаких полей? Какие проблемы будут у этого кода?".

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

Естественно, это неправда.

Если с виду ничего плохого не может произойти и даже при запуске программы ничего плохого не происходит - это не значит, что в программе нет проблем. Стандарт говорит:

if the static type of the object to be deleted 
is different from its dynamic type, the static type 
shall be a base class of the dynamic type of 
the object to be deleted and the static type 
shall have a virtual destructor or
 the behavior is undefined.

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

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

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

Stay armed. Stay cool.

#cppcore #interview