xcode - Swift 字典内存消耗是天文数字

Question

谁能帮助阐明为什么以下代码在运行时消耗超过 100 MB 的 RAM？

public struct Trie<Element : Hashable> {
    private var children: [Element:Trie<Element>]
    private var endHere : Bool

    public init() {
        children = [:]
        endHere  = false
    }
    public init<S : SequenceType where S.Generator.Element == Element>(_ seq: S) {
        self.init(gen: seq.generate())
    }
    private init<G : GeneratorType where G.Element == Element>(var gen: G) {
        if let head = gen.next() {
            (children, endHere) = ([head:Trie(gen:gen)], false)
        } else {
            (children, endHere) = ([:], true)
        }
    }
    private mutating func insert<G : GeneratorType where G.Element == Element>(var gen: G) {
        if let head = gen.next() {
            let _ = children[head]?.insert(gen) ?? { children[head] = Trie(gen: gen) }()
        } else {
            endHere = true
        }
    }
    public mutating func insert<S : SequenceType where S.Generator.Element == Element>(seq: S) {
        insert(seq.generate())
    }
}

var trie = Trie<UInt32>()
for i in 0..<300000 {
    trie.insert([UInt32(i), UInt32(i+1), UInt32(i+2)])
}

根据我的计算，上述数据结构的总内存消耗应该在以下某处......

3 * count * sizeof(Trie<UInt32>)

或者——

3 * 300,000 * 9 = 8,100,000 bytes = ~8 MB

为什么这个数据结构在运行时消耗超过 100 MB？

Answer 1

sizeof 仅报告堆栈上的静态占用空间，Dictionary 只是对其内部引用类型实现的引用的一种包装，也是副本写支持。也就是说，你的字典的键值对和哈希表是分配在堆上的，sizeof不覆盖。这适用于所有其他 Swift 集合类型。

在您的情况下，您正在创建三个 Trie - 并间接创建三个字典 - 300000 的每次迭代。如果 @Macmade 提到的 96 字节分配是最小值，我不会感到惊讶字典的开销(例如它的哈希桶)。

增加存储空间也可能会产生成本。因此，您可以尝试查看在字典上设置 minimumCapacity 是否有帮助。另一方面，如果您不需要每次迭代都生成不同的路径，您可以考虑使用间接枚举作为替代方案，例如

public enum Trie<Element> {
    indirect case Next(Element, Trie<Element>)
    case End
}

应该使用更少的内存。