Использование постоянных структур данных в нефункциональных языках

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

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

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

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

Почему же тогда неизменность PDS рекламируется как нечто полезное для «безопасности потоков»? Есть ли реальные примеры, когда PDS помогают в синхронизации или решении проблем параллелизма? Или PDS - просто способ предоставить объекту без состояния интерфейс для поддержки функционального стиля программирования?

Постоянные / неизменные структуры данных не решают проблемы параллелизма сами по себе, но значительно облегчают их решение.

Рассмотрим поток T1, который передает набор S в другой поток T2. Если S является изменяемым, у T1 есть проблема: он теряет контроль над тем, что происходит с S. Поток T2 может изменить его, поэтому T1 вообще не может полагаться на содержимое S. И наоборот - T2 не может быть уверен, что T1 не изменяет S, пока T2 работает с ним.

Одним из решений является добавление какого-либо контракта к обмену данными T1 и T2, так что только один из потоков может изменять S. Это подвержено ошибкам и обременяет как дизайн, так и реализацию.

Другое решение состоит в том, что T1 или T2 клонируют структуру данных (или их обоих, если они не скоординированы). Однако, если S не является постоянным, это дорогостоящая операция O (n) .

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

Смотрите также: постоянная и неизменная структура данных .

Почему же тогда неизменность PDS рекламируется как нечто полезное для «безопасности потоков»? Есть ли реальные примеры, когда PDS помогают в синхронизации или решении проблем параллелизма?

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

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

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

Что касается примеров из нефункциональных языков, то в Java String.substring()используется то, что я бы назвал постоянной структурой данных. Строка представлена ​​массивом символов плюс начальные и конечные смещения диапазона массива, который фактически используется. Когда подстрока создается, новый объект повторно использует тот же массив символов, только с измененными начальными и конечными смещениями. Поскольку оно Stringявляется неизменным, оно (относительно substring()операции, а не других) является неизменяемой постоянной структурой данных.

Неизменность структур данных является частью, относящейся к безопасности потоков. Их постоянство (повторное использование существующих фрагментов при создании новой структуры) имеет отношение к эффективности при работе с такими коллекциями. Поскольку они являются неизменяемыми, такая операция, как добавление элемента, не изменяет существующую структуру, а возвращает новую с добавлением дополнительного элемента. Если бы каждый раз копировалась вся структура, начиная с пустой коллекции и добавляя 1000 элементов один за другим, чтобы в итоге получить 1000-элементную коллекцию, создавались бы временные объекты с 0 + 1 + 2 + ... + 999 = Всего 500000 элементов, что было бы огромной тратой. С постоянными структурами данных этого можно избежать, поскольку набор из 1 элемента повторно используется в 2-элементном, который повторно используется в 3-элементном и т. Д.,

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

Возьмите этот упрощенный пример C ++ (по общему признанию, не оптимизирован для простоты, чтобы не смущать себя перед любыми экспертами по обработке изображений):

// Inputs an image and outputs a new one with the specified size.
Image resized_image(const Image& src, int new_w, int new_h)
{
     Image dst(new_w, new_h);
     for (int y=0; y < new_h; ++y)
     {
         for (int x=0; x < new_w; ++x)
              dst[y][x] = src.sample(x / (float)new_w, y / (float)new_h);
     }
     return dst;
}

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

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

чистота

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

Дешевое Копирование Здоровенных Структур

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

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

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

неизменность

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

И хотя я считаю это наименее интересным из этих трех языков, таких как C ++, он, безусловно, может упростить тестирование, безопасность потоков и анализ нетривиальных объектов. Это может быть нагрузкой, чтобы работать с гарантией того, что объекту не может быть предоставлена ​​какая-либо уникальная комбинация состояний вне его конструктора, например, и что мы можем свободно передавать его, даже посредством ссылки / указателя, не полагаясь на константность и читаемость. только итераторы и дескрипторы и тому подобное, гарантируя (ну, по крайней мере, столько, сколько мы можем в пределах языка), что его оригинальное содержимое не будет видоизменено.

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

В заключение:

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

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

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