чем больше читаю про lock-free структуры данных и алгоритмы, тем больше путаницы и не уверенности порождаю в своем сознании. Дошло до того, что поймал себя на мысли, что не могу однозначно ответить на ряд простых с виду вопросов. Буду очень признателен, если кто то поможет упорядочить ту кашу, которая у меня сейчас вертится в голове. Ниже представлены типичные паттерны использования операции CAS:
1.
public static T
Change<T>(this T source, Func<T, T> operation)
where T : class
{
T original, value;
do
{
original = source;value = operation(original);
}
while (Interlocked.CompareExchange(ref source, value, original) != original);
return original;
}
2.
public static T
Change<T>(this T source, Func<T, T> operation)
where T : class
{
var original = source;while (true)
{
var value = operation(original);
if (Interlocked.CompareExchange(ref source, value, original) == original)
break;
}
return original;
}
3.
private double foo;
public double
Foo {
get { return this.foo; }
set
{
while (true)
if (Interlocked.CompareExchange(ref this.foo, this.foo + value, this.foo) == this.foo)
break;
}
}
Вопросы:
1. Имеет ли какое то значение порядок операций выделенных жирным в первом и втором примерах?
2. Тот же самый вопрос, но в случае использования подобного кода для value type?
3. Есть ли концептуальная разница между 1, 2 и 3 вариантами (за исключением первых двух вопросов) — меня смущает, что в ряде примеров авторы сохраняют исходное значение в отдельную переменную и так же поступают с вычисляемым значением, а в других нет.
4. Правильно, ли я понимаю, что CAS применяется, только при необходимости модификации shared данных с учетом возможных изменений произведенных другими потоками? Иными словами, в случае, если перезатирание данных последним потоком является нормальным поведением программы, использования CAS излишне?
UPD:
5. При использовании CAS для List<T> с целью сохранения производительности, стоит ли в обязательном порядке переопределять методы Equals для типа с которым работает список? На сколько это вообще разумно применять CAS для generic коллекций?
Здравствуйте, RQ, Вы писали:
RQ>Вопросы:
Как человек, абсолютно ничего не смыслящий в данном направлении, могу сказать, что:
RQ>1. Имеет ли какое то значение порядок операций выделенных жирным в первом и втором примерах?
И да и нет. Не имеет, потому что оба примера не жизнеспособны. Передача параметра this происходит по значению, а не по ссылке.
Поэтому любые изменения в этом методе коснутся лишь локальной переменной source, но не объекта, для которого был вызван этот метод. ref this в настоящий момент не поддерживается.
Если заменить статическим методом с ref T source в качестве первого параметра, то да, имеет.
В первом случае ты пытаешься модифицировать и сохранить последнее состояние. Если оно изменилось за время итерации — вычисляешь значение заново.
Второй пример — просто надёжный способ повиснуть в вечном цикле.
Изменение ref source за время итерации приведёт к тому, что ref source и original не будут равны, замена не будет произведена, условие не будет выполнено и будешь ты крутиться в этом цикле аж до страшного суда.
RQ>2. Тот же самый вопрос, но в случае использования подобного кода для value type?
Не имеет значения, Interlocked методы работают с ссылками, а не со значениями. Естественно, пока ты сравниваешь value-типы при помощи предназначенных для этого методов, а не их упаковки.
The objects are compared for reference equality, rather than Object.Equals.As a result, two boxed instances of the same value type (for example, the integer 3) always appear to be unequal, and no operation is performed.Do not use this overload with value types.
RQ>3. Есть ли концептуальная разница между 1, 2 и 3 вариантами (за исключением первых двух вопросов) — меня смущает, что в ряде примеров авторы сохраняют исходное значение в отдельную переменную и так же поступают с вычисляемым значением, а в других нет.
Разница есть. В третьем примере значение будет вычислено дважды, так как вначале будет выполнена левая часть сравнения, затем — правая.
Поскольку this.foo + value != this.foo, условие не будет выполнено и ты уйдёшь на новую итерацию. Для чего это может понадобиться — я не знаю.
Всё это усугубляется тем, что поле foo не volatile, а читается не посредством Inerlocked.Read(ref this.foo). Следовательно, значение может быть не актуальным и отличаться от реально записанного в ref this.foo. Ожидал ли автор этого или нет — загадка.
RQ>4. Правильно, ли я понимаю, что CAS применяется, только при необходимости модификации shared данных с учетом возможных изменений произведенных другими потоками? Иными словами, в случае, если перезатирание данных последним потоком является нормальным поведением программы, использования CAS излишне?
Interlocked-методы позволяют добиться атомарности операций. Если работа с устаревшими данными является нормальной — да, излишне.
На прикладном уровне это выглядит, как добавление объектов в более не актуальный список или инкремент из множества потоков одного и того же поля с 0 до 1, так как каждый из них прочитал начальное состояние 0 и прибавил к нему 1.
RQ>5. При использовании CAS для List<T> с целью сохранения производительности, стоит ли в обязательном порядке переопределять методы Equals для типа с которым работает список? На сколько это вообще разумно применять CAS для generic коллекций?
Не представляю о каком использовании идёт речь и какое отношение к нему имеет Equals.CompareExchange сравнивает два значения (для значимых типов) или две ссылки (для ссылочных). Метод Equals при этом не вызывается. Аналогично можно сравнить два ссылочных объекта при помощи метода ReferenceEquals. Опять же:
The objects are compared for reference equality, rather than Object.Equals.As a result, two boxed instances of the same value type (for example, the integer 3) always appear to be unequal, and no operation is performed.Do not use this overload with value types.
"Хаос всегда побеждает порядок, поскольку лучше организован." (с) Терри Пратчетт
RQ>чем больше читаю про lock-free структуры данных и алгоритмы, тем больше путаницы и не уверенности порождаю в своем сознании. Дошло до того, что поймал себя на мысли, что не могу однозначно ответить на ряд простых с виду вопросов. Буду очень признателен, если кто то поможет упорядочить ту кашу, которая у меня сейчас вертится в голове. Ниже представлены типичные паттерны использования операции CAS:
По трём примерам. Сразу: this T работать не будет. Нужен ref, иначе метод будет обновлять не исходную переменную (поле), а её копию. ref this пока нет, но будет (если планы не поменяются).
Пример 1.
* начало цикла
* запоминаем текущее значение
* считаем новое значение
* _атомарная_операция_: если запомненное текущее значение совпадает с актуальным (считаем, что никто его не поменял), то обновляем, иначе на новый круг.
Вроде всё ок, если глаз не замылился.
Пример 2.
* запоминаем текущее значение (**)
* начало цикла
* считаем новое значение
* _атомарная_операция_: если запомненное текущее значение совпадает с актуальным (считаем, что никто его не поменял), то обновляем, иначе на новый круг.
Вечная петля, если конкуренты поменяют значение после (**).
Пример 3. Баг-баг-баг.
Сразу два косяка: или некорректный атомарный инкремент, или повторные обновления после сработавшего CompareExchange.
// foo == 1, value == 10
while (true)
{
var x = this.foo; // x == 1
var y = this.foo; // соседний поток вмешивается, foo стало 2, y == 2
var t = Interlocked.CompareExchange(ref this.foo, x + value, y)
// CompareExchange сработал, но foo == 11 а не 12. t == foo
// соседний поток вмешивается, foo == 4
var z = this.foo; // z == 4
if (t == z)
break; // нифига не break, пошли на новый круг
}
Оба примера — отличный довод за "не надо вносить творческие изменения в код, работающий с shared-ресурсами". Спасибо!
RQ>Вопросы:
Я очень советую сначала разобраться в конкурентной обработке данных вообще и лишь затем копать в сторону lock-free. Штука весьма специфичная, узкоприменимая и абсолютно не прощает ошибок. Ошибки делаются очень легко, воспроизводятся очень сложно, а надёжно ловятся — ещё хуже.
Отличное обсуждение вот тут + не менее отличный совет от Джо Скита. Лично меня не тянет распространять подобный экстрим за границы очень хорошо изолированных и оттестированных кусков кода.
RQ>2. Тот же самый вопрос, но в случае использования подобного кода для value type?
Interlocked.* не умеет в произвольные value type.
RQ>4. Правильно, ли я понимаю, что CAS применяется, только при необходимости модификации shared данных с учетом возможных изменений произведенных другими потоками? Иными словами, в случае, если перезатирание данных последним потоком является нормальным поведением программы, использования CAS излишне?
Только для потокобезопасных операций над атомарными (иммутабельными) значениями. Для остальных случаев есть свои средства со своими косяками и неожиданностями.
RQ>5. При использовании CAS для List<T>
Не будет работать. Лучше использовать специализированные Concurrent* — коллекции.
Спасибо за ответы!
S>По трём примерам. Сразу: this T работать не будет.
Даже не смотря на то, что указано ограничение class? Я знал, что в случае value типов будет произведено копирование значения, но до этого момента был уверен, что в случае ссылочных типов extension метод работает со ссылкой.
S>Пример 2. S>Вечная петля, если конкуренты поменяют значение после (**).
Пример был составлен после прочтения этой статьи. В ней то ли автор ошибся (сомнительно), то ли я совсем плохо понимаю С++, у него практически подряд идут примеры:
int FAA( int * pAddr, int nIncr )
{
int ncur ;do {
ncur = *pAddr ;
} while ( !CAS( pAddr, ncur, ncur + nIncr ) ;
return ncur ;
}
bool compare_exchange( int volatile * pAddr, int& nExpected, int nNew );
int FAA( int * pAddr, int nIncr )
{
int ncur = *pAddr;do {} while ( !compare_exchange( pAddr, ncur, ncur + nIncr ) ;
return ncur ;
}
Это меня сбило с толку.
S>Пример 3. Баг-баг-баг.
Если не сложно, объясните пожалуйста разницу между моим третьим примером и этим:
int shared = 0;
void Set(int index) {
while (true) {
if (Interlocked.CompareExchange<int>(ref shared, shared | (1 << index), shared) == shared)
break; //success
}
}
S>Оба примера — отличный довод за "не надо вносить творческие изменения в код, работающий с shared-ресурсами". Спасибо!
RQ>>Вопросы:
S>Я очень советую сначала разобраться в конкурентной обработке данных вообще и лишь затем копать в сторону lock-free. Штука весьма специфичная, узкоприменимая и абсолютно не прощает ошибок. Ошибки делаются очень легко, воспроизводятся очень сложно, а надёжно ловятся — ещё хуже.
Я пытаюсь, а необходимость подпирает. Буду признателен если вы посоветуете литературу в разрезе C#. Лучшее, что я пока нашел это выше приведенная статья на habrahabr.ru, но автор приводит там примеры на С++, для меня это тяжело.
S>Interlocked.* не умеет в произвольные value type.
Вопрос был про базовые типы, но думаю, ответ я уже получил и понял.
Здравствуйте, RQ, Вы писали:
RQ>Я пытаюсь, а необходимость подпирает. Буду признателен если вы посоветуете литературу в разрезе C#. Лучшее, что я пока нашел это выше приведенная статья на habrahabr.ru, но автор приводит там примеры на С++, для меня это тяжело.
RQ>Даже не смотря на то, что указано ограничение class? Я знал, что в случае value типов будет произведено копирование значения, но до этого момента был уверен, что в случае ссылочных типов extension метод работает со ссылкой.
Даже. Ты лишь ограничиваешь множество возможных T. С тем же успехом, можешь заменить на "this object".
this — это просто синтаксический сахар, который позволяет опустить первый аргумент статического метода.
В примере ниже, автор как раз использует указатель на объект, а ты его разыменовываешь.
RQ>Пример был составлен после прочтения этой статьи. В ней то ли автор ошибся (сомнительно), то ли я совсем плохо понимаю С++, у него практически подряд идут примеры:
Читай комментарии к статье и сигнатуры методов.
RQ>Если не сложно, объясните пожалуйста разницу между моим третьим примером и этим:
Никакой разницы. Те же грабли.
"Хаос всегда побеждает порядок, поскольку лучше организован." (с) Терри Пратчетт
