1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2022 - 2024 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
//===----------------------------------------------------------------------===//
public struct _HashTreeStatistics {
/// The number of nodes in the tree.
public internal(set) var nodeCount: Int = 0
/// The number of collision nodes in the tree.
public internal(set) var collisionNodeCount: Int = 0
/// The number of elements within this tree.
public internal(set) var itemCount: Int = 0
/// The number of elements whose keys have colliding hashes in the tree.
public internal(set) var collisionCount: Int = 0
/// The number of key comparisons that need to be done due to hash collisions
/// when finding every key in the tree.
public internal(set) var _collisionChainCount: Int = 0
/// The maximum depth of the tree.
public internal(set) var maxItemDepth: Int = 0
internal var _sumItemDepth: Int = 0
/// The sum of all storage within the tree that is available for item storage,
/// measured in bytes. (This is storage is shared between actual
/// items and child references. Depending on alignment issues, not all of
/// this may be actually usable.)
public internal(set) var capacityBytes: Int = 0
/// The number of bytes of storage currently used for storing items.
public internal(set) var itemBytes: Int = 0
/// The number of bytes of storage currently used for storing child
/// references.
public internal(set) var childBytes: Int = 0
/// The number of bytes currently available for storage, summed over all
/// nodes in the tree.
public internal(set) var freeBytes: Int = 0
/// An estimate of the actual memory occupied by this tree. This includes
/// not only storage space for items & children, but also the memory taken up
/// by node headers and Swift's object headers.
public internal(set) var grossBytes: Int = 0
/// The average level of an item within this tree.
public var averageItemDepth: Double {
guard nodeCount > 0 else { return 0 }
return Double(_sumItemDepth) / Double(itemCount)
}
/// An estimate of how efficiently this data structure manages memory.
/// This is a value between 0 and 1 -- the ratio between how much space
/// the actual stored data occupies and the overall number of bytes allocated
/// for the entire data structure. (`itemBytes / grossBytes`)
public var memoryEfficiency: Double {
guard grossBytes > 0 else { return 1 }
return Double(itemBytes) / Double(grossBytes)
}
public var averageNodeSize: Double {
guard nodeCount > 0 else { return 0 }
return Double(capacityBytes) / Double(nodeCount)
}
/// The average number of keys that need to be compared within the tree
/// to find a member item. This is exactly 1 unless the tree contains hash
/// collisions.
public var averageLookupChainLength: Double {
guard itemCount > 0 else { return 1 }
return Double(itemCount + _collisionChainCount) / Double(itemCount)
}
internal init() {
// Nothing to do
}
}
extension _HashNode {
internal func gatherStatistics(
_ level: _HashLevel, _ stats: inout _HashTreeStatistics
) {
// The empty singleton does not count as a node and occupies no space.
if self.raw.storage === _emptySingleton { return }
read {
stats.nodeCount += 1
stats.itemCount += $0.itemCount
if isCollisionNode {
stats.collisionNodeCount += 1
stats.collisionCount += $0.itemCount
stats._collisionChainCount += $0.itemCount * ($0.itemCount - 1) / 2
}
let keyStride = MemoryLayout<Key>.stride
let valueStride = MemoryLayout<Value>.stride
stats.maxItemDepth = Swift.max(stats.maxItemDepth, level.depth)
stats._sumItemDepth += (level.depth + 1) * $0.itemCount
stats.capacityBytes += $0.byteCapacity
stats.freeBytes += $0.bytesFree
stats.itemBytes += $0.itemCount * (keyStride + valueStride)
stats.childBytes += $0.childCount * MemoryLayout<_RawHashNode>.stride
let objectHeaderSize = 2 * MemoryLayout<Int>.stride
// Note: for simplicity, we assume that there is no padding between
// the object header and the storage header.
let start = _getUnsafePointerToStoredProperties(self.raw.storage)
let capacity = self.raw.storage.capacity
let end = $0._memory + capacity * MemoryLayout<_RawHashNode>.stride
stats.grossBytes += objectHeaderSize + (end - start)
for child in $0.children {
child.gatherStatistics(level.descend(), &stats)
}
}
}
}
|
