Часть 1

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

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

Если неизменность безопасна, учитывая определенные границы или предположения, я хочу знать, каковы границы «зоны безопасности». Некоторые примеры возможных границ:

• I / O
• Исключения / ошибки
• Взаимодействие с программами, написанными на других языках
• Взаимодействие с другими машинами (физическими, виртуальными или теоретическими)

Особая благодарность @JimmaHoffa за его комментарий, который начал этот вопрос!

Часть 2

Многопроцессорное программирование часто используется как метод оптимизации, чтобы заставить некоторый код работать быстрее. Когда быстрее использовать замки и неизменные объекты?

Учитывая ограничения, установленные в Законе Амдала , когда вы сможете достичь более высокой общей производительности (с учетом или без учета сборщика мусора) с неизменяемыми объектами по сравнению с блокировкой изменяемых объектов?

Резюме

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

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

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

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

Оказывается, что многие вещи читают объекты. IO делает, но сам IO имеет тенденцию плохо обрабатывать параллельное использование. Практически вся обработка выполняется, но другие объекты могут быть изменяемыми, или сама обработка может использовать состояние, не дружественное параллелизму. Копирование объекта является большой скрытой проблемой в некоторых языках, поскольку полная копия (почти) никогда не является атомарной операцией. Здесь вам помогут неизменные объекты.

Что касается производительности, это зависит от вашего приложения. Замки (обычно) тяжелые. Другие механизмы управления параллелизмом работают быстрее, но оказывают большое влияние на ваш дизайн. В целом , высококонкурентный дизайн, который использует неизменяемые объекты (и избегает их слабостей), будет работать лучше, чем высококонкурентный дизайн, который блокирует изменяемые объекты. Если ваша программа слегка параллельна, то это зависит и / или не имеет значения.

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

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

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

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

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

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

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    string result = string.Empty;
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result += s;
        else
            result += ", " + s;
    }
    return result;
} 

Этот пример неизменен, prima facie. Откуда я это знаю? Потому что stringобъект неизменен. Однако реализация не идеальна. Поскольку он resultявляется неизменным, каждый раз в цикле необходимо создавать новый строковый объект, заменяя исходный объект, на который resultуказывает. Это может отрицательно повлиять на скорость и оказать давление на сборщик мусора, поскольку он должен очистить все эти дополнительные строки.

Теперь, допустим, я делаю это:

public string ConcatenateWithCommas(ImmutableList<string> list)
{
    var result = new StringBuilder();
    bool isFirst = false;

    foreach (string s in list)
    {
        if (isFirst)
            result.Append(s);
        else
            result.Append(", " + s);
    }
    return result.ToString();
} 

Обратите внимание, что я заменил string resultизменяемый объект StringBuilder. Это намного быстрее, чем в первом примере, потому что новая строка не создается каждый раз в цикле. Вместо этого объект StringBuilder просто добавляет символы из каждой строки в коллекцию символов и выводит все в конце.

Является ли эта функция неизменной, даже если StringBuilder изменчив?

Да, это. Зачем? Поскольку каждый раз, когда вызывается эта функция, создается новый StringBuilder только для этого вызова. Итак, теперь у нас есть чистая функция, которая является поточно-ориентированной, но содержит изменяемые компоненты.

Но что, если я сделал это?

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;

    public string ConcatenateWithCommas(ImmutableList<string> list)
    {
        foreach (string s in list)
        {
            if (isFirst)
                result.Append(s);
            else
                result.Append(", " + s);
        }
        return result.ToString();
    } 
}

Этот метод потокобезопасен? Нет, это не так. Зачем? Потому что класс теперь держит состояние, от которого зависит мой метод. Теперь в методе присутствует условие гонки: один поток может измениться IsFirst, но другой поток может выполнить первый Append(), и в этом случае у меня теперь есть запятая в начале моей строки, которой не должно быть.

Почему я могу захотеть сделать это так? Ну, я мог бы хотеть, чтобы потоки накапливали строки в моем, resultнезависимо от порядка или в порядке поступления потоков. Может, это регистратор, кто знает?

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

public class Concatenate
{
    private StringBuilder result = new StringBuilder();
    bool isFirst = false;
    private static object locker = new object();

    public string AppendWithCommas(ImmutableList<string> list)
    {
        lock (locker)
        {
            foreach (string s in list)
            {
                if (isFirst)
                    result.Append(s);
                else
                    result.Append(", " + s);
            }
            return result.ToString();
        }
    } 
}

Теперь это снова потокобезопасно.

Единственный способ, которым мои неизменяемые методы могут быть не в состоянии быть потокобезопасными, - это если метод каким-то образом пропускает часть своей реализации. Может ли это случиться? Нет, если компилятор верен, а программа верна. Будут ли мне когда-нибудь нужны блокировки для таких методов? Нет.

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

Я не уверен, что понял ваши вопросы.

ИМХО ответ - да. Если все ваши объекты неизменны, то вам не нужны замки. Но если вам нужно сохранить состояние (например, вы реализуете базу данных или вам нужно агрегировать результаты из нескольких потоков), тогда вам нужно использовать изменчивость и, следовательно, также блокировки. Неизменность устраняет необходимость в блокировках, но обычно вы не можете позволить себе иметь полностью неизменные приложения.

Ответ на часть 2 - блокировки должны быть всегда медленнее, чем отсутствие блокировок.

Инкапсуляция связанного состояния в одной изменяемой ссылке на неизменяемый объект может сделать возможным выполнение многих видов изменения состояния без блокировки с использованием шаблона:

do
{
   oldState = someObject.State;
   newState = oldState.WithSomeChanges();
} while (Interlocked.CompareExchange(ref someObject.State, newState, oldState) != oldState;

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

Этот шаблон имеет преимущество в том, что поток, который становится отложенным, не может блокировать продвижение других потоков. Это имеет еще одно преимущество, заключающееся в том, что даже при сильном конфликте некоторые потоки всегда будут прогрессировать. Однако у него есть недостаток, заключающийся в том, что при наличии конкуренции множество потоков могут тратить много времени на выполнение работы, которую они в конечном итоге отбрасывают. Например, если все 30 потоков на отдельных процессорах одновременно пытаются изменить объект, один из них преуспеет с первой попытки, один - со второй, один - с третьей и т. Д., Так что каждый поток в среднем завершает выполнение около 15 попыток. обновить свои данные. Использование «консультативной» блокировки может значительно улучшить ситуацию: прежде чем поток попытается выполнить обновление, он должен проверить, установлен ли индикатор «конкуренции». Если так, он должен получить блокировку перед обновлением. Если поток делает несколько неудачных попыток обновления, он должен установить флаг конкуренции. Если поток, который пытается получить блокировку, обнаруживает, что никто больше не ждет, он должен сбросить флаг конфликта. Обратите внимание, что блокировка здесь не требуется для «правильности»; код будет работать правильно даже без него. Цель блокировки - минимизировать время, затрачиваемое кодом на операции, которые вряд ли будут успешными.

Вы начинаете с

Очевидно, что неизменность сводит к минимуму необходимость блокировок в многопроцессорном программировании.

Неправильно. Вы должны внимательно прочитать документацию для каждого класса, который вы используете. Например, const std :: string в C ++ не является потокобезопасным. Неизменяемые объекты могут иметь внутреннее состояние, которое изменяется при доступе к ним.

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

Теперь в примере кода кто-то написал с функцией с именем «ConcatenateWithCommas»: если бы ввод был изменяемым и вы использовали блокировку, что бы вы получили? Если кто-то еще попытается изменить список, пока вы пытаетесь объединить строки, блокировка может предотвратить сбой. Но вы все еще не знаете, объединяете ли вы строки до или после того, как другой поток их изменил. Так что ваш результат довольно бесполезен. У вас есть проблема, которая не связана с блокировкой и не может быть исправлена ​​с помощью блокировки. Но затем, если вы используете неизменяемые объекты, а другой поток заменяет весь объект новым, вы используете старый объект, а не новый объект, поэтому ваш результат бесполезен. Вы должны думать об этих проблемах на реальном функциональном уровне.