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

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

НЛО прилетело и опубликовало эту надпись здесь

От мыслей о барьерах и слабой модели памяти вас не защитит и C# с Java :-)

«В компьютерных науках есть только две сложные проблемы – инвалидация кэша, придумывание названий и выход за границы» — Фил Карлтон
но, позвольте! у вас тут три пробле… oh shit!!!
C++ это язык, который пытается всячески преодолеть ограничения своего C-прошлого, не принося в жертву эффективность и скорость, предоставляя широкий набор возможностей и инструментов. Но такой подход опасен тем, что его пользователю предоставляется полная свобода прострелить себе ноги. А lock-free подход — это самое опасное оружие из этого арсенала, которое при неумелом использовании может не прострелить, а целиком отстрелить обе ноги сразу %)
Если для вас это проблема — не используйте lock-free. А многопоточное программирование само по себе очень сложная тема.
Многопоточно программировать очень легко на python, спасибо gil :)
Что то меня наводит на мысль, что одно атомарное поле, как замок, над пачкой не атомарных, тоже хорошо работает «случайно».
Работа с g_data1, g_data2, g_data3 действительно происходит неатомарно. Но работа с этими данными заканчивается строго до того (happens before), как происходит атомарное изменение флага. Поэтому пофиг, как именно происходит взаимодействие с g_data*, параллельных обращений к ним нет. Это верно для ограниченного примера, где среди читателей есть только пример с
if (g_flag) f(g_data1, g_data2, g_data3);

Если бы было чтение или запись в эти переменные до проверки g_flag, то действительно была бы гонка, а с т.з. стандарта языка — UB.
Это не соотвествует действительности. Так было бы если использовался std::atomic_thread_fence. В данном случае атомарный доступ к флагу никак не влияет на видимость полей g_data1, g_data2, g_data3. Более того, даже компилятор может вызовы местами переставить.
по-моему, все же влияет, и segoon прав:

«A store operation with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this store. All writes in the current thread are visible in other threads that acquire the same atomic variable»

(взято отсюда: en.cppreference.com/w/cpp/atomic/memory_order)
Ключевое в этой фразе
the same atomic variable
.
Т.е. упорядочиваются все операции чтения/записи в конкретную атомик переменную.
На уровне x86 CPU — это означает синхронизацию(очистка store-buffer) конкретной кеш линии с переменной, а не вообще всей памяти.
нет. При release-семантике все операции записи (а не только в атомики), сделанные до записи в атомик A с release-барьером становятся видимыми другим тредам, но только при условии, что они выполняют чтение этой переменной (A) с acquire-барьером. Если они читают другой атомик B с acquire-барьером, то тогда не гарантируется, что они увидят все операции записи, в том числе в A, в нужном порядке, и вообще их увидят, что логично, так как B может в другой кэш-линии лежать.
работает «случайно».

#include <atomic>
void test(int *ptr1, int*ptr2, std::atomic<bool> f)
{
  *ptr1 = 1;
  *ptr2 = 2;
  f.store(true, std::memory_order_release);
}

test(int*, int*, std::atomic<bool>):                // @test(int*, int*, std::atomic<bool>)
        mov     w8, #1
        mov     w9, #2
        str     w8, [x0]
        str     w9, [x1]
        stlrb   w8, [x2]
        ret

STLRB — Store-release register byte

A store-release will be observed by each observer after that observer observes any loads or stores that appear in program order before the store-release, but says nothing about loads and stores appearing after the store-release.

Т.е. запись во флаг (STLRB) выполняется только после того как другие ядра увидят все чтения и записи выполненные до инструкции stlrb в порядке следования программы.
К сожалению, я не могу аргументированно спорить, т.к. не знаю модели памяти С++ и гарантий которые она дает.
Но в примере выше, по факту это барьер памяти, который требует выдавить из буферов записи все перед тем как запишет сам.
На этой платформе это так, а как будет на остальных?
Пойду как почитаю про модель памяти в с++)
От блокировок избавится очень просто: достаточно объявить данные только для чтения, и только для записи. То-есть поток данных будет всегда однонаправленным. Нужно двухстороннее общение — вот вам два потока.
К тому-же в ARM на уровне команд реализована атомарная передача данных, для случаев когда объект на запись доступен всем.

Нет такого.

Есть.
volatile — всегда сохранять в память
const volatile — всегда читать из памяти
Эти комбинации модификаторов сами по себе являются барьерами памяти. То-есть они будут безусловно выполнены, даже если есть валидная копия в регистре. Но это не спасает от оптимизатора — чтение/запись могут быть буквально где у годно. И тогда приходят на помощь операторы условия и цикла — способ выполнить участок кода в строго определённом месте.

Атомарная передача для ARM __STREXW(), и так далее.
const volatile, кстати — неопределённое поведение. const-значения не могут менять свои значения, а значит компилятор при оптимизации может пропустить повторное чтение, даже если это volatile. Т.е. первое чтение будет по правилам volatile, а последующие могут быть опущены. И даже видел такой эффект на каком-то компиляторе.
Но на практике практически всегда работает, конечно.
И то, о чём вы говорите ни разу не помогает в обсуждаемом вопросе — на ARM чтение вашего const volatile точно так же может быть исполнено ПОСЛЕ того, как начнётся работа этим значением — это аппаратная особенность. Т.е. всё равно нужны платформо-зависимые барьеры чтения/записи, а значит, ничего не меняется — хоть оно двунаправленное, хоть однонапрвленное.
По стандарту это не так. Сonst всего лишь говорит что семантика переменной такова что её нельзя изменить в данном контексте. Компилятор не может рассчитывать, и почти никогда не рассчитывает, что сonst переменная не может быть изменена извне. На практике это является большим препятствием для возможных оптимизаций. Простейший пример:
int var1 = ...
...
const int& var2 = var1;

Var2 просто может появляться в контексте в котором в неё нельзя писать, и всё. Тоже самое относиться и к классам и их методам.
Volatile — не разрешает кеширование переменной. Т.е. её чтение всегда должно производится из памяти. Это легко можно проверить посмотрев выход ассемблера.
Const volatile — заставляет всегда читать значение переменной из памяти и запрещает туда писать, но значение может бы изменено извне.
Модификатор volatile также не имеет никакого отношения к многопоточности и не может заставить компилятор вставлять барьеры и не управляет когерентностью кешей.
Нет, не так.
По станандарту изменение const-значения приводит к неопределнному поведению вне зависимости от volatile. Вот, например цитата из C++11 раздел 1.9 пункт 4 (повторяется в стандарте несколько раз):
Certain other operations are described in this International Standard as undefined (for example, the effect of attempting to modify a const object).
Аналогичное правило есть во всех остальных версиях стандарта.

В результате компилятор имеет право кэшировать volatile const значения. Да, он обязан прочитать их в месте использовани и соблюсти семантику volatile, но только один раз.
Сюрприз-сюрприз.
А вот тут люди не согласны isocpp.org/wiki/faq/const-correctness#aliasing-and-const и приводят примерно тот же пример, то выше. Да и ваша цитата не говорит ничего про данную ситуацию. Модификация константного объекта и модификация неконстантного объекта, на который где-то там существует константная ссылка, это совершенно разные вещи. Запретить последнее это надо сильно умнее компилятор иметь по типу раста. Поэтому в примере выше var1 можно спокойно менять и var2 будет у всех под ногами меняться, а вот var1 через var2 поменять не сможем. Ну разве что через const_cast, ибо ссылаемся на неконстантный объект. Опять же, совершенно легально.
Я лишь хотел сказать, что вы не можете рассчитывать на то, что const будет оптимизирован (кеширован). Пример который вы привели не противоречит этому. Стандарт говорит о том что будет если вы «хакерскими» методами (грубо reinterpret_cast) попытаетесь поменять значение которое объявлено как const. Представьте что "..." это граница между разными файлами или модулями. Компилятор спокойно в праве не догадаться меняется переменная из вне или нет, а это будет важно в случае если это указатели, ведь переная не обязательно имеет POD тип. Это может быть массив, структура или класс, поэтому всегда гарантированно сделать оптимизацию он не может: ему возможно понадобиться знать адрес, инициализация окажется очень сложной и т.д.:
const int var = 5; // Думаю всегда заоптимизируется

const int var1 = 5; // Скорее всего не будет оптимизирован
const int& var2 = &var1;

const MyClass var1(..., ..., ...); // Зависит от класса, но рассчитывать на это я бы не стал

то, что на мутабельную переменную есть const ссылка, не делает её иммутабельной
Я как раз об этом и говорю. const в С++ это, по большому счету, бесполезная конструкция. Она призвана только какие-то инварианты программиста соблюдать. На генерацию кода, я думаю, она практически не влияет кроме самых самых очевидных случаев. С++ не имеет понятия и поддержки иммутабельности, он не умеет трекать какие ссылки когда были созданы, чтобы понять, что константный указатель на самом деле ссылается на неконстантную переменную. Мало того, что const сам по себе бесполезен по-определению, так еще дано полно инструментов для его легального обхода, что полностью связывает руки компилятору.
По сути я с вами согласен, но вот утверждение что const бесполезно, это вы слишком… Сonst бывает бесполезен с точки зрения оптимизации, особенно с ссылками и указателями с точки зрения алиасинга. Но также const может задавать константность методов где наоборот можно добиться гарантированной оптимизации, типа:
const Huge& MyClass::GetHuge() const
{
    return m_huge;
}

Huge MyClass::GetHuge()
{
    return m_huge;
}
Я всегда пишу код соблюдающий const-корректность и это сильно помогает, но все же, думаю, лучше рассматривать const не как оптимизацию, а как выражение семантики неизменяемости с точки зрения внешнего кода. Т.е. мы гарантированно не можем поменять состояние объекта снаружи, но это не значит что он не может поменяться откуда-то еще.
Но человек же утверждает что const отменяет volatile и вот это уже очень странно, т.к. такое поведение полностью нарушает логику кода, на мой взгляд.
Ваш пример про преобразование типов. Если const убрать (через привидение типов или через указатель), то несомненно всё будет иначе работать, но с точки зрения компилятора это будет другое значение с другими атрибутами и другим поведением, что очевидно.
Нет, мой пример про
int var1 = 1;
const int& var2 = var1;
var1 = 2; //var2 тоже станет равен 2 и это легально


А про const_cast это лишь к тому, что в языке столько инструментов для того, чтобы сломать const, что у компилятора нет практически никаких шансов чего-то там закэшировать. Уж точно он не может кэшировать значение, на которое ссылается константный указатель. Это значение может поменяться в любой момент. Вот сам указатель пусть кэширует сколько влезет.
Нет, там такого. Там указатели, а вы тут пример ссылки приводите. Ваш пример ссылками некорректен и однозначно приводит к неопределённому поведению поведению. У вас в этом примере вообще aliasing жестокого нарушен и все современные компиляторы на этом споткнутся.
Там указатели, а вы тут пример ссылки приводите

Указатель/ссылка здесь абсолютно эквивалентны. Заменяем & на * и пример остается ровно таким же.

Ваш пример ссылками некорректен

Я вам скинул ссылку на isocpp.org (где как раз про алиазинг речь), где черным по белому говорят, что это корректный код. Давайте тогда цитату из стандарт, если считаете это UB. Ваш цитата выше тут не подходит.
Указатель и ссылка с точки зрения компилятора и стандарта ни разу не эквивалентны.
Стандарт имеет в виду «хакерское» изменение переменной, типа:
const int var = 5;
...
*const_cast<int&>(&var) = 6;

Volatile же как раз и нужен для того, что бы сказать компилятору что бы он не кешировал переменную. У вас же получается что const отменяет volatile. Вы можете привести ссылку на стандарт где бы было об этом прямо написано?
В стандарте нет исключения для const volatile. Там просто написано, что изменение const — неопределённое поведение.
volatile влияет на const, не так как вы думаете. В почему-то много додумываете за стандарт. Для volatile будет соблюдён порядок выполнения относительно других volatile. Само чтение будет исполнено. Но результат может быть запомнен! Где тут «отмена» const? Без «volatile» компилятор вообще может переставить чтение в другое место или опустить его если значение не используется, так что ничего не отменяется. Но кэшировать значение компилятор может.
const volatile, кстати — неопределённое поведение

Это не свойства переменной, это модификатор памяти где она находится. Значение переменной, и конкретные байты в физической памяти, где лежит эта переменная — могут иметь разные модификаторы.
Есть очень нехорошая шутка «register volatile», за которую могут оторвать руки и ноги. А если не дойдёт с четвёртого раза, то и голову.
Register де-факто уже давным-давно не имеет никакого влияния на компилятор, а начиная с С++17 и де-юре.

Кстати, раз тут вспомнили М1 — то там есть возможность нативно отключить для потока слабую модель памяти и использовать TSO ;-)

А эта возможность где-то задокументирована или доступна в пользовательском коде? Или вы просто из существования rosetta 2 делаете вывод?

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

TL;DR: на x86 переданный в атомарные операции memory_order по сути не имеет значения, а на ARM имеет. Благо там по умолчанию std::memory_order_seq_cst, поэтому если вы не меняли этот аргумент, у вас всё продолжит работать. Если меняли, значит наверно подумали зачем?
Почему не имеет? Это так же указание оптимизатору, что ему позволено с кодом делать.

Вопрос, разве g_dataN не должны быть тоже атомарными (например для простых типов), что бы memory_order при g_flag.store() имел на них влияние?

Смотрите, тут есть два вопроса.


Один — это доступ к разделяемым данным. Атомарные операции над атомарными типами позволяют нескольким процессорам наблюдать определённые состояние атомарных величин. Естественно, если процессоры совместно, одновременно выполняют неатомарные операции с разделяемыми данными — они наблюдают их в неопределённом состоянии. Поэтому подразумевается, что атомарный g_flag используется для синхронизации доступа к неатомарным g_data. То есть, только один процессор в один момент времени — на протяжении «критической секции» — должен работать с g_data. В этом случае этот процессор будет уверенно наблюдать определённое поведение g_data: если туда записать 123, там так и останется 123 — ведь никто другой больше не трогает g_data.


Другой вопрос — это каким образом атомарные операции с g_flag гарантируют, что при входе в критическую секцию процессор увидит изменения, которые выполнялись с «не связанными» данными в g_data. Ведь как вы правильно заметили — это совершенно разные регионы памяти и не очевидно, почему атомарная операция по адресу &g_flag должна вдруг влиять на значения по адресу &g_data. Вопрос можно поставить и по-другому: будет ли g_flag влиять на g_some_other_data? Откуда процессор знает, что именно g_data связана с g_flag, а не что-то другое?


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


Наиболее примивная реализация «барьеров памяти»: атомарные операции влияют на всю память сразу. После атомарной операции с g_flag (или любым другим флагом) процессор увидит обновления в g_data (или любом другом месте памяти). Когда один процессор трогает атомарную переменную, то все другие процессоры обязаны сбросить все свои кеши и читать значения из памяти.


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

Один процессор, находясь в критической секции записал в неатомарную переменную i=42. А когда это i реально окажется в ОЗУ?
В это время второй процессор в нетерпении перетаптывается на входе в критическую секцию и как только она освобождается — мигом читает значение этой переменной… из СВОЕГО кеша.
Или первый процессор, во время записи переменной, даже не скинув ещё данные в ОЗУ — сообщает остальным, что если у кого в кеше есть данные с этого адреса, то они протухли, ждите, сейчас скину обновление?

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


Для ARM не скажу, к сожалению, я в их деталях не силён. Например, x86 процессоры Intel используют протокол MESIF. В нём процессоры обмениваются информацией о том, что происходит с их кеш-линиями, и могут отправлять их друг другу в обход памяти. (Для того, чтобы i = 42 добралось до RAM, надо сначала пройти через L2 и L3 кеш.)


И действительно, как только один процессор пишет что-то в свою кеш-линию, где живёт i, то аналогичные кеш-линии других процессоров переходят в состояние Invalid. Когда другой процессор хочет прочитать переменную, то он знает, что его кеш протух и надо идти его обновлять.


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


Кроме того, запись из регистров в кеш-линию тоже происходит не напрямую. Записи обычно попадают в ещё одну очередь, а попадают в кеш этого же процессора уже оттуда. Роль «барьера записи» как раз в том, чтобы перелить все обновления в кеш (и разослать уведомления другим процессорам, где что протухло).


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

Что-то я первый раз слышу о влиянии барьеров памяти на кэш.

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

А можно поподробнее, как барьеры памяти влияют на кэш?

Да, правильно: барьер не позволяет процессору перемещать операции через него. Ключевая идея здесь в том, что «повторное чтение значения из кеша» — это фактически операция «чтения из памяти», перемещённая далеко в прошлое, в тот момент, когда значение попало в кеш (и его считали из памяти таким, каким оно тогда было). Барьер чтения не даёт выполнить процессору такое «как бы перемещение», запрещая читать данные из кеша (если он инвалидирован; если же значение занесено в кеш уже после барьера — пожалуйста). Аналогично, барьер записи не позволяет процессору отложить запись в кеш куда-то в будущее, на потом, вынуждая записать данные сейчас.


Сейчас мне пора идти спать. Если всё ещё не понятно, я завтра постараюсь нарисовать схему, как это примерно работает.

Да, без схемы — трудно уловить идею.
Это от архитектуры зависит. В некоторых архитектурах с кэшированием в команде барьера может передавать адрес, что вызывает сброс/инвалидацию кэшей по этому адресу.
Для ARM барьеры на кэш не влияют — они работают только внутри процессорного ядра. Когерентность кэша описывается отдельно и кэши ядер могут быть когерентными или некогерентными. Вплоть до того, что это это может быть отельной управляемой опцией шины/кэша для каждого из ядер — Snoop Control Logic (SCU).
Если кэши некогерентны, то нужно ещё кроме барьеров чтения/записи выдавать инструкции сброса/инвалидации кэша по нужным адресам — DCCSW, например.
Эффективная многоядерность на ARM этот ещё адок.
Если барьеры на кеши других ядер не влияют, тогда в чем их смысл на ARM, что они делают? Ведь ядро которое производило запись и так видит все свои локальные изменения.
1. В процессорах с суперскаляроной архитектурой несколько ассемлерных комманд выполняются однорменно. Барьер гарнтирует результат и/или порядок выполнения таких команд.
2. В процессоре кроме кэш памяти есть ещё очереди чтения/записи. Барьеры гарантируют, что эти очереди будут сброшены/очищены. Команды барьеров, например есть на архитектура вообще без кэша. Cortex-M3, например, в лице всяких STM32. Кэшей там нет, а команды барьеров есть и нужны. Без этих команд запись в порт будет выполена не во время исполня соответствующей инструкции, а когда-нибудь потом.
3. Управление кэшированием может осуществляться в MMU (зависит от архитектуры и реализации). Т.е. для некоторых регионов памяти кэширование может выключенено или частично выключено (всякие аппаратыне регистры, DMA и т.п.), но барьеры всё равно нужны в силу особенностей, описанных в пункте 2.

Получается запись (или чтение) атомарных переменных это невероятно дорого, так как по сути сбрасывается кэш на всех процессорах? А использование shared_ptr влияет на все потоки, так как там тоже атомарные переменные.
Спасибо за ответ! я пару лет назад пытался сымитировать такое спонтанное чтение, но не смог, я так понял что причина в была в x86 которая не даёт такой проблемы.

А использование shared_ptr влияет на все потоки, так как там тоже атомарные переменные.

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

Если копирование одного умного указателя в нескольких потоках требует mutex, зачем тогда в нем атомарный счётчик?

Я имел в виду синхронизацию кэшей при изменении атомарного счётчика. Мьютексов там нет.

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


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


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


Особенность x86 в том, что его LOCK-префикс — это полный барьер: и на запись после операции, и на чтение перед. Поэтому там не только дорого читать с этим префиксом (что логично: вы только что возможно сбросили себе кеш), но и писать тоже — после записи у вас теперь возможно сброшенный кеш. Был бы барьер только на запись — пишущие процессоры могли бы дальше считать, что то, что они только что записали — это актуальное значение.


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


Дороги не атомарные операции сами по себе. Дороги барьеры.

Не так.
На том же ARM барьеры не влияют кэш. Барьеры работают внутри ядра, а кэш — снаружи. Так что, после барьера записи на ARM остальные ядра могут ничего и не увидеть.
не весь кэш и не на всех процессорах. На пишущем происходит сброс кэша по нужным адресам, а на читающих — инвалидация. Для этого есть специальные команды. Ну, или можно зафигачить когерентный кэш, но производительность упадёт.
Если компилятор переставит местами инструкции записи, то флаг g_flag может получить значение true до того, как будут записаны все данные


Да что все о перестановках?
Достаточно иметь разные переменные на разных кэшлайнах, а потоки- на ядрах, имеющих собственный кэш. И пожалуйста- до ядра «читателя» разные переменные (линии кэша) доезжают в произвольном порядке.
>Если компилятор переставит местами инструкции записи…
И эти люди ругают меня за то, что я использую GoTo.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.