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

你的结构的大小是 9 字节，而不是 5。

你可以用sizeof查看：

let size = sizeof( Trie< UInt32 > );

此外，您迭代了 300'000 次，但插入了 3 个值（当然，这是一个 trie）。所以这是 900'000。
无论如何，这本身并不能解释您观察到的内存消耗。

我不是很流利Swift，我也看不懂你的代码。
也许它也有一些错误，导致它分配了比需要更多的内存。

但是无论如何，为了了解发生了什么，您需要运行在 Instruments (command-i) 中运行您的代码。

在我的机器上，我可以看到 swift_slowAlloc.
分配了 900'000 96 字节 这样更像...

假设您的代码没有错误，为什么是 96 个字节？
好吧，这可能是因为为元素分配内存的方式。
当满足请求时，内存分配器可能会分配比请求更多的内存。这可能是因为它需要一些内部元数据，因为分页，因为对齐，...

但是尽管如此，它似乎真的很夸张，所以请使用工具并仔细检查您的代码在做什么。

Answer 2

sizeof 仅报告堆栈上的静态足迹，Dictionary 只是对其内部引用类型实现的引用的一种包装，以及写时复制支持。也就是说，你字典的key-value对和hashtable是分配在堆上的，sizeof没有覆盖到。这适用于所有其他 Swift 集合类型。

在你的例子中，你正在创建三个 Trie - 间接创建三个字典 - 300000 的每次迭代。如果@Macmade 提到的 96 字节分配是最小开销，我不会感到惊讶字典的（例如它的哈希桶）。

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

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

应该使用更少的内存。

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

Swift Dictionary Memory Consumption is Astronomical

xcode

swift

dictionary

memory

trie