Комментарии 62
Ни черта не понятно.
«Вот вам код — разбирайтесь, как он работает».
«Вот вам код — разбирайтесь, как он работает».
и вообще статьи подобного толка не требуют ни одной строки кода, а иллюстрировать лучше на блок-схемах.
Вы о чем, какие блок-схемы? Я их последний раз чертил тушью по ГОСТу на ватманских листах, когда диплом сдавал 20 лет назад. Уже тогда это выглядело явным маразмом. Код гораздо понятнее.
Вообще, я вот по таким книжкам учился — ни одной блок-схемы и состоит из распечаток. Или по таким и таким.
Тут вся соль именно в деталях реализации — в том как именно этот список построен, как его собрать в страйпы, что из этого получается. Вот суперблок размера 48, вот у него раздача прямо из суперблока, вот — классический однонаправленный список свободных блоков. Вот тут — попадает в список, вот тут — берется. Суть метода то именно в деталях.
Вообще, я вот по таким книжкам учился — ни одной блок-схемы и состоит из распечаток. Или по таким и таким.
Тут вся соль именно в деталях реализации — в том как именно этот список построен, как его собрать в страйпы, что из этого получается. Вот суперблок размера 48, вот у него раздача прямо из суперблока, вот — классический однонаправленный список свободных блоков. Вот тут — попадает в список, вот тут — берется. Суть метода то именно в деталях.
Всё отлично, не парьтесь. Многие читатели «мимо кассы» из-за того, что это же не про «копирастеры что-то накопирастили», а о программировании.
Спасибо за статью.
Спасибо за статью.
Хмм, у вас удивительная статья — с одной стороны я понял чего в моем на досуге пописываемом просмотровщеке изображений лагает генерация превьюх (первый абзац), а остального я не бельмеса не понял — нужно перечитать.
и я по таким же книжкам учился…
у меня на полке стоит второе издание Страуструпа 1987г на 257 листах. Сколько там сейчас листов? 1136…
ни какого STL, только С++ как Си «с постинкрементом»
спасибо за статью, в жизни пригодится
сам свои пулы памяти «изобретаю»…
некоторые готовые использовал — не понравилось.
у меня на полке стоит второе издание Страуструпа 1987г на 257 листах. Сколько там сейчас листов? 1136…
ни какого STL, только С++ как Си «с постинкрементом»
спасибо за статью, в жизни пригодится
сам свои пулы памяти «изобретаю»…
некоторые готовые использовал — не понравилось.
С самого начала:
"… превращается вот в такие макароны"
Что это?! Что оно делает? Что за типы? Что за поля?
А дальше всё становится запутанней и запутанней.
Нет разобраться можно, то проще в инете где-нибудь почитать, А те, кто сходу это понимаю и так знают алгоритм и им не нужно это читать — парадокс.
"… превращается вот в такие макароны"
descriptor_queue old_queue, new_queue;
do {
old_queue = queue_head;
desc->Next = (descriptor*)old_queue.DescAvail;
new_queue.DescAvail = (unsigned __int64)desc;
new_queue.tag = old_queue.tag + 1;
} while (!compare_and_swap64k(queue_head, old_queue, new_queue));
Что это?! Что оно делает? Что за типы? Что за поля?
А дальше всё становится запутанней и запутанней.
Нет разобраться можно, то проще в инете где-нибудь почитать, А те, кто сходу это понимаю и так знают алгоритм и им не нужно это читать — парадокс.
А я не понял, зачем нужен ocount, и как это так мы взяли и ограничили адресное пространство в 48 бит.
Пока что 48 бит это то что можно реально адресовать, так что страшного ничего не вижу. Да, в kernel mode не сработает, там чуть сложнее, ибо старший бит / биты — индикация.
Используется такой трюк чтобы не допускать возможных коллизий. Вот почему
Note that if a thread is delayed at any point while executing this routine, other active threads will be able to proceed with their operations without waiting for the delayed thread, and every time a thread executes a full iteration of the loop, some operation must have made progress.
If the CAS succeeds, then the increment of the current thread has taken effect. If the CAS fails, then the value of the counter must have changed during the loop. The only way the counter changes is if a CAS succeeds.
Then, some other thread’s CAS must have succeeded during the loop and hence that other thread’s increment must have taken effect.
Используется такой трюк чтобы не допускать возможных коллизий. Вот почему
Note that if a thread is delayed at any point while executing this routine, other active threads will be able to proceed with their operations without waiting for the delayed thread, and every time a thread executes a full iteration of the loop, some operation must have made progress.
If the CAS succeeds, then the increment of the current thread has taken effect. If the CAS fails, then the value of the counter must have changed during the loop. The only way the counter changes is if a CAS succeeds.
Then, some other thread’s CAS must have succeeded during the loop and hence that other thread’s increment must have taken effect.
Вообще «стандартный консервативный аллокатор» не так уж и плох, по крайней мере в gcc он и так оперирует аренами и всякую мелочь выделяет без локов.
Во-вторых, если хочется совсем продвинутого, то естьgoogle tcmalloc, который делает это еще лучше. Работает как drop-in replacement для стандартного аллокатора.
В тех 0.5% случаев, когда tcmalloc загнется скорее всего загнется и то что вы описали.
А вообще за статью + конечно.
Во-вторых, если хочется совсем продвинутого, то естьgoogle tcmalloc, который делает это еще лучше. Работает как drop-in replacement для стандартного аллокатора.
В тех 0.5% случаев, когда tcmalloc загнется скорее всего загнется и то что вы описали.
А вообще за статью + конечно.
Зато стандартный аллокатор от msvcrt — очень даже занимается тем что висит в giant locks (тьфу на него еще раз).
Вообще je / tc аллокаторы гораздо сложнее для понимания, тут-то весь исходник в 30 килобайт, они обозримы. Конечно, это не тот простой код из книжки Кернигана, Ритчи и Фьюэра — но тоже боле-мене понятен.
Вообще je / tc аллокаторы гораздо сложнее для понимания, тут-то весь исходник в 30 килобайт, они обозримы. Конечно, это не тот простой код из книжки Кернигана, Ритчи и Фьюэра — но тоже боле-мене понятен.
Я в конец добавил пару графиков, там в общем видно — как аллокаторы работают в разных случаях. Позаимствовал из собственных источников картинку ;-)
За статью плюс, синтаксис volatile unsigned __int64 top:46, ocount:18; увидел впервые, что за top и ocount? Гугл почему-то не помог (
P.S. Если не сложно — добавьте комментарии к коду. Хотя бы чуть-чуть.
P.S. Если не сложно — добавьте комментарии к коду. Хотя бы чуть-чуть.
Битовые поля. 64бит целое делим на битовые поля — верхнюю (top) 46 бит (адрес) и нижнюю (ocount) 18 бит, для индикации прогресса в цикле. Зачем так странно — в общем известный ход.
CAS (который compare-and-swap) атомарен только сам по себе.
И если 2 треда одновременно наступят на это — у них может получиться весьма интересный набор эффектов (ABA problem). Чтобы такого не происходило — надо использовать индикатор прогресса, и в цикле этот ocount каждый раз наращивается. Т… о. каждый раз в compare-and-swap используется уникальное число.
Конечно, 18 бит под счетчик отводить это сурово — но в работе Michael именно так. Я к примеру когда реализовывал свои lock-free lists в kernel-mode использовал пару бит всего для этого, а тут — оставил ровно как есть.
CAS (который compare-and-swap) атомарен только сам по себе.
И если 2 треда одновременно наступят на это — у них может получиться весьма интересный набор эффектов (ABA problem). Чтобы такого не происходило — надо использовать индикатор прогресса, и в цикле этот ocount каждый раз наращивается. Т… о. каждый раз в compare-and-swap используется уникальное число.
Конечно, 18 бит под счетчик отводить это сурово — но в работе Michael именно так. Я к примеру когда реализовывал свои lock-free lists в kernel-mode использовал пару бит всего для этого, а тут — оставил ровно как есть.
Я правильно понял, что освобождённые блоки по FIFO используются? Но тогда на часто выделяемых/освобождаемых блоках загрязняется кэш процессора (особенно нынешние многоуровневые большие кэши). Для аллокаторов оптимально будет LIFO — тогда есть шанс что при частом обращении блок не будет покидать кэш второго-третьего уровня.
И ещё вопрос, что значит "Выделение маленьких кусочков привяжем к нитям (а освобождение — нет)."? А именно — не понял что значит "а освобождение — нет".
И ещё вопрос, что значит "Выделение маленьких кусочков привяжем к нитям (а освобождение — нет)."? А именно — не понял что значит "а освобождение — нет".
Да, там FIFO в partial list. Это не самый лучший способ, я согласен. Однако тут я разбираю готовую работу, а не свое пишу, свое я бы немного не так делал ;-)
Да, и учтите, работа вышла аж в 2004м, кто тогда серьезно задумывался про lock-free? Все более менее известные аллокаторы появились позже, емнип. Исходная работа вообще была рассчитана на 32 бита и Linux, это уже последователи ее перенесли и адаптировали.
По выделенному тексту — я был косноязычен, согласен.
Идея тут вот в чем — при выделении памяти мы можем начальную таблицу proc heap (для блоков размером до 2К) выделить в TLS aka thread local storage. Тогда нам не надо будет задумываться о дополнительной синхронизации, мелочь — а приятно.
А вот при освобождении памяти назад — мы можем блок выделенный в одном треде освобождать в другом, поэтому в качестве penalty каждый memory block descriptor должен знать — из какого он proc heap.
Да, и учтите, работа вышла аж в 2004м, кто тогда серьезно задумывался про lock-free? Все более менее известные аллокаторы появились позже, емнип. Исходная работа вообще была рассчитана на 32 бита и Linux, это уже последователи ее перенесли и адаптировали.
По выделенному тексту — я был косноязычен, согласен.
Идея тут вот в чем — при выделении памяти мы можем начальную таблицу proc heap (для блоков размером до 2К) выделить в TLS aka thread local storage. Тогда нам не надо будет задумываться о дополнительной синхронизации, мелочь — а приятно.
А вот при освобождении памяти назад — мы можем блок выделенный в одном треде освобождать в другом, поэтому в качестве penalty каждый memory block descriptor должен знать — из какого он proc heap.
Идея про TLS уже ближе к практике.
По хорошему проблема аллокации возникает только когда она нужна очень часто для мелких блоков в многопоточной среде.
При этом основные временные затраты уходят именно на само выделение памяти. Ну и в отрыве от железа не стоит заниматься такой оптимизацией. Есть целый ворох связанных вопросов — выравнивание, кэши процессора разного уровня и т.п.
Для решения этой проблемы нет особого смысла в создании специального аллокатора, который только все усложняет.
Достаточно простого кэша заранее выделенных блоков, где суперблоки будут выделяться per cpu или per thread, а при запросе на аллокацию оттуда просто с минимальными затратами будут отдаваться готовые блоки.
CAS не панацея — фактически те же локи, вид с боку. Спинлоки и мутексы по ходу на них же и реализуются обычно. Да и не портируемо получается — CAS на разных платформах разный.
Минимизация CAS и раскидывание достаточно больших суперблоков по CPU/thread позволяет обойти дискард кэша процессора при записи в выделенные блоки.
Реальная деаллокация здесь происходит только для суперблоков — мелкие блоки просто добавляются в список доступных.
При этом даже не нужно писать аллокатор — можно взять один из многих уже готовых.
Но еще проще решить вопрос сразу на уровне приложения. Пусть выделением памяти занимается нечто системное, а кэш аллокацию построить исходя из задачи. Ну и главное помнить, что частая аллокация и деаллокакация — признак ошибки вднк проектировании.
По хорошему проблема аллокации возникает только когда она нужна очень часто для мелких блоков в многопоточной среде.
При этом основные временные затраты уходят именно на само выделение памяти. Ну и в отрыве от железа не стоит заниматься такой оптимизацией. Есть целый ворох связанных вопросов — выравнивание, кэши процессора разного уровня и т.п.
Для решения этой проблемы нет особого смысла в создании специального аллокатора, который только все усложняет.
Достаточно простого кэша заранее выделенных блоков, где суперблоки будут выделяться per cpu или per thread, а при запросе на аллокацию оттуда просто с минимальными затратами будут отдаваться готовые блоки.
CAS не панацея — фактически те же локи, вид с боку. Спинлоки и мутексы по ходу на них же и реализуются обычно. Да и не портируемо получается — CAS на разных платформах разный.
Минимизация CAS и раскидывание достаточно больших суперблоков по CPU/thread позволяет обойти дискард кэша процессора при записи в выделенные блоки.
Реальная деаллокация здесь происходит только для суперблоков — мелкие блоки просто добавляются в список доступных.
При этом даже не нужно писать аллокатор — можно взять один из многих уже готовых.
Но еще проще решить вопрос сразу на уровне приложения. Пусть выделением памяти занимается нечто системное, а кэш аллокацию построить исходя из задачи. Ну и главное помнить, что частая аллокация и деаллокакация — признак ошибки в
Еше немного дополню.
Да, решение с суперблоками под каждое ядро/поток будет неоптимальным в части фрагментации памяти.
Но вопрос в том, какова основная цель. Если скорость в какой-то опредеденной узкой задаче, то при локальных суперблоках будет получен максимальный результат. При этом чем более узкая задача, тем меньше будет и фрагментации.
Да, решение с суперблоками под каждое ядро/поток будет неоптимальным в части фрагментации памяти.
Но вопрос в том, какова основная цель. Если скорость в какой-то опредеденной узкой задаче, то при локальных суперблоках будет получен максимальный результат. При этом чем более узкая задача, тем меньше будет и фрагментации.
В целом статья понравилась НО:
1) где КОД — Я ХОЧУ КОД — GitHub в этом Вам поможет, и не забудьте добавить README.md с кратким описанием исходников + ссылку на пост
2) по поводу compare_and_swap64 не проще ли бы было сразу обернуть в ASM CMPXCHG8B? Поскольку только она гарантировано дает 1 шаговый обмен, например Apple GCC на x64 разворачивает этот код в более чем 6 инструкций — что в многопоточной среде может привести к эпик фэйлу. (говорю поскольку были случаи)
3) про грамматику и мелкие недочеты — отписал в личку.
4) от себя лично бы просил добавить к заголовкам функций комментарии для autodoc.
5) картники — о боже, зачем JPG ??? — Перезалейте например их в PNG на habrastorage — так будет реально лучше.
В целом статья хорошая от меня +1 (жаль что кармы на это не хватает).
Продолжайте дальше.
1) где КОД — Я ХОЧУ КОД — GitHub в этом Вам поможет, и не забудьте добавить README.md с кратким описанием исходников + ссылку на пост
2) по поводу compare_and_swap64 не проще ли бы было сразу обернуть в ASM CMPXCHG8B? Поскольку только она гарантировано дает 1 шаговый обмен, например Apple GCC на x64 разворачивает этот код в более чем 6 инструкций — что в многопоточной среде может привести к эпик фэйлу. (говорю поскольку были случаи)
3) про грамматику и мелкие недочеты — отписал в личку.
4) от себя лично бы просил добавить к заголовкам функций комментарии для autodoc.
5) картники — о боже, зачем JPG ??? — Перезалейте например их в PNG на habrastorage — так будет реально лучше.
В целом статья хорошая от меня +1 (жаль что кармы на это не хватает).
Продолжайте дальше.
Эээ??? Там же для винды пример там есть специальная функция на этот счёт. А на других платформах, естественно, нужно иные макросы использовать? А где Вы в GCC нашли InterlockedExchangeAdd? А если нашли, то он будет работать он же Interlocked! ASM будет не кросс-платформенно и не понятно.
Это я про compare_and_swap64, естественно.
:)
В GCC под Windows InterlockedExchangeAdd эта функция как-раз есть.
По тексту не было комментарий на эту тему, а вот пример для SSMAlloc — github.com/Naruil/SSMalloc/blob/master/include-x86_64/atomic.h о чем Я и говорил.
В GCC под Windows InterlockedExchangeAdd эта функция как-раз есть.
По тексту не было комментарий на эту тему, а вот пример для SSMAlloc — github.com/Naruil/SSMalloc/blob/master/include-x86_64/atomic.h о чем Я и говорил.
Да, конечно же я имел в виду Apple.
Приведённый Вами файл заголовка — под конкретную архитектуру и конкретный компилятор. Т.е. не переносимо. А автор явно написал, что это под Windows — там рекомендуется использовать именно InterlockedExchangeAdd. К тому же это понятнее — даже не знакомый с WinAPI поймёт что это, зачем и чем заменить на целевой платформе.
Приведённый Вами файл заголовка — под конкретную архитектуру и конкретный компилятор. Т.е. не переносимо. А автор явно написал, что это под Windows — там рекомендуется использовать именно InterlockedExchangeAdd. К тому же это понятнее — даже не знакомый с WinAPI поймёт что это, зачем и чем заменить на целевой платформе.
Вам таки реально нужен код 2004 года? ;-)
Реализаций таких много, одна из них на гитхабе, как заказывали.
Это ж больше исследовательская работа, подробно расписанная самим автором, ссылки приведены. Код там кстати ровно такой же и без комментариев.
Реализаций таких много, одна из них на гитхабе, как заказывали.
Это ж больше исследовательская работа, подробно расписанная самим автором, ссылки приведены. Код там кстати ровно такой же и без комментариев.
лучше наверно оригинал прочитать
people.cs.vt.edu/~scschnei/papers/ismm06.pdf
people.cs.vt.edu/~scschnei/streamflow/
people.cs.vt.edu/~scschnei/papers/ismm06.pdf
people.cs.vt.edu/~scschnei/streamflow/
Совершенно непонятно назвачение
Какие-то глюки были и вы их так замаскировали?
#pragma pack(1) в первой структуре и наличие unsigned __int64 _pad0[8]; (да ещё два раза) во второй.Какие-то глюки были и вы их так замаскировали?
это старый как мир прием — если не указать pack(1) то компилятор может делать выравнивание переменных шире — например по 256 байтной границе в сумме с кросс-платформенностью может выдать глюки.
для x86 это НЕ принципиально, а вот для других платформ — вполне.
для x86 это НЕ принципиально, а вот для других платформ — вполне.
Мне кажется, вы не понимаете, что делаете.
Вначале вы принудительно указали компилятору, что для этой структуры не использовать требования к alignment. Как следствие, все interlocked функции будут глючить. Смотрите здесь, например: blogs.msdn.com/b/oldnewthing/archive/2004/08/30/222631.aspx
Потом вы начали вставлять по 8*8=64 байта перед/после каждой
Вы точно разбираетесь в том, что пишете?
ps: oх, вы не автор.
Вначале вы принудительно указали компилятору, что для этой структуры не использовать требования к alignment. Как следствие, все interlocked функции будут глючить. Смотрите здесь, например: blogs.msdn.com/b/oldnewthing/archive/2004/08/30/222631.aspx
Потом вы начали вставлять по 8*8=64 байта перед/после каждой
top_aba_t (без этого же не работало, да?). В результате вместо 8-ми байтовой top_aba_t используется 130-байтовая структура.Вы точно разбираетесь в том, что пишете?
ps: oх, вы не автор.
msdn.microsoft.com/en-us/library/2e70t5y1(v=vs.80).aspx — Я предлагал использовать CMPXCHG8B для аллоцирования памяти по 8байт за 1 такт, там глюков нету — Я уже применял такой прием для атомарного изменения ячейки памяти в общей среде выполнения.
По поводу метода — это не ко мне.
А к чему тогда комментарий?
По поводу метода — это не ко мне.
А к чему тогда комментарий?
Несколько комментариев:
1. Структура данных в статье — это стек, а не очередь, она не FIFO, а LIFO. Реализовать lock-free очередь очень сложно. Почти все статьи о lock-free очередях на связных списках не верны.
2. Из статьи не понятно, зачем нужен ocount. Это реализация так назвыемых tagged pointer. Идея в том, что если бы его не было, то возможен был бы такой сценарий (называется проблемой ABA — поэтому и структура в статье называется top_aba_t):
Пусть операция pop выглядит примерно так:
В принципе код deque в статье делает именно это, но с ocount. Теперь рассмотрим такой сценарий: на вершине стека лежит элемент А, за ним элемент B (стек выглядит как A -> B). Мы запомнили snapshot = A, next = B.
В этот момент другой поток убрал элемент A, затем вставил элемент C, и вставил обратно А. Теперь стек выглядит как:
A -> C -> B
Операция pop просыпается, и ее CAS срабатывает (stack->head == snapshot, они оба равны A), и заменяет stack->head на B. Элемент C теряется.
С ocount такого не произойдет, потому что свежевставленный A будет иметь другой ocount, и CAS провалится.
ocount спасает конечно только на практике. В теории после того как мы запомнили snapshot и next другой поток может удалить A 2^18 раз, пока ocount не примет такое же значение как было, и ABA проблема опять произойдет.
На современном железе конечно никто не отводит под указатель 48 бит. Вместо этого используется две 64-битных переменных, идущих подряд, первая под указатель, вторая под ocount (теоретический сценарий с вставкой элемента А много раз становится еще более теоретическим), и используется double cas.
И пара мелких недочетов — в коде в реализации стека (очереди в терминологии статьи :)) ocount для новой переменной не копируется со старой, то есть он всегда будет равен единице (или, что более вероятно, какому-то мусору — переменная заводится на стеке, и конструктора у нее нет).
И вот такие конструкции:
Вообще говоря опасны — queue->both может поменяться между этими двумя строками. Кажется, что в этом случае это не приведет ни к чему страшному, просто провалится cas и начнется другая итерация, но не понятно, почему не присвоить в одну операцию (например можно top_aba_t сделать union с long long, и копировать этот long long).
1. Структура данных в статье — это стек, а не очередь, она не FIFO, а LIFO. Реализовать lock-free очередь очень сложно. Почти все статьи о lock-free очередях на связных списках не верны.
2. Из статьи не понятно, зачем нужен ocount. Это реализация так назвыемых tagged pointer. Идея в том, что если бы его не было, то возможен был бы такой сценарий (называется проблемой ABA — поэтому и структура в статье называется top_aba_t):
Пусть операция pop выглядит примерно так:
do {
long snapshot = stack->head;
long next = snapshot->next;
} while (!cas(&stack->head, next, snapshot));
В принципе код deque в статье делает именно это, но с ocount. Теперь рассмотрим такой сценарий: на вершине стека лежит элемент А, за ним элемент B (стек выглядит как A -> B). Мы запомнили snapshot = A, next = B.
В этот момент другой поток убрал элемент A, затем вставил элемент C, и вставил обратно А. Теперь стек выглядит как:
A -> C -> B
Операция pop просыпается, и ее CAS срабатывает (stack->head == snapshot, они оба равны A), и заменяет stack->head на B. Элемент C теряется.
С ocount такого не произойдет, потому что свежевставленный A будет иметь другой ocount, и CAS провалится.
ocount спасает конечно только на практике. В теории после того как мы запомнили snapshot и next другой поток может удалить A 2^18 раз, пока ocount не примет такое же значение как было, и ABA проблема опять произойдет.
На современном железе конечно никто не отводит под указатель 48 бит. Вместо этого используется две 64-битных переменных, идущих подряд, первая под указатель, вторая под ocount (теоретический сценарий с вставкой элемента А много раз становится еще более теоретическим), и используется double cas.
И пара мелких недочетов — в коде в реализации стека (очереди в терминологии статьи :)) ocount для новой переменной не копируется со старой, то есть он всегда будет равен единице (или, что более вероятно, какому-то мусору — переменная заводится на стеке, и конструктора у нее нет).
И вот такие конструкции:
old_top.ocount = queue->both.ocount;
old_top.top = queue->both.top;
Вообще говоря опасны — queue->both может поменяться между этими двумя строками. Кажется, что в этом случае это не приведет ни к чему страшному, просто провалится cas и начнется другая итерация, но не понятно, почему не присвоить в одну операцию (например можно top_aba_t сделать union с long long, и копировать этот long long).
Комментарий гораздо полезнее самой статьи, спасибо.
ПО поводу union — современные компиляторы, по-идее, в обоих случаях сгенерируют одинаковый код. И не понятно с чего бы union был лучше — если архитектура x32/x64 то всё равно будет не атомарно. Чем копирование юниона лучше-то?
union не обязателен, но важно не разбивать это присвоение на две команды. union упрощает с той точки зрения, что CAS принимает как аргумент long, и не придется делать каст, если сделать union.
Ваша точка зрения, что компилятор сообразит эти два присвоения преобразовать в одно 64-ех битное копирование неверно.
Ваша точка зрения, что компилятор сообразит эти два присвоения преобразовать в одно 64-ех битное копирование неверно.
Почему -- смотрите под спойлер.
В следующем коде, если бы ваше предположение было верно, все три блока в thread2 были бы идентичны, и ни один из них никогда бы ничего не вывел. На деле же скомпилированный G++ код многократно выводят OMG1
Ключи компиляции, которые я использовал:
g++ -std=c++0x test.cpp -pthread -m64 -O2
#include <thread>
#include <assert.h>
struct test_t { union { struct { volatile int64_t a:48, b:16; }; int64_t i; }; };
test_t test;
void thread1()
{
while (true)
{
test_t x;
x.a = (test.a + 1) % 1000;
x.b = x.a;
test.i = x.i;
}
}
void thread2()
{
while (true)
{
{
test_t x;
x.a = test.a;
x.b = test.b;
if (x.a != x.b) printf("OMG 1, %ld != %ld\n", x.a, x.b);
}
{
test_t x = test;
if (x.a != x.b) printf("OMG 2, %ld != %ld\n", x.a, x.b);
}
{
test_t x; x.i = test.i;
if (x.a != x.b) printf("OMG 3, %ld != %ld\n", x.a, x.b);
}
}
}
int main()
{
assert(sizeof(test_t) == 8);
std::thread t1(thread1);
std::thread t2(thread2);
t1.join();
t2.join();
return 0;
}
Ключи компиляции, которые я использовал:
g++ -std=c++0x test.cpp -pthread -m64 -O2
… а каст приведёт к нарушению strict aliasing rules.
Крайне вредная оптимизация. Будет работать на некоторых компиляторах, некоторых архитектурах при некоторых настройках. Есть мнение, что так делать нельзя. Однажды что-то изменится в компиляторе и никто и никогда не узнает, почему программа перестала работать.
Делая 64-ех битный CAS мы уже делаем определенные предположения об архитектуре (например, что она по меньшей мере 64-ех битная).
Вариант в коде в статье использует casts:
Мало того, что он использует cast, он использует C-style cast, который в С++ по хорошему не должен применяться никогда. Выше объяснили, почему такой вариант как раз-таки работать не обязан.
Использование union — это хороший способ реализовать 64-ех битный tagged pointer в данной ситуации и избежать casts.
Какой вариант вы предлагаете, если union — это «крайне вредная оптимизация»?
Вариант в коде в статье использует casts:
#define compare_and_swap64(address, old_value, new_value) \
(InterlockedCompareExchange64(\
(PLONGLONG)(address), (__int64)(new_value), (__int64)(old_value)) \
== (__int64)(old_value))
Мало того, что он использует cast, он использует C-style cast, который в С++ по хорошему не должен применяться никогда. Выше объяснили, почему такой вариант как раз-таки работать не обязан.
Использование union — это хороший способ реализовать 64-ех битный tagged pointer в данной ситуации и избежать casts.
Какой вариант вы предлагаете, если union — это «крайне вредная оптимизация»?
Кстати C-style cast это не хорошо, но не страшно. А варианту в статье, для полного счастье не хватает приведения к volatile в некоторых местах. Либо объявление, как volatile, и приведения к не-volatile там, где нужна оптимизация (да, есть случаи, когда можно убирать volatile, но это рискованный трюк).
Приведите пример. В доках по union ясно сказано, что все его элементы хранятся в одной памяти, так что же по-вашему может пойти не так? Это не праздный интерес, я как раз люблю такие вещи делать, интересно знать, почему так нельзя.
1. Вы не знаете, когда компилятор сохранит значение при присвоении. И сохранит ли он его вообще. А код многопоточный.
2. Вы снова не знаете на какой архитектуре это будет работать. То, что вы делаете предположения на счёт того, что она 64-битная ни о чём не говорит. А если её потом соберут под x86? Писать в каждом файле НЕ СОБИРАТЬ ПОД x86? А если соберут под ARM? Там вообще всё несколько иначе работает.
3. Вы в любом случае не знаете на какой архитектуре это будет работать. Кто-то когда-то расположит ваш union по не выравненному адресу и дальше поведение будет зависеть от количества процессоров, организации кэш-памяти, разрядности шины и т.п.
4. Ваш код зависит от настроек компилятора — где гарантия, что в следующих версиях, поведение компилятора будет таким же? Есть всякого рода форки GCC, поведение которых отличает от эталона.
5. При таком подходе есть риск однажды получить нарушение pointer aliasing, тогда уже кошмар начнётся — может самые непредсказуемым образом перестать работать с -O2.
Вы пытаетесь найти оправдание плохому коду? Что-то вроде, я пишу под конкретный компилятор, конкретную архитектуру и конкретные настройки? Так это как-минимум не профессионально.
2. Вы снова не знаете на какой архитектуре это будет работать. То, что вы делаете предположения на счёт того, что она 64-битная ни о чём не говорит. А если её потом соберут под x86? Писать в каждом файле НЕ СОБИРАТЬ ПОД x86? А если соберут под ARM? Там вообще всё несколько иначе работает.
3. Вы в любом случае не знаете на какой архитектуре это будет работать. Кто-то когда-то расположит ваш union по не выравненному адресу и дальше поведение будет зависеть от количества процессоров, организации кэш-памяти, разрядности шины и т.п.
4. Ваш код зависит от настроек компилятора — где гарантия, что в следующих версиях, поведение компилятора будет таким же? Есть всякого рода форки GCC, поведение которых отличает от эталона.
5. При таком подходе есть риск однажды получить нарушение pointer aliasing, тогда уже кошмар начнётся — может самые непредсказуемым образом перестать работать с -O2.
Вы пытаетесь найти оправдание плохому коду? Что-то вроде, я пишу под конкретный компилятор, конкретную архитектуру и конкретные настройки? Так это как-минимум не профессионально.
Во-первых, я не пытаюсь искать оправдание плохому коду, я искренне считаю его хорошим. Во-вторых, вы неубедительны, вы говорите, что что-то где-то когда-то может быть. Меня может автобус вечером сбить, например, я же не меняю свою жизнь из за этой вероятности. Вы либо приведите конкретный пример, либо ссылку в стандарт.
Пока мой код работал на win\linux на обоих 86- и 64-битных архитектурах и, соответственно, ОС. Машин не то чтобы много, штук 7-8 тестировалось. И под gcc(both win\linux) и под msvc компилерами работает. То есть пока все ок, ничего даже с -O3 не глючит. Код pure C98, к слову.
Под ARM, кстати, тоже работает (android-ndk), штук 8 мобильникопланшетов пробовалось.
Вот отсутствие проблем меня убеждает, а вероятность их в будущем меня может убедить только ссылкой в стандарт си.
Пока мой код работал на win\linux на обоих 86- и 64-битных архитектурах и, соответственно, ОС. Машин не то чтобы много, штук 7-8 тестировалось. И под gcc(both win\linux) и под msvc компилерами работает. То есть пока все ок, ничего даже с -O3 не глючит. Код pure C98, к слову.
Под ARM, кстати, тоже работает (android-ndk), штук 8 мобильникопланшетов пробовалось.
Вот отсутствие проблем меня убеждает, а вероятность их в будущем меня может убедить только ссылкой в стандарт си.
Странный спор. Вы мне показывает плохой код, и говорите что он работает. При этом априори известно, что он может не работать. Ну, что тут сказать, пишете такой код дальше
априори известно, что он может не работать
В том-то и дело, что мне не известно. Я вас же и прошу подтверждение этого факта привести. Нельзя же просто на слово верить. Я не могу найти в литературе по си указания на ub или еще каких противопоказаний.
Факт чего? Того, что Вы НЕ знаете, какой код сгенерирует компилятор для не-volatile обращения? Это написано в стандарте C.
В стандарте С написано, что этот код будет работать. Вернее, я не нашел там ничего насчет того, что работать он не будет. Вы же заявляете, что может и нет.
В стандарте написано, что вы не можете делать предположений о том, когда и каким образом компилятор выполнит модификацию переменной. Для многопоточного когда этого достаточно. Что они должны были ещё написать?
Вы как-то отклоняетесь от темы при этом говоря верные вещи, но не касающиеся изначального вопроса добавлять в юнион long, чтобы одной строкой кода копировать\кастовать это значение. В многопоточном коде, как вы верно сказали, все может пойти крахом, но тут что добавлять в юнион лонг, что руками кастовать и копировать — одно и то же. В любом случае нужна блокировка или что-то неблокирующее. Я, собственно, хочу сказать что этот лонг в юнионе будет вести себя точно так же, как касты руками (по крайней мере не хуже).
Я нигде не говорил, что я забиваю на синхронизацию в многопоточной среде, расчитывая на атомарность чего-либо.
Я нигде не говорил, что я забиваю на синхронизацию в многопоточной среде, расчитывая на атомарность чего-либо.
Вопрос именно в многопоточности, которая тут имеет место быть, и именно при работе с этой структурой. В иных случах (без многопоточности), если вложенная в uinion структура не слишком сложная (чтобы компилятор не запутался), то это использовать можно.
С многопоточностью же если хотим какой-то портабельности, то поле long нужно тоже сделать volatile.
Без многопоточности (и соответственно без volatile), такая оптимизация практически не имеет смысла, так как:
Последние две строки если оптимизация не '-O0' после компиляции должны быть эквивалентны (либо у компилятора должны быть основания не оптимизировать копирование — например, дальнейшее использование одного из параметров, когда можно избежать лишней команды пересылки). Об этом случае, кстати, говорится во множестве (всех?) всяких комментариев к стандарту C/C++ — не оптимизируйте копирование через union.
И ещё один момент, уж если и писать такой код, то обязательно указывая packed для структуры, т.к. если выравнивание на целевой платформе будет отличаться, то int64 может вовсе не равен двум int32.
Как-то так.
С многопоточностью же если хотим какой-то портабельности, то поле long нужно тоже сделать volatile.
Без многопоточности (и соответственно без volatile), такая оптимизация практически не имеет смысла, так как:
union {
struct {
int a;
int b;
};
long long l;
} u1,u2;
u1.a=u2.a; u1.b=u2.b;
u1.l=u2.l;
Последние две строки если оптимизация не '-O0' после компиляции должны быть эквивалентны (либо у компилятора должны быть основания не оптимизировать копирование — например, дальнейшее использование одного из параметров, когда можно избежать лишней команды пересылки). Об этом случае, кстати, говорится во множестве (всех?) всяких комментариев к стандарту C/C++ — не оптимизируйте копирование через union.
И ещё один момент, уж если и писать такой код, то обязательно указывая packed для структуры, т.к. если выравнивание на целевой платформе будет отличаться, то int64 может вовсе не равен двум int32.
Как-то так.
Кстати, если будет несколько таких присвоений, то компилятор может это соптимизировать в какие-нибудь блочные операции (в зависимости от процессора и архитектуры) и тогда вы вообще не сможете сказать, как оно работает.
Если оптимизация компилятора ломает корректность кода, то это вина компилятора и будет пофикшено. Да, баги такого типа — тот еще геморрой и проблемы, спорить не буду, но проблема не в моем коде, все-таки давайте исходить из того, что мы можем лично контролировать.
И вы не подумайте, что это я холивара ради спорю, мне реально стремно, что я ошибаюсь и все может рухнуть, и виноват буду я, а не разрабы компилера\либ\ос.
И вы не подумайте, что это я холивара ради спорю, мне реально стремно, что я ошибаюсь и все может рухнуть, и виноват буду я, а не разрабы компилера\либ\ос.
Мы НЕ можем контролировать архиеткутуру. Так как код должен быть портабельным или хотя бы легко адаптироваться. А мы НЕ знаем на каких архитектурах и компиляторах он будет работать.
И, кстати, это не вина компилятора — это и есть оптимизация. Компилятор не знает, что программист ССЗБ и собрался выстрелить себе в ногу. Никто этого фиксить не будет — это нормальное поведение. Для других случаев есть volatile, и для совсем уж тяжёлых — sheduler barrier и тому подобное.
Во второй задаче, в последнем варианте вообще может ничего не копироваться (и скорее всего не будет).
Во втором варианте второй задачи, тоже самое — может не быть копирования.
Первые вариант естественно будет приводит к коллизиям.
В любом случае, даже при известном компиляторе и архитектуре, никто ничего не гарантирует. Например может быть система с некогеренентным кэом процессоров. Или архитектура, где транзакция чтения 64-битного слова из памяти с меньшей разрядностью может быть прервана обращением другого процессора.
Или банальное нарушение выравнивание (вот напишете такой код, а он будет на packed структуре использоваться), и всё — глюки зависят от конкретной системы и процессора.
В общем, в данном случае два нарушения — приведение volatile к не-volatile в многопоточном выражении и нарушение aliasing (а если забыть и начать с указателями работать, так и вообще эпических зад начнётся из-за нарушения pointer aliasing)
Во втором варианте второй задачи, тоже самое — может не быть копирования.
Первые вариант естественно будет приводит к коллизиям.
В любом случае, даже при известном компиляторе и архитектуре, никто ничего не гарантирует. Например может быть система с некогеренентным кэом процессоров. Или архитектура, где транзакция чтения 64-битного слова из памяти с меньшей разрядностью может быть прервана обращением другого процессора.
Или банальное нарушение выравнивание (вот напишете такой код, а он будет на packed структуре использоваться), и всё — глюки зависят от конкретной системы и процессора.
В общем, в данном случае два нарушения — приведение volatile к не-volatile в многопоточном выражении и нарушение aliasing (а если забыть и начать с указателями работать, так и вообще эпических зад начнётся из-за нарушения pointer aliasing)
Короче, такой код писать нельзя ни в коем случае — этот код может работать только под конкретным компилятором, с конкретными настройками и на конкретной архитектуре (причём архитектура это не только x86/x64 и x86/ARM/MIPS, но и способ работы с памятью и кэшем, по поводу которых вообще нельзя делать никаких предположений).
Всё прочитал, ничего не понял.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Об одном методе распределения памяти