Swift Beta性能：排序数组

8 回答

• 425

  来自The Swift Programming Language：

  Sort函数Swift的标准库提供了一个名为sort的函数，它根据您提供的排序闭包的输出对已知类型的值数组进行排序 . 完成排序过程后，sort函数返回一个与旧数组相同类型和大小的新数组，其元素按正确的排序顺序排列 .

  sort 函数有两个声明 .

  允许您指定比较闭包的默认声明：

  func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]
  

  并且第二个声明只接受一个参数（数组）并且“硬编码以使用小于比较器” .

  func sort<T : Comparable>(array: T[]) -> T[]
  
  Example:
  sort( _arrayToSort_ ) { $0 > $1 }
  

  我在操场上测试了代码的修改版本并添加了闭包因此，我可以更密切地监视函数，并且我发现当n设置为1000时，闭包被调用大约11,000次 .

  let n = 1000
  let x = Int[](count: n, repeatedValue: 0)
  for i in 0..n {
      x[i] = random()
  }
  let y = sort(x) { $0 > $1 }
  

  它不是一个有效的功能，我建议使用更好的排序功能实现 .

  EDIT:

  我看了一下Quicksort维基百科页面并为它编写了一个Swift实现 . 这是我用过的完整程序（在操场上）

  import Foundation
  
  func quickSort(inout array: Int[], begin: Int, end: Int) {
      if (begin < end) {
          let p = partition(&array, begin, end)
          quickSort(&array, begin, p - 1)
          quickSort(&array, p + 1, end)
      }
  }
  
  func partition(inout array: Int[], left: Int, right: Int) -> Int {
      let numElements = right - left + 1
      let pivotIndex = left + numElements / 2
      let pivotValue = array[pivotIndex]
      swap(&array[pivotIndex], &array[right])
      var storeIndex = left
      for i in left..right {
          let a = 1 // <- Used to see how many comparisons are made
          if array[i] <= pivotValue {
              swap(&array[i], &array[storeIndex])
              storeIndex++
          }
      }
      swap(&array[storeIndex], &array[right]) // Move pivot to its final place
      return storeIndex
  }
  
  let n = 1000
  var x = Int[](count: n, repeatedValue: 0)
  for i in 0..n {
      x[i] = Int(arc4random())
  }
  
  quickSort(&x, 0, x.count - 1) // <- Does the sorting
  
  for i in 0..n {
      x[i] // <- Used by the playground to display the results
  }
  

  使用n = 1000，我发现了

  • quickSort（）被召唤约650次，

  • 约6000次互换，

  • 并且大约有10,000次比较

  似乎内置的排序方法是（或接近）快速排序，而且非常慢......

  回复于 2024-04-30T11:32:05+08:00
• 44

  tl; Dr Swift 1.0现在使用默认版本优化级别[-O]通过此基准测试与C一样快 .

  ---

  这是Swift Beta中的就地快速排序：

  func quicksort_swift(inout a:CInt[], start:Int, end:Int) {
      if (end - start < 2){
          return
      }
      var p = a[start + (end - start)/2]
      var l = start
      var r = end - 1
      while (l <= r){
          if (a[l] < p){
              l += 1
              continue
          }
          if (a[r] > p){
              r -= 1
              continue
          }
          var t = a[l]
          a[l] = a[r]
          a[r] = t
          l += 1
          r -= 1
      }
      quicksort_swift(&a, start, r + 1)
      quicksort_swift(&a, r + 1, end)
  }
  

  在C中也一样：

  void quicksort_c(int *a, int n) {
      if (n < 2)
          return;
      int p = a[n / 2];
      int *l = a;
      int *r = a + n - 1;
      while (l <= r) {
          if (*l < p) {
              l++;
              continue;
          }
          if (*r > p) {
              r--;
              continue;
          }
          int t = *l;
          *l++ = *r;
          *r-- = t;
      }
      quicksort_c(a, r - a + 1);
      quicksort_c(l, a + n - l);
  }
  

  两者都有效：

  var a_swift:CInt[] = [0,5,2,8,1234,-1,2]
  var a_c:CInt[] = [0,5,2,8,1234,-1,2]
  
  quicksort_swift(&a_swift, 0, a_swift.count)
  quicksort_c(&a_c, CInt(a_c.count))
  
  // [-1, 0, 2, 2, 5, 8, 1234]
  // [-1, 0, 2, 2, 5, 8, 1234]
  

  两者都在与编写的程序中调用 .

  var x_swift = CInt[](count: n, repeatedValue: 0)
  var x_c = CInt[](count: n, repeatedValue: 0)
  for var i = 0; i < n; ++i {
      x_swift[i] = CInt(random())
      x_c[i] = CInt(random())
  }
  
  let swift_start:UInt64 = mach_absolute_time();
  quicksort_swift(&x_swift, 0, x_swift.count)
  let swift_stop:UInt64 = mach_absolute_time();
  
  let c_start:UInt64 = mach_absolute_time();
  quicksort_c(&x_c, CInt(x_c.count))
  let c_stop:UInt64 = mach_absolute_time();
  

  这会将绝对时间转换为秒：

  static const uint64_t NANOS_PER_USEC = 1000ULL;
  static const uint64_t NANOS_PER_MSEC = 1000ULL * NANOS_PER_USEC;
  static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MSEC;
  
  mach_timebase_info_data_t timebase_info;
  
  uint64_t abs_to_nanos(uint64_t abs) {
      if ( timebase_info.denom == 0 ) {
          (void)mach_timebase_info(&timebase_info);
      }
      return abs * timebase_info.numer  / timebase_info.denom;
  }
  
  double abs_to_seconds(uint64_t abs) {
      return abs_to_nanos(abs) / (double)NANOS_PER_SEC;
  }
  

  以下是编译器优化级别的摘要：

  [-Onone] no optimizations, the default for debug.
  [-O]     perform optimizations, the default for release.
  [-Ofast] perform optimizations and disable runtime overflow checks and runtime type checks.
  

  使用 [-Onone] for n=10_000 的时间（以秒为单位）：

  Swift:            0.895296452
  C:                0.001223848
  

  这是Swift对 n=10_000 的内置排序（）：

  Swift_builtin:    0.77865783
  

  这是 [-O] for n=10_000 ：

  Swift:            0.045478346
  C:                0.000784666
  Swift_builtin:    0.032513488
  

  如您所见，Swift的性能提高了20倍 .

  根据mweathers' answer，设置 [-Ofast] 会产生真正的差异，导致 n=10_000 的这些时间：

  Swift:            0.000706745
  C:                0.000742374
  Swift_builtin:    0.000603576
  

  对于 n=1_000_000 ：

  Swift:            0.107111846
  C:                0.114957179
  Swift_sort:       0.092688548
  

  为了比较，这是 [-Onone] for n=1_000_000 ：

  Swift:            142.659763258
  C:                0.162065333
  Swift_sort:       114.095478272
  

  因此，在此开发阶段，没有优化的Swift在此基准测试中比C慢近1000倍 . 另一方面，两个编译器设置为[-Ofast] Swift实际上至少表现得相当好，如果不是比C略好 .

  有人指出[-Ofast]会改变语言的语义，使其可能不安全 . 这就是Apple在Xcode 5.0发行说明中所说的：

  LLVM中提供的新优化级别-Ofast可实现积极的优化 . -Ofast放松了一些保守的限制，主要用于浮点运算，对大多数代码都是安全的 . 它可以从编译器中获得显着的高性能胜利 .

  他们都提倡它 . 是否's wise or not I couldn' t说，但是从我所知道的，如果你确信在你的程序中没有整数或数组溢出，那么在一个版本中使用[-Ofast]似乎是合理的 . 如果您确实需要高性能和溢出检查/精确算术，那么现在就选择另一种语言 .

  BETA 3更新：

  n=10_000 与 [-O] ：

  Swift:            0.019697268
  C:                0.000718064
  Swift_sort:       0.002094721
  

  一般来说Swift有点快，看起来Swift的内置排序已经发生了很大变化 .

  FINAL UPDATE:

  [-Onone] ：

  Swift:   0.678056695
  C:       0.000973914
  

  [-O] ：

  Swift:   0.001158492
  C:       0.001192406
  

  [-Ounchecked] ：

  Swift:   0.000827764
  C:       0.001078914
  

  回复于 2024-04-30T11:32:05+08:00
• 5

  其他人提到的主要问题却没有得到充分说明， -O3 在Swift中根本没有做任何事情（从来没有），因此在编译时它实际上是非优化的（ -Onone ） .

  选项名称随着时间的推移而发生了变化，因此其他一些答案的构建选项都有过时的标志 . 正确的当前选项（Swift 2.2）是：

  -Onone // Debug - slow
  -O     // Optimised
  -O -whole-module-optimization //Optimised across files
  

  整个模块优化具有较慢的编译，但可以跨模块内的文件优化，即在每个框架内和实际应用程序代码内但不在它们之间 . 您应该将此用于任何性能关键）

  您还可以禁用安全检查以获得更高的速度，但所有断言和前置条件不仅被禁用，而且在它们正确的基础上进行优化 . 如果您遇到过断言，则意味着您处于未定义的行为 . 请谨慎使用，并且只有在确定速度提升对您有用时（通过测试） . 如果您确实发现它对某些代码很有 Value ，我建议将该代码分离到一个单独的框架中，并且只禁用该模块的安全检查 .

  回复于 2024-04-30T11:32:05+08:00
• 15

  从Xcode 7开始，您可以打开 Fast, Whole Module Optimization . 这应该会立即提高您的表现 .

  

  回复于 2024-04-30T11:32:05+08:00
• 8

  重新审视Swift Array性能：

  我编写了自己的基准，将Swift与C / Objective-C进行了比较 . 我的基准计算了素数 . 它使用先前素数的数组来寻找每个新候选者中的素因子，因此它非常快 . 但是，它确实可以读取数组，而且可以减少对数组的写入 .

  我最初针对Swift 1.2做了这个基准测试 . 我决定更新项目并针对Swift 2.0运行它 .

  该项目允许您在使用普通swift数组和使用数组语义的Swift不安全内存缓冲区之间进行选择 .

  对于C / Objective-C，您可以选择使用NSArrays或C malloc的数组 .

  测试结果似乎与最快，最小的代码优化（[-0s]）或最快，激进（[ - 0fast]）优化非常相似 .

  Swift 2.0的性能仍然很糟糕，代码优化关闭，而C / Objective-C性能只是适度慢 .

  最重要的是C malloc的基于数组的计算是最快的，是适度的余量

  使用最快，最小的代码优化时，使用不安全缓冲区的Swift比C malloc阵列长约1.19倍 - 1.20倍 . 通过快速，积极的优化，差异似乎略微减少（Swift比C长1.18倍到1.16倍更长）

  如果使用常规的Swift数组，与C的差异会略大一些 . （斯威夫特需要大约1.22到1.23 . ）

  常规的Swift数组比它们在Swift 1.2 / Xcode 6中的速度快97.97.7 . 它们的性能非常接近Swift不安全的基于缓冲区的数组，使用不安全的内存缓冲区似乎不值得再麻烦了，这很大 .

  BTW，Objective-C NSArray表现很糟糕 . 如果你打算在两种语言中使用本机容器对象，那么Swift的速度要快得多_97758 .

  您可以在SwiftPerformanceBenchmark上查看我在github上的项目

  它有一个简单的用户界面，可以很容易地收集统计数据 .

  有趣的是，Swift中的排序似乎比现在的C稍快，但是这个素数算法在Swift中仍然更快 .

  回复于 2024-04-30T11:32:05+08:00
• 4

  我决定看看这个很有趣，以下是我得到的时间：

  Swift 4.0.2           :   0.83s (0.74s with `-Ounchecked`)
  C++ (Apple LLVM 8.0.0):   0.74s
  

  斯威夫特

  // Swift 4.0 code
  import Foundation
  
  func doTest() -> Void {
      let arraySize = 10000000
      var randomNumbers = [UInt32]()
  
      for _ in 0..<arraySize {
          randomNumbers.append(arc4random_uniform(UInt32(arraySize)))
      }
  
      let start = Date()
      randomNumbers.sort()
      let end = Date()
  
      print(randomNumbers[0])
      print("Elapsed time: \(end.timeIntervalSince(start))")
  }
  
  doTest()
  

  结果：

  Swift 1.1

  xcrun swiftc --version
  Swift version 1.1 (swift-600.0.54.20)
  Target: x86_64-apple-darwin14.0.0
  
  xcrun swiftc -O SwiftSort.swift
  ./SwiftSort     
  Elapsed time: 1.02204304933548
  

  Swift 1.2

  xcrun swiftc --version
  Apple Swift version 1.2 (swiftlang-602.0.49.6 clang-602.0.49)
  Target: x86_64-apple-darwin14.3.0
  
  xcrun -sdk macosx swiftc -O SwiftSort.swift
  ./SwiftSort     
  Elapsed time: 0.738763988018036
  

  Swift 2.0

  xcrun swiftc --version
  Apple Swift version 2.0 (swiftlang-700.0.59 clang-700.0.72)
  Target: x86_64-apple-darwin15.0.0
  
  xcrun -sdk macosx swiftc -O SwiftSort.swift
  ./SwiftSort     
  Elapsed time: 0.767306983470917
  

  如果我用 -Ounchecked 编译，它似乎是相同的性能 .

  Swift 3.0

  xcrun swiftc --version
  Apple Swift version 3.0 (swiftlang-800.0.46.2 clang-800.0.38)
  Target: x86_64-apple-macosx10.9
  
  xcrun -sdk macosx swiftc -O SwiftSort.swift
  ./SwiftSort     
  Elapsed time: 0.939633965492249
  
  xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
  ./SwiftSort     
  Elapsed time: 0.866258025169373
  

  似乎从Swift 2.0到Swift 3.0的性能回归，我也第一次看到了 -O 和 -Ounchecked 之间的差异 .

  Swift 4.0

  xcrun swiftc --version
  Apple Swift version 4.0.2 (swiftlang-900.0.69.2 clang-900.0.38)
  Target: x86_64-apple-macosx10.9
  
  xcrun -sdk macosx swiftc -O SwiftSort.swift
  ./SwiftSort     
  Elapsed time: 0.834299981594086
  
  xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift
  ./SwiftSort     
  Elapsed time: 0.742045998573303
  

  Swift 4再次改善了性能，同时保持了 -O 和 -Ounchecked 之间的差距 . -O -whole-module-optimization 似乎没有什么区别 .

  C.

  #include <chrono>
  #include <iostream>
  #include <vector>
  #include <cstdint>
  #include <stdlib.h>
  
  using namespace std;
  using namespace std::chrono;
  
  int main(int argc, const char * argv[]) {
      const auto arraySize = 10000000;
      vector<uint32_t> randomNumbers;
  
      for (int i = 0; i < arraySize; ++i) {
          randomNumbers.emplace_back(arc4random_uniform(arraySize));
      }
  
      const auto start = high_resolution_clock::now();
      sort(begin(randomNumbers), end(randomNumbers));
      const auto end = high_resolution_clock::now();
  
      cout << randomNumbers[0] << "\n";
      cout << "Elapsed time: " << duration_cast<duration<double>>(end - start).count() << "\n";
  
      return 0;
  }
  

  结果：

  Apple Clang 6.0

  clang++ --version
  Apple LLVM version 6.0 (clang-600.0.54) (based on LLVM 3.5svn)
  Target: x86_64-apple-darwin14.0.0
  Thread model: posix
  
  clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
  ./CppSort     
  Elapsed time: 0.688969
  

  Apple Clang 6.1.0

  clang++ --version
  Apple LLVM version 6.1.0 (clang-602.0.49) (based on LLVM 3.6.0svn)
  Target: x86_64-apple-darwin14.3.0
  Thread model: posix
  
  clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
  ./CppSort     
  Elapsed time: 0.670652
  

  Apple Clang 7.0.0

  clang++ --version
  Apple LLVM version 7.0.0 (clang-700.0.72)
  Target: x86_64-apple-darwin15.0.0
  Thread model: posix
  
  clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
  ./CppSort     
  Elapsed time: 0.690152
  

  Apple Clang 8.0.0

  clang++ --version
  Apple LLVM version 8.0.0 (clang-800.0.38)
  Target: x86_64-apple-darwin15.6.0
  Thread model: posix
  
  clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
  ./CppSort     
  Elapsed time: 0.68253
  

  Apple Clang 9.0.0

  clang++ --version
  Apple LLVM version 9.0.0 (clang-900.0.38)
  Target: x86_64-apple-darwin16.7.0
  Thread model: posix
  
  clang++ -O3 -std=c++11 CppSort.cpp -o CppSort
  ./CppSort     
  Elapsed time: 0.736784
  

  判决

  截至本文撰写时，使用 -O 与上述编译器和库编译时，Swift 's sort is fast, but not yet as fast as C++'的排序 . 使用 -Ounchecked ，它似乎与Swift 4.0.2和Apple LLVM 9.0.0中的C一样快 .

  回复于 2024-04-30T11:32:05+08:00
• 29

  func partition(inout list : [Int], low: Int, high : Int) -> Int {
      let pivot = list[high]
      var j = low
      var i = j - 1
      while j < high {
          if list[j] <= pivot{
              i += 1
              (list[i], list[j]) = (list[j], list[i])
          }
          j += 1
      }
      (list[i+1], list[high]) = (list[high], list[i+1])
      return i+1
  }
  
  func quikcSort(inout list : [Int] , low : Int , high : Int) {
  
      if low < high {
          let pIndex = partition(&list, low: low, high: high)
          quikcSort(&list, low: low, high: pIndex-1)
          quikcSort(&list, low: pIndex + 1, high: high)
      }
  }
  
  var list = [7,3,15,10,0,8,2,4]
  quikcSort(&list, low: 0, high: list.count-1)
  
  var list2 = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
  quikcSort(&list2, low: 0, high: list2.count-1)
  
  var list3 = [1,3,9,8,2,7,5]
  quikcSort(&list3, low: 0, high: list3.count-1)
  

  这是关于快速排序的博客Github sample Quick-Sort

  您可以在分区列表中查看Lomuto的分区算法 . 用Swift写的

  回复于 2024-04-30T11:32:05+08:00
• 101

  TL;DR ：是的，目前唯一的Swift语言实现很慢 . 如果您需要快速的数字（以及其他类型的代码，可能是代码）代码，请使用另一个代码 . 将来，您应该重新评估您的选择 . 但是，对于大多数应用程序代码而言，它可能已经足够好了 .

  从我在SIL和LLVM IR中看到的情况来看，似乎他们需要一堆优化来删除保留和释放，这可能是在Clang（针对Objective-C）中实现的，但他们却没有't ported them yet. That' s理论我是（现在......我还需要确认Clang对此做了些什么），因为在这个问题的最后一个测试用例上运行的探查器产生了这个“漂亮”的结果：

  

  

  正如许多其他人所说， -Ofast 完全不安全并且改变了语言语义 . 对我来说，'s at the “If you'将继续使用它，只需使用另一种语言“舞台 . 如果它发生变化，我将在稍后重新评估该选择 .

  -O3 给我们带来了一堆 swift_retain 和 swift_release 调用，老实说，看起来他们不应该在这个例子中 . 优化器应该将它们（大部分）省略为AFAICT，因为它知道有关该数组的大部分信息，并且知道它（至少）有一个强引用它 .

  它甚至不应该调用可能释放对象的函数 . 我不认为数组构造函数可以返回一个小于所要求的数组，这意味着发出的大量检查都是无用的 . 它也知道整数永远不会超过10k，所以可以优化溢出检查（不是因为 -Ofast 古怪，但是由于语言的语义（没有其他任何东西改变了var也无法访问它，并且加起来10k对于 Int ）类型是安全的 .

  但是，编译器可能无法取消装入数组或数组元素，因为它们被传递给 sort() ，这是一个外部函数，必须得到它所期望的参数 . 这将使我们必须间接使用 Int 值，这会使它变得有点慢 . 如果编译器可以使用 sort() 泛型函数（不是以多方法方式）并且内联，则可能会发生这种情况 .

  这是一种非常新的（公开）语言，它正在经历我认为的很多变化，因为有人（大量）参与Swift语言请求反馈，他们都说语言没有完成，并且会更改 .

  使用的代码：

  import Cocoa
  
  let swift_start = NSDate.timeIntervalSinceReferenceDate();
  let n: Int = 10000
  let x = Int[](count: n, repeatedValue: 1)
  for i in 0..n {
      for j in 0..n {
          let tmp: Int = x[j]
          x[i] = tmp
      }
  }
  let y: Int[] = sort(x)
  let swift_stop = NSDate.timeIntervalSinceReferenceDate();
  
  println("\(swift_stop - swift_start)s")
  

  P.S：我不是Objective-C的专家，也不是Cocoa，Objective-C或Swift运行时的所有工具 . 我也可能会假设一些我没写过的东西 .

  回复于 2024-04-30T11:32:05+08:00