[譯]Swift 中數(shù)組和鏈表的性能

作者：airspeedvelocity，原文鏈接，原文日期：2015/08/03
譯者：mmoaay；校對：shanks；定稿：numbbbbb

病人：醫(yī)生醫(yī)生，我一啪啪就蛋疼
醫(yī)生：那就別啪

我在Twitter上說過：

使用 reduce 構(gòu)建數(shù)組雖然有趣，但有使性能減半的風(fēng)險(xiǎn)。

很多人覺得這句話很奇怪，這讓我非常驚訝。相當(dāng)一部分人建議將 reduce 改成不做數(shù)組拷貝（我不認(rèn)為這樣是可行的）。也有建議說需要對 + 運(yùn)算符做優(yōu)化，讓它不做拷貝操作（我同樣不認(rèn)為這樣做很簡單，而且很快我們就會(huì)意識(shí)到這一點(diǎn)）。

其他人建議我除非文檔有提到，不然就不需要在意這些細(xì)枝末節(jié)的問題（而我認(rèn)為這是在編寫代碼時(shí)必須注意的——說什么“只有在文檔告訴我這里有問題時(shí)我才注意”就好像“只有單元測試結(jié)果顯示不正確時(shí)我才編寫正確代碼”一樣。）

<!--more-->

而其他的反饋中，有一部分與我之前發(fā)的鏈表那篇文章有關(guān)，為什么去實(shí)現(xiàn)一個(gè)已經(jīng)過時(shí)的數(shù)據(jù)結(jié)構(gòu)？我們已經(jīng)有數(shù)組了，它的存在還有什么意義？

所以，你就知道為什么我有時(shí)候會(huì)特別提到這不只是一個(gè)關(guān)于 Mac 和 iOS 編程的博客？這當(dāng)然不是一個(gè)只關(guān)于 Mac 和 iOS 編程的博客！不要因?yàn)槲遗既挥X得一個(gè)包含枚舉類型的鏈表有趣你就把它放到你的 app 里。因?yàn)槲視?huì)對隨之而來的性能問題產(chǎn)生興趣，而你不會(huì)。盡管如此，我覺得鏈表的例子非常有意思，而且值得實(shí)現(xiàn)和把玩，它有可能會(huì)提升數(shù)組 reduce 方法的性能。甚至在某些（少見的）場景下對實(shí)際編碼有用。

同時(shí)我認(rèn)為 Swift 的一些額外特性很有趣：比如它的枚舉可以靈活的在對象和具體方法中自由選擇，以及“默認(rèn)安全”。這些都促使它成為一門非常好的計(jì)算機(jī)教學(xué)類語言。這本書 未來的版本可能就會(huì)用 Swift 作為實(shí)現(xiàn)語言。

言歸正傳——有時(shí)你會(huì)用 reduce 來構(gòu)建一個(gè)數(shù)組（字典或者集合）。下面是使用 reduce 實(shí)現(xiàn)的 map：

extension SequenceType {
   func mapUsingReduce<T>(transform: Generator.Element->T) -> [T] {
        return reduce([]) { $0 + [transform($1)] }
    }
}

作為對比，可以創(chuàng)建可變數(shù)組然后使用 for 循環(huán)：

extension SequenceType {
   func mapUsingFor<T>(transform: Generator.Element->T) -> [T] {
        var result: [T] = []
        for x in self { result.append(transform(x)) }
        return result
    }
}

不同點(diǎn)在于， + 運(yùn)算每次都會(huì)拷貝不斷變長的數(shù)組。拷貝數(shù)組消耗的時(shí)間是線性的。也就是說，遍歷整個(gè)數(shù)組時(shí)，隨著數(shù)組長度的增長，消耗總時(shí)間成二次冪增長。

盡管如此，正常來說人們都不會(huì)去重新實(shí)現(xiàn) map 函數(shù)：你看到的會(huì)是這樣一些技巧：告訴你先去重或者根據(jù)詞頻建立字典。但是最本質(zhì)的問題仍然存在。

但是這個(gè)和鏈表又有什么關(guān)系？因?yàn)槟憧梢岳?上次鏈表的代碼 來實(shí)現(xiàn) reduce 版本的 map，就像下面這樣：

extension SequenceType {
    func mapToList<T>(transform: Generator.Element->T) -> List<T> {
        return reduce(List()) { $0.cons(transform($1)) }.reverse()
    }
}

結(jié)果就是這個(gè)版本的性能竟然只有數(shù)組版本的一半（因?yàn)?reverse 這一步），以至于你的老師都會(huì)懷疑你是在測試結(jié)果上作弊，而不是實(shí)驗(yàn)產(chǎn)生的結(jié)果：

得到這個(gè)結(jié)果的原因是鏈表是連續(xù)的——舊的鏈表和新連接的鏈表之間永遠(yuǎn)都是用節(jié)點(diǎn)相連。所以不需要拷貝。但是代價(jià)是只能從頭部增加鏈表的長度（所以才需要 reverse），而且鏈表必須保持不變。所以就算鏈表只有一個(gè)引用，也需要先拷貝再對它進(jìn)行修改。這和 Array 是有區(qū)別的， Array 可以檢測它的緩沖區(qū)何時(shí)被單獨(dú)訪問，這樣就可以直接修改，不需要拷貝。使用鏈表還有其他的代價(jià)——統(tǒng)計(jì)鏈表節(jié)點(diǎn)的個(gè)數(shù)所需要的時(shí)間是統(tǒng)計(jì)數(shù)組元素個(gè)數(shù)時(shí)間的兩倍，因?yàn)楸闅v鏈表時(shí)的間接尋址方式是需要消耗時(shí)間的。

所以數(shù)組在 + 操作時(shí)做完全拷貝的問題到底能不能解決？在考慮這個(gè)問題之前，我們先來看一個(gè)寫時(shí)拷貝數(shù)組能有什么幫助。Mike Ash 的 一篇牛x博文 已經(jīng)實(shí)現(xiàn)了一個(gè)寫時(shí)拷貝數(shù)組，所以我們稍作改變，使用標(biāo)準(zhǔn)庫中的 ManagedBuffer 類來實(shí)現(xiàn)寫時(shí)拷貝數(shù)組。

ManagedBuffer

ManagedBuffer 是一個(gè)可繼承的用于簡化分配/釋放內(nèi)存操作和堆上內(nèi)存管理的類。它是泛型，有 Value 和 Element 這兩個(gè)獨(dú)立占位符。Element 是存儲(chǔ)元素的類型，在創(chuàng)建實(shí)例時(shí)被動(dòng)態(tài)分配。Value 則是附加信息的類型——比如，如果要實(shí)現(xiàn)數(shù)組，你需要存儲(chǔ)元素的個(gè)數(shù)，因?yàn)樵趦?nèi)存釋放之前需要把元素銷毀掉。訪問元素需要使用 withUnsafeMutablePointerToElements，而訪問 value 則可以通過一個(gè)簡單的非安全方法，或者直接使用 .value 屬性。

下面的代碼實(shí)現(xiàn)了一個(gè)極簡的自銷毀數(shù)組緩沖區(qū)：

private class MyArrayBuffer<Element>: ManagedBuffer<Int,Element> {
    deinit {
        self.withUnsafeMutablePointerToElements { elems->Void in
            elems.destroy(self.value)
        }
    }
}

這樣一來， MyArrayBuffer 存儲(chǔ)的元素仍然是泛型， 但是我們把 ManagedBuffer 的 Value 設(shè)置為 Int， 用來保存緩沖區(qū)元素的個(gè)數(shù)（有一點(diǎn)要銘記于心，我們會(huì)分配比數(shù)組中元素更多的空間，用來避免頻繁的重分配操作）。

當(dāng)緩沖區(qū)被析構(gòu)時(shí)，MyArrayBuffer.deinit 會(huì)在 ManagedBuffer.deinit 之前調(diào)用，ManagedBuffer.deinit 會(huì)釋放內(nèi)存。這樣的話 MyArrayBuffer 就有機(jī)會(huì)銷毀其所有對象。如果 Element 不單單是一個(gè)被動(dòng)的結(jié)構(gòu)體，銷毀對象就非常有必要——比如，如果數(shù)組里面包含了其他寫時(shí)拷貝類型，銷毀它們會(huì)觸發(fā)它們?nèi)メ尫抛陨淼膬?nèi)存。

現(xiàn)在我們可以建立一個(gè)數(shù)組類型的結(jié)構(gòu)體，這個(gè)結(jié)構(gòu)體使用一個(gè)私有的緩沖區(qū)來進(jìn)行存儲(chǔ)：

public struct MyArray<Element> {
    private var _buf: MyArrayBuffer<Element>


    public init() {
        _buf = MyArrayBuffer<Element>.create(8) { _ in 0 } as! MyArrayBuffer<Element>
    }
}

我們不直接使用 MyArrayBuffer 的 init —— 而使用 ManagedBuffer 的類方法。因?yàn)檫@個(gè)方法的返回值是父類，我們需要將其向下強(qiáng)制轉(zhuǎn)換為正確的類型。

然后我們讓 MyArray 支持集合操作：

extension MyArray: CollectionType {
    public var startIndex: Int { return 0 }
    public var endIndex: Int { return _buf.value }


    public subscript(idx: Int) -> Element {
        guard idx < self.endIndex else { fatalError("Array index out of range") }
        return _buf.withUnsafeMutablePointerToElements { $0[idx] }
    }
}

接著，我們需要為緩沖區(qū)添加兩個(gè)相當(dāng)相似的方法，一個(gè)用來拷貝內(nèi)存，另一個(gè)用來調(diào)整內(nèi)存大小。拷貝方法會(huì)在檢測到共享存儲(chǔ)時(shí)調(diào)用，調(diào)整大小方法則會(huì)在需要更多內(nèi)存時(shí)調(diào)用：

extension MyArrayBuffer {
    func clone() -> MyArrayBuffer<Element> {
        return self.withUnsafeMutablePointerToElements { oldElems->MyArrayBuffer<Element> in
            return MyArrayBuffer<Element>.create(self.allocatedElementCount) { newBuf in
                newBuf.withUnsafeMutablePointerToElements { newElems->Void in
                    newElems.initializeFrom(oldElems, count: self.value)
                }
                return self.value
            } as! MyArrayBuffer<Element>
        }
    }


    func resize(newSize: Int) -> MyArrayBuffer<Element> {
        return self.withUnsafeMutablePointerToElements { oldElems->MyArrayBuffer<Element> in
            let elementCount = self.value
            return MyArrayBuffer<Element>.create(newSize) { newBuf in
                newBuf.withUnsafeMutablePointerToElements { newElems->Void in
                    newElems.moveInitializeFrom(oldElems, count: elementCount)
                }
                self.value = 0
                return elementCount
            } as! MyArrayBuffer<Element>
        }
    }
}

同時(shí)構(gòu)建和填充緩沖區(qū)是有些苛刻的——首先我們需要獲得指向已存在元素的非安全指針，然后調(diào)用 create，這個(gè)方法擁有的閉包會(huì)接收一個(gè)只構(gòu)建了一部分的對象（比如，分配了內(nèi)存但是沒有初始化），這個(gè)對象隨后需要調(diào)用 newBuf.withUnsafeMutablePointerToElements 來把內(nèi)存從舊的緩沖區(qū)拷貝到新的緩沖區(qū)。

這兩個(gè)方法最主要的不同點(diǎn)是 clone 不會(huì)改變舊的緩沖區(qū)中的元素，而只是把新的拷貝加載到新的緩沖區(qū)。 resize 則會(huì)把元素從舊的內(nèi)存移動(dòng)到新的內(nèi)存（通過 UnsafeMutablePointer 的 moveInitializeFrom 方法），然后更新舊的緩沖區(qū)，告訴它已經(jīng)不需要管理任何元素——不然，它會(huì)試圖在 deinit 時(shí)銷毀它們。

最后，我們給 MyArray 添加一個(gè) append 和 extend 方法：

extension MyArray {
    public mutating func append(x: Element) {
        if !isUniquelyReferencedNonObjC(&_buf) {
            _buf = _buf.clone()
        }


        if _buf.allocatedElementCount == count {
            _buf = _buf.resize(count*2)
        }


        _buf.withUnsafeMutablePointers { (val, elems)->Void in
            (elems + val.memory++).initialize(x)
        }
    }


    public mutating func extend<S: SequenceType where S.Generator.Element == Element>(seq: S) {
        for x in seq { self.append(x) }
    }
}

這只是一段樣例代碼。事實(shí)上，你可能會(huì)把唯一性判斷代碼和調(diào)整大小代碼單獨(dú)抽出來，這樣你就可以在下標(biāo)集和其他稍微有變化的方法中重用。我懶得寫，所以就把他們都塞在 append 方法里面了。此外，有可能的話你應(yīng)該為 append 保留足夠的空間讓它進(jìn)行擴(kuò)展，這樣就可以防止在同時(shí)共享且空間太小時(shí)緩沖區(qū)被加倍。但是所有這些對于我們的偉大藍(lán)圖都沒有太大影響。

好了，下面就到操作符了。首先， += ，賦值操作符，它的左值是 inout 的，使用右值對左側(cè)進(jìn)行擴(kuò)展：

func +=<Element, S: SequenceType where S.Generator.Element == Element>
  (inout lhs: MyArray<Element>, rhs: S) {
    lhs.extend(rhs)
}

最后是 + 操作符。我們可以根據(jù) += 操作符的方式來實(shí)現(xiàn)它。這個(gè)操作符傳入兩個(gè)不可變的數(shù)組，然后將它們合并成一個(gè)新的數(shù)組。它依賴于寫時(shí)拷貝動(dòng)作來為左值創(chuàng)建一個(gè)可變拷貝，然后使用右值進(jìn)行擴(kuò)展：

func +<Element, S: SequenceType where S.Generator.Element == Element>
  (lhs: MyArray<Element>, rhs: S) -> MyArray<Element> {
    var result = lhs
    result += rhs
    return result
}

事實(shí)上你可以在 lhs 變量之前使用 var 標(biāo)識(shí)符來進(jìn)一步縮短代碼：

func +<Element, S: SequenceType where S.Generator.Element == Element>
  (var lhs: MyArray<Element>, rhs: S) -> MyArray<Element> {
    lhs += rhs
    return lhs
}

之所以有第二個(gè)版本是因?yàn)橛腥苏f reduce 的實(shí)現(xiàn)中應(yīng)該為累加參數(shù)添加 var 標(biāo)識(shí)符。而這和我們對 lhs 的修改類似： var 所做的事情只是聲明傳入的參數(shù)是可變的。它仍然是拷貝——它不是以某種方式傳遞過來原值的引用。

+ 操作符可以優(yōu)化嗎？

現(xiàn)在我們有了一個(gè)完全可用的寫時(shí)拷貝數(shù)組的雛形，你可以對它做 append 操作，它也實(shí)現(xiàn)了 + 操作符。這也就意味著我們可以用它來重寫 reduce 版的 map 方法：

func mapUsingMyReduce<T>(transform: Generator.Element->T) -> MyArray<T> {
    return reduce([]) { $0 + [transform($1)] }
}


func mapUsingMyFor<T>(transform: Generator.Element->T) -> MyArray<T> {
    var result = MyArray<T>()
    for x in self { result.append(transform(x)) }
    return result
}

如果你用圖表對性能進(jìn)行記錄，你會(huì)發(fā)現(xiàn)這兩段代碼和使用數(shù)組實(shí)現(xiàn)的方式的表現(xiàn)完全類似。

所以，現(xiàn)在的情況是我們擁有一個(gè)完全受我們自己控制的實(shí)現(xiàn)，我們可以改變 + 操作符然后讓它不做拷貝么？我不認(rèn)為我們做到了。

來看一個(gè)更簡單的例子：

var a = MyArray<Int>()
a.extend(0..<3)
let b = a + [6,7,8]

我們可以改變這段代碼讓它不做拷貝么？很明顯我們不能。 b 必須是一個(gè)新的數(shù)組拷貝，目的是不影響 a。即使我們在創(chuàng)建 b 之后不對 a 做任何修改， + 操作符的實(shí)現(xiàn)也是沒有辦法知道這些的。也許編譯器會(huì)知道，然后根據(jù)情況進(jìn)行優(yōu)化，但是 + 方法是不可能知道的。

檢查唯一引用也無濟(jì)于事。a 仍然存在，所以 lhs 不可能是緩沖區(qū)的唯一持有者。

reduce 方法也沒什么不同，下面是一種可能的實(shí)現(xiàn)：

extension SequenceType {
    func myReduce<T>(initial: T, combine: (T,Generator.Element)->T) -> T {
        var result = initial
        for x in self {
            result = combine(result,x)
        }
        return result
    }
}

假設(shè)這里的 combine 是 { $0 + [transform($1)] }，你會(huì)發(fā)現(xiàn) + 操作符同樣不知道我們直接將結(jié)果賦值給了 result 變量。檢查代碼我們就知道，如果有可能的話把右側(cè)的內(nèi)容添加到左側(cè)的內(nèi)容中是可行的（理論上來說是的，因?yàn)楸M管數(shù)組是以不可變值傳遞，但是它的緩沖區(qū)是一個(gè)類，這樣它就有了引用語義，從而可以被改變）。但是 + 操作符單通過它的位置是不可能知道這點(diǎn)的。它只是明確的知道左側(cè)內(nèi)容的拷貝不是緩沖區(qū)唯一的持有者，還有另外一個(gè)持有者—— reduce 也持有 result 的一份拷貝——而且馬上就要將其摒棄然后使用新的結(jié)果來替換它，但是這都是在 + 操作執(zhí)行之后。

還有一線希望就是如果每個(gè)數(shù)組剛好是它們自己的分片（然而并不是——而是有一個(gè)叫 ArraySlice 的東西，它需要額外的開銷來把分片的起始和結(jié)束點(diǎn)記錄到父數(shù)組中）。如果它們是的話，也許它們就可以被修改成允許其中一個(gè)、也只能是一個(gè)數(shù)組在做 append 操作時(shí)被其他數(shù)組忽略。但是這通常會(huì)增加數(shù)組的開銷，而我們的目的是快——你肯定不會(huì)為了這種情況就讓它們變慢吧。

也許有一種非常聰明的辦法可以解決所有的問題，可能需要編譯器的幫助也可能不需要。但盡管如此這仍然不是一個(gè)很好的主意。+ 操作符語義是創(chuàng)建一個(gè)新數(shù)組。而想讓它在某種非常特定情況下隱式的修改一個(gè)已經(jīng)存在的數(shù)組顯然不是正確的解決方案。如果你愿意，可以把 var 封裝在一個(gè)小的泛型方法中，就好像它不存在一樣。這樣可以在提高代碼效率的同時(shí)讓代碼更優(yōu)雅。