Очень мне это напоминает "с больной головы на здоровую". Помню как в C++ вводили inline чтобы помочь компилятору принять решение о встраивомости. До этого были register и т.п.

Так вот я о том что компиляторы могли бы на стадии анализа распознавать неизменяемые данные, первые шаги в этом направлении делаются ICС. Может просто подождать ?

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

M>Очень мне это напоминает "с больной головы на здоровую". Помню как в C++ вводили inline чтобы помочь компилятору принять решение о встраивомости. До этого были register и т.п.

M>Так вот я о том что компиляторы могли бы на стадии анализа распознавать неизменяемые данные, первые шаги в этом направлении делаются ICС. Может просто подождать ?

Имхо некорректная аналогия: понимание того, что mutability вещь чаще всего вредная, по сути нуждается в некоем принуждении (как в том же немерле принудительно надо добавлять mutable, насколько я помню). inline/register являются по сути premature optimization, а вот программу написанную со сплошными mutable переменными запросто в программу на immutable переменных переписать вряд ли получится, т.к. чаще всего даже алгоритмы меняются (начиная с цилков/рекусии в ИЯ/ФЯ). Правда чётких доказательств этого у меня нет, поэтому можно считать лишь субъективным мнением.

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

S>Здравствуйте, Gaperton, Вы писали:
G>>Ничего страшного мы тут не имеем.
G>>1) У тебя разных счетчиков ссылок столько, сколько разных элементов в структуре данных — коллизий будет немного.
S>Ну и что? Проблема не в коллизии. Проблема в том, что даже холостой lock/free — очень дорогая штука.
Ну, в реальности, положим, тебе надо не lock/free, а InterlockedIncrement сделать, а это, насколько я помню, одна ассемблерная инструкция.

G>>Реально — трогает разделяемые данные другой поток ровно один раз — при первой модификации стека. И все.
S>Это почему еще? Напоминаю, что из одного стека можно получмть сколько угодно стеков.
При первой модификации стека отдельным потоком. Надо на реальные кейсы смотреть. Приведи реальный пример использования, при котором получается сколько угодно. Мне кажется, на практике будет немного "стеков".

G>>И далеко не факт, что налетит на коллизию. Не слишком страшно, правда? Тем более, что в случае NUMA тебе надо по-любому очень аккуратно к распараллеливанию подходить, выделяя слабосвязные по данным фрагменты. Скажем, ты уверен, что общий хип будет вообще хорошо рабоать при NUMA?
S>Скажем, я уверен, что здесь можно использовать heap-per-thread. Тогда создание нового стека вообще не будет использовать никакую синхронизацию.
Конечно. В этом случае тебе правда весь стек откопировать придется сразу, что не хорошо. В С++ ты вообще можешь честный GC закрутить на элементах стека, кстати, полностью перекрыв аллокацию для объектов класса стек.

G>>2) От хотя бы однобитного счетчика ссылок вряд-ли кто откажется в данной ситуации — уж очень он здорово поправляет здоровье отца русской демократии — сильно разгружается GC.
S>Совершенно не представляю себе, чем бы здесь помог однобитный счетчик ссылок.
Это не так просто представить сразу — надо для начала представить себе как устроен этот стек. Однобитные счетчики ссылок позволят тебе отличать ситуацию, когда на объект наброшена одна ссылка, от ситуаций, когда ссылок много. В первом случае, который наиболее част для элементов однонаправленных списков, на которых и будет реализован твой стек, однобитные ссылки позволяют удалять длинные цепочки не привлекая GC. В реальности, "разных стеков" будет немного, в большинстве случаев ты получишь не сильно разветвленное дерево с длинными цепочками в ветвях. Эта техника уж более лет 10 применяется в лисп-машинах и других рантаймах ФЯ, очень старый фокус.

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

S>Здравствуйте, Gaperton, Вы писали:
G>>Это полная фигня.
S>Можно раскрыть это утверждение? Я не понял, к чему именно относилось "фигня" и что она означает.
К простоте реализации иммутабельного стека, сравнительно, например, с queue. Иммутабельный стек — полная фигня. Если ты не будешь отвечать подстрочником, на каждое предложение, а будешь отвечать на абзац целиком, который есть законченная мысль, то понять к чему это относится будет гораздо проще.

G>> Попробуй лучше сделать ImmutableQueue. И чтобы push и pop было за О(1). Хорошее управжнение для мозга, ну, и изобретешь заново Okasaki Queue — тоже дело. .
S>Я не ощущаю какой-то потребности в упражнениях для мозга.
Напрасно, это бы помогло тебе понять, что ImmutableStack полная фигня. Но не ощущаешь, так не ощущаешь, ради бога.

G>>На второй взгляд, такую же структуру на С++ так же легко, как и на первый. Эта структура делается однонаправленным списком. Хвост которого может указывать на начало или середину другого списка.
S>Это очевидно, потому что именно это описано в статье.
Это очевидно независимо от того, что именно написано в статье . Я ее, например, не читал. Не интересно.

G>>В узлах делаешь счетчик ссылок. И все.
S>Совершенно верно — "и всё". И теряем возможность создавать списки без блокировок.
G>>Можно делать хитрее — для экономии памяти применять однобитныесчетчики ссылок — техника оптимизации, которая применялась еще в древних лисп-машинах.
S>А можно мне рассказать про эти однобитные щетчики ссылок, и как они помогут выполнять детерминистическое освобождение памяти?
Почитай про них в сети. Я, видишь-ли, что-то тоже какой-то потребности рассказывать вдруг ощущать перестал.

G>>Как раз на С++ структура и не перестанет быть иммутабельной, если завести mutable счетчик ссылок. mutable как раз для таких ситуаций и предназначен, и никакого вреда кроме пользы от него не будет. Это, собственно, два.
S>Не надо путать божий дар с яичницей. mutable предназначен для обмана трудящихся масс, и вред от него очевиден. Процессор обмануть не удастся — для него нет ни mutable ни const; а есть жосткая реальность — необходимость синхронизации счетчика ссылок, который вы заботливо впендюрили.
InterlockedIncrement и InterlockedDecrement.
http://www.yandex.ru/yandsearch?text=InterlockedIncrement+%E8%ED%F1%F2%F0%F3%EA%F6%E8%FF&rpt=rad
Почитай про эту "жосткую реальность", реальность надо знать в лицо, даже если это всего-навсего одна инструкция x86. Нормальные пацаны пользуются этими примитивами, и ничего не "синхронизуют". Mutable же нужен для обмана компилятора.

S>Однобитный счетчик синхронизовывать не обязательно, но он всё равно требует GC.
Требует или GC, или полноценного счетчика ссылок. Это оптимизация. Ты про него уже прочитал, видимо, или раньше знал — эт хорошо. Значит, понимаешь, о чем я говорю.

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

S>Здравствуйте, Константин Л., Вы писали:
КЛ>>Не понял про вред. Или ты в свете immutability?
S>Да. Понимаешь, тут некоторые участники дискуссии путают отсутствие зависимостей, гарантированное отсутствием модификаций, со словом сonst. Если я на сарае напишу const, это не сделает лежащие в нем дрова неизменяемыми.

Синклер, я ничего не путаю. Не знаю как ты на сарае там консты пишешь, но когда Я ПИШУ const, то я уж забочусь о том, чтобы семантика операций была константной на самом деле.

S>Это то же самое, что полагать, что маскировка обращения к глобальной переменной за доступом к приватному нестатическому члену класса избавит от проблем. Типа раз мы в коде пишем this->setMap(...), то всё уже в порядке, хоть этот setMap по прежнему пишет в static CMap* g_map.

Ты просто не понимаешь, о чем я. Бывает.

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

M>Очень мне это напоминает "с больной головы на здоровую". Помню как в C++ вводили inline чтобы помочь компилятору принять решение о встраивомости. До этого были register и т.п.

M>Так вот я о том что компиляторы могли бы на стадии анализа распознавать неизменяемые данные, первые шаги в этом направлении делаются ICС. Может просто подождать ?

Immutable cтруктуры по-другому монтируются. И операции над ними по-другому реализуются. См., например, Окасаки.

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

M>Так вот я о том что компиляторы могли бы на стадии анализа распознавать неизменяемые данные, первые шаги в этом направлении делаются ICС. Может просто подождать ?
В случае среды Net — такое невозможно. Невозможно предсказать как будет использоваться тот или иной метод класса, учитывая то что в момент компиляции на уровне C# известен только код сборки, на уровне JIT — глобальный анализ невозможен поскольку компилируется только вызванная процедура и ее зависимости.

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

S>Не надо путать божий дар с яичницей. mutable предназначен для обмана трудящихся масс, и вред от него очевиден. Процессор обмануть не удастся — для него нет ни mutable ни const; а есть жосткая реальность — необходимость синхронизации счетчика ссылок, который вы заботливо впендюрили.

Кстати, не объяснишь мне, какой такой всем очевидный вред есть от mutable? И каким именно образом он у нас "для обмана трудящихся масс" предназначен?

ЗЫ: Я пока о трудящихся позабочусь. Итак, для обманутых трудящихся — зачем нужен mutable в С++. Обратите внимание на пример — класс "генератор случайных чисел". Абсолютно константный по своей семантике класс — по крайней мере если говорить о его основном методе get_rnd_value() или как вы его назовете. Тока у нея внутре будет mutable член, который хранит последнее число. Однако, класс по своей семантике — иммутабелен, или, как говорим мы, функциональщики — функция get_rnd_value() имеет "чистую" семантику.

Обратите внимание на пример номер 2. Мы делаем чистую функцию — которая вычисляет некоторое значение без побочных эффектов — не меняя состояние системы (т.е. ее возвращаемое значение целиком и полностью определяется значениями ее аргументов). Мы разумеется сразу помечаем ее как const. Но она однако тормозит иногда, при некоторых сочетаниях параметров, и мы решаем всунуть внутрь ея кэш. Который, разумеется, будет у нас mutable. При этом, семантика нашей функции останется "чистой", все в порядке.

Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет.

Здравствуйте, Константин Л., Вы писали:

КЛ>Здравствуйте, VladD2, Вы писали:

КЛ>[]

VD>>const же в С++ — это, как говорится, "почти ничто". Это атрибут переменной (о const на фунции вообще не говорим, так как это из другой оперы), который ко всему прочему элементарно обойти. Сделать какие либо оптимизации на основании знания о const-стантности или как-то другим образом использовать это явление скажем при многопоточном программировании нельзя.

КЛ>Вполне себе можно. Компайлер может оптимайзить "настоящие" константы.

Другое дело, что для immutable type'ов это намного проще

КЛ>[]

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

[]

G>Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет.

1. Interlocked не так дешев, как кажется.
2. mutexes не так дороги, как кажутся (e.g. CRITICAL_SECTION)
3. Sinclair говорит о том, что и без Interlocked можно легко обойтись

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

S>>Ну и что? Проблема не в коллизии. Проблема в том, что даже холостой lock/free — очень дорогая штука.
G>Ну, в реальности, положим, тебе надо не lock/free, а InterlockedIncrement сделать, а это, насколько я помню, одна ассемблерная инструкция.
Количество инструкций != количеству тактов.

G>При первой модификации стека отдельным потоком. Надо на реальные кейсы смотреть. Приведи реальный пример использования, при котором получается сколько угодно. Мне кажется, на практике будет немного "стеков".
Ты статью читал? Там же А* реализуется. Стеков будет столько, сколько выходов из клетки.

S>>Скажем, я уверен, что здесь можно использовать heap-per-thread. Тогда создание нового стека вообще не будет использовать никакую синхронизацию.
G>Конечно. В этом случае тебе правда весь стек откопировать придется сразу, что не хорошо.
Нет, не надо. Никакой проблемы ссылаться из одного хипа в другой нету. Возможно, будут особенности с cache locality, но их, скорее всего, можно побороть грамотным выравниванием.
G>В С++ ты вообще можешь честный GC закрутить на элементах стека, кстати, полностью перекрыв аллокацию для объектов класса стек.
Свой скепсис по поводу честного GC в С++ я уже высказывал.

S>>Совершенно не представляю себе, чем бы здесь помог однобитный счетчик ссылок.
G>Это не так просто представить сразу — надо для начала представить себе как устроен этот стек. Однобитные счетчики ссылок позволят тебе отличать ситуацию, когда на объект наброшена одна ссылка, от ситуаций, когда ссылок много. В первом случае, который наиболее част для элементов однонаправленных списков, на которых и будет реализован твой стек, однобитные ссылки позволяют удалять длинные цепочки не привлекая GC.
G>В реальности, "разных стеков" будет немного, в большинстве случаев ты получишь не сильно разветвленное дерево с длинными цепочками в ветвях. Эта техника уж более лет 10 применяется в лисп-машинах и других рантаймах ФЯ, очень старый фокус.
Это всего лишь оптимизация GC. Без GC этот счетчик не работает.

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

G>>В реальности, "разных стеков" будет немного, в большинстве случаев ты получишь не сильно разветвленное дерево с длинными цепочками в ветвях. Эта техника уж более лет 10 применяется в лисп-машинах и других рантаймах ФЯ, очень старый фокус.
S>Это всего лишь оптимизация GC. Без GC этот счетчик не работает.
Кстати, достаточно известная оптимизация. Называется (неудивительно) one-bit reference counting: http://citeseer.ist.psu.edu/130110.html

А вообще, RC как оптимизация GC вообще не помешал бы.

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

G>>Ничего страшного мы тут не имеем.
G>>1) У тебя разных счетчиков ссылок столько, сколько разных элементов в структуре данных — коллизий будет немного.
S>Ну и что? Проблема не в коллизии. Проблема в том, что даже холостой lock/free — очень дорогая штука.
Ну не совсем так — есть wait-free алгоритмы, позволяющие не блокировать читающие потоки во время мутации коллекций и т.п.

Здравствуйте, Gaperton, Вы писали:
G>Кстати, не объяснишь мне, какой такой всем очевидный вред есть от mutable?
G>И каким именно образом он у нас "для обмана трудящихся масс" предназначен?
Поясняю еще раз: преимущества в многоядерной среде есть не у константных, а у иммутабельных структур. У некоторых людей при взгляде на ключевое слово const может возникнуть иллюзия того, что соответствующий метод не нуждается в синхронизации. Ан нет — внутри него есть модификация mutable.

G>ЗЫ: Я пока о трудящихся позабочусь. Итак, для обманутых трудящихся — зачем нужен mutable в С++. Обратите внимание на пример — класс "генератор случайных чисел". Абсолютно константный по своей семантике класс — по крайней мере если говорить о его основном методе get_rnd_value() или как вы его назовете.
Никакой константной семантики у него нету.
G>Тока у нея внутре будет mutable член, который хранит последнее число. Однако, класс по своей семантике — иммутабелен, или, как говорим мы, функциональщики — функция get_rnd_value() имеет "чистую" семантику.
Откуда взялась чистая семантика в коде, который меняет глобальное состояние? Для чистой семантики вам, функциональщикам, придется передавать (seed, state) в каждый вызов.
Иначе вы будете обязаны выполнять синхронизацию внутри этого "чистого" метода. А то значения, случайно генерящиеся в параллельно исполняемых потоках, будут волшебным образом коррелировать. Если об этом знать, то можно сразу выделить по генератору на поток, и избежать race condition. Но ключевое слово const прячет он нас mutable природу этого генератора, и мы удивляемся, почему это у нас четыре ядра пашут не быстрее двух.

G>Обратите внимание на пример номер 2. Мы делаем чистую функцию — которая вычисляет некоторое значение без побочных эффектов — не меняя состояние системы (т.е. ее возвращаемое значение целиком и полностью определяется значениями ее аргументов). Мы разумеется сразу помечаем ее как const. Но она однако тормозит иногда, при некоторых сочетаниях параметров, и мы решаем всунуть внутрь ея кэш. Который, разумеется, будет у нас mutable. При этом, семантика нашей функции останется "чистой", все в порядке.
Хороший пример. С кэшем опять то же самое — скрытое состояние, которое нужно синхронизовывать. Вы выполняете запись в структуру, и либо там стоит InterlockedExchange, либо у вас начинаются проблемы с нарушением целостности.

G>Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет.
InterlockedIncrement все еще на пару порядков медленнее обычного инкремента. Кстати, не все примитивы синхронизации требуют режима ядра. Захват critical section традиционно строится на interlocked операциях в user mode.

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

G>>ЗЫ: Я пока о трудящихся позабочусь. Итак, для обманутых трудящихся — зачем нужен mutable в С++. Обратите внимание на пример — класс "генератор случайных чисел". Абсолютно константный по своей семантике класс — по крайней мере если говорить о его основном методе get_rnd_value() или как вы его назовете.
S>Никакой константной семантики у него нету.
G>>Тока у нея внутре будет mutable член, который хранит последнее число. Однако, класс по своей семантике — иммутабелен, или, как говорим мы, функциональщики — функция get_rnd_value() имеет "чистую" семантику.
S>Откуда взялась чистая семантика в коде, который меняет глобальное состояние? Для чистой семантики вам, функциональщикам, придется передавать (seed, state) в каждый вызов.
S>Иначе вы будете обязаны выполнять синхронизацию внутри этого "чистого" метода. А то значения, случайно генерящиеся в параллельно исполняемых потоках, будут волшебным образом коррелировать. Если об этом знать, то можно сразу выделить по генератору на поток, и избежать race condition. Но ключевое слово const прячет он нас mutable природу этого генератора, и мы удивляемся, почему это у нас четыре ядра пашут не быстрее двух.

хочется еще добавить, относительно данного конкретного примера, со своей точки зрения.. бог бы с ней со скоростью, но тут вылезет еще одна проблема, связанная с тем, что ф-ия get_rnd_value() изменяет внутреннее состояние нашего "генератора случайных чисел". Связана эта проблема с воспроизводимостью результатов. Т.е. в ряде наших, например, задач (исследования распределений статистик различных критериев методом монте-карло) бывает важно, что установливая один и то же seed для генератора на выходе мы получаем одинаковые результаты. А в случае разделения такого нашего генератора разными потоками воспроизводимость мы потерям, т.к. помимо seed на результаты влияет очередность обращений потоков к этому генератору -- а она в общем случае может изменяться в определенных пределах. Был бы он immutable -- не было бы этой проблемы (хотя immutable генератор псевдослучайных величин это само по себе достаточно загадочно)) ).

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

S>Здравствуйте, Gaperton, Вы писали:
G>>Кстати, не объяснишь мне, какой такой всем очевидный вред есть от mutable?
G>>И каким именно образом он у нас "для обмана трудящихся масс" предназначен?
S>Поясняю еще раз: преимущества в многоядерной среде есть не у константных, а у иммутабельных структур. У некоторых людей при взгляде на ключевое слово const может возникнуть иллюзия того, что соответствующий метод не нуждается в синхронизации. Ан нет — внутри него есть модификация mutable.

Поясняешь? У некоторых людей? Если метод нуждается в синхронизации, то она будет у него внутри. И он будет помечен комментарием как thredsafe. Снаружи ты синхронизацию все равно не навесишь, ее надо внутрь прятать. Это раз.

Два. Преимущество в многоядерной среде есть у lock-free datastructures, а не у иммутабельных структур.
http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms
Обрати внимание на список литературы внизу. Реализуются многие из них с применением инструкции CAS (http://en.wikipedia.org/wiki/Compare-and-swap).

Вот на это глянь.
http://en.wikipedia.org/wiki/Non-blocking_synchronization

Вот на это посмотри — как на самом деле нормальные пацаны делают нормальную очередь.
http://www.cs.brown.edu/people/mph/HerlihyLM03/main.pdf

Также, обрати внимание на транзакционную память (http://en.wikipedia.org/wiki/Software_transactional_memory) которая в процессорах уже следующего поколения будет поддержана аппаратно.

Вот это — то, что на самом деле в скором будущем обеспечит преимущество в многоядерной среде. А "иммутабельные" структуры — лоховство. У тебя на одной иммутабельной очереди, которая реально полезна для синхронизации и передачи данных в отличии от стека, которая называется Okasaki Queue и чуточку более сложна чем лоховской стек, и над которой ты думать отказался, оверхэд будет в разы по сравнению с нормальной лок-фри реализацией очереди, не говоря уже о худшем случае ( О(N) она в худшем случае дает, у нее только среднее O(1) ).

Так что хватит "обманывать трудящиеся массы".

G>>ЗЫ: Я пока о трудящихся позабочусь. Итак, для обманутых трудящихся — зачем нужен mutable в С++. Обратите внимание на пример — класс "генератор случайных чисел". Абсолютно константный по своей семантике класс — по крайней мере если говорить о его основном методе get_rnd_value() или как вы его назовете.
S>Никакой константной семантики у него нету.
Есть у нее "чистая" семантика. Поди людям в декларативном программировании объясни, что чистой семантики здесь нет . Увидишь, что будет.

G>>Тока у нея внутре будет mutable член, который хранит последнее число. Однако, класс по своей семантике — иммутабелен, или, как говорим мы, функциональщики — функция get_rnd_value() имеет "чистую" семантику.
S>Откуда взялась чистая семантика в коде, который меняет глобальное состояние? Для чистой семантики вам, функциональщикам, придется передавать (seed, state) в каждый вызов.
Ты нас, функциональщиков, функционалить не учи . Для чистой семантики нам, функциональщикам, достаточно не заботится о порядке вызовов, и иметь "прозрачность по ссылкам". Что в данном случае дает случайная семантика самой функции.

S>Иначе вы будете обязаны выполнять синхронизацию внутри этого "чистого" метода. А то значения, случайно генерящиеся в параллельно исполняемых потоках, будут волшебным образом коррелировать. Если об этом знать, то можно сразу выделить по генератору на поток, и избежать race condition. Но ключевое слово const прячет он нас mutable природу этого генератора, и мы удивляемся, почему это у нас четыре ядра пашут не быстрее двух.

Знаешь, я могу в TLS состояние этой штуки хранить, вообще-то. Так, к слову. И будут у меня четыре ядра пахать как надо, ага.

А ты, прежде чем говорить об "иммутабельных структурах", для начала почитал бы хотя бы про окасаки кью. Чтобы знать, о чем говоришь, и представлять, на какой именно performance penalty ты налетишь при их применении. Также, тебе, и автору этой вашей статьи, не помешало бы знать, что без "ленивых вычислений" реализуется эффективно очень небольшой класс "иммутабельных структур", которого особливо для работы не хватит. Упражнения для мозга полезны — почитай диссертацию Окасаки. А именно, ничего, кроме деревянного дерева да очереди (и то и другое с хорошим оверхэдом, да и то — требует специально заточенного аллокатора для хорошей работы, в котором еще надо будет те же самые проблемы синхронизации половить, о которых ты забыл) ты по большому счету не сделаешь.

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
На посмотри.

G>>Обратите внимание на пример номер 2. Мы делаем чистую функцию — которая вычисляет некоторое значение без побочных эффектов — не меняя состояние системы (т.е. ее возвращаемое значение целиком и полностью определяется значениями ее аргументов). Мы разумеется сразу помечаем ее как const. Но она однако тормозит иногда, при некоторых сочетаниях параметров, и мы решаем всунуть внутрь ея кэш. Который, разумеется, будет у нас mutable. При этом, семантика нашей функции останется "чистой", все в порядке.
S>Хороший пример. С кэшем опять то же самое — скрытое состояние, которое нужно синхронизовывать. Вы выполняете запись в структуру, и либо там стоит InterlockedExchange, либо у вас начинаются проблемы с нарушением целостности.

А если у меня внутри локфри-структура данных для кэша, что тогда?

G>>Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет.
S>InterlockedIncrement все еще на пару порядков медленнее обычного инкремента.
Рекомендую прекратить вводить "трудящиеся массы" в смущение. Это одна процессорная инструкция, которая в случае нескольких ядер на общем кэше (например, как в проце XBox360) не имеет никакого оверхэда. В случае, если кэшей несколько (их в реальности будет мало — разработчики процов стараются их объединять) то тогда надо будет слазить в соседний кэш. Это не более чем несколько накладных тактов. Фигня полная, учитывая, что современные процы либо суперскалярные, либо мультитредные (на фоне этой операции они преспокойно продолжат свою работу, либо текущего, либо очередного треда). Так что не надо пугать людей зазря.

Для "трудящихся масс" — делаем быстрый атомарный счетчик на x86.
http://www.codemaestro.com/reviews/review00000104.html

S>Кстати, не все примитивы синхронизации требуют режима ядра. Захват critical section традиционно строится на interlocked операциях в user mode.
Конечно, дык как мы выяснили можно и вообще без них .

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

I>хочется еще добавить, относительно данного конкретного примера, со своей точки зрения.. бог бы с ней со скоростью, но тут вылезет еще одна проблема, связанная с тем, что ф-ия get_rnd_value() изменяет внутреннее состояние нашего "генератора случайных чисел". Связана эта проблема с воспроизводимостью результатов. Т.е. в ряде наших, например, задач (исследования распределений статистик различных критериев методом монте-карло) бывает важно, что установливая один и то же seed для генератора на выходе мы получаем одинаковые результаты. А в случае разделения такого нашего генератора разными потоками воспроизводимость мы потерям, т.к. помимо seed на результаты влияет очередность обращений потоков к этому генератору -- а она в общем случае может изменяться в определенных пределах. Был бы он immutable -- не было бы этой проблемы (хотя immutable генератор псевдослучайных величин это само по себе достаточно загадочно)) ).

В случае его использования разными потоками надо хранить его состояние в Thread Local Storage. И все будет хорошо. "Чистый" он, "чистый", как слеза младенца. Несмотря на mutable внутри.

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

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

S>>>Ну и что? Проблема не в коллизии. Проблема в том, что даже холостой lock/free — очень дорогая штука.
G>>Ну, в реальности, положим, тебе надо не lock/free, а InterlockedIncrement сделать, а это, насколько я помню, одна ассемблерная инструкция.
S>Количество инструкций != количеству тактов.
Фундаментальная истина, не поспоришь, особенно для процов x86 . Может быть, ты знаешь, сколько конкретнонакладных тактов будет на инструкцию XADD, через которую делается этот инкремент, а? А я тебе скажу. Если ядра работают на общем кэше — то ноль. Если на нескольких раздельных — то плюс несколько тактов слазить в соседний кэш (не будет их там больше двух), на что ядро преспокойно наложит выполнение следующих операций — зависимостей по регистрам от этого XADD у нас нет. Или выполнение следующего аппаратного треда. Случай промаха в кэш мы не рассматриваем — я надеюсь, ты понимаешь почему? Потому что в этом случае эта операция займет ровно столько же времени, сколько и обычный инкремент, на фоне-то доступа во внешний DDR.

G>>При первой модификации стека отдельным потоком. Надо на реальные кейсы смотреть. Приведи реальный пример использования, при котором получается сколько угодно. Мне кажется, на практике будет немного "стеков".
S>Ты статью читал? Там же А* реализуется. Стеков будет столько, сколько выходов из клетки.
Ладно, уговорил. Почитаю статью.

S>>>Скажем, я уверен, что здесь можно использовать heap-per-thread. Тогда создание нового стека вообще не будет использовать никакую синхронизацию.
G>>Конечно. В этом случае тебе правда весь стек откопировать придется сразу, что не хорошо.
S>Нет, не надо. Никакой проблемы ссылаться из одного хипа в другой нету. Возможно, будут особенности с cache locality, но их, скорее всего, можно побороть грамотным выравниванием.
А управлять ссылками между хипами кто будет? Пушкин А.С.? И каким образом мы это будем делать, не мог бы ты пояснить? Уж не ссылки ли на хипы ты собрался считать (что совершенно то же, только вид сбоку)?

G>>В С++ ты вообще можешь честный GC закрутить на элементах стека, кстати, полностью перекрыв аллокацию для объектов класса стек.
S>Свой скепсис по поводу честного GC в С++ я уже высказывал.
Ну тогда придумай, как будешь считать ссылки между разными хипами.

S>>>Совершенно не представляю себе, чем бы здесь помог однобитный счетчик ссылок.
G>>Это не так просто представить сразу — надо для начала представить себе как устроен этот стек. Однобитные счетчики ссылок позволят тебе отличать ситуацию, когда на объект наброшена одна ссылка, от ситуаций, когда ссылок много. В первом случае, который наиболее част для элементов однонаправленных списков, на которых и будет реализован твой стек, однобитные ссылки позволяют удалять длинные цепочки не привлекая GC.
G>>В реальности, "разных стеков" будет немного, в большинстве случаев ты получишь не сильно разветвленное дерево с длинными цепочками в ветвях. Эта техника уж более лет 10 применяется в лисп-машинах и других рантаймах ФЯ, очень старый фокус.
S>Это всего лишь оптимизация GC. Без GC этот счетчик не работает.
Надо ли понимать этот твой ответ так, что ты понял, что такое однобитный счетчик ссылок? Разумеется это оптимизация. И не "всего лишь", а "хорошая" оптимизация. Я тебе это с самого начала и сказал.

2) От хотя бы однобитного счетчика ссылок вряд-ли кто откажется в данной ситуации — уж очень он здорово поправляет здоровье отца русской демократии — сильно разгружается GC.

По существу вопроса возражения есть?

Здравствуйте, Константин Л., Вы писали:

КЛ>Здравствуйте, Gaperton, Вы писали:

КЛ>[]

G>>Продолжать? Возьмем счетчик ссылок. Счетчик ссылок — строго говоря к данным объекта никак не относится. Вы сослались на объект, не изменив его — счетчик набросился. Убили ссылку — счетчик уменьшился. Сам объект, вернее его данные — никак не изменились. Вот, потому счетчик сцылок у нас будет mutable. И это правильно. Однако, Синклер поднял серьезный вопрос — а как же мы процессор то обманем? Такое можно и повторить. Воспользуемся специальной иво инструкцией, эта, процессора то есть. Interlocked Increment. Примитивы синхронизации, которые "медленные" (еще бы, в режим ядра сходить надо, они на шедулер опресистемы завязаны — не, обойдемся как-нить), мы применять не будем, нет.

КЛ>1. Interlocked не так дешев, как кажется.
Откуда ты знаешь, насколько именно дешев он мне кажется? Знаешь точно, насколько он дешев — скажи. Не знаешь — зачем пугаться самому и пугать других?

КЛ>2. mutexes не так дороги, как кажутся (e.g. CRITICAL_SECTION)
То же самое. Есть что конкретно сказать касательно производительности — давай. То что критическая секция дешевле мьютекса — я в курсе.

КЛ>3. Sinclair говорит о том, что и без Interlocked можно легко обойтись
Ну, и где именно он об этом говорит? Я вообще достаточно внимательно читаю те посты, на которые отвечаю.

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

N>>

N>>Immutable data structures are the way of the future in C#.

VD>Интересно, когда я говорил о том же саом, то тут меня чуть ли не закевали.

Гхм. Кажется, что-то такое припоминаю. Не здесь, случаем?

http://www.rsdn.ru/forum/message/2110922.1.aspx

Автор: VladD2
Дата: 15.09.06

Что тут не понятного? ФЯ по Гапертону (и тебе, в общем-то) это запрет на модификацию переменных. А это деградация функциональности и больше ничто. Этот запрет не даст никаких приемущество с точки зрения реализации алгоритмов. Никакие паттерн-матчинги от этого не зависят. Никакие функции высшего порядка тоже. Это просто запрет ради запрета. Он яко бы должен привести к гипотетическому упрощению программирования. Но по жизни, как говорится рулят, ковровые бомбордировки и танковые клинья и еще этот, как его? А, гриб Сарумяна. То есть рулят отладчики, IDE, визуальные дизайнеры и т.п.

http://www.rsdn.ru/forum/message/2106373.1.aspx

Автор: VladD2
Дата: 12.09.06

...
И вообще, большой вопрос что считать функциональным, а что императивным. Лично я считаю фунциональным стиль программирования в котором программист старается использовть вычисление выражений вместо выполнения инструкций. Гапертон же тут рядом заявил, что если в программе используется модификация переменных, то это уже "императивщина" (таки оскорбление какое-то ).

Так вот можно без проблем писать очень компактный и выразительный код во всю используя модификацию переменных. И программа от этого сложнее не или непонятнее не станет. Так что если определять ФП как это делает Гапертон, то ФП вообще мало чего дает.
...

http://www.rsdn.ru/forum/message/2125668.1.aspx

Автор: VladD2
Дата: 23.09.06

L> Это новый взгляд на проблему и именно с этой точки зрения я рассматриваю оспариваемый тезис. Собственно мое мнение можно читать как "объектно ориентированный взгляд на проблему имеет оверхед по сравнению с функциональным".

А я считаю это мнение заблуждением. Ну, что же поделаешь?

VD>>А каковы тогда критерии отнесения чего-то к ООП или императивному программированию (ИП)? Ведь ООП код может быть функциональным по сути, а может быть императивным. Как же быть?

L>Что такое функциональный ООП? Это использование ОО и функциональщины в одном флаконе? Если да, то нам не о чем спорить.

Тут г. Гапертон выразил мысль, что главное в ФП это "immutability". А используя ООП я могу сделать класс immutable или mutable. Отличный пример реализация класса строк в std::C++ и в Яве. Пользуясь определением Гапертона, я выбирая реализацию класса делаю выбор между императивным и функциональным дизайном. Так?