Iri*_*mFX 7 memory-management swift
在尝试学习Swift 2.2时,我在尝试分配许多小对象时遇到了严重的性能下降(从根本上说,是一个262144元素的BST).我目前的基准是一个古老的喀嚓,我几年前写的,一个Java 1.8.0_74编译它,在59秒(59036178微秒)我2012的Retina MacBook Pro的执行.我可以通过Instruments观察到的问题是每次迭代我会得到几十个swift_retain_和swift_release.不知道如何避免它们:
import Foundation
import Darwin;
import Foundation
public class BinarySearchTree<T : Comparable> {
private var _value : T?;
private var _leftTree : BinarySearchTree<T>?;
private var _rightTree : BinarySearchTree<T>?;
public init(value : T) {
_value = value;
}
var value : T? {
get {
return self._value;
}
set {
self._value = newValue;
}
}
var leftTree : BinarySearchTree<T>? {
get {
return self._leftTree;
}
set {
self._leftTree = newValue;
}
}
var rightTree : BinarySearchTree<T>? {
get {
return self._rightTree;
}
set {
self._rightTree = newValue;
}
}
public func add(newValue : T) -> BinarySearchTree<T> {
var navigator : BinarySearchTree<T>?;
var subtree : BinarySearchTree<T>?;
var done : Bool?;
done = false;
navigator = self;
while (!done!) {
if (newValue < navigator?.value) {
subtree = navigator?.leftTree;
if (subtree != nil) {
navigator = subtree;
} else {
let newNode = BinarySearchTree<T>(value: newValue);
navigator!.leftTree = newNode;
done = true;
}
} else if (newValue > navigator?.value) {
subtree = navigator?.rightTree;
if (subtree != nil) {
navigator = subtree;
} else {
let newNode = BinarySearchTree<T>(value: newValue);
navigator?.rightTree = newNode;
done = true;
}
} else {
done = true;
}
}
return self;
}
} /* cut remove/search methods */
这是我为测试运行编写的测试代码
let count : Int32 = 262144;
let base : Int32 = 65536;
let target : Int32 = count + 1;
var info = mach_timebase_info(numer:0, denom:0);
var timebase = mach_timebase_info(&info);
let numer = UInt64(info.numer);
let denom = UInt64(info.denom);
let norm = UInt64(numer/denom);
let check1 = (mach_absolute_time() * norm);
var root = BinarySearchTree<Int32>(value:base);
for var loop in 0 ... count-1 {
if (loop % 1000 == 0) {
print(loop);
}
root = root.add(loop);
}
let check2 = (mach_absolute_time() * norm);
print("Creation phase microseconds: [" + String((check2 - check1) / 1000) + "]");
我试着寻找特定的快速释放/保留问题而没有运气,我不知道如何继续.感谢大家
你注意到的问题是保留/释放(虽然它不是真的,保留/释放在嗯的力量旁边是微不足道的......我们最终会到达那里).这与分配无关.你没有分配额外的对象,你只是简单地保留它们然后释放它们.我将从Kenneth的代码开始,该代码优化了原始版本中的许多性能问题,但仍然存在这个问题.(我没有考虑递归代码,因为它在你当前的用例中崩溃了.但它确实躲避了一些冗余的保留.)
值得一提的是,Kenneth的代码很好,通常是你应该做的事情(因为随着你的进展,你会看到更多).
首先要注意:当你提到的时候-Ofast,那就是ObjC,而不是Swift.Swift的旗帜就是-O.你也想要-whole-module-optimization,但这对这里没有任何帮助.
还有一件小事,那我们就明白了.final随时标记课程.这确保没有动态调度.这与保留/释放相比并不重要,但是,嘿,采取简单的东西.
好的,现在是一个很大的,这是一个技巧.我发现我可以通过重写这个来减少大约30%的时间(从完全导入的大约6分钟到大约4分钟):
guard let subtree = navigator.leftTree else {
navigator.leftTree = BinarySearchTree<T>(value: newValue)
break
}
navigator = subtree
continue
这样:
let subtree = navigator.leftTree
if subtree == nil {
navigator.leftTree = BinarySearchTree(value: newValue)
break
}
navigator = subtree!
continue
这是一件非常谨慎的事情.在这种情况下,结果会更快,但在其他输入中可能不会那么快.对于优化器的更改可能没有那么快(SIL生成有点奇怪,我怀疑实际上可能是一个错误,因为它似乎navigator在第二种情况下加倍保留,但只有在if成功之后).但它似乎目前似乎更快.(编辑:Swift团队对这一发现感到惊讶,现在有一个错误对它开放了.不要指望这会在将来发挥作用.)
但就像你说的那样,我们难道不能用结构避免这一切吗？但是每次触摸它时复制整棵树都是非常昂贵的.当然,我们可以通过像Array一样使用copy-on-write来显着改善它.但COW非常复杂.如果只有一种方法可以重用现有的东西.如果我们使用Array怎么办？
private struct Node<Element: Comparable> {
let value: Element
var leftIndex = -1 // Ugly, but ~25% faster than using Int? in my tests
var rightIndex = -1
init(_ value: Element) { self.value = value }
}
// This works exactly the same if you make it a `final class`. Your choice.
public struct BinarySearchTree<Element: Comparable> {
private var storage: [Node<Element>] = []
init(value: Element) { storage.append(Node(value)) }
public mutating func add(newValue: Element) {
if storage.isEmpty {
storage.append(Node(newValue))
}
var index = 0
while (true) {
let node = storage[index]
if (newValue < node.value) {
if node.leftIndex < 0 {
storage.append(Node(newValue))
storage[index].leftIndex = storage.count - 1 // Don't use node here; remember value types!
break
}
index = node.leftIndex
continue
} else if (newValue > node.value) {
if node.rightIndex < 0 {
storage.append(Node(newValue))
storage[index].rightIndex = storage.count - 1
break
}
index = node.rightIndex
continue
} else {
break
}
}
}
}
这需要大约45秒才能在我的系统上运行.当然这delete有点复杂.您要么必须接受"泄露"的内存(可能需要定期重新打包),要么您需要维护空闲列表.但是,自由主义者不会太难添加.
add().当然,重要的是要记住,这是BST的近乎病态的情况.即使你经常按顺序交付数据,你最好在插入数据之前应用shuffle,甚至包括shuffle的成本.例如,使用shuffleInPlace(并计算其时间),插入完全相同的值:
var values = Array(0 ... count - 1)
values.shuffleInPlace()
for (loop, value) in values.enumerate() {
if (loop % 1000 == 0) {
print(loop)
}
root.add(value)
}
这需要我们从45s到大约0.1s.(Kenneth的版本和我的"!"版本在这个指标下约为0.2秒;我可能会使用Kenneth的解决方案,final添加.甚至你的原始代码,肯尼斯修复了很多低效率,只需0.5秒记住,在我的系统上,带有按顺序添加的Kenneth优化版本是6分钟.)
在插入之前进行随机播放是值得的.如果你随着时间的推移得到了东西,那么在插入之前将它们分批并随机播放是值得的.如果树随着时间的推移而变化,那么值得检查它是否变得太深并且定期重建它.保持树深度合理压倒所有其他优化.解决Swift内存管理的聪明方法无法触及这一变化.
修复算法.相比之下,其他一切都是花生.
小智 1
我简化了您的代码，删除了一些代码Optionals和您的 getter/setter，因为它们是不必要的并且可能会导致代码缓慢。
我分析了你的代码和我的代码，并在相同的随机元素数据集上得到了这个结果：
1000 个元素：
您的：创建阶段微秒：[28680771]
我的：创建阶段微秒：[8564279]
10000 个元素：
您的：创建阶段微秒：[426233689]
我的：创建阶段微秒：[126725800]
这是我的代码：
public class BinarySearchTree2<T : Comparable> {
public init(value : T) {
self.value = value
}
var value : T
var leftTree : BinarySearchTree2<T>?
var rightTree : BinarySearchTree2<T>?
public func add(newValue : T) -> BinarySearchTree2<T> {
var navigator = self
while (true) {
if (newValue < navigator.value) {
guard let subtree = navigator.leftTree else {
navigator.leftTree = BinarySearchTree2<T>(value: newValue)
break
}
navigator = subtree
continue
}
if (newValue > navigator.value) {
guard let subtree = navigator.rightTree else {
navigator.rightTree = BinarySearchTree2<T>(value: newValue)
break
}
navigator = subtree
continue
}
break
}
return self
}
} /* cut remove/search methods */
编辑：
我还做了一个更优化的平衡树测试，其中创建了一个包含 1001 个连续元素的数据集，删除了中间元素，使用 Fisher-Yates 洗牌来随机化顺序，使用中间元素初始化根，然后运行两个集合。这是我的结果：
您的：创建阶段微秒：[27648219]
我的：创建阶段微秒：[8332361]
编辑2：
我将add()方法切换为使用递归，从而显着提高了速度：
之前（我的原始代码）：创建阶段微秒：[8088804]
之后：创建阶段微秒：[1179398]
这是新代码：
public class BinarySearchTree3<T : Comparable> {
public init(value : T) {
self.value = value
}
let value : T
var leftTree : BinarySearchTree3<T>?
var rightTree : BinarySearchTree3<T>?
public func add(newValue : T) {
if (newValue < self.value) {
if self.leftTree?.add(newValue) == nil {
self.leftTree = BinarySearchTree3<T>(value: newValue)
}
return
}
if (newValue > self.value) {
if self.rightTree?.add(newValue) == nil {
self.rightTree = BinarySearchTree3<T>(value: newValue)
}
return
}
}
} /* cut remove/search methods */
| 归档时间： |
|
| 查看次数： |
359 次 |
| 最近记录： |