company_banner

C++ велосипедостроение для профессионалов

    Классы, которые люди самостоятельно пишут, а потом копируют из одного проекта в другой, хотя они уже есть в стандартных библиотеках, в простонародье называются велосипедами. Первый вопрос, который возникает при встрече с таким «велосипедом» — зачем люди переписывают что-то заново? Вариантов может быть несколько.

    • Некоторые делают это для самообучения: берут класс стандартной библиотеки, пишут его сами с нуля, сравнивают то, что получилось, с тем, что есть в стандартной библиотеке — в процессе узнают для себя что-то новое.
    • Некоторые проекты имеют особое требования к коду. В embedded-разработке принято работать без RTTI и без exception, поэтому части стандартной библиотеки, которые используют RTTI и exception, необходимо переписать без них.
    • Редко, но бывает, когда велосипед пишут, потому что могут написать лучше, чем в стандартной библиотеке. Как правило, такие нововведения рано или поздно попадают в стандартную библиотеку.
    • Другим только кажется, что они могут написать лучше, и таких людей больше. Но в процессе они обучаются, выясняют для себя что-то новое и что-то интересное открывают.
    • Могут быть другие причины.

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

    • бездумно переносить устаревшие технологии 20-30-летней давности в современные проекты;
    • пользоваться «вредными» бенчмарками и оптимизациями.

    А также затронем «вредные» советы, обсудим новейшие практики программирования (C++ 11 и позднее), подумаем, что делать с «идеальным» велосипедом.


    О спикере: Антон Полухин (@antoshkka) сотрудник компании Яндекс, активный разработчик библиотек Boost, автор TypeIndex, DLL, Stacktrace, Maintainer Boost Any, Conversion, LexicalСast, Variant, сопредседатель Национальной рабочей группы по стандартизации С++. Всё это вместе значит, что Антон ежедневно видит очень много кода, как опенсорсного, так и коммерческого, и очень хорошо знает, как часто разработчики изобретают велосипеды.

    Итак, тема — велосипеды. С какого класса начнем? Правильно — со строки.

    std::string


    string: C++98


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

    class string {
      char* data;
      size_t size;
      size_t capacity;
      // ...
    };
    

    Вы начнете писать что-то очень простое без всяких шаблонов. У вас будет указатель на динамический проаллоцированный кусок памяти (data), переменная size, которая хранит количество символов в проаллоцированном куске памяти, и переменная capacity, которая задает размер этого динамического куска памяти.

    class string {
      char* data;
      // ...
    public:
      string(const string& s)
      :data(s. clone()) // new + memmove
      {}
      // ...
      string(const char* s); // new + memmove
    };
    

    Для вашего класса строки вы напишите конструктор копирования и конструктор от массива символов. Оба они будут динамически аллоцировать кусок памяти, перемещать туда символы. Здесь написано new + memmove, но на самом деле там могут быть быть небольшие вариации типа malloc, memcpy, смысл остается тем же.

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

    std::map<string, int> m;
    
    m.insert(
      std::pair<string, int>("Hello!", 1)
    );
    

    И тут вы понимаете, что дела плохи — медленно, очень медленно.

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

    • Cначала вызывается конструктор строки от массива символов — это вызов new и memmove (string("Hello!")).
    • Потом вызывается конструктор пары, т. е. будет вызван copy-конструктор строки. Это еще один вызов new и еще один вызов memmove (make_pair(string("Hello!"), 1)).
    • Потом эта пара вставляется в map. Копируется пара и ее содержимое — еще один вызов new и memmove (m.insert(make_pair(string("Hello!"), 1))).
    • После этого временный объект пары и временный объект строки будут удалены.

    Получается весьма печальная картина — 3 вызова new, 3 вызова memmove, пара вызовов delete, и все это жутко медленно. Вас раздражает, что у Васи быстрее, и вы начинаете думать, как сделать лучше.

    string: COW


    Тут вы либо сами придумываете, либо где-то читаете о технологии Copy-On-Write (COW). Она позволяет эффективнее работать с временными объектами. Большая часть потерь была за счет того, что создаются временные объекты, которые никак не модифицируются: их просто создали, что-то из них скопировали и тут же уничтожили.

    std::map<string, int> m;
    
    m.insert(
      std::pair<string, int>("Hello!", 1) // копии которые не надо копировать
    ); // копии которые не надо копировать
    

    По технологии Copy-On-Write вместо того, чтобы строка уникально владела динамическим объектом, который создан в куче, можно сделать так, чтобы несколько строк одновременно ссылались на динамический объект. Тогда в этом динамическом объекте будет счетчик ссылок — сколько одновременно строчек работает с ним. Код будет выглядеть так:

    class string_impl {
      char* data;
      size_t size;
      size_t capacity;
      size_t use_count; // <===
      // ...
    };
    

    Вы напишете class string_impl (можно написать его получше) и добавите use_count, т. е. счетчик ссылок — сколько строчек ссылается одновременно на динамический объект. Еще вы поменяете конструктор копирования, теперь он будет брать указатель на динамический объект от входной строки и увеличивать счетчик ссылок.

    class string {
      string_impl*impl;
    public:
      string(const string& s)
        :impl(s.impl)
      {
        ++impl->use_count;
      }
    };
    

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

    Нужно добавить проверку: если мы уникально владеем динамическим объектом, то есть счетчик ссылок равен 1, то мы можем делать с ним все, что угодно. Если счетчик ссылок не равен 1, мы должны вызвать new и memmove, создать еще один динамический объект и скопировать туда данные из старого объекта.

    class string {
      string_impl*impl;
    public:
      char& operator[](size_t i) {
        if (impl->use_count > 1)
          *this = clone();
        }
        return impl->data[i];
      }
    };
    

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

    class string {
      string_impl*impl;
    public:
      ~string() {
        --impl->use_count;
        if (!impl->use_count) {
          delete impl;
        }
      }
    };
    

    Производительность вставки в std::map


    В конструкторе от массива символов ничего лучше не стало, по-прежнему new и memmove. Зато дальше вызовется конструктор копирования строки при создании пары, который теперь не вызывает ни new, ни memmove. Когда пара будет вставляться в map, опять будет вызван конструктор копирования строки, который опять-таки не вызывает new и memmove.

    Все деструкторы временных объектов тоже не вызовут delete — красота!

    Итого, COW более чем в 2 раза ускоряет код в C++98.

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

    В 90-е года многие библиотеки так делали. Например, есть библиотека QT, где COW присутствует практически во всех базовых классах.

    Но технологии не стоят на месте. Наступают 2000-е года, появляются процессоры с Hyper-threading и многоядерные процессоры, причем не только серверные, но и пользовательские:

    • Hyper-threading в процессорах Pentium 4.
    • 2-ядерный процессор Opteron архитектуры AMD64, предназначенный для серверов.
    • Pentium D x86-64 — первый 2-ядерный процессором для персональных компьютеров.

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

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

    string: COW MT fixes


    Чтобы это исправить, вводим атомарную переменную — сделаем вид, что в C++ 98 есть std::atomic. Теперь наш класс выглядит так:

    class string_impl {
      char* data;
      size_t size;
      size_t capacity;
      atomic<size_t> use_count; //<=== Fixed
      // ...
    };
    

    Все работает — замечательно! Почти…

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

    class string {
      string_impl*impl;
    public:
      char& operator[](size_t i) {
        if (impl->use_count > 1) { // atomic
          string cloned = clone(); // new + memmove + atomic —
          swap(*this, cloned);
          // atomic in ~string for cloned; delete in ~string if other thread released the string
        } // ...
      }
    };
    

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

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

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

    Atomic


    На X86 не атомарный инкремент — простое увеличение integer на единицу занимает один такт процессора [1]. Если сделать эту операцию атомарной, то она будет занимать от 5 до 20 тактов, если только одно ядро делает атомарную инструкцию и если это ядро последнее меняло атомарную переменную [2]. Если ядро не последним меняло атомарную переменную, то в районе 40 тактов.

    Итого, такое решение в 5-40 раз медленнее только за счет того, что использована атомарная переменная. Дальше хуже.



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

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

    Так выглядит график ожидания последнего ядра:



    В этом примере 16 ядер и последнее ядро ждет в районе 600 тактов. Это простой самого несчастливого ядра. Если просуммировать простои, то получится картина простоя получится квадратичная.



    На 16 ядрах примерно 6000 тактов ушло в никуда.

    Существуют системы, содержащие более 90 ядер, и если все они 90 ядер решат одновременно работать с одной и той же атомарной переменной, все будет очень печально.

    COW более чем в 2 раза ускоряет код в C++98. Все равно Copy-On-Write быстрее и все тут.

    С++11


    В C++11 появляются rvalue reference, что позволяет писать специальные классы и специальные методы, которые работают с временными объектами.

    Например, move-конструктор для строки одинаково хорошо работает, если строка COW и если строка самая обычная базовая из средневековья, где динамически аллоцируется объект, и только одна строка им владеет.

    string::string(string&& s) {
      swap(*this, s);
    }
    

    Что здесь происходит? На вход приходит объект s. Он временный, мы знаем, что компиллятор его скоро удалит, что больше им никто пользоваться не будет, и мы можем забрать у него ресурсы. С ним можно делать вообще все, что угодно, — главное, чтобы для него потом можно было вызвать деструктор.

    Забрали ресурсы. Мы — пустая строка, нам пришла строка с результатом, делаем swap. Теперь мы строка с результатом, а временная строка без всяких ресурсов — пустая.

    Посмотрим, как это работает на нашем примере, если у нас строка без COW.

    std::map<string, int> m;
    m.insert(
      std::pair<string, int>("Hello!", 1) // string("Hello!")
    );
    

    Создается строка от массива символов «Hello». Тут new и memmove — так же, как с COW.

    Дальше — лучше. При копировании строки в пару у нас вызовется move-конструктор строки (pair(string&&, int)). Пара видит, что строка временная, и забирает ресурсы из временного объекта. New и memmove не будет.

    При вставке пары в map, map видит, что пара у нас тоже временный объект (m.insert(pair&&)). Map вызовет move-конструктор для пары, пара вызовет move-конструктор для своего содержимого, move-конструктор для строки.

    Без new и memmove строка перекочует внутрь map: 1 вызов new и 1 вызов memmove — так же, как с COW, но без атомарных операций.

    Хорошо, а если мы хотим копировать строчку? Мы все разумные люди, и хотим копировать строчку, как правило, если мы хотим ее менять.

    Без COW мы скопировали строчку, сразу вызывался new и memmove. Мы можем менять строчку и делать все, что угодно.

    Если у нас COW строка:

    • создаем новый объект строки с атомарным инкрементом общего счетчика ссылок;
    • одну из этих строчек начинаем менять;
    • строчка атомарно посмотрит, что мы не уникально владеем строкой, вызовет new, memmove, проведет дополнительные проверки, чтобы внезапно второй поток не уничтожил эту строчку, что у нас нужное количество строчек и т. д.

    Результат тот же, что и без COW, но, как минимум, пара лишних атомарных операций появляется.

    char& operator[](size_t i) {
      if (impl->use_count > 1) { // atomic
        string cloned = clone(); // atomic—
        swap(*this, cloned); // atomic in ~string for cloned
      }
      return impl->data[i];
    }
    

    Неконстантные методы по-прежнему ужасны. Если мы хотим пройтись по нашей строке (первым десяти символам в строке), используя индексы, с COW строкой — это 10 атомарных операций над одной и той же атомарной переменной. Если два потока одновременно проходятся по одной и той же строке — большая беда.



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

    Начиная с C++11 COW строчки запрещены в стандарте. Там наложены специальные условия на строчку, что COW реализовать невозможно. Все современные имплементации стандартных библиотек не имеют COW строк.

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

    Аккуратнее используйте COW в новых проектах. Не доверяйте статьям, которым больше 10 лет, перепроверяйте их. COW не показывает таких хороших результатов, как 20 лет назад.

    Случаи, где COW все еще жжет


    Если вы имели COW строчку и всем своим пользователям говорили: «У нас COW строка — она идеально все копирует, у нас все замечательно, у нас везде COW», пользователи могли заточиться под это, и писать код с учетом того, что ваши классы используют COW.

    Например, пользователь мог написать класс bimap — это класс, который умеет искать как по ключу, так и по значению.

    // COW legacy
    class bimap {
      std::map<string, int> str_to_int;
      std::map<int, string> int_to_str;
    public:
      void insert(string s, int i) {
        str_to_int.insert(make_pair(s, i));
        int_to_str.insert(make_pair(i, std::move(s)));
    }
    

    Он мог написать его через два std::map, каждая из которых имеет строчку. Здесь строчка COW, пользователь об этом знает, как и то, что в map две копии строки. Пользователь знает, что они динамически будут ссылаться на один и тот же объект памяти, и что это эффективно по памяти. Если здесь COW строчку поменять на обычную, затраты по памяти увеличатся вдвое.

    // COW legacy fix
    class bimap {
      std::map<string, int> str_to_int;
      std::map<int, string_view> int_to_str;
    public:
      void insert(string s, int i) {
        auto it = str_to_int.insert(make_pair(std::move(s), i));
        int_to_str.insert(make_pair(i, *it.first)));
    }
    

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

    Одна оптимизация для string


    Получается, что к той древней строчке 98 года, которая уникально владела динамическим объектом, мы добавили move-конструктор, и все — это идеальная строка? Ничего лучше сделать нельзя?

    Вот что придумали люди. Они посмотрели на один из первых наших примеров, где создается map от строки и int, и туда вставляется пара, долго качали головой и говорили, как все плохо:

    — Тут вызывается new и memmove. За new может стоять системный вызов и атомарные операции, а у нас еще нет C++14, где компилятор умеет оптимизировать new. Все очень плохо — давайте сделаем что-нибудь получше!


    Люди придумали, как можно, не меняя размер строки — переменной std::string — хранить в ней символы, не аллоцируя динамически память. Они посмотрели на самый первый класс строки:

    —У нас здесь указатель на 64-битной платформе — это 8 байт, у нас size тоже на 64-битной платформе — это опять 8 байт. Это 16 байт — в них можно сохранить 15 символов! Что, если пользоваться этими двумя переменными не как переменной-указателем и переменной size, а прямо поверх них располагать данные.

    class string {
      size_t capacity;
      union {
        struct no_small_buffer_t {
          char* data;
          size_t size;
        } no_small_buffer;
        struct small_buffer_t {
          char data[sizeof(no_small_buffer_t)];
        }small_buffer;
      }impl;
    }
    

    Теперь внутри строки в примере выше находится union. Первая часть — это указатель на data и переменная size_t. Вторая часть union — структура — содержит data (маленький буфер размером с char* и size_t). В него влезает примерно 16 байт.

    Если сapacity = 0 — это значит, что мы память динамически не аллоцировали и нам надо идти в impl small_buffer_t, и в data будет лежать наша строчка без динамической аллокации.

    Если сapacity ≠ 0, значит, мы динамически где-то проаллоцировали память, и нужно идти в impl no_small_buffer_t. Там есть указатель на динамически проаллоцированный кусок памяти и переменная size.

    Конечно, в примере немного упрощенный вариант. Некоторые стандартные библиотеки, например Boost, умеют хранить 22 символа и вдобавок терминирующий 0 без динамических аллокаций, не увеличивая размер строки. Все современные стандартные библиотеки используют этот трюк. Это называется Small String Optimization.

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

    Я знаю компании, которые переписывали std::string, потому что у них пустая строка динамически аллоцировала память. Не надо этого больше делать.

    Во-вторых, например, наш «Hello!» влезет без динамической аллокации. Если в строчках хранятся логины пользователей, их имена и фамилии отдельно от имен, какие-то идентификаторы, города, страны, названия валют — как правило, все влезет в строчку без динамических аллокаций.

    Но люди посмотрели и опять подумали, что медленно. Начиная с C++17, компилятор умеет оптимизировать memmove, его альтернативу — ту, которая находится в строке, на этапе компиляции. Но и этого показалось мало. В C++17 есть Guaranteed copy elision, который гарантирует, что в ряде случаев вообще никаких копирований и memmove не будет. Просто в map каким-то чудом образуется эта строчка без промежуточных переменных.

    Со строкой разобрались, но ответы на некоторые уточняющие вопросы из зала здесь
    — Пока все выглядит как реклама велосипедов на самом деле. Например, COW в GCC был до 2015 года, до выхода 5.1. Значит, нужно было писать велосипеды?

    — Больше-то не нужно!

    — Как? Например, все говорят, что классная штука Small String Optimization. Но, допустим, когда строка выделяется динамически, size и capacity можно засунуть в тот же самый буфер, в котором лежит строка. Тогда строка будет всего 8 байт. И если у меня в объекте много строк, это будет выгоднее?

    — У меня реальный случай из практики. Замена COW-строки на строку со Small String Optimization ускорила проект на 7-15%, потому что большую часть времени мы работаем почему-то с маленькими строчками, которые в std::string влезают. Поэтому становится быстрее.

    Можно ли использовать строчку, которая будет динамически в памяти хранить size и capacity? Можно. Тут подключатся проблемы с оптимизатором. Видя, что у нас указатель на какой-то участок памяти, он не сможет лучше оптимизировать эти переменные. Оптимизатор не сможет делать эвристики, основанные на size и capacity. Если же size и capacity расположены на стеке и оптимизатор видит это, он сможет делать на этом эвристики и лучше оптимизировать код.

    — С широкими юникодными строками эта оптимизация хуже работает?

    — Да, хуже. Но количество байтов, которое есть в small_buffer, все то же.

    Разработка без оглядки на готовые решения. std::variant


    На примере std::variant рассмотрим, что бывает, если люди пытаются велосипедостроительствовать, не заглядывая в чужие решения.

    В C++17 принят класс std::variant — это умный union, который помнит, что он хранит. Мы можем написать std::variant<std::string, std::vector<int>>. Это значит, что вариант может хранить в себе либо строку, либо вектор. Если мы запишем в такой вариант слово «Hello», variant запомнит индекс шаблонного параметра в переменной t_index (что он содержит в себе строчку), по месту проаллоцирует строчку и будет ее хранить.

    union {
      T0 v0;
      T1 v1;
      T2 v2;
      // ...
    };
    
    int t_index;
    

    Если теперь попытаться записать туда вектор, std::variant посмотрит, что он хранит в себе строчку в данный момент, а не вектор, вызовет delete для строки, на месте строки сконструирует вектор и в какой-то момент обновит t_index.

    Класс приняли в C++17, и люди по всему миру сразу кинулись его писать заново, переписывать, велосипедостроительствовать.

    template <class... T>
    class variant {
      // ...
      std::tuple<T...> data;
    };
    

    Выше — реальный код из опенсорсного проекта, видите в нем ошибку? Здесь вместо union получился struct.

    Ниже — код из коммерческого проекта:

    variant<T...>& operator=(const U& value) {
      if (&value == this) {
        return *this;
      }
    
      destroy(); // data->~Ti()
      construct_value(value); // new (data) Tj(value);
      t_index = get_index_from_type<U>(); // t_index = j;
    
      return *this;
    }
    

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

    Например, у нас variant, который хранит в себе std::string и мы пытаемся записать в него вектор. В строчке destroy вызовется delete для строки. С этого момента variant пустой, он ничего не хранит.

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

    variant<T...>& operator=(const U& value) {
      if (&value == this) {
        return *this;
      }
    
    destroy(); // data->~Ti()
    construct_value(value); // throw; ...
    // ...
    // ~variant() {
    // data->~Ti() // Oops!!!
    

    Деструктор варианта смотрит, что у него записано в переменной index, которая еще не обновлена. В ней записано std::string, т. е. variant думает, что у него есть строка, которую надо удалить. А на самом деле на этом месте уже ничего нет, строка уже удалена. В этот момент вся ваша программа аварийно завершится.

    Чтобы этого избежать, достаточно открыть интерфейс стандартной библиотеки и посмотреть, что std::variant имеет функцию valueless_by_exception, удивиться, что это такое, и посмотреть, зачем оно нужно. Можно открыть исходники Boost — там 2/3 кода посвящено этой проблеме.

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

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

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

    FORCE_INLINE


    Самое время попрыгать по больным мозолям.

    Можно найти проекты, где все методы помечены как FORCE_INLINE — буквально весь проект вдоль и поперек на гигабайты кода. У людей спрашиваешь:

    — Зачем вы все пометили FORCE_INLINE?

    — Мы написали маленький бенчмарк, проверили — с FORCE_INLINE быстрее. Мы написали и здесь маленький бенчмарк — проверили, с FORCE_INLINE быстрее. Мы протестировали все маленькими бенчмарками и везде с FORCE_INLINE быстрее — мы FORCE_INLINE запихнули во весь проект.

    — Вы неправильно делали бенчмарк.


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

    У процессора есть не только кеш данных


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

    "Большинство современных микропроцессоров для компьютеров и серверов имеют как минимум три независимых кеша: кеш инструкций для ускорения загрузки машинного кода, кеш данных для ускорения чтения и записи данных и буфер ассоциативной трансляции (TLB) для ускорения трансляции виртуальных (логических) адресов в физические, как для инструкций, так и для данных" [1].

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

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



    Представьте, что на рисунке выше ваша программа. Зеленым отмечено то, что поместилось в кеш. Это еще дополнительно ваш hot path — то место, где ваша программа тратит основное количество времени. Сейчас оно все поместилось в кеш процессора, в кеше инструкций простоя не будет.

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



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

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

    • в бинарном виде занимать столько же, сколько ваш production код;
    • иметь приблизительно такое же количество функций и переходов, как ваш production код;
    • вызывать методы так же, как ваш production код.

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

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

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

    Однако, разработчики компиляторов умные люди. Они видят, что пользователи пишут везде FORCE_INLINE и программы становится медленнее. Поэтому современные компиляторы имеют разные эвристики на игнорирование FORCE_INLINE. Некоторые компиляторы просто считают строчки внутри функции — если ваша функция длиннее трех строчек кода, FORCE_INLINE будет проигнорирован.

    Ходит легенда, что есть компилятор, где люди очень сильно озаботились FORCE_INLINE, он их так достал, что они придумали следующую эвристику:

    Если пользователь помечает FORCE_INLINE функцию, которую гарантированно не надо делать FORCE_INLINE, компилятор это запоминает и считает, сколько раз такое произошло. Если превышено некое пороговое значение, компилятор у себя выставляет галочку: «Пользователь не знает, что такое FORCE_INLINE и использует его не там, где нужно — игнорировать все FORCE_INLINE от пользователя».

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

    И наоборот, компилятор может тихо игнорировать ваше «не инлайнить». Он подумает: «Ты не знаешь, что делаешь, написал не инлайнить, но я лучше знаю — я заинлайню».

    Cлучай из практики


    Я знаю очень умного программиста, который писал имплементацию B-Tree. Все было сделано на С++, на шаблонах, везде perfect forwarding, без всяких динамический аллокаций — просто идеально. Когда этот код стали проверять на одном из Performance Analyze, выяснилось, что исполнение не достаточно быстрое из-за того, что большую часть времени занимает ожидание инструкций в кеше инструкций.

    Программист подумал, чуть упростил B-tree, убрал perfect forwarding, заменил его везде на константные ссылки, потому что B-tree никак не менял данные, которые ему приходили, убрал пару шаблонов, сделал код чуть компактнее, добавил noexcept, что тоже уменьшает объем бинарного кода.

    В итоге код стал работать в 2 раза быстрее. Алгоритм не меняли — все то же самое, но код стал работать быстрее.

    Если не верите мне, что FORCE_INLINE плохо, то рекомендую посмотреть лекции (1, 2) разработчика Clang Чендлера Каррута. Он говорит о том же, что и я, но короче, быстрее и на английском.



    От «вредных» бенчмарков переходим к «вредным» советам.

    Aliasing


    Редко, когда разработка идет под одну платформу. Чаще бывает, что когда-то давным-давно разрабатывали под одну платформу, а теперь — под несколько.

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

    Но в момент, когда люди начинают портировать на GCC, программа перестает работать: все компилируется, но тесты не проходят, программа выдает какой-то неадекватный вывод. Люди лезут на Stack Overflow или на другие ресурсы, посвященные программированию, задают этот вопрос и получают ответ:

    — Добавьте волшебную опцию компилятора -fno-strict-aliasing и у вас все заработает.

    И действительно — все начинает работать.

    Объясню на примере, что делает эта опция (с именем функции я здесь не заморачивался).

    bar qwe(foo& f, const bar& b) {
      f += b;
      return b * b;
    }
    

    Функция qwe принимает в себя две переменные: foo по ссылке, bar по константной ссылке. Это два разных типа данных. Внутри тела функции к f прибавляется значение b и выводится квадрат от b.

    Ниже немного ассемблерного псевдокода, который скомпилирует компилятор, если подсунуть опцию -fno-strict-aliasing.

    bar qwe(foo& f, const bar& b) {
      // load b
      // load f
      f += b;
      // load b
      return b * b;
    }
    

    Компилятор:

    • подгрузит в регистр значение переменной b,
    • подгрузит в регистр значение переменной f,
    • произведет операцию f += b,
    • запишет значение f в память,
    • подгрузит значение b опять в память,
    • выполнит b2.

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

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

    Когда вы делаете f += b, компилятор думает, что возможно f и b находятся в одной и той же ячейке памяти, и запись в f меняет значение b. И это во всем вашем проекте — добавили опцию, во всем проекте код стал генерироваться хуже.

    По разным замерам (например, этому и этому), в зависимости от кода и оптимизации, это дает от 5% до 30% просадки производительности. Все очень зависит от вашего кода. Если у вас просто системные вызовы и работа с сетью, возможно, ничего не изменится для вас с -fno-strict-aliasing. Но просто ее писать при сборке вашего проекта не совсем правильно.

    Правильнее включить предупреждение компилятора (GCC умеет предупреждать, когда нарушается strict-aliasing) и исправить в этом месте нарушение strict-aliasing. Как правило, это нарушение происходит, когда вы используете reinterpret_cast для двух несвязанных друг с другом типов.

    Вместо reinterpret_cast лучше использовать memcopy или memmove. Компиляторы GCC умеют их оптимизировать. Просадки производительности в том месте, где вы делаете memcpy вместо reinterpret_cast, быть не должно.

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

    Советы на каждый день


    Скорее всего, вы все это знаете, и, скорее всего, не используете.

    Пример #1, vector


    Ниже пример функции foo, в которой создается вектор от shared_ptr. Мы знаем, shared_ptr — ровно тысяча. Они вставляются в вектор, и он возвращается.

    auto foo() {
      std::vector< std::shared_ptr<int> > res;
      
      for (unsigned i = 0; i < 1000; ++i)
        res.push_back(
          std::shared_ptr<int>(new int)
        );
      return res;
    }
    

    Первый недочет: если мы знаем, сколько элементов будет хранить наш вектор, стоит вызвать res. reserve(1000). Это заранее проаллоцирует нужное количество памяти, и вектор при вставке в него не будет пытаться угадать, сколько памяти нужно. Без reserve в C++11 и раньше вектор сначала примет значение под 2 элемента, потом под 4 элемента, 8, 16 и т. д. Все это время при изменении размера он будет вызывать new, delete, копирование либо move вашего типа данных, что медленно.

    Если же вызвать res. reserve(1000), то вектор точно знает, что это 1000 элементов, никаких дополнительных move, new, delete не будет.

    Начиная с C++14 компиляторам разрешено оптимизировать вызовы new. Некоторые компиляторы умеют это делать, но им должно повезти — не во всех случаях это получается. Если вы хотите быть уверены, что компилятор сгенерирует оптимальный код, лучше вставить reserve — хуже не будет.

    Другое проблемное место в этом примере компилятор соптимизировать не сможет. Это вызов std::shared_ptr<int>. В этой строчке происходит две динамические аллокации:

    1. Первая — new int.
    2. Вторая скрыта внутри конструктора shared_ptr. Ему нужен счетчик ссылок, который он динамически аллоцирует где-то в куче.

    Причем в памяти они находятся в разных местах. Если ваше приложение не использует weak pointers, или использует их не сильно, вместо строчки std::shared_ptr<int>(new int) имеет смысл написатьstd::make_shared<int>().

    Make_shared сразу проаллоцирует кусок памяти, где может хранить и int, и счетчик ссылок. За счет того, что эти две переменные будут находиться рядом, это более кеш-дружелюбно. Работа с shared_ptr станет чуть быстрее, динамических аллокаций будет не две, а одна.

    Итого, код в первом примере мы ускорили чуть более, чем в два раза,просто добавив reserve и заменив конструктор shared_ptr на make_shared.

    Пример #2, for (auto v: data)


    auto foo() {
      std::vector<std::string> data = get_data();
      // ...
      
      for (auto v: data)
        res. insert(
          v
        );
      return res;
    }
    

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

    V здесь копия элемента из вектора. За пределами цикла, и после итераций цикла она нам особо не нужна. Мы можем сказать компилятору, что переменная v больше не используется, заменив v на std::move(v), превратить ее в rvalue, и тогда вставка в результирующий контейнер res произойдет по rvalue ссылке. Ресурсы из v будут просто перекинуты внутрь контейнера, что быстрее.

    Массив vector data больше никак не используется, все, что в нем содержится, будет уничтожено при выходе из функции. Вместо того, чтобы копировать v, мы можем написать for (auto&& v: data), т. е. сделать ссылку на v (&& — здесь это тоже ссылка).

    В итоге получится следующее: v — ссылка на элемент внутри data. Когда мы к этой ссылке применим std::move, ресурс заберется уже из вектора data — прямо из вектора строка перетянется внутрь контейнера res. Никаких динамических аллокаций в итоге не будет. По сравнению с изначальным кодом стало в 100500 раз быстрее.

    Пример #3, vector


    auto foo() {
      std::vector<std::string> data = get_data();
      // ...
      std::string res = data.back();
      data.pop_back();
      // ...
      return res;
    }
    

    Ситуация, как в примере выше, возникает чаще — то же самое, но из вектора мы запоминаем последний элемент, а потом этот последний элемент извлекаем.

    Также можно соптимизировать: мы говорим std::string res = std::move(data. back()). После этого в res — значение последнего элемента (мы перетащили ресурсы из вектора в переменную res). Теперь back внутри вектора — это пустая строка, data.pop_back() просто изменит одну из внутренних переменных вектора. Никаких динамических аллокаций, никаких вызовов delete — все быстрее.

    Пример #4, глобальные константы


    В парсерах и протоколах зачастую есть массивы заранее известных строк. Люди часто пишут их так:

    #include <vector>
    #include <string>
    
    static const std::vector<std::string> CONSTANTS = {
    
      "Hello",
      "Word",
      "!"
    };
    

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

    Но когда проект очень большой, то в разных его частях может накопиться большое количество таких кусков кода — 10, 100, 1000. Инициализация переменной CONSTANTS происходит при запуске программы либо при подгрузке динамической библиотеки. В этот момент этот однопоточный код будет вызывать new, аллокации, инициализировать вектор строк и это может замедлить старт вашей программы либо подгрузку динамической библиотеки.

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

    Если вам массив констант нужен, и вы обращаетесь к нему только по индексу или используете его только в range-based for, вы можете заменить вектор на обычный массив. То есть вместо std::vector<std::string> CONSTANTS можно написать std::string_viewCONSTANTS[].

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

    Если вам нужна строгая гарантия, что это выполнится еще до того, как ваша программа запустится, вы можете static const заменить на constexpr. Это будет обязывать ваш компилятор выполнить этот кусок кода до рантайма.

    Пример #5, наследование


    // base. hpp
    
    struct base {
      // ...
      virtual void act() = 0;
      virtual ~base(){}
    };
    

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

    // something. cpp
    
    struct some_implementation: base {
      // ...
      void act() { /* ... */ }
    };
    

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

    Вы можете сделать код более читабельным, просто добавив слово override:

    // something. cpp
    
    struct some_implementation: base {
      // ...
      void act() override { /* ... */ } // <======
    };
    

    Он будет не только более читабельный, но и более безопасный. Новый человек, когда будет читать ваш код, увидит override и подумает: «Ага, значит, этот метод объявлен в базовом классе, мы его перегружаем, все в порядке».

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

    В итоге он не поломает ваш код. Без override все скомпилируется, как-то будет работать, но будет ошибка на рантайме. На ее отлавливание может уйти много времени. С override сломается на компайлтайме. Человек, который будет делать рефакторинг, это заметит и поправит и здесь метод act.

    Еще можно добавить final в первую строку: struct some_implementation final: base. Это значит, что этот класс финальный, больше от него никто не наследуется. Нам от этого не очень жарко и не очень холодно, но от этого веселее компилятору.

    Компилятор видит, что класс final. Когда он видит some_implementation и переменную этого класса, и у этой переменной вызывается act, компилятор понимает, что от этого класса больше никто не наследуется, и в нем есть act. Он будет вызывать act без прохода по виртуальным таблицам, не будет различных динамических вещей — будет вызов act, как будто он не виртуальный.

    Можно еще чуть-чуть улучшить, запихнув все в анонимный namespace:

    // something. cpp
    
    namespace { // <======
    
      struct some_implementation final: base {
      // ...
      void act() override { /* ... */ }
    };
    } // anonymous namespace</strong>
    

    Анонимный namespace — это как бы static на стероидах. Можно объявить переменную или функцию статиком, тогда она не будет видна наружу. Все, что вы объявите внутри анонимного пространства имен, будет видно только в этой единице трансляции.

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

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

    Пример #5, move constructors


    Ниже move constructors для класса my_data_struct. В нем только вектор data.

    class my_data_struct {
      std::vector<int> data_;
    public:
      // ...
      my_data_struct(my_data_struct&& other)
        :data_(other.data_)
      {}
    };
    

    Только move забыли. И еще noexcept. Давайте перепишем:

    class my_data_struct {
      std::vector<int> data_;
    public:
      // ...
      my_data_struct(my_data_struct&& other) noexcept // <======
        :data_(std::move(other.data_))
      {}
    };
    

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

    Чтобы было быстрее, добавляем noexcept.

    Эта запись не нравится большинству людей. Здесь непонятно, что написано, и нужно знать:

    • как устроен std::vector;
    • кидает ли он exception при move-конструировании;
    • будет ли он кидать exception, если туда подставить необычный аллокатор;
    • можно ли этот move-конструктор пометить noexcept;
    • обзательно ли его нужно помечать noexcept.

    Куча каких-то деталей, которые нам не нужны.

    Надо все лишь написать вот так и все это станет заботой компилятора:

    class my_data_struct {
      std::vector<int> data_;
    public:
      // ...
      my_data_struct(my_data_struct&& ) = default; // <======
    };
    

    Теперь компилятор сам расставит noexcept, constexpr, если сможет. Код из стандартной библиотеки будет работать быстрее — вам легче.

    Caching divs


    Хочу рассказать об одной штуке, на которую я недавно натолкнулся, и которая меня удивила.

    // .h
    extern const double fractions[256];
    
    // .cpp
    const double fractions[256] = { 1.0 / i, ... };
    

    Люди закешировали деление единицы на число. Они создали extern массив на 256 элементов, в котором запомнили:

    • первое число — это 1/0 (сделали 0).
    • второе число по индексу 1 — это 1/1.
    • число по индексу 100 — это 1/100 и т. д.

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

    Как вы думаете, так будет быстрее или медленнее? Давайте выясним.



    Залезаем в талмуды, где описано, сколько тактов занимают инструкции, и обнаруживаем, что доступ к элементу массива, который находится в L1 кеше, занимает 5 тактов, а деление — 22-29 тактов. Итого такое кеширование может быть в 2-4 раза быстрее, но…

    Недостатки cashing divs:


    1. Оптимизатор не видит значения

    • Нет возможности оптимизировать ближайшие инструкции. Массив объявлен в другой единице трансляции. Если у вас нет Link-time -оптимизации, или link-time-optimizer недостаточно продвинутый, он не будет видеть значения и не сможет оптимизировать, основываясь на значениях. Если у вас будет обращение к 1/100, а потом умножение на 100, то, если бы оптимизатор видел значение, сразу получилось бы 1 (плюс-минус). Но если оптимизатор не видит значение, он не сможет это соптимизировать и умножение на 100 останется.
    • Нет возможности использовать этот массив в constexpr выражениях, шаблонах.
    • Другая проблема — aliasing. Ссылка на double может указывать на ту же ячейку памяти, как в примере с -fno-strict-aliasing при изменении этого double компилятор будет перечитывать значение из памяти для этой переменной.

    Это серьезное негативное влияние на производительность.

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

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

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

    3. Мы потратили 1Kb L1 кеша из 16/32Kb

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

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

    Ахо, Сети, Ульман. Компиляторы. Принципы, технологии, инструменты. 2ed.2008

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

    Разработчик стандартной библиотеки C под Linux Ульрих Дреппер написал труд «What Every Programmer Should Know About Memory», то есть о том, что каждый программист должен знать о памяти. В нем намешана серьезная теория и физика, но есть замечательный простой пример важности кеша. На куске кода с переумножением матриц, не меняя практически алгоритм и ассемблерные инструкции, Ульрих Дреппер ускорил производительность в 10 раз просто за счет более эффективной работы с кешом данных.

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

    Станет ли быстрее с таким кешированием единиц или нет — непонятно:

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

    Но люди написали кучу кода, а мы потратили кучу времени на его разбор. Когда вы его встретите в чужом продакшн-коде, вы тоже потратите кучу времени на разбор, ваша производительность упадет. Работодатель будет недоволен.

    Мы уже поговорили о «вредном», перейдем к хорошему.

    Идеальный велосипед


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

    1. кроссплатформенная;
    2. быстрая;
    3. полезная;
    4. функциональная
    5. пригодится большому количеству людей,


    добро пожаловать в рабочую группу РГ21, мы:

    • Поможем с формальностями.
    • Поможем с принятием в Boost.
    • Поможем с написанием proposal.
    • Защитим ваши интересы на международном заседнии при ISO, передадим отзывы на ваше предложение.

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

    Идеи в разработке РГ21:


    • P0539R0: wide_int by Игорь Клеванец, чтобы можно было писать int256, int512, int4000000;
    • P0275R1: Dynamic library load;
    • ConcurrentHashMap by Сергей Мурылев, Антон Малахов — пока очень ранний этап;
    • Constexpr: «D0202R2: Constexpr algorithm», std::array — добавление везде, где только можно;
    • Улучшение поддержки динамических библиотек в стандартной библиотеке (?dlsym?);
    • Stacktrace в стандартной библиотеке, чтобы можно было иметь класс Stacktrace, который в поток можно вывести и посмотреть Stacktrace, например, что происходило до этого, почему мы здесь упали.
    • Множество мелочей, которые делают все в ISO WG21 — это исправление мелких недочетов стандарта, стенографирование заседаний и куча других дел.

    Заходите на сайт рабочей группы https://stdcpp.ru/, там можно предложить свою идею, посмотреть, что предлагают другие, а самые интересные предложения мы обсудим вместе.

    Узнать о других докладах Антона, посмотреть его презентации, публикации и множество другой полезной информации можно здесь — http://apolukhin.github.io/

    Эта статья — расшифровка одного из лучших докладов наших друзей C++ Russia 2017, ближайшая их конференция в этом году пройдет уже в апреле с 19 по 21 число.

    Открывать конференцию в этом году будет Jon Kalb, разработчик с 25-летним стажем
    В течении этого времени успел поработать в Amazon, Microsoft, Netscape,
    Yahoo и других компаниях. Jon — организатор конференции CppCon. Автор книги
    C++ Today: The Beast is Back.

    А мы пока активно работаем над программой фестиваля конференций Российские интернет-технологии (РИТ++), до 9 апреля еще можно успеть подать заявку на доклад, и выходим на финишную прямую. Обещаем, что серверный блок будет представлен очень хорошо, хотя и про другие можно сказать то же самое.
    Конференции Олега Бунина (Онтико)
    486.94
    Конференции Олега Бунина
    Share post

    Comments 102

      0
      —У нас здесь указатель на 64-битной платформе — это 8 байт, у нас size тоже на 64-битной платформе — это опять 8 байт. Это 16 байт — в них можно сохранить 15 символов! Что, если пользоваться этими двумя переменными не как переменной-указателем и переменной size, а прямо поверх них располагать данные.

      хм. А рассматривались ли варианты сделать layout строки с битовым флагом?
      Например
      union string_data {
          struct heap_data {
              size_t flag : 1;
              size_t size : sizeof(size_t)*8-1;
              size_t capacity;
              void *buff;
          } heap;
      
          struct stack_data {
              uint8_t flag : 1;
              uint8_t size : 7;
              char buff[sizeof(heap_data)-1];
          } stack;
      };
      


      Размер буфера строки на x64 увеличивается с 16 до 23, 7 бит гарантированно вмещают размер буфера на стеке. Если я не ошибаюсь, проверка строки стек/куча будет не дольше. Минусы: нет поддержки строк с size > 2^63 и стоимость сдвига (1 такт) при работе с size.
        0
          0
          а в реализациях STL? И, если нет, почему?
            0
            В реализации стандартной библиотеки может быть любая имплементация. Например GCC предпочитает жертвовать несколькими символами, но держать валидный указатель — эту убирет if на каждую операцию.
              0

              В этом ответе на SO есть обзор реализаций в стандартных библиотеках https://stackoverflow.com/a/28003328/4451432

          +1
          Спасибо за статью, обожаю плюсы.
            0
            обезательно ли его нужно помечать noexcept.

            А не может ли кто-нибудь проявить на это свет? Я конечно, рад что можно сказать = default мув конструктору, но не всегда же они дефолтные.
            У нас в проекте не принято расставлять noexcept, только если для самих-себя, т.е. в теле метода точно есть catch всего или ему вылетать неоткуда и использующему надо точно это знать. Но ситуация с вектором всегда напрягала.
            Действительно ли noexcept делает что-то полезное? А если исключение все таки вылетит от туда?
              +1
              std::vector и прочие контейнеры на этапе компиляции проверяют, является ли класс is_noexcept_(movable/copyable/constructible/...) и в ряде случаев используют разный код для noexcept и не-noexcept случаев, чтобы гарантировать корректность состояния контейнера при возможном исключении, но использовать более быстрый вариант если исключение невозможно. Самый простой пример — std::vector::push_back() для пустого вектора.

              А если исключение все таки вылетит от туда?

              если внутри noexcept функции возникает необработанное исключение, вызывается std::terminate. Т.е. не вылетит
                0

                Скорректирую вопрос. Если явно не поменить, что noexcept, и не использовать мув-конструктор по умолчанию, то всегда будет выбираться noexcept вариант (т.е. в случае вектора — медленное копирование)? Правило жесткое на уровне языка или есть маневр для компилятора, что он сам вычислит, что исключений не будет?

                  0
                  Результат noexcept(...) опирается на гарантии языка. Нет гарантий — будет подставлена ветка с исключениями, которую дальше компилятор может оптимизировать в силу собственного разумения. Но даже если компилятор и умеет сложные оптимизации (например, выкинуть new+copy+delete) ему может банально не хватить контекстуальной информации.
              +2
              Ой какие знакомые грабельки)
              Остаётся только со всем согласиться. И ещё предложить добавить трик, учитывающий проблему ссылок и strict-aliasing: если так сложилось, что в performance critical код приходит переменная (особенно POD) по ссылке, то имеет смысл сделать временную служебную переменную по значению, в которую сразу загрузить то, что было по ссылке, и использовать её. Тогда мы обезопасим себя от бесконечных загрузок значения из памяти через ссылку. Наблюдал в таких условиях десятикратные приросты скорости.
              Не спроста стараются передавать POD переменные по значению, но во первых, бывает legacy, а во вторых, — тип может быть под шаблоном, который не всегда развернётся в POD.
                0
                Еще одна причина — чтобы точно понимать как это работает. Особенно если функционал касается денег.
                  +1
                  Это работает с точностью до наоборот: количество ошибок в ПО, работающем с деньгами, на несколько порядков больше чем в любом другом проекте.

                  Если не верите — сделайте не долларовый перевод из небольшого европейского банка в небольшой российский. У вас будут неплохие шансы натолкнуться на «неподдерживаемая кодировка», «получены не все поля, необходимые дле перевода» и т.п.
                    –1
                    Кодировка в C++ это отдельная беда. Очень приятно, что в современных (без обид, господа ярые сторонники C++) языках эту проблему решают в начале дизайна языка.
                      +3
                      Кодировка (точнее, проблема зоопарка кодировок) беда прежде всего винды. В цивилизованном мире просто используется UTF-8.
                        0
                        Современные — это какие? Пока что худшее, что я видел — это Python3. C++ отдыхает.
                    –1
                    мы из двух потоков будем пытаться одновременно менять динамический счетчик ссылок use_count.

                    Многоядерные процы и hyperthreading, которые упоминались в связи с этим, на самом деле тут не особо при чём. Хотя они и увеличивают шансы напороться на race condition по сравнению с одноядерными, но не создают их там, где их не было — многозадачные ОС вполне прозрачно организуют многопоточность (и все её проблемы — тоже) вне зависимости от количества ядер.

                      0
                      Атомарная инструкция выполняется на процессоре, ОС о ней ничего не знает.

                      Одновременно может сработать только одна rmw атомарная инструкция, остальные должны будут «попытаться еще раз, позднее».
                        0
                        Видел я адскую реализацию атомика от микрософта, замкнутую на системный мьютекс. По разному бывает.
                          +1
                          это fallback implementation для типов, размер которых превышает поддерживаемый атомарными операциями.
                          0

                          Где вы там атомарную инструкцию увидели? Или вы обсуждаете какой-то другой код, не тот что в статье?


                          1
                          class string {
                            string_impl*impl;
                          public:
                            char& operator[](size_t i) {
                              if (impl->use_count > 1)
                                *this = clone();
                              }
                              return impl->data[i];
                            }

                          2
                          class string {
                            string_impl*impl;
                          public:
                            ~string() {
                              --impl->use_count;
                              if (!impl->use_count) {
                                delete impl;
                              }
                            }
                          };
                            0
                            class string_impl {
                              char* data;
                              size_t size;
                              size_t capacity;
                              atomic<size_t> use_count; //<=== атомарная переменная. Все операции над ней выльются в атомарные инструкции на x86
                              // ...
                            };
                              –1
                              А вот вы мне объясните такую вещь. Когда это у нас std::string стал mt-safe? И если он не mt-safe, то каким образом он у вас окажется в многопоточном контексте сам по себе? На каком основании вы требуете mt-safe от COW-строки?
                                0
                                На основании того, что иначе многопоточные программы на C++ писать невозможно. GCC 4.x так делает, например.
                                  0
                                  Точно так же, как и с дефолтным std::string. Тут можно пытаться ехать в сторону «а как нам пошарить две одинаковые строки между тредами», но это так же не является проблемой. Решается одним методом, который делает реальную копию.
                                    0
                                    Если на большинстве компиляторов (где нет COW) это работает без дополнительных методов, то ваш COW нужно закрутить так, чтобы он тоже работал, извините.
                                  0
                                  Есть отличный коментарий с ютуба от Konstantin Akimov:

                                  Смотрите:
                                  string a = «abc»;
                                  string b = a;

                                  Запускаем process(a) в треде 1, запускаем process(b) в треде 2. Мы имеем 2 разных переменных в двух разных тредах, но они обе указывают на одну область памяти, нужно обеспечить из-за COW thread-safe для обоих тогда когда он как раз и не нужен. И на пользователя переложить нельзя, потому что это «кишки».
                                    –2
                                    Я уже ответил на это выше. Ничего не мешает сделать сделать метод copy для строки.

                                    И на пользователя переложить нельзя, потому что это «кишки».

                                    Тут и не нужны никакие кишки. Вызов clone/copy не является кишками. Шарить «cow-копии» строки между тредами нельзя, так же как и ссылки, так же как и мувить из другого треда и прочее.

                                      +2

                                      А как реализовать деструктор для COW строк без atomic ref counter?


                                      (при условии, что наша реализации должна соответствовать стандарту C++, которая не запрещает передавать копии строки в другие потоки)

                                        –2
                                        (при условии, что наша реализации должна соответствовать стандарту C++, которая не запрещает передавать копии строки в другие потоки)

                                        А зачем вы пытаетесь придумывать какие-то новый условия? Никто не сравнивал реализацию std::string с COW и без COW. Сравнивали COW-велосипед, а теперь вы пытаетесь превратить COW-велосипед в «std::string с COW». Как так получилось?

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

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


                                          Например, если последовать вашему совету — убрать atomic rc из string, который рассматривается в статье, то код:


                                          string a="abc";
                                          string b=a;
                                          process (a);
                                          process (b);

                                          Будет гарантированно рейсить в момент освобождения памяти, в которой лежит массив байтов "abc".
                                          Что бы этого избежать, прийдется постоянно держать в голове, что в проекте своя реализация string, копии которого нельзя передавать в потоки.


                                          Согласитесь, не плохая подстава для новых людей на проекте.

                                            –3
                                            На мой вкус, если называешь свой велосипед именем стандартного контейнера

                                            С каких пор какой-то стандарт приватизировал имя string? Оно было ещё тогда, когда этого стандарта в проекте не было, как и С++.

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

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

                                            Что бы этого избежать, прийдется постоянно держать в голове, что в проекте своя реализация string, копии которого нельзя передавать в потоки.

                                            Чтобы этого избежать — постоянно надо держать в голове, что просто замувить что-то нельзя. Дальше что? Я что-то не вижу от вас тех же рассуждений в адрес move?

                                            Согласитесь, не плохая подстава для новых людей на проекте.

                                            Я обсуждаю тему в рамках тезисов определённых в статье. Хотите использовать другие тезисы — поменяйте их в статье.

                                              +3

                                              Попробую еще раз, с комментариями


                                              // Функция process получает str по значения и не может  модифицировать переданный ей аргумент str
                                              void process (string str);
                                              ...
                                              string a="abc";
                                              string b=a;
                                              process (a);
                                              process (b);
                                              // в этом месте без atomic rc в объектах a и b может быть все что угодно. 
                                              cout << a; // наша программа в этом месте "внезапно" упала.
                                              

                                              И при чем тут move?
                                              Естественно, move имеет право модифицировать исходный объект.

                                    +3
                                    Когда это у нас std::string стал mt-safe?

                                    С тех самых пор, как появились потоки и само понятие потокобезопасности, как следствие — то есть с C++11. Все классы потокобезопасны (на базовом уровне), если не оговорено обратное; в частности, здесь применимо следующее правило:
                                    Implementations may share their own internal objects between threads if the objects are not visible to users and are protected against data races.
                                    (С++11/14, 17.6.5.9 Data race avoidance, абзац 7
                                    C++17, 20.5.5.9 Data race avoidance, абзац 7)

                                    На каком основании вы требуете mt-safe от COW-строки

                                    В C++ нет понятия «COW-строка», есть просто «строка». COW — это один из возможных видов реализации, про которые пользователь ничего знать не обязан, ибо инкапсуляцию никто не отменял. Связанные с COW проблемы потокобезопасности лежат исключительно на разработчиках стандартной библиотеки.
                                      –2
                                      С тех самых пор, как появились потоки и само понятие потокобезопасности, как следствие — то есть с C++11. Все классы потокобезопасны (на базовом уровне), если не оговорено обратное; в частности, здесь применимо следующее правило:

                                      К чему это написано и спащена цитата ниже? Спащенная цитат имеет отношение к нюансам реализации. «Если вы используете потоки в реализации — вы должны сами обеспечивать их безопасность», но из этого никак не следует то, что строка mt-safe.

                                      В C++ нет понятия «COW-строка», есть просто «строка».

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

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

                                      Неверно. Вы можете мне попытаться показать, где в статье говорилось об cow-реализациях std::string. Да, там приводились в примеры cow-реализации std::string(старого), но ими дело не ограничивалось. std::string там приведён на правах истории, как объяснение того — почему раньше так было в std::string.

                                      Да что говорить — там даже эта строка есть:
                                      Начиная с C++11 COW строчки запрещены в стандарте. Там наложены специальные условия на строчку, что COW реализовать невозможно. Все современные имплементации стандартных библиотек не имеют COW строк.


                                      Т.е. автор явно не сравнивает std::string и std::string. Это следует и из множество других мест.

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

                                      Осталось только понять — откуда вы взяли всю эти историю со стандартной библиотекой? Сами придумали? А какое отношение ваши придумки имеют к теме?

                                      Автор дал определение «cow-велосипед», который никаким образом не является стандартной библиотекой и не является имплементацией std::string.
                                        +2
                                        К чему это написано

                                        К вашему вопросу «Когда это у нас std::string стал mt-safe?».

                                        и спащена цитата ниже?

                                        Цитата из стандарта C++.

                                        «Если вы используете потоки в реализации — вы должны сами обеспечивать их безопасность», но из этого никак не следует то, что строка mt-safe.

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

                                        «Реализация» — это компилятор+стандартная библиотека, если что. В частности, реализация std::string.

                                        Потокобезопасность std::string (в том смысле, что два потока могут параллельно работать с двумя разными объектами std::string, пусть даже полученными из одного объекта std::string присваиванием или конструктором копии) следует из всей совокупности требований раздела «Data race avoidance», в частности:
                                        A C++ standard library function shall not directly or indirectly access objects (1.10) accessible by threads other than the current thread unless the objects are accessed directly or indirectly via the function’s arguments, including this.
                                        A C++ standard library function shall not directly or indirectly modify objects (1.10) accessible by threads other than the current thread unless the objects are accessed directly or indirectly via the function’s non-const arguments, including this.


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

                                        Я отвечаю на ваш комментарий про якобы потоконебезопасный std::string, а не на статью.

                                        Вы написали два вопроса про std::string и один — про COW-строки, таким образом, словно это три вопроса на одну и ту же тему.
                                    0
                                    Ваш процитированный код расположен в статье после заявления о том, что виноваты multi-core процессоры, в качестве исправления той проблемы. Так что на момент описания проблемы этот код ещё не используется. Я в своём первом комментарии как раз писал о том, что этот код нужен вне зависимости от того, сколько ядер в проце, потому как без него может случиться (хоть и с меньшей вероятностью) race и на одном ядре с разделением времени между потоками.

                                    Впрочем, сейчас посмотрел внимательнее — появилась ещё одна претензия к статье — ибо даже этот код от race может не спасти. Посмотрите на деструктор ~string ещё раз. Там сначала делается декремент, а потом переменная сравнивается с нулём (и atomic тут не защищает). Между этим декрементом и сравнением теоретически может произойти переключение на другой поток, который сделает ещё один декремент. После чего либо оба потока увидеть use_count==0 с сделают double-delete, либо второй из этих потоков сделает UB обращением к impl->use_count уже освобождённого соседним потоком impl. Возможно, компилятор оптимизирует декремент + сравнение в одну операцию (и тогда скомпилированный код станет хорошим даже без atomic<>), но в любом случае делать он этого не обязан, а в зависимости от деталей реализации класса atomic<> может оказаться что и вообще не имеет права.
                                    Хотя наверно эта проблема обходится через if(!--impl->use_count) — тут явно указано что надо брать именно результат декремента, а не содержимое переменной после него.
                                      0
                                      Извиняюсь, код должен выглядеть как
                                      class string {
                                        string_impl*impl;
                                      public:
                                        ~string() {
                                          const bool is_used = --impl->use_count;
                                          if (!is_used) {
                                            delete impl;
                                          }
                                        }
                                      };
                              0
                              А потому, что добавили опцию -fno-strict-aliasing. Она говорит компилятору о том, что два типа данных, абсолютно разных, никак друг с другом не пересекающихся, все равно могут находиться в одной и той же ячейке памяти.

                              В C для указателей для этого есть restrict — что бы явно указать, что не надо подозревать два указателя пересекающимися (причём это работает и если они одинакового типа). На локальные переменные эти подозрения и так и так не распространяются (если только вы где-то не применили к ним оператор &) а ссылок там нет. Не в курсе касательно C++ но возможно там есть какой-нить restrict для ссылок — было бы очень хорошо, потому как strict-aliasing реально можно много чего испортить.

                                +2
                                Стандартного restrict-а нет, но есть как расширение, например, в gcc (__restrict__/__restrict).

                                Если -fstrict-aliasing что-то «испортил», код в любом случае надо переписывать. К тому же, он включается по умолчанию уже на -O2.
                                0
                                static const std::vector<std::string> CONSTANTS = {
                                
                                  "Hello",
                                  "Word",
                                  "!"
                                };
                                А ещё для этого есть библиотеки с compile-time контейнерами, например frozen и sprout.
                                  0
                                  Прямо из вектора строка перетянется внутрь контейнера res. Никаких динамических аллокаций в итоге не будет.


                                  Как это реализуется технически? Не могу себе представить другой реализации кроме как обмен ссылок, но тогда контейнеры должны хранить указатели, а не сами объекты, что приводит к замедлению чтения данных из контейнера.
                                    +1
                                    Поля объекта string побайтно (примерно так) копируются, выделенная в куче память для данных — остаётся на месте (сама строка в общем случае хранится не в объекте string а по указателю из него). Если компилятор умный то он может и копирование полей объекта местами соптимизировать.
                                    +1
                                    При этом компилятор даже не поверит вам, если вы везде напишите const, потому что он не оптимизирует, основываясь на const. Если вы где-то написали const, компилятор проигнорирует это, потому что где-то в другом месте вы могли написать const_cast.


                                    Оптимизирует. Пример (присваивание *ptr = 9; может изменить x2, но не x1): godbolt.org/g/QPvwup С массивами получается аналогично.

                                    Модификация константного объекта (посредством const_cast или другими путями) — неопределённое поведение, компилятор всегда имеет право полагать, что такого не происходит.

                                    Другое дело, если нам передали параметр типа const T& или const T* и он ссылается на на самом деле неконстантный объект.
                                      +1
                                      Например, есть два потока, в них по строке, которые ссылаются на общий динамический объект. Если потоки работают со строками и одновременно решают их удалить, получается, что мы из двух потоков будем пытаться одновременно менять динамический счетчик ссылок use_count. Это приведет к тому, что либо возникнет утечка памяти, либо приложение аварийно завершится.

                                      Либо всё будет хорошо. Либо прилетят назальные демоны.


                                      Ну серьезно, сколько можно с серьезным лицом описывать последствия UB, если они непредсказуемы?

                                        0
                                        Тем не менее, вероятность конкретных последствий на распространенных платформах с распространенными компиляторами выше остальных. О вероятности уже рассуждать можно.
                                        0
                                        Неплохо было бы написать вам книгу по типу «Эффективный современный С++», где были бы наиболее актуальные советы, включая C++17 :)
                                          –6
                                          Закапывайте уже это разложившийся труп ЦЭПЛУСПЛУС, хватит его насиловать
                                            +1
                                            То есть вместо std::vector<std::string> CONSTANTS можно написать std::string_viewCONSTANTS[].


                                            Нельзя просто так взять и заменить std::string на std::string_view, ведь в очень многих кейсах нужна c_str(). Да, по факту там будет си-строка, но завязываться на это мы не можем.

                                            Это касается и первого случая.
                                              +1

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

                                              0
                                              Не хочу показаться грубым, но

                                              Caching divs


                                              Вы не понимаете талмуд и вообще всю эту тему с тактами:

                                              Залезаем в талмуды, где описано, сколько тактов занимают инструкции, и обнаруживаем, что доступ к элементу массива, который находится в L1 кеше, занимает 5 тактов, а деление — 22-29 тактов. Итого такое кеширование может быть в 2-4 раза быстрее, но…

                                              Во-первых, 2раза ещё можно как-то объяснил отсылкой к l2, но 22-29 — это более пяти раз.

                                              Во-вторых. Вы показываете не фпешный див для 32битных чисел в контексте даблов.

                                              Третье — вы совсем не понимаете этих цифр. На самом деле там не 5тактов, чтение пайплайновое, дак и к тому же параллельное. Там от 0.5тактов, что уже в 50раз. На самом деле там разница до 100раз, ведь деление не обладает этими свойствами. Именно поэтому и оптимизируют деление.

                                              Четвёртое. Это скорее всего не «Caching divs» — это n / m (~)== n * (1 / m) — поэтому аргумент уровня:

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

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

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

                                              Если у вас будет обращение к 1/100, а потом умножение на 100, то, если бы оптимизатор видел значение, сразу получилось бы 1 (плюс-минус). Но если оптимизатор не видит значение, он не сможет это соптимизировать и умножение на 100 останется.

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

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

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

                                              Оба тезиса не имеют никакого отношения к Caching divs, а имеют отношение к конкретной реализации. Ничего не мешает таблицу вынести в хедер со статик, либо сделать её constexpr.

                                              Другая проблема — aliasing. Ссылка на double может указывать на ту же ячейку памяти, как в примере с -fno-strict-aliasing при изменении этого double компилятор будет перечитывать значение из памяти для этой переменной.

                                              Если оно будет алиасится, то в 95% случаев — с другими даблами, и уже только потом с чем-то другим. Никакой strict-aliasing этому не поможет. К тому же. В случае со static, либо constexpr — никакой из этих проблем не будет.

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

                                              Зачастую эти люди имеют мало отношения к практики, но дело даже не в этом. Ссылка на это ничего не даёт, ведь эти тезисы бессмысленны. Это некие общие рассуждения, которые к данному контексту отношения не имеют.

                                              Естественно, что в тех кейсах, которые завязаны на летенси памяти — всё будет упираться в кэш. Это уровень КО. И что самое главное — подобные рассуждения существуют только потому, что интел сделал alu с летенси 1 такт. Как только дело касается плавучки, где такой халявы нет — все эти истории работают слабо.

                                              И что самое важное. l1d — это уровень именно «скорости процессора», как и все операция связанные с ним — завязаны на процессоре, на инструкциях и работе с ними.

                                              Причины просты — если этот код не является горячим, то его в кэше ИТАК НЕ БУДЕТ, а если он является горячим, то он ГОРЯЧИЙ, а значит от времени ЕГО исполнения ЗНАЧИТЕЛЬНО зависит время работы ПРОГРАММЫ в целом.

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

                                              Полная глупость.

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

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

                                              Естественно, что важны любые ресурсы и оптимальное их использование даёт профит. Но из этого не следует «вычислительное время неважно». Она так же важно. И самое важное — тот-то в glibc весь код на асме. Не нужно ведь — там всякие строки и прочая работа с памятью. Ан нет.

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

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

                                              Но люди написали кучу кода, а мы потратили кучу времени на его разбор. Когда вы его встретите в чужом продакшн-коде, вы тоже потратите кучу времени на разбор, ваша производительность упадет. Работодатель будет недоволен.

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

                                                0
                                                читается лишь несколько соседних элементов

                                                On x86 cache lines are usually 64 bytes. Если кешировать флоаты, к примеру, но выходит 16 элементов, что не так уж и мало.
                                                  0
                                                  Абсолютно неважно сколько их там выходит — из этого ровным счётом ничего не следует.
                                                    0
                                                    а если выходит 100?
                                                      0
                                                      Да хоть мильён — какая разница? Это свойство памяти — она не читается по 1/2/4/8 байт — она читается кешлайнами и любая память читается только через кэш(за исключением nt). Это не свойство это таблицы — это глобальное свойство, которое распространяется на все чтения в программе.

                                                      На любое чтение — процессор прочитает кешлайн. Если этот кешлайн далее не нужен — он вытеснится чтением другого кешлайна. И это, ровным счётом, ни на что не повлияет.

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

                                                          Это ни из чего не следует. По крайней мере я не вижу связи, но вы можете мне её показать. Внимательно слушаю.
                                                            +1
                                                            Что бы работало вытеснение, нужно что бы те объекты, к которым нет обращения могли быть вымыты из кеша. Поскольку в реальности вытеснение идет на уровне линий, то достаточно что бы хоть один элемент из линии использовался, что бы заблокировать вытеснение всей линии. В результате эффективность вытеснения тем ниже, чем больше размер кеш линии по отношению к размеру элемента. Если размер кеш линии уже порядка размера всего кешируемого массива — вытеснение почти не работает. В результате может получится, что «несколько соседних элементов» — это практически весь кешируемый массив и есть. В случае с массивом на 100 флоатов (400 байт) и линией на 64 байта, при случайном доступе достаточно задействовать примерно 8-10 флоатов из 100 что бы исключить вытеснение и забить кеш.
                                                              –2
                                                              Что бы работало вытеснение, нужно что бы те объекты, к которым нет обращения могли быть вымыты из кеша.

                                                              Это не имеет смысла. Зачем вы пытаетесь общие вещи натянуть на конкретный случай? Общие вещи не относятся к данному случаю — ведь они на то и общие.

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

                                                              Неверно. Абсолютно неважен размер элемента — память считается не в элементах.

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

                                                              Работает.

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

                                                              Может, но из этого ничего не следует. Это явно не этот массив, да и даже если бы был этот — это ничего не меняет.

                                                              В случае с массивом на 100 флоатов (400 байт) и линией на 64 байта, при случайном доступе достаточно задействовать примерно 8-10 флоатов из 100 что бы исключить вытеснение и забить кеш.

                                                              Неверно. Во-первых, как я уже говорил — это попытка натянут сову на глобус.

                                                              Во-вторых, это ничего не меняет, ведь будет вытеснятся тот кешлайн, в который было прочитано предыдущие значение. Описанное вами может случится только в том случае, если эти 8-10 элементов ГОРЯЧЕЕ ДРУГИХ данных, а значит — другие данные объективно менее важные. А то, что ненужно — то неважно. И есть ли ненужны данные в кэше, либо их нет — абсолютно неважно.

                                                              Повторю ещё раз. Тут есть два основных тезиса Первый общий и предпосылки к нему формулируются так «чтение какого угодно куска памяти — триггерит чтение куска данных шириной в кешлайн»", а далее — все вытекающие. Но а) этих вытекающих почти нет, б) они итак есть везде и эта «таблица» — не исключение.

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

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

                                                              Слишком притянуто за уши.
                                                                0
                                                                память считается не в элементах.
                                                                А я про количество элементов и не писал. Я писал про их _размер_ (в байтах) по отношению к размеру кеш-линии (тоже в байтах).
                                                                будет вытеснятся тот кешлайн, в который было прочитано предыдущие значение
                                                                не будет. на след такте он снова понадобится.
                                                                они итак есть везде и эта «таблица» — не исключение.
                                                                Не исключение. Просто при расчёте того, на сколько кеширующая таблица зафлудит кеш нужно считать не среднее число используемых элементов в некий короткий промежуток времени (скажем ~100-1000 тактов), а среднее число используемых кеш линий. Вытеснение определяется не размером элемента (в байтах) и таблицы, а размером кеш-линии и распределением обращений по таблице. При таблице в 400 байт (100 флоатов) и 10 случайно распределенных релевантных (на промежутке в 100 тактов) элементов, на эти 100 тактов, будет забито 384 байта кеша, а не 40 байт. Выходит, что при 10% использовании таблицы кеш будет зафлужен на ~100% размера таблицы. И это вполне обычный сценарий использования таких таблиц. Я не беру самый неблагоприятный случай, когда достаточно что бы каждый 16й элемент был задействован. Я беру именно 10% случайно распределенных элементов. Конечно, могут быть и более благоприятные, но проблема именно в том, что столкнуться с неблагоприятным очень легко.
                                                                  +1
                                                                  А я про количество элементов и не писал. Я писал про их _размер_ (в байтах) по отношению к размеру кеш-линии (тоже в байтах).

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

                                                                  Просто при расчёте того, на сколько кеширующая таблица зафлудит кеш нужно считать не среднее число используемых элементов в некий короткий промежуток времени (скажем ~100-1000 тактов)

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

                                                                  Второе — промежуток времени никого не интересует и ничего не значит. И вам уже объяснили почему.

                                                                  При таблице в 400 байт (100 флоатов) и 10 случайно распределенных релевантных (на промежутке в 100 тактов) элементов, на эти 100 тактов, будет забито 384 байта кеша, а не 40 байт.

                                                                  Не будет.

                                                                  Выходит, что при 10% использовании таблицы кеш будет зафлужен на ~100% размера таблицы.

                                                                  Не будет.

                                                                  Я не беру самый неблагоприятный случай, когда достаточно что бы каждый 16й элемент был задействован. Я беру именно 10% случайно распределенных элементов. Конечно, могут быть и более благоприятные, но проблема именно в том, что столкнуться с неблагоприятным очень легко.

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

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

                                                                  Если у нас есть горячие данные в кэше, то абсолютно неважно сколько вы там будите читать, хоть каждый 16элемент — занимать это будет ровно ОДИН кешлайн. Хоть там будь терабайт табилцы — это ничего не изменит.

                                                                  И только тогда, когда ваши данные из таблице станут горячее других данных — в кеше будут оставаться данные из таблице, но в этом случае таблица станет узким местом, а раз таблица быстрее вычислений — таблица себя оправдает.
                                                                    0
                                                                    Если у нас есть горячие данные в кэше, то абсолютно неважно сколько вы там будите читать, хоть каждый 16элемент — занимать это будет ровно ОДИН кешлайн. Хоть там будь терабайт табилцы — это ничего не изменит.


                                                                    Глупость. Процессор не умеет делать арифметику с данными из памяти напрямую. Поэтому он читает их в кеш.

                                                                    Кеши устроены в виде хеш таблицы, где корзинка выбирается как (memory address) / (line size) % (number of sets), а в корзинке хранится обычно 4 элемента. Итого: какими бы мусорными данными не были, они выкинут одно данное из строго определённой корзинки.

                                                                    Чтобы не позорится в дальнейшем, ознакомьтесь с «Optimizing software in C++» от Agner Fog
                                                  0
                                                  Хотелось бы сделать небольшое замечание, касательно быстрого деления на число. На самом деле кеширование результата операции целесообразно только для деление на небольшое число. Кроме того доступ к закешированным данным плохо векторизуется. Если деление настолько массовая операция, то наиболее оптимально будет ее выполнять на лету при помощи векторных инструкций. Нашел пример с умножением по модулю:
                                                  stackoverflow.com/questions/46790237/vectorization-of-modulo-multiplication/46790553#46790553
                                                    0
                                                    На самом деле кеширование результата операции целесообразно только для деление на небольшое число.

                                                    Это абсолютно неважно. Число может быть каким угодно — определяющим является их кол-во, а не то «большое» оно, либо нет.

                                                    Кроме того доступ к закешированным данным плохо векторизуется.

                                                    Неверно. Можно хранить целые вектора, либо есть броадкаст. Да что там далеко ходить — по вашей ссылки есть пример:

                                                    __m128 _k = _mm_set1_ps(1.0f / p);

                                                    Это именно одно число с «броадкастом», ничего не мешает подставить сюда число из таблицы.

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

                                                    Таблица таблице рознь, но до — таблица не векторизуется и они почти полностью бесполезны при векторизации.

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

                                                    Этот пример никакого отношения к тому, о чём вы говорите — не имеет. Это оптимизация деления на констанату, которая вычисляется не «при помощи векторных инструкций», а банальным делением, а потом используется как константа при вычислениях.

                                                    Если у вас константа одна и её можно предрассчитать, то проще предрассчитать, но не всегда и не везде. К тому же — есть множество кейсов, где длинна предвычисление будет стоит дорого, неоправданно дорого.

                                                    В данном примере просто векторизуется операция int(float(d)/float(p))*p. Причём очень колхозно. И самое интересное — этот же пример вас опровергает. Это деление будет исполнятся значительную часть от самого цикла. 10-20+% и это лишь потому, что флоат-деление достаточно халявное. К тому же флоаты тут явно не подходят, ведь их точности на инт не хватит — нужны даблы. Там уже ситуация будет куда хуже.

                                                    К тому же, не стоит забывать, что данная реализация слишком кастыльная — там почти всё время тратится на касты. Будь это изначально флоаты/даблы — мы бы потеряли не 10-20%+, а все 100%+.

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

                                                      0
                                                      Да пример не самый удачный. Тем не менее даже с учетом конвертации туда и обратно, fp деление будет быстрее, потому как векторизуемо.
                                                        –2
                                                        Быстрее чего? Какое деление? Откуда оно взялось? О чём вы вообще говорите?

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

                                                        Ваш пример — это 1в1 то, что критиковал автор, а именно — кэширование 1/n, а после использование этого коэффициента для замены деления на умножения. При его вычисление НЕ ИСПОЛЬЗУЕТ НИКАКИХ " выполнять на лету при помощи векторных инструкций. ", вообще никаких векторных инструкций.

                                                        Никакого отношения ваш пример к векторизации деления не имеет. Повторюсь уже в 3-4раз.
                                                          +2
                                                          Я не поленился и проверил скорость деления с применением закешированного значение и напрямую с использованием SSE:
                                                          #include <emmintrin.h>
                                                          #include <windows.h>
                                                          #include <inttypes.h>
                                                          #include <vector>
                                                          #include <iostream>
                                                          
                                                          float fractions[256];
                                                          
                                                          void Div1(const float * a, const int * b, size_t n, float * c)
                                                          {
                                                          	const int step = 4;
                                                          	for (size_t i = 0; i < n; i += step)
                                                          	{
                                                          		c[0] = a[0] * fractions[b[0]];
                                                          		c[1] = a[1] * fractions[b[1]];
                                                          		c[2] = a[2] * fractions[b[2]];
                                                          		c[3] = a[3] * fractions[b[3]];
                                                          		a += step;
                                                          		b += step;
                                                          		c += step;
                                                          	}
                                                          }
                                                          
                                                          void Div2(const float * a, const int * b, size_t n, float * c)
                                                          {
                                                          	const int step = 4;
                                                          	for (size_t i = 0; i < n; i += step)
                                                          	{
                                                          		_mm_storeu_ps(c, _mm_div_ps(_mm_loadu_ps(a), _mm_cvtepi32_ps(_mm_loadu_si128((__m128i*)b))));
                                                          		a += step;
                                                          		b += step;
                                                          		c += step;
                                                          	}
                                                          }
                                                          
                                                          double GetFrequency()
                                                          {
                                                          	LARGE_INTEGER frequency;
                                                          	QueryPerformanceFrequency(&frequency);
                                                          	return double(frequency.QuadPart);
                                                          }
                                                          
                                                          double g_frequency = GetFrequency();
                                                          double Time()
                                                          {
                                                          	LARGE_INTEGER counter;
                                                          	QueryPerformanceCounter(&counter);
                                                          	return double(counter.QuadPart) / ::g_frequency;
                                                          }
                                                          
                                                          int main()
                                                          {
                                                          	for (size_t i = 0; i < 256; ++i)
                                                          		fractions[i] = 1.0f / i;
                                                          
                                                          	const size_t n = 1024 * 256, m = 256;
                                                          	std::vector<int> b(n);
                                                          	std::vector<float> a(n), c1(n), c2(n);
                                                          	for (size_t i = 0; i < n; ++i)
                                                          	{
                                                          		a[i] = (float)::rand();
                                                          		b[i] = (::rand() * 256) / RAND_MAX;
                                                          	}
                                                          
                                                          	double t1 = Time();
                                                          	for (size_t i = 0; i < m; i++)
                                                          		Div1(a.data(), b.data(), n, c1.data());
                                                          	t1 = Time() - t1;
                                                          	std::cout << "t1 = " << t1 * 1000 << " ms." << std::endl;
                                                          
                                                          	double t2 = Time();
                                                          	for (size_t i = 0; i < m; i++)
                                                          		Div2(a.data(), b.data(), n, c2.data());
                                                          	t2 = Time() - t2;
                                                          	std::cout << "t2 = " << t2 * 1000 << " ms." << std::endl;
                                                          
                                                          	return 0;
                                                          }
                                                          

                                                          У меня получилось, что второй вариант более чем вдвое быстрее (35 ms и 15 ms).
                                                    +2
                                                    Это оптимизация деления, которая не имеет смысла <...>

                                                    Так в этом и посыл: «Не делайте преждевременных оптимизаций».

                                                    Если оно будет алиасится, то в 95% случаев — с другими даблами, и уже только потом с чем-то другим. Никакой strict-aliasing этому не поможет. К тому же. В случае со static, либо constexpr — никакой из этих проблем не будет.

                                                    Вы говорите, что бездумное выключение оптимизацией компилятора, вместо исправления ошибок, это ОК? Или вы спорите ради спора?

                                                    Зачастую эти люди имеют мало отношения к практики, но дело даже не в этом.

                                                    Разработчики оптимизаторов имеют мало отношения к оптимизациям? Я вам не верю.

                                                    ######

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

                                                    Вы: Out Of Order Execution увидит что доступ к памяти и заранее постарается подтянуть данные в кеш, зачастую сводя на нет простои
                                                    Я: Это не гарантия. Если этот код будет стоять в начале одной из веток, branch predictor мог бы сплоховать и мы получили бы простой в полной мере.
                                                    Вы: Вы взяли количество тактов для целочисленного деления, вместо деления double
                                                    Я: Это просто неудачное название для деления на слайде. Да и современные процессоры, деление делают достаточно быстро. Так FDIV на Ivy Bridge занимает 10-24 тактов
                                                      –4
                                                      Так в этом и посыл: «Не делайте преждевременных оптимизаций».

                                                      Зачем вы пытаетесь врать и дёргать фразы из контекста? Там написано то, что если убрать таблицу и заменить её на деление — это не будет иметь смысла и вам объяснили почему. У вас получится x * (1 / m), что попросту не имеет смысла.

                                                      В этом ваша проблемы — вы не понимает того, о чём пишите. Это касается всего, и бездумное пасты «тактов» и из таблицы, и обвинение кода в непонятности, который понятен всем, кто имел отношение к оптимизации вычислений.

                                                      Вы говорите, что бездумное выключение оптимизацией компилятора, вместо исправления ошибок, это ОК? Или вы спорите ради спора?

                                                      Опять какое-то враньё. Где я говорил подобное? Покажите мне.

                                                      Разработчики оптимизаторов имеют мало отношения к оптимизациям? Я вам не верю.

                                                      Мне не нужно верить. Есть факты, которые мною доказаны: а) вы не понимаете тему, б) вы не понимаете матчасть. Поэтому извините, но ваши рассуждения об оптимизациях, тактах, понятности кода — стоят ноль.

                                                      И самое важное — мы опять видим враньё. Вы выдернули какую-то фразу из контекста, в которой вообще не говорится об «Разработчики оптимизаторов».

                                                      Давайте я перечислю вам всё ваше враньё.

                                                      Первое — оптимизации оптимизациям рознь. Один вид оптимизаций требует совершенного другого понимания, нежели другой. Как бы вам попроще объяснить. Берём llvm, в котором( на уровне ир, т.е. почти все) почти все оптимизации являются обобщёнными, т.е. они никак не учитывают таргет. Да, частично и в каком-то виде они могут это делать, но это крохи. В этом их смысл, ведь таргетов много.

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

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

                                                      Враньё второе. Вы написали это, а после «Разработчики оптимизаторов». Зачем? Разработчик компилятора — это далеко не только разработчик оптимизатора, вернее в подавляющем большинстве случаев это не так.

                                                      пишут книги на эту тему и защищают сложные теории

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

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

                                                      Это очередной пример того, как человек где-то услышал какую-то фразу и повторяет её везде. Зачем? Это ничего не стоит и ничего не значит. Это общие фразы, которые никакого отношения к конкретному случаю не имеют.

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

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

                                                      Вы мне не покажите «неправильно», в этом и проблема. Это не спор ради спора, не агрессия — это лишь ваши попытки свести дискуссию куда-то не туда.

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

                                                      Вы: Out Of Order Execution увидит что доступ к памяти и заранее постарается подтянуть данные в кеш, зачастую сводя на нет простои

                                                      Вы не понимаете того, о чём говорите. Зачем вы мои слова выдаёте какой-то малограмотный бред?

                                                      Я: Это не гарантия. Если этот код будет стоять в начале одной из веток, branch predictor мог бы сплоховать и мы получили бы простой в полной мере.

                                                      Опять — вы не понимаете того, о чём говорите. Ну и тут прослеживается явная попытка съехать с темы. В рамках конкретного примера можно почитать — будет там гарантия, либо нет. И ваши общие фразы — ничего не стоят.

                                                      Вы: Вы взяли количество тактов для целочисленного деления, вместо деления double

                                                      Нет, опять враньё. Вы не просто взяли не то, вы неправильно даже разделили 25+ на 5, не говоря уже о том, что там будет 4-5раз( в рамках вашей логики), но никак не 2-4. Т.е. тут проблема даже с банальной арифметикой.

                                                      Тут вы опять пытаетесь врать. Это не ваша основная проблема — ваша проблема( основная) в том, что вы пытаетесь кидаться какими-то цифрами, значения которых вы не понимаете. Зачем?

                                                      Я: Это просто неудачное название для деления на слайде. Да и современные процессоры, деление делают достаточно быстро. Так FDIV на Ivy Bridge занимает 10-24 тактов

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

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

                                                      Но я вам сообщаю — fpu сдохло во времена core2, а значит все fdiv«ы тоже. Такие дела.

                                                      Хотя о чём это я, 10-24такта — это в 20-48раз медленнее чтения из l1d.

                                                      Разберитесь в теме перед тем, как о чём-то рассуждать. Да, никто тут вас не поймает и можно с умным видом нести откровенный бред. И меня всегда можно заминусовать, но. Это ничего не изменит. Если вы хотите действительно говорить полезные вещи — изучите тему, а если нет — продолжайте в том же духе. Шансы на изобличение крайне малы.

                                                      Я хотел разобрать и то, что вы там наговорили на тему форсинлайна, но мне стало лень. И до сих пор лень. На самом деле везде, где вы пытаетесь говорить о матчасти — выходит полный бред.
                                                        +1
                                                        Прочитайте публикацию ещё раз, но внимательно. Вы додумываете факты которых в примере не было, приписываете мне отсебятину и оскорбляетесь на неё.
                                                          –3
                                                          Опять враньё, опять ноль аргументации. Опять попытка врать в надежде, что публике будет лень читать мой подробный разбор. Мне достаточно спросить:

                                                          Вы додумываете факты которых в примере не было

                                                          Где, покажите. Почему вы не показали ни одного примера?

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

                                                          Хорошо, возьмём пример, который будет понятен всем.

                                                          Разработчики оптимизаторов имеют мало отношения к оптимизациям? Я вам не верю.

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

                                                          И вы тут можете заметить то, о чём говорил я. Человек пытается врать, т.е. вначале он говорил об одном, а потом «разрабатывают компиляторы» пропали и появились «Разработчики оптимизаторов».

                                                          И мало того, я даже на эти «Разработчики оптимизаторов» ответил, но что мы видим? Видим игнор и очередное враньё.

                                                            +2
                                                            Ваш подробный разбор не стоит и выеденного яйца, потому что вы разбираете не пример из статьи, а что-то из своей головы. Откуда вы взяли «x * (1 / m)» мне не ведомо, почему вы вдруг считаете что мы на горячем пути — не понятно, из-за чего мы вдруг оказались в CPU bound примере — ????, почему на основе этих выдуманных фактов вы делаете какие-то выводы о компетентности — совсем не очевидно.

                                                            Давайте я разберу пример подробнее. Берём godbolt. Видим что код с делением превращается в
                                                            test2(unsigned int):
                                                            mov edi, edi
                                                            vcvtsi2sd xmm0, xmm0, rdi
                                                            vmovsd xmm1, QWORD PTR .LC0[rip]
                                                            vdivsd xmm0, xmm1, xmm0
                                                            ret


                                                            Код с доступом к памяти превращается в
                                                            test1(unsigned int):
                                                            mov edi, edi
                                                            vmovsd xmm0, QWORD PTR divs[0+rdi*8]
                                                            ret


                                                            Прогоняем через Intel Architecture Code Analyzer, видим что код с делением занимает 14 тактов, код с досупом к памяти — 0.5 тактов
                                                            iaca-lin64$ gcc -O2 -c slow.S -o slow.o && ./iaca -arch HSW --reduceout ./slow.o
                                                            
                                                            Throughput Analysis Report
                                                            --------------------------
                                                            Block Throughput: 14.00 Cycles       Throughput Bottleneck: Backend
                                                            
                                                            
                                                            antoshkka@antoshkka-ub14:~/experiments/iaca-lin64$ gcc -O2 -c slow.S -o slow.o && ./iaca -arch HSW --reduceout ./slow.o
                                                            
                                                            Throughput Analysis Report
                                                            --------------------------
                                                            Block Throughput: 0.52 Cycles       Throughput Bottleneck: FrontEnd
                                                            


                                                            Внезапно вспоминаем, что этот инструмент не принимает во внимание летенси кешей, смотрим на летенси.

                                                            Видим что в случае L2 доступа перимущество практически сходит на нет, в случае L3 или доступа к памяти — кеширование серьёзно проигрывает.

                                                            Данный вывод сходится с выводом из статьи «Станет ли быстрее с таким кешированием единиц или нет — непонятно:<и далее по тексту> может стать лучше<...>может ухудшиться». (Я вообще удивлён, что вы пытаетесь спорить с таким выводом!).

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

                                                              Вам задали вопрос выше — вы сели в лужу. Вы не предоставили ни единого примера и никак не обосновали свои обвинения.

                                                              Внезапно вспоминаем, что этот инструмент не принимает во внимание летенси кешей, смотрим на летенси.

                                                              Ещё раз вам повторю — вы нихрена не понимаете и несёте откровенную ахинею. Никакое летенси ни на что не влияет, вычисления не являются latency-bound задачей.

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

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

                                                              А что же у нас там по трупуту кешей?
                                                              L2 Write (Write, 64 bytes step) = 6.1 cycles per write (cache line)
                                                              L3 Write (Write, 64 bytes step) = 8.4 cycles per write (cache line)

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

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

                                                              Данный вывод сходится с выводом из статьи «Станет ли быстрее с таким кешированием единиц или нет — непонятно:<и далее по тексту> может стать лучше<...>может ухудшиться». (Я вообще удивлён, что вы пытаетесь спорить с таким выводом!).

                                                              Подобные выводы не имеют смысла. И опять же, глупая попытка врать. Куда вы потеряли все остальные тезисы? Про «тратить 1кб памяти»? Расскажите мне о том, как оно тратит 1кб памяти. Что же вы не пытаетесь?

                                                              Расскажите мне про 2-4раза. Что же вы не рассказываете?

                                                              И как только вы сели в лужу со всем, чем только можно — вы пытаетесь юлить в сторону общих фраз.

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

                                                              Эта клоунада. Я вас поймал уже с десяток раз, а вы меня ноль. Вы пытаетесь юлить и врать, на чём я так вас раз 10 поймал. Ответов вразумительных от вас последовало ровно ноль.

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

                                                                0
                                                                L2 Write (Write, 64 bytes step) = 6.1 cycles per write (cache line)
                                                                L3 Write (Write, 64 bytes step) = 8.4 cycles per write (cache line)


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


                                                                И где же у нас в коде множественные последовательные записи в кеш с шагом в 64 байта?

                                                                Вам задали вопрос выше — вы сели в лужу.

                                                                Повторите вопрос, а то я что-то его пропустил.
                                                                  –1
                                                                  И где же у нас в коде множественные последовательные записи в кеш с шагом в 64 байта?

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

                                                                  Block Throughput: 14.00 Cycles

                                                                  Внезапно вспоминаем, что этот инструмент не принимает во внимание летенси кешей,


                                                                  Чёткое объяснение. Почему здесь есть рассуждения о летенси кеша, но нет рассуждений о летенси дива? Почему это обстоятельство куда-то пропало? Почему эксперт не сказал об этом, почему вместо правильного определения — эксперт дал неправильное?
                                                                    +1
                                                                    Ознакомьтесь с вот этим и найдите отличия с тем, что делаете вы.

                                                                    Прежде чем вступать в дальнейший диалог, прошу вас так же выучить вот это.
                                                                      –1
                                                                      Задам вопрос ещё раз.

                                                                      Внезапно вспоминаем, что этот инструмент не принимает во внимание летенси кешей,

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

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

                                                                      Я нормально написал множество раз, что я увидел в ответ? Игнорирование. Что там по манерам? Как это называется? Вы в край обнаглели, вы пользовались моими манерами, вы на этом паразитируете. Вы пишите бред в надежде, что оппонент вас не спрос, ведь это «грубо». Всегда можно врать.

                                                                      В любом случае, мне это неинтересно. Я жду ответов на мои вопросы.
                                                                        +1
                                                                        Вы дурачок или прикидываетесь?

                                                                        Вы собираетесь тупо складывать летенси инструкций исполняющихся на разных портах?

                                                                        Давайте перенесём нашу дискуссию на лето, когда сезонное обострение пройдет, и вы сможете подробно и аргументированно (со ссылками на сторонние источники), без истерик и ругани, расписать как вы видите этот пример и почему вдруг вы выкидываете кеши/доступы к памяти из картины.
                                                                          –1
                                                                          Вы собираетесь тупо складывать летенси инструкций исполняющихся на разных портах?

                                                                          Мне лень комментировать эту откровенную ахинею, всё равно читать некому.

                                                                          Но я спрошу ещё раз. Вам задали вопрос( не про летенси, не про порты и прочую кейворды, которые вы пастите мне из гугла). Вопрос звучал так:

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


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

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

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

                                                                          Я могу в очередной раз констатировать — балабол. Ведь мы так и не узнали, почему вы ну учли то, что тулза не учитывает не только летенси кешей, но и инструкций. Человек, который понимает тему — никогда такую ахинею не напишет. НИКОГДА.

                                                                            +3
                                                                            Давайте на секундочку забудем весь предыдущий диалог.

                                                                            Я перечитал всю нашу переписку, а заодно и все ваши комментарии в принципе.

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

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

                                                                            Возможно, контекст что пример cpu bound, возник из-за специфики вашей работы, где вы решаете cpu bound задачи.

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

                                                                            Ну и наконец. Подавляющее большинство людей, с которыми вы общаетесь на этом сайте, являются профессионалами своего дела. Ваша точка зрения не единственная правильная. А если вы уверены, что вы правы, то надо оппоненту не грубить, а объяснять максимально мягко, обоснованно и безэмоционально.
                                                                  +1
                                                                  Подобные выводы не имеют смысла. И опять же, глупая попытка врать. Куда вы потеряли все остальные тезисы? Про «тратить 1кб памяти»? Расскажите мне о том, как оно тратит 1кб памяти. Что же вы не пытаетесь?


                                                                  Кеши устроены в виде хеш таблицы, где корзинка выбирается как (memory address) / (line size) % (number of sets), а в корзинке хранится обычно 4 элемента. Итого: какими бы мусорными данными не были, они выкинут одно данное из строго определённой корзинки.

                                                                  Соответственно чтобы протерять 1Kb кеша достаточно пройтись по данным с шагом 64 байта. Это затронет максимум корзинок.

                                                                  Чтобы не позорится в дальнейшем, ознакомьтесь с «Optimizing software in C++» от Agner Fog. Там есть немного плохих советов, но низкоуровневые вещи расписаны верно.
                                                                    0
                                                                    Отвечать что-то бессмысленно(данному персонажу — он неадекватен в порывах своего невежества. Он будет врать, игнорировать, врать, но никогда свои промашки не признавать), но — отвечаю для тех, кому действительно интересно.

                                                                    Кеши устроены в виде хеш таблицы, где корзинка выбирается как (memory address) / (line size) % (number of sets), а в корзинке хранится обычно 4 элемента.

                                                                    Тут мы видим попытку натянуть свои слабые представления на реальность. Я бы мог тут придраться к «memory address» в контексте всех тех проблем, которые вызывают тот факт, что адресов два и как это решается и почему там не memory address. Я бы мог придраться к «смотрю в книгу — вижу фигу», ведь человек выше кидался в меня таблицей по кешам, где чёрным по белом написано 8-way, но у него 4. Всё это неважно.

                                                                    Соответственно чтобы протерять 1Kb кеша достаточно пройтись по данным с шагом 64 байта. Это затронет максимум корзинок.

                                                                    32kb кэша — это 512 кешлайнов, при 8-way — это 64бакета.

                                                                    Таким образом проход под массиву из 2к в среднем попадёт в 32бакета, что вытеснит 2кб. Мало того, что вы не умеете делить 25+ на 5, вы ещё и не смогли правильно посчитать ширину таблицы.

                                                                    Но, в чём смысл — в любом кейсе, кроме одного(когда мы работаем на датасете шириною в кеш) — 1way никогда не используется, т.е. он временный и вытесняется при чтении. И вытеснятся будет либо кешлайн из таблицы, либо ещё более ненужный кешлайн. Т.е. полезного пространства таблица занимать не будет.

                                                                    Если проще — любое чтение из памяти пробрасывает данные в кеш, а значит — попадает в рандомный бакет, где лежит наше значение из таблицы. И это значение из таблицы — вытесняется. Не вытеснится оно ТОЛЬКО тогда, когда будет горячее самого холодного. А что это значит? Это значит то, что оно используется часто. А значит — оно уже даёт профит.

                                                                    Нужно понять базовую вещь — таблица либо выкидывается из памяти, либо даёт профит. Какие-то варианты есть тогда, когда мы читаем данные ТОЛЬКО в рамках определённого датасета и этот датасет примерно равен ширине кеша. Это очень, очень редкий кейс. В любом случае почти всегда(даже в близких этому кейсах) читаются левые данные, а значит — 1way всегда будет временный.

                                                                    Таким образом — в 99+% случаев может быть 2кейса. Таблица используется редко — оно вытесняется из кеша сразу же, при чтении новых данных(любых). Таблица используется часто, но тогда она действительно лочит место в кеше, но в этом случае — она даёт профит. Ведь она во много раз быстрее деления.

                                                                    Таким образом, даже если у вас есть нужные данные(которые вытеснит эта таблица) — они вытеснятся в л2, но у л2 летенси меньше, чем у дива. Вы получите деградацию, но в 12тактов, с дивом в 15.

                                                                    Если вы хотите спросить «а если мои данные читаются чаще, чем исполняется див — почему ты считаешь одно чтение за одну операцию» — очень просто. Ведь если ваша программа читает нужны данные чаще, чем считает по таблице — ваши нужные данные ВСЕГДА(за исключением очень редких кейсов, но об этом я уже говорил выше) будет в кеше.

                                                                      0
                                                                      Я с вами полностью согласен.

                                                                      Помимо рассмотренных вами приложений, работающих с небольшими наборами данных, есть приложения, где узкое место — память, и активный датасет занимает несколько мегабайт. В таких приложениях, дополнительно наращивая объёмы данных, которые надо хранить в кеше, вы вытесняете что-то полезное из l1/l2/l3.
                                                                        +1
                                                                        Помимо рассмотренных вами приложений, работающих с небольшими наборами данных, есть приложения, где узкое место — память, и активный датасет занимает несколько мегабайт.

                                                                        Смысл в том, что реальность она сложнее. В ней нет такого понятия как «узкое место — память» — у памяти есть совершенно разные места, которые могут быть узкими.

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

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

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

                                                                        В таких приложениях, дополнительно наращивая объёмы данных, которые надо хранить в кеше, вы вытесняете что-то полезное из l1/l2/l3.

                                                                        В кеше хранятся активные данные. Если данные неактивные — они ненужны. Это ничего не изменит. Если мы не хотим вытеснять данные из кеша — мы вообще НИЧЕГО не должны читать из памяти(кроме активного датасета). Любое чтение — вытесняет нужны данные.

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

                                                                        И опять же, всё неправильно — активный датасет в несколько мегабайт вообще никак не зависит от llc, от l2 — влезет в l3 — зависит от l3.

                                                                        В данном случае меньшие кеши имеют только одно применение — кешировать некие часто используемые данные и тут будет такое же вытеснение одного way.

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

                                                                        Реально подобный случай — это банальная оптимизация скалярной лапши. Смысл очень просто. Когда мы попадаем в тот же l2 — данные( а именно кешлайн) мигрируют в l1d, а т.к. скалярный лапша читает данные по 1/2/4/8 байт, то в рамках последовательного чтения — мы перечитываем этот кешлайн множество раз, до 64. Если бы он не мигровал в l1d, то мы бы множество раз читали куски из l2, что явно хуже

                                                                        С учётом некой параллельности( в простонародье prefetch) — нам желательно читать сразу несколько кешлайнов. На самом деле тут и l1d не нужен — хватит буферов, но мы не об этом.

                                                                        И казалось бы — мы нашли подходящий кейс, но нет — ему не нужен весь l1d — ему хватит десяток кешлайнов. Остальной кеш ненужен и ни на что не влияет.

                                                                        Всё это к чему? А к тому, что очень сложной придумать кейс, в котором 1way будет не временным. Всё то, что кажется подходящим — лишь кажется.

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

                                                                        И вот у нас есть выбор. Даже если случится так, что мы проиграем в паре вызовов диву, но — это будут те случаи, которые никак не влияют на производительность нашей программы. А вот в случае частого использования — она будет в кеше, не будет его тратить( за очень-очень редкими исключениями), но при этом будет давать профит. А раз она используется часто, то и влияние на производительность нашей программы оказывает весомое.

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

                                                                          0
                                                                          А какой алгоритм для выбора кэш линии внутри корзинки? Он явно отличается от LRU, на который я опирался в своих рассуждениях.

                                                                          Длительное же время во многих CPU был LRU, из-за которого в 4-way кэше, 4 новых значения для корзинки вытесняли все старые значения (вне зависимости от того, как часто они использовались до этого).
                                                                    0
                                                                    Эта клоунада. Я вас поймал уже с десяток раз, а вы меня ноль.


                                                                    А давайте клоуна найдет не предвзятый свидетель спора. Расскажите в какой компании работаете и как вас зовут.

                                                                    Интересно, ваше руководство в курсе о наличии в рядах сотрудников столь ценных кадров?
                                                        +1

                                                        Спасибо, отличная статья.


                                                        В свое время искал реализацию std::vector, с SSO оптимизацией (по аналогии с std::string, хранящий N элементов внутри себя, без дополнительных аллоков на куче)


                                                        Не нашел, в итоге написали свой.

                                                            0

                                                            О, спасибо!
                                                            Про llvm small_vector не знал — посмотрю.


                                                            А boost ИМХО, все же жирноват, что бы из за нескольких полезных контейнеров тащить в зависимости десятки мегабайт либ, и усложнять процесс сборки...

                                                              0
                                                              можно не тащить весь буст, а скопировать только сам вектор.
                                                                0

                                                                Согласен, мы именно так и поступили с intrusive_ptr

                                                                  0

                                                                  UPD:
                                                                  Посмотрел на boost small_vector — увы, тащит за собой много #include из буста.


                                                                  И по использованию памяти не очень оптимальный:


                                                                  sizeof (small_vector<int,4>) = 40 байт, а наша реализация обходится 20-тью, для аналогичного случая

                                                            0
                                                            _
                                                              0
                                                              В итоге он не поломает ваш код. Без override все скомпилируется, как-то будет работать, но будет ошибка на рантайме. На ее отлавливание может уйти много времени.
                                                              Аж передёрнуло, вспомнил старые добрые времена, когда не покрывал код тестами на 99% и более. Фишка конечно полезная, как и все прочие подобные конструкции, но без тестов это просто оттянет момент, когда вы сидите перед огромным проектом, который разрабатывался с десяток лет, а юнит-тестов нету и каждое исправление ошибки или добавление фичи вызывает 10 новых ошибок.
                                                                +1

                                                                Одно другому не мешает, а дополняет.


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

                                                                +1
                                                                Класс! Прочитал на одном дыхании.
                                                                  +1
                                                                  Насчет FORCE_INLINE имеется некоторое лукавство.
                                                                  1. Проблема с кэшом инструкций может возникнуть не от самого по себе инлайна, а когда один и тот же код инлайнится многократно. Ибо если функция не инлайнится, то ее код все равно попадает в кэш инструкций :)
                                                                  2. Обычно FORCE_INLINE применяют в тех случаях, когда это буквально пара строчек, которые определять #define'ом вроде как уже некошерно, а возможности сделать intrinsic для компилятора нет. И в этих случаях FORCE_INLINE вполне оправдан. А если кто-то принудительно инлайнит функции на несколько десятков строчек кода, то он сам себе злобный Буратино.

                                                                  Если уж тема инлайна и кэша инструкций была затронута, то можно было бы обратить внимание и на смежную проблему — когда кэш заполняется за счет кусков кода, которые потенциально не исполняются вообще или исполняются на slow path. В некоторых случаях компилятор может сам оптимизировать такие случаи, хороший пример — инициализация статических переменных, которую компилятор выносит за пределы тела функции. В общем же случае компилятор ничего не знает, насколько вероятно выполнение/невыполнение некоторого условия. С точки зрения процессора, пока код еще не выполнялся, действует static branch prediction, у которого, например, на Intel'е крайне простые правила — условный переход назад считается вероятным событием, условный переход вперед — маловероятным. В соответствии с этим префетчер будет подтягивать инсрукции в кэш. Поэтому во многих случаях является оправданным использование интринсиков типа GCC'шного __builtin_expect — те самые макросы likely и unlikely, которые многие так не любят. Эти макросы позволяют компилятору наиболее оптимально организовать код с точки зрения кэша инструкций и работы механизма предсказания переходов.
                                                                    0
                                                                    +1

                                                                    В случае c 2) я говорил именно о неразумных применениях («весь проект вдоль и поперек»).

                                                                    К несчастью, о всех интересных темах сразу рассказать не возможно из-за ограничений по времени. В дополнение к тому что вы сказали — некоторые компиляторы вытаскивают вероятность исполнения условия из наличия в одной из веток [[noreturn]] или throw. Ещё одна из забавных и неплохо работающих эвристик — «если if без else — то условие редко выполняется; если if с else — условие выполняется часто».
                                                                      0
                                                                      +1
                                                                      для корректного «force_inline» должна быть runtime статистика, а для этого нужна Profile Guided Optimization. Про умные «в статике» компиляторы, которые знают, что инлайнить, а что нет — не верю, ибо практика показывает иное, да и VTune подтверждает.
                                                                      +1
                                                                      Если ваше приложение не использует weak pointers, или использует их не сильно, вместо строчки std::shared_ptr<int>(new int) имеет смысл написать std::make_shared<int>().

                                                                      Думаю, имеет смысл пояснить, откуда взялось такое условие.
                                                                      Поскольку make_shared аллоцирует память для хранимого объекта, и для своего управляющего блока одним куском, то и освободить её можно только всю сразу. В свою очередь, weak_ptr, помимо своего собственного счетчика ссылок, использует счётчик ссылок, хранящийся в shared_ptr. Иначе говоря, ему нужно, чтобы управляющий блок shared_ptr оставался валидным. Удалять его нельзя. Поэтому, даже если все shared_ptr, ссылающиеся на ваш объект прекратили своё существование, память, выделенная с помощью make_shared, не освободится, пока хотя бы один weak_ptr «остаётся в живых». Это может приводить к некоторой утечке памяти, если у вас есть weak_ptr, который «живёт» существенно дольше чем ваши shared_ptr.
                                                                      Отдельно стоит отметить, что деструктор для объекта, хранимого внутри shared_ptr, в любом случае, будет вызван сразу после того, как счётчик ссылок shared_ptr станет равен нулю. Так что на логику работы кода, описанная выше особенность, не влияет.
                                                                      Что касается масштабов утечки, на практике, массивные объекты, типа векторов или списков хранят свои элементы в отдельно выделенной памяти, которая как раз освободится деструктором объекта. Висеть в памяти останется лишь малая часть. Так что, наибольший эффект оказывает именно количество таких объектов. И это приводит нас к указанному выше условию: использовать make_shared имеет смысл
                                                                      Если ваше приложение не использует weak pointers, или использует их не сильно
                                                                        0
                                                                        Велосипедам быть. К сожалению многие стандартные функции работают в РАЗЫ медленнее, чем кастомные. Взять хотя-бы простейшие (но широко используемые) ф-ции конвертации строк в число и наоборот.
                                                                          +1
                                                                          Это постарались исправить в C++17, добавив std::to_chars/std::from_chars.

                                                                          Так что у меня слабая надежда, что со временем велосипеды сойдут на нет.

                                                                        Only users with full accounts can post comments. Log in, please.