Здравствуйте, deniok, Вы писали:
D>Собственно, меня-то больше всего интересует выигрыш/проигрыш по производительности по сравнению с параллельным программированием с использованием блокировок. Что удобства больше — это понятно, но если это будет работать медленнее аналогичной "однопоточной" программы (что иногда случается due to кривые ручки), то зачем огород городить?
Конкретных цифр не помню, но вроде там была речь о том, что на однопроцессорных системах и однопотоковых задачах есть солидный проигрыш, в 2 раза медленней чтоли, но при повышении показателей параллельности получается обратная картина + сложность реализации получается много меньше, чем реализации с блокировками.
AndreiF wrote: > Насколько я понимаю, проблема даже не в циклических ссылках. Просто, > если нам нужно склонировать объект, то придется клонировать и все > объекты, которые имеют ссылки на него (если в пределах транзакции может > произойти обращение и к ним тоже).
Да, но особенно это хорошо с циклами видно.
Здравствуйте, AndreiF, Вы писали:
AF>Насколько я понимаю, проблема даже не в циклических ссылках. Просто, если нам нужно склонировать объект, то придется клонировать и все объекты, которые имеют ссылки на него (если в пределах транзакции может произойти обращение и к ним тоже).
Тут рулят неизменяемые типы. Например, в том же компиляторе Немерле для пространст имен используется неизменяемы Map. При открытии пространства имен создается новая копия, но так как она инкрементальная, то памяти и времени особо не расходуется. Это позволяет получить офигительно чистый и тем не менее быстрый код.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Тут рулят неизменяемые типы. Например, в том же компиляторе Немерле для пространст имен используется неизменяемы Map. При открытии пространства имен создается новая копия, но так как она инкрементальная, то памяти и времени особо не расходуется. Это позволяет получить офигительно чистый и тем не менее быстрый код.
Увы, со сложными структурами данных это не сработает. Если ты хочешь создать измененную копию одного объекта, который входит в граф — придется за ним тянуть по цепочке все объекты, которые на него ссылаются.
AndreiF wrote:
> Насколько я понимаю, проблема даже не в циклических ссылках. Просто, > если нам нужно склонировать объект, то придется клонировать и все > объекты, которые имеют ссылки на него (если в пределах транзакции может > произойти обращение и к ним тоже).
Может я торможу и не понял проблемы, но может быть возможно сделать так:
понятие "ссылка" сделать контекстно-зависимым. В зависимости от того, какая транзакция в контексте, при разыменовании
ссылки выдаваться будет либо оригинальный объект, либо изменённый.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, Аноним, Вы писали:
А>Может я торможу и не понял проблемы, но может быть возможно сделать так: А>понятие "ссылка" сделать контекстно-зависимым. В зависимости от того, какая транзакция в контексте, при разыменовании А>ссылки выдаваться будет либо оригинальный объект, либо изменённый.
Тоже вариант, но это сильно увеличит стоимость разыменования ссылок.
Аноним wrote: > Может я торможу и не понял проблемы, но может быть возможно сделать так: > понятие "ссылка" сделать контекстно-зависимым. В зависимости от того, > какая транзакция в контексте, при разыменовании > ссылки выдаваться будет либо оригинальный объект, либо изменённый.
Я так и сделал.
Получается с достаточно большими накладными расходами — каждая ссылка
вместо обычных 32/64-бит начинает занимать около 16 байт (4 байта —
длина, 3*4 байта — small buffer optimization, с последним словом —
указателем на список с остальными ссылками).
Еще там по мелочам — для эффективной реализации нужно каждой транзакции
присваивать последовательный номер (требует минимум interlocked),
требуется использовать связный список (медленно!) для хранения ссылок
для видов. Ну и т.п.
AndreiF wrote:
> А>Может я торможу и не понял проблемы, но может быть возможно сделать так: > А>понятие "ссылка" сделать контекстно-зависимым. В зависимости от того, > какая транзакция в контексте, при разыменовании > А>ссылки выдаваться будет либо оригинальный объект, либо изменённый. > > Тоже вариант, но это сильно увеличит стоимость разыменования ссылок.
Из двух зол — меньшее.
Вроде, простая проверка — наличие объекта в HashSet изменённых объектов транзакции. Обычно должно получаться, что таких
объектов мало, а значит всё не так плохо.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, AndreiF, Вы писали:
VD>>Тут рулят неизменяемые типы. Например, в том же компиляторе Немерле для пространст имен используется неизменяемы Map. При открытии пространства имен создается новая копия, но так как она инкрементальная, то памяти и времени особо не расходуется. Это позволяет получить офигительно чистый и тем не менее быстрый код.
AF>Увы, со сложными структурами данных это не сработает. Если ты хочешь создать измененную копию одного объекта, который входит в граф — придется за ним тянуть по цепочке все объекты, которые на него ссылаются.
Для особо невнимательных повторяю — НЕИЗМЕНЯЕМЫЕ СТРУКТУРЫ ДАННЫХ.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Cyberax wrote:
>> Может я торможу и не понял проблемы, но может быть возможно сделать так: >> понятие "ссылка" сделать контекстно-зависимым. В зависимости от того, >> какая транзакция в контексте, при разыменовании >> ссылки выдаваться будет либо оригинальный объект, либо изменённый. > Я так и сделал. > > Получается с достаточно большими накладными расходами — каждая ссылка > вместо обычных 32/64-бит начинает занимать около 16 байт (4 байта — > длина, 3*4 байта — small buffer optimization, с последним словом — > указателем на список с остальными ссылками). > > Еще там по мелочам — для эффективной реализации нужно каждой транзакции > присваивать последовательный номер (требует минимум interlocked), > требуется использовать связный список (медленно!) для хранения ссылок > для видов. Ну и т.п.
А если наоборот — хранить множество изменённых внутри транзакции:
берём 32 бита ссылку, ищем в карте изменённых объектов транзакции — находим — возвращаем найденный, не находим —
возвращаем оригинальный.
Ссылка остаётся такого же размера и номера транзакциям не нужны, вроде.
Хотя типы придётся кастить из void* или подобного...
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, Аноним, Вы писали:
А>А если наоборот — хранить множество изменённых внутри транзакции: А>берём 32 бита ссылку, ищем в карте изменённых объектов транзакции — находим — возвращаем найденный, не находим — А>возвращаем оригинальный.
Если я правильно понимаю, то вы предлагаете некоторый аналог transaction log'а, который применяется в реализации STM для Haskell: http://research.microsoft.com/Users/simonpj/papers/stm/stm.pdf
Аноним wrote: > А если наоборот — хранить множество изменённых внутри транзакции: > берём 32 бита ссылку, ищем в карте изменённых объектов транзакции — > находим — возвращаем найденный, не находим — > возвращаем оригинальный.
Может быть очень дорого. Во-первых, lookup в таблице далеко не самое
дешовое занятие, во-вторых, часто будет нарушаться cache locality.
Хотя для многих случаев — действительно более подходящий вариант.
Здравствуйте, VladD2, Вы писали:
VD>Для особо невнимательных повторяю — НЕИЗМЕНЯЕМЫЕ СТРУКТУРЫ ДАННЫХ.
Вся прелесть неизменяемых данных в том, что их можно использовать в измененной копии, не так ли? Это еще называется "неразрушающее присваивание". Например, создать новый список, приклеив новую голову к старому, и далее работать с ним. Ты уж извини, что я тебе о таких азах напоминаю.
Ну так вот — этот подход прекрасно работает со списками, немного похуже с деревьями, а вот с графами всё совсем плохо.
Здравствуйте, Аноним, Вы писали:
А>Из двух зол — меньшее. А>Вроде, простая проверка — наличие объекта в HashSet изменённых объектов транзакции. Обычно должно получаться, что таких А>объектов мало, а значит всё не так плохо.
Ну я например не уверен, что это зло — меньшее Во всяком случае, далеко не для всех случаев.
Здравствуйте, Cyberax, Вы писали:
C>Теперь понятнее?
Немного понятнее, только мы о разном говорим.
Ты описываешь проблему, которая возникает в твоей собственной реализации механизма транзакций. Я рассматриваю STM как абстракцию, реализованную в библиотеке/языке/рантайме.
Если будет время, опиши, пожалуйста, задачу, а не реализацию. Хорошо бы в таком виде, чтобы решение можно было набросать за пару часов. Самому интересно, решается ли она с помощью хаскелловской реализации STM.
Здравствуйте, palm mute, Вы писали:
PM>Здравствуйте, Cyberax, Вы писали:
C>>Теперь понятнее? PM>Немного понятнее, только мы о разном говорим. PM>Ты описываешь проблему, которая возникает в твоей собственной реализации механизма транзакций. Я рассматриваю STM как абстракцию, реализованную в библиотеке/языке/рантайме.
PM>Если будет время, опиши, пожалуйста, задачу, а не реализацию. Хорошо бы в таком виде, чтобы решение можно было набросать за пару часов. Самому интересно, решается ли она с помощью хаскелловской реализации STM.
По-моему так задача ясна. Вот есть контейнер cycle_list, который пользователи-императивщики привыкли использовать в каком-то своём прикладном коде. Теперь они хотят засунуть его в STM. Но получается, что эффективного решения для разруливания транзакций над этим контейнером нет: пользователь меняет один элемент, а для обеспечения ACID неодходимо в каждой транзакции делать копию всего контейнера.
Cyberax'у — я правильно понял?
Здравствуйте, deniok, Вы писали:
D>По-моему так задача ясна. Вот есть контейнер cycle_list...
Это уже описание решения. Хотелось бы содержательную постановку, в терминах предметной области.
palm mute wrote: > C>Теперь понятнее? > Немного понятнее, только мы о разном говорим. > Ты описываешь проблему, которая возникает в /твоей собственной > реализации/ механизма транзакций. Я рассматриваю STM как абстракцию, > реализованную в библиотеке/языке/рантайме.
Какая разница? Стандартный рантайм магическими способностями не обладает.
> Если будет время, опиши, пожалуйста, задачу, а не реализацию. Хорошо бы > в таком виде, чтобы решение можно было набросать за пару часов. Самому > интересно, решается ли она с помощью хаскелловской реализации STM.
Задача простая:
1) Дан обычный линейный однонаправленый список.
2) Необходимо придумать механизм транзакций, чтобы можно было поменять
элемент из середины списка, не влияя на клиентов вне транзакции.
3) Этот механизм не должен приводить к копированию списка.
deniok wrote: > По-моему так задача ясна. Вот есть контейнер cycle_list, который > пользователи-императивщики привыкли использовать в каком-то своём > прикладном коде. Теперь они хотят засунуть его в STM. Но получается, что > эффективного решения для разруливания транзакций над этим контейнером > нет: пользователь меняет один элемент, а для обеспечения ACID неодходимо > в каждой транзакции делать копию всего контейнера. > Cyberax'у — я правильно понял?
Да, хотя можно взять и обычный императивный список — там придется
клонировать начало списка до измененного элемента.
Просто хуже всего этот эффект проявляется на циклических графах.
Во всяком случае, далеко не для всех случаев.
Вот есть контейнер cycle_list, который пользователи-императивщики привыкли использовать в каком-то своём прикладном коде. Теперь они хотят засунуть его в STM. Но получается, что эффективного решения для разруливания транзакций над этим контейнером нет: пользователь меняет один элемент, а для обеспечения ACID неодходимо в каждой транзакции делать копию всего контейнера.
