Производительность кода ADT, ориентированного на одно назначение, на современных процессорах

32

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

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

Я надеялся, что кто-нибудь сможет пролить свет на то, как это правда (или, если это не так?).

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

Джимми Хоффа
источник
2
это в основном полезно в многопоточности, когда читатель может атомарно получить снимок и быть уверенным в том, что он не будет видоизменяться во время его чтения
ratchet freak
@ratchetfreak Я понимаю, что с точки зрения программирования ваш код получает больше гарантий безопасности, но мое любопытство связано с контроллером памяти на процессоре и с тем, как это поведение имеет для него значение (или, если нет), как я слышал, претензии бандитизированы. о руке, полной времен, которые говорили, что она более эффективна для контроллера памяти, и я не знаю достаточно хорошо подробности низкого уровня, чтобы сказать, может ли это быть правдой или нет.
Джимми Хоффа
Даже если бы это было правдой, я бы не подумал, что меньшее количество модификаций памяти - лучший аргумент в пользу неизменности. В конце концов, память должна быть модифицирована, и за эти годы процессоры и менеджеры памяти стали достаточно хорошими.
Рейн Хенрикс
1
Я также хотел бы отметить, что эффективность использования памяти не обязательно должна зависеть от оптимизации компилятора при использовании неизменяемых структур. В этом примере let a = [1,2,3] in let b = 0:a in (a, b, (-1):c)разделении снижают требования к памяти, но зависит от определения (:)и , []а не компилятор. Я думаю? Не уверен насчет этого.

Ответы:

28

Процессор (в частности, контроллер памяти) может использовать тот факт, что память не видоизменяется

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

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

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


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

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

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

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

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

Видите ли, все ядра ничего не делают, пока данные копируются между глобальным и локальным кэшем . Это необходимо для обеспечения правильной синхронизации изменяемых данных (поточно-ориентированных). Если имеется 4 ядра, все 4 останавливаются и ждут, пока кешируются данные. Если их 8, все 8 останавливаются. Если их 16 ... ну, у вас есть 15 ядер, которые ничего не делают в ожидании того, что нужно сделать на одном из них.

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

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

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


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

комар
источник