Влияет ли неизменность производительности в JavaScript?

88

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

Моя первоначальная реакция звучит так, как будто это плохо сказывается на производительности.

Но тогда библиотеки Immutable.js и Redux.js написаны умными людьми , чем я, и , кажется, есть сильное беспокойство по производительности, так что это заставляет меня задаться вопросом, если мое понимание мусора (и его влияние на производительность) является неправильным.

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

Каллум
источник
8
Они сильно обеспокоены производительностью, отчасти потому, что неизменность (иногда) влечет за собой снижение производительности, и они хотят максимально снизить эти затраты на производительность. Неизменность, сама по себе, имеет только преимущества в производительности в том смысле, что облегчает написание многопоточного кода.
Роберт Харви
8
По моему опыту, производительность важна только для двух сценариев - один, когда действие выполняется более 30 раз в секунду, и два, когда его влияние увеличивается с каждым выполнением (Windows XP однажды обнаружила ошибку, в которой время обновления Windows заняло время O(pow(n, 2))для каждого обновления в его истории .) Большинство других кодов - это немедленный ответ на событие; щелчок, запрос API или аналогичный, и, пока время выполнения постоянно, очистка любого количества объектов вряд ли имеет значение.
Katana314
4
Также учтите, что существуют эффективные реализации неизменяемых структур данных. Возможно, они не так эффективны, как изменчивые, но, вероятно, все же более эффективны, чем наивная реализация. См. Например, чисто функциональные структуры данных Крис Окасаки
Джорджо
1
@ Katana314: 30+ раз для меня все равно было бы недостаточно, чтобы оправдать беспокойство по поводу производительности. Я портировал небольшой эмулятор ЦП, который я записал в node.js, и узел выполнял виртуальный ЦП на частоте около 20 МГц (это 20 миллионов раз в секунду). Так что я бы беспокоился о производительности, только если бы делал что-то 1000+ раз в секунду (даже тогда я бы не стал беспокоиться, пока не выполню 1000000 операций в секунду, потому что я знаю, что могу с комфортом выполнить более 10 из них одновременно) ,
Slebetman
2
@RobertHarvey «Неизменность сама по себе имеет только преимущества в производительности в том смысле, что она облегчает написание многопоточного кода». Это не совсем так, неизменность позволяет распространять информацию без каких-либо реальных последствий. Что очень небезопасно в изменчивой среде. Это дает вам представление о том, что вы можете O(1)нарезать массив и O(log n)вставлять его в двоичное дерево, при этом все еще имея возможность свободно использовать старое дерево, и еще один пример, tailsкоторый берет все хвосты списка, tails [1, 2] = [[1, 2], [2], []]только занимает O(n)время и пространство, но находится O(n^2)в количестве элементов
точка с запятой

Ответы:

59

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

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

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

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

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

Мое личное правило для этой ситуации:

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

Для ситуаций между этими двумя крайностями, используйте свое суждение. Но YMMV.

Док Браун
источник
8
That will leave a lot more garbage than in your case.и что еще хуже, ваша среда выполнения, вероятно, не сможет обнаружить бессмысленное дублирование, и, таким образом (в отличие от неизменяемого неизменяемого объекта, который никто не использует), она даже не будет иметь права на сбор.
Джейкоб Райл
37

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

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

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

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

Карл Билефельдт
источник
8
«... тогда я показываю типичную императивную версию того же алгоритма, который создает столько же». Этот. Кроме того, люди, которые плохо знакомы с этим стилем, и особенно если они плохо знакомы с функциональным стилем в целом, могут первоначально произвести неоптимальные функциональные реализации.
Wberry
1
«не рекомендуется создавать переменные» Разве это не допустимо только для языков, в которых по умолчанию используется копирование при присваивании / неявном построении? В JavaScript переменная - это просто идентификатор; это не объект сам по себе. Он по-прежнему занимает место где-то, но это незначительно (особенно, поскольку большинство реализаций JavaScript, насколько мне известно, все еще используют стек для вызовов функций, то есть, если у вас нет много рекурсии, вы просто в конечном итоге будете использовать одно и то же пространство стека для большинства временные переменные). Неизменность не имеет никакого отношения к этому аспекту.
JAB
33

Поздно пришёл к этому Q & A с уже отличными ответами, но я хотел вмешаться, поскольку иностранец привык смотреть на вещи с низкоуровневой точки зрения битов и байтов в памяти.

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

Медленнее / Faster

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

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

Преобразование неизменяемых битов и байтов

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

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

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

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

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

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

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

Большие агрегаты

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

Чтобы избежать слишком сложной диаграммы, давайте представим, что этот простой блок памяти был каким-то дорогим (возможно, символы UTF-32 на невероятно ограниченном оборудовании).

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

В этом случае, если мы захотим заменить «HELP» на «KILL» и этот блок памяти будет неизменным, нам придется создать целый новый блок целиком, чтобы создать уникальный новый объект, даже если изменились только его части :

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

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

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

Одним из способов смягчения этой избыточной работы копирования является превращение этих блоков памяти в набор указателей (или ссылок) на символы, например, так:

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

Синий указывает на мелкие скопированные данные.

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

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

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

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

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

Разделите данные

Чтобы смягчить проблему, описанную выше, мы можем применить ту же базовую стратегию, но на более грубом уровне из 8 символов, например

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

Результат требует загрузки данных в 4 строки кэша (1 для 3 указателей и 3 для символов) для прохождения этой строки, что лишь на 1 меньше теоретического оптимума.

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

скорость

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

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

Хранение новых и старых данных

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

Пример: отменить систему

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

Интерфейсы высокого уровня

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

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

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

Структуры данных

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

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

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

Представление

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

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

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

ChrisF
источник
11

ImmutableJS на самом деле довольно эффективен. Если мы возьмем пример:

var x = {
    Foo: 1,
    Bar: { Baz: 2 }
    Qux: { AnotherVal: 3 }
}

Если вышеупомянутый объект сделан неизменным, тогда вы изменяете значение свойства 'Baz', что вы получите:

var y = x.setIn('/Bar/Baz', 3);
y !== x; // Different object instance
y.Bar !== x.Bar // As the Baz property was changed, the Bar object is a diff instance
y.Qux === y.Qux // Qux is the same object instance

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

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

Bringer128
источник
4

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

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

Собаки
источник
4

Чтобы добавить к этому (уже отлично ответил) вопрос:

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


Однако длинный ответ не совсем .

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

Для меня наибольшее увеличение производительности связано не с производительностью во время выполнения, а с разработчиками . Одна из первых вещей, которую я узнал, работая над приложениями Real World (tm), заключается в том, что изменчивость действительно опасна и сбивает с толку. Я потерял много часов, гоняясь за потоком (не типом параллелизма) выполнения, пытаясь выяснить, что вызывает неясную ошибку, когда она оказывается мутацией с другой стороны проклятого приложения!

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

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


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


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

Дэн кладовая
источник