Как стать автором
Обновить

Комментарии 102

—У нас здесь указатель на 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.
а в реализациях STL? И, если нет, почему?
В реализации стандартной библиотеки может быть любая имплементация. Например GCC предпочитает жертвовать несколькими символами, но держать валидный указатель — эту убирет if на каждую операцию.
Спасибо за статью, обожаю плюсы.
обезательно ли его нужно помечать noexcept.

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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


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

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

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

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

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


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


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

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


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

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

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

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

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

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

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

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

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

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


// Функция 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 имеет право модифицировать исходный объект.

Когда это у нас 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 проблемы потокобезопасности лежат исключительно на разработчиках стандартной библиотеки.
С тех самых пор, как появились потоки и само понятие потокобезопасности, как следствие — то есть с 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.
К чему это написано

К вашему вопросу «Когда это у нас 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-строки, таким образом, словно это три вопроса на одну и ту же тему.
Ваш процитированный код расположен в статье после заявления о том, что виноваты multi-core процессоры, в качестве исправления той проблемы. Так что на момент описания проблемы этот код ещё не используется. Я в своём первом комментарии как раз писал о том, что этот код нужен вне зависимости от того, сколько ядер в проце, потому как без него может случиться (хоть и с меньшей вероятностью) race и на одном ядре с разделением времени между потоками.

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

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

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

Если -fstrict-aliasing что-то «испортил», код в любом случае надо переписывать. К тому же, он включается по умолчанию уже на -O2.
static const std::vector<std::string> CONSTANTS = {

  "Hello",
  "Word",
  "!"
};
А ещё для этого есть библиотеки с compile-time контейнерами, например frozen и sprout.
Прямо из вектора строка перетянется внутрь контейнера res. Никаких динамических аллокаций в итоге не будет.


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


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

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

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

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


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

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


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

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

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

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

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 весь код на асме. Не нужно ведь — там всякие строки и прочая работа с памятью. Ан нет.

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

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

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

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

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

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

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

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

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

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

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

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

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

Работает.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Не будет.

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

Не будет.

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

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

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

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

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


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

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

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

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

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

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

__m128 _k = _mm_set1_ps(1.0f / p);

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

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

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

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

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

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

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

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

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

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

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

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

Никакого отношения ваш пример к векторизации деления не имеет. Повторюсь уже в 3-4раз.
Я не поленился и проверил скорость деления с применением закешированного значение и напрямую с использованием 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).
Это оптимизация деления, которая не имеет смысла <...>

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

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

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

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

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

######

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

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

Зачем вы пытаетесь врать и дёргать фразы из контекста? Там написано то, что если убрать таблицу и заменить её на деление — это не будет иметь смысла и вам объяснили почему. У вас получится 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.

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

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

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

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

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

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

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

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

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

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

Ваш подробный разбор не стоит и выеденного яйца, потому что вы разбираете не пример из статьи, а что-то из своей головы. Откуда вы взяли «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 или доступа к памяти — кеширование серьёзно проигрывает.

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

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

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

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

Ещё раз вам повторю — вы нихрена не понимаете и несёте откровенную ахинею. Никакое летенси ни на что не влияет, вычисления не являются 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 поймал. Ответов вразумительных от вас последовало ровно ноль.

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

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 байта?

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

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

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

Block Throughput: 14.00 Cycles

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


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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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


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

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

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

Кеши устроены в виде хеш таблицы, где корзинка выбирается как (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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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


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


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

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


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

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

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

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


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


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

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

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


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

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

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

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

К несчастью, о всех интересных темах сразу рассказать не возможно из-за ограничений по времени. В дополнение к тому что вы сказали — некоторые компиляторы вытаскивают вероятность исполнения условия из наличия в одной из веток [[noreturn]] или throw. Ещё одна из забавных и неплохо работающих эвристик — «если if без else — то условие редко выполняется; если if с else — условие выполняется часто».
+1
для корректного «force_inline» должна быть runtime статистика, а для этого нужна Profile Guided Optimization. Про умные «в статике» компиляторы, которые знают, что инлайнить, а что нет — не верю, ибо практика показывает иное, да и VTune подтверждает.
Если ваше приложение не использует 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, или использует их не сильно
Велосипедам быть. К сожалению многие стандартные функции работают в РАЗЫ медленнее, чем кастомные. Взять хотя-бы простейшие (но широко используемые) ф-ции конвертации строк в число и наоборот.
Это постарались исправить в C++17, добавив std::to_chars/std::from_chars.

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