发表Golang20 分钟读完 (大约3029个字)0次访问

三色灯控制实现

数组

数组是一个由固定长度的特定类型元素组成的序列，一个数组可以由零个或者多个元素组成，由于数组的长度是固定的，所以在Go中很少使用。所以不作过多介绍。

数组的初始化的两种方式：

1
2
var r = [3]int{1, 2, 3}
q := [...]int{1, 2, 3} //语法糖

Slice

本文代码基于Go 1.17

slice 结构体

1
2
3
4
5
6
7
8
type slice struct {
    //指向底层数组的指针
	array unsafe.Pointer
    //slice当前元素的个数
	len   int
    //slice的容量
	cap   int
}

创建切片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func makeslice(et *_type, len, cap int) unsafe.Pointer {
	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
	if overflow || mem > maxAlloc || len < 0 || len > cap {
		// NOTE: Produce a 'len out of range' error instead of a
		// 'cap out of range' error when someone does make([]T, bignumber).
		// 'cap out of range' is true too, but since the cap is only being
		// supplied implicitly, saying len is clearer.
		// See golang.org/issue/4085.
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}

	return mallocgc(mem, et, true)
}

这边有个unsafe.Pointer

1
2
3
4
5
go里面的指针类似于C++里的y
任意类型的指针值都可以转换为unsafe.Pointer（A pointer value of any type can be converted to a Pointer.）
unsafe.Pointer可以转换为任意类型的指针值（A Pointer can be converted to a pointer value of any type.）
uintptr可以转换为unsafe.Pointer（A uintptr can be converted to a Pointer.）
unsafe.Pointer可以转换为uintptr（A Pointer can be converted to a uintptr.）

增加元素以及扩容

slice相比于数组的一大优势就是可以进行扩容，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// growslice handles slice growth during append.
// It is passed the slice element type, the old slice, and the desired new minimum capacity,
// and it returns a new slice with at least that capacity, with the old data
// copied into it.
// The new slice's length is set to the old slice's length,
// NOT to the new requested capacity.
// This is for codegen convenience. The old slice's length is used immediately
// to calculate where to write new values during an append.
// TODO: When the old backend is gone, reconsider this decision.
// The SSA backend might prefer the new length or to return only ptr/cap and save stack space.
func growslice(et *_type, old slice, cap int) slice {
	if raceenabled {
		callerpc := getcallerpc()
		racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
	}
	if msanenabled {
		msanread(old.array, uintptr(old.len*int(et.size)))
	}
	//如果需求的容量小于原始容量则报panic错误
	if cap < old.cap {
		panic(errorString("growslice: cap out of range"))
	}
	//append不能创建一个nil指针但是len长度不为0的切片
	if et.size == 0 {
		// append should not create a slice with nil pointer but non-zero len.
		// We assume that append doesn't need to preserve old.array in this case.
        //当前切片大小为0，调用了扩容方法，直接返回应该新的容量的切片
		return slice{unsafe.Pointer(&zerobase), old.len, cap}
	}
    
    //扩容策略
    //doublecap:原来容量的两倍
	newcap := old.cap
	doublecap := newcap + newcap
    //如果要扩容的容量比原容量的两倍还要大，那么将要扩容的容量改为指定容量
	if cap > doublecap {
		newcap = cap
	} else {
        //如果旧容量小于1024,那么扩容至原来的两倍
		if old.cap < 1024 {
			newcap = doublecap
		} else {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newcap && newcap < cap {
                //循环 扩容容量=旧容量+旧容量*1/4
				newcap += newcap / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
                //如果溢出 新容量=要扩容的容量
				newcap = cap
			}
		}
	}
	
    //计算新的切片的容量和长度
	var overflow bool
	var lenmem, newlenmem, capmem uintptr
	// Specialize for common values of et.size.
	// For 1 we don't need any division/multiplication.
	// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
	// For powers of 2, use a variable shift.
	switch {
	case et.size == 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	case et.size == sys.PtrSize:
		lenmem = uintptr(old.len) * sys.PtrSize
		newlenmem = uintptr(cap) * sys.PtrSize
        //64位系统 这里sys.PtrSize=8
		capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
		newcap = int(capmem / sys.PtrSize)
	case isPowerOfTwo(et.size):
		var shift uintptr
		if sys.PtrSize == 8 {
			// Mask shift for better code generation.
			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
		} else {
			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
		}
		lenmem = uintptr(old.len) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
	}

	// The check of overflow in addition to capmem > maxAlloc is needed
	// to prevent an overflow which can be used to trigger a segfault
	// on 32bit architectures with this example program:
	//
	// type T [1<<27 + 1]int64
	//
	// var d T
	// var s []T
	//
	// func main() {
	//   s = append(s, d, d, d, d)
	//   print(len(s), "\n")
	// }
	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: cap out of range"))
	}

	var p unsafe.Pointer
	if et.ptrdata == 0 {
		p = mallocgc(capmem, nil, false)
		// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
		// Only clear the part that will not be overwritten.
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
		p = mallocgc(capmem, et, true)
		if lenmem > 0 && writeBarrier.enabled {
			// Only shade the pointers in old.array since we know the destination slice p
			// only contains nil pointers because it has been cleared during alloc.
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
		}
	}
	memmove(p, old.array, lenmem)

	return slice{p, old.len, newcap}
}

roundupsize

假设这边传入的是1600*8=12800，那么size是小于_MaxSmallSize(32768)，进入下一层条件判断，有12800>1024-8，所以进入else，计算(size-smallSizeMax)/largeSizeDiv=(12800-1024+128-1)/128=92,则size_to_class128[92]=57,class_to_size[57]/8=1696

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func roundupsize(size uintptr) uintptr {
	if size < _MaxSmallSize {
		if size <= smallSizeMax-8 {
			return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
		} else {
			return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
		}
	}
	if size+_PageSize < size {
		return size
	}
	return alignUp(size, _PageSize)
}

const (
	_MaxSmallSize   = 32768
	smallSizeDiv    = 8
	smallSizeMax    = 1024
	largeSizeDiv    = 128
	_NumSizeClasses = 68
	_PageShift      = 13
)
1
2
3
4
5
var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}
var class_to_allocnpages = [_NumSizeClasses]uint8{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 2, 3, 1, 3, 2, 3, 4, 5, 6, 1, 7, 6, 5, 4, 3, 5, 7, 2, 9, 7, 5, 8, 3, 10, 7, 4}
var class_to_divmagic = [_NumSizeClasses]uint32{0, ^uint32(0)/8 + 1, ^uint32(0)/16 + 1, ^uint32(0)/24 + 1, ^uint32(0)/32 + 1, ^uint32(0)/48 + 1, ^uint32(0)/64 + 1, ^uint32(0)/80 + 1, ^uint32(0)/96 + 1, ^uint32(0)/112 + 1, ^uint32(0)/128 + 1, ^uint32(0)/144 + 1, ^uint32(0)/160 + 1, ^uint32(0)/176 + 1, ^uint32(0)/192 + 1, ^uint32(0)/208 + 1, ^uint32(0)/224 + 1, ^uint32(0)/240 + 1, ^uint32(0)/256 + 1, ^uint32(0)/288 + 1, ^uint32(0)/320 + 1, ^uint32(0)/352 + 1, ^uint32(0)/384 + 1, ^uint32(0)/416 + 1, ^uint32(0)/448 + 1, ^uint32(0)/480 + 1, ^uint32(0)/512 + 1, ^uint32(0)/576 + 1, ^uint32(0)/640 + 1, ^uint32(0)/704 + 1, ^uint32(0)/768 + 1, ^uint32(0)/896 + 1, ^uint32(0)/1024 + 1, ^uint32(0)/1152 + 1, ^uint32(0)/1280 + 1, ^uint32(0)/1408 + 1, ^uint32(0)/1536 + 1, ^uint32(0)/1792 + 1, ^uint32(0)/2048 + 1, ^uint32(0)/2304 + 1, ^uint32(0)/2688 + 1, ^uint32(0)/3072 + 1, ^uint32(0)/3200 + 1, ^uint32(0)/3456 + 1, ^uint32(0)/4096 + 1, ^uint32(0)/4864 + 1, ^uint32(0)/5376 + 1, ^uint32(0)/6144 + 1, ^uint32(0)/6528 + 1, ^uint32(0)/6784 + 1, ^uint32(0)/6912 + 1, ^uint32(0)/8192 + 1, ^uint32(0)/9472 + 1, ^uint32(0)/9728 + 1, ^uint32(0)/10240 + 1, ^uint32(0)/10880 + 1, ^uint32(0)/12288 + 1, ^uint32(0)/13568 + 1, ^uint32(0)/14336 + 1, ^uint32(0)/16384 + 1, ^uint32(0)/18432 + 1, ^uint32(0)/19072 + 1, ^uint32(0)/20480 + 1, ^uint32(0)/21760 + 1, ^uint32(0)/24576 + 1, ^uint32(0)/27264 + 1, ^uint32(0)/28672 + 1, ^uint32(0)/32768 + 1}
var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32}
var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{32, 33, 34, 35, 36, 37, 37, 38, 38, 39, 39, 40, 40, 40, 41, 41, 41, 42, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 47, 47, 48, 48, 48, 49, 49, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67}

内置的append函数可能使用比appendInt更复杂的内存扩展策略。因此，通常我们并不知道append调用是否导致了内存的重新分配，因此我们也不能确认新的slice和原始的slice是否引用的是相同的底层数组空间。同样，我们不能确认在原先的slice上的操作是否会影响到新的slice。因此，通常是将append返回的结果直接赋值给输入的slice变量,比如x=append(x,y)

Map

在Go语言中，一个map就是一个哈希表的引用，map类型可以写为map[K]V，其中K和V分别对应key和value。map中所有的key都有相同的类型，所有的value也有着相同的类型，但是key和value之间可以是不同的数据类型。其中K对应的key必须是支持==比较运算符的数据类型，所以map可以通过测试key是否相等来判断是否已经存在。虽然浮点数类型也是支持相等运算符比较的，但是将浮点数用做key类型则是一个坏的想法，正如第三章提到的，最坏的情况是可能出现的NaN和任何浮点数都不相等。对于V对应的value数据类型则没有任何的限制。

抽象结构

go/src/cmd/compile/internal/types/type.go

1
2
3
4
5
6
7
8
9

type Map struct {
	Key  *Type // Key type
	Elem *Type // Val (elem) type

	Bucket *Type // internal struct type representing a hash bucket
	Hmap   *Type // internal struct type representing the Hmap (map header object)
	Hiter  *Type // internal struct type representing hash iterator state
}

前两个字段分别位Key和Value，并且支持多种数据类型，Bucket是哈希桶，Hmap是map底层使用的hashtable的原始数据结构，Hiter是用于遍历go map的数据结构。

底层结构

hmap

go中map的底层结构是hamp，结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	count     int //当前map的元素个数
	flags     uint8	//当前map的状态：读，写，扩容等
    // map标记:
    // 1. key和value是否包指针
    // 2. 是否正在扩容
    // 3. 是否是同样大小的扩容
    // 4. 是否正在 `range`方式访问当前的buckets
    // 5. 是否有 `range`方式访问旧的bucket
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)  桶个数为2^B
	noverflow uint16 // 溢出桶个数
	hash0     uint32 // hash种子 用于计算hash值

	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0. 哈希桶首地址
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing 旧哈希桶地址
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated) 已迁移的哈希桶个数

	extra *mapextra // optional fields这个字段是为了优化GC扫描而设计的。当key和value均不包含指针，并且都可以inline时使用，extra是指向mapextra类型的指针。
}

通过该数据结构也可以知道，map在作为函数传参的时候，实际传递的是一个指针。直接看下面这个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
func main(){		
	m := make(map[string]string, 3)
	m["test"] = "fail"
	fmt.Printf("%#v\n", m)
	fmt.Printf("原map的内存地址是：%p\n", m)
	m=update(m)
	fmt.Printf("%#v\n", m)
	fmt.Printf("修改后map的内存地址是：%p\n", m)
}

func update(m map[string]string) {
	m["test"] = "success"
}

输出为：

bmap

bmap就是bucket map，它是桶bucket的底层结构，但是在go的源码中并没有显示的定义，下面的结构体中中只是存储了一个tophash。

1
2
3
4
5
type bmap struct {
	//tophash 此桶中每个键的值的哈希值最高字节的高8位信息，用来在每一个桶中区别出键。
    //如果tophash[0]<minTopHash,那么tophash[0]就表示该桶的搬迁(evacuation)状态。
	tophash [bucketCnt]uint8
}

根据src/cmd/compile/internal/reflectdata/reflect.go可以还原出bmap的结构：

1
2
3
4
5
6
type bmap struct {
    topbits  [8]uint8	//hash值的高8位
    keys     [8]keytype	//存放哈希桶中所有的键
    elems    [8]elemtype	//存放哈希桶中所有的值
    overflow uintptr	//overflow是一个uintptr类型的指针，存放了指向溢出桶的地址
}

这里需要注意的是为了保证内存对齐，键值对并不是连续存储的，由此我们可以得到一个bucket的抽象内存模型:

mapextra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// mapextra holds fields that are not present on all maps.
type mapextra struct {
	// 如果 key 和 value 都不包含指针，并且可以被 inline(<=128 字节)
	// 就使用 hmap的extra字段 来存储 overflow buckets，这样可以避免 GC 扫描整个 map
	// 然而 bmap.overflow 也是个指针。这时候我们只能把这些 overflow 的指针
	// 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
	// overflow 包含的是 hmap.buckets 的 overflow 的指针
	// oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的指针
	overflow    *[]*bmap 
	oldoverflow *[]*bmap 

	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap //指向下一个溢出桶
}

这边需要注意一个问题，当key和elem的长度超过128的时候，go在map中会使用指针存储，如下代码：

1
2
3
4
5
6
if keytype.Width > MAXKEYSIZE {
   keytype = types.NewPtr(keytype)
}
if elemtype.Width > MAXELEMSIZE {
   elemtype = types.NewPtr(elemtype)
}

而当一个bmap的key和elem的长度都没有超过128的时候，该map的bucket类型会被标注为不含指针，这样GC将不会扫描到该map，这样就会出现问题，因为bucket的底层结构bmap中含有一个指向溢出桶的uintptr类型的指针，不能保证该指针指向的内存区域不会被GC给清理掉，因为GC不扫描bmap结构，就会导致该指针指向的内存区域被GC给清理掉。因此Go在hmap中新增了一个mapextra字段，其中的overflow是一个指向保存所有hamp.buckets的溢出桶地址的slice指针，oldoverflow是指向保存所有hamp.oldbuckets的溢出桶地址的slice指针。并且只有当map的key和elem都不含之争的时候这两个字段才会有效，因此mapextra的设置就是为了解决因为map没有没有被GC扫描掉而导致相关内存被GC释放的问题，当map的key和elem字段是指针的时候，GC会扫描map，也就知道了bmap中指针指向的内存区域是有被引用的，也就不会释放相应的内存。

由此，现在可以得到一个Go的map结构图：

hiter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 遍历map
type hiter struct {
	key         unsafe.Pointer // Must be in first position.  Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go).
	elem        unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go).
	t           *maptype
	h           *hmap
	buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
	bptr        *bmap          // current bucket
	overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
	oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
	startBucket uintptr        // bucket iteration started at
	offset      uint8          // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1)
	wrapped     bool           // already wrapped around from end of bucket array to beginning
	B           uint8
	i           uint8
	bucket      uintptr
	checkBucket uintptr
}

三色灯控制实现

http://caixindi.github.io/Golang/三色灯控制实现/

作者

Cindy

发布于

2021-12-03

许可协议

CC BY-NC-SA 4.0

#
关注我

目录

分类

标签

CS217 Lecture4
EdgeX平台构建1
EdgeX机器学习以及推理3
EdgeX构建5
EdgeX概念2
EdgeX部署2
Git使用指南1
Golang圣经4
Java并发编程6
Java知识点7
Linux知识点1
Redis2
docker部署1
kubeedge1
kubeedge example1
kubeflow1
好看的PowerShell1
快速傅里叶变换1
智能计算系统学习8
暗硅1
深度神经网络的高效处理：教程和综述1
硬件加速背景以及卷积神经网络优化1
神经网络与深度学习5
粗粒度可重构体系结构与Plasticine1
虚拟化1
计算机组成与体系结构2
轻量级神经网络加速1
高性能矩阵乘法剖析1
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×