Здравствуйте, 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 не требует полной деархивации
). Ну на мой взгляд для общего механизма синхронизацити это многовато
