Здравствуйте, remark, Вы писали:
R>Я обычно пользуюсь до смешного тупым паттерном:
Ну то есть свой аналог CDS?
R>Проблема, что кода много, тут не проблема, т.к. схема реализации тупа как тумбочка.
Проблема в том, что производительность этой схемы не ахти. Лок на каждый чих. Для типовых современных многопоточных задач это обычно не страшно, но если нам именно вычисления многопоточные нужны для ускорения единой задачи на многоядерниках, может не прокатить.
... << RSDN@Home 1.2.0 alpha 4 rev. 1095 on Windows Vista 6.0.6001.65536>>
Здравствуйте, remark, Вы писали:
R>Но когда mutable объект находится внутри uniqueness объекта, то на mutable объект тоже гарантированно только одна ссылка. Правильно?
Внутри uniqueness объекта куча mutable объектов могут создавать произвольные графы.
R>Ну вообще, в совсем общем случае, — нет. R>Например, счётчик ссылок можно модифицировать одновременно из разных потоков с помощью атомарных операций.
Неявный мьютекс.
R>А насколько ты считаешь это проблемой? R>По моему личному опыту, это НЕ ПРОБЛЕМА. Ну то есть, конечно, если это так, то хорошо; но если и не так, то тоже нормально.
Людей которые разбираются в многопоточности на твоем уровне ой как мало.
Даже просто способных написать код без race condition'ов не все могут.
А если учесть еще существование различных библиотек с хрен хнает какими неявными контрактами
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Cyberax, Вы писали:
C>На самом деле, у тебя получается вещь, изоморфная обычным мьютексам (которые тоже могут в один момент времени быть захваченными только в одном экземпляре).
Вобще говоря все операции синхронизации изоморфны... те через один примитив можно реализовать любой другой...
Главное отличие от мьютексов в том что у меня четко определен объект защиты.
Еще эта система обладает возможностью спокойно перекинуть весь uniqueness объект на другую машину...
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Главное отличие от мьютексов в том что у меня четко определен объект защиты. WH>Еще эта система обладает возможностью спокойно перекинуть весь uniqueness объект на другую машину...
Идея неплохая. Но оно не решит проблемы дэдлоков — мне больше STM/HTM тут нравится.
До меня только что дошло, что я использую этот паттерн уже года четыре в С++
Здравствуйте, Cyberax, Вы писали:
C>Идея неплохая. Но оно не решит проблемы дэдлоков —
А я вобще не вижу способа ее решить не превратив жизнь программистов в ад.
А если вспомнить про распределеннае дедлоки, лайвлоки, старвейшены,... Короче голову никто не отменял.
Тем не менее безгеморойная гарантированная защита от локальных race condition'ов уже многого стоит.
C>мне больше STM/HTM тут нравится.
1)STM не работает. Вобще.
2)С HTM то же не все понятно. Скорей всего будет та же байда.
3)Проблем дедлоков и тп они то же не решат. Вспомни хотябы про дедлоки у MSSQL и "не могу сериализовать" у Oracle...
C>До меня только что дошло, что я использую этот паттерн уже года четыре в С++
А local_ptr может передавать владение так же как std::auto_ptr?
А про барьеры памяти local_ptr не забывает?
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, remark, Вы писали:
R>>Но когда mutable объект находится внутри uniqueness объекта, то на mutable объект тоже гарантированно только одна ссылка. Правильно? WH>Внутри uniqueness объекта куча mutable объектов могут создавать произвольные графы.
У меня сложилось впечатление, что remark интересовался следующей ситуацией:
— существует некий граф mutable объектов и среди них объект "А" на ктр существует произвольное количество ссылок
— возникает необхродимость передать этот объект "А" в другой поток, для этого его надо поместить в uniqueness объект и отдать в этой обертке в другой поток. правильно?
— но тут основной вопрос, что делать с тем, что у первого потока остаются ссылки на "А" из упомянутого графа
— придется либо копировать "А" либо в процесе помещения его в uniquness объект как-то обрезать ссылки или требовать, чтобы их не было?
Здравствуйте, RailRoadMan, Вы писали:
RRM>У меня сложилось впечатление, что remark интересовался следующей ситуацией: RRM>- существует некий граф mutable объектов и среди них объект "А" на ктр существует произвольное количество ссылок RRM>- возникает необхродимость передать этот объект "А" в другой поток, для этого его надо поместить в uniqueness объект и отдать в этой обертке в другой поток. правильно?
Вот на это месте ты получишь по рукам от компилятора.
Ибо нельзя передать ссылку на mutable объект в uniqueness объект.
Ни через методы ни через конструктор. Вернуть mutable объект то же нельзя.
mutable объект можно только создать внутри uniqueness объекта и работать с ним то же только внутри этого объекта.
Те тебе придется изменить архитектуру чтобы такого небыло.
Впрочем тебе это придется делать по любоу иначе получишь RC от которого и бежали.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, remark, Вы писали:
R>Интересно а какой производительности можно добиться для таких аппаратных примитивов синхронизации? Понятно, что можно сделать более специализировано, чем кэш, но фактор расстояния всё равно остаётся... R>Кстати, а как быть с многопроцессорными системами? Надо ещё какой-то отдельный канал между процессорами и специальный протокол для этих целей...
Никак, речь шла о многоядерных. Передавать поток с одного многоядерного процессора на другой — это моветон, ИМХО.
R>Похоже, что HTM как раз и есть реализация таких хардварных примитивов синхронизации. По крайней мере её можно так использовать (HTM lock elission). Причём похоже, что на Sun Rock такая хитрая реализация мьютексов (через HTM lock elission) работает таки быстрее честных мьютексов и масштабируется лучше.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, RailRoadMan, Вы писали:
RRM>>У меня сложилось впечатление, что remark интересовался следующей ситуацией: RRM>>- существует некий граф mutable объектов и среди них объект "А" на ктр существует произвольное количество ссылок RRM>>- возникает необхродимость передать этот объект "А" в другой поток, для этого его надо поместить в uniqueness объект и отдать в этой обертке в другой поток. правильно? WH>Вот на это месте ты получишь по рукам от компилятора. WH>Ибо нельзя передать ссылку на mutable объект в uniqueness объект. WH>Ни через методы ни через конструктор. Вернуть mutable объект то же нельзя. WH>mutable объект можно только создать внутри uniqueness объекта и работать с ним то же только внутри этого объекта.
Что можно положить в uniqueness объект? Могу я сделать копию mutual объекта и положить его в uniqueness объект?
Видимо тип объекта при такого рода копировании должен измениться на uniqueness. Правильно?
Или надо создать сначала mutual объект внитри uniqueness и потом произвести копирование туда из другого mutual-а находящегося вне uniqueness
В общем как перетащить данные из mutual объекта в uniqueness, чтобы потом их можно было отправить в другой поток?
Здравствуйте, RailRoadMan, Вы писали:
RRM>Что можно положить в uniqueness объект?
Передать в метод uniqueness объекта можно только объекты pure и uniqueness типов.
RRM>Могу я сделать копию mutual объекта и положить его в uniqueness объект?
Нет.
Эта копия не пролезит через интерфейс uniqueness объекта.
RRM>Видимо тип объекта при такого рода копировании должен измениться на uniqueness. Правильно?
Типы меняться не умеют.
RRM>Или надо создать сначала mutual объект внитри uniqueness и потом произвести копирование туда из другого mutual-а находящегося вне uniqueness
Это можно. Но через зад автогеном.
Те тебе придется дергать методы uniqueness объекта чтобы привести состояние mutable объекта в нужное.
Как вариант можно попросить рантайм создать глубокий клон uniqueness объекта при условии что он не держит ссылок на uniqueness объекты.
RRM>В общем как перетащить данные из mutual объекта в uniqueness, чтобы потом их можно было отправить в другой поток?
Я думаю нужно просто изначально проектировать так чтобы это было не нужно.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
C>>мне больше STM/HTM тут нравится. WH>1)STM не работает. Вобще. WH>2)С HTM то же не все понятно. Скорей всего будет та же байда. WH>3)Проблем дедлоков и тп они то же не решат. Вспомни хотябы про дедлоки у MSSQL и "не могу сериализовать" у Oracle...
Да, дедлоков нет, зато возможны лайвлоки и оно всё равно не поможет для contended-ресурсов.
C>>До меня только что дошло, что я использую этот паттерн уже года четыре в С++ WH>А local_ptr может передавать владение так же как std::auto_ptr?
Нет, достаточно было простого scope-владения.
WH>А про барьеры памяти local_ptr не забывает?
Примитивы синхронизации их и так ставят.
V>>Угу, и нам нужно будет дёргать АЛУ для банального декремента семафора или проверки состояния события. Это ничем не отличается от существующего подхода. WH>А ты уверен что твой подход вобще имеет смысл делать? WH>Как насчет систем которые работают на примитивах синхронизации ориентированных на данные?
Я такого еще не видел. Даже если "лочишь" область отображения памяти видеокарты или звуковой карты, то ты имеешь дело лишь с внешним АПИ, а внутри — всё равно мьютекс и еще доп. поля по обслуживанию диапазонов. Для всяких ДМА — аналогично.
WH>Для них твой подход не эффективен.
Эффективен для обслуживания того самого внутреннего мьютекса. Ведь мы не только область данных "лочим", мы лочим доступ к некоторым регистрам девайса и котроллера памяти в т.ч. (для отображения памяти девайса на обычную), и это всё — по старинке внутри ОС, через мютексы и соглашения на их использования. Просто от тебя весь этот процесс скрыт.
Здравствуйте, vdimas, Вы писали:
V>Я такого еще не видел.
Переход к таким системам неизбежен.
Ибо защищать код идея бредовая.
Про то что взамен читай ветку еще раз.
V>Эффективен для обслуживания того самого внутреннего мьютекса.
Да нету никакого мъютекса.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
V>>Я такого еще не видел. WH>Переход к таким системам неизбежен. WH>Ибо защищать код идея бредовая. WH>Про то что взамен читай ветку еще раз.
Тогда еще раз:
ты управляешь внешним устройством, способным отображать некую область своей памяти на практически произвольную область из доступного диапазона ОП. Сама операция по такому отображению — многоходовая. Доступ конкретно к этому устройству и конкретно к этому диапазону памяти устройства должен быть как-то сериализован. Ну как тут можно защитить данные, а не код?
Практически весь ввод/вывод примерно так работает, именно задержки ввода/вывода являются основными задержками, и именно из-за этих ожиданий завершения операций так часто прыгает шедуллер по задачам.
V>>Эффективен для обслуживания того самого внутреннего мьютекса. WH>Да нету никакого мъютекса.
Пока что есть, на каждый хендл ввода-вывода внутри ОС. И еще один глобальный — на создание и удаление подобных хендлов из общего списка.
Здравствуйте, AndrewVK, Вы писали:
R>>Я обычно пользуюсь до смешного тупым паттерном:
AVK>Ну то есть свой аналог CDS?
R>>Проблема, что кода много, тут не проблема, т.к. схема реализации тупа как тумбочка.
AVK>Проблема в том, что производительность этой схемы не ахти. Лок на каждый чих.
Нет, нет, нет. Очередь тут просто в качестве примера. Я имел в виду, что делается безопасная "синхронизированная" обертка для какой-то функциональности. Гранулярность функций — "бизнес операция", а не примитивное действие, т.ч. производительность такая же, как если бы блокировки были "снаружи".
AVK>Для типовых современных многопоточных задач это обычно не страшно, но если нам именно вычисления многопоточные нужны для ускорения единой задачи на многоядерниках, может не прокатить.
По моему личному опыту такая схема покрывает более 90% случаев. Хотя, действительно, есть более изощренные ситуации, когда надо, например, блокировать сразу несколько произвольных объектов из множества; или когда блокировки должны быть вложенными.
Здравствуйте, AndrewVK, Вы писали:
AVK>но если нам именно вычисления многопоточные нужны для ускорения единой задачи на многоядерниках, может не прокатить.
А вот, кстати, по поводу вычислительных задач. Допустим возьмем следующую задачу. Итеративно считаем некую матрицу. Всегда храним 2 версии матрицы — одна текущая, значения в которой модифицируются; вторая — значения на предыдущей итерации, значения в этой матрице только читаются. После очередной итерации матрицы меняются местами. Для определенности допустим, что у нас есть 4 процессора/потока, каждый поток обсчитывает свой квадрант текущей матрицы, но при этом читает он значения из всей предыдущей матрицы.
Интересно, справится ли система типов WolfHound'а с такой задачей? Интересно было бы услышать комментарии.
Я тут вижу 2 интересных момента.
Во-первых, доступ к матрице (читай массиву) тут надо обеспечивать не на уровне всего массива, а на уровне определенных частей массива (квадрантов). В системах статического анализа массивы — это стандартная засада, обычно системы анализа трактуют массив как один объект, что в некоторых случаях очень не благоприятно сказывается на свойствах системы анализа. Вариант разбить массив на несколько объектов не очень хорошая, т.к. массив — это быстро; индексация в матрице на основе массива очень быстрая; работать на основе массивов просто принято в HPC сообществе; да и вообще не возможность решить именно поставленную задачу бьет по "мощности" и "гибкости" системы.
Второй момент, константность ("pureness") объекта определяется не статически, а динамически. Т.е. на одной итерации одна матрица pure, на другой — другая. Необходимость получения доступа на чтение к "предыдущей" матрице без всяких блокировок — критична. Копировать матрицы на каждой итерации тоже не вариант.
Вообще идея динамическо-статической типизации, по-моему, достаточно интересна. Что-то типа такого:
vector v = new mutable vector (100);
mutate(v);
declare_const(v);
read(v);
mutate(v); // - не скомпилируется
Т.е. можем менять тип объекта в ран-тайм, но в тоже время компилятор следит какой тип имеет объект в каждой точке программы. Соотв. трюки типа такого компилятор будет просто запрещать:
if (rand())
declare_const(v);
Типа того, как это есть для определений переменных в С/С++:
{
int x = 0; // можноswitch (y)
{
case 0:
{
int w = 0; // можно
}
break;
case 1:
int q = 0; // нельзяbreak;
}
}
Т.е. с одной стороны переменные можно создавать динамически, и кол-во созданных переменных зависит от ран-тайм состояния; но с другой стороны компилятор всё равно точно знает какая переменная доступна/жива в каждой конкретной точке программы. Соотв. аналогично трюки с "условным" созданием переменных запрещены.
Но правда похоже, что всё равно корректность не всех динамических изменений типа можно проверить во-время компиляции, и соотв. придется вставлять динамические проверки, кидающие исключения. Что, конечно, не очень круто.
Здравствуйте, remark, Вы писали:
R>А вот, кстати, по поводу вычислительных задач. Допустим возьмем следующую задачу. Итеративно считаем некую матрицу. Всегда храним 2 версии матрицы — одна текущая, значения в которой модифицируются; вторая — значения на предыдущей итерации, значения в этой матрице только читаются. После очередной итерации матрицы меняются местами. Для определенности допустим, что у нас есть 4 процессора/потока, каждый поток обсчитывает свой квадрант текущей матрицы, но при этом читает он значения из всей предыдущей матрицы.
Ты подходишь к решению как императивный программист.
Тут нужно уточнить как именно получаются новые значения.
Если они зависят исключительно от состояния предыдущего шага и индекса ячейки матрици то тут за нас вобще все рантайм в лучшем виде сделает:
В данном случае мы просто указали системе какими значениями заполнить матрицу на очередном шаге.
Видя независимость по данным ячеек матрици рантайм при жилании может запустить обсчет каждой ячейки в своем потоке.
Матрицу с шага N-2 просто уберет GC.
А при более вдумчивом анализе (довольно простом в данном случае) система просто переиспользует память от матрици на предыдущем шаге.
R>Второй момент, константность ("pureness") объекта определяется не статически, а динамически. Т.е. на одной итерации одна матрица pure, на другой — другая. Необходимость получения доступа на чтение к "предыдущей" матрице без всяких блокировок — критична. Копировать матрицы на каждой итерации тоже не вариант.
В принципе если ввести аналог С++'ного const для методов uniqueness типа то можно сделать преобразование uniqueness -> pure при условии что у pure варианта можно будет трогать только const методы.
Обратная трансформация невозможна.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, RailRoadMan, Вы писали:
RRM>>Что можно положить в uniqueness объект? WH>Передать в метод uniqueness объекта можно только объекты pure и uniqueness типов.
RRM>>Могу я сделать копию mutual объекта и положить его в uniqueness объект? WH>Нет. WH>Эта копия не пролезит через интерфейс uniqueness объекта.
RRM>>Видимо тип объекта при такого рода копировании должен измениться на uniqueness. Правильно? WH>Типы меняться не умеют.
RRM>>Или надо создать сначала mutual объект внитри uniqueness и потом произвести копирование туда из другого mutual-а находящегося вне uniqueness WH>Это можно. Но через зад автогеном. WH>Те тебе придется дергать методы uniqueness объекта чтобы привести состояние mutable объекта в нужное.
ты говоришь, что внутри uniqueness объекта куча mutable объектов могут создавать произвольные графы.
Это делается тоже через методы uniqueness объекта? тоже через зад получается...
RRM>>В общем как перетащить данные из mutual объекта в uniqueness, чтобы потом их можно было отправить в другой поток? WH>Я думаю нужно просто изначально проектировать так чтобы это было не нужно.
Я не согласен с такой точкой зрения. У меня есть две достаточно сложные модели (граф mutual объектов), каждая и ктр обрабатывается своим потоком. Мне необходимо передавать данные между этими моделями (не всю можель целиком). Как я могу это сделать?
Я должен сразу в модели для тех данных ктр я потом буду передавать в другую модель сразу использовать uniquness объекты?
ты говоришь, что внутри uniqueness объекта куча mutable объектов могут создавать произвольные графы. RRM>Это делается тоже через методы uniqueness объекта? тоже через зад получается...
Зачем демагогию то разводить?
Одно дело когда мы пытаемся ломиться в открытую дверь и совсем другое когда просто работаем накапливая данные в контейнере.
RRM>Я не согласен с такой точкой зрения. У меня есть две достаточно сложные модели (граф mutual объектов), каждая и ктр обрабатывается своим потоком.
Закатываем каждую из них в uniquness объект.
Общаемся через типизированные каналы (типа как в сингулярити).
Концы канала uniquness объекты. Соответственно проходить через каналы могут только uniquness и pure объекты.
RRM>Мне необходимо передавать данные между этими моделями (не всю можель целиком). Как я могу это сделать? RRM>Я должен сразу в модели для тех данных ктр я потом буду передавать в другую модель сразу использовать uniquness объекты?
Как вариант.
Но я думаю тебе таки стоит обратить внимание на pure объекты. Те твои модели будут смесью из mutable и где возможно pure объектов.
В очень многих ситуациях на них можно сделать гораздо более эффективные решения чем думают программисты с большим императивным опытом. Свежий пример.
Еще можно посмотреть на то как на операциях конкатенации, втавки, удаления и взятия подстроки неизменяемые rope'ы жестоко рвут классические строки. Причем и по памяти и по производительности.
Еще один хрестоматийный пример это неизменяемые сбалансированные деревья (RB, AVL, 2-3,...) когда у нас сотни тысяч словарей с разным содержанием занимают N*log(N) памяти. Например в компиляторах бывает очень полезно.
...
А к uniquness объектам нужно относится как к границам синхронизации. И использовать их соответственно. Даже не смотря на то что при однопоточной рабете с таким объектом мы имеем нулевой оверхед вплоть до инлайна методов.
Еще один вариант их использования это организация детерминированной финализации. Да у uniquness объектов есть полноценные деструкторы.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
R>>А вот, кстати, по поводу вычислительных задач. Допустим возьмем следующую задачу. Итеративно считаем некую матрицу. Всегда храним 2 версии матрицы — одна текущая, значения в которой модифицируются; вторая — значения на предыдущей итерации, значения в этой матрице только читаются. После очередной итерации матрицы меняются местами. Для определенности допустим, что у нас есть 4 процессора/потока, каждый поток обсчитывает свой квадрант текущей матрицы, но при этом читает он значения из всей предыдущей матрицы.
WH>Ты подходишь к решению как императивный программист. WH>Тут нужно уточнить как именно получаются новые значения. WH>Если они зависят исключительно от состояния предыдущего шага и индекса ячейки матрици то тут за нас вобще все рантайм в лучшем виде сделает: WH>
WH>В данном случае мы просто указали системе какими значениями заполнить матрицу на очередном шаге. WH>Видя независимость по данным ячеек матрици рантайм при жилании может запустить обсчет каждой ячейки в своем потоке. WH>Матрицу с шага N-2 просто уберет GC.
Я поражаюсь как у тебя всё всегда просто
А компилятор в действительности сможет это сделать приемлемо?
Ну хорошо, допустим даже, что сможет.
А теперь допустим, что матрица — это у нас изображение. Которое мы обсчитываем путем ray-tracing'а. Как компилятор побъет эту матрицу для независимой обработки потоками? Бить её квадрантами или широкими горизонтальными или вертикальными линиями очень не хорошо. Т.к. при ray-tracing'е объем работы сильно зависит от изображения, соотв., если мы будем бить широкими горизонтальными полосами, мы получим, что объем работы для обработки верхней полосы, где небо, будет в 100 раз меньше, чем объем работы для нижней полосы, где несколько детализированных моделей деревьев. Соотв. бить надо в зависимости от задачи, например очень узкими горизонтальными полосами, и каждому потоку достается множество полос, удовлетворяющее (stripe_index % thread_count == thread_index).
Теперь допустим, что компилятор не сможет это сделать автоматически и вернемся к исходному вопросу.
