Re[6]: Как работает потокобезопасность ImmutableList ?
От: igor-booch Россия  
Дата: 28.02.22 10:44
Оценка:
VD>Он просто бесмысленнен.

Получается это
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/
не правда?
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[5]: Как работает потокобезопасность ImmutableList ?
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.02.22 21:03
Оценка:
Здравствуйте, Sinclair, Вы писали:

S>Я пытался улучшить ImmutableList, реализовав его в виде B-Tree, но это оказалось сложнее, чем я ожидал https://github.com/evilguest/atropos


Бенчмарки писал Вольфхаунд. Я ему где-то написал, что особого смысла в переписывании Set-а на 2-3-деревьях не вижу. Он решил доказать. Формально доказал, но когда мы померили время компиляции немерла, то оно почти не отличалось, т.е. в реально жизни одна структура не определяет.

Не знаю уж остались ли у Вольфхаунда тесты. Но ты можешь написать и новые. Немерловые коллекции без проблем можно из Шарпа использовать. Скачай Nemerle.dll отсюда и попробуй. Не уверен, правда, что там релизная сборка. Но все же.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Как работает потокобезопасность ImmutableList ?
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.02.22 21:09
Оценка: +1
Здравствуйте, igor-booch, Вы писали:

IB>Получается это

IB>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/
IB>не правда?

Что, конкретно? Я не телепат.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Как работает потокобезопасность ImmutableList ?
От: igor-booch Россия  
Дата: 01.03.22 14:46
Оценка:
IB>>Получается это
IB>>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/
IB>>не правда?

VD>Что, конкретно? Я не телепат.


Там основная идея, что с помощью ImmutableHasSet можно реализовать брокер событий.
То есть поле с коллекцией подписок (ImmutableHasSet),
к нему есть доступ из многих потоков
(на подписку
и энумерацию при публикации события)
Статья имеет незавершенный вид, неизвестно точно как автор хотел в конечном итоге реализовать,
может предполагаться, что для подписок доступ синхронизируется через монитор.
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[6]: lock-free алгоритмы
От: igor-booch Россия  
Дата: 01.03.22 14:54
Оценка: +1
IB>>где применять ImmutableList?
S>Если ты хочешь зачем-то сгенерировать много вариантов добавлений, выбрать, например, лучший, и его один оставить. Тогда стадию генерации многих вариантов можно распараллелить, не опасаясь, что потоки, читающие из исходника одновременно, его испортят. Если бы был просто List, то каждому потоку пришлось бы делать свою копию List прежде, чем начинать добавлять.

Ещё важное применение: lock-free алгоритмы. В них важно уметь быстро создавать модифицированную копию. Вот мой пример исправленный


            void Add<T>(ref ImmutableList<T> location, T value)
            {
                var priorCollection = Volatile.Read(ref location);
                bool successful;
                do
                {
                    var updatedCollection = priorCollection.Add(value);
                    var interlockedResult = Interlocked.CompareExchange(ref location, updatedCollection, priorCollection);
                    successful = object.ReferenceEquals(priorCollection, interlockedResult);
                    priorCollection = interlockedResult;
                }
                while (!successful);
            }

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

            int loopCount = 1000000;

            ParameterizedThreadStart fillImmutableList = o =>
            {
                int loopNum = (int) o;
                for (int i = 1; i <= loopCount; i++)
                    Add(ref immutableList, 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 + 1);
            }

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

            Debug.Assert(immutableList.Count == threadCount * loopCount);
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[9]: Как работает потокобезопасность ImmutableList ?
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.03.22 16:22
Оценка:
Здравствуйте, igor-booch, Вы писали:

IB>Там основная идея, что с помощью ImmutableHasSet можно реализовать брокер событий.


Применение явно не по делу, но в принципе можно.

IB>То есть поле с коллекцией подписок (ImmutableHasSet),

IB>к нему есть доступ из многих потоков

В статье об этом не годится. Может подписка из одного потока идет, например, UI-потока. Тогда все ОК.

Метод Subscribe не потокобезопасен. Если он вызывается из разных потоков, в нем нужно добавить лочку. Иначе может оказаться, что параллельная подписка будет потеряна (как в твоем тесте).

IB> (на подписку

IB> и энумерацию при публикации события)

Вот при переборе проблем не будет, по указанным в статье основаниям. Сам список неизменяемый, а операция чтения ссылки в дотнете является атомарной.

IB>Статья имеет незавершенный вид, неизвестно точно как автор хотел в конечном итоге реализовать,

IB>может предполагаться, что для подписок доступ синхронизируется через монитор.

Я тебе так скажу. Пример в статье не просто надуманный, а дурацкий. А сам писатель не действующий программист, а евангелист Майкрософт. Ждать от него рабочего кода и примера для подражания я бы не стал.

Для реализации описанной в статье идеи проще взять ImmutableArray, так как подписчиков (обычно) мало и подписки делаются очень редко или связанный список (который дешевле всего при добавлении). Доступ на запись к полю обезопасить лочкой. Ну, а чтение (перебор) будет потокобезопасным.

В общем, не надо путать потокобезопасность структуры данных и поля/переменной в которой она хранится. Просто надо помнить, что чудес не бывает и если ты решил сделать глобальный склад, то без синхронизации не обойтись. Неизменяемые структуры позволяют тебе пользоваться тем фактом, что каждая их копия создает версию данных. По этому ты можешь смело перебирать их не боясь, что элементы изменятся. Атомарность чтения поля позволяет не делать лочек на чтение поля при переборе. Но запись поля (и предварительное ее чтение) должна быть защищена, так как одна версия может быть затерта другой.

Кстати, ImmutableHashSet и ImmutableList это разные вещи. Посмотрел последний внимательнее. Там вообще шиза. АВЛ-дерево там используются для упорядочивания по индексу. То есть это все таки список, но устроен он как словарь отображающий целочисленные индексы на значения. Его Add устроен вот так:
        public ImmutableList<T> Add(T value)
        {
            return Insert(Count, value);
        }


Т.е. такая штука нужна только если тебе важен порядок добавления, а элементов может быть довольно много. Для хранения списка подписок оно на фиг е нужно (закладываться на порядок подписок — плохая идея). Но это свойство обеспечивается и куда более простым ImmutableArray. Разница лишь в том, что при создании ImmutableArray-я будет перезанята память под все элементы, а в ImmutableList только для элементов от корня до текущего индекса. Но количество заёмов памяти будет больше. И памяти ImmutableList будет занимать существенно больше, так как каждый его элемент будет являться объедком. Перебор у ImmutableList тоже будет существенно дороже. Плюс из-за фрагментации памяти могу пойти промахи по кэшу (ну это уже совсем микроменеджмент, но иногда и он влияет).

Короче, ImmutableList штука весьма специфическая. Нужен он при частом доступе по индексу в купе с использованием версионности неизменяемых структур данных.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: Как работает потокобезопасность ImmutableList ?
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.03.22 16:27
Оценка:
Здравствуйте, igor-booch, Вы писали:

IB>Статья имеет незавершенный вид, неизвестно точно как автор хотел в конечном итоге реализовать,

IB>может предполагаться, что для подписок доступ синхронизируется через монитор.

Поглядел комментарии к статье. Там первый же комментарием идет замечание о непотокобезопасности Subscribe и автор это признает.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: Как работает потокобезопасность ImmutableList ?
От: samius Россия http://sams-tricks.blogspot.com
Дата: 01.03.22 16:42
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Метод Subscribe не потокобезопасен. Если он вызывается из разных потоков, в нем нужно добавить лочку. Иначе может оказаться, что параллельная подписка будет потеряна (как в твоем тесте).


Или в цикле Interlocked.Exchange с новой коллекцией пока не получится корректно подменить старую и без лочки. При большой нагрузке на подписку/отписку можно и просесть с избыточными обновлениями коллекций (которые уйдут в молоко с неудачной попыткой обновления), но подписка и не должна быть узким местом в производительности.

пы.сы. Сначала написал, потом прочитал этот ответ
http://rsdn.org/forum/dotnet/8215518.1
Автор: igor-booch
Дата: 01.03 17:54
Отредактировано 01.03.2022 16:45 samius . Предыдущая версия .
Re[11]: Как работает потокобезопасность ImmutableList ?
От: VladD2 Российская Империя www.nemerle.org
Дата: 01.03.22 20:27
Оценка:
Здравствуйте, samius, Вы писали:

S>Или в цикле Interlocked.Exchange с новой коллекцией пока не получится корректно подменить старую и без лочки.


Тогда уж хотя бы SpinWait используйте.

S>При большой нагрузке на подписку/отписку можно и просесть с избыточными обновлениями коллекций (которые уйдут в молоко с неудачной попыткой обновления), но подписка и не должна быть узким местом в производительности.


Большая нагрузка на подписку/отписку говорит о ошибке в проектировании. А если они относительная редкость, то и оптимизировать их особо нет смысла.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: Как работает потокобезопасность ImmutableList ?
От: samius Россия http://sams-tricks.blogspot.com
Дата: 02.03.22 04:53
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, samius, Вы писали:


VD>Тогда уж хотя бы SpinWait используйте.


S>>При большой нагрузке на подписку/отписку можно и просесть с избыточными обновлениями коллекций (которые уйдут в молоко с неудачной попыткой обновления), но подписка и не должна быть узким местом в производительности.


VD>Большая нагрузка на подписку/отписку говорит о ошибке в проектировании. А если они относительная редкость, то и оптимизировать их особо нет смысла.

Подход довольно широко используется и даже есть хелперы для него. Проблема в том, что пример неудачный. И я почему-то решил обозначить тонкое место подхода под нагрузской (в широком смысле) на примере подписки, который был выше, так и получилась нагрузка на подписку.
Re[7]: lock-free алгоритмы
От: samius Россия http://sams-tricks.blogspot.com
Дата: 02.03.22 04:55
Оценка: 78 (1)
Здравствуйте, igor-booch, Вы писали:

IB>>>где применять ImmutableList?

S>>Если ты хочешь зачем-то сгенерировать много вариантов добавлений, выбрать, например, лучший, и его один оставить. Тогда стадию генерации многих вариантов можно распараллелить, не опасаясь, что потоки, читающие из исходника одновременно, его испортят. Если бы был просто List, то каждому потоку пришлось бы делать свою копию List прежде, чем начинать добавлять.

IB>Ещё важное применение: lock-free алгоритмы. В них важно уметь быстро создавать модифицированную копию. Вот мой пример исправленный


Погляди на вот эти хелперы
https://docs.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutableinterlocked

В них сразу зацикленный CompareExchange используется.
Re[8]: lock-free алгоритмы
От: igor-booch Россия  
Дата: 02.03.22 08:27
Оценка:
S>Погляди на вот эти хелперы
S>https://docs.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutableinterlocked

Я на них и глядел когда свой пример исправлял,
в них для ImmutableList нет методов
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания
http://rsdn.ru/Info/rules.xml
Re[9]: lock-free алгоритмы
От: samius Россия http://sams-tricks.blogspot.com
Дата: 02.03.22 08:52
Оценка:
Здравствуйте, igor-booch, Вы писали:

S>>Погляди на вот эти хелперы

S>>https://docs.microsoft.com/en-us/dotnet/api/system.collections.immutable.immutableinterlocked

IB>Я на них и глядел когда свой пример исправлял,

хорошо
IB>в них для ImmutableList нет методов
Обе перегрузки Update должны подойти для ImmutableList.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.