1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
//===--- SortArrayInClass.swift -------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2019 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
// This benchmark is derived from user code that encountered a major
// performance problem in normal usage. Contributed by Saleem
// Abdulrasool (compnerd).
//
//===----------------------------------------------------------------------===//
import TestsUtils
// Specifically tests efficient access to Array subscript when the
// array is a class property, but also generally tests quicksort in a
// class which needs a slew of array optimizations, uniqueness, bounds
// and exclusivity optimizations.
public let benchmarks = [
BenchmarkInfo(
name: "SortArrayInClass",
runFunction: run_SortArrayInClass,
tags: [.abstraction, .safetychecks, .exclusivity, .algorithm, .api, .Array])
]
let largeArraySize = 10000
class Sorter {
var array: [Int]
init(size: Int) {
array = Array((0..<size).reversed())
}
private func _swap(i: Int, j: Int) {
let t = array[i]
// This currently copies the entire array. Assigning to a
// temporary, or using swapAt would avoid the copy, but users
// shouldn't need to know that.
array[i] = array[j]
array[j] = t
}
private func _quicksort(left: Int, right: Int) {
if left < right {
let pivot = array[left + ((right - left) / 2)]
var left_new = left
var right_new = right
repeat {
while array[left_new] < pivot {
left_new += 1
}
while pivot < array[right_new] {
right_new -= 1
}
if left_new <= right_new {
_swap(i:left_new, j:right_new)
left_new += 1
right_new -= 1
}
} while left_new <= right_new
_quicksort(left: left, right: right_new)
_quicksort(left: left_new, right:right)
}
}
func quicksort() {
_quicksort(left:0, right:array.count - 1);
}
}
public func run_SortArrayInClass(_ n: Int) {
for _ in 1...n {
// The array needs to be reinitialized before each sort, so it
// can't be a setup/tearDown function.
let sorter = Sorter(size: largeArraySize)
sorter.quicksort()
}
}
|
