Colobu | 鸟窝 晁岳攀

// A timers is a per-P set of timers.

type timers struct {
    // 互斥锁保护timers; 虽然timers是每个P的，但是调度器可以访问另一个P的timers，所以我们必须锁定。
	mu mutex
    // heap是一组计时器，按heap[i].when排序。这就是一个四叉堆，虽然没有明确的说明。
    // 必须持有锁才能访问这个堆。
	heap []timerWhen
    // len是heap的长度的原子副本。
	len atomic.Uint32
    // zombies是堆中标记为删除的计时器的数量。
	zombies atomic.Int32
	raceCtx uintptr
    // minWhenHeap是最小的heap[i].when值(= heap[0].when)。
    // wakeTime方法使用minWhenHeap和minWhenModified来确定下一个唤醒时间。
    // 如果minWhenHeap = 0，表示堆中没有计时器。
	minWhenHeap atomic.Int64
    // minWhenModified是具有timerModified位设置的计时器的最小heap[i].when的下界。
    // 如果minWhenModified = 0，表示堆中没有timerModified计时器。
	minWhenModified atomic.Int64
}

type timerWhen struct {
	timer *timer
	when  int64
}

func (ts *timers) lock() {
	lock(&ts.mu)
}

func (ts *timers) unlock() {
	ts.len.Store(uint32(len(ts.heap)))
	unlock(&ts.mu)
}

type timer struct {
	mu mutex
	astate atomic.Uint8 
	state  uint8       
	isChan bool       
	blocked uint32
	when   int64
	period int64
	f      func(arg any, seq uintptr, delay int64)
	arg    any
	seq    uintptr
	ts *timers // 注意这里
	sendLock mutex
	isSending atomic.Int32
}

const timerHeapN = 4

// siftUp将位置i的计时器在堆中合适的位置，通过将其向堆的顶部移动。

func (ts *timers) siftUp(i int) {
	heap := ts.heap
	if i >= len(heap) {
		badTimer()
	}
    // 注意下面两行我们保存了当前i的计时器和它的when值
	tw := heap[i] 
	when := tw.when
	if when <= 0 {
		badTimer()
	}
	for i > 0 {
		p := int(uint(i-1) / timerHeapN) // 父节点 (i-1)/4
		if when >= heap[p].when { // 如果父节点的when <= 当前节点的when，那么就不需要再上浮了
			break
		}
		heap[i] = heap[p] // 父节点下沉到当前的i
		i = p // i指向父节点, 继续循环上浮检查
	}
    // 如果发生了上浮，那么最后将tw放到上浮到的合适位置
	if heap[i].timer != tw.timer {
		heap[i] = tw
	}
}

// siftDown将位置i的计时器放在堆中的正确位置，通过将其向堆的底部移动。

func (ts *timers) siftDown(i int) {
	heap := ts.heap
	n := len(heap)
	if i >= n {
		badTimer()
	}
    // 如果已经是叶子节点，不用下沉了
	if i*timerHeapN+1 >= n {
		return
	}
    // 保存当前i的计时器和when值
	tw := heap[i]
	when := tw.when
	if when <= 0 {
		badTimer()
	}
    // 从左子节点开始，找到最小的when值，然后将当前节点下沉到这个位置
	for {
		leftChild := i*timerHeapN + 1 // 左子节点
		if leftChild >= n {
			break
		}
		w := when
		c := -1
		for j, tw := range heap[leftChild:min(leftChild+timerHeapN, n)] { // 从左子节点开始遍历子节点,找到小于当前w的最小的子节点
			if tw.when < w {
				w = tw.when
				c = leftChild + j
			}
		}
		if c < 0 { // 如果没有找到比当前节点更小的子节点，那么就不用下沉了
			break
		}
        // 将当前节点下沉到最小的子节点
		heap[i] = heap[c]
		i = c
	}
    // 如果发生了下沉，那么最后将tw放到下沉到的合适位置
	if heap[i].timer != tw.timer {
		heap[i] = tw
	}
}

func (ts *timers) initHeap() {
	if len(ts.heap) <= 1 {
		return
	}
    
    // 从最后一个非叶子节点开始，依次下沉
	for i := int(uint(len(ts.heap)-1-1) / timerHeapN); i >= 0; i-- {
		ts.siftDown(i)
	}
}

func (ts *timers) deleteMin() {
    // 得到堆顶元素
	t := ts.heap[0].timer
	if t.ts != ts {
		throw("wrong timers")
	}
	t.ts = nil // 将timer的ts置为nil，自此和ts一别两宽，再无瓜葛
    // 将最后一个元素设置为堆顶
	last := len(ts.heap) - 1
	if last > 0 {
		ts.heap[0] = ts.heap[last]
	}
	ts.heap[last] = timerWhen{} // 将最后一个元素置为空
	ts.heap = ts.heap[:last] // 缩减slice,剔除最后的空元素
	if last > 0 { // 将堆顶元素下沉
		ts.siftDown(0)
	}
	ts.updateMinWhenHeap()
	if last == 0 {
		ts.minWhenModified.Store(0)
	}
}

func (ts *timers) addHeap(t *timer) {
	if netpollInited.Load() == 0 {
		netpollGenericInit()
	}
	if t.ts != nil {
		throw("ts set in timer")
	}
    // 设置timer的ts为当前的timers,从此执子之手，笑傲江湖
	t.ts = ts
    // 添加到最后
	ts.heap = append(ts.heap, timerWhen{t, t.when})
	ts.siftUp(len(ts.heap) - 1) // 上浮它到合适的位置
	if t == ts.heap[0].timer {
		ts.updateMinWhenHeap()
	}
}

import "github.com/ahrav/go-d-ary-heap"

package main

import (
    "fmt"
    "github.com/ahrav/go-d-ary-heap"
)

func main() {
    // Create a min-heap for integers with a branching factor of 3.
    minHeap := heap.NewHeap[int](3, func(a, b int) bool { return a < b })
    // Create a max-heap for integers with a branching factor of 4.
    maxHeap := heap.NewHeap[int](4, func(a, b int) bool { return a > b })
}

minHeap.Push(10)
minHeap.Push(5)
minHeap.Push(15)
maxHeap.Push(10)
maxHeap.Push(5)
maxHeap.Push(15)

fmt.Println(minHeap.Pop()) // Outputs: 5
fmt.Println(maxHeap.Pop()) // Outputs: 15

fmt.Println(minHeap.Peek()) // Assuming more elements were added, outputs the smallest
fmt.Println(maxHeap.Peek()) // Assuming more elements were added, outputs the largest

type Entry[K comparable, V, P any] struct {
	Key      K
	Value    V
	Priority P
	index    int
}

type heapmap[K comparable, V, P any] struct {
	h pq[K, V, P]
	m map[K]*Entry[K, V, P]
}

func (hm *heapmap[K, V, P]) Len() int {
	return len(hm.m)
}

func (hm *heapmap[K, V, P]) Peek() (Entry[K, V, P], bool) {
	if hm.Empty() {
		return Entry[K, V, P]{}, false
	}
	return *hm.h.entries[0], true
}

func (hm *heapmap[K, V, P]) Pop() (Entry[K, V, P], bool) {
	if hm.Empty() {
		return Entry[K, V, P]{}, false
	}
	e := *heap.Pop(&hm.h).(*Entry[K, V, P])
	delete(hm.m, e.Key)
	return e, true
}

func (hm *heapmap[K, V, P]) Set(key K, value V, priority P) {
	if e, ok := hm.m[key]; ok {
		e.Value = value
		e.Priority = priority
		heap.Fix(&hm.h, e.index)
		return
	}
	e := &Entry[K, V, P]{
		Key:      key,
		Value:    value,
		Priority: priority,
	}
	heap.Push(&hm.h, e)
	hm.m[key] = e
}

func (hm *heapmap[K, V, P]) Get(key K) (Entry[K, V, P], bool) {
	if e, ok := hm.m[key]; ok {
		return *e, true
	}
	return Entry[K, V, P]{}, false
}

type Data struct {
    x int64 // 线程A更新的变量
    y int64 // 线程B更新的变量
}

type Data struct {
    x int64           // 线程A更新的变量
    _ [7]int64        // 填充7个int64以对齐至64字节的cache line大小
    y int64           // 线程B更新的变量
}

package main

import (
	"testing"
)
// NonAlignedStruct 未对齐的结构体，补充后占24个字节

type NonAlignedStruct struct {
	a byte // 1字节,补齐7字节
	b int64 // 8字节
	c byte // 1字节,补齐7字节
}
// AlignedStruct 已对齐的结构体，补充后占16个字节

type AlignedStruct struct {
	b int64 // 8字节
	a byte // 1字节
	c byte // 1字节
	_ [6]byte // 填充6个字节，总共16个字节
}

const arraySize = 1024 * 1024

var (
	nonAlignedArray [arraySize]NonAlignedStruct
	alignedArray    [arraySize]AlignedStruct
	result          int64
)
// 初始化数组

func init() {
	for i := 0; i < arraySize; i++ {
		nonAlignedArray[i] = NonAlignedStruct{
			a: byte(i),
			b: int64(i),
			c: byte(i),
		}
		alignedArray[i] = AlignedStruct{
			a: byte(i),
			b: int64(i),
			c: byte(i),
		}
	}
}
// BenchmarkNonAligned 测试未对齐结构体的性能

func BenchmarkNonAligned(b *testing.B) {
	var sum int64
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for j := 0; j < arraySize; j++ {
			sum += nonAlignedArray[j].b // 读取未对齐结构体的字段
		}
	}
	result = sum // 防止编译器优化
}
// BenchmarkAligned 测试已对齐结构体的性能

func BenchmarkAligned(b *testing.B) {
	var sum int64
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for j := 0; j < arraySize; j++ {
			sum += alignedArray[j].b // 读取已对齐结构体的字段
		}
	}
	result = sum // 防止编译器优化
}

// CacheLinePad 用来填充结构体，避免伪共享

type CacheLinePad struct{ _ [CacheLinePadSize]byte }
// CacheLineSize 是 CPU 的缓存行大小，不同的 CPU 架构可能不同.
// 目前 Go 运行时没有检测真实的缓存行大小，所以代码实现使用每个 GOARCH 的常量 CacheLinePadSize 作为近似值。

var CacheLineSize uintptr = CacheLinePadSize

// CacheLinePadSize is used to prevent false sharing of cache lines.
// We choose 128 because Apple Silicon, a.k.a. M1, has 128-byte cache line size.
// It doesn't cost much and is much more future-proof.

const CacheLinePadSize = 128

// CacheLinePadSize is used to prevent false sharing of cache lines.
// We choose 64 because Loongson 3A5000 the L1 Dcache is 4-way 256-line 64-byte-per-line.

const CacheLinePadSize = 64

//go:build 386 || amd64

package cpu

const CacheLinePadSize = 64

type CacheLinePad struct{ _ [cacheLineSize]byte }

type semaRoot struct {
	lock  mutex
	treap *sudog        // root of balanced tree of unique waiters.
	nwait atomic.Uint32 // Number of waiters. Read w/o the lock.
}

var semtable semTable
// Prime to not correlate with any user patterns.

const semTabSize = 251

type semTable [semTabSize]struct {
	root semaRoot
	pad  [cpu.CacheLinePadSize - unsafe.Sizeof(semaRoot{})]byte
}

type mheap struct {
	_ sys.NotInHeap
	lock mutex
	pages pageAlloc // page allocation data structure
	sweepgen uint32 // sweep generation, see comment in mspan; written during STW
	allspans []*mspan // all spans out there
	pagesInUse         atomic.Uintptr // pages of spans in stats mSpanInUse
	pagesSwept         atomic.Uint64  // pages swept this cycle
	pagesSweptBasis    atomic.Uint64  // pagesSwept to use as the origin of the sweep ratio
	sweepHeapLiveBasis uint64         // value of gcController.heapLive to use as the origin of sweep ratio; written with lock, read without
	sweepPagesPerByte  float64        // proportional sweep ratio; written with lock, read without
	reclaimIndex atomic.Uint64
	reclaimCredit atomic.Uintptr
	_ cpu.CacheLinePad // prevents false-sharing between arenas and preceding variables
	
	arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
    ...
}

var stackpool [_NumStackOrders]struct {
	item stackpoolItem
	_    [(cpu.CacheLinePadSize - unsafe.Sizeof(stackpoolItem{})%cpu.CacheLinePadSize) % cpu.CacheLinePadSize]byte
}

type semaRoot struct {
	lock  mutex
	treap *sudog        // 不重复的等待者(goroutine)的平衡树(treap)的根节点
	nwait atomic.Uint32 // 等待者(goroutine)的数量
}

type sudog struct {
	g *g
	next *sudog
	prev *sudog
	elem unsafe.Pointer // data element (may point to stack)
	acquiretime int64
	releasetime int64
	ticket      uint32
	isSelect bool
	success bool
	waiters uint16
	parent   *sudog // semaRoot binary tree
	waitlink *sudog // g.waiting list or semaRoot
	waittail *sudog // semaRoot
	c        *hchan // channel
}

func (root *semaRoot) queue(addr *uint32, s *sudog, lifo bool) {
	// 设置这个要加入的节点
	s.g = getg()
	s.elem = unsafe.Pointer(addr)
	s.next = nil
	s.prev = nil
	s.waiters = 0
	var last *sudog
	pt := &root.treap
	// 从根节点开始
	for t := *pt; t != nil; t = *pt { // ①
		// 如果地址已经在列表中,则加入到这个地址的链表中
		if t.elem == unsafe.Pointer(addr) {
			// 如果地址已经在列表中，并且指定了先入后出flag,这是一个替换操作
			if lifo {
				// 替换操作
				*pt = s
				s.ticket = t.ticket
				... // 把t的各种信息复制给s
			} else {
				// 增加到到等待列表的末尾
				if t.waittail == nil {
					t.waitlink = s
				} else {
					t.waittail.waitlink = s
				}
				t.waittail = s
				s.waitlink = nil
				if t.waiters+1 != 0 {
					t.waiters++
				}
			}
			return
		}
		last = t
		// 二叉搜索树查找
		if uintptr(unsafe.Pointer(addr)) < uintptr(t.elem) { // ②
			pt = &t.prev
		} else {
			pt = &t.next
		}
	}
	// 为新节点设置ticket.这个ticket是一个随机值，作为随机堆的优先级，用于保持treap的平衡。
	s.ticket = cheaprand() | 1 // ③
	s.parent = last
	*pt = s
	// 根据优先级(ticket)旋转以保持treap的平衡
	for s.parent != nil && s.parent.ticket > s.ticket { // ④
		if s.parent.prev == s {
			root.rotateRight(s.parent) // ⑤
		} else {
			if s.parent.next != s {
				panic("semaRoot queue")
			}
			root.rotateLeft(s.parent) // ⑥
		}
	}
}

type Mutex struct {
	state int32
	sema  uint32
}

func (root *semaRoot) dequeue(addr *uint32) (found *sudog, now, tailtime int64) {
	ps := &root.treap
	s := *ps
	for ; s != nil; s = *ps { // ①， 二叉搜索树查找
		if s.elem == unsafe.Pointer(addr) { // ②
			goto Found
		}
		if uintptr(unsafe.Pointer(addr)) < uintptr(s.elem) {
			ps = &s.prev
		} else {
			ps = &s.next
		}
	}
	return nil, 0, 0
Found: // ③
	...
	if t := s.waitlink; t != nil { // ④
		*ps = t
		...
	} else { // ⑤
		// 旋转s到叶节点，以便删除
		for s.next != nil || s.prev != nil {
			if s.next == nil || s.prev != nil && s.prev.ticket < s.next.ticket {
				root.rotateRight(s)
			} else {
				root.rotateLeft(s)
			}
		}
		// ⑤ 删除s
		if s.parent != nil {
			if s.parent.prev == s {
				s.parent.prev = nil
			} else {
				s.parent.next = nil
			}
		} else {
			root.treap = nil
		}
		tailtime = s.acquiretime
	}
	... // 清理s的不需要的信息
	return s, now, tailtime
}

func (root *semaRoot) rotateLeft(x *sudog) {
	// p -> (x a (y b c))
	p := x.parent
	y := x.next
	b := y.prev
	y.prev = x // ①
	x.parent = y // ②
	x.next = b // ③
	if b != nil {
		b.parent = x // ④
	}
	y.parent = p // ⑤
	if p == nil {
		root.treap = y // ⑥
	} else if p.prev == x { // ⑦
		p.prev = y
	} else {
		if p.next != x {
			throw("semaRoot rotateLeft")
		}
		p.next = y
	}
}

func (root *semaRoot) rotateRight(y *sudog) {
	// p -> (y (x a b) c)
	p := y.parent
	x := y.prev
	b := x.next
	x.next = y // ①
	y.parent = x // ②
	y.prev = b // ③
	if b != nil {
		b.parent = y // ④
	}
	x.parent = p // ⑤
	if p == nil {
		root.treap = x // ⑥
	} else if p.prev == y { // ⑦
		p.prev = x
	} else {
		if p.next != y {
			throw("semaRoot rotateRight")
		}
		p.next = x
	}
}

// 旋转s到叶节点，以便删除

for s.next != nil || s.prev != nil {
	if s.next == nil || s.prev != nil && s.prev.ticket < s.next.ticket {
		root.rotateRight(s)
	} else {
		root.rotateLeft(s)
	}
}

type BitVec struct {
	N int32    // 这个向量中包含的bit数
	B []uint32 // 保存这些bit所需的数组
}

func New(n int32) BitVec {
	nword := (n + wordBits - 1) / wordBits // 计算保存这些bit所需的最少的数组
	return BitVec{n, make([]uint32, nword)}
}

func (dst BitVec) And(src1, src2 BitVec) {
	if len(src1.B) == 0 {
		return
	}
	_, _ = dst.B[len(src1.B)-1], src2.B[len(src1.B)-1] // hoist bounds checks out of the loop
	for i, x := range src1.B {
		dst.B[i] = x & src2.B[i]
	}
}

func (bv BitVec) Not() {
	for i, x := range bv.B {
		bv.B[i] = ^x
	}
	if bv.N%wordBits != 0 {
		bv.B[len(bv.B)-1] &= 1<<uint(bv.N%wordBits) - 1 // clear bits past N in the last word
	}
}

func (bv BitVec) Count() int {
	n := 0
	for _, x := range bv.B {
		n += bits.OnesCount32(x)
	}
	return n
}