go语言中的bit go语言中的函数
golang 实现bitmap
type bitmap struct {
东至网站建设公司创新互联公司,东至网站设计制作，有大型网站制作公司丰富经验。已为东至成百上千提供企业网站建设服务。企业网站搭建\成都外贸网站制作要多少钱，请找那个售后服务好的东至做网站的公司定做！
keys []byte
len int
}
func NewBitMap() *bitmap {
return bitmap{keys:make([]byte, 0), len:0}
}
func (b *bitmap)has(v int) bool {
k := v /8
kv :=byte(v %8)
if k len(b.keys) { //todo not exist
return false
}
if b.keys[k](1kv) != 0 {
return true
}
return false
}
func (b *bitmap)set(v int) {
k := v /8
kv :=byte(v %8)
for b.len = k {
b.keys =append(b.keys, 0)
b.len++
}
b.keys[k] =b.keys[k] | (1 kv)
}
func (b *bitmap)length()int {
return b.len
}
func (b *bitmap)print() {
for _, v :=range b.keys {
fmt.Printf("%08b\n", v)
}
}
（十一）golang 内存分析
编写过C语言程序的肯定知道通过malloc()方法动态申请内存，其中内存分配器使用的是glibc提供的ptmalloc2。 除了glibc，业界比较出名的内存分配器有Google的tcmalloc和Facebook的jemalloc。二者在避免内存碎片和性能上均比glic有比较大的优势，在多线程环境中效果更明显。
Golang中也实现了内存分配器，原理与tcmalloc类似，简单的说就是维护一块大的全局内存，每个线程(Golang中为P)维护一块小的私有内存，私有内存不足再从全局申请。另外，内存分配与GC（垃圾回收）关系密切，所以了解GC前有必要了解内存分配的原理。
为了方便自主管理内存，做法便是先向系统申请一块内存，然后将内存切割成小块，通过一定的内存分配算法管理内存。 以64位系统为例，Golang程序启动时会向系统申请的内存如下图所示：
预申请的内存划分为spans、bitmap、arena三部分。其中arena即为所谓的堆区，应用中需要的内存从这里分配。其中spans和bitmap是为了管理arena区而存在的。
arena的大小为512G，为了方便管理把arena区域划分成一个个的page，每个page为8KB,一共有512GB/8KB个页；
spans区域存放span的指针，每个指针对应一个page，所以span区域的大小为(512GB/8KB)乘以指针大小8byte = 512M
bitmap区域大小也是通过arena计算出来，不过主要用于GC。
span是用于管理arena页的关键数据结构，每个span中包含1个或多个连续页，为了满足小对象分配，span中的一页会划分更小的粒度，而对于大对象比如超过页大小，则通过多页实现。
根据对象大小，划分了一系列class，每个class都代表一个固定大小的对象，以及每个span的大小。如下表所示：
上表中每列含义如下：
class： class ID，每个span结构中都有一个class ID, 表示该span可处理的对象类型
bytes/obj：该class代表对象的字节数
bytes/span：每个span占用堆的字节数，也即页数乘以页大小
objects: 每个span可分配的对象个数，也即（bytes/spans）/（bytes/obj）waste
bytes: 每个span产生的内存碎片，也即（bytes/spans）%（bytes/obj）上表可见最大的对象是32K大小，超过32K大小的由特殊的class表示，该class ID为0，每个class只包含一个对象。
span是内存管理的基本单位,每个span用于管理特定的class对象, 跟据对象大小，span将一个或多个页拆分成多个块进行管理。src/runtime/mheap.go:mspan定义了其数据结构：
以class 10为例，span和管理的内存如下图所示：
spanclass为10，参照class表可得出npages=1,nelems=56,elemsize为144。其中startAddr是在span初始化时就指定了某个页的地址。allocBits指向一个位图，每位代表一个块是否被分配，本例中有两个块已经被分配，其allocCount也为2。next和prev用于将多个span链接起来，这有利于管理多个span，接下来会进行说明。
有了管理内存的基本单位span，还要有个数据结构来管理span，这个数据结构叫mcentral，各线程需要内存时从mcentral管理的span中申请内存，为了避免多线程申请内存时不断的加锁，Golang为每个线程分配了span的缓存，这个缓存即是cache。src/runtime/mcache.go:mcache定义了cache的数据结构
alloc为mspan的指针数组，数组大小为class总数的2倍。数组中每个元素代表了一种class类型的span列表，每种class类型都有两组span列表，第一组列表中所表示的对象中包含了指针，第二组列表中所表示的对象不含有指针，这么做是为了提高GC扫描性能，对于不包含指针的span列表，没必要去扫描。根据对象是否包含指针，将对象分为noscan和scan两类，其中noscan代表没有指针，而scan则代表有指针，需要GC进行扫描。mcache和span的对应关系如下图所示：
mchache在初始化时是没有任何span的，在使用过程中会动态的从central中获取并缓存下来，跟据使用情况，每种class的span个数也不相同。上图所示，class 0的span数比class1的要多，说明本线程中分配的小对象要多一些。
cache作为线程的私有资源为单个线程服务，而central则是全局资源，为多个线程服务，当某个线程内存不足时会向central申请，当某个线程释放内存时又会回收进central。src/runtime/mcentral.go:mcentral定义了central数据结构：
lock: 线程间互斥锁，防止多线程读写冲突
spanclass : 每个mcentral管理着一组有相同class的span列表
nonempty: 指还有内存可用的span列表
empty: 指没有内存可用的span列表
nmalloc: 指累计分配的对象个数线程从central获取span步骤如下：
将span归还步骤如下：
从mcentral数据结构可见，每个mcentral对象只管理特定的class规格的span。事实上每种class都会对应一个mcentral,这个mcentral的集合存放于mheap数据结构中。src/runtime/mheap.go:mheap定义了heap的数据结构：
lock： 互斥锁
spans: 指向spans区域，用于映射span和page的关系
bitmap：bitmap的起始地址
arena_start: arena区域首地址
arena_used: 当前arena已使用区域的最大地址
central: 每种class对应的两个mcentral
从数据结构可见，mheap管理着全部的内存，事实上Golang就是通过一个mheap类型的全局变量进行内存管理的。mheap内存管理示意图如下：
系统预分配的内存分为spans、bitmap、arean三个区域，通过mheap管理起来。接下来看内存分配过程。
针对待分配对象的大小不同有不同的分配逻辑：
(0, 16B) 且不包含指针的对象： Tiny分配
(0, 16B) 包含指针的对象：正常分配
[16B, 32KB] : 正常分配
(32KB, -) : 大对象分配其中Tiny分配和大对象分配都属于内存管理的优化范畴，这里暂时仅关注一般的分配方法。
以申请size为n的内存为例，分配步骤如下：
Golang内存分配是个相当复杂的过程，其中还掺杂了GC的处理，这里仅仅对其关键数据结构进行了说明，了解其原理而又不至于深陷实现细节。1、Golang程序启动时申请一大块内存并划分成spans、bitmap、arena区域
2、arena区域按页划分成一个个小块。
3、span管理一个或多个页。
4、mcentral管理多个span供线程申请使用
5、mcache作为线程私有资源，资源来源于mcentral。
go程序如何分配堆栈的
在Go语言中有一些调试技巧能帮助我们快速找到问题，有时候你想尽可能多的记录异常但仍觉得不够，搞清楚堆栈的意义有助于定位Bug或者记录更完整的信息。
本文将讨论堆栈跟踪信息以及如何在堆栈中识别函数所传递的参数。
Functions
先从这段代码开始：
Listing 1
01 package main
02
03 func main() {
04 slice := make([]string, 2, 4)
05 Example(slice, "hello", 10)
06 }
07
08 func Example(slice []string, str string, i int) {
09 panic("Want stack trace")
10 }
Example函数定义了3个参数，1个string类型的slice, 1个string和1个integer, 并且抛出了panic，运行这段代码可以看到这样的结果：
Listing 2
Panic: Want stack trace
goroutine 1 [running]:
main.Example(0x2080c3f50, 0x2, 0x4, 0x425c0, 0x5, 0xa)
/Users/bill/Spaces/Go/Projects/src/github点抗 /goinaction/code/
temp/main.go:9 +0x64
main.main()
/Users/bill/Spaces/Go/Projects/src/github点抗 /goinaction/code/
temp/main.go:5 +0x85
goroutine 2 [runnable]:
runtime.forcegchelper()
/Users/bill/go/src/runtime/proc.go:90
runtime.goexit()
/Users/bill/go/src/runtime/asm_amd64.s:2232 +0x1
goroutine 3 [runnable]:
runtime.bgsweep()
/Users/bill/go/src/runtime/mgc0.go:82
runtime.goexit()
/Users/bill/go/src/runtime/asm_amd64.s:2232 +0x1
堆栈信息中显示了在panic抛出这个时间所有的goroutines状态，发生的panic的goroutine会显示在最上面。
Listing 3
01 goroutine 1 [running]:
02 main.Example(0x2080c3f50, 0x2, 0x4, 0x425c0, 0x5, 0xa)
/Users/bill/Spaces/Go/Projects/src/github点抗 /goinaction/code/
temp/main.go:9 +0x64
03 main.main()
/Users/bill/Spaces/Go/Projects/src/github点抗 /goinaction/code/
temp/main.go:5 +0x85
第1行显示最先发出panic的是goroutine 1, 第二行显示panic位于main.Example中, 并能定位到该行代码，在本例中第9行引发了panic。
下面我们关注参数是如何传递的：
Listing 4
// Declaration
main.Example(slice []string, str string, i int)
// Call to Example by main.
slice := make([]string, 2, 4)
Example(slice, "hello", 10)
// Stack trace
main.Example(0x2080c3f50, 0x2, 0x4, 0x425c0, 0x5, 0xa)
这里展示了在main中带参数调用Example函数时的堆栈信息，比较就能发现两者的参数数量并不相同，Example定义了3个参数，堆栈中显示了6个参数。现在的关键问题是我们要弄清楚它们是如何匹配的。
第1个参数是string类型的slice，我们知道在Go语言中slice是引用类型，即slice变量结构会包含三个部分：指针、长度(Lengthe)、容量(Capacity)
Listing 5
// Slice parameter value
slice := make([]string, 2, 4)
// Slice header values
Pointer: 0x2080c3f50
Length: 0x2
Capacity: 0x4
// Declaration
main.Example(slice []string, str string, i int)
// Stack trace
main.Example(0x2080c3f50, 0x2, 0x4, 0x425c0, 0x5, 0xa)
因此，前面3个参数会匹配slice， 如下图所示：
Figure 1
figure provided by Georgi Knox
我们现在来看第二个参数，它是string类型，string类型也是引用类型，它包括两部分：指针、长度。
Listing 6
// String parameter value
"hello"
// String header values
Pointer: 0x425c0
Length: 0x5
// Declaration
main.Example(slice []string, str string, i int)
// Stack trace
main.Example(0x2080c3f50, 0x2, 0x4, 0x425c0, 0x5, 0xa)
可以确定，堆栈信息中第4、5两个参数对应代码中的string参数，如下图所示：
Figure 2
figure provided by Georgi Knox
最后一个参数integer是single word值。
Listing 7
// Integer parameter value
10
// Integer value
Base 16: 0xa
// Declaration
main.Example(slice []string, str string, i int)
// Stack trace
main.Example(0x2080c3f50, 0x2, 0x4, 0x425c0, 0x5, 0xa)
现在我们可以匹配代码中的参数到堆栈信息了。
Figure 3
figure provided by Georgi Knox
Methods
如果我们将Example作为结构体的方法会怎么样呢?
Listing 8
01 package main
02
03 import "fmt"
04
05 type trace struct{}
06
07 func main() {
08 slice := make([]string, 2, 4)
09
10 var t trace
11 t.Example(slice, "hello", 10)
12 }
13
14 func (t *trace) Example(slice []string, str string, i int) {
15 fmt.Printf("Receiver Address: %p\n", t)
16 panic("Want stack trace")
17 }
如上所示修改代码，将Example定义为trace的方法，并通过trace的实例t来调用Example。
再次运行程序，会发现堆栈信息有一点不同：
Listing 9
Receiver Address: 0x1553a8
panic: Want stack trace
01 goroutine 1 [running]:
02 main.(*trace).Example(0x1553a8, 0x2081b7f50, 0x2, 0x4, 0xdc1d0, 0x5, 0xa)
/Users/bill/Spaces/Go/Projects/src/github点抗 /goinaction/code/
temp/main.go:16 +0x116
03 main.main()
/Users/bill/Spaces/Go/Projects/src/github点抗 /goinaction/code/
temp/main.go:11 +0xae
首先注意第2行的方法调用使用了pointer receiver，在package名字和方法名之间多出了"*trace"字样。另外，参数列表的第1个参数标明了结构体(t)地址。我们从堆栈信息中看到了内部实现细节。
Packing
如果有多个参数可以填充到一个single word, 则这些参数值会合并打包：
Listing 10
01 package main
02
03 func main() {
04 Example(true, false, true, 25)
05 }
06
07 func Example(b1, b2, b3 bool, i uint8) {
08 panic("Want stack trace")
09 }
这个例子修改Example函数为4个参数：3个bool型和1个八位无符号整型。bool值也是用8个bit表示，所以在32位和64位架构下，4个参数可以合并为一个single word。
Listing 11
01 goroutine 1 [running]:
02 main.Example(0x19010001)
/Users/bill/Spaces/Go/Projects/src/github点抗 /goinaction/code/
temp/main.go:8 +0x64
03 main.main()
/Users/bill/Spaces/Go/Projects/src/github点抗 /goinaction/code/
temp/main.go:4 +0x32
这是本例的堆栈信息，看下图的具体分析：
Listing 12
// Parameter values
true, false, true, 25
// Word value
Bits Binary Hex Value
00-07 0000 0001 01 true
08-15 0000 0000 00 false
16-23 0000 0001 01 true
24-31 0001 1001 19 25
// Declaration
main.Example(b1, b2, b3 bool, i uint8)
// Stack trace
main.Example(0x19010001)
以上展示了参数值是如何匹配到4个参数的。当我们看到堆栈信息中包括十六进制值，需要知道这些值是如何传递的。
文章题目：go语言中的bit go语言中的函数
网址分享：http://azwzsj.com/article/ddigode.html
