Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 37
Отличная статья!
А есть ли сейчас смысл писать что-то по 32-битную архитектуру? Подобные алгоритмы используются обычно для серверных приложений, где даже ARM к моменту выхода в широкое применение будет 64-битным.
А есть ли сейчас смысл писать что-то по 32-битную архитектуру? Подобные алгоритмы используются обычно для серверных приложений, где даже ARM к моменту выхода в широкое применение будет 64-битным.
Совершенно согласен! В своей повседневной профессиональной деятельности я уже лет 5 сижу на 64 битах.
Но 32 бита ещё довольно распространены, особенно для десктопных и «смартфонных» приложений. К тому же, когда пишешь некую библиотеку с замахом на общность, — 32 бита дисциплинируют. Иногда приходится поломать голову, как засунуть то, что хорошо вписывается в 64-битовую архитектуру, в 32 бита.
Но 32 бита ещё довольно распространены, особенно для десктопных и «смартфонных» приложений. К тому же, когда пишешь некую библиотеку с замахом на общность, — 32 бита дисциплинируют. Иногда приходится поломать голову, как засунуть то, что хорошо вписывается в 64-битовую архитектуру, в 32 бита.
Ну станет атомарным чтение не 32 бит, а 64 — суть-то не меняется.
И да, где в статье привязка именно к 32-битной архитектуре? (а примеры на то и примеры, что показывают конкретные числа)
И да, где в статье привязка именно к 32-битной архитектуре? (а примеры на то и примеры, что показывают конкретные числа)
По сути — да, не меняется.
Но иногда 32 бита — мало. 32 бита — это выравненность по 4 байтам, то есть 2 младших бита адреса всегда нули. В 64 — имеем нулевыми 3 младших бита. В lock-free алгоритмах часто нужно вместе с некоторым адресом атомарно поменять и некоторые статусы. Для статусов необходимо использовать как раз эти младшие свободные биты в адресе (это так называемый marked pointer), чтобы и адрес, и статусы влезли в CAS. Естественно, в 3 бита влезет больше статусов, чем в 2. Иногда этот лишний бит в 64 бывает очень полезен. А в 32-битовой архитектуре приходится явно указывать выравнивание по 8 байтам, чтобы алгоритм был работоспособным. И тут начинаются танцы с бубном — aligned-распределение памяти (оно зачастую намного медленнее и прожорливей), компиляторно-зависимые конструкции и ограничения и пр.
Но иногда 32 бита — мало. 32 бита — это выравненность по 4 байтам, то есть 2 младших бита адреса всегда нули. В 64 — имеем нулевыми 3 младших бита. В lock-free алгоритмах часто нужно вместе с некоторым адресом атомарно поменять и некоторые статусы. Для статусов необходимо использовать как раз эти младшие свободные биты в адресе (это так называемый marked pointer), чтобы и адрес, и статусы влезли в CAS. Естественно, в 3 бита влезет больше статусов, чем в 2. Иногда этот лишний бит в 64 бывает очень полезен. А в 32-битовой архитектуре приходится явно указывать выравнивание по 8 байтам, чтобы алгоритм был работоспособным. И тут начинаются танцы с бубном — aligned-распределение памяти (оно зачастую намного медленнее и прожорливей), компиляторно-зависимые конструкции и ограничения и пр.
>А есть ли сейчас смысл писать что-то по 32-битную архитектуру?
Запустите 64-битную винду. Поставьте туда все популярные браузеры (не из репозиториев, а из первой ссылки в гугле). Запустите. Откройте менеджер процессов и посмотрите на битность запущенных процессов. Все (даже дефолтый IE из 64-битной винды 8.1) будут 32-битные. И это браузеры — передовой, можно сказать, продукт. Хайтек и флаг прогресса. Стоит ли говорить, что основная масса софта ещё долго будет в основном 32-битной.
Запустите 64-битную винду. Поставьте туда все популярные браузеры (не из репозиториев, а из первой ссылки в гугле). Запустите. Откройте менеджер процессов и посмотрите на битность запущенных процессов. Все (даже дефолтый IE из 64-битной винды 8.1) будут 32-битные. И это браузеры — передовой, можно сказать, продукт. Хайтек и флаг прогресса. Стоит ли говорить, что основная масса софта ещё долго будет в основном 32-битной.
Про стоимость атомарных операций — порядок-таки изменился: uncontended lock xadd на Sandy Bridge стоит 3ns/op — это где-то десяток «обычных» инструкций.
Стоимость атомарных операций действительно может скакать на порядки в зависимости от состояния кэша: если нужная строка уже в вашем кэше и в M/E-state — стоимость будет минимальной, иначе придется долго ждать либо загрузки из основной памяти/L2/L3, либо — что еще хуже — арбитрации за владение строкой с другим ядром. Но все то же самое применимо и к обычной, не-атомарной последовательности read-modify-write — любая запись требует строку в L1 в M/E-state, и поэтому бОльшая часть затрат в неудачном варианте уходит именно на то, чтобы ее туда затащить. Разница между атомарными RMW и не-атомарными RMW в основном как раз в барьерах памяти — в неатомарном варианте высокую стоимость записи в неудачном варианте процессор может (если повезет) самортизировать за счет буферизации и спекулятивного исполнения. У атомиков же, как правило, есть семантика барьера, и потому возможности спекуляции сильно ограничены — и потому большую стоимость записи (которая ничем особо не специфична для атомиков — запись сама по себе дорогая) не удается замаскировать. Я недавно писал об этих вещах (и там в комментариях привели ссылку на статью с более детальными и современными бенчмарками инструкций синхронизации)
Стоимость атомарных операций действительно может скакать на порядки в зависимости от состояния кэша: если нужная строка уже в вашем кэше и в M/E-state — стоимость будет минимальной, иначе придется долго ждать либо загрузки из основной памяти/L2/L3, либо — что еще хуже — арбитрации за владение строкой с другим ядром. Но все то же самое применимо и к обычной, не-атомарной последовательности read-modify-write — любая запись требует строку в L1 в M/E-state, и поэтому бОльшая часть затрат в неудачном варианте уходит именно на то, чтобы ее туда затащить. Разница между атомарными RMW и не-атомарными RMW в основном как раз в барьерах памяти — в неатомарном варианте высокую стоимость записи в неудачном варианте процессор может (если повезет) самортизировать за счет буферизации и спекулятивного исполнения. У атомиков же, как правило, есть семантика барьера, и потому возможности спекуляции сильно ограничены — и потому большую стоимость записи (которая ничем особо не специфична для атомиков — запись сама по себе дорогая) не удается замаскировать. Я недавно писал об этих вещах (и там в комментариях привели ссылку на статью с более детальными и современными бенчмарками инструкций синхронизации)
Спасибо, очень интересный для меня материал, — как ваша заметка, так и ссылки. Радует, что прогресс у hardware-вендоров не стоит на месте и вместо гигагерцев они наконец-то серьезно озаботились внутренней архитектурой и разруливанием узких мест в процессорах.
Это не то чтобы прогресс… закладка в архитектуру была еще лет 10 назад, когда 64-битные процессоры еще были только в проекте. Был вероятно какой-то эксклюзив на котором это все обкатывалось и только потом весь успешный опыт пошел в массовые процессоры. Сложно вообще представить а тем более подсчитать сколько неудачных решений было отсеяно(даже не дошедших до стадии железа).
Так что верней сказать что это последствия прогресса, а сам прогресс — от там где-то в далеке. Хотя, кому-то ведь везет и он находится на вершине прогресса. Может, где-то в лабораториях уже давным давно обкатывают 128 а может даже и 1024-битные процессоры. Может даже только в симуляторах… поскольку пока процессоры общего назначения большей битности не востребованы, а вот специализированные ядрышки по 1024 бита для видеокарты или биткоин-генератора пришлись бы как раз по месту. Черт побери, а может это уже реальность?
Так что верней сказать что это последствия прогресса, а сам прогресс — от там где-то в далеке. Хотя, кому-то ведь везет и он находится на вершине прогресса. Может, где-то в лабораториях уже давным давно обкатывают 128 а может даже и 1024-битные процессоры. Может даже только в симуляторах… поскольку пока процессоры общего назначения большей битности не востребованы, а вот специализированные ядрышки по 1024 бита для видеокарты или биткоин-генератора пришлись бы как раз по месту. Черт побери, а может это уже реальность?
Вся эта «многобитность» чисто логическая, т.е существует только для асм-программиста. Внутри там все равно все АЛУшки 16-битные. Микрокод конвеера процессора разбивает 64-битные операции на набор выполняющихся частично-параллельно 16-битных.
Там чисто технологические заморочки с нагрузочной способностью транзисторов и синхронизацией. Ну т.е. на практике можно сделать АЛУ хоть на 1024 бита, только работать оно будет медленнее, чем 64 запараллеленых 16-битных + управляющая логика по той же технологии.
Там чисто технологические заморочки с нагрузочной способностью транзисторов и синхронизацией. Ну т.е. на практике можно сделать АЛУ хоть на 1024 бита, только работать оно будет медленнее, чем 64 запараллеленых 16-битных + управляющая логика по той же технологии.
Микрокод конвеера процессора разбивает 64-битные операции на набор выполняющихся частично-параллельно 16-битных.
Где вы такого набрались?
Ничего разбивать (и тем более неким «микрокодом конвеера») не нужно.
www.ee.usyd.edu.au/research/allresearch/seminars/01332644-a4GHz300mV.pdf
Вы вообще по своей же ссылке ходили?
Это 10-летний (!) дискретный (!!) 64-битный АЛУ, состоящий из двух 32-битных секций(!!!).
Это 10-летний (!) дискретный (!!) 64-битный АЛУ, состоящий из двух 32-битных секций(!!!).
И? Как будто это что-то меняет? 2 секции там потому что верхняя половина независимо отключается чтобы минимизировать утечки — для 32битных операций она не нужна. Дискретный разумеется — это результат работы R&D отдела Intel для некоего процессора. Стандартный срок проектирования больших CPU — 3-5 лет. Вполне возможно что подобный дизайн использован в Nehalem или около того. У вас есть материалы лучше? В студию!
FP ALU у какого-нибудь 5+GHz Power имеет ширину 128 бит и более.
«Микрокод конвеера» это вообще нечто.
FP ALU у какого-нибудь 5+GHz Power имеет ширину 128 бит и более.
«Микрокод конвеера» это вообще нечто.
Открою вам страшную тайну — x64 процессоры при выполнении 16- и 32-разрядных операций также не вычисляют «верхние половины», и тоже с целью минимизировать утечки, нагрев и расход энергии. Поэтому физически никаких 64-битных АЛУ (так же как и отдельных блоков MMX/SSE) в современных x86/x64 процессорах просто нет (про другие архитектуры не скажу). Конвеер разбивает 32/64 операции на последовательность 16-разрядных микроинструкций, которые выполняются частично параллельно. Именно благодаря этому факту в те же Атомы так просто и без пафоса была добавлена поддержка 64 бит.
Что касается дискретных АЛУ — то это тяжелое наследие той мрачной эпохи на заре компьютеростроения, когда необходимость обрабатывать мощные потоки данных со всяких сенсоров в реальном времени уже была, а адекватных GPU, DSP и ПЛИС ещё не было. Вот и приходилось в приёмных цепях реализовывать вычисление функций типа A*B + C*D схемотехинчески, подключая на входы дискретного сумматора выходы двух дискретных умножителей.
Что касается дискретных АЛУ — то это тяжелое наследие той мрачной эпохи на заре компьютеростроения, когда необходимость обрабатывать мощные потоки данных со всяких сенсоров в реальном времени уже была, а адекватных GPU, DSP и ПЛИС ещё не было. Вот и приходилось в приёмных цепях реализовывать вычисление функций типа A*B + C*D схемотехинчески, подключая на входы дискретного сумматора выходы двух дискретных умножителей.
Что касается дискретных АЛУ — то это тяжелое наследие той мрачной эпохи на заре компьютеростроения
Когда я упоминал Power, я имел в виду вот этот сумматор — так же вариация на тему Kogge-Stone 1973г:
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.2881&rep=rep1&type=pdf
Там ещё довольно детальная блок-схема всего ALU показана.
Схема огранизации переноса в старшие разряды и «дробление» разрядности ALU это нюансы реализации.
Поэтому физически никаких 64-битных АЛУ (так же как и отдельных блоков MMX/SSE) в современных x86/x64 процессорах просто нет
Вы хотите сказать что и скалярные и векторные данные обрабатывают одни и те же ALU?
Скандалы, интриги, расследования. Что же получается, Интел всем врёт?
Как вы обьясните, например, такую блок-схему:
www.realworldtech.com/haswell-cpu/4/
Конвеер разбивает 32/64 операции на последовательность 16-разрядных микроинструкций,
Ага, и имея всего 4 порта запуска EU они, согласно вашим словам, магически комбинируются в 64битные =)
Большинство микроопераций на выходе декодера аналогично исходным х86 включая load-op.
А вообще вы бы лучше ссылочки на соотвествующие патенты привели. Пожалуйста.
Именно благодаря этому факту в те же Атомы так просто и без пафоса была добавлена поддержка 64 бит.
А латентность не изменилась. Чудеса.
Вообще 64бит там было изначально.
x64 процессоры при выполнении 16- и 32-разрядных операций также
Почему вы кстати отрицаете связь мною приведённого Интеловского ALU для высокопроизводительных процессоров и х86?
IA64 не имеет 32битных операций и не рассчитан на высокую частоту.
Вы как-то так смело утверждаете, что volatile в C++излишне…
"Таким образом, для C++11-совместимого компилятора указание volatile для атомарной переменной излишне. А вот для старого компилятора бывает необходимо, если вы сами реализуете atomic."
Да, проблема выравнивание в C++ есть, но по-умолчанию (во всех компиляторах?) работает выравнивание не менее int. А если кто-то изменяет выравнивание, то предполагается, что он знает, что делает.
Видимо, Вы имеете в виду, что в C++11 нужно пользоваться compare_exchange? Но кроме масса готового кода, библиотек, которые использует volatile есть же множество алгоритмов, на всякого рода флажках, когда не нужно менять состояние, а только определить текущее мгновенное состояние некоторого разделяемого флага или счётчика. Там compare_exchange даже вреден бывает и без volatile не обойтись.
"Таким образом, для C++11-совместимого компилятора указание volatile для атомарной переменной излишне. А вот для старого компилятора бывает необходимо, если вы сами реализуете atomic."
Да, проблема выравнивание в C++ есть, но по-умолчанию (во всех компиляторах?) работает выравнивание не менее int. А если кто-то изменяет выравнивание, то предполагается, что он знает, что делает.
Видимо, Вы имеете в виду, что в C++11 нужно пользоваться compare_exchange? Но кроме масса готового кода, библиотек, которые использует volatile есть же множество алгоритмов, на всякого рода флажках, когда не нужно менять состояние, а только определить текущее мгновенное состояние некоторого разделяемого флага или счётчика. Там compare_exchange даже вреден бывает и без volatile не обойтись.
Да, volatile в C++11 излишне. Более того, если строго следовать стандарту, оно приводит к data race (ведь volatile обычно используют для разделяемых данных), что, согласно нового стандарта, есть undefined behaviour. То есть поведение программы никак не гарантируется.
Data race не будет только на атомарных переменных atomic (это постулируется стандартом). Поэтому в C++11 в качестве флажков нужно использовать atomic.
Compare_exchange вовсе не обязателен — можно использовать и atomic load/store (разумеется, с правильным memory_order).
Вообще про volatile в C++ была большая и интересная дискуссия среди авторов нового стандарта. С кучей примеров pro и contra. В конце концов решили, что в C++11 не будут наделять volatile какой-то магической силой, как это сделали в Java или C#.
Я так подробно расписывал compare_exchange не потому, что только его нужно использовать, а потому, что он самый удобный и распространенный для lock-free алгоритмов. Конечно, есть множество алгоритмов, построенных без compare_exchange.
Data race не будет только на атомарных переменных atomic (это постулируется стандартом). Поэтому в C++11 в качестве флажков нужно использовать atomic.
Compare_exchange вовсе не обязателен — можно использовать и atomic load/store (разумеется, с правильным memory_order).
Вообще про volatile в C++ была большая и интересная дискуссия среди авторов нового стандарта. С кучей примеров pro и contra. В конце концов решили, что в C++11 не будут наделять volatile какой-то магической силой, как это сделали в Java или C#.
Я так подробно расписывал compare_exchange не потому, что только его нужно использовать, а потому, что он самый удобный и распространенный для lock-free алгоритмов. Конечно, есть множество алгоритмов, построенных без compare_exchange.
А как же пресловутая совместимость по исходному коду, из-за которой столько говна в стандарте? Ведь 99% софта использует volatile на С/С++?
И, кстати, а если я пишу на системном уровне и ЗНАЮ, что переменная выравнена и не хочу никакого дополнительного выравнивания и мне нужно получить atomic-чтение?
Просто пример — поля структур. Вот нужно мне одновременно PACKED и atomic (вполне обычная ситуация, например, при работе с железом) — что делать? В C++11 это фактически взаимоисключающие вещи. А volatile для упакованных структур вполне имеет смысл и полезен, если программист гарантирует выравненность структуры.
Короче, с ненужностью volatile в C++11 категорически не согласен.
Просто пример — поля структур. Вот нужно мне одновременно PACKED и atomic (вполне обычная ситуация, например, при работе с железом) — что делать? В C++11 это фактически взаимоисключающие вещи. А volatile для упакованных структур вполне имеет смысл и полезен, если программист гарантирует выравненность структуры.
Короче, с ненужностью volatile в C++11 категорически не согласен.
Наверное, я был недостаточно точен.
Я не говорю про ненужность (и тем более вредность) вообще, я говорю про избыточность для атомарных переменных. Атомарная переменная — это переменная типа
Были обсуждения при подготовке стандарта, нужно или нет навешивать acquire/release семантику на чтение/записть volatile-переменных, как это сделали в C#. И было принято решение — не нужно. Эту семантику навесили на
Кстати, один из аргументов против придания
Эта структура очень большая (по объему) и никак не влезает в atomic. Поэтому и acquire/release семантику на её представителей (
Никто не отменял (или переопределял) значения
Насчет выравнивания. Атомарная переменная должна быть правильно выровнена. Это необходимое условие атомарности. Иначе — UB.
По поводу packed — это нас x86 избаловала. На другой архитектуре при попытке обращения к невыровненному
Я не говорю про ненужность (и тем более вредность) вообще, я говорю про избыточность для атомарных переменных. Атомарная переменная — это переменная типа
atomic<T>. Несмотря на то, что она определена в STL и, вроде бы, независима от самого языка, на самом деле на atomic<T> навешано довольно много семантики, то есть [очень грубо] можно считать, что atomic<T> является ключевым словом. И компиляторы, поддерживающие C++11 atomic, были существенно переработаны внутри, чтобы поддержать требования стандарта, новую модель памяти.Были обсуждения при подготовке стандарта, нужно или нет навешивать acquire/release семантику на чтение/записть volatile-переменных, как это сделали в C#. И было принято решение — не нужно. Эту семантику навесили на
atomic<T>.Кстати, один из аргументов против придания
volatile какого-то статуса в C++11 был таким:struct VeryLargeStruct {
// 100500 полей
};
VeryLargeStruct volatile x;
Эта структура очень большая (по объему) и никак не влезает в atomic. Поэтому и acquire/release семантику на её представителей (
x в данном примере) навесить не получится. Никто не отменял (или переопределял) значения
volatile, как это случилось с auto в C++11. Используйте на здоровье! Просто надо помнить, что для атомарных переменных volatile избыточна.Насчет выравнивания. Атомарная переменная должна быть правильно выровнена. Это необходимое условие атомарности. Иначе — UB.
По поводу packed — это нас x86 избаловала. На другой архитектуре при попытке обращения к невыровненному
int мы получим segmentation fault. Это и называется в стандарте «неопределенным поведением» (UB).>И, кстати, а если я пишу на системном уровне и ЗНАЮ, что переменная выравнена и не хочу никакого дополнительного выравнивания и мне нужно получить atomic-чтение?
Разве в новом стандарте нет явных барьеров памяти — как раз для тех, кто любит пожесче? По-моему, были.
А у volatile в С просто недоопределенная семантика. С ним не связано никаких барьеров памяти, это только барьер уровня компилятора. То есть компилятор-то в нужном месте выдаст store/load, а вот процессору ничего не помешает поспекулировать. Поэтому используя volatile вы вынуждены закладываться на детали какой-то конкретной железной (процессорной) модели памяти — например на то, что x86 использует total store order, и не переставляет записи. Гораздо лучше иметь возможность явно сказать «здесь я хочу семантику release», и чтобы компилятор сам в зависимости от target платформы подставил нужное.
Разве в новом стандарте нет явных барьеров памяти — как раз для тех, кто любит пожесче? По-моему, были.
А у volatile в С просто недоопределенная семантика. С ним не связано никаких барьеров памяти, это только барьер уровня компилятора. То есть компилятор-то в нужном месте выдаст store/load, а вот процессору ничего не помешает поспекулировать. Поэтому используя volatile вы вынуждены закладываться на детали какой-то конкретной железной (процессорной) модели памяти — например на то, что x86 использует total store order, и не переставляет записи. Гораздо лучше иметь возможность явно сказать «здесь я хочу семантику release», и чтобы компилятор сам в зависимости от target платформы подставил нужное.
С использованием compare_exchange примитив fetch-and-add, показанный выше, может быть написан так:
int FAA( int * pAddr, int nIncr )
{
int ncur = *pAddr;
do {} while ( !compare_exchange( pAddr, ncur, ncur + nIncr );
return ncur;
}
Если значение по адресу pAddr будет изменено другим потоком в момент после окончания
int ncur = *pAddr;но до начала выполнения
do {} ...то получится бесконечный цикл do {} while.
Это у вас ошибка, или я недопонял? Если второе, то прокомментируйте подробней пожалуйста.
Здесь используется «специальная» CAS из С++11. Чуть выше по тексту:
Поэтому это эвивалентно(вроде бы..) следующему коду с использованием CAS:
Аргумент nExpected передается по ссылке и на входе содержит ожидаемое значение переменной по адресу pAddr, а на выходе – значение перед изменением. Возвращает же функция признак успеха: true, если по адресу находится значение nExpected (в этом случае оно меняется на nNew), false в случае неудачи (тогда nExpected будет содержать текущее значение переменной по адресу pAddr).
Поэтому это эвивалентно(вроде бы..) следующему коду с использованием CAS:
int ncur;
do { ncur = *pAddr; } while ( !CAS( pAddr, ncur, ncur + nIncr ) );
return ncur;
Есть ли проблема ABA в языках с GC, например Java? Решим ли мы проблему если никогда не будем освобождать выделенную память?
Мне трудно ответить на этот вопрос, так как я не знаток Java. Поэтому могу только поразмышлять.
Если мы говорим о физическом удалении, то ABA-проблема возникает при удалении (delete) и тут же включении вновь (allocate) некоего элемента. Удаление в C++ — это физическое удаление. В языках же с GC физического удаления не произойдет, пока кто-то держит ссылку на удаляемый элемент. Такую локальную ссылку какой-то поток держит (тот, который работает с CAS, на котором возникает ABA). Поэтому мой ответ — да, языки с GC свободны от ABA-проблемы.
Ответ на второй вопрос — решим ли мы проблему если никогда не будем освобождать выделенную память — скорее отрицательный. В общем случае не решим.
Рассмотрим такой пример, на двух lock-free интрузивных стеках (интрузивный контейнер — хранит не копии данных, а сами данные, — сишный подход, позволяет избавиться от аллокатора в контейнере): поток 1 делает
Вслед за этим поток 1 выполняет CAS, меняя
Кажется, что этот пример входит в противоречие с моим первым утверждением — языки с GC свободны от ABA. На самом деле, противоречия нет. Языки с GC не позволяют работать с сырыми указателями (а если всё же позволяют, то на ваш страх и риск).
PS: смотрите внимательно, я могу наврать в примерах. ABA — очень тонкая вещь для обнаружения и объяснения, хотя и очень понятная, когда (и если :) разберешься.
Если мы говорим о физическом удалении, то ABA-проблема возникает при удалении (delete) и тут же включении вновь (allocate) некоего элемента. Удаление в C++ — это физическое удаление. В языках же с GC физического удаления не произойдет, пока кто-то держит ссылку на удаляемый элемент. Такую локальную ссылку какой-то поток держит (тот, который работает с CAS, на котором возникает ABA). Поэтому мой ответ — да, языки с GC свободны от ABA-проблемы.
Ответ на второй вопрос — решим ли мы проблему если никогда не будем освобождать выделенную память — скорее отрицательный. В общем случае не решим.
Рассмотрим такой пример, на двух lock-free интрузивных стеках (интрузивный контейнер — хранит не копии данных, а сами данные, — сишный подход, позволяет избавиться от аллокатора в контейнере): поток 1 делает
stack1.pop(), доходит до CAS и, к примеру, вытесняется. Поток 2, пока первый вытеснен, успевает сделать:T * a = stack1.pop() ;
T * anext = stack1.pop() ;
stack1.push( a ) ;
stack2.push( anext );
Вслед за этим поток 1 выполняет CAS, меняя
a на anext, который он запомнил. Но anext теперь включен в stack2! Нарушение stack1: он теперь будет указывать в stack2. ABA-проблема, без освобождения выделенной памяти.Кажется, что этот пример входит в противоречие с моим первым утверждением — языки с GC свободны от ABA. На самом деле, противоречия нет. Языки с GC не позволяют работать с сырыми указателями (а если всё же позволяют, то на ваш страх и риск).
PS: смотрите внимательно, я могу наврать в примерах. ABA — очень тонкая вещь для обнаружения и объяснения, хотя и очень понятная, когда (и если :) разберешься.
Спасибо за развернутый ответ!
AFAIK в JAVA есть CAS для указателей и кроме того определена memory model довольно тщательно, народ делает lock-free в Java.
Пример с перетыканием узла из одного списка в другой интересен, мне это не приходило в голову.
Существуют ли lock-free контейнеры с поддержкой такой операции? Кажется, что в общем случае такое эффективно не сделать (в отличии от отложенного удаления элемента, здесь нам важна задержка до момента, когда на объект больше нет ссылок).
Я где то видел такой подход по противодействию ABA — внедрение счетчика в неиспользуемые биты указателя. Насколько такое эффективно при «достаточной» разрядности счетчика? Может быть выделять память под lock-free элементы специальным аллокатором, и надеяться, что при 64 битных указателях мы сможем организовать счетчики большой разрядности?
AFAIK в JAVA есть CAS для указателей и кроме того определена memory model довольно тщательно, народ делает lock-free в Java.
Пример с перетыканием узла из одного списка в другой интересен, мне это не приходило в голову.
Существуют ли lock-free контейнеры с поддержкой такой операции? Кажется, что в общем случае такое эффективно не сделать (в отличии от отложенного удаления элемента, здесь нам важна задержка до момента, когда на объект больше нет ссылок).
Я где то видел такой подход по противодействию ABA — внедрение счетчика в неиспользуемые биты указателя. Насколько такое эффективно при «достаточной» разрядности счетчика? Может быть выделять память под lock-free элементы специальным аллокатором, и надеяться, что при 64 битных указателях мы сможем организовать счетчики большой разрядности?
Про Java. Могу сказать, что изобретатели lock-free алгоритмов очень любят Java (вся книга Shavit & Herlihy «The Art of Multiprocessor programming» наполнена примерами только на Java). И это понятно: в Java они избавлены от необходимости следить за указателями, за правильным (в подходящий момент) удалением и пр. — за них все делает GC. Поэтому портировать Java-алгоритмы на C++ бывает довольно сложно.
Существуют ли lock-free контейнеры с поддержкой такой операции?
Явных контейнеров с перетаскиванием не встречал. Хотя такая задача иногда возникала на практике. Обходился своими силами — если понимаешь, как контейнер реализован (вернее, когда можно удаленный элемент контейнера 1 поместить в контейнер 2, — это уже из области алгоритмов safe memory reclamation типа Hazard Pointer), это не представляет труда.
внедрение счетчика в неиспользуемые биты указателя — совершенно верно! Это техника tagged pointers. В статье я утверждаю, что для неё нужен dwCAS, но на самом деле — не всегда. Можно использовать и неиспользуемые биты указателя. В современных 64-битовых платформах на самом деле адресуется, вроде бы, 48 бит (или 42? — не помню). Остальное может быть, в принципе, использовано. Насколько я знаю, boost.lockfree построен на этом.
Мне такой подход не нравится, — нет никакой уверенности, что в какой-то прекрасный момент производитель не сделает настоящий 64-битный адрес. И всё — наш алгоритм отправится на свалку :-(
Про достаточную разрядность счетчика — интересный и хороший вопрос! На этот счет были исследования. Насколько я помню (пруф сейчас не готов указать), их результатом было: достаточно 32-битового счетчика. Меньше — можно попасть на переполнение в неподходящий момент (а следствие — ABA). Обоснование: таймслот, выделяемый ОС для потока. Например, где-то в mail-list разработчиков Линукса я встречал такую оценку таймслота: 300 — 500 тысяч «простых» инструкций. После этого поток вытесняется. 300 тысяч не влезут в 16 бит. Это ещё один аргумент против использования 16 бит 64-битового указателя.
Про специальный аллокатор. Здесь я ничего сказать не могу, — очень большая тема. Я остановился на схемах безопасного освобождения памяти (Hazard Pointer, Pass-the-Buck, RCU), они решают все эти вопросы про ABA и освобождение (конечно, при правильном приготовлении :-) Повесить это на аллокатор… Нужно думать
Существуют ли lock-free контейнеры с поддержкой такой операции?
Явных контейнеров с перетаскиванием не встречал. Хотя такая задача иногда возникала на практике. Обходился своими силами — если понимаешь, как контейнер реализован (вернее, когда можно удаленный элемент контейнера 1 поместить в контейнер 2, — это уже из области алгоритмов safe memory reclamation типа Hazard Pointer), это не представляет труда.
внедрение счетчика в неиспользуемые биты указателя — совершенно верно! Это техника tagged pointers. В статье я утверждаю, что для неё нужен dwCAS, но на самом деле — не всегда. Можно использовать и неиспользуемые биты указателя. В современных 64-битовых платформах на самом деле адресуется, вроде бы, 48 бит (или 42? — не помню). Остальное может быть, в принципе, использовано. Насколько я знаю, boost.lockfree построен на этом.
Мне такой подход не нравится, — нет никакой уверенности, что в какой-то прекрасный момент производитель не сделает настоящий 64-битный адрес. И всё — наш алгоритм отправится на свалку :-(
Про достаточную разрядность счетчика — интересный и хороший вопрос! На этот счет были исследования. Насколько я помню (пруф сейчас не готов указать), их результатом было: достаточно 32-битового счетчика. Меньше — можно попасть на переполнение в неподходящий момент (а следствие — ABA). Обоснование: таймслот, выделяемый ОС для потока. Например, где-то в mail-list разработчиков Линукса я встречал такую оценку таймслота: 300 — 500 тысяч «простых» инструкций. После этого поток вытесняется. 300 тысяч не влезут в 16 бит. Это ещё один аргумент против использования 16 бит 64-битового указателя.
Про специальный аллокатор. Здесь я ничего сказать не могу, — очень большая тема. Я остановился на схемах безопасного освобождения памяти (Hazard Pointer, Pass-the-Buck, RCU), они решают все эти вопросы про ABA и освобождение (конечно, при правильном приготовлении :-) Повесить это на аллокатор… Нужно думать
«Специальный аллокатор» — подразумевалась процедура, которая возвращает указатели с «особыми свойствами». Например, резервирует 4ГБ адресного пространства и выделяет память внутри этих 4 ГБ, в указателях будет задействовано только 32 бита, а все остальное можно использовать под счетчики.
Субаллокатор и offset-указатели… Да, согласен, на этом пути можно добиться многого. Готовых решений, заточенных под lock-free, я не знаю. Быть может, вы будете первым, кто реализует подобное?.. Я серьезно, без всякой иронии. Дерзайте!
Что-то подобное делает JVM автоматически, если размер кучи на 64-битной системе меньше некого предела. До 4Гб большинство указателей будут прозрачно 32-битными указатели, до 32Гб — с offset-ом (где можно, конечно — иногда придется их разворачивать в полные)
Уходите вы уже с ваших C++ — у нас, на яве, такие печеньки для concurrency… :)
Уходите вы уже с ваших C++ — у нас, на яве, такие печеньки для concurrency… :)
И это понятно: в Java они избавлены от необходимости следить за указателями, за правильным (в подходящий момент) удалением и пр. — за них все делает GC.
Решит ли ABA проблему в C++ использование объектов со встроенным GC таких как shared_ptr?
В принципе, да, если все аккуратно сделать. У Вильямса в C++ Concurrency in Action приводятся стек и очередь на shared_ptr. Другое дело, что это не всегда будет эффективно.
В языках с GC в первом приближении ABA нет — и это их огромнейшее достоинство в области lock-free.
Но, конечно, если вы начинаете делать свой собственный memory-management, скажем, заводите пул объектов, чтобы снять нагрузку на GC — вы можете получить ABA назад. Нужно быть очень аккуратным, когда делаете одновременно lock-free и GC-less компоненты.
Но, конечно, если вы начинаете делать свой собственный memory-management, скажем, заводите пул объектов, чтобы снять нагрузку на GC — вы можете получить ABA назад. Нужно быть очень аккуратным, когда делаете одновременно lock-free и GC-less компоненты.
Подскажите, есть ли какой-нибудь "толстый" материал чтобы понимать внутренности процессора, битность, кэши и прочие детали упомянутые в этой статье и последующих, спасибо
Мне такой материал неизвестен.
Есть многотомные описания для каждой модели процессора (не архитектуры, а фактически каждой модели), там есть всё, но в 10-ти томах
Можно эту статью, например, почитать: Ulrich Drepper — What Every Programmer Should Know About Memory.
Она старая, но хороший старт в этих вопросах.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Lock-free структуры данных. Основы: Атомарность и атомарные примитивы