golang泛型在btree的应用与优化

近几个月更新的 golang1.18 支持了泛型,正好前两天看到了 google 官方的 golang-btree 更新了 v2,使用泛型generics代替了interface{},号称提升了 40% 的性能

Show me the code

https://github.com/google/btree

重新整理后的函数级别的完整的diff (原始MR点这里):


展开函数层面的完整diff
btree.go → btree_generic.go RENAMED
@@ -1,4 +1,4 @@
1
- // Copyright 2014 Google Inc.
2
  //
3
  // Licensed under the Apache License, Version 2.0 (the "License");
4
  // you may not use this file except in compliance with the License.
@@ -12,8 +12,13 @@
12
  // See the License for the specific language governing permissions and
13
  // limitations under the License.
14
 
15
- //go:build !go1.18
16
- // +build !go1.18
 
 
 
 
 
17
 
18
  // Package btree implements in-memory B-Trees of arbitrary degree.
19
  //
@@ -48,6 +53,11 @@
48
  // Its functions, therefore, exactly mirror those of
49
  // llrb.LLRB where possible. Unlike gollrb, though, we currently don't
50
  // support storing multiple equivalent values.
 
 
 
 
 
51
  package btree
52
 
53
  import (
@@ -72,32 +82,27 @@
72
  DefaultFreeListSize = 32
73
  )
74
 
75
- var (
76
- nilItems = make(items, 16)
77
- nilChildren = make(children, 16)
78
- )
79
-
80
- // FreeList represents a free list of btree nodes. By default each
81
  // BTree has its own FreeList, but multiple BTrees can share the same
82
- // FreeList.
83
  // Two Btrees using the same freelist are safe for concurrent write access.
84
- type FreeList struct {
85
  mu sync.Mutex
86
- freelist []*node
87
  }
88
 
89
- // NewFreeList creates a new free list.
90
  // size is the maximum size of the returned free list.
91
- func NewFreeList(size int) *FreeList {
92
- return &FreeList{freelist: make([]*node, 0, size)}
93
  }
94
 
95
- func (f *FreeList) newNode() (n *node) {
96
  f.mu.Lock()
97
  index := len(f.freelist) - 1
98
  if index < 0 {
99
  f.mu.Unlock()
100
- return new(node)
101
  }
102
  n = f.freelist[index]
103
  f.freelist[index] = nil
@@ -106,9 +111,7 @@
106
  return
107
  }
108
 
109
- // freeNode adds the given node to the list, returning true if it was added
110
- // and false if it was discarded.
111
- func (f *FreeList) freeNode(n *node) (out bool) {
112
  f.mu.Lock()
113
  if len(f.freelist) < cap(f.freelist) {
114
  f.freelist = append(f.freelist, n)
@@ -118,37 +121,55 @@
118
  return
119
  }
120
 
121
- // ItemIterator allows callers of Ascend* to iterate in-order over portions of
122
  // the tree. When this function returns false, iteration will stop and the
123
  // associated Ascend* function will immediately return.
124
- type ItemIterator func(i Item) bool
125
 
126
- // New creates a new B-Tree with the given degree.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
127
  //
128
- // New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items
129
  // and 2-4 children).
130
- func New(degree int) *BTree {
131
- return NewWithFreeList(degree, NewFreeList(DefaultFreeListSize))
 
 
132
  }
133
 
134
- // NewWithFreeList creates a new B-Tree that uses the given node free list.
135
- func NewWithFreeList(degree int, f *FreeList) *BTree {
136
  if degree <= 1 {
137
  panic("bad degree")
138
  }
139
- return &BTree{
140
  degree: degree,
141
- cow: ©OnWriteContext{freelist: f},
142
  }
143
  }
144
 
145
  // items stores items in a node.
146
- type items []Item
147
 
148
  // insertAt inserts a value into the given index, pushing all subsequent values
149
  // forward.
150
- func (s *items) insertAt(index int, item Item) {
151
- *s = append(*s, nil)
 
152
  if index < len(*s) {
153
  copy((*s)[index+1:], (*s)[index:])
154
  }
@@ -157,100 +178,61 @@
157
 
158
  // removeAt removes a value at a given index, pulling all subsequent values
159
  // back.
160
- func (s *items) removeAt(index int) Item {
161
  item := (*s)[index]
162
  copy((*s)[index:], (*s)[index+1:])
163
- (*s)[len(*s)-1] = nil
 
164
  *s = (*s)[:len(*s)-1]
165
  return item
166
  }
167
 
168
  // pop removes and returns the last element in the list.
169
- func (s *items) pop() (out Item) {
170
  index := len(*s) - 1
171
  out = (*s)[index]
172
- (*s)[index] = nil
 
173
  *s = (*s)[:index]
174
  return
175
  }
176
 
177
  // truncate truncates this instance at index so that it contains only the
178
  // first index items. index must be less than or equal to length.
179
- func (s *items) truncate(index int) {
180
- var toClear items
181
  *s, toClear = (*s)[:index], (*s)[index:]
182
- for len(toClear) > 0 {
183
- toClear = toClear[copy(toClear, nilItems):]
 
184
  }
185
  }
186
 
187
  // find returns the index where the given item should be inserted into this
188
  // list. 'found' is true if the item already exists in the list at the given
189
  // index.
190
- func (s items) find(item Item) (index int, found bool) {
191
  i := sort.Search(len(s), func(i int) bool {
192
- return item.Less(s[i])
193
  })
194
- if i > 0 && !s[i-1].Less(item) {
195
  return i - 1, true
196
  }
197
  return i, false
198
  }
199
 
200
- // children stores child nodes in a node.
201
- type children []*node
202
-
203
- // insertAt inserts a value into the given index, pushing all subsequent values
204
- // forward.
205
- func (s *children) insertAt(index int, n *node) {
206
- *s = append(*s, nil)
207
- if index < len(*s) {
208
- copy((*s)[index+1:], (*s)[index:])
209
- }
210
- (*s)[index] = n
211
- }
212
-
213
- // removeAt removes a value at a given index, pulling all subsequent values
214
- // back.
215
- func (s *children) removeAt(index int) *node {
216
- n := (*s)[index]
217
- copy((*s)[index:], (*s)[index+1:])
218
- (*s)[len(*s)-1] = nil
219
- *s = (*s)[:len(*s)-1]
220
- return n
221
- }
222
-
223
- // pop removes and returns the last element in the list.
224
- func (s *children) pop() (out *node) {
225
- index := len(*s) - 1
226
- out = (*s)[index]
227
- (*s)[index] = nil
228
- *s = (*s)[:index]
229
- return
230
- }
231
-
232
- // truncate truncates this instance at index so that it contains only the
233
- // first index children. index must be less than or equal to length.
234
- func (s *children) truncate(index int) {
235
- var toClear children
236
- *s, toClear = (*s)[:index], (*s)[index:]
237
- for len(toClear) > 0 {
238
- toClear = toClear[copy(toClear, nilChildren):]
239
- }
240
- }
241
-
242
  // node is an internal node in a tree.
243
  //
244
  // It must at all times maintain the invariant that either
245
  // * len(children) == 0, len(items) unconstrained
246
  // * len(children) == len(items) + 1
247
- type node struct {
248
- items items
249
- children children
250
- cow *copyOnWriteContext
251
  }
252
 
253
- func (n *node) mutableFor(cow *copyOnWriteContext) *node {
254
  if n.cow == cow {
255
  return n
256
  }
@@ -258,20 +240,20 @@
258
  if cap(out.items) >= len(n.items) {
259
  out.items = out.items[:len(n.items)]
260
  } else {
261
- out.items = make(items, len(n.items), cap(n.items))
262
  }
263
  copy(out.items, n.items)
264
  // Copy children
265
  if cap(out.children) >= len(n.children) {
266
  out.children = out.children[:len(n.children)]
267
  } else {
268
- out.children = make(children, len(n.children), cap(n.children))
269
  }
270
  copy(out.children, n.children)
271
  return out
272
  }
273
 
274
- func (n *node) mutableChild(i int) *node {
275
  c := n.children[i].mutableFor(n.cow)
276
  n.children[i] = c
277
  return c
@@ -280,7 +262,7 @@
280
  // split splits the given node at the given index. The current node shrinks,
281
  // and this function returns the item that existed at that index and a new node
282
  // containing all items/children after it.
283
- func (n *node) split(i int) (Item, *node) {
284
  item := n.items[i]
285
  next := n.cow.newNode()
286
  next.items = append(next.items, n.items[i+1:]...)
@@ -294,7 +276,7 @@
294
 
295
  // maybeSplitChild checks if a child should be split, and if so splits it.
296
  // Returns whether or not a split occurred.
297
- func (n *node) maybeSplitChild(i, maxItems int) bool {
298
  if len(n.children[i].items) < maxItems {
299
  return false
300
  }
@@ -308,70 +290,70 @@
308
  // insert inserts an item into the subtree rooted at this node, making sure
309
  // no nodes in the subtree exceed maxItems items. Should an equivalent item be
310
  // be found/replaced by insert, it will be returned.
311
- func (n *node) insert(item Item, maxItems int) Item {
312
- i, found := n.items.find(item)
313
  if found {
314
  out := n.items[i]
315
  n.items[i] = item
316
- return out
317
  }
318
  if len(n.children) == 0 {
319
  n.items.insertAt(i, item)
320
- return nil
321
  }
322
  if n.maybeSplitChild(i, maxItems) {
323
  inTree := n.items[i]
324
  switch {
325
- case item.Less(inTree):
326
  // no change, we want first split node
327
- case inTree.Less(item):
328
  i++ // we want second split node
329
  default:
330
  out := n.items[i]
331
  n.items[i] = item
332
- return out
333
  }
334
  }
335
  return n.mutableChild(i).insert(item, maxItems)
336
  }
337
 
338
  // get finds the given key in the subtree and returns it.
339
- func (n *node) get(key Item) Item {
340
- i, found := n.items.find(key)
341
  if found {
342
- return n.items[i]
343
  } else if len(n.children) > 0 {
344
  return n.children[i].get(key)
345
  }
346
- return nil
347
  }
348
 
349
  // min returns the first item in the subtree.
350
- func min(n *node) Item {
351
  if n == nil {
352
- return nil
353
  }
354
  for len(n.children) > 0 {
355
  n = n.children[0]
356
  }
357
  if len(n.items) == 0 {
358
- return nil
359
  }
360
- return n.items[0]
361
  }
362
 
363
  // max returns the last item in the subtree.
364
- func max(n *node) Item {
365
  if n == nil {
366
- return nil
367
  }
368
  for len(n.children) > 0 {
369
  n = n.children[len(n.children)-1]
370
  }
371
  if len(n.items) == 0 {
372
- return nil
373
  }
374
- return n.items[len(n.items)-1]
375
  }
376
 
377
  // toRemove details what item to remove in a node.remove call.
@@ -384,27 +366,27 @@
384
  )
385
 
386
  // remove removes an item from the subtree rooted at this node.
387
- func (n *node) remove(item Item, minItems int, typ toRemove) Item {
388
  var i int
389
  var found bool
390
  switch typ {
391
  case removeMax:
392
  if len(n.children) == 0 {
393
- return n.items.pop()
394
  }
395
  i = len(n.items)
396
  case removeMin:
397
  if len(n.children) == 0 {
398
- return n.items.removeAt(0)
399
  }
400
  i = 0
401
  case removeItem:
402
- i, found = n.items.find(item)
403
  if len(n.children) == 0 {
404
  if found {
405
- return n.items.removeAt(i)
406
  }
407
- return nil
408
  }
409
  default:
410
  panic("invalid type")
@@ -424,8 +406,9 @@
424
  // We use our special-case 'remove' call with typ=maxItem to pull the
425
  // predecessor of item i (the rightmost leaf of our immediate left child)
426
  // and set it into where we pulled the item from.
427
- n.items[i] = child.remove(nil, minItems, removeMax)
428
- return out
 
429
  }
430
  // Final recursive call. Once we're here, we know that the item isn't in this
431
  // node and that the child is big enough to remove from.
@@ -451,7 +434,7 @@
451
  // We then simply redo our remove call, and the second time (regardless of
452
  // whether we're in case 1 or 2), we'll have enough items and can guarantee
453
  // that we hit case A.
454
- func (n *node) growChildAndRemove(i int, item Item, minItems int, typ toRemove) Item {
455
  if i > 0 && len(n.children[i-1].items) > minItems {
456
  // Steal from left child
457
  child := n.mutableChild(i)
@@ -495,6 +478,18 @@
495
  ascend = direction(+1)
496
  )
497
 
 
 
 
 
 
 
 
 
 
 
 
 
498
  // iterate provides a simple method for iterating over elements in the tree.
499
  //
500
  // When ascending, the 'start' should be less than 'stop' and when descending,
@@ -502,13 +497,13 @@
502
  // will force the iterator to include the first item when it equals 'start',
503
  // thus creating a "greaterOrEqual" or "lessThanEqual" rather than just a
504
  // "greaterThan" or "lessThan" queries.
505
- func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit bool, iter ItemIterator) (bool, bool) {
506
  var ok, found bool
507
  var index int
508
  switch dir {
509
  case ascend:
510
- if start != nil {
511
- index, _ = n.items.find(start)
512
  }
513
  for i := index; i < len(n.items); i++ {
514
  if len(n.children) > 0 {
@@ -516,12 +511,12 @@
516
  return hit, false
517
  }
518
  }
519
- if !includeStart && !hit && start != nil && !start.Less(n.items[i]) {
520
  hit = true
521
  continue
522
  }
523
  hit = true
524
- if stop != nil && !n.items[i].Less(stop) {
525
  return hit, false
526
  }
527
  if !iter(n.items[i]) {
@@ -534,8 +529,8 @@
534
  }
535
  }
536
  case descend:
537
- if start != nil {
538
- index, found = n.items.find(start)
539
  if !found {
540
  index = index - 1
541
  }
@@ -543,8 +538,8 @@
543
  index = len(n.items) - 1
544
  }
545
  for i := index; i >= 0; i-- {
546
- if start != nil && !n.items[i].Less(start) {
547
- if !includeStart || hit || start.Less(n.items[i]) {
548
  continue
549
  }
550
  }
@@ -553,7 +548,7 @@
553
  return hit, false
554
  }
555
  }
556
- if stop != nil && !stop.Less(n.items[i]) {
557
  return hit, false // continue
558
  }
559
  hit = true
@@ -570,28 +565,32 @@
570
  return hit, true
571
  }
572
 
573
- // Used for testing/debugging purposes.
574
- func (n *node) print(w io.Writer, level int) {
575
  fmt.Fprintf(w, "%sNODE:%v\n", strings.Repeat(" ", level), n.items)
576
  for _, c := range n.children {
577
  c.print(w, level+1)
578
  }
579
  }
580
 
581
- // BTree is an implementation of a B-Tree.
582
  //
583
- // BTree stores Item instances in an ordered structure, allowing easy insertion,
584
  // removal, and iteration.
585
  //
586
  // Write operations are not safe for concurrent mutation by multiple
587
  // goroutines, but Read operations are.
588
- type BTree struct {
589
  degree int
590
  length int
591
- root *node
592
- cow *copyOnWriteContext
593
  }
594
 
 
 
 
 
595
  // copyOnWriteContext pointers determine node ownership... a tree with a write
596
  // context equivalent to a node's write context is allowed to modify that node.
597
  // A tree whose write context does not match a node's is not allowed to modify
@@ -606,8 +605,9 @@
606
  // tree's context, that node is modifiable in place. Children of that node may
607
  // not share context, but before we descend into them, we'll make a mutable
608
  // copy.
609
- type copyOnWriteContext struct {
610
- freelist *FreeList
 
611
  }
612
 
613
  // Clone clones the btree, lazily. Clone should not be called concurrently,
@@ -621,7 +621,7 @@
621
  // will initially experience minor slow-downs caused by additional allocs and
622
  // copies due to the aforementioned copy-on-write logic, but should converge to
623
  // the original performance characteristics of the original tree.
624
- func (t *BTree) Clone() (t2 *BTree) {
625
  // Create two entirely new copy-on-write contexts.
626
  // This operation effectively creates three trees:
627
  // the original, shared nodes (old b.cow)
@@ -635,17 +635,17 @@
635
  }
636
 
637
  // maxItems returns the max number of items to allow per node.
638
- func (t *BTree) maxItems() int {
639
  return t.degree*2 - 1
640
  }
641
 
642
  // minItems returns the min number of items to allow per node (ignored for the
643
  // root node).
644
- func (t *BTree) minItems() int {
645
  return t.degree - 1
646
  }
647
 
648
- func (c *copyOnWriteContext) newNode() (n *node) {
649
  n = c.freelist.newNode()
650
  n.cow = c
651
  return
@@ -662,7 +662,7 @@
662
  // freeNode frees a node within a given COW context, if it's owned by that
663
  // context. It returns what happened to the node (see freeType const
664
  // documentation).
665
- func (c *copyOnWriteContext) freeNode(n *node) freeType {
666
  if n.cow == c {
667
  // clear to allow GC
668
  n.items.truncate(0)
@@ -679,19 +679,16 @@
679
  }
680
 
681
  // ReplaceOrInsert adds the given item to the tree. If an item in the tree
682
- // already equals the given one, it is removed from the tree and returned.
683
- // Otherwise, nil is returned.
684
  //
685
  // nil cannot be added to the tree (will panic).
686
- func (t *BTree) ReplaceOrInsert(item Item) Item {
687
- if item == nil {
688
- panic("nil item being added to BTree")
689
- }
690
  if t.root == nil {
691
  t.root = t.cow.newNode()
692
  t.root.items = append(t.root.items, item)
693
  t.length++
694
- return nil
695
  } else {
696
  t.root = t.root.mutableFor(t.cow)
697
  if len(t.root.items) >= t.maxItems() {
@@ -702,146 +699,149 @@
702
  t.root.children = append(t.root.children, oldroot, second)
703
  }
704
  }
705
- out := t.root.insert(item, t.maxItems())
706
- if out == nil {
707
  t.length++
708
  }
709
- return out
710
  }
711
 
712
  // Delete removes an item equal to the passed in item from the tree, returning
713
- // it. If no such item exists, returns nil.
714
- func (t *BTree) Delete(item Item) Item {
715
  return t.deleteItem(item, removeItem)
716
  }
717
 
718
  // DeleteMin removes the smallest item in the tree and returns it.
719
- // If no such item exists, returns nil.
720
- func (t *BTree) DeleteMin() Item {
721
- return t.deleteItem(nil, removeMin)
 
722
  }
723
 
724
  // DeleteMax removes the largest item in the tree and returns it.
725
- // If no such item exists, returns nil.
726
- func (t *BTree) DeleteMax() Item {
727
- return t.deleteItem(nil, removeMax)
 
728
  }
729
 
730
- func (t *BTree) deleteItem(item Item, typ toRemove) Item {
731
  if t.root == nil || len(t.root.items) == 0 {
732
- return nil
733
  }
734
  t.root = t.root.mutableFor(t.cow)
735
- out := t.root.remove(item, t.minItems(), typ)
736
  if len(t.root.items) == 0 && len(t.root.children) > 0 {
737
  oldroot := t.root
738
  t.root = t.root.children[0]
739
  t.cow.freeNode(oldroot)
740
  }
741
- if out != nil {
742
  t.length--
743
  }
744
- return out
745
  }
746
 
747
  // AscendRange calls the iterator for every value in the tree within the range
748
  // [greaterOrEqual, lessThan), until iterator returns false.
749
- func (t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator) {
750
  if t.root == nil {
751
  return
752
  }
753
- t.root.iterate(ascend, greaterOrEqual, lessThan, true, false, iterator)
754
  }
755
 
756
  // AscendLessThan calls the iterator for every value in the tree within the range
757
  // [first, pivot), until iterator returns false.
758
- func (t *BTree) AscendLessThan(pivot Item, iterator ItemIterator) {
759
  if t.root == nil {
760
  return
761
  }
762
- t.root.iterate(ascend, nil, pivot, false, false, iterator)
763
  }
764
 
765
  // AscendGreaterOrEqual calls the iterator for every value in the tree within
766
  // the range [pivot, last], until iterator returns false.
767
- func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator) {
768
  if t.root == nil {
769
  return
770
  }
771
- t.root.iterate(ascend, pivot, nil, true, false, iterator)
772
  }
773
 
774
  // Ascend calls the iterator for every value in the tree within the range
775
  // [first, last], until iterator returns false.
776
- func (t *BTree) Ascend(iterator ItemIterator) {
777
  if t.root == nil {
778
  return
779
  }
780
- t.root.iterate(ascend, nil, nil, false, false, iterator)
781
  }
782
 
783
  // DescendRange calls the iterator for every value in the tree within the range
784
  // [lessOrEqual, greaterThan), until iterator returns false.
785
- func (t *BTree) DescendRange(lessOrEqual, greaterThan Item, iterator ItemIterator) {
786
  if t.root == nil {
787
  return
788
  }
789
- t.root.iterate(descend, lessOrEqual, greaterThan, true, false, iterator)
790
  }
791
 
792
  // DescendLessOrEqual calls the iterator for every value in the tree within the range
793
  // [pivot, first], until iterator returns false.
794
- func (t *BTree) DescendLessOrEqual(pivot Item, iterator ItemIterator) {
795
  if t.root == nil {
796
  return
797
  }
798
- t.root.iterate(descend, pivot, nil, true, false, iterator)
799
  }
800
 
801
  // DescendGreaterThan calls the iterator for every value in the tree within
802
  // the range [last, pivot), until iterator returns false.
803
- func (t *BTree) DescendGreaterThan(pivot Item, iterator ItemIterator) {
804
  if t.root == nil {
805
  return
806
  }
807
- t.root.iterate(descend, nil, pivot, false, false, iterator)
808
  }
809
 
810
  // Descend calls the iterator for every value in the tree within the range
811
  // [last, first], until iterator returns false.
812
- func (t *BTree) Descend(iterator ItemIterator) {
813
  if t.root == nil {
814
  return
815
  }
816
- t.root.iterate(descend, nil, nil, false, false, iterator)
817
  }
818
 
819
- // Get looks for the key item in the tree, returning it. It returns nil if
820
- // unable to find that item.
821
- func (t *BTree) Get(key Item) Item {
822
  if t.root == nil {
823
- return nil
824
  }
825
  return t.root.get(key)
826
  }
827
 
828
- // Min returns the smallest item in the tree, or nil if the tree is empty.
829
- func (t *BTree) Min() Item {
830
  return min(t.root)
831
  }
832
 
833
- // Max returns the largest item in the tree, or nil if the tree is empty.
834
- func (t *BTree) Max() Item {
835
  return max(t.root)
836
  }
837
 
838
  // Has returns true if the given key is in the tree.
839
- func (t *BTree) Has(key Item) bool {
840
- return t.Get(key) != nil
 
841
  }
842
 
843
  // Len returns the number of items currently in the tree.
844
- func (t *BTree) Len() int {
845
  return t.length
846
  }
847
 
@@ -865,7 +865,7 @@
865
  // O(tree size): when all nodes are owned by another tree, all nodes are
866
  // iterated over looking for nodes to add to the freelist, and due to
867
  // ownership, none are.
868
- func (t *BTree) Clear(addNodesToFreelist bool) {
869
  if t.root != nil && addNodesToFreelist {
870
  t.root.reset(t.cow)
871
  }
@@ -875,7 +875,7 @@
875
  // reset returns a subtree to the freelist. It breaks out immediately if the
876
  // freelist is full, since the only benefit of iterating is to fill that
877
  // freelist up. Returns true if parent reset call should continue.
878
- func (n *node) reset(c *copyOnWriteContext) bool {
879
  for _, child := range n.children {
880
  if !child.reset(c) {
881
  return false
@@ -891,3 +891,193 @@
891
  func (a Int) Less(b Item) bool {
892
  return a < b.(Int)
893
  }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
+ // Copyright 2014-2022 Google Inc.
2
  //
3
  // Licensed under the Apache License, Version 2.0 (the "License");
4
  // you may not use this file except in compliance with the License.
12
  // See the License for the specific language governing permissions and
13
  // limitations under the License.
14
 
15
+ //go:build go1.18
16
+ // +build go1.18
17
+
18
+ // In Go 1.18 and beyond, a BTreeG generic is created, and BTree is a specific
19
+ // instantiation of that generic for the Item interface, with a backwards-
20
+ // compatible API. Before go1.18, generics are not supported,
21
+ // and BTree is just an implementation based around the Item interface.
22
 
23
  // Package btree implements in-memory B-Trees of arbitrary degree.
24
  //
53
  // Its functions, therefore, exactly mirror those of
54
  // llrb.LLRB where possible. Unlike gollrb, though, we currently don't
55
  // support storing multiple equivalent values.
56
+ //
57
+ // There are two implementations; those suffixed with 'G' are generics, usable
58
+ // for any type, and require a passed-in "less" function to define their ordering.
59
+ // Those without this prefix are specific to the 'Item' interface, and use
60
+ // its 'Less' function for ordering.
61
  package btree
62
 
63
  import (
82
  DefaultFreeListSize = 32
83
  )
84
 
85
+ // FreeListG represents a free list of btree nodes. By default each
 
 
 
 
 
86
  // BTree has its own FreeList, but multiple BTrees can share the same
87
+ // FreeList, in particular when they're created with Clone.
88
  // Two Btrees using the same freelist are safe for concurrent write access.
89
+ type FreeListG[T any] struct {
90
  mu sync.Mutex
91
+ freelist []*node[T]
92
  }
93
 
94
+ // NewFreeListG creates a new free list.
95
  // size is the maximum size of the returned free list.
96
+ func NewFreeListG[T any](size int) *FreeListG[T] {
97
+ return &FreeListG[T]{freelist: make([]*node[T], 0, size)}
98
  }
99
 
100
+ func (f *FreeListG[T]) newNode() (n *node[T]) {
101
  f.mu.Lock()
102
  index := len(f.freelist) - 1
103
  if index < 0 {
104
  f.mu.Unlock()
105
+ return new(node[T])
106
  }
107
  n = f.freelist[index]
108
  f.freelist[index] = nil
111
  return
112
  }
113
 
114
+ func (f *FreeListG[T]) freeNode(n *node[T]) (out bool) {
 
 
115
  f.mu.Lock()
116
  if len(f.freelist) < cap(f.freelist) {
117
  f.freelist = append(f.freelist, n)
121
  return
122
  }
123
 
124
+ // ItemIteratorG allows callers of {A/De}scend* to iterate in-order over portions of
125
  // the tree. When this function returns false, iteration will stop and the
126
  // associated Ascend* function will immediately return.
127
+ type ItemIteratorG[T any] func(item T) bool
128
 
129
+ // Ordered represents the set of types for which the '<' operator work.
130
+ type Ordered interface {
131
+ ~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~float32 | ~float64 | ~string
132
+ }
133
+
134
+ // Less[T] returns a default LessFunc that uses the '<' operator for types that support it.
135
+ func Less[T Ordered]() LessFunc[T] {
136
+ return func(a, b T) bool { return a < b }
137
+ }
138
+
139
+ // NewOrderedG creates a new B-Tree for ordered types.
140
+ func NewOrderedG[T Ordered](degree int) *BTreeG[T] {
141
+ return NewG[T](degree, Less[T]())
142
+ }
143
+
144
+ // NewG creates a new B-Tree with the given degree.
145
  //
146
+ // NewG(2), for example, will create a 2-3-4 tree (each node contains 1-3 items
147
  // and 2-4 children).
148
+ //
149
+ // The passed-in LessFunc determines how objects of type T are ordered.
150
+ func NewG[T any](degree int, less LessFunc[T]) *BTreeG[T] {
151
+ return NewWithFreeListG(degree, less, NewFreeListG[T](DefaultFreeListSize))
152
  }
153
 
154
+ // NewWithFreeListG creates a new B-Tree that uses the given node free list.
155
+ func NewWithFreeListG[T any](degree int, less LessFunc[T], f *FreeListG[T]) *BTreeG[T] {
156
  if degree <= 1 {
157
  panic("bad degree")
158
  }
159
+ return &BTreeG[T]{
160
  degree: degree,
161
+ cow: ©OnWriteContext[T]{freelist: f, less: less},
162
  }
163
  }
164
 
165
  // items stores items in a node.
166
+ type items[T any] []T
167
 
168
  // insertAt inserts a value into the given index, pushing all subsequent values
169
  // forward.
170
+ func (s *items[T]) insertAt(index int, item T) {
171
+ var zero T
172
+ *s = append(*s, zero)
173
  if index < len(*s) {
174
  copy((*s)[index+1:], (*s)[index:])
175
  }
178
 
179
  // removeAt removes a value at a given index, pulling all subsequent values
180
  // back.
181
+ func (s *items[T]) removeAt(index int) T {
182
  item := (*s)[index]
183
  copy((*s)[index:], (*s)[index+1:])
184
+ var zero T
185
+ (*s)[len(*s)-1] = zero
186
  *s = (*s)[:len(*s)-1]
187
  return item
188
  }
189
 
190
  // pop removes and returns the last element in the list.
191
+ func (s *items[T]) pop() (out T) {
192
  index := len(*s) - 1
193
  out = (*s)[index]
194
+ var zero T
195
+ (*s)[index] = zero
196
  *s = (*s)[:index]
197
  return
198
  }
199
 
200
  // truncate truncates this instance at index so that it contains only the
201
  // first index items. index must be less than or equal to length.
202
+ func (s *items[T]) truncate(index int) {
203
+ var toClear items[T]
204
  *s, toClear = (*s)[:index], (*s)[index:]
205
+ var zero T
206
+ for i := 0; i < len(toClear); i++ {
207
+ toClear[i] = zero
208
  }
209
  }
210
 
211
  // find returns the index where the given item should be inserted into this
212
  // list. 'found' is true if the item already exists in the list at the given
213
  // index.
214
+ func (s items[T]) find(item T, less func(T, T) bool) (index int, found bool) {
215
  i := sort.Search(len(s), func(i int) bool {
216
+ return less(item, s[i])
217
  })
218
+ if i > 0 && !less(s[i-1], item) {
219
  return i - 1, true
220
  }
221
  return i, false
222
  }
223
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
224
  // node is an internal node in a tree.
225
  //
226
  // It must at all times maintain the invariant that either
227
  // * len(children) == 0, len(items) unconstrained
228
  // * len(children) == len(items) + 1
229
+ type node[T any] struct {
230
+ items items[T]
231
+ children items[*node[T]]
232
+ cow *copyOnWriteContext[T]
233
  }
234
 
235
+ func (n *node[T]) mutableFor(cow *copyOnWriteContext[T]) *node[T] {
236
  if n.cow == cow {
237
  return n
238
  }
240
  if cap(out.items) >= len(n.items) {
241
  out.items = out.items[:len(n.items)]
242
  } else {
243
+ out.items = make(items[T], len(n.items), cap(n.items))
244
  }
245
  copy(out.items, n.items)
246
  // Copy children
247
  if cap(out.children) >= len(n.children) {
248
  out.children = out.children[:len(n.children)]
249
  } else {
250
+ out.children = make(items[*node[T]], len(n.children), cap(n.children))
251
  }
252
  copy(out.children, n.children)
253
  return out
254
  }
255
 
256
+ func (n *node[T]) mutableChild(i int) *node[T] {
257
  c := n.children[i].mutableFor(n.cow)
258
  n.children[i] = c
259
  return c
262
  // split splits the given node at the given index. The current node shrinks,
263
  // and this function returns the item that existed at that index and a new node
264
  // containing all items/children after it.
265
+ func (n *node[T]) split(i int) (T, *node[T]) {
266
  item := n.items[i]
267
  next := n.cow.newNode()
268
  next.items = append(next.items, n.items[i+1:]...)
276
 
277
  // maybeSplitChild checks if a child should be split, and if so splits it.
278
  // Returns whether or not a split occurred.
279
+ func (n *node[T]) maybeSplitChild(i, maxItems int) bool {
280
  if len(n.children[i].items) < maxItems {
281
  return false
282
  }
290
  // insert inserts an item into the subtree rooted at this node, making sure
291
  // no nodes in the subtree exceed maxItems items. Should an equivalent item be
292
  // be found/replaced by insert, it will be returned.
293
+ func (n *node[T]) insert(item T, maxItems int) (_ T, _ bool) {
294
+ i, found := n.items.find(item, n.cow.less)
295
  if found {
296
  out := n.items[i]
297
  n.items[i] = item
298
+ return out, true
299
  }
300
  if len(n.children) == 0 {
301
  n.items.insertAt(i, item)
302
+ return
303
  }
304
  if n.maybeSplitChild(i, maxItems) {
305
  inTree := n.items[i]
306
  switch {
307
+ case n.cow.less(item, inTree):
308
  // no change, we want first split node
309
+ case n.cow.less(inTree, item):
310
  i++ // we want second split node
311
  default:
312
  out := n.items[i]
313
  n.items[i] = item
314
+ return out, true
315
  }
316
  }
317
  return n.mutableChild(i).insert(item, maxItems)
318
  }
319
 
320
  // get finds the given key in the subtree and returns it.
321
+ func (n *node[T]) get(key T) (_ T, _ bool) {
322
+ i, found := n.items.find(key, n.cow.less)
323
  if found {
324
+ return n.items[i], true
325
  } else if len(n.children) > 0 {
326
  return n.children[i].get(key)
327
  }
328
+ return
329
  }
330
 
331
  // min returns the first item in the subtree.
332
+ func min[T any](n *node[T]) (_ T, found bool) {
333
  if n == nil {
334
+ return
335
  }
336
  for len(n.children) > 0 {
337
  n = n.children[0]
338
  }
339
  if len(n.items) == 0 {
340
+ return
341
  }
342
+ return n.items[0], true
343
  }
344
 
345
  // max returns the last item in the subtree.
346
+ func max[T any](n *node[T]) (_ T, found bool) {
347
  if n == nil {
348
+ return
349
  }
350
  for len(n.children) > 0 {
351
  n = n.children[len(n.children)-1]
352
  }
353
  if len(n.items) == 0 {
354
+ return
355
  }
356
+ return n.items[len(n.items)-1], true
357
  }
358
 
359
  // toRemove details what item to remove in a node.remove call.
366
  )
367
 
368
  // remove removes an item from the subtree rooted at this node.
369
+ func (n *node[T]) remove(item T, minItems int, typ toRemove) (_ T, _ bool) {
370
  var i int
371
  var found bool
372
  switch typ {
373
  case removeMax:
374
  if len(n.children) == 0 {
375
+ return n.items.pop(), true
376
  }
377
  i = len(n.items)
378
  case removeMin:
379
  if len(n.children) == 0 {
380
+ return n.items.removeAt(0), true
381
  }
382
  i = 0
383
  case removeItem:
384
+ i, found = n.items.find(item, n.cow.less)
385
  if len(n.children) == 0 {
386
  if found {
387
+ return n.items.removeAt(i), true
388
  }
389
+ return
390
  }
391
  default:
392
  panic("invalid type")
406
  // We use our special-case 'remove' call with typ=maxItem to pull the
407
  // predecessor of item i (the rightmost leaf of our immediate left child)
408
  // and set it into where we pulled the item from.
409
+ var zero T
410
+ n.items[i], _ = child.remove(zero, minItems, removeMax)
411
+ return out, true
412
  }
413
  // Final recursive call. Once we're here, we know that the item isn't in this
414
  // node and that the child is big enough to remove from.
434
  // We then simply redo our remove call, and the second time (regardless of
435
  // whether we're in case 1 or 2), we'll have enough items and can guarantee
436
  // that we hit case A.
437
+ func (n *node[T]) growChildAndRemove(i int, item T, minItems int, typ toRemove) (T, bool) {
438
  if i > 0 && len(n.children[i-1].items) > minItems {
439
  // Steal from left child
440
  child := n.mutableChild(i)
478
  ascend = direction(+1)
479
  )
480
 
481
+ type optionalItem[T any] struct {
482
+ item T
483
+ valid bool
484
+ }
485
+
486
+ func optional[T any](item T) optionalItem[T] {
487
+ return optionalItem[T]{item: item, valid: true}
488
+ }
489
+ func empty[T any]() optionalItem[T] {
490
+ return optionalItem[T]{}
491
+ }
492
+
493
  // iterate provides a simple method for iterating over elements in the tree.
494
  //
495
  // When ascending, the 'start' should be less than 'stop' and when descending,
497
  // will force the iterator to include the first item when it equals 'start',
498
  // thus creating a "greaterOrEqual" or "lessThanEqual" rather than just a
499
  // "greaterThan" or "lessThan" queries.
500
+ func (n *node[T]) iterate(dir direction, start, stop optionalItem[T], includeStart bool, hit bool, iter ItemIteratorG[T]) (bool, bool) {
501
  var ok, found bool
502
  var index int
503
  switch dir {
504
  case ascend:
505
+ if start.valid {
506
+ index, _ = n.items.find(start.item, n.cow.less)
507
  }
508
  for i := index; i < len(n.items); i++ {
509
  if len(n.children) > 0 {
511
  return hit, false
512
  }
513
  }
514
+ if !includeStart && !hit && start.valid && !n.cow.less(start.item, n.items[i]) {
515
  hit = true
516
  continue
517
  }
518
  hit = true
519
+ if stop.valid && !n.cow.less(n.items[i], stop.item) {
520
  return hit, false
521
  }
522
  if !iter(n.items[i]) {
529
  }
530
  }
531
  case descend:
532
+ if start.valid {
533
+ index, found = n.items.find(start.item, n.cow.less)
534
  if !found {
535
  index = index - 1
536
  }
538
  index = len(n.items) - 1
539
  }
540
  for i := index; i >= 0; i-- {
541
+ if start.valid && !n.cow.less(n.items[i], start.item) {
542
+ if !includeStart || hit || n.cow.less(start.item, n.items[i]) {
543
  continue
544
  }
545
  }
548
  return hit, false
549
  }
550
  }
551
+ if stop.valid && !n.cow.less(stop.item, n.items[i]) {
552
  return hit, false // continue
553
  }
554
  hit = true
565
  return hit, true
566
  }
567
 
568
+ // print is used for testing/debugging purposes.
569
+ func (n *node[T]) print(w io.Writer, level int) {
570
  fmt.Fprintf(w, "%sNODE:%v\n", strings.Repeat(" ", level), n.items)
571
  for _, c := range n.children {
572
  c.print(w, level+1)
573
  }
574
  }
575
 
576
+ // BTreeG is a generic implementation of a B-Tree.
577
  //
578
+ // BTreeG stores items of type T in an ordered structure, allowing easy insertion,
579
  // removal, and iteration.
580
  //
581
  // Write operations are not safe for concurrent mutation by multiple
582
  // goroutines, but Read operations are.
583
+ type BTreeG[T any] struct {
584
  degree int
585
  length int
586
+ root *node[T]
587
+ cow *copyOnWriteContext[T]
588
  }
589
 
590
+ // LessFunc[T] determines how to order a type 'T'. It should implement a strict
591
+ // ordering, and should return true if within that ordering, 'a' < 'b'.
592
+ type LessFunc[T any] func(a, b T) bool
593
+
594
  // copyOnWriteContext pointers determine node ownership... a tree with a write
595
  // context equivalent to a node's write context is allowed to modify that node.
596
  // A tree whose write context does not match a node's is not allowed to modify
605
  // tree's context, that node is modifiable in place. Children of that node may
606
  // not share context, but before we descend into them, we'll make a mutable
607
  // copy.
608
+ type copyOnWriteContext[T any] struct {
609
+ freelist *FreeListG[T]
610
+ less LessFunc[T]
611
  }
612
 
613
  // Clone clones the btree, lazily. Clone should not be called concurrently,
621
  // will initially experience minor slow-downs caused by additional allocs and
622
  // copies due to the aforementioned copy-on-write logic, but should converge to
623
  // the original performance characteristics of the original tree.
624
+ func (t *BTreeG[T]) Clone() (t2 *BTreeG[T]) {
625
  // Create two entirely new copy-on-write contexts.
626
  // This operation effectively creates three trees:
627
  // the original, shared nodes (old b.cow)
635
  }
636
 
637
  // maxItems returns the max number of items to allow per node.
638
+ func (t *BTreeG[T]) maxItems() int {
639
  return t.degree*2 - 1
640
  }
641
 
642
  // minItems returns the min number of items to allow per node (ignored for the
643
  // root node).
644
+ func (t *BTreeG[T]) minItems() int {
645
  return t.degree - 1
646
  }
647
 
648
+ func (c *copyOnWriteContext[T]) newNode() (n *node[T]) {
649
  n = c.freelist.newNode()
650
  n.cow = c
651
  return
662
  // freeNode frees a node within a given COW context, if it's owned by that
663
  // context. It returns what happened to the node (see freeType const
664
  // documentation).
665
+ func (c *copyOnWriteContext[T]) freeNode(n *node[T]) freeType {
666
  if n.cow == c {
667
  // clear to allow GC
668
  n.items.truncate(0)
679
  }
680
 
681
  // ReplaceOrInsert adds the given item to the tree. If an item in the tree
682
+ // already equals the given one, it is removed from the tree and returned,
683
+ // and the second return value is true. Otherwise, (zeroValue, false)
684
  //
685
  // nil cannot be added to the tree (will panic).
686
+ func (t *BTreeG[T]) ReplaceOrInsert(item T) (_ T, _ bool) {
 
 
 
687
  if t.root == nil {
688
  t.root = t.cow.newNode()
689
  t.root.items = append(t.root.items, item)
690
  t.length++
691
+ return
692
  } else {
693
  t.root = t.root.mutableFor(t.cow)
694
  if len(t.root.items) >= t.maxItems() {
699
  t.root.children = append(t.root.children, oldroot, second)
700
  }
701
  }
702
+ out, outb := t.root.insert(item, t.maxItems())
703
+ if !outb {
704
  t.length++
705
  }
706
+ return out, outb
707
  }
708
 
709
  // Delete removes an item equal to the passed in item from the tree, returning
710
+ // it. If no such item exists, returns (zeroValue, false).
711
+ func (t *BTreeG[T]) Delete(item T) (T, bool) {
712
  return t.deleteItem(item, removeItem)
713
  }
714
 
715
  // DeleteMin removes the smallest item in the tree and returns it.
716
+ // If no such item exists, returns (zeroValue, false).
717
+ func (t *BTreeG[T]) DeleteMin() (T, bool) {
718
+ var zero T
719
+ return t.deleteItem(zero, removeMin)
720
  }
721
 
722
  // DeleteMax removes the largest item in the tree and returns it.
723
+ // If no such item exists, returns (zeroValue, false).
724
+ func (t *BTreeG[T]) DeleteMax() (T, bool) {
725
+ var zero T
726
+ return t.deleteItem(zero, removeMax)
727
  }
728
 
729
+ func (t *BTreeG[T]) deleteItem(item T, typ toRemove) (_ T, _ bool) {
730
  if t.root == nil || len(t.root.items) == 0 {
731
+ return
732
  }
733
  t.root = t.root.mutableFor(t.cow)
734
+ out, outb := t.root.remove(item, t.minItems(), typ)
735
  if len(t.root.items) == 0 && len(t.root.children) > 0 {
736
  oldroot := t.root
737
  t.root = t.root.children[0]
738
  t.cow.freeNode(oldroot)
739
  }
740
+ if outb {
741
  t.length--
742
  }
743
+ return out, outb
744
  }
745
 
746
  // AscendRange calls the iterator for every value in the tree within the range
747
  // [greaterOrEqual, lessThan), until iterator returns false.
748
+ func (t *BTreeG[T]) AscendRange(greaterOrEqual, lessThan T, iterator ItemIteratorG[T]) {
749
  if t.root == nil {
750
  return
751
  }
752
+ t.root.iterate(ascend, optional[T](greaterOrEqual), optional[T](lessThan), true, false, iterator)
753
  }
754
 
755
  // AscendLessThan calls the iterator for every value in the tree within the range
756
  // [first, pivot), until iterator returns false.
757
+ func (t *BTreeG[T]) AscendLessThan(pivot T, iterator ItemIteratorG[T]) {
758
  if t.root == nil {
759
  return
760
  }
761
+ t.root.iterate(ascend, empty[T](), optional(pivot), false, false, iterator)
762
  }
763
 
764
  // AscendGreaterOrEqual calls the iterator for every value in the tree within
765
  // the range [pivot, last], until iterator returns false.
766
+ func (t *BTreeG[T]) AscendGreaterOrEqual(pivot T, iterator ItemIteratorG[T]) {
767
  if t.root == nil {
768
  return
769
  }
770
+ t.root.iterate(ascend, optional[T](pivot), empty[T](), true, false, iterator)
771
  }
772
 
773
  // Ascend calls the iterator for every value in the tree within the range
774
  // [first, last], until iterator returns false.
775
+ func (t *BTreeG[T]) Ascend(iterator ItemIteratorG[T]) {
776
  if t.root == nil {
777
  return
778
  }
779
+ t.root.iterate(ascend, empty[T](), empty[T](), false, false, iterator)
780
  }
781
 
782
  // DescendRange calls the iterator for every value in the tree within the range
783
  // [lessOrEqual, greaterThan), until iterator returns false.
784
+ func (t *BTreeG[T]) DescendRange(lessOrEqual, greaterThan T, iterator ItemIteratorG[T]) {
785
  if t.root == nil {
786
  return
787
  }
788
+ t.root.iterate(descend, optional[T](lessOrEqual), optional[T](greaterThan), true, false, iterator)
789
  }
790
 
791
  // DescendLessOrEqual calls the iterator for every value in the tree within the range
792
  // [pivot, first], until iterator returns false.
793
+ func (t *BTreeG[T]) DescendLessOrEqual(pivot T, iterator ItemIteratorG[T]) {
794
  if t.root == nil {
795
  return
796
  }
797
+ t.root.iterate(descend, optional[T](pivot), empty[T](), true, false, iterator)
798
  }
799
 
800
  // DescendGreaterThan calls the iterator for every value in the tree within
801
  // the range [last, pivot), until iterator returns false.
802
+ func (t *BTreeG[T]) DescendGreaterThan(pivot T, iterator ItemIteratorG[T]) {
803
  if t.root == nil {
804
  return
805
  }
806
+ t.root.iterate(descend, empty[T](), optional[T](pivot), false, false, iterator)
807
  }
808
 
809
  // Descend calls the iterator for every value in the tree within the range
810
  // [last, first], until iterator returns false.
811
+ func (t *BTreeG[T]) Descend(iterator ItemIteratorG[T]) {
812
  if t.root == nil {
813
  return
814
  }
815
+ t.root.iterate(descend, empty[T](), empty[T](), false, false, iterator)
816
  }
817
 
818
+ // Get looks for the key item in the tree, returning it. It returns
819
+ // (zeroValue, false) if unable to find that item.
820
+ func (t *BTreeG[T]) Get(key T) (_ T, _ bool) {
821
  if t.root == nil {
822
+ return
823
  }
824
  return t.root.get(key)
825
  }
826
 
827
+ // Min returns the smallest item in the tree, or (zeroValue, false) if the tree is empty.
828
+ func (t *BTreeG[T]) Min() (_ T, _ bool) {
829
  return min(t.root)
830
  }
831
 
832
+ // Max returns the largest item in the tree, or (zeroValue, false) if the tree is empty.
833
+ func (t *BTreeG[T]) Max() (_ T, _ bool) {
834
  return max(t.root)
835
  }
836
 
837
  // Has returns true if the given key is in the tree.
838
+ func (t *BTreeG[T]) Has(key T) bool {
839
+ _, ok := t.Get(key)
840
+ return ok
841
  }
842
 
843
  // Len returns the number of items currently in the tree.
844
+ func (t *BTreeG[T]) Len() int {
845
  return t.length
846
  }
847
 
865
  // O(tree size): when all nodes are owned by another tree, all nodes are
866
  // iterated over looking for nodes to add to the freelist, and due to
867
  // ownership, none are.
868
+ func (t *BTreeG[T]) Clear(addNodesToFreelist bool) {
869
  if t.root != nil && addNodesToFreelist {
870
  t.root.reset(t.cow)
871
  }
875
  // reset returns a subtree to the freelist. It breaks out immediately if the
876
  // freelist is full, since the only benefit of iterating is to fill that
877
  // freelist up. Returns true if parent reset call should continue.
878
+ func (n *node[T]) reset(c *copyOnWriteContext[T]) bool {
879
  for _, child := range n.children {
880
  if !child.reset(c) {
881
  return false
891
  func (a Int) Less(b Item) bool {
892
  return a < b.(Int)
893
  }
894
+
895
+ // BTree is an implementation of a B-Tree.
896
+ //
897
+ // BTree stores Item instances in an ordered structure, allowing easy insertion,
898
+ // removal, and iteration.
899
+ //
900
+ // Write operations are not safe for concurrent mutation by multiple
901
+ // goroutines, but Read operations are.
902
+ type BTree BTreeG[Item]
903
+
904
+ var itemLess LessFunc[Item] = func(a, b Item) bool {
905
+ return a.Less(b)
906
+ }
907
+
908
+ // New creates a new B-Tree with the given degree.
909
+ //
910
+ // New(2), for example, will create a 2-3-4 tree (each node contains 1-3 items
911
+ // and 2-4 children).
912
+ func New(degree int) *BTree {
913
+ return (*BTree)(NewG[Item](degree, itemLess))
914
+ }
915
+
916
+ // FreeList represents a free list of btree nodes. By default each
917
+ // BTree has its own FreeList, but multiple BTrees can share the same
918
+ // FreeList.
919
+ // Two Btrees using the same freelist are safe for concurrent write access.
920
+ type FreeList FreeListG[Item]
921
+
922
+ // NewFreeList creates a new free list.
923
+ // size is the maximum size of the returned free list.
924
+ func NewFreeList(size int) *FreeList {
925
+ return (*FreeList)(NewFreeListG[Item](size))
926
+ }
927
+
928
+ // NewWithFreeList creates a new B-Tree that uses the given node free list.
929
+ func NewWithFreeList(degree int, f *FreeList) *BTree {
930
+ return (*BTree)(NewWithFreeListG[Item](degree, itemLess, (*FreeListG[Item])(f)))
931
+ }
932
+
933
+ // ItemIterator allows callers of Ascend* to iterate in-order over portions of
934
+ // the tree. When this function returns false, iteration will stop and the
935
+ // associated Ascend* function will immediately return.
936
+ type ItemIterator ItemIteratorG[Item]
937
+
938
+ // Clone clones the btree, lazily. Clone should not be called concurrently,
939
+ // but the original tree (t) and the new tree (t2) can be used concurrently
940
+ // once the Clone call completes.
941
+ //
942
+ // The internal tree structure of b is marked read-only and shared between t and
943
+ // t2. Writes to both t and t2 use copy-on-write logic, creating new nodes
944
+ // whenever one of b's original nodes would have been modified. Read operations
945
+ // should have no performance degredation. Write operations for both t and t2
946
+ // will initially experience minor slow-downs caused by additional allocs and
947
+ // copies due to the aforementioned copy-on-write logic, but should converge to
948
+ // the original performance characteristics of the original tree.
949
+ func (t *BTree) Clone() (t2 *BTree) {
950
+ return (*BTree)((*BTreeG[Item])(t).Clone())
951
+ }
952
+
953
+ // Delete removes an item equal to the passed in item from the tree, returning
954
+ // it. If no such item exists, returns nil.
955
+ func (t *BTree) Delete(item Item) Item {
956
+ i, _ := (*BTreeG[Item])(t).Delete(item)
957
+ return i
958
+ }
959
+
960
+ // DeleteMax removes the largest item in the tree and returns it.
961
+ // If no such item exists, returns nil.
962
+ func (t *BTree) DeleteMax() Item {
963
+ i, _ := (*BTreeG[Item])(t).DeleteMax()
964
+ return i
965
+ }
966
+
967
+ // DeleteMin removes the smallest item in the tree and returns it.
968
+ // If no such item exists, returns nil.
969
+ func (t *BTree) DeleteMin() Item {
970
+ i, _ := (*BTreeG[Item])(t).DeleteMin()
971
+ return i
972
+ }
973
+
974
+ // Get looks for the key item in the tree, returning it. It returns nil if
975
+ // unable to find that item.
976
+ func (t *BTree) Get(key Item) Item {
977
+ i, _ := (*BTreeG[Item])(t).Get(key)
978
+ return i
979
+ }
980
+
981
+ // Max returns the largest item in the tree, or nil if the tree is empty.
982
+ func (t *BTree) Max() Item {
983
+ i, _ := (*BTreeG[Item])(t).Max()
984
+ return i
985
+ }
986
+
987
+ // Min returns the smallest item in the tree, or nil if the tree is empty.
988
+ func (t *BTree) Min() Item {
989
+ i, _ := (*BTreeG[Item])(t).Min()
990
+ return i
991
+ }
992
+
993
+ // Has returns true if the given key is in the tree.
994
+ func (t *BTree) Has(key Item) bool {
995
+ return (*BTreeG[Item])(t).Has(key)
996
+ }
997
+
998
+ // ReplaceOrInsert adds the given item to the tree. If an item in the tree
999
+ // already equals the given one, it is removed from the tree and returned.
1000
+ // Otherwise, nil is returned.
1001
+ //
1002
+ // nil cannot be added to the tree (will panic).
1003
+ func (t *BTree) ReplaceOrInsert(item Item) Item {
1004
+ i, _ := (*BTreeG[Item])(t).ReplaceOrInsert(item)
1005
+ return i
1006
+ }
1007
+
1008
+ // AscendRange calls the iterator for every value in the tree within the range
1009
+ // [greaterOrEqual, lessThan), until iterator returns false.
1010
+ func (t *BTree) AscendRange(greaterOrEqual, lessThan Item, iterator ItemIterator) {
1011
+ (*BTreeG[Item])(t).AscendRange(greaterOrEqual, lessThan, (ItemIteratorG[Item])(iterator))
1012
+ }
1013
+
1014
+ // AscendLessThan calls the iterator for every value in the tree within the range
1015
+ // [first, pivot), until iterator returns false.
1016
+ func (t *BTree) AscendLessThan(pivot Item, iterator ItemIterator) {
1017
+ (*BTreeG[Item])(t).AscendLessThan(pivot, (ItemIteratorG[Item])(iterator))
1018
+ }
1019
+
1020
+ // AscendGreaterOrEqual calls the iterator for every value in the tree within
1021
+ // the range [pivot, last], until iterator returns false.
1022
+ func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator) {
1023
+ (*BTreeG[Item])(t).AscendGreaterOrEqual(pivot, (ItemIteratorG[Item])(iterator))
1024
+ }
1025
+
1026
+ // Ascend calls the iterator for every value in the tree within the range
1027
+ // [first, last], until iterator returns false.
1028
+ func (t *BTree) Ascend(iterator ItemIterator) {
1029
+ (*BTreeG[Item])(t).Ascend((ItemIteratorG[Item])(iterator))
1030
+ }
1031
+
1032
+ // DescendRange calls the iterator for every value in the tree within the range
1033
+ // [lessOrEqual, greaterThan), until iterator returns false.
1034
+ func (t *BTree) DescendRange(lessOrEqual, greaterThan Item, iterator ItemIterator) {
1035
+ (*BTreeG[Item])(t).DescendRange(lessOrEqual, greaterThan, (ItemIteratorG[Item])(iterator))
1036
+ }
1037
+
1038
+ // DescendLessOrEqual calls the iterator for every value in the tree within the range
1039
+ // [pivot, first], until iterator returns false.
1040
+ func (t *BTree) DescendLessOrEqual(pivot Item, iterator ItemIterator) {
1041
+ (*BTreeG[Item])(t).DescendLessOrEqual(pivot, (ItemIteratorG[Item])(iterator))
1042
+ }
1043
+
1044
+ // DescendGreaterThan calls the iterator for every value in the tree within
1045
+ // the range [last, pivot), until iterator returns false.
1046
+ func (t *BTree) DescendGreaterThan(pivot Item, iterator ItemIterator) {
1047
+ (*BTreeG[Item])(t).DescendGreaterThan(pivot, (ItemIteratorG[Item])(iterator))
1048
+ }
1049
+
1050
+ // Descend calls the iterator for every value in the tree within the range
1051
+ // [last, first], until iterator returns false.
1052
+ func (t *BTree) Descend(iterator ItemIterator) {
1053
+ (*BTreeG[Item])(t).Descend((ItemIteratorG[Item])(iterator))
1054
+ }
1055
+
1056
+ // Len returns the number of items currently in the tree.
1057
+ func (t *BTree) Len() int {
1058
+ return (*BTreeG[Item])(t).Len()
1059
+ }
1060
+
1061
+ // Clear removes all items from the btree. If addNodesToFreelist is true,
1062
+ // t's nodes are added to its freelist as part of this call, until the freelist
1063
+ // is full. Otherwise, the root node is simply dereferenced and the subtree
1064
+ // left to Go's normal GC processes.
1065
+ //
1066
+ // This can be much faster
1067
+ // than calling Delete on all elements, because that requires finding/removing
1068
+ // each element in the tree and updating the tree accordingly. It also is
1069
+ // somewhat faster than creating a new tree to replace the old one, because
1070
+ // nodes from the old tree are reclaimed into the freelist for use by the new
1071
+ // one, instead of being lost to the garbage collector.
1072
+ //
1073
+ // This call takes:
1074
+ // O(1): when addNodesToFreelist is false, this is a single operation.
1075
+ // O(1): when the freelist is already full, it breaks out immediately
1076
+ // O(freelist size): when the freelist is empty and the nodes are all owned
1077
+ // by this tree, nodes are added to the freelist until full.
1078
+ // O(tree size): when all nodes are owned by another tree, all nodes are
1079
+ // iterated over looking for nodes to add to the freelist, and due to
1080
+ // ownership, none are.
1081
+ func (t *BTree) Clear(addNodesToFreelist bool) {
1082
+ (*BTreeG[Item])(t).Clear(addNodesToFreelist)
1083
+ }


简述:

google实现的btree包,本身其实已经做了很多的优化,其中每个外部可以调用的函数都有对应的Benchmark,这对我们分析泛型带来的优势提供了很大的帮助.

本文不讨论btree本身的优劣,单纯的从一个可以进行数据操作的集合函数库来着重讨论泛型带来的golang性能优化.

如果对golang的1.18新带来的泛型(generics)不太了解,可以先阅读一下 https://go.dev/doc/tutorial/generics (官方) 或者 https://segmentfault.com/a/1190000041634906 (中文讲解)

实现解析:

  1. 如上文diff代码能看到的,泛型化的btree代码,主要就是将原来的 item/node 替换成 item[T]/node[T]
@@ -72,32 +82,27 @@
-type FreeList struct {
+type FreeListG[T any] struct {
 	mu       sync.Mutex
-	freelist []*node
+	freelist []*node[T]
 }
 
 // size is the maximum size of the returned free list.
-func NewFreeList(size int) *FreeList {
-	return &FreeList{freelist: make([]*node, 0, size)}
+func NewFreeListG[T any](size int) *FreeListG[T] {
+	return &FreeListG[T]{freelist: make([]*node[T], 0, size)}
 }
 
-func (f *FreeList) newNode() (n *node) {
+func (f *FreeListG[T]) newNode() (n *node[T]) {
 	f.mu.Lock()
 	index := len(f.freelist) - 1
 	if index < 0 {
 		f.mu.Unlock()
-		return new(node)
+		return new(node[T])
 	}
 	n = f.freelist[index]
 	f.freelist[index] = nil

这一块就是标准的泛型更新,不需要特别的说明.

  1. 全新定义了泛型里面可以被排序的类型集合与他们的generics的比较函数
// LessFunc[T] 函数是用来定义泛型的类型形参(Type parameter) 'T'是如何比较大小的.
// 返回的顺序必须是严密的,且当'a' < 'b'是返回true.
type LessFunc[T any] func(a, b T) bool

// Ordered 定义了golang原生可以被比较大小的内置类型
// @Note: 这里主要是做前向兼容,如果有自定义的类型,实现了`Less`方法也可以用
type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~float32 | ~float64 | ~string
}

// Less[T] 就是内置的Less函数,直接返回支持的泛型类型形参的比较结果
func Less[T Ordered]() LessFunc[T] {
	return func(a, b T) bool { return a < b }
}

相对的,老版本直接是定义了一个Iteminterface{}来实现同样的Less函数

// Item 表示树上的一个独立对象.
type Item interface {
	// Less 函数必须要实现判断当前值是否小于传递进来的值.
	// 相等的值只会保存一个
	Less(than Item) bool
}
  1. 修改内部函数的返回值
@@ -308,70 +290,70 @@
-func (n *node) insert(item Item, maxItems int) Item {
-	i, found := n.items.find(item)
+func (n *node[T]) insert(item T, maxItems int) (_ T, _ bool) {
+	i, found := n.items.find(item, n.cow.less)
 	if found {
 		out := n.items[i]
 		n.items[i] = item
-		return out
+		return out, true
 	}
 	if len(n.children) == 0 {
 		n.items.insertAt(i, item)
-		return nil
+		return
 	}
@@ -424,8 +406,9 @@
 		// 在这里使用的了一个内部的'remove'调用并且传递了一个'maxItem'参数,
 		// 拉取i的前一项(最右边的子节点)并设置到拉取的当前节点上
-		n.items[i] = child.remove(nil, minItems, removeMax)
-		return out
+		var zero T
+		n.items[i], _ = child.remove(zero, minItems, removeMax)
+		return out, true
 	}

之前的函数实现返回Item,Item是一个interface{}(1.18之后是一个基本接口),之前可以通过直接返回一个nil表示没有找到数据或者操作失败

但是泛型之后,不同的类型形参不能表示这种状态,所以在返回泛型的形参T之外,还增加返回了一个bool类型来表示操作结果

这里的Item(实际是一个interface{}接口)是性能瓶颈与优化的核心,后续我们回详细展开聊到

  1. 最后再增加亿点点兼容代码
// 前向兼容的方式,定义泛型下的'BTree'是一个'BTreeG'的Item约束
type BTree BTreeG[Item]

// 定义默认的函数,就是上文#2定义好的比较函数的实例
var itemLess LessFunc[Item] = func(a, b Item) bool {
	return a.Less(b)
}

// New 创建一个新的'BTree',内部转换为创建一个'BTreeG[item]',同时传递less函数
func New(degree int) *BTree {
	return (*BTree)(NewG[Item](degree, itemLess))
}
...更多的函数

性能测试结果

MR里面提到使用泛型改造之后,对于官方的bench函数(int存储),性能能优化40%+!

这里写一个简单的Bench来对比两种实现方式的性能

Code

package main

import (
	"math/rand"
	"testing"
	"time"

	"github.com/google/btree"
)

const treeSize = 50000

func init() {
	rand.Seed(time.Now().Unix())
}

func BenchmarkBTree(b *testing.B) {
	b.StopTimer()
	insertP := rand.Perm(treeSize)
	b.StartTimer()
	i := 0
	for i < b.N {
		tr := btree.New(32)
		for _, item := range insertP {
			tr.ReplaceOrInsert(btree.Int(item))
			i++
			if i >= b.N {
				return
			}
		}
	}
}

func BenchmarkBTreeG(b *testing.B) {
	b.StopTimer()
	insertP := rand.Perm(treeSize)
	b.StartTimer()
	i := 0
	for i < b.N {
		tr := btree.NewOrderedG[int](32)
		for _, item := range insertP {
			tr.ReplaceOrInsert(item)
			i++
			if i >= b.N {
				return
			}
		}
	}
}

Bench执行之后的结果对比(使用github-codespace机器)

Running tool: /usr/local/go/bin/go test -benchmem -run=^$ -bench ^(BenchmarkBTree|BenchmarkBTreeG)$ gh/btree -count=1 -failfast

goos: linux
goarch: amd64
pkg: gh/btree
cpu: Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz
BenchmarkBTree-4    	 3254396	       373.8 ns/op	      44 B/op	       1 allocs/op
BenchmarkBTreeG-4   	 5487584	       215.7 ns/op	      19 B/op	       0 allocs/op
PASS
ok  	gh/btree	5.106s

完整的官方全部bench对比结果:(再次感叹下原来版本的btree已经非常优化了,alloc(s)已经很小)

go test -bench -count=5 -failfast > [old|new].txt
benchstst old.txt new.txt


nameold time/opnew time/opdelta
Insert-20175ns ± 1%131ns ± 1%-25.23%(p=0.008 n=5+5)
Seek-20141ns ± 2%82ns ± 6%-42.10%(p=0.008 n=5+5)
DeleteInsert-20357ns ± 1%272ns ± 1%-24.01%(p=0.008 n=5+5)
DeleteInsertCloneOnce-20354ns ± 1%269ns ± 1%-24.01%(p=0.008 n=5+5)
DeleteInsertCloneEachTime-201.53µs ± 1%0.97µs ± 7%-36.70%(p=0.008 n=5+5)
Delete-20196ns ± 1%145ns ± 2%-25.91%(p=0.008 n=5+5)
Get-20155ns ± 2%108ns ± 0%-30.03%(p=0.008 n=5+5)
GetCloneEachTime-20239ns ± 1%180ns ± 2%-24.78%(p=0.008 n=5+5)
Ascend-2047.7µs ± 1%35.0µs ± 1%-26.63%(p=0.008 n=5+5)
Descend-2047.3µs ± 1%34.1µs ± 1%-27.88%(p=0.008 n=5+5)
AscendRange-2091.7µs ± 2%54.7µs ± 1%-40.36%(p=0.008 n=5+5)
DescendRange-20130µs ± 5%72µs ± 1%-44.78%(p=0.008 n=5+5)
AscendGreaterOrEqual-2056.9µs ± 1%42.0µs ± 1%-26.19%(p=0.008 n=5+5)
DescendLessOrEqual-2094.0µs ± 2%57.4µs ± 1%-38.89%(p=0.008 n=5+5)
DeleteAndRestore/CopyBigFreeList-205.08ms ± 1%3.60ms ± 0%-29.02%(p=0.016 n=5+4)
DeleteAndRestore/Copy-205.41ms ± 3%3.66ms ± 0%-32.37%(p=0.008 n=5+5)
DeleteAndRestore/ClearBigFreelist-202.92ms ± 1%2.16ms ± 1%-26.09%(p=0.008 n=5+5)
DeleteAndRestore/Clear-203.14ms ± 1%2.24ms ± 1%-28.91%(p=0.008 n=5+5)
nameold alloc/opnew alloc/opdelta
Insert-2036.0B ± 3%18.4B ± 3%-48.89%(p=0.008 n=5+5)
Seek-207.00B ± 0%0.00B-100.00%(p=0.008 n=5+5)
DeleteInsert-200.00B0.00B~(all equal)
DeleteInsertCloneOnce-200.00B0.00B~(all equal)
DeleteInsertCloneEachTime-202.97kB ± 1%1.95kB ± 4%-34.30%(p=0.008 n=5+5)
Delete-200.00B0.00B~(all equal)
Get-200.00B0.00B~(all equal)
GetCloneEachTime-2064.0B ± 0%64.0B ± 0%~(all equal)
Ascend-200.00B0.00B~(all equal)
Descend-200.00B0.00B~(all equal)
AscendRange-200.00B0.00B~(all equal)
DescendRange-200.00B0.00B~(all equal)
AscendGreaterOrEqual-200.00B0.00B~(all equal)
DescendLessOrEqual-200.00B0.00B~(all equal)
DeleteAndRestore/CopyBigFreeList-20274kB ± 0%142kB ± 0%-48.20%(p=0.008 n=5+5)
DeleteAndRestore/Copy-20876kB ± 0%443kB ± 0%-49.36%(p=0.008 n=5+5)
DeleteAndRestore/ClearBigFreelist-20631B ± 1%510B ± 5%-19.06%(p=0.008 n=5+5)
DeleteAndRestore/Clear-20553kB ± 0%278kB ± 0%-49.77%(p=0.000 n=5+4)
nameold allocs/opnew allocs/opdelta
Insert-200.000.00~(all equal)
Seek-200.000.00~(all equal)
DeleteInsert-200.000.00~(all equal)
DeleteInsertCloneOnce-200.000.00~(all equal)
DeleteInsertCloneEachTime-2011.0 ± 0%11.0 ± 0%~(all equal)
Delete-200.000.00~(all equal)
Get-200.000.00~(all equal)
GetCloneEachTime-203.00 ± 0%3.00 ± 0%~(all equal)
Ascend-200.000.00~(all equal)
Descend-200.000.00~(all equal)
AscendRange-200.000.00~(all equal)
DescendRange-200.000.00~(all equal)
AscendGreaterOrEqual-200.000.00~(all equal)
DescendLessOrEqual-200.000.00~(all equal)
DeleteAndRestore/CopyBigFreeList-2012.0 ± 0%14.0 ± 0%+16.67%(p=0.008 n=5+5)
DeleteAndRestore/Copy-201.18k ± 0%1.13k ± 0%-4.15%(p=0.008 n=5+5)
DeleteAndRestore/ClearBigFreelist-201.00 ± 0%1.00 ± 0%~(all equal)
DeleteAndRestore/Clear-201.07k ± 0%1.02k ± 0%-4.49%(p=0.008 n=5+5)

原理分析与说明

细心的人已经发现了端倪,Seek的bench结果显示泛型之后的代码的alloc/op直接将为了0

google/btree的bench使用的是一个int类型,但是传递的都是一个Item接口.在bench的开头,创建了一个填充了随机数的int数组(同时转换为btree.Int,一个Item的实现).

type node struct {
	items    items
	children children
	cow      *copyOnWriteContext
}
type items []Item
type Item interface {
	Less(than Item) bool
}
type children []*node

当我们调用一个函数的时候,比如Seek实际内部调用AscendGreaterOrEqual实际内部去循环t.root.iterate()

bench代码模拟了一个大树的随机数据创建,const benchmarkTreeSize = 10000个int已经在函数的堆(heap)上了,正常来说,我们调用函数传参都是简单的复制了指向这个int地址的一个指针而已

但是当btree传递数据参数变成Item之后,情况就发生了变化,这个时候,传递的int地址的指针,变成了一个Itemintertface{}的指针,这个时候参数就会逃逸到栈上(escape to heap)

这种情况其实很常见,比如最常用到的printf系列函数,他接收的永远是interface{}作为参数,golang的编译器就会认为这类的函数,任意传递的v都会被转换成interface{}之后复制到栈上,再进行处理

这其实很好理解,v(aka Item in btree)可以是任何类型,传递形参为了保证安全,会复制到一个叫做interface{}的万能圣杯里,再去传递

// fmt.Printf 接收任意个interface{}变量,所以在go编译阶段,会逃逸到栈heap上
func Printf(format string, a ...interface{}) (n int, err error) {}

// btree.AscendGreaterOrEqual 接收一个Item变量,实际还是一个实现了Less函数的interface{},同样会被编译器转换成interface{}的指针,这个时候就会逃逸到栈上
func (t *BTree) AscendGreaterOrEqual(pivot Item, iterator ItemIterator) {}

// 泛型实现,在编译阶段就会解析成实际的int类型,此时的pivot就是int,不会发生逃逸
func (t *BTreeG[T]) AscendGreaterOrEqual(pivot T, iterator ItemIteratorG[T]) {}

想要检测是否发生逃逸也很简单,直接使用golang自带的go build -gcflags="-m" .

golang这些年来做了很多编译的智能推断与优化,实际情况没有这么简单,举一个编译器可以优化的例子:

如果函数虽然接收的是一个interface{},但是实际内部只用了一种类型断言的时候,go编译器是不会发生逃逸到栈的处理的

func IsUIntStr(v interface{}) string {
  if vi, ok := v.(int); ok && vi > 0 {
     return "true"
  }
  return "false"
}

在这种情况下,是不会发生额外的复制行为的

回到正题,btree接收的类型是Item(interface{}),当有大量的Item对象调用的时候,需要复制到栈(heap)的数据也会很大.

这种情况在bench里面更加明显,Item实际内部只是一个int的占用空间,但是发生函数调用时,需要生成一个指向这个int的完整的interface{},每调用一个参数,增加的指针比实际int的内存占用空间还多的多

一个非空的interface{} 至少包含

  1. 一个itab指针,指向一个对象的类型信息
  2. 一个unsafe.Pointer,指向实际的data地址

@see: https://github.com/golang/go/blob/master/src/reflect/value.go#L200

使用了 泛型之后,上述的函数在编译阶段就会被解析成:

func (t *BTreeG[int]) AscendGreaterOrEqual(pivot int, iterator ItemIteratorG[int]) {}

这样永远传递的都是指向int实际地址的一个确定指针,指挥复制一次指针,在函数的堆内就能完成操作

大量的对象逃逸到栈(heap)的时候,由于heap是随着函数调用随机不连续的调用与复制(copy+alloc),进一步加大gc了的扫描与处理时间,导致最终的性能下降

关于为什么逃逸到堆(heap)之后的go性能会下降,和对应的cpu与alloc相关的详细说明,可以参考下面这些,这里就不再赘述了:

引申

从上面的分析可以看到,泛型在处理interface{}的问题上提供了一个新的优化思路,在我目前使用的小工具合集的utils里面也有一定的借鉴思路

可以假设有这样一个非常常用的需求: 把一组数组去重,需要同时支持[]string,[]int64,[]float64等等

以前的go代码只有有两种思路:

  1. 使用 // go generate 使用模板自动生成N个函数 但是这样会带来一个问题,不同函数的签名方法名肯定是不一样的,比如UniqStringSlice或者是UniqInt64Slice,对于调用方来说维护或者查询需要的函数也不简单
  2. 使用 switch .(type) 断言,全部代码写到一个函数里面去 但是老的版本,只能使用一个interface{}去接收slice,好处是一个函数走天下,但是需要通过runtime+reflect的方式去判断具体传入的是怎么样 interface{}=>[]interface{}{}=> reflect.Slice(i).Interface()多种转换,性能必然下降

有了泛型(generics)之后,这类需求就非常容易了:(这也是在我的项目升级之后的utils库里)

func UniqSlice[T constraints.Ordered](list []T) []T {
	target := make([]T, 0)
	listMap := make(map[T]bool)
	for _, v := range list {
		if _, ok := listMap[v]; !ok {
			listMap[v] = true
			target = append(target, v)
		}
	}
	return target
}

总结

看起来泛型的引入没有对google/btree的代码结构发生大的变化,但是实际测试结果却让性能好了不少,可以预见到很多使用slice+interface{}的场景,更改为泛型(generics)之后都能带来代码量的减少和一定的性能的提升

后续希望可以看到更多的go代码使用泛型来进行优化,或者给出更多的解决实际问题的思路.


comments powered by Disqus