Быстрое потребление памяти словаря является астрономическим

Question

Может ли кто-нибудь помочь пролить свет на то, почему приведенный ниже код потребляет более 100 МБ ОЗУ во время работы?

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 МБ во время работы?

Answer 1

sizeof содержит только статический след в стеке, который Dictionary является своего рода оболочкой ссылки на ее внутреннюю реализацию ссылочного типа, а также копию на поддержку записи. Другими словами, пары ключ-значение и хэш-таблица вашего словаря выделяются в куче, которая не покрывается sizeof. Это относится ко всем другим типам коллекции Swift.

В вашем случае вы создаете три Trie - и косвенно три словаря - каждую итерацию 300000. Я не удивлюсь, если 96-байтные распределения, упомянутые @Macmade, являются минимальными служебными данными словаря (например, его хэш-ведро).

Возможны также расходы, связанные с выращиванием хранилища. Поэтому вы можете попытаться выяснить, поможет ли установка словаря minimumCapacity.С другой стороны, если вам не нужен расходящийся путь, сгенерированный на итерацию, вы можете рассматривать косвенное перечисление как альтернативу, например.

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

который должен использовать меньше памяти.

Answer 2

Размер вашей структуры является байт, а не 5.

Вы можете проверить это с sizeof:

let size = sizeof(Trie<UInt32>); 

Кроме того, вы итерацию 300'000 раз, но вставка 3 значения (из Конечно, это трюк). Так что это 900'000.
В любом случае, это не объясняет само по себе потребление памяти, которое вы наблюдаете.

Я не очень свободно владею Свифт, и я не понимаю вас в коде.
Возможно, в нем есть и некоторые ошибки, из-за чего он выделяет больше памяти, чем необходимо.

Но так или иначе, чтобы понять, что происходит, вам необходимо запустить свой код в Приборы (command-i).

На моей машине я могу видеть 900'000 96 bytes Распределение: swift_slowAlloc.
Это больше похоже на это ...

Почему 96 байтов, если в вашем коде нет ошибки?
Ну, это может быть из-за того, как память выделяется для ваших элементов.
При удовлетворении запроса распределитель памяти может выделять больше памяти, чем запрошено. Это может быть связано с тем, что ему нужны некоторые внутренние метаданные из-за подкачки из-за выравнивания, ...

Но, хотя это кажется действительно преувеличенным, используйте инструменты и дважды проверьте, что делает ваш код.