Стоит ли неизменность, когда нет параллелизма?

53

Кажется, что безопасность потоков всегда / часто упоминается как основное преимущество использования неизменяемых типов и особенно коллекций.

У меня есть ситуация, когда я хотел бы убедиться, что метод не будет изменять словарь строк (которые являются неизменными в C #). Я хотел бы ограничить вещи как можно больше.

Однако я не уверен, стоит ли добавлять зависимость в новый пакет (Microsoft Immutable Collections). Производительность тоже не большая проблема.

Поэтому я предполагаю, что мой вопрос заключается в том, настоятельно ли рекомендуется использовать неизменяемые коллекции, когда нет жестких требований к производительности и нет проблем с безопасностью потоков? Учтите, что семантика значений (как в моем примере) может или не может быть требованием.

логово
источник
1
Параллельная модификация не должна означать потоки. Просто посмотрите на точно названное имя, ConcurrentModificationExceptionкоторое обычно вызывается тем же потоком, мутирующим коллекцию в том же потоке, в теле foreachцикла над той же коллекцией.
1
Я имею в виду, что вы не ошибаетесь, но это отличается от того, что спрашивает ОП. Это исключение выдается, потому что изменение во время перечисления не допускается. Например, при использовании ConcurrentDictionary все равно будет эта ошибка.
edthethird
13
Может быть, вы должны также задать себе противоположный вопрос: когда стоит изменчивость?
Джорджио
2
В Java, если изменчивость влияет hashCode()или equals(Object)приводит к изменению результата, это может привести к ошибкам при использовании Collections(например, HashSetесли объект был сохранен в «корзине», а после изменения он должен перейти к другому).
SJuan76
2
@ DavorŽdralo Что касается абстракций языков высокого уровня, распространяемая неизменность довольно ручная. Это просто естественное продолжение очень распространенной абстракции (присутствующей даже в C) создания и молча отбрасывания «временных ценностей». Возможно, вы хотите сказать, что это неэффективный способ использования ЦП, но этот аргумент также имеет недостатки: изменчивость, но динамические языки часто работают хуже, чем неизменяемые, но статические языки, отчасти потому, что есть некоторые умные (но в конечном итоге довольно простые) хитрости для оптимизации программ по манипулированию неизменяемыми данными: линейные типы, вырубка лесов и т. д.

Ответы:

101

Неизменность упрощает объем информации, которую необходимо отслеживать мысленно при чтении кода позже . Для изменяемых переменных, и особенно изменчивых членов класса, очень трудно знать, в каком состоянии они будут находиться в конкретной строке, о которой вы читаете, без выполнения кода с помощью отладчика. Неизменные данные легко рассуждать - они всегда будут одинаковыми. Если вы хотите изменить его, вам нужно сделать новое значение.

Я бы честно предпочел сделать объекты неизменяемыми по умолчанию , а затем изменить их на изменяемые, где доказано, что они должны быть, означает ли это, что вам нужна производительность, или ваш алгоритм не имеет смысла для неизменности.

KChaloux
источник
23
+1 Параллелизм - это одновременная мутация, но о мутации, распространяющейся со временем, может быть так же трудно рассуждать
guillaume31
20
Чтобы расширить это: функцию, которая опирается на изменяемую переменную, можно рассматривать как принимающую дополнительный скрытый аргумент, который является текущим значением изменяемой переменной. Любая функция, которая изменяет изменяемую переменную, также может рассматриваться как создающая дополнительное возвращаемое значение, то есть новое значение изменяемого состояния. При просмотре фрагмента кода вы не представляете, зависит ли он от изменчивого состояния или изменяет его, поэтому вам нужно выяснить, а затем отслеживать эти изменения мысленно. Это также вводит связь между любыми двумя частями кода, которые имеют изменяемое состояние, и связь плохая.
Довал
29
@Mehrdad People также десятилетиями умудрялись запускать большие программы по сборке. Затем мы сделали пару десятилетий С.
Доваль
11
@ Mehrdad Копирование целых объектов не является хорошим вариантом, когда объекты большие. Я не понимаю, почему порядок, связанный с улучшением, имеет значение. Вы бы отказались от повышения производительности на 20% (примечание: произвольное число) просто потому, что это не было трехзначным улучшением? Неизменность - нормальное значение по умолчанию ; Вы можете отклониться от этого, но вам нужна причина.
Довал
9
@ Джорджио Скала заставил меня осознать, насколько редко нужно даже сделать значение изменчивым. Всякий раз, когда я использую этот язык, я делаю все a val, и только в очень, очень редких случаях я нахожу, что мне нужно что-то изменить в a var. Многие «переменные», которые я определяю в любом данном языке, просто содержат значение, которое хранит результат некоторых вычислений и не нуждается в обновлении.
КЧалу
22

Ваш код должен выражать ваше намерение. Если вы не хотите, чтобы объект был изменен после создания, сделайте невозможным его изменение.

Неизменность имеет несколько преимуществ:

  • Намерение оригинального автора выражено лучше.

    Как вы узнали бы, что в следующем коде изменение имени приведет к тому, что приложение сгенерирует исключение где-то позже?

    public class Product
    {
        public string Name { get; set; }
    
        ...
    }
    
  • Проще убедиться, что объект не появится в недопустимом состоянии.

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

    Например, объект действителен, если адрес не является null или GPS-координаты не являются null, но он недействителен, если указаны и адрес, и GPS-координаты. Можете ли вы представить, что, черт возьми, это можно проверить, если и адрес, и координаты GPS имеют установщик, или оба являются изменяемыми?

  • Параллелизм.

Кстати, в вашем случае вам не нужны никакие сторонние пакеты. .NET Framework уже включает в себя ReadOnlyDictionary<TKey, TValue>класс.

Арсений Мурзенко
источник
1
+1, особенно для «Вы должны контролировать это в конструкторе, и только там». ИМО это огромное преимущество.
Джорджио
10
Еще одно преимущество: копирование объекта бесплатно. Просто указатель.
Роберт Грант
1
@MainMa Спасибо за ваш ответ, но насколько я понимаю, ReadOnlyDictionary не дает никаких гарантий того, что кто-то другой не изменит базовый словарь (даже без параллелизма я могу захотеть сохранить ссылку на исходный словарь в объекте, к которому относится метод для последующего использования). ReadOnlyDictionary даже объявлен в странном пространстве имен: System.Collections.ObjectModel.
Ден
2
@Den: Это относится к одной из моих любимых мозолей: людям, которые считают «только для чтения» и «неизменяемыми» синонимами. Если объект инкапсулирован в оболочку, доступную только для чтения, и никакая другая ссылка не существует или сохраняется где-либо в юниверсе, то перенос объекта сделает его неизменным, и ссылка на оболочку может использоваться как сокращение для инкапсуляции состояния объект, содержащийся в нем. Однако нет механизма, с помощью которого код мог бы установить, так ли это на самом деле. Напротив, потому что оболочка скрывает тип обернутого объекта, оборачивая неизменный объект ...
суперкат
2
... сделает невозможным для кода узнать, можно ли считать полученную оболочку неизменной.
суперкат
13

Существует много однопоточных причин для использования неизменяемости. Например

Объект A содержит объект B.

Внешний код запрашивает ваш объект B, и вы его возвращаете.

Теперь у вас есть три возможных ситуации:

  1. B неизменен, нет проблем.
  2. B изменчив, вы делаете защитную копию и возвращаете ее. Производительность снизилась, но без риска.
  3. B изменчив, вы возвращаете это.

В третьем случае пользовательский код может не осознавать, что вы сделали, и может вносить изменения в объект, и, таким образом, изменять внутренние данные вашего объекта, когда вы не контролируете и не видите этого.

Тим Б
источник
9

Неизменность также может значительно упростить реализацию сборщиков мусора. Из вики GHC :

[...] Неизменность данных вынуждает нас создавать много временных данных, но также помогает быстро собирать этот мусор. Хитрость в том, что неизменные данные НИКОГДА не указывают на младшие значения. Действительно, младшие значения еще не существуют в то время, когда создается старое значение, поэтому на него нельзя указывать с нуля. И поскольку значения никогда не изменяются, на них также нельзя указывать позже. Это ключевое свойство неизменяемых данных.

Это значительно упрощает сборку мусора (GC). В любое время мы можем отсканировать последние созданные значения и освободить те, на которые не указаны из одного и того же набора (конечно, реальные корни иерархии реальных значений находятся в стеке). [...] Так что он ведет себя нелогично: чем больше процентов ваших ценностей, тем быстрее он работает. [...]

Петр Пудлак
источник
5

Разъясняю, на что очень хорошо подвел итог К.Чалу ...

В идеале у вас есть два типа полей и, следовательно, два типа кода, использующего их. Любые поля являются неизменяемыми, и код не должен учитывать изменчивость; или поля являются изменяемыми, и нам нужно написать код, который либо делает снимок ( int x = p.x), либо корректно обрабатывает такие изменения.

По моему опыту, большая часть кода находится между двумя, будучи оптимистичным кодом: он свободно ссылается на изменяемые данные, предполагая, что первый вызов p.xбудет иметь тот же результат, что и второй вызов. И в большинстве случаев это правда, кроме случаев, когда оказывается, что это больше не так. К сожалению.

Так что, действительно, переверните этот вопрос: каковы мои причины сделать это изменчивым ?

  • Сокращение памяти выделяется / освобождается?
  • Изменчивый от природы? (например, счетчик)
  • Сохраняет модификаторы, горизонтальный шум? (Const / конечный)
  • Делает код короче / проще? (init default, возможно перезаписать после)

Вы пишете защитный код? Неизменность спасет вас от копирования. Вы пишете оптимистичный код? Неизменность избавит вас от безумия этой странной, невозможной ошибки.

JVR
источник
3

Еще одним преимуществом неизменности является то, что это первый шаг в округлении этих неизменных объектов в пул. Затем вы можете управлять ими, чтобы не создавать несколько объектов, которые концептуально и семантически представляют одну и ту же вещь. Хорошим примером будет строка Java.

Это хорошо известное явление в лингвистике, когда несколько слов появляются много, могут появиться и в другом контексте. Таким образом, вместо создания нескольких Stringобъектов, вы можете использовать один неизменный. Но тогда вам нужно сохранить менеджера пула, чтобы заботиться об этих неизменных объектах.

Это сэкономит вам много памяти. Это интересная статья для чтения: http://en.wikipedia.org/wiki/Zipf%27s_law

InformedA
источник
1

В Java, C # и других подобных языках поля типа класса могут использоваться либо для идентификации объектов, либо для инкапсуляции значений или состояний в этих объектах, но языки не делают различий между такими использованиями. Предположим, у объекта класса Georgeесть поле типа char[] chars;. Это поле может инкапсулировать последовательность символов в одном из следующих:

  1. Массив, который никогда не будет изменен и не подвергнут никакому коду, который может его изменить, но на который могут существовать внешние ссылки.

  2. Массив, на который нет внешних ссылок, но который Джордж может свободно модифицировать.

  3. Массив, который принадлежит Джорджу, но для которого могут существовать внешние представления, которые должны были бы представлять текущее состояние Джорджа.

Кроме того, переменная может вместо инкапсуляции последовательности символов инкапсулировать представление в реальном времени в последовательность символов, принадлежащую некоторому другому объекту.

Если в charsнастоящее время инкапсулируется последовательность символов [ветер], а Джордж хочет charsинкапсулировать последовательность символов [палочка], Джордж может сделать несколько вещей:

A. Создайте новый массив, содержащий символы [палочка], и измените его, charsчтобы идентифицировать этот массив, а не старый.

Б. Определите каким-либо образом существующий массив символов, который всегда будет содержать символы [палочка], и измените его, charsчтобы идентифицировать этот массив, а не старый.

C. Измените второй символ массива, обозначенный charsкак a.

В случае 1, (A) и (B) являются безопасными способами достижения желаемого результата. В случае, когда (2), (A) и (C) безопасны, но (B) не будет [это не вызовет немедленных проблем, но, поскольку Джордж предположил бы, что он владеет массивом, он предположил бы, что он может изменить массив по желанию]. В случае (3) варианты (A) и (B) нарушают любые внешние взгляды, и, следовательно, только выбор (C) является правильным. Таким образом, знание того, как изменить последовательность символов, инкапсулированную в поле, требует знания, какой это семантический тип поля.

Если вместо использования поля типа char[], которое инкапсулирует потенциально изменяемую последовательность символов, в коде используется тип String, который инкапсулирует неизменяемую последовательность символов, все вышеперечисленные проблемы исчезнут. Все поля типа Stringинкапсулируют последовательность символов, используя разделяемый объект, который никогда не изменится. Следовательно, если поле типаStringинкапсулирует «ветер», единственный способ заставить его инкапсулировать «палочку» - заставить его идентифицировать другой объект - тот, который содержит «палочку». В тех случаях, когда код содержит единственную ссылку на объект, изменение объекта может быть более эффективным, чем создание нового, но всякий раз, когда класс является изменяемым, необходимо различать различные способы, которыми он может инкапсулировать значение. Лично я думаю, что Apps венгерский язык должен был использоваться для этого (я бы посчитал, что четыре применения char[]- это семантически отличные типы, хотя система типов считает их идентичными - в точности такая ситуация, когда Apps венгерский сияет), но так как Был не самый простой способ избежать таких неоднозначностей, это спроектировать неизменяемые типы, которые инкапсулируют значения только одним способом.

Supercat
источник
Это выглядит как разумный ответ, но его немного сложно прочитать и понять.
Ден
1

Здесь есть несколько хороших примеров, но я хотел бы перейти к некоторым личным, где неизменность помогла очень много. В моем случае я начал с разработки неизменяемой параллельной структуры данных, в основном с надеждой на то, что мы сможем уверенно выполнять код параллельно с перекрывающимися операциями чтения и записи и не беспокоиться о состоянии гонки. Был разговор, который Джон Кармак дал мне, вдохновил меня сделать это, где он говорил о такой идее. Это довольно простая структура и довольно тривиальная реализация:

введите описание изображения здесь

Конечно, с еще несколькими наворотами, такими как возможность удалять элементы в постоянное время и оставлять исправимые дыры позади, а блоки смещаются, если они становятся пустыми и потенциально освобождаются для данного неизменяемого экземпляра. Но в основном, чтобы изменить структуру, вы изменяете «временную» версию и атомарно фиксируете внесенные в нее изменения, чтобы получить новую неизменяемую копию, которая не касается старой, а новая версия создает только новые копии блоков, которые должны быть сделаны уникальными при мелком копировании и подсчете ссылок на другие.

Тем не менее, я не нашел это, чтополезно для многопоточности. В конце концов, все еще существует концептуальная проблема, когда, скажем, физическая система применяет физику одновременно, пока игрок пытается перемещать элементы в мире. С какой неизменной копией преобразованных данных вы идете, той, которую преобразовал игрок, или той, которую преобразовала физическая система? Так что я действительно не нашел хорошего и простого решения этой основной концептуальной проблемы, кроме наличия изменяемых структур данных, которые просто блокируют более разумным способом и не допускают перекрывающихся операций чтения и записи в одних и тех же разделах буфера, чтобы избежать зависания потоков. Это то, что Джон Кармак, возможно, выяснил, как решить в своих играх; по крайней мере, он говорит об этом так, будто почти видит решение, не открывая червячную машину. Я не дошел до него в этом отношении. Все, что я вижу, - это бесконечные вопросы дизайна, если я попытаюсь просто распараллелить все вокруг неизменяемых. Хотел бы я потратить день на то, чтобы поразмыслить над его мозгом, поскольку большинство моих усилий начиналось с тех идей, которые он выбрасывал.

Тем не менее, я нашел огромное значение этой неизменной структуры данных в других областях. Я даже использую его сейчас для хранения изображений, что действительно странно и требует, чтобы произвольный доступ требовал еще нескольких инструкций (сдвиг вправо и побитовый, andа также слой косвенного указателя), но я расскажу о преимуществах ниже.

Отменить систему

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

Таким образом, объем требуемого кода отмены был огромен, часто соперничая с объемом кода, реализующего систему, для которой система отмены должна была регистрировать изменения состояния. Опираясь на эту структуру данных, я смог свести систему отмены к следующему:

on user operation:
    copy entire application state to undo entry
    perform operation

on undo/redo:
    swap application state with undo entry

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

Теперь здесь все еще есть некоторые накладные расходы. В прошлый раз, когда я измерил, было около 10 килобайт, просто для поверхностного копирования всего состояния приложения без внесения в него каких-либо изменений (это не зависит от сложности сцены, поскольку сцена организована в иерархии, поэтому, если ничего не меняется под корнем, только корень мелко скопировано без необходимости спускаться в детей). Это далеко от 0 байтов, что необходимо для системы отмены, хранящей только дельты. Но при 10 килобайтах накладных расходов на отмену на операцию, это все равно только мегабайт на 100 пользовательских операций. Кроме того, я все еще мог бы в будущем, если понадобится, раздавить это дальше.

Исключение-безопасность

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

Слишком много людей часто просто используют RAII-совместимые ресурсы в C ++ и думают, что этого достаточно, чтобы быть безопасными для исключений. Часто это не так, так как функция обычно может вызывать побочные эффекты для состояний, выходящих за пределы области действия. Как правило, в этих случаях вам нужно начинать работать с защитой области видимости и сложной логикой отката. Эта структура данных сделала это таким образом, что мне часто не нужно беспокоиться об этом, поскольку функции не вызывают побочных эффектов. Они возвращают преобразованные неизменные копии состояния приложения вместо преобразования состояния приложения.

Неразрушающее редактирование

введите описание изображения здесь

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

Однако, например, при неразрушающем редактировании сетки многие операции часто хотят преобразовать только часть сетки. Одна операция может просто захотеть переместить некоторые вершины сюда. Другой может просто захотеть разделить некоторые полигоны там. В этом случае неизменяемая структура данных помогает избежать необходимости делать полную копию всей сетки только для того, чтобы вернуть новую версию сетки с небольшой измененной частью.

Минимизация побочных эффектов

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

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

Когда в вашей системе есть больше подобных функций, которые не вызывают побочных эффектов, это определенно облегчает рассуждение о его правильности, а также проверку его правильности.

Преимущества дешевых копий

Так или иначе, именно в этих областях я нашел наибольшее применение неизменяемых структур данных (или постоянных структур данных). Я также немного переусердствовал изначально и создал неизменное дерево, неизменный связанный список и неизменную хеш-таблицу, но со временем я редко находил такую ​​возможность. В основном я обнаружил, что наибольшее использование массивного неизменяемого массива-подобного контейнера показано на диаграмме выше.

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


источник
0

Уже есть много хороших ответов. Это просто дополнительная информация, относящаяся к .NET. Я копался в старых сообщениях в блоге .NET и нашел хороший итог с точки зрения разработчиков коллекций Microsoft Immutable Collections:

  1. Семантика снимков, позволяющая вам делиться своими коллекциями таким образом, чтобы получатель мог рассчитывать на то, что он никогда не изменится.

  2. Неявная защита потоков в многопоточных приложениях (для доступа к коллекциям не требуется блокировок).

  3. Каждый раз, когда у вас есть член класса, который принимает или возвращает тип коллекции, и вы хотите включить в контракт семантику только для чтения.

  4. Функциональное программирование дружественное.

  5. Разрешить изменение коллекции во время перечисления, при этом гарантируя, что исходная коллекция не изменится.

  6. Они реализуют те же интерфейсы IReadOnly *, с которыми уже работает ваш код, поэтому миграция проста.

Если кто-то вручает вам ReadOnlyCollection, IReadOnlyList или IEnumerable, единственная гарантия состоит в том, что вы не можете изменить данные - нет гарантии, что человек, который вручил вам коллекцию, не изменит ее. Тем не менее, вам часто нужна уверенность, что это не изменится. Эти типы не предлагают события, чтобы уведомить вас, когда их содержимое изменяется, и если они действительно изменяются, может ли это произойти в другом потоке, возможно, при перечислении его содержимого? Такое поведение может привести к повреждению данных и / или случайным исключениям в вашем приложении.

логово
источник