Как работает потокобезопасность ImmutableList ?
От: igor-booch Россия  
Дата: 21.02.22 15:58
Оценка:
В документации заявлено, что потокобезопасно. Внутри АВЛ-дерево. На первый взгляд не видно, что потокобезопасно.
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re: Как работает потокобезопасность ImmutableList ?
От: Sharowarsheg  
Дата: 21.02.22 16:17
Оценка: +5
Здравствуйте, igor-booch, Вы писали:

IB>В документации заявлено, что потокобезопасно. Внутри АВЛ-дерево. На первый взгляд не видно, что потокобезопасно.


А что в нём может быть потоконебезопасно, если он не мутабельный, и, по сути, единственная операция, которую он умеет, это чтение?
Re[2]: Как работает потокобезопасность ImmutableList ?
От: igor-booch Россия  
Дата: 22.02.22 10:25
Оценка: :))
S>А что в нём может быть потоконебезопасно, если он не мутабельный, и, по сути, единственная операция, которую он умеет, это чтение?
Не единственная. Есть, например, операция Add(newElement). Она возвращает новый ImmutableList, который является копией текущего + newElement. Как обеспечивается потокобезопасность операции Add?
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[3]: Как работает потокобезопасность ImmutableList ?
От: samius Россия http://sams-tricks.blogspot.com
Дата: 22.02.22 10:40
Оценка: +1
Здравствуйте, igor-booch, Вы писали:

S>>А что в нём может быть потоконебезопасно, если он не мутабельный, и, по сути, единственная операция, которую он умеет, это чтение?

IB>Не единственная. Есть, например, операция Add(newElement). Она возвращает новый ImmutableList, который является копией текущего + newElement. Как обеспечивается потокобезопасность операции Add?

Add ничего не меняет в исходном дереве, только читает его.
Re[3]: Как работает потокобезопасность ImmutableList ?
От: karbofos42 Россия  
Дата: 22.02.22 10:43
Оценка: -1
Здравствуйте, igor-booch, Вы писали:

S>>А что в нём может быть потоконебезопасно, если он не мутабельный, и, по сути, единственная операция, которую он умеет, это чтение?

IB>Не единственная. Есть, например, операция Add(newElement). Она возвращает новый ImmutableList, который является копией текущего + newElement. Как обеспечивается потокобезопасность операции Add?

Её никак и не нужно обеспечивать.
Каждый поток создаст для себя копию текущего списка и в свою копию добавит новый элемент.
Чего тут синхронизировать то и защищать, если каждый со своим объектом работает и никто не пересекается?
Re[3]: Мелкая копия
От: Qbit86
Дата: 22.02.22 10:49
Оценка:
Здравствуйте, igor-booch, Вы писали:

IB>Она возвращает новый ImmutableList, который является копией текущего + newElement.


В дополнение к другим комментариям: оно не обязательно делает глубокую копию. Там внутри дерево (не плоский массив), со всеми вытекающими последствиями для асимптотики. Новый экземпляр по возможности ссылается на старое дерево. В крайнем случае, по-моему, делает перебалансированную копию.
Глаза у меня добрые, но рубашка — смирительная!
Re[3]: Как работает потокобезопасность ImmutableList ?
От: Sinclair Россия http://corp.ingrammicro.com/Solutions/Cloud.aspx
Дата: 22.02.22 11:57
Оценка: +1
Здравствуйте, igor-booch, Вы писали:

S>>А что в нём может быть потоконебезопасно, если он не мутабельный, и, по сути, единственная операция, которую он умеет, это чтение?

IB>Не единственная. Есть, например, операция Add(newElement). Она возвращает новый ImmutableList, который является копией текущего + newElement. Как обеспечивается потокобезопасность операции Add?
Давайте развернём вопрос. Как эта операция может оказаться потоконебезопасной?
Исходный список является неизменяемым. Поэтому мы можем, к примеру, мееееедленно строить его копию в любом потоке.
Копия, которую мы строим, пока что никому не видна — это локальная переменная в стеке того потока, который вызвал Add.
Поэтому её можно (временно) считать изменяемой. Мы берём, и добавляем к этой копии нужный элемент.
После этого мы наконец "публикуем" изменения — то есть возвращаем ссылку на новый список из операции Add().
Вот уже эта ссылка может быть видима в нескольких потоках — например, если мы сохранили её в поле какого-то объекта, видимого в нескольких потоках.
Но к этому моменту содержимое, на которое указывает эта ссылка, является неизменяемым, поэтому беспокоиться нам не о чем.

Эти рассуждения применимы к любому immutable-типу.
К примеру, мы могли бы построить ImmutableList поверх обычного (mutable) масссива.
Публичный API просто не выставляет методов, которые бы изменяли этот внутренний массив.
А метод Add у нас мог быть устроен вот так:
public ImmutableList<T> Add(T item)
{
   var s = Count + 1;
   var c = new T[s]; // выделяем новый массив нужного размера. 
   Array.Copy(_items, c, Count); // копируем данные из старого массива в новый
   c[Count] = item; // "добавляем" элемент, пользуясь изменяемостью массива
   return new ImmutableList(c); // вызываем приватный конструктор, который просто "заворачивает" массив в ImmutableList
}

По большому счету, реальный ImmutableList устроен точно так же, с поправкой на внутреннюю кухню — вместо T[] _items используется TreeNode<T> _root. И точно так же экземпляр ноды можно безопасно изменять вплоть до выхода из метода Add().
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
http://rsdn.org/File/5743/rsdnaddict.GIF
Re[4]: Мелкая копия
От: Sinclair Россия http://corp.ingrammicro.com/Solutions/Cloud.aspx
Дата: 22.02.22 12:05
Оценка: 6 (1) +1
Здравствуйте, Qbit86, Вы писали:
Q>В дополнение к другим комментариям: оно не обязательно делает глубокую копию. Там внутри дерево (не плоский массив), со всеми вытекающими последствиями для асимптотики. Новый экземпляр по возможности ссылается на старое дерево. В крайнем случае, по-моему, делает перебалансированную копию.
Вообще, все древовидные структуры очень дружелюбны к иммутабельности.
Любой алгоритм, изменяющий деревья, можно превратить в иммутабельный, заменив "изменение" ноды в "изготовление копии, отличающейся на указанный элемент".
При этом такое клонирование-с-изменением узла — это O(1) операция.
Более-менее все алгоритмы на деревьях уже построены так, чтобы иметь O(logN) асимптотику всех операций — включая "изменения".
Так что если у нас операция "изменить элемент по ключу" выполняется за O(logN) операций, то в immutable случаев он превращается в алгоритм, который клонирует O(logN) узлов.
А остальные N-O(logN) узлов исходного дерева повторно используются.

Дополнительной оптимизацией является поддержка "блочных" изменений — например, в дополнение к Add(T item) мы можем реализовать Add(IEnumerable<T> items), который будет минимизировать количество выделяемого мусора благодаря изменению одних и тех же узлов — ведь они не видны нигде за пределами стека текущего потока вплоть до возврата из Add().

Именно это реализовано в FCL-ном ImmutableList в виде флага Frozen, который поддерживается в узлах. Свежесозданные узлы порождаются с Frozen = false; это позволяет неоднократно изменять их.
Перед возвратом нового ImmutableList на его узлах рекурсивно выполняется Frozen=true; таким образом, невозможно получить ссылку на изменяемый узел за пределами внутренних методов.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
http://rsdn.org/File/5743/rsdnaddict.GIF
Re[4]: Мелкая копия
От: igor-booch Россия  
Дата: 22.02.22 12:13
Оценка: :))) :))
IB>>Она возвращает новый ImmutableList, который является копией текущего + newElement.
Q>В дополнение к другим комментариям: оно не обязательно делает глубокую копию. Там внутри дерево (не плоский массив), со всеми вытекающими последствиями для асимптотики. Новый экземпляр по возможности ссылается на старое дерево. В крайнем случае, по-моему, делает перебалансированную копию.

Надеялся на потокобезопасность, такую, что

            ImmutableList<int> immutableList = ImmutableList<int>.Empty;

            int loopCount = 1000000;

            ParameterizedThreadStart fillImmutableList = o =>
            {
                int loopNum = (int) o;
                for (int i = 1; i <= loopCount; i++)
                    immutableList = immutableList.Add(i * loopNum);
            };

            int threadCount = 3;
            Thread[] threads = new Thread[threadCount];

            for (int i = 0; i < threadCount; i++)
            {
                threads[i] = new Thread(fillImmutableList);
                threads[i].Start(i);
            }

            for (int i = 0; i < threadCount; i++)
                threads[i].Join();

            Debug.Assert(immutableList.Count == threadCount * loopCount);



По факту получается, что immutableList.Count < threadCount * loopCount
и в конце immutableList не ожидаемо много элементов == 0 (наверное нарушается внутреннее состояние)

Повёлся на эту статью https://nesteruk.wordpress.com/2013/07/20/%D0%BD%D0%B5%D0%BC%D1%83%D1%82%D0%B0%D0%B1%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5-%D0%BA%D0%BE%D0%BB%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B8/ и на указание в документации, что Thread safe.

Тогда не понятно
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Отредактировано 22.02.2022 12:26 igor-booch . Предыдущая версия .
Re[5]: Порядок операций
От: Qbit86
Дата: 22.02.22 12:34
Оценка: +1
Здравствуйте, igor-booch, Вы писали:

IB>Надеялся на потокобезопасность, такую, что


IB>
immutableList = immutableList.Add(i * loopNum);


Так у тебя проблема не внутри реализации ImmutableList<T>, а снаружи, при его использовании.
Если у тебя два потока одновременно начнут конструировать новые потокобезопасные экземпляры ImmutableList'а, то в результате твоя переменная immutableList будет ссылаться на одну из этих копий (которая присвоится последней), а не на смердженный магическим образом экземпляр.

Например, был у тебя массив [1, 2, 3].
1) Один поток добавляет 5 к [1, 2, 3], чтобы получить [1, 2, 3, 5].
2) Второй поток добавляет 8 к [1, 2, 3], чтобы получить [1, 2, 3, 8].
3) Потом ты присваиваешь immutableList := [1, 2, 3, 5].
4) Потом ты присваиваешь immutableList := [1, 2, 3, 8].

У тебя не будет [1, 2, 3, 5, 8] в общем случае — только если шаги выполнятся в порядке 1) 3) 2) 4).
Каждый из шагов сам по себе потокобезопасный. В совокупности же шаги твоего алгоритма (а не алгоритма ImmutableList<T>) — не потокобезопасны.
Глаза у меня добрые, но рубашка — смирительная!
Отредактировано 22.02.2022 12:40 Qbit86 . Предыдущая версия .
Re[6]: Порядок операций
От: igor-booch Россия  
Дата: 22.02.22 12:54
Оценка:
Q>Так у тебя проблема не внутри реализации ImmutableList<T>, а снаружи, при его использовании.
Q>Каждый из шагов сам по себе потокобезопасный. В совокупности же шаги твоего алгоритма (а не алгоритма ImmutableList<T>) — не потокобезопасны.
1) ok, приведите, пожалуйста, пример кода, корректно использующего потокобезопасность ImmutableList
2) Откуда нули в immutableList, при выполнении моего примера, если каждый из шагов сам по себе потокобезопасный?

Debug.Assert(immutableList.Any(i => i == 0));

выполняется
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Отредактировано 22.02.2022 12:55 igor-booch . Предыдущая версия .
Re[7]: Порядок операций
От: Qbit86
Дата: 22.02.22 13:03
Оценка:
Здравствуйте, igor-booch, Вы писали:

IB>2) Откуда нули в immutableList, при выполнении моего примера, если каждый из шагов сам по себе потокобезопасный?


Отсюда:
//                                    VVVVVVV
immutableList = immutableList.Add(i * loopNum);


//           V
for (int i = 0; ...)
{
    //               V
    threads[i].Start(i);
Глаза у меня добрые, но рубашка — смирительная!
Re[5]: Мелкая копия
От: Sharowarsheg  
Дата: 22.02.22 13:26
Оценка: 6 (1) +1
Здравствуйте, igor-booch, Вы писали:

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

IB>Тогда не понятно

IB>
Если ты хочешь зачем-то сгенерировать много вариантов добавлений, выбрать, например, лучший, и его один оставить. Тогда стадию генерации многих вариантов можно распараллелить, не опасаясь, что потоки, читающие из исходника одновременно, его испортят. Если бы был просто List, то каждому потоку пришлось бы делать свою копию List прежде, чем начинать добавлять.
Re[8]: Порядок операций
От: igor-booch Россия  
Дата: 22.02.22 13:40
Оценка:
да , спасибо
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[4]: Как работает потокобезопасность ImmutableList ?
От: igor-booch Россия  
Дата: 22.02.22 14:01
Оценка:
S>По большому счету, реальный ImmutableList устроен точно так же, с поправкой на внутреннюю кухню — вместо T[] _items используется TreeNode<T> _root. И точно так же экземпляр ноды можно безопасно изменять вплоть до выхода из метода Add().

Какой смысл в этой внутренней кухне с АВЛ деревом? Лучшая производительность?
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[5]: Как работает потокобезопасность ImmutableList ?
От: Sinclair Россия http://corp.ingrammicro.com/Solutions/Cloud.aspx
Дата: 22.02.22 15:29
Оценка: 12 (1)
Здравствуйте, igor-booch, Вы писали:
IB>Какой смысл в этой внутренней кухне с АВЛ деревом? Лучшая производительность?
Эмм, не очень понимаю смысл вопроса.
Смысл внутренней кухни — спрятать от пользователя детали реализации.
Смысл реализации на основе дерева — иметь возможность порождения копий за O(depth), а не за O(N) (как можно было бы сделать на основе массива. См. тж. std::string).
Смысл использования AVL — соблюдение балансировки дерева, чтобы иметь depth ~ log(N).
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
http://rsdn.org/File/5743/rsdnaddict.GIF
Re[3]: Как работает потокобезопасность ImmutableList ?
От: VladD2 Российская Империя www.nemerle.org
Дата: 23.02.22 00:23
Оценка: 27 (3)
Здравствуйте, igor-booch, Вы писали:

IB>Не единственная. Есть, например, операция Add(newElement). Она возвращает новый ImmutableList, который является копией текущего + newElement. Как обеспечивается потокобезопасность операции Add?


При добавлении пересоздаются элементы от корня дерева до текущего элемента. Для АВЛ-балансированного дерева — это всегда очень небольшое число элементов. По этому это относительно дешево. А главное, это потокобезопасно, так как каждое добавление порождает новое дерево. Твоя ошибка в "тесте" была в том, что ты сувал копии этого дерева в одну разделяемую переменную.

При добавлении всегда создается новая копия дерева. Для того чтобы число ветвей до корня всегда было небольшим используется балансировка. АВЛ — это название алгоритма балансировки, названного так по первым буквам авторов Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича.

В МС в алгоритмах не очень. По этому используют относительно устаревшие и неверно называют сами коллекции. По сути это не список, а упорядоченное множество. Наши местные сабакоеды (rampelstinskin акак WolfHaund на РСДН) додумались использовать для этого не АВЛ, а 2-3-деревья о которых тут многие и не слышали. По пенесометрии самих сабакоедов это значительно более быстрый алгоритм/структура даннх. .

https://github.com/rsdn/nemerle/blob/master/lib/set.n
https://github.com/rsdn/nemerle/blob/master/lib/TwoThreeTree.n
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: Как работает потокобезопасность ImmutableList ?
От: Sinclair Россия http://corp.ingrammicro.com/Solutions/Cloud.aspx
Дата: 23.02.22 05:47
Оценка: 12 (1)
Здравствуйте, VladD2, Вы писали:
VD>В МС в алгоритмах не очень. По этому используют относительно устаревшие и неверно называют сами коллекции. По сути это не список, а упорядоченное множество. Наши местные сабакоеды (rampelstinskin акак WolfHaund на РСДН) додумались использовать для этого не АВЛ, а 2-3-деревья о которых тут многие и не слышали. По пенесометрии самих сабакоедов это значительно более быстрый алгоритм/структура даннх. .

VD>https://github.com/rsdn/nemerle/blob/master/lib/set.n

VD>https://github.com/rsdn/nemerle/blob/master/lib/TwoThreeTree.n
Было бы интересно посмотреть на бенчмарки.
Я пытался улучшить ImmutableList, реализовав его в виде B-Tree, но это оказалось сложнее, чем я ожидал https://github.com/evilguest/atropos
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
http://rsdn.org/File/5743/rsdnaddict.GIF
Re[4]: Как работает потокобезопасность ImmutableList ?
От: igor-booch Россия  
Дата: 25.02.22 09:38
Оценка:
VD>Твоя ошибка в "тесте" была в том, что ты сувал копии этого дерева в одну разделяемую переменную.

Да, наверное такая структура данных, удовлетворяющая моему тесту, невозможна даже теоретически
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[5]: Как работает потокобезопасность ImmutableList ?
От: VladD2 Российская Империя www.nemerle.org
Дата: 25.02.22 19:42
Оценка:
Здравствуйте, igor-booch, Вы писали:

IB>Да, наверное такая структура данных, удовлетворяющая моему тесту, невозможна даже теоретически


Он просто бесмысленнен.

Подобные структуры данных используются для безопасной "передачи" данных между потоками, для функционального программирования и для создания множества версий данных, а не для конструирования в разных потоках. Это не императивная структура данных.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.