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

Пример из предыдущего поста - рабочая версия паттерна. Однако, нам, вообще говоря, можно всего этого не писать. Ведь начиная с С++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

Сочетание member initialization list и default member initializer
#опытным

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

Также в С++11 у нас появилась фича под названием default member initializer. Это та самая штуковина, которая позволяет вам инициализировать нестатические поля класса не в конструкторе, а прям inplace. Типа того:

struct Class {
  int field = 5;
};

Фича полезная, многие ей часто пользуются. Но вот возникает вопрос: как список инициализации конструктора взаимодействует с default member initializer? Если я инициализирую поля вне конструктора и компилятор видит эти значения явным образом, то возможно эти поля и получают значение первыми? Сейчас все узнаем.

Посмотрим на такой пример:

struct Char {
  Char(char c) : field{c} {std::cout << "Char " << field << std::endl;}
  Char() = default;
  char field;
};

struct TestClass {
  TestClass() : a{'1'},
          c{'3'},
          e{'5'} {}
  Char a;
  Char b = '2';
  Char c;
  Char d = '4';
  Char e;
};

Есть простенький класс Char, который выводит на консоль момент создания объекта. И тестовый класс, на котором мы и проводим эксперимент. И в этом эксперименте мы и проверим, в каком порядке свои значения получают поля b и d, относительно a, c, e.

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

Char 1
Char 2
Char 3
Char 4
Char 5

С этим разобрались.

И тут назревает вопрос: а что будет, если я в начале проициализирую поле inplace, а потом еще раз в constructor initializer list? Какая из инициализаций победит другую? Или быть может они произойдут обе в какой-то очередности?

Выглядеть это может так:

struct Char {
  Char(char c) : field{c} {std::cout << "Char " << field << std::endl;}
  Char() = default;
  char field;
};

struct TestClass {
  TestClass() : a{'1'},
          b{'2'},
          c{'3'},
          d{'4'},
          e{'5'} {}
  Char a;
  Char b = 'b';
  Char c;
  Char d = 'd';
  Char e;
};

Опять в подопытные мы взяли поля b и d и задали им значения с помощью default member initializer. А вдогонку еще и в списке инициализации присвоили им значение.

В такой ситуации default member initializer не играет никакой роли, блаженно складывает лапки и отдает бразды правления списку инициализации. Вывод будет тем же, что и в прошлом примере:

Char 1
Char 2
Char 3
Char 4
Char 5

Но это только список инициализации так работает. Если для инициализации поля вы используете обычный конструктор, то оно первый раз проинициализируется с помощью default member initializer(которая обязательно происходит до входа в тело конструктора), а второй раз - в теле конструктора.

struct TestClass {
  TestClass() : a{'1'},
          c{'3'},
          d{'4'},
          e{'5'} {b = '2';}
  Char a;
  Char b = 'b';
  Char c;
  Char d = 'd';
  Char e;
};
// Output

Char 1
Char b
Char 3
Char 4
Char 5
Char 2

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

Mix things properly. Stay cool.

#cpp11 #cppcore

​​Short circuit для кастомных операторов
#опытным

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

В плюсах короткосхемностью обладают операторы && и ||. Из коробки их операндами могут быть переменные логического, целочисленного и указательного типа. Однако они все так или иначе приводятся к типу булеан. Поэтому в принципе корректно говорить, что логические операторы работают только с логическими типами. Что в целом довольно логичная логика.

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

Взгляните на следующий код:

struct CustomStruct
{
  int number = 0;
  bool operator&&(const CustomStruct& other) 
  {
    return number && other.number;
  }
};

static int check = 0;

CustomStruct func()
{
  check = 1;
  return CustomStruct{};
}

int main() {
  CustomStruct a{};
  a && func();
  std::cout << check << std::endl;
}

Здесь мы создаем самую простую структурку и перегружаем для нее оператор логического И. Дальше, чтобы проверить ленивость вычисления оператора, пишем простую функцию, которая при исполнении изменяет статическую переменную. Так мы сможем наверняка убедиться, выполнилась ли функция или нет: если выполнилась, то переменная check будет выставлена в единицу, если нет, то останется нулем.

И вывод будет реально "1". Что выглядит довольно печально.

Ну и кстати, такое поведение довольно легко объяснить. Когда мы перегружаем операторы, то мы создаем новые функции. И я хочу акцентировать на этом внимание: это именно пользовательские функции, как бы они там не назывались. А аргументы пользовательских функций должны быть вычислены ДО захода в функцию. Поэтому любые операнды должны быть полностью вычислены до вычисления значения всего выражения. Это и приводит к отсутствию свойства short circuit.

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

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

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

Don't loose your properties. Stay cool

#cppcore

Виртуальный деструктор и std::shared_ptr
#опытным

Плюсы - поистине удивительный язык. Вот подписчик изучил у нас на канале пользу виртуального деструктора и пошел в комментарии. А там Василий прислал пример, который говорит о том, что в определенном случае виртульность деструктора не важна и без него все работает корректно. И подписчик действительно удивляется: "What the fuck is going on?!?!?!?". Разберем все по порядку.

Пример вот такой:

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

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

int main() {
  std::shared_ptr<Base> p1 = std::make_shared<Derived>();
}

Прикол в том, что при удалении p1 вызовется деструктор наследованного класса:

Derived::~Derived()
Base::~Base()

Почему так?

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

Так вот логично, что, если мы создаем указатель от объекта тип Derived, то и делитер выбирается соотвествующий. И в контрол блоке правого шареда будет делитер, который удаляет Derived*. Далее при присваивании указатель на этот конкретный контрол блок копируется левому шареду. После этого контрольный блок p1 содержит тот самый изначальный делитер, который условно говоря сделает перед удалением указателя каст к классу наследника(delete static_cast<Derived*>(ptr)).

Именно поэтому и вызывается деструктор наследника.

Если мы попытаемся создать std::shared_ptr вот так:

std::shared_ptr<Base> shared(static_cast<Base*>(new Derived));

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

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

std::unique_ptr<Base> p1 = std::make_unique<Derived>();

для p1 не вызовется деструктор наследника, потому что делитер типа std::unique_ptr<Base> удаляет только указатели на базовый класс. Чтобы объект удалялся корректно, нужен виртуальный деструктор базового класса. Без него никак.

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

Stay amazed. Stay cool.

#cpp11 #cppcore

​​Шаблонный сеттер
#опытным

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

Если у вас есть какой-то шаблонный класс, который хранит тип Т, и в этом классе есть сеттер на этот тип, то по давней привычке(еще с 98 стандарта) его можно написать вот так:

template <class T>
struct TemplateClass {
  void SetValue(const T& value) {
    value_ = value;
  }
private:
  T value_;
};

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

Но иногда привычки ограничивают нас. Мы-то уже в modern C++ эре. И в данном случае как раз такой кейс.

Что будет, если мы захотим передать в этот метод временный объект? Например так:

struct ShowConstruct {
  ShowConstruct() = default;
  ShowConstruct(int value) : field{value} {
    std::cout << "Param construct " << field << std::endl;}
  ShowConstruct& operator=(const ShowConstruct& other) {
    field = other.field;
    std::cout << "Copy assign " << field << std::endl;
    return *this;}
  ShowConstruct& operator=(ShowConstruct&& other) {
    field = other.field;
    std::cout << "Move assign " << field << std::endl;
    return *this;}
  int field = 0;
};

TemplateClass<ShowConstruct> obj;
obj.SetValue(ShowConstruct{5});

На экран выведется:

Param construct 5
Copy assign 5

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

Потому что в сеттере value уже относится к категории lvalue. А при присваивании объекта от lvalue будет вызываться копирующий оператор присваивания.

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

Использовать универсальную ссылку. Скажет прошаренный читатель.

Для шаблонного кода мы можем пометить параметр метода двумя амперсандами и дальше внутри передавать его во все места через std::forward. Таким образом, если нам на вход пришел именованный объект, то std::forward скастует его к lvalue ссылке, а если временный, то к rvalue ссылке. И это поможет нам в нужных случая вызывать правильный оператор присваивания. И std::forward и universal reference доступны с 11-го стандарта вместе с введением мув-семантики.

template <class T>
struct TemplateClass {
  void SetValue(T&& value) {
    value_ = std::forward<T>(value);
  }
private:
  T value_;
};

TemplateClass<ShowConstruct> obj;
obj.SetValue(ShowConstruct{5});

Теперь мы получаем нужный вывод:

Param construct 5
Move assign 5

Однако этот прошаренный читатель оказался не таким уж и прошаренным! Такая штука не сработает для шаблонных параметров класса!

in class template argument deduction, template parameter 
of a class template is never a forwarding reference

Универсальная ссылка(она же forwarding reference) появляется только, когда тип параметра функции Т&& и Т - шаблонной параметр самой функции. В нашем случае нет никакого вывода - тип Т известен из класса. Поэтому и никакой универсальной ссылки не появляется.

Мы просто определили метод, который принимает rvalue ссылку. При попытке передать туда lvalue будет ошибка:

TemplateClass<ShowConstruct> obj;
ShowConstruct lvalue{7};
obj.SetValue(lvalue);

//ERROR: rvalue reference to type 'ShowConstruct' 
// cannot bind to lvalue of type 'ShowConstruct'

Какой выход? Просто рядышком с сеттером для константной lvalue ссылки написать сеттер для rvalue ссылки.

template <class T>
struct TemplateClass {
  void SetValue(const T& value) {
    value_ = value;
  }
  void SetValue(T&& value) {
    value_ = std::move(value);
  }
private:
  T value_;
};

TemplateClass<ShowConstruct> obj;
obj.SetValue(ShowConstruct{5});
ShowConstruct lvalue{7};
obj.SetValue(lvalue);

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

Stay universal. Stay cool.

#cpp11

​​Swap idiom. Pros and cons
#опытным

В этом посте поговорили про суть swap идиомы. Сегодня обсудим ее плюсы и минусы.

Плюсы вроде как обсуждали, но я финализирую, когда можно рассмотреть внедрение swap idiom:

✅ Если у вас конструктор копирования может бросить исключение и вы можете написать небросающую функцию swap. Тогда за счет того, что захват ресурсов(копирование или перемещение во временный объект параметра функции) происходит до модификации текущего объекта, то мы получаем строгую гарантию безопасности исключений при работе с присваиванием объектов.

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

✅ Вы не очень беспокоитесь о потенциальных потерях производительности.

Погнали по минусам:

❗️ Не всегда можно написать nothrowing swap. Для базовых типов и указателей - да. Но swap нетривиальных типов использует временный объект. При создании которого и может возникнуть исключение. Сейчас swap делается с помощью перемещающих операций, но например в С++03 std::string мог кинуть исключение в копирующем конструкторе. Да и сейчас поля класса могут быть немувабельными и бросающими при копировании. Это надо иметь ввиду.

❗️ Каждый раз при присваивании мы выполняем 2 операции: конструктор копирования + swap или конструктор перемещения + swap. "Потери производительности" надо конечно тестить и смотреть реальные результаты, но в голове все равно надо держать потенциальные просадки.

❗️ Самостоятельно писать деструктор для менеджинга ресурсов в 2к24 - такая себе практика в большинстве случаев. Давно есть std::unique_ptr<T[]>, указатели с кастомными делитерами и прочие вещи. Одно из ключевых преимуществ идиомы - сокращение и переиспользование кода. Так вот с отсутствием деструктора вам вообще может не понадобится кастомное присваивание и вы сможете объявить операции дефолтными, поэтому надобность в идиоме сама по себе отпадет.

❗️❗️ Часто пропускаемый огромный минус: технически у нас есть оператор перемещения, который может принимать rvalue ссылки. Однако мы явным образом не реальзовывали присваивание перемещением, поэтому по правилу 5, компилятор не будет его генерировать за нас и у класса просто будет отсутствовать оператор присваивания перемещением.

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

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

struct FirstField {
  FirstField() = default;
  FirstField(const FirstField& other) {
    std::cout << "FirstField Copy ctor" << std::endl;
  }
  FirstField& operator=(FirstField other) {
    std::cout << "FirstField assign" << std::endl;
    return *this;
  }
  FirstField(FirstField&& other) {
    std::cout << "FirstField Move ctor" << std::endl;
  }
};

struct SecondField {
  SecondField() = default;
  SecondField(const SecondField& other) {
    std::cout << "SecondField Copy ctor" << std::endl;
  }
  SecondField& operator=(const SecondField& other) {
    std::cout << "SecondField Copy assign" << std::endl;
    return *this;
  }
  SecondField(SecondField&& other) {
    std::cout << "SecondField Move ctor" << std::endl;
  }
  SecondField& operator=(SecondField&& other) {
    std::cout << "SecondField Copy assign" << std::endl;
    return *this;
  }
};

struct Wrapper {
  FirstField ff;
  SecondField sf;
};

Wrapper w;
w = std::move(Wrapper{});

// OUTPUT:
// FirstField Move ctor
// FirstField assign
// SecondField Copy assign

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

Analyse your solutions. Stay cool.

#cppcore #cpp11

​​Вектор ссылок
#опытным

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

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

std::vector<int&> vec;

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

В сущности это происходит по одной причине. Шаблонный тип vec не удовлетворяет требованиям к типам элементов вектора.

До C++11 и появления мув-семантики элементы вектора должны были удовлетворять требованиям CopyAssignable и CopyConstructible. То есть из этих объектов должны получаться валидные копии, притом что исходный объект оказывается нетронутым. Это условие, кстати, не выполняется для запрещенного в РФ иноагента std::auto_ptr. Так вот ссылочный тип - не CopyAssignable. При попытке присвоить ссылке что-то копирования не происходит, а происходит просто перенаправление ссылки на другой объект.

После С++11 требования немного смягчились и теперь единственный критерий, которому тип элементов вектора должен удовлетворять - Erasable. Но ссылки также не попадают под этот критерий(для них не определен деструктор). Поэтому сидим без вектора ссылок. Или нет?

Можно хакнуть этот ваш сиплюсплюс и создать вектор из std::reference_wrapper. Это такая тривиальная обертка над ссылками, чтобы ими можно было оперировать, как обычными объектами. В смысле наличия у них всех специальных методов классов.

Но будьте осторожны(!), потому что есть одна большая проблема со ссылками. Вот мы создали и заполнили контейнер ссылками на какие-то объекты. И потом вышли из скоупа, где были объявлены объекты, на которые ссылки указывают. Вектор есть, ссылки есть, а объектов нет. Это чистой воды undefined behavior. Ссылки будут указывать на уже удаленные объекты. Пример:

std::vector<std::reference_wrapper<int>> vec;
int * p = nullptr;
{
  int i;
  for (i = 0, p = &i; i < 5; i++) {
    vec.emplace_back(i);
  }
}

*p = 10;

for (int i = 0; i < 5; i++) {
  std::cout << vec[i] << std::endl;
}

Вывод будет такой:

10
10
10
10
10

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

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

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

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

Be careful. Stay cool.

#cpp11 #cppcore #STL

​​Странный размер std::unordered_map
#опытным

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

constexpr size_t map_size = 6;
std::unordered_map<int, int> mymap;
mymap.reserve(map_size);
for (int i = 0; i < map_size; i++) {
  mymap[i] = i;
}
std::cout << "mymap has " << mymap.bucket_count() << " buckets\n";

Все, как обычно. А теперь вывод:

mymap has 7 buckets

WTF? Я же сказал выделить в мапе 6 бакетов, а не 7. Какой непослушный компилятор!

Вообще, поведение странное, но может там просто всегда +1 по какой-то причине?

Поменяем map_size на 9 и посмотрим вывод:

mymap has 11 buckets

Again. WTF? Уже на 2 разница. Нужна новая гипотеза... Попробуем третье число. Возьмем 13.

mymap has 13 buckets

А тут работает! Но это не прибавляет понимания проблемы... В чем же дело?

Из цппреференса про метод reserve:

Request a capacity change

Sets the number of buckets in the container (bucket_count) to the most appropriate to contain at least n elements.

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

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

Реализации обычно выбирают bucket_count исходя из соображений быстродействия(как обычно). Тут они выбирают из двух опций:

1️⃣ Выбирают в качестве bucket_count степень двойки, то есть округляют до степени двойки в большую сторону. Это помогает эффективно маппить результат хэш функции на размер самой хэш-таблицы. Можно просто сделать битовое И и отбросить все биты, старше нашей степени. Что делается на один цикл цпу.

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

Таким способом пользуется Visual C++.

2️⃣ Поддерживают bucket_count простым числом.

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

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

Этой реализацией пользуется GCC и Clang.

Вот такие страсти происходят у нас под носом под капотом неупорядоченной мапы.

Optimize everything. Stay cool.

#STL #optimization #compiler

Ревью
#опытным

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

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

Оставляйте в комментах свои замечания и возможные варианты исправления ситуации.

Комментарии наиболее продуктивного критика выложу на канал вместе с ответом.

Хватит отдыхать, пора ошибки в коде искать!

Analyse your life. Stay cool.

​​Опасности std::unordered_map
#опытным

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

В копилку полезности auto.

Вдруг вы решили не пользоваться этой фичей и пишите вот так:

struct Customer{
  Customer(int num) : data{num} {}
  Customer(const Customer& other) {
    data = other.data;
    std::cout << "Copy ctor" << std::endl;
  }
private:
  int data;
};
std::unordered_map<std::string, std::vector<Customer>> data;
data["qwe"] = {Customer{1}, Customer{2}};
for (const std::pair<std::string, std::vector<Customer>>& item : data) {
  std::cout << "Idle print" << std::endl;
}

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

Copy ctor
Copy ctor
Idle print

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

Однако на самом деле вывод будет такой:

Copy ctor
Copy ctor
Copy ctor
Copy ctor
Idle print

Мы этого совсем не ожидали. Откуда еще 2 копии?!!

Дело в том, что в нашей неупорядоченной мапе хранятся не std::pair<std::string, std::vector<Customer>>, а std::pair<const std::string, std::vector<Customer>>. Это в принципе особенность std::unordered_map: ключ мапы - неизменяемый объект, поэтому обобщенно мапа хранит std::pair<const Key, Value>.

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

Ну и естественно, эта проблема просто решается использованием ключевого слова auto.

struct Customer{
  Customer(int num) : data{num} {}
  Customer(const Customer& other) {
    data = other.data;
    std::cout << "Copy ctor" << std::endl;
  }
private:
  int data;
};
std::unordered_map<std::string, std::vector<Customer>> data;
data["qwe"] = {Customer{1}, Customer{2}};
for (const auto& item : data) {
  std::cout << "Idle print" << std::endl;
}

Теперь у нас есть ожидаемый вывод.

Make your life easier. Stay cool.

#cpp11 #STL