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

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

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

我在Twitter上說過：

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

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

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

<!--more-->

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

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

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

言歸正傳——有時你會用 reduce 來構(gòu)建一個數(shù)組（字典或者集合）。下面是使用 reduce 實現(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
    }
}

不同點在于， + 運算每次都會拷貝不斷變長的數(shù)組?？截悢?shù)組消耗的時間是線性的。也就是說，遍歷整個數(shù)組時，隨著數(shù)組長度的增長，消耗總時間成二次冪增長。

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

但是這個和鏈表又有什么關(guān)系？因為你可以利用 上次鏈表的代碼 來實現(xiàn) reduce 版本的 map，就像下面這樣：

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

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

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

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

ManagedBuffer

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

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

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

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

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

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

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


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

我們不直接使用 MyArrayBuffer 的 init —— 而使用 ManagedBuffer 的類方法。因為這個方法的返回值是父類，我們需要將其向下強制轉(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ū)添加兩個相當相似的方法，一個用來拷貝內(nèi)存，另一個用來調(diào)整內(nèi)存大小?？截惙椒〞跈z測到共享存儲時調(diào)用，調(diào)整大小方法則會在需要更多內(nèi)存時調(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>
        }
    }
}

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

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

最后，我們給 MyArray 添加一個 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) }
    }
}

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

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

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

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

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

事實上你可以在 lhs 變量之前使用 var 標識符來進一步縮短代碼：

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

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

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

現(xiàn)在我們有了一個完全可用的寫時拷貝數(shù)組的雛形，你可以對它做 append 操作，它也實現(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
}

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

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

來看一個更簡單的例子：

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

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

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

reduce 方法也沒什么不同，下面是一種可能的實現(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)] }，你會發(fā)現(xiàn) + 操作符同樣不知道我們直接將結(jié)果賦值給了 result 變量。檢查代碼我們就知道，如果有可能的話把右側(cè)的內(nèi)容添加到左側(cè)的內(nèi)容中是可行的（理論上來說是的，因為盡管數(shù)組是以不可變值傳遞，但是它的緩沖區(qū)是一個類，這樣它就有了引用語義，從而可以被改變）。但是 + 操作符單通過它的位置是不可能知道這點的。它只是明確的知道左側(cè)內(nèi)容的拷貝不是緩沖區(qū)唯一的持有者，還有另外一個持有者—— reduce 也持有 result 的一份拷貝——而且馬上就要將其摒棄然后使用新的結(jié)果來替換它，但是這都是在 + 操作執(zhí)行之后。

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

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