Неизменным может быть боров памяти? - PullRequest
27 голосов
/ 27 марта 2010

Допустим, у нас есть класс с интенсивным использованием памяти, такой как Image, с цепочечными методами, такими как Resize() и ConvertTo().

Если этот класс является неизменяемым, не займет ли он огромное количество памяти, когда я начну делать такие вещи, как i.Resize(500, 800).Rotate(90).ConvertTo(Gif), по сравнению с изменяемым, который модифицирует себя? Как справиться с такой ситуацией на функциональном языке?

Ответы [ 6 ]

24 голосов
/ 27 марта 2010

Если этот класс неизменен, не займет ли он огромное количество памяти?

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

Как справиться с подобной ситуацией на функциональном языке?

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


Можете ли вы предоставить более подробную информацию?

Конечно. Я собираюсь взять исключительно простой пример: изображение в оттенках серого 1000x1000 с 8 битами на пиксель, повернутое на 180 градусов. Вот что мы знаем:

  • Для представления изображения в памяти требуется 1 МБ.

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

    for (i in columns) do
      for (j in first half of rows) do {
         pixel temp := a[i, j]; 
         a[i, j] := a[width-i, height-j]; 
         a[width-i, height-j] := tmp
      }
    
  • Если изображение неизменное , необходимо создать новое изображение целиком, и временно вам придется повесить старое изображение. Код выглядит примерно так:

    new_a = Image.tabulate (width, height) (\ x y -> a[width-x, height-y])
    

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

  • Пока идет вращение, нет необходимости иметь копии объектов других классов; временное пространство требуется только для поворачиваемого изображения.

N.B. Для других операций, таких как изменение масштаба или поворот (неквадратного) изображения на 90 градусов, вполне вероятно, что даже когда изображения являются изменяемыми, потребуется временная копия всего изображения, поскольку размеры изменяются. С другой стороны, преобразования цветового пространства и другие вычисления, которые выполняются попиксельно, могут быть выполнены с использованием мутации с очень небольшим временным пространством.

11 голосов
/ 27 марта 2010

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

Функциональные языки обычно обрабатывают операции такого рода, разбивая их на очень мелкие зерна. Ваш класс Image на самом деле не содержит логических битов данных изображения; скорее он использует указатели или ссылки на гораздо меньшие неизменяемые сегменты данных, которые содержат данные изображения. Когда необходимо выполнить операции с данными изображения, меньшие сегменты клонируются и видоизменяются, и возвращается новая копия изображения с обновленными ссылками - большинство из которых указывают на данные, которые не были скопированы или изменены и остались нетронутыми .

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

3 голосов
/ 27 марта 2010

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

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

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

class Image { 
  Bitmap source;
  FileFormat format;
  float newWidth, newHeight;
  float rotation;

  // Public constructor to load the image from a file
  public Image(string sourceFile) { 
    this.source = Bitmap.FromFile(sourceFile); 
    this.newWidth = this.source.Width;
    this.newHeight = this.source.Height;
  }

  // Private constructor used by the 'cloning' methods
  private Image(Bitmap s, float w, float h, float r, FileFormat fmt) {
    source = s; newWidth = w; newHeight = h; 
    rotation = r; format = fmt;
  }

  // Methods that can be used for creating modified clones of
  // the 'Image' value using method chaining - these methods only
  // store operations that we need to do later
  public Image Rotate(float r) {
    return new Image(source, newWidth, newHeight, rotation + r, format);
  }
  public Image Resize(float w, float h) {
    return new Image(source, w, h, rotation, format);
  }
  public Image ConvertTo(FileFormat fmt) {
    return new Image(source, newWidth, newHeight, rotation, fmt);
  }

  public void SaveFile(string f) { 
    // process all the operations here and save the image
  }
}

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

 var i = new Image("file.jpg");
 i.Resize(500, 800).Rotate(90).ConvertTo(Gif).SaveFile("fileNew.gif");

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

1 голос
/ 27 марта 2010

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

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

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

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

0 голосов
/ 30 марта 2010

Короткий, тангенциальный ответ: на языке FP, с которым я знаком (scala, erlang, clojure, F #), и для обычных структур данных: массивов, списков, векторов, кортежей, вам нужно понимать мелкие / глубокие копии и как реализовано:

, например

Scala, объект clone () и конструктор копирования

Scala AnyRef.clone выполняет поверхностную или глубокую копию?

Erlang: передача сообщений мелко скопированной структуры данных может взорвать процесс:

http://groups.google.com/group/erlang-programming/msg/bb39d1a147f72800

0 голосов
/ 27 марта 2010

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...