Почему Swift использует синтаксис нижнего индекса в циклах for-in быстрее, чем прямой доступ к элементу? - PullRequest
Новая
       69

Почему Swift использует синтаксис нижнего индекса в циклах for-in быстрее, чем прямой доступ к элементу?

0 голосов
/ 30 июня 2018

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

В Swift можно получить доступ к элементам в массиве либо прямым способом, либо с помощью нижнего индекса, находясь в цикле for-in. Например, этот код: 

for i in 0..<size {
    sum += data[i]
}

Может быть написано: 

for element in data {
    sum += element
}

С size длиной data и data массивом суммируемых элементов.

Итак, я только что реализовал в Swift (код ниже) тот же алгоритм, что и в вопросе, который я упомянул в первом абзаце, и меня удивило то, что первый метод примерно в 5 раз быстрее, чем второй.

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

Вопрос

У меня вопрос, в чем разница между двумя for-in синтаксисами и почему быстрее использовать индекс?

вот деталь таймеров. Я использую Xcode 9.4.1 с Swift 4.1 на MacBook Air начала 2015 года с проектом Commande Line. 

// Using Direct Element Access
Elapsed Time: 8.506288427
Sum: 1051901000

против 

// Using Subscript
Elapsed Time: 1.483967902
Sum: 1070388000

Бонусный вопрос : почему выполнение в Swift в 100 раз медленнее, чем в C ++ (оба выполняются на одном Mac в проекте n Xcode)? Например, 100 000 повторений в C ++ занимают почти столько же времени, сколько 1000 повторений в Swift. Мое первое предположение состоит в том, что Swift является языком более высокого уровня, чем C ++, и что Swift, например, выполняет больше проверок безопасности.

Вот код Swift, который я использовал, я только изменил второй вложенный цикл: 

import Foundation
import GameplayKit

let size = 32_768
var data = [Int]()
var sum  = 0
var rand = GKRandomDistribution(lowestValue: 0, highestValue: 255)

for _ in 0..<size {
    data.append(rand.nextInt())
}

// data.sort()

let start = DispatchTime.now()

for _ in 0..<1_000 {
    // Only the following for-in loop changes
    for i in 0..<size {
        if data[i] <= 128 {
            sum += data[i]
        }
    }
}

let stop     = DispatchTime.now()
let nanoTime = stop.uptimeNanoseconds - start.uptimeNanoseconds
let elapsed  = Double(nanoTime) / 1_000_000_000

print("Elapsed Time: \(elapsed)")
print("Sum: \(sum)")

1 Ответ

0 голосов
/ 30 июня 2018

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

Чтобы продемонстрировать это, я обновил ваш код, добавив два метода, один с subscripting, а другой с использованием for-in. 

import Foundation
import GameplayKit

let size = 32_768
var data = [Int]()
var sum  = 0
var rand = GKRandomDistribution(lowestValue: 0, highestValue: 255)

for _ in 0..<size {
    data.append(rand.nextInt())
}

// data.sort()

func withSubscript() {
  let start = DispatchTime.now()

  for _ in 0..<1_000 {
      for i in 0..<size {
          if data[i] <= 128 {
              sum += data[i]
          }
      }
  }

  let stop    = DispatchTime.now()
  let elapsed = Double(stop.uptimeNanoseconds - start.uptimeNanoseconds) / 1_000_000_000

  print("With subscript:")
  print("- Elapsed Time: \(elapsed)")
  print("- Sum: \(sum)")
}

func withForIn() {
  let start = DispatchTime.now()

  for _ in 0..<1_000 {
      for element in data {
          if element <= 128 {
              sum += element
          }
      }
  }

  let stop    = DispatchTime.now()
  let elapsed = Double(stop.uptimeNanoseconds - start.uptimeNanoseconds) / 1_000_000_000

  print("With for-in:")
  print("- Elapsed Time: \(elapsed)")
  print("- Sum: \(sum)")
}

withSubscript()
withForIn()

Я сохранил этот код в файл с именем array-subscripting.swift.

Затем из командной строки мы можем запустить ее без каких-либо оптимизаций, например: 

$ swift array-subscripting.swift 
With subscript:
- Elapsed Time: 0.924554249
- Sum: 1057062000
With for-in:
- Elapsed Time: 5.796038213
- Sum: 2114124000

Как вы упомянули в посте, есть большая разница в производительности.

Эта разница довольно незначительна, когда код скомпилирован с оптимизацией: 

$ swiftc array-subscripting.swift -O
$ ./array-subscripting 
With subscript:
- Elapsed Time: 0.110622556
- Sum: 1054578000
With for-in:
- Elapsed Time: 0.11670454
- Sum: 2109156000

Как видите, оба решения намного быстрее, чем раньше, и очень похожи по времени выполнения.

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

Циклы

for-in, с другой стороны, создают неизменную копию каждого элемента из массива, что приводит к снижению производительности.

...