Skip to content

Commit 8f3ee02

Browse files
jakebaileyjakebailey
committed
Store ordinary relationship keys as exact type ID pairs
Ordinary type comparisons need only two 32-bit IDs and intersection context, but retained a 128-bit hash for every cached result. Hashing and storing twice the necessary key width wastes allocations and memory. Keep exact 64-bit pairs in separate maps for the four intersection states. Generic-reference normalization still uses its original full-width hash. An explicit key tag separates both namespaces, including recursion guards, without sacrificing hash bits or changing constrained generic behavior. Six fresh-process interleaved VS Code comparisons against the parent commit, using normal GC, reduce retained heap 0.94% (roughly 33 MiB) and total allocated bytes 1.29%. GC scanning, allocation events, and instruction counts are not statistically different. Tests cover directional and identity comparisons, all intersection contexts, result replacement, exact high-bit IDs, namespace isolation, generic parameter normalization, and constrained versus unconstrained recursion keys. Production diagnostics and all semantic counts match exactly. goos: linux goarch: amd64 pkg: github.com/microsoft/TypeScript/tsc/internal/checker cpu: Intel(R) Core(TM) i9-10900K CPU @ 3.70GHz │ vscode-relation-before-6.txt │ vscode-relation-6.txt │ │ retained-B │ retained-B vs base │ ExternalProgram-20 3.456Gi ± 0% 3.424Gi ± 0% -0.94% (p=0.002 n=6) │ vscode-relation-before-6.txt │ vscode-relation-6.txt │ │ scan-B │ scan-B vs base │ ExternalProgram-20 2.998Gi ± 0% 2.997Gi ± 0% ~ (p=0.310 n=6) │ vscode-relation-before-6.txt │ vscode-relation-6.txt │ │ B/op │ B/op vs base │ ExternalProgram-20 5.021Gi ± 0% 4.956Gi ± 0% -1.29% (p=0.002 n=6) │ vscode-relation-before-6.txt │ vscode-relation-6.txt │ │ allocs/op │ allocs/op vs base │ ExternalProgram-20 31.08M ± 0% 31.07M ± 0% ~ (p=0.240 n=6) │ relation-before-instructions.txt │ relation-instructions.txt │ │ instructions/op │ instructions/op vs base │ ExternalInstructions-20 269.3G ± 2% 270.0G ± 3% ~ (p=0.937 n=6)
1 parent 6c976da commit 8f3ee02

3 files changed

Lines changed: 112 additions & 15 deletions

File tree

‎tsc/internal/checker/checker.go‎

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -18068,7 +18068,7 @@ func getConditionalTypeKey(typeArguments []*Type, alias *TypeAlias, forConstrain
1806818068
return b.hash()
1806918069
}
1807018070

18071-
func getRelationKey(source *Type, target *Type, intersectionState IntersectionState, isIdentity bool, ignoreConstraints bool) (CacheHashKey, bool) {
18071+
func getRelationKey(source *Type, target *Type, intersectionState IntersectionState, isIdentity bool, ignoreConstraints bool) (relationKey, bool) {
1807218072
if isIdentity && source.id > target.id {
1807318073
source, target = target, source
1807418074
}
@@ -18078,12 +18078,15 @@ func getRelationKey(source *Type, target *Type, intersectionState IntersectionSt
1807818078
b.writeByte('g')
1807918079
constrained = b.writeGenericTypeReferences(source, target, ignoreConstraints)
1808018080
} else {
18081-
b.writeByte('s')
18082-
b.writeType(source)
18083-
b.writeType(target)
18081+
// Ordinary relationships need only the two exact IDs. Intersection
18082+
// states select separate maps, leaving generic hashes unmodified.
18083+
return relationKey{value: CacheHashKey{
18084+
Lo: uint64(source.id)<<32 | uint64(target.id),
18085+
Hi: uint64(intersectionState),
18086+
}}, false
1808418087
}
1808518088
b.writeUint32(uint32(intersectionState))
18086-
return b.hash(), constrained
18089+
return relationKey{value: b.hash(), generic: true}, constrained
1808718090
}
1808818091

1808918092
func getNodeListKey(nodes []*ast.Node) CacheHashKey {

‎tsc/internal/checker/relater.go‎

Lines changed: 31 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -96,22 +96,43 @@ func asRecursionId[T *ast.Node | *ast.Symbol | *Type](value T) RecursionId {
9696
}
9797

9898
type Relation struct {
99-
results map[CacheHashKey]RelationComparisonResult
99+
genericResults map[CacheHashKey]RelationComparisonResult
100+
simpleResults [4]map[uint64]RelationComparisonResult
100101
}
101102

102-
func (r *Relation) get(key CacheHashKey) RelationComparisonResult {
103-
return r.results[key]
103+
type relationKey struct {
104+
value CacheHashKey
105+
generic bool
104106
}
105107

106-
func (r *Relation) set(key CacheHashKey, result RelationComparisonResult) {
107-
if r.results == nil {
108-
r.results = make(map[CacheHashKey]RelationComparisonResult)
108+
func (r *Relation) get(key relationKey) RelationComparisonResult {
109+
if key.generic {
110+
return r.genericResults[key.value]
111+
}
112+
return r.simpleResults[key.value.Hi][key.value.Lo]
113+
}
114+
115+
func (r *Relation) set(key relationKey, result RelationComparisonResult) {
116+
if key.generic {
117+
if r.genericResults == nil {
118+
r.genericResults = make(map[CacheHashKey]RelationComparisonResult)
119+
}
120+
r.genericResults[key.value] = result
121+
} else {
122+
results := &r.simpleResults[key.value.Hi]
123+
if *results == nil {
124+
*results = make(map[uint64]RelationComparisonResult)
125+
}
126+
(*results)[key.value.Lo] = result
109127
}
110-
r.results[key] = result
111128
}
112129

113130
func (r *Relation) size() int {
114-
return len(r.results)
131+
size := len(r.genericResults)
132+
for _, results := range r.simpleResults {
133+
size += len(results)
134+
}
135+
return size
115136
}
116137

117138
func (c *Checker) isTypeIdenticalTo(source *Type, target *Type) bool {
@@ -2584,8 +2605,8 @@ type Relater struct {
25842605
errorNode *ast.Node
25852606
errorChain *ErrorChain
25862607
relatedInfo []*ast.Diagnostic
2587-
maybeKeys []CacheHashKey
2588-
maybeKeysSet collections.Set[CacheHashKey]
2608+
maybeKeys []relationKey
2609+
maybeKeysSet collections.Set[relationKey]
25892610
sourceStack []*Type
25902611
targetStack []*Type
25912612
maybeCount int

‎tsc/internal/checker/types_test.go‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -142,6 +142,79 @@ func TestKeyBuilder(t *testing.T) {
142142
}
143143
}
144144

145+
func TestRelationKeys(t *testing.T) {
146+
t.Parallel()
147+
source := &Type{id: 1}
148+
target := &Type{id: ^TypeId(0)}
149+
var relation Relation
150+
assert.Equal(t, relation.size(), 0)
151+
for state := IntersectionStateNone; state <= IntersectionStateSource|IntersectionStateTarget; state++ {
152+
key, constrained := getRelationKey(source, target, state, false, false)
153+
assert.Assert(t, !constrained)
154+
assert.Equal(t, relation.get(key), RelationComparisonResultNone)
155+
relation.set(key, RelationComparisonResultSucceeded)
156+
reverse, _ := getRelationKey(target, source, state, false, false)
157+
assert.Assert(t, key != reverse)
158+
assert.Equal(t, relation.get(reverse), RelationComparisonResultNone)
159+
identity, _ := getRelationKey(target, source, state, true, false)
160+
assert.Equal(t, key, identity)
161+
relation.set(key, RelationComparisonResultFailed|RelationComparisonResultReportsUnreliable)
162+
assert.Equal(t, relation.get(key), RelationComparisonResultFailed|RelationComparisonResultReportsUnreliable)
163+
}
164+
assert.Equal(t, relation.size(), 4)
165+
for state := IntersectionStateNone; state <= IntersectionStateSource|IntersectionStateTarget; state++ {
166+
key, _ := getRelationKey(source, target, state, false, false)
167+
assert.Equal(t, relation.get(key), RelationComparisonResultFailed|RelationComparisonResultReportsUnreliable)
168+
}
169+
}
170+
171+
func TestRelationKeyNamespaces(t *testing.T) {
172+
t.Parallel()
173+
simple, _ := getRelationKey(&Type{id: 1}, &Type{id: 2}, IntersectionStateNone, false, false)
174+
generic := relationKey{value: simple.value, generic: true}
175+
var relation Relation
176+
relation.set(simple, RelationComparisonResultSucceeded)
177+
assert.Equal(t, relation.get(generic), RelationComparisonResultNone)
178+
relation.set(generic, RelationComparisonResultFailed)
179+
assert.Equal(t, relation.get(simple), RelationComparisonResultSucceeded)
180+
assert.Equal(t, relation.get(generic), RelationComparisonResultFailed)
181+
assert.Equal(t, relation.size(), 2)
182+
}
183+
184+
func TestGenericRelationKeys(t *testing.T) {
185+
t.Parallel()
186+
c, types := newCompositeTestChecker()
187+
c.noConstraintType = c.newIntrinsicType(TypeFlagsNever, "no constraint")
188+
root := types[0]
189+
newParameter := func(constraint *Type) *Type {
190+
parameter := &TypeParameter{constraint: constraint}
191+
return c.newType(TypeFlagsTypeParameter, ObjectFlagsNone, parameter.AsType(), typeKindTypeParameter)
192+
}
193+
newReference := func(argument *Type) *Type {
194+
reference := &TypeReference{resolvedTypeArguments: []*Type{argument}}
195+
reference.target = root
196+
return c.newType(TypeFlagsObject, ObjectFlagsReference, reference.AsType(), typeKindTypeReference)
197+
}
198+
left := newReference(newParameter(c.noConstraintType))
199+
right := newReference(newParameter(c.noConstraintType))
200+
equivalentLeft := newReference(newParameter(c.noConstraintType))
201+
equivalentRight := newReference(newParameter(c.noConstraintType))
202+
key, constrained := getRelationKey(left, right, IntersectionStateNone, false, false)
203+
assert.Assert(t, !constrained)
204+
equivalent, _ := getRelationKey(equivalentLeft, equivalentRight, IntersectionStateNone, false, false)
205+
assert.Equal(t, key, equivalent)
206+
var relation Relation
207+
relation.set(key, RelationComparisonResultSucceeded)
208+
assert.Equal(t, relation.get(equivalent), RelationComparisonResultSucceeded)
209+
constrainedLeft := newReference(newParameter(types[1]))
210+
constrainedKey, constrained := getRelationKey(constrainedLeft, right, IntersectionStateNone, false, false)
211+
assert.Assert(t, constrained)
212+
assert.Assert(t, constrainedKey != key)
213+
broadest, constrained := getRelationKey(constrainedLeft, right, IntersectionStateNone, false, true)
214+
assert.Assert(t, !constrained)
215+
assert.Equal(t, broadest, key)
216+
}
217+
145218
func TestTypeListKeyAllocations(t *testing.T) { //nolint:paralleltest
146219
if race.Enabled {
147220
t.Skip("race instrumentation changes hashing allocations")

0 commit comments

Comments
 (0)