Быстрое сокращение массива на порядки медленнее, чем небезопасное сокращение - PullRequest
Новая
       34

Быстрое сокращение массива на порядки медленнее, чем небезопасное сокращение

7 голосов
/ 19 июня 2020

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

struct Container {
  var data: Double
}

Затем создается массив этой структуры, потенциально большой: 

let containers = (0...<10_000_000).map { _ in 
  Container(data: .random(in: -10...10))
}

Затем a ( map) операция уменьшения применяется к массиву для извлечения значения, например: 

let sum = containers.reduce(0.0) { $0 + $1.data }

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

Но затем я сравнил производительность с этой небезопасной реализацией сокращения на массивах: 

extension Array {
  func unsafeReduce<Result>(
    _ initialResult: Result,
    _ nextPartialResult: (Result, Element) throws -> Result
  ) rethrows -> Result {
    try self.withUnsafeBufferPointer { buffer -> Result in
      try buffer.reduce(initialResult, nextPartialResult)
    }
  }
}

Я скомпилировал обе программы с полной оптимизацией -O -unchecked и также использовал Xcode профилировщик для временных программ, кажется, что небезопасное сокращение в 16 раз быстрее, чем его безопасный аналог: 200 мс против 4 с.

Мои вопросы:

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

Я использую Xcode 11.5 с Swift 5 на MacBook Air середины 2015 года.

Edit

Я перенес код на Python, и без использования Numpy для любых вычислений он все еще в 2 раза быстрее, чем операция Swift reduce. Впрочем, потребление памяти я не проверял.

...