Skip to content

Commit aa81492

Browse files
ahejlsbergahejlsberg
authored
Dense link stores (#64711)
1 parent 2d8450f commit aa81492

4 files changed

Lines changed: 120 additions & 66 deletions

File tree

‎tsc/internal/ast/utilities.go‎

Lines changed: 51 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,8 +15,10 @@ import (
1515
// Atomic ids
1616

1717
var (
18-
nextNodeId atomic.Uint64
19-
nextSymbolId atomic.Uint64
18+
nextNodeId atomic.Uint64
19+
nextSymbolId atomic.Uint64
20+
nextNodeBlockId atomic.Uint64
21+
nextSymbolBlockId atomic.Uint64
2022
)
2123

2224
func GetNodeId(node *Node) NodeId {
@@ -43,6 +45,53 @@ func GetSymbolId(symbol *Symbol) SymbolId {
4345
return SymbolId(id)
4446
}
4547

48+
const (
49+
BlockIdOffset = 0x1_0000_0000_0000
50+
BlockIdSize = core.LinkPageSize
51+
)
52+
53+
type NodeIdGenerator struct {
54+
nextId uint64
55+
lastId uint64
56+
}
57+
58+
func (a *NodeIdGenerator) GetNodeId(node *Node) NodeId {
59+
id := node.id.Load()
60+
if id == 0 {
61+
if a.nextId == a.lastId {
62+
a.nextId = nextNodeBlockId.Add(BlockIdSize) - BlockIdSize
63+
a.lastId = a.nextId + BlockIdSize
64+
}
65+
id = a.nextId + BlockIdOffset
66+
a.nextId++
67+
if !node.id.CompareAndSwap(0, id) {
68+
id = node.id.Load()
69+
}
70+
}
71+
return NodeId(id)
72+
}
73+
74+
type SymbolIdGenerator struct {
75+
nextId uint64
76+
lastId uint64
77+
}
78+
79+
func (a *SymbolIdGenerator) GetSymbolId(symbol *Symbol) SymbolId {
80+
id := symbol.id.Load()
81+
if id == 0 {
82+
if a.nextId == a.lastId {
83+
a.nextId = nextSymbolBlockId.Add(BlockIdSize) - BlockIdSize
84+
a.lastId = a.nextId + BlockIdSize
85+
}
86+
id = a.nextId + BlockIdOffset
87+
a.nextId++
88+
if !symbol.id.CompareAndSwap(0, id) {
89+
id = symbol.id.Load()
90+
}
91+
}
92+
return SymbolId(id)
93+
}
94+
4695
func GetSymbolTable(data *SymbolTable) SymbolTable {
4796
if *data == nil {
4897
*data = make(SymbolTable)

‎tsc/internal/checker/checker.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -684,7 +684,7 @@ type Checker struct {
684684
jsxElementLinks core.LinkStore[*ast.Node, JsxElementLinks]
685685
computedNameLinks core.LinkStore[*ast.Node, ComputedNameNodeLinks]
686686
symbolReferenceLinks core.LinkStore[*ast.Symbol, SymbolReferenceLinks]
687-
valueSymbolLinks symbolArenaLinkStore[ValueSymbolLinks]
687+
valueSymbolLinks symbolLinkStore[ValueSymbolLinks]
688688
mappedSymbolLinks core.LinkStore[*ast.Symbol, MappedSymbolLinks]
689689
deferredSymbolLinks core.LinkStore[*ast.Symbol, DeferredSymbolLinks]
690690
aliasSymbolLinks core.LinkStore[*ast.Symbol, AliasSymbolLinks]

‎tsc/internal/checker/links.go‎

Lines changed: 37 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -5,46 +5,62 @@ import (
55
"github.com/microsoft/TypeScript/tsc/internal/core"
66
)
77

8-
// nodeLinkStore is a links store keyed by node references. Values are stored directly
9-
// in the pages of the store which is suitable for values where sizeof(V) is small.
8+
// When possible, nodeLinkStore and symbolLinkStore store Node and Symbol links in an efficient and densely
9+
// packed paged array store. When a Node or Symbol has not yet been assigned an ID, the store provides one
10+
// from a generator that produces sequences of IDs in a reserved range of the ID space. The generator grabs
11+
// chunks of 256 IDs from a central atomic counter, ensuring that each block of 256 IDs is consecutive and
12+
// causing Node or Symbol links to be densely packed within a single page.
13+
14+
const maxPageLinkCount = 0x100_0000 // 16M
15+
1016
type nodeLinkStore[V any] struct {
11-
store core.PagedLinkStore[V]
17+
gen ast.NodeIdGenerator
18+
links core.LinkStore[uint64, V]
19+
pages core.PagedLinkStore[V]
1220
}
1321

1422
func (s *nodeLinkStore[V]) Get(node *ast.Node) *V {
15-
return s.store.Get(uint64(ast.GetNodeId(node)))
23+
id := uint64(s.gen.GetNodeId(node))
24+
if id >= ast.BlockIdOffset && id < ast.BlockIdOffset+maxPageLinkCount {
25+
return s.pages.Get(id - ast.BlockIdOffset)
26+
}
27+
return s.links.Get(id)
1628
}
1729

1830
func (s *nodeLinkStore[V]) Has(node *ast.Node) bool {
19-
return s.store.Has(uint64(ast.GetNodeId(node)))
31+
return s.TryGet(node) != nil
2032
}
2133

2234
func (s *nodeLinkStore[V]) TryGet(node *ast.Node) *V {
23-
return s.store.TryGet(uint64(ast.GetNodeId(node)))
35+
id := uint64(s.gen.GetNodeId(node))
36+
if id >= ast.BlockIdOffset && id < ast.BlockIdOffset+maxPageLinkCount {
37+
return s.pages.TryGet(id - ast.BlockIdOffset)
38+
}
39+
return s.links.TryGet(id)
2440
}
2541

26-
// symbolArenaLinkStore is a links store keyed by symbol references. Values are stored
27-
// indirectly in an arena which is suitable for values where sizeof(V) is larger.
28-
type symbolArenaLinkStore[V any] struct {
29-
store core.PagedLinkStore[*V]
30-
arena core.Arena[V]
42+
type symbolLinkStore[V any] struct {
43+
gen ast.SymbolIdGenerator
44+
links core.LinkStore[uint64, V]
45+
pages core.PagedLinkStore[V]
3146
}
3247

33-
func (s *symbolArenaLinkStore[V]) Get(symbol *ast.Symbol) *V {
34-
link := s.store.Get(uint64(ast.GetSymbolId(symbol)))
35-
if *link == nil {
36-
*link = s.arena.New()
48+
func (s *symbolLinkStore[V]) Get(symbol *ast.Symbol) *V {
49+
id := uint64(s.gen.GetSymbolId(symbol))
50+
if id >= ast.BlockIdOffset && id < ast.BlockIdOffset+maxPageLinkCount {
51+
return s.pages.Get(id - ast.BlockIdOffset)
3752
}
38-
return *link
53+
return s.links.Get(id)
3954
}
4055

41-
func (s *symbolArenaLinkStore[V]) Has(symbol *ast.Symbol) bool {
56+
func (s *symbolLinkStore[V]) Has(symbol *ast.Symbol) bool {
4257
return s.TryGet(symbol) != nil
4358
}
4459

45-
func (s *symbolArenaLinkStore[V]) TryGet(symbol *ast.Symbol) *V {
46-
if link := s.store.TryGet(uint64(ast.GetSymbolId(symbol))); link != nil {
47-
return *link
60+
func (s *symbolLinkStore[V]) TryGet(symbol *ast.Symbol) *V {
61+
id := uint64(s.gen.GetSymbolId(symbol))
62+
if id >= ast.BlockIdOffset && id < ast.BlockIdOffset+maxPageLinkCount {
63+
return s.pages.TryGet(id - ast.BlockIdOffset)
4864
}
49-
return nil
65+
return s.links.TryGet(id)
5066
}

‎tsc/internal/core/linkstore.go‎

Lines changed: 31 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,8 @@
11
package core
22

3-
import "slices"
3+
import (
4+
"slices"
5+
)
46

57
// Links store
68

@@ -32,62 +34,49 @@ func (s *LinkStore[K, V]) TryGet(key K) *V {
3234
}
3335

3436
const (
35-
pageShift = 8
36-
pageSize = 1 << pageShift
37-
pageMask = pageSize - 1
38-
maxPageCount = 65536
37+
LinkPageShift = 8
38+
LinkPageSize = 1 << LinkPageShift
39+
LinkPageMask = LinkPageSize - 1
3940
)
4041

41-
// Implements a sparse-array-like structure for storing elements keyed by dense uint64 keys. Elements are
42-
// stored in fixed-size pages of 256 entries and an index of pages is maintained in an array for lower valued
43-
// page indices and a map for higher valued page indices.
42+
// PagedLinkStore implements a sparse-array-like structure for storing elements keyed by dense uint64 keys.
43+
// Elements are allocated in an area, element references are stored in fixed-size pages of 256 entries, and
44+
// an index of pages is maintained in a growable list.
45+
4446
type PagedLinkStore[V any] struct {
45-
pageMap map[uint64]*[pageSize]V // Page map for page indices above maxPageCount
46-
pageList []*[pageSize]V // Page table for page indices below maxPageCount
47+
pages []*[LinkPageSize]*V
48+
arena Arena[V]
4749
}
4850

4951
func (s *PagedLinkStore[V]) Get(key uint64) *V {
50-
var page *[pageSize]V
51-
pageIndex := key >> pageShift
52-
if pageIndex < maxPageCount {
53-
if int(pageIndex) >= len(s.pageList) {
54-
// Grow the length of the list to pageIndex+1
55-
s.pageList = slices.Grow(s.pageList, int(pageIndex)-len(s.pageList)+1)[:pageIndex+1]
56-
}
57-
page = s.pageList[pageIndex]
58-
if page == nil {
59-
page = new([pageSize]V)
60-
s.pageList[pageIndex] = page
61-
}
62-
} else {
63-
page = s.pageMap[pageIndex]
64-
if page == nil {
65-
page = new([pageSize]V)
66-
if s.pageMap == nil {
67-
s.pageMap = make(map[uint64]*[pageSize]V)
68-
}
69-
s.pageMap[pageIndex] = page
70-
}
52+
pageIndex := key >> LinkPageShift
53+
if int(pageIndex) >= len(s.pages) {
54+
// Grow the length of the list to pageIndex+1
55+
s.pages = slices.Grow(s.pages, int(pageIndex)-len(s.pages)+1)[:pageIndex+1]
56+
}
57+
page := s.pages[pageIndex]
58+
if page == nil {
59+
page = new([LinkPageSize]*V)
60+
s.pages[pageIndex] = page
7161
}
72-
return &page[key&pageMask]
62+
link := page[key&LinkPageMask]
63+
if link == nil {
64+
link = s.arena.New()
65+
page[key&LinkPageMask] = link
66+
}
67+
return link
7368
}
7469

7570
func (s *PagedLinkStore[V]) Has(key uint64) bool {
7671
return s.TryGet(key) != nil
7772
}
7873

7974
func (s *PagedLinkStore[V]) TryGet(key uint64) *V {
80-
var page *[pageSize]V
81-
pageIndex := key >> pageShift
82-
if pageIndex < maxPageCount {
83-
if int(pageIndex) < len(s.pageList) {
84-
page = s.pageList[pageIndex]
75+
pageIndex := key >> LinkPageShift
76+
if int(pageIndex) < len(s.pages) {
77+
if page := s.pages[pageIndex]; page != nil {
78+
return page[key&LinkPageMask]
8579
}
86-
} else {
87-
page = s.pageMap[pageIndex]
88-
}
89-
if page != nil {
90-
return &page[key&pageMask]
9180
}
9281
return nil
9382
}

0 commit comments

Comments
 (0)