In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It functions as an alternative to lock-based synchronization, and is typically implemented in a lock-free way. A transaction in this context is a piece of code that executes a series of reads and writes to shared memory. These reads and writes logically occur at a single instant in time; intermediate states are not visible to other (successful) transactions. The idea of providing hardware support for transactions originated in 1993 by Maurice Herlihy and J. Eliot B. Moss. In 1995 Nir Shavit and Dan Touitou extended this idea to software-only transactional memory (STM). STM has recently been the focus of intense research and support for practical implementations is growing.
Здравствуйте, AndreiF, Вы писали:
AF>Здравствуйте, deniok, Вы писали:
D>>Какие мнения об идее/технологии?
AF>Очень правильная идея. Хотя в дополнение к ней нужны еще механизмы ограничений на данные, аналогично базам данных. Только помощнее
Что ты имеешь в виду под ограничениями? Права доступа? Целостность? Ещё что-то?
И каким образом это в STM может быть "встроено"?
ИМХО это задачи приложения.
Здравствуйте, Курилка, Вы писали:
К>Что ты имеешь в виду под ограничениями? Права доступа? Целостность? Ещё что-то?
Ограничения на значения целых переменных и длин строк, null/not null, допустимые диапазоны значений, допустимые отношения между объектами и так далее. Если ограничения нарушены — исключение и откат транзакции по умолчанию.
Здравствуйте, AndreiF, Вы писали:
AF>Здравствуйте, Курилка, Вы писали:
К>>Что ты имеешь в виду под ограничениями? Права доступа? Целостность? Ещё что-то?
AF>Ограничения на значения целых переменных и длин строк, null/not null, допустимые диапазоны значений, допустимые отношения между объектами и так далее. Если ограничения нарушены — исключение и откат транзакции по умолчанию.
Ты думаешь, что это всё должно быть выведено на "базовый" уровень?
Почему не использовать сам механизм транзакций и реализовать уже логику ограничений под приложение?
Здравствуйте, Курилка, Вы писали:
К>Ты думаешь, что это всё должно быть выведено на "базовый" уровень? К>Почему не использовать сам механизм транзакций и реализовать уже логику ограничений под приложение?
Думаю Такие задачи есть практически в каждом первом приложении, везде практически в неизменном виде. Это конечно не неотъемлемая часть механизма транзакций, но очень тесно с ним связано.
Здравствуйте, AndreiF, Вы писали:
AF>Здравствуйте, Курилка, Вы писали:
К>>Что ты имеешь в виду под ограничениями? Права доступа? Целостность? Ещё что-то?
AF>Ограничения на значения целых переменных и длин строк, null/not null, допустимые диапазоны значений, допустимые отношения между объектами и так далее. Если ограничения нарушены — исключение и откат транзакции по умолчанию.
Что-то мне кажется, что STM — штука более низкоуровневая. А это всё легко обеспечить на уровне библиотеки, её (STM) обёртывающей. Или имеется ввиду уже упаковка под .NET?
Здравствуйте, deniok, Вы писали:
D>Что-то мне кажется, что STM — штука более низкоуровневая. А это всё легко обеспечить на уровне библиотеки, её (STM) обёртывающей. Или имеется ввиду уже упаковка под .NET?
Упаковка чего именно? Библиотека не есть "упаковка"?
deniok wrote: > Какие мнения об идее/технологии?
Я использовал аналогичный подход в своей программе (на С++!) —
действительно, достаточно удобно. Очень напоминает программирование БД
Проблемы в этом подходе будут при работе с циклическими графами
объектов. Для чистых функциональных языков это не важно — там невозможно
создать цикл (все переменные иммутабельны), но вот для императивного
стиля — все плохо.
У себя я обошел эту проблему с помощью понятия "видов" (view) графа, но
у меня они использовались только для некоторых частных случаев изменений.
Здравствуйте, Cyberax, Вы писали:
C>Проблемы в этом подходе будут при работе с циклическими графами C>объектов. Для чистых функциональных языков это не важно — там невозможно C>создать цикл (все переменные иммутабельны), но вот для императивного C>стиля — все плохо.
Циклический граф на чистом функциональном ленивом языке создать элементарно:
-- cyclic list
oneTwoThrees = 1:2:3:oneTwoThrees
-- cyclic graphdata Graph a = Node a [Graph a]
x = Node "x" [y,z]
y = Node "y" [x,z]
z = Node "z" [x,y]
Теперь онтопик: какие проблемы с циклическими графами в транзакциях? Транзакция, насколько я понимаю, связана с атомарным обновлением нескольких значений с сохранением некоторого инварианта. Если граф конечный, то узлов/ребер также конечное число. Какое значение тут имеют циклы?
palm mute wrote: > Теперь онтопик: какие проблемы с циклическими графами в транзакциях? > Транзакция, насколько я понимаю, связана с атомарным обновлением > нескольких значений с сохранением некоторого инварианта. Если граф > конечный, то узлов/ребер также конечное число. Какое значение тут имеют > циклы?
Я имел в виду ненаправленный граф. Проблемы в том, что простое изменение
одного узла в цикле может потребовать хранить в транзакции все узлы, на
которые он ссылается.
PM>Циклический граф на чистом функциональном ленивом языке создать элементарно:
Пардон, ленивость я здесь по инерции приплел, она в данном случае роли не играет.
Здравствуйте, Cyberax, Вы писали:
C>Я имел в виду ненаправленный граф.
Ненаправленный граф делается так же легко.
C> Проблемы в том, что простое изменение C>одного узла в цикле может потребовать хранить в транзакции все узлы, на C>которые он ссылается. C>Я уже об этом писал: http://rsdn.ru/Forum/?mid=2209784
После беглого осмотра ссылки я не понял, как она связана с транзакциями. Насколько я понял, там ты демонстрировал сложности написания чисто-функционального ОО-кода на С++ (задача, несомненно, хитрая, но непревзойденный Олег Киселев ее решал, правда на Схеме, — http://okmij.org/ftp/Scheme/pure-oo-system.scm).
Транзакции не требуют клонирования циклических графов, потому мне по-прежнему непонятно, в чем проблема. Что значит "хранить в транзакции все узлы"? Может быть, приведешь пример (псевдо-)кода?
Здравствуйте, palm mute, Вы писали:
C>>Я имел в виду ненаправленный граф. PM>Ненаправленный граф делается так же легко.
Тормознул. А где в моем примере видно, что граф направленный?
palm mute wrote: > C> Проблемы в том, что простое изменение > C>одного узла в цикле может потребовать хранить в транзакции все узлы, на > C>которые он ссылается. > C>Я уже об этом писал: http://rsdn.ru/Forum/?mid=2209784
Cyberax wrote: > Теперь понятнее?
Да, еще добавлю — в случае чистых функциональных языков мы просто НЕ
МОЖЕМ поменять объект в середине цепи, так что такая ситуация просто
невозможна.
Здравствуйте, Cyberax, Вы писали:
C>Я имел в виду ненаправленный граф. Проблемы в том, что простое изменение C>одного узла в цикле может потребовать хранить в транзакции все узлы, на C>которые он ссылается.
AndreiF wrote: > C>Я имел в виду ненаправленный граф. Проблемы в том, что простое изменение > C>одного узла в цикле может потребовать хранить в транзакции все узлы, на > C>которые он ссылается. > То есть основная проблема — в накладных расходах?
Не знаю. Думать надо.
Проблема в том, что ВСЕ соединения в графе начинают зависеть от
контекста. Мне пришлось искусственно ограничить количество операций, так
как многие частные случаи у меня не были рассмотрены.
Насколько я понимаю, проблема даже не в циклических ссылках. Просто, если нам нужно склонировать объект, то придется клонировать и все объекты, которые имеют ссылки на него (если в пределах транзакции может произойти обращение и к ним тоже).
Здравствуйте, Курилка, Вы писали:
К>Здравствуйте, deniok, Вы писали:
D>>Что-то мне кажется, что STM — штука более низкоуровневая. А это всё легко обеспечить на уровне библиотеки, её (STM) обёртывающей. Или имеется ввиду уже упаковка под .NET?
К>Упаковка чего именно? Библиотека не есть "упаковка"?
Есть ведь разные реализации STM под разные платформы. Первая моя ссылка на твою же ссылку на Кембридж — так они там на сановских многопроцессорных станциях свою STM тестировали.
Я, возможно неправильно, понимаю STM, как механизм разруливания транзакций. То есть есть ядро STM, которое обеспечивает атомарность и изолированность операций (естественно за счёт некоторых накладных расходов по времени и памяти). Доступ к этому механизму — это atomically и retry. А есть всякие доп. сервисы, которые можно надстроить над базовым механизмом.
В отличие от баз данных, откуда пришла сама идея, запись в переменную при обращении к памяти может происходить гораздо чаще, чем запись в таблицу. Я боюсь, что всякие дополнительные проверки диапазонов и т.п., характерные для БД, могут создать узкое место, если они будут неотъемлемой частью STM.
Собственно, меня-то больше всего интересует выигрыш/проигрыш по производительности по сравнению с параллельным программированием с использованием блокировок. Что удобства больше — это понятно, но если это будет работать медленнее аналогичной "однопоточной" программы (что иногда случается due to кривые ручки), то зачем огород городить?
Здравствуйте, 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'у — я правильно понял?
Да, хотя можно взять и обычный императивный список — там придется
клонировать начало списка до измененного элемента.
Просто хуже всего этот эффект проявляется на циклических графах.
Здравствуйте, Cyberax, Вы писали:
>> Если будет время, опиши, пожалуйста, задачу, а не реализацию. Хорошо бы >> в таком виде, чтобы решение можно было набросать за пару часов. Самому >> интересно, решается ли она с помощью хаскелловской реализации STM. C>Задача простая: C>1) Дан обычный линейный однонаправленый список. C>2) Необходимо придумать механизм транзакций, чтобы можно было поменять C>элемент из середины списка, не влияя на клиентов вне транзакции. C>3) Этот механизм не должен приводить к копированию списка.
По моему скромному имху, "дан линейный однонаправленный список ..." — это не задача. Задача — это, например, перевести деньги со счета на счет.
Теперь по сути вопроса. Если дан список неизменяемых значений (целых чисел, например) — то задача некорректно поставлена, т.к. и без транзакций нельзя поменять элемент в середине списка, не скопировав элементы, ему предшествующие. Т.е., если в терминах хаскелловской реализации мы работаем с переменной типа TVar [Int] (по сути, это одна транзакционная ячейка, содержащая весь список), каждая транзакция будет вызывать копирование всего списка; правда, смысла в таких транзакциях немного. А вот если мы работаем со списком ячеек транзакционной памяти — [TVar Int] — изменение одной из ячеек в списке копирования других элементов не вызовет. Механизм придумывать не надо — он уже придуман и реализован, я уже приводил здесь ссылку на статью.
Здравствуйте, AndreiF, Вы писали:
AF>Здравствуйте, VladD2, Вы писали:
VD>>Для особо невнимательных повторяю — НЕИЗМЕНЯЕМЫЕ СТРУКТУРЫ ДАННЫХ.
AF>Вся прелесть неизменяемых данных в том, что их можно использовать в измененной копии, не так ли?
Не так. Вся прелесть их в том, что при грамотном проектировании можно порождать икрементальные не изменяемые копии.
AF> Это еще называется "неразрушающее присваивание". Например, создать новый список, приклеив новую голову к старому, и далее работать с ним. Ты уж извини, что я тебе о таких азах напоминаю.
Это ты уж извини, но ты напоминашь о них другим, а сам похоже путашся. Никаких изменений при создании одного списка из другого не происходит. Мы просто получаем две структуры данных. Просто часть одной из низ является другой. Копирование при этом не происходит. И все это именно из-за того, что струкры данных неименяемые.
AF>Ну так вот — этот подход прекрасно работает со списками, немного похуже с деревьями, а вот с графами всё совсем плохо.
Никаких проблем с деревьями (которые являются чатными случаеями графов) нет и быть не может. Циклические графы тоже можно соорудить, хотя решение будет посложнее. Циклические ссылки прийдется хранить отдельно.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2 wrote: > Никаких проблем с деревьями (которые являются чатными случаеями графов) > нет и быть не может. Циклические графы тоже можно соорудить, хотя > решение будет посложнее. Циклические ссылки прийдется хранить отдельно.
Не просто сложнее, а на Ph.d в общем случае тянет, как минимум.
Здравствуйте, VladD2, Вы писали:
VD>Не так. Вся прелесть их в том, что при грамотном проектировании можно порождать икрементальные не изменяемые копии.
Если тебе нужно получить дерево, у которого вот у этого конкретного узла на одну ветку меньше, то неважно, каким образом это достигается. Или изменением изначального дерева, или созданием копии старого — с точки зрения конечного результата это эквивалентно. Важно то, что в случае дерева создать копию одного этого узла и прицепить ее к старому дереву, как со списками, не получится. Придется копировать еще все вышестоящие узлы вверх по дереву. А это — дополнительные расходы. С графами все еще хуже.
Нужно еще пояснить, что я имею в виду?
Здравствуйте, AndreiF, Вы писали:
AF>Если тебе нужно получить дерево, у которого вот у этого конкретного узла на одну ветку меньше, то неважно, каким образом это достигается. Или изменением изначального дерева, или созданием копии старого — с точки зрения конечного результата это эквивалентно. Важно то, что в случае дерева создать копию одного этого узла и прицепить ее к старому дереву, как со списками, не получится. Придется копировать еще все вышестоящие узлы вверх по дереву. А это — дополнительные расходы. С графами все еще хуже. AF>Нужно еще пояснить, что я имею в виду?
Зачем? Твоя ошибка не в теоритических знаниях, а в их неверной интрерпретации.
Ты не учитывашь, что обычно в сбалансированном дереве очень немного уровней. А так как в "функциональном" дереве пересоздавать нужно только элементы лежащие по пути к вставляемому, то расходы получаются в пределах разумного. Да, это менее эффектино чем хэш-таблица (еще бы алгорит ведь гогарифмический), но более чем достаточно для большинства задач.
Вот могжешь поглядеть на реальную реализацию. Она используется в самом компиляторе для хранения "отркытых" (using-ами) пространств имен: http://nemerle.org/svn/nemerle/trunk/lib/tree.n
Эффекнивность более чем приемлемая.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
В любом случае это эффективнее чем копировать все и всегда.
Из других вариантов я вижу только создание аналога СУБД с версионной системой (аля Оракл/Интербэйс) в памяти. Это задача намного сложнее и менее эффективнее. Плюс без блогировок необойтись.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Ты не учитывашь, что обычно в сбалансированном дереве очень немного уровней. А так как в "функциональном" дереве пересоздавать нужно только элементы лежащие по пути к вставляемому, то расходы получаются в пределах разумного. Да, это менее эффектино чем хэш-таблица (еще бы алгорит ведь гогарифмический), но более чем достаточно для большинства задач.
Это в случае дерева всё относительно просто, и можно обойтись сравнительно небольшой потерей эффективности. Если взять граф, то в общем случае решение будет крайне неэффективным. Потому что там придется клонировать все элементы, которые прямо или косвенно имеют ссылку на копируемый узел графа. А эти элементы надо еще найти, что в случае однонаправленного графа тоже очень затратно.
Пощупал я реализацию SXM от майкрософта. Впечатления, в общем то, не самые радужные.
Мануал очень неполный и с ошибками. Особенно порадовал раздел Advanced (заголовок, и больше ничего )
Для всех типов, которые участвуют в транзакции, они создают прокси-тип с помощью эмита, которые и замещает его во всех операциях в транзакции. Прокси-тип наследуется от замещаемого типа и перехватывает все обращения к геттерам/сеттерам (точнее, там делается override). Перехватчики геттеров и сеттеров как раз и отвечают за всю магию Проблема с созданием измененной копии объекта решается имеено так, как предполагал Аноним — когда геттер возвращает ссылку на объект, то сначала происходит проверка "а не был ли этот объект изменен в транзакции", и если был, то вместо оригинального объекта подсовывается его копия.
Понятно, что это накладывает ряд ограничений на типы — доступ ко всем полям должен быть только через свойства, а все свойства должны быть виртуальными, и никак иначе. Создание объектов — только через специальную фабрику. (Было бы намного лучше и правильнее использовать IL rewriting, но автор этого почему-то не сделал) Если где-то по ошибке произойдет прямой доступ к полю вместо инкапсулирующего его свойства, то вместо измененной копии объекта код получит его старый вариант. Всё, приплыли
Например, вот такой код — это замаскированная ошибка:
[Atomic]
static void Main(string[] args)
{
XObjectFactory factory = new XObjectFactory(typeof(Test));
Test t1 = (Test)factory.Create(null, 1);
Test t2 = (Test)factory.Create(t1, 1);
XStart start = new XStart(delegate (object[] a) { Test.TestMethod(t1, t2); return null; });
XAction.ManagerType = Type.GetType(DEFAULT_MANAGER);
XAction.Run(start);
Console.WriteLine(t2.Next.Value);
}
public class Test : ICloneable
{
public Test()
{
}
public Test(Test next, int value)
{
_next = next;
_value = value;
}
private Test _next;
public virtual Test Next
{
get { return _next; }
set { _next = value; }
}
private int _value;
public virtual int Value
{
get { return _value; }
set { _value = value; }
}
public object Clone()
{
Test res = new Test(this.Next, this.Value);
return res;
}
public static void TestMethod(Test t1, Test t2)
{
t1.Value = 2;
Console.WriteLine(t2.Next._value); // <<<< ошибка здесь, вместо 2 мы получим 1
//Console.WriteLine(t2.Next.Value); // Правильно - только так!
}
}
Поскольку мало кто привык использовать само-инкапсуляцию, можно предположить, что такие ошибки будут происходить часто А отлавливать их — не очень тривиальная задача.
Текущая версия очень старая, и похоже, что работа по проекту больше не ведется.
VladD2 wrote: > C>Не просто сложнее, а на Ph.d в общем случае тянет, как минимум. > А в чем проблема?
Тут где-то пробегала ссылка на работу по функциональному представлению
графов. Я вот найти ее не могу.
> Сам граф представляем в виде функционального дерева на подобии этого: > http://nemerle.org/svn/nemerle/trunk/lib/tree.n > а циклические связи в виде коллекций внутри элементов.
Циклические связи нужно хранить в виде карты узел-связь глобально для графа.
> В любом случае это эффективнее чем копировать все и всегда.
Фига. В куче алгоритмов на графах заметно повышается сложность. Чтобы
это обойти приходится использовать другие способы (разреженные матрицы
инцидентности, разбиение графа на кластеры и т.п.) — все имеют
определенные trade-off'ы.
> Из других вариантов я вижу только создание аналога СУБД с версионной > системой (аля Оракл/Интербэйс) в памяти. Это задача намного сложнее и > менее эффективнее. Плюс без блогировок необойтись.
Я это сделал в своем проекте Для ограниченного ряда частных случаев,
но все же. Блокировки — это не самая большая проблема, гораздо хуже то,
что оверхед по памяти и скорости получается достаточно заметным.
VladD2 wrote: > Ты не учитывашь, что обычно в сбалансированном дереве очень немного > уровней. А так как в "функциональном" дереве пересоздавать нужно только > элементы лежащие по пути к вставляемому, то расходы получаются в > пределах разумного. Да, это менее эффектино чем хэш-таблица (еще бы > алгорит ведь гогарифмический), но более чем достаточно для большинства > задач.
А ты представь, что у тебя граф треугольников для поверхности в
1000х1000 точек
Здравствуйте, AndreiF, Вы писали:
AF>Это в случае дерева всё относительно просто, и можно обойтись сравнительно небольшой потерей эффективности.
Ну, что же... уже сдвиг. Недвано по твоим словам и деревья было невозможно поддерживать.
AF> Если взять граф, то в общем случае решение будет крайне неэффективным.
Согласен, с графом будет сложнее. Но для многих задач более чем приемлемо. Темболее, что сероезная работа с графами редко встречается в прикладном коде.
AF> Потому что там придется клонировать все элементы, которые прямо или косвенно имеют ссылку на копируемый узел графа.
Это не так. Но откровенно говоря мне не нинтересно обсуждение этого вопроса.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Cyberax, Вы писали:
C>А ты представь, что у тебя граф треугольников для поверхности в C>1000х1000 точек
Всегда можно найти неприемлемые условия для любого решения. Однако это не делает решение невозможным в других случаях. Данная тема интересна скорее в прикладных системах (вроде учета на предприятиях) где сложных мат-вычислений нет. И решения вполне себе приемлемы.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Cyberax, Вы писали:
C>VladD2 wrote: >> C>Не просто сложнее, а на Ph.d в общем случае тянет, как минимум. >> А в чем проблема? C>Тут где-то пробегала ссылка на работу по функциональному представлению C>графов. Я вот найти ее не могу.
z00n wrote: > C> Фига. В куче алгоритмов на графах заметно повышается сложность. > log n — обычно это терпимо, зато бесплатная персистентность.
Ты забываешь про константу, которая перед log n (C*log n) — в реальных
ситуациях она часто очень даже важна. Кроме того, для графов в тысячу
узлов "log n" уже будет минимум 10, то есть квадратичные алгоритмы будут
работать в 100 раз медленнее.
palm mute wrote: > C>Задача простая: > C>1) Дан обычный линейный однонаправленый список. > C>2) Необходимо придумать механизм транзакций, чтобы можно было поменять > C>элемент из середины списка, не влияя на клиентов вне транзакции. > C>3) Этот механизм не должен приводить к копированию списка. > По моему скромному имху, "дан линейный однонаправленный список ..." — > это не задача. Задача — это, например, перевести деньги со счета на счет.
Да без проблем. Куда грузовичком документацию по проекту подвозить?
Просто модельные примеры, где у одного объекта вычитается сумма, а к
другому добавляется — это просто детский лепет.
У меня была реальная задача версирования графа треугольников
(триангуляция большой карты высот) — я самую ее суть написал.
> Теперь по сути вопроса. Если дан список неизменяемых значений (целых > чисел, например) — то задача некорректно поставлена, т.к. и без > транзакций нельзя поменять элемент в середине списка, не скопировав > элементы, ему предшествующие.
А ты представь, что объекты — изменяемые. Так как с иммутабельными
объектами — все просто.
Здравствуйте, AndreiF, Вы писали:
AF> AF>На основании чего, хотелось бы знать?
На основании перехода на личности вместо аргументации. Надменные размышления о чужих знаниях при полном отсутсвии своих аргументов по другому и назвать то трудно. Не находишь?
AF>Кстати, подонковская терминология разве не запрещена на форуме?
Какая уж тут "падонковщина"? Сливали люди еще тогда когда их родимых в проекте еще не было.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>На основании перехода на личности вместо аргументации. Надменные размышления о чужих знаниях при полном отсутсвии своих аргументов по другому и назвать то трудно. Не находишь?
Не нахожу.
Тебе привели и аргументы, и формулировку задачи, никакого внятного ответа так и не было. Только надменные заявления, что тебе неинтересно это обсуждать, и угрозы забанить непонятно за что.
VD>Какая уж тут "падонковщина"?
Вот такая. Это выражение — типичный подонковский сленг.
Здравствуйте, Cyberax, Вы писали:
C>У меня была реальная задача версирования графа треугольников C>(триангуляция большой карты высот) — я самую ее суть написал.
>> Теперь по сути вопроса. Если дан список неизменяемых значений (целых >> чисел, например) — то задача некорректно поставлена, т.к. и без >> транзакций нельзя поменять элемент в середине списка, не скопировав >> элементы, ему предшествующие. C>А ты представь, что объекты — изменяемые. Так как с иммутабельными C>объектами — все просто.
фишка в том, что при каждом изменении может не потребоваться пересчитывать все эти данные благодаря lazy evaluation. почитай вышеупомняутый диссер Окасаки — он там развил целую теорию насчёт "амортизированной" производительности. насчёт графов я не в курсе, но скажем списки с добавлением в конец таким образом реализуются. фактически в памяти при этом сохраняется _алгоритм_ вычисления конечного списка/графа и изменение этого списка/графа, например добавление новых элементов в конец списка, не требует полного вычисления его предыдущего содержимого
Здравствуйте, deniok, Вы писали:
D>Какие мнения об идее/технологии?
Посмотрел статью по реализации на Haskell, по реализации на Java, и еще чего-то
Мои впечатления (возможно поверхностный, готов выслушать доводы)
Ограничения/недостатки:
1) Серьезное ограничение по сравнению с блокировками — невозможность синхронизировать ввод/вывод.
Транзацкии должны быть _перезапускаемы_ (автоматически или явно — это не важно) — этим все сказано.
2) Насколько я понял в STM используется оптимистичная синхронизация, ктр предполагает практическое отсутствие конфликтов между потоками, т.е. транзакиция выполнятеся в надежде, что синхронизация вообще не нужна, в момент commit-а это проверяется и если все нормально действия принимаются, если конфликт был транзакция перезапускается.
Чем длинее транзакция и чем больше потоков могут потенциально пересечься тем меньше вероятность что транзакия не будет перезапушена, т.е. под нагрузкой производительность будет падать. Вопрос насколько?
Вырожденный случай — полная блокировка программы несколькими транзакциями ктр постоянно прерывают друг друга. Т.е. фактически корретныя программа при увеличении нагрузки может повиснуть в своеобразном deadlock-е
Я не говорю, что это реальная проблема, но тем не менее неприятно что это вообще возможно.
Вообще мне вся идея STM очень напомнила Ethernet (тот ктр на хабах).
3) Сложность с транзакцоными переменными, ктр являются большимо сложными объектами.
Затраты на создании копии сложного объекта (как память на хранение копии, так и время на копирование)
Затраты на определения был ли реально этот объект изменен и нужно ли перрывать транзакцию
Причем чем длинее транзакция тем сильнее будут проявляться проблемы
4) В одной из статей нашел предложение использовать специальный manager для реализации различных политик сброса транзакций (в основном для борьбы с проблемой 2) ), использование приоритетов и вплоть до написани специализированного менеджера для каждого конкретного приложения (даже с вариантами блокировки транзацкии на время ). Ну на мой взгляд для общего механизма синхронизацити это многовато
5) В процессе выполнения транзакции может получиться inconsistent состояние транзакционных переменных ктр она видит. Понятно что в этом случае эта транзакция будет рано или поздно прекращена, но вот 100% уверен, что какой-нибудь косяк в каком-нибудь приложении вылезет (ну как с ружъем на стене в театре)
Достоинства:
1) Можно написать большими буквами. ОТСУТСВИЕ БЛОКИРОВОК и все проблемм с ними связянных
Ну и как выводы
1) STM наиболее применима на _коротких_ транзакциях (в Haskell реализации предполагают, что транзакция может быть выполнена целиком за один квант диспетчирования потока), в которых учатвуют достаточно _простые_ транзакционные переменны (числа, указатели), желательно с минимальным взаимодействием потоков
Вообще не удивительно, идея STM, насколько я понимаю, пришла из железа (варианты железной поддержки STM на прогопроцессорных машинах)
2) Можно использовать похожий подход ("по мотивам" так сказать) для каких-то более сложных, высокоуровненых случаев, но тут мне кажется придется изрядно поработать напильником. Т.е. STM в качестве исходной идеи
3) Блокировки в качетсве _универсального_ средства все же получше ИМХО
Здравствуйте, BulatZiganshin, Вы писали:
BZ>фактически в памяти при этом сохраняется _алгоритм_ вычисления конечного списка/графа и изменение этого списка/графа, например добавление новых элементов в конец списка, не требует полного вычисления его предыдущего содержимого
Примерно так работают стандартные реализации LInQ. Там это называется deffered query evaluation. Опять же, можно определенные параллели с каррингом провести.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, BulatZiganshin, Вы писали:
BZ>>фактически в памяти при этом сохраняется _алгоритм_ вычисления конечного списка/графа и изменение этого списка/графа, например добавление новых элементов в конец списка, не требует полного вычисления его предыдущего содержимого
AVK>Примерно так работают стандартные реализации LInQ. Там это называется deffered query evaluation.
в FP это называют lazy evaluation
AVK>Опять же, можно определенные параллели с каррингом провести.
фишка значит в следующем. когда у тебя значение функционального типа — оно в любом случае будет невычисленным, скажем хаскеловское (2+) — это функция, но никак не значение. и в любых FP языках это трактуется одинаково. разница в трактовке нуль-арных значений. в strict языках они ссразу вычисляются, в lazy — остаются представлены в памяти как формула пока их значение действительно не понадобится. вероятно, linq тоже строит нечто вроде lazy значения в памяти, и вычисляет его только по явному запросу (как и уэмулируется lazy evaluation во всех strict языках, от C++ с Boost до Ocaml)
BulatZiganshin wrote: > например добавление новых > элементов в конец списка, не требует полного вычисления его предыдущего > содержимого
Только вот в реальности это далеко не всегда получается. Точнее, почти
всегда не получается.
Здравствуйте, Cyberax, Вы писали:
C>BulatZiganshin wrote: >> например добавление новых >> элементов в конец списка, не требует полного вычисления его предыдущего >> содержимого C>Только вот в реальности это далеко не всегда получается. Точнее, почти C>всегда не получается.
я бы так ответил — это не получается при использовании императивного подхода к записи алгоритмов. при функциональном стиле вся работа с данными идёт "волной" — сначала мы целиком преобразовываем входное значение в промежуточное, затем в следующее и т.д. и на выходе у нас уже формула окончательного значения. а вычисляться оно будет по мере надобности при использовании
нечто подобное вы можете наблюдать в unix pipes — для меня это как раз пример функционального подхода к обработке данных, одна из причин сделавших систему столь популярной. и что-нибудь типа unzip|head не требует полной деархивации
