# [转]Go Data Structures

When explaining Go to new programmers, I’ve found that it often helps to explain what Go values look like in memory, to build the right intuition about which operations are expensive and which are not. This post is about basic types, structs, arrays, and slices.

## Basic types

The variable i has type int, represented in memory as a single 32-bit word. (All these pictures show a 32-bit memory layout; in the current implementations, only the pointer gets bigger on a 64-bit machine—int is still 32 bits—though an implementation could choose to use 64 bits instead.)

The variable j has type int32, because of the explicit conversion. Even though i and j have the same memory layout, they have different types: the assignment i = j is a type error and must be written with an explicit conversion: i = int(j).

The variable f has type float, which the current implementations represent as a 32-bit floating-point value. It has the same memory footprint as the int32 but a different internal layout.

## Structs and pointers

Now things start to pick up. The variable bytes has type [5]byte, an array of 5 bytes. Its memory representation is just those 5 bytes, one after the other, like a C array. Similarly, primesis an array of 4 ints.

Go, like C but unlike Java, gives the programmer control over what is and is not a pointer. For example, this type definition:

```type Point struct { X, Y int }
```

defines a simple struct type named Point, represented as two adjacent ints in memory.

The composite literal syntax Point{10, 20} denotes an initialized Point. Taking the address of a composite literal denotes a pointer to a freshly allocated and initialized Point. The former is two words in memory; the latter is a pointer to two words in memory.

Fields in a struct are laid out side by side in memory.

```type Rect1 struct { Min, Max Point }
type Rect2 struct { Min, Max *Point }```

Rect1, a struct with two Point fields, is represented by two Points—four ints—in a row. Rect2, a struct with two *Point fields, is represented by two *Points.

Programmers who have used C probably won’t be surprised by the distinction between Point fields and *Point fields, while programmers who have only used Java or Python (or …) may be surprised by having to make the decision. By giving the programmer control over basic memory layout, Go provides the ability to control the total size of a given collection of data structures, the number of allocations, and the memory access patterns, all of which are important for building systems that perform well.

## Strings

With those preliminaries, we can move on to more interesting data types.

(The gray arrows denote pointers that are present in the implementation but not directly visible in programs.)

A string is represented in memory as a 2-word structure containing a pointer to the string data and a length. Because the string is immutable, it is safe for multiple strings to share the same storage, so slicing s results in a new 2-word structure with a potentially different pointer and length that still refers to the same byte sequence. This means that slicing can be done without allocation or copying, making string slices as efficient as passing around explicit indexes.

(As an aside, there is a well-known gotcha in Java and other languages that when you slice a string to save a small piece, the reference to the original keeps the entire original string in memory even though only a small amount is still needed. Go has this gotcha too. The alternative, which we tried and rejected, is to make string slicing so expensive—an allocation and a copy—that most programs avoid it.)

## Slices

A slice is a reference to a section of an array. In memory, it is a 3-word structure contaning a pointer to the first element, the length of the slice, and the capacity. The length is the upper bound for indexing operations like x[i] while the capacity is the upper bound for slice operations like x[i:j].

Like slicing a string, slicing an array does not make a copy: it only creates a new structure holding a different pointer, length, and capacity. In the example, evaluating the composite literal[]int{2, 3, 5, 7, 11} creates a new array containing the five values and then sets the fields of the slice x to describe that array. The slice expression x[1:3] does not allocate more data: it just writes the fields of a new slice structure to refer to the same backing store. In the example, the length is 2—y[0] and y[1] are the only valid indexes—but the capacity is 4—y[0:4] is a valid slice expression. (See Effective Go for more about length and capacity and how slices are used.)

Because slices are multiword structures, not pointers, the slicing operation does not need to allocate memory, not even for the slice header, which can usually be kept on the stack. This representation makes slices about as cheap to use as passing around explicit pointer and length pairs in C. Go originally represented a slice as a pointer to the structure shown above, but doing so meant that every slice operation allocated a new memory object. Even with a fast allocator, that creates a lot of unnecessary work for the garbage collector, and we found that, as was the case with strings above, programs avoided slicing operations in favor of passing explicit indices. Removing the indirection and the allocation made slices cheap enough to avoid passing explicit indices in most cases.

## New and Make

Go has two data structure creation functions: new and make. The distinction is a common early point of confusion but seems to quickly become natural. The basic distinction is thatnew(T) returns a *T, a pointer that Go programs can dereference implicitly (the black pointers in the diagrams), while make(T, args) returns an ordinary T, not a pointer. Often that T has inside it some implicit pointers (the gray pointers in the diagrams). New returns a pointer to zeroed memory, while make returns a complex structure.

There is a way to unify these two, but it would be a significant break from the C and C++ tradition: define make(*T) to return a pointer to a newly allocated T, so that the currentnew(Point) would be written make(*Point). We tried this for a few days but decided it was too different from what people expected of an allocation function.

## Coming soon…

This has already gotten a bit long. Interface values, maps, and channels will have to wait for future posts.

# [转]GC学习笔记

1、垃圾回收器的特性
2、对垃圾回收器的选择
2.1 连续 VS. 并行
2.2 并发 VS. stop-the-world
2.3 压缩 VS. 不压缩 VS. 复制

### 1. GC特性以及各种GC的选择

#### 1.3 并发 VS. stop-the-world

stop the world 的GC相对简单，因为heap被冻结，对象的活动也已经停止。但缺点是可能不太满足对实时性要求很高的应用。

### 2. GC性能指标

GC负荷 与吞吐量相反，指应用花在GC上的时间百分比

GC频率 顾名思义
Footprint 一些资源大小的测量，比如堆的大小

### 4. J2SE 5.0的HotSpot JVM上的GC学习 – 分代、GC类型、快速分配

J2SE5.0 update 6 的HotSpot上有4个GC。

#### 4.2 年轻代

survivor区里面放至少熬过一个YGC的对象，在survivor里面的对象，才有机会被考虑提升到年老代中。

### 5. J2SE 5.0的HotSpot JVM上的GC学习 – SerialGC

#### 5.1 串行GC

##### 5.1.2 old区的串行GC

mark阶段是对有引用的对象进行标识
sweep是对垃圾进行清理
compact对把活着的对象进行迁移，解决内存碎片的问题

### 6. J2SE 5.0的HotSpot JVM上的GC学习 – ParallelGC

#### 6.2 YGC的并行GC

YGC的情况，还是使用stop-the-world + 复制算法的GC。

### 7. J2SE 5.0的HotSpot JVM上的GC学习 – ParallelCompactingGC

#### 7.1 Parallel Compacting GC

parallelCompactingGC是在J2SE5.0 update6 引入的。
parallel compacting GC 与 parallel GC的不同地方，是在年老区的收集使用了一个新的算法。并且以后，parallel compacting GC 会取代 parallem GC的。

### 8. J2SE 5.0的HotSpot JVM上的GC学习 – CMS GC

#### 8.1 Concurrent mark sweep GC

YGC并不暂停多少时间，但FGC对时间的暂用还是很长的。特别是在年老区使用的空间较多时。

#### 8.3 CMS的FGC

CMS的FGC在大部分是和应用程序一起并发的！
CMS在FGC的时候，一开始需要做一个短暂的暂停，这个阶段称为最初标记：识别所有被引用的对象。

CMS是唯一没有进行压缩的GC。如下图：

CMS的另一个缺点，就是他需要的堆比较大，因为在并发标记的时候和并发清除的时候，应用程序很有可能在不断产生新的对象，而垃圾又还没有被删除。

n是一个百分比，默认值为68。

### 9. 结合线上启动参数学习

-Dprogram.name=run.sh -Xmx2g -Xms2g -Xmn256m -XX:PermSize=128m -Xss256k -XX:+DisableExplicitGC -XX:+UseConcMarkSweepGC -XX:+CMSParallelRemarkEnabled -XX:+UseCMSCompactAtFullCollection -XX:LargePageSizeInBytes=128m -XX:+UseFastAccessorMethods -XX:+UseCMSInitiatingOccupancyOnly -XX:CMSInitiatingOccupancyFraction=70 -Djava.awt.headless=true -Djava.net.preferIPv4Stack=true -Dcom.sun.management.config.file=/home/admin/web-deploy/conf/jmx/jmx_monitor_management.properties -Djboss.server.home.dir=/home/admin/web-deploy/jboss_server -Djboss.server.home.url=file\:/home/admin/web-deploy/jboss_server -Dapplication.codeset=GBK -Ddatabase.codeset=ISO-8859-1 -Ddatabase.logging=false -Djava.endorsed.dirs=/usr/alibaba/jboss/lib/endorsed

-Xmx2g -Xms2g 表示堆为2G
-Xmn256m 表示新生代为 256m
-Xss256k 设置每个线程的堆栈大小。JDK5.0以后每个线程堆栈大小为1M，以前每个线程堆栈大小为256K。更具应用的线程所需内存大小进行调整。在相同物理内存下，减小这个值能生成更多的线程。但是操作系统对一个进程内的线程数还是有限制的，不能无限生成，经验值在3000~5000左右
-XX:PermSize=128m 表示永久区为128m
-XX:+DisableExplicitGC 禁用显示的gc，程序程序中使用System.gc()中进行垃圾回收，使用这个参数后系统自动将 System.gc() 调用转换成一个空操作
-XX:+UseConcMarkSweepGC 表示使用CMS
-XX:+CMSParallelRemarkEnabled 表示并行remark
-XX:+UseCMSCompactAtFullCollection 表示在FGC之后进行压缩，因为CMS默认不压缩空间的。
-XX:+UseCMSInitiatingOccupancyOnly 表示只在到达阀值的时候，才进行CMS GC
-XX:CMSInitiatingOccupancyFraction=70 设置阀值为70%，默认为68%。
-XX:+UseCompressedOops JVM优化之压缩普通对象指针（CompressedOops），通常64位JVM消耗的内存会比32位的大1.5倍，这是因为对象指针在64位架构下，长度会翻倍（更宽的寻址）。对于那些将要从32位平台移植到64位的应用来说，平白无辜多了1/2的内存占用，这是开发者不愿意看到的。幸运的是，从JDK 1.6 update14开始，64 bit JVM正式支持了 -XX:+UseCompressedOops 这个可以压缩指针，起到节约内存占用的新参数.

The concurrent collection generally cannot be sped up but it can be started earlier.
A concurrent collection starts running when the percentage of allocated space in the old generation crosses a threshold. This threshold is calculated based on general experience with the concurrent collector. If full collections are occurring, the concurrent collections may need to be started earlier. The command line flag CMSInitiatingOccupancyFraction can be used to set the level at which the collection is started. Its default value is approximately 68%. The command line to adjust the value is
-XX:CMSInitiatingOccupancyFraction= The concurrent collector also keeps statistics on the promotion rate into the old generation for the application and makes a prediction on when to start a concurrent collection based on that promotion rate and the available free space in the old generation. Whereas the use of CMSInitiatingOccupancyFraction must be conservative to avoid full collections over the life of the application, the start of a concurrent collection based on the anticipated promotion adapts to the changing requirements of the application. The statistics that are used to calculate the promotion rate are based on the recent concurrent collections. The promotion rate is not calculated until at least one concurrent collection has completed so at least the first concurrent collection has to be initiated because the occupancy has reached CMSInitiatingOccupancyFraction . Setting CMSInitiatingOccupancyFraction to 100 would not cause only the anticipated promotion to be used to start a concurrent collection but would rather cause only non-concurrent collections to occur since a concurrent collection would not start until it was already too late. To eliminate the use of the anticipated promotions to start a concurrent collection set UseCMSInitiatingOccupancyOnly to true.
-XX:+UseCMSInitiatingOccupancyOnly

# [转]The Go scheduler

One of the big features for Go 1.1 is the new scheduler, contributed by Dmitry Vyukov. The new scheduler has given a dramatic increase in performance for parallel Go programs and with nothing better to do, I figured I’d write something about it.

Most of what’s written in this blog post is already described in the original design doc. It’s a fairly comprehensive document, but pretty technical.

All you need to know about the new scheduler is in that design document but this post has pictures, so it’s clearly superior.

# What does the Go runtime need with a scheduler?

But before we look at the new scheduler, we need to understand why it’s needed. Why create a userspace scheduler when the operating system can schedule threads for you?

The POSIX thread API is very much a logical extension to the existing Unix process model and as such, threads get a lot of the same controls as processes. Threads have their own signal mask, can be assigned CPU affinity, can be put into cgroups and can be queried for which resources they use. All these controls add overhead for features that are simply not needed for how Go programs use goroutines and they quickly add up when you have 100,000 threads in your program.

Another problem is that the OS can’t make informed scheduling decisions, based on the Go model. For example, the Go garbage collector requires that all threads are stopped when running a collection and that memory must be in a consistent state. This involves waiting for running threads to reach a point where we know that the memory is consistent.

When you have many threads scheduled out at random points, chances are that you’re going to have to wait for a lot of them to reach a consistent state. The Go scheduler can make the decision of only scheduling at points where it knows that memory is consistent. This means that when we stop for garbage collection, we only have to wait for the threads that are being actively run on a CPU core.

# Our Cast of Characters

There are 3 usual models for threading. One is N:1 where several userspace threads are run on one OS thread. This has the advantage of being very quick to context switch but cannot take advantage of multi-core systems. Another is 1:1 where one thread of execution matches one OS thread. It takes advantage of all of the cores on the machine, but context switching is slow because it has to trap through the OS.

Go tries to get the best of both worlds by using a M:N scheduler. It schedules an arbitrary number of goroutines onto an arbitrary number of OS threads. You get quick context switches and you take advantage of all the cores in your system. The main disadvantage of this approach is the complexity it adds to the scheduler.

To acomplish the task of scheduling, the Go Scheduler uses 3 main entities:

The triangle represents an OS thread. It’s the thread of execution managed by the OS and works pretty much like your standard POSIX thread. In the runtime code, it’s called M for machine.

The circle represents a goroutine. It includes the stack, the instruction pointer and other information important for scheduling goroutines, like any channel it might be blocked on. In the runtime code, it’s called a G.

The rectangle represents a context for scheduling. You can look at it as a localized version of the scheduler which runs Go code on a single thread. It’s the important part that lets us go from a N:1 scheduler to a M:N scheduler. In the runtime code, it’s called P for processor. More on this part in a bit.

Here we see 2 threads (M), each holding a context (P), each running a goroutine (G). In order to run goroutines, a thread must hold a context.

The number of contexts is set on startup to the value of the GOMAXPROCS environment variable or through the runtime function GOMAXPROCS(). Normally this doesn’t change during execution of your program. The fact that the number of contexts is fixed means that only GOMAXPROCS are running Go code at any point. We can use that to tune the invocation of the Go process to the individual computer, such at a 4 core PC is running Go code on 4 threads.

The greyed out goroutines are not running, but ready to be scheduled. They’re arranged in lists called runqueues. Goroutines are added to the end of a runqueue whenever a goroutine executes a go statement. Once a context has run a goroutine until a scheduling point, it pops a goroutine off its runqueue, sets stack and instruction pointer and begins running the goroutine.

To bring down mutex contention, each context has its own local runqueue. A previous version of the Go scheduler only had a global runqueue with a mutex protecting it. Threads were often blocked waiting for the mutex to unlocked. This got really bad when you had 32 core machines that you wanted to squeeze as much performance out of as possible.

The scheduler keeps on scheduling in this steady state as long as all contexts have goroutines to run. However, there are a couple of scenarios that can change that.

# Who you gonna (sys)call?

You might wonder now, why have contexts at all? Can’t we just put the runqueues on the threads and get rid of contexts? Not really. The reason we have contexts is so that we can hand them off to other threads if the running thread needs to block for some reason.

An example of when we need to block, is when we call into a syscall. Since a thread cannot both be executing code and be blocked on a syscall, we need to hand off the context so it can keep scheduling.

Here we see a thread giving up its context so that another thread can run it. The scheduler makes sure there are enough threads to run all contexts. M1 in the illustration above might be created just for the purpose of handling this syscall or it could come from a thread cache. The syscalling thread will hold on to the goroutine that made the syscall since it’s technically still executing, albeit blocked in the OS.

When the syscall returns, the thread must try and get a context in order to run the returning goroutine. The normal mode of operation is to steal a context from one of the other threads. If it can’t steal one, it will put the goroutine on a global runqueue, put itself on the thread cache and go to sleep.

The global runqueue is a runqueue that contexts pull from when they run out of their local runqueue. Contexts also periodically check the global runqueue for goroutines. Otherwise the goroutines on global runqueue could end up never running because of starvation.

This handling of syscalls is why Go programs run with multiple threads, even when GOMAXPROCS is 1. The runtime uses goroutines that call syscalls, leaving threads behind.

# Stealing work

Another way that the steady state of the system can change is when a context runs out of goroutines to schedule to. This can happen if the amount of work on the contexts’ runqueues is unbalanced. This can cause a context to end up exhausting it’s runqueue while there is still work to be done in the system. To keep running Go code, a context can take goroutines out of the global runqueue but if there are no goroutines in it, it’ll have to get them from somewhere else.

That somewhere is the other contexts. When a context runs out, it will try to steal about half of the runqueue from another context. This makes sure there is always work to do on each of the contexts, which in turn makes sure that all threads are working at their maximum capacity.

# Where to go?

There are many more details to the scheduler, like cgo threads, the LockOSThread() function and integration with the network poller. These are outside the scope of this post, but still merit study. I might write about these later. There are certainly plenty of interesting constructions to be found in the Go runtime library.

# [转]How to write benchmarks in Go

This post continues a series on the testing package I started a few weeks back. You can read the previous article on writing table driven tests here. You can find the code mentioned below in the https://github.com/davecheney/fib repository.

Introduction

The Go testing package contains a benchmarking facility that can be used to examine the performance of your Go code. This post explains how to use the testing package to write a simple benchmark.

You should also review the introductory paragraphs of Profiling Go programs, specifically the section on configuring power management on your machine. For better or worse, modern CPUs rely heavily on active thermal management which can add noise to benchmark results.

Writing a benchmark

We’ll reuse the Fib function from the previous article.

 123456 func Fib(n int) int {         if n < 2 {                 return n         }         return Fib(n-1) + Fib(n-2) }

Benchmarks are placed inside _test.go files and follow the rules of their Test counterparts. In this first example we’re going to benchmark the speed of computing the 10th number in the Fibonacci series.

 1234567 // from fib_test.go func BenchmarkFib10(b *testing.B) {         // run the Fib function b.N times         for n := 0; n < b.N; n++ {                 Fib(10)         } }

Writing a benchmark is very similar to writing a test as they share the infrastructure from the testing package. Some of the key differences are

Benchmark functions are run several times by the testing package. The value of b.N will increase each time until the benchmark runner is satisfied with the stability of the benchmark. This has some important ramifications which we’ll investigate later in this article.
Each benchmark must execute the code under test b.N times. The for loop in BenchmarkFib10 will be present in every benchmark function.

Running benchmarks

Now that we have a benchmark function defined in the tests for the fib package, we can invoke it with go test -bench=.

 1234 % go test -bench=. PASS BenchmarkFib10   5000000               509 ns/op ok      github.com/davecheney/fib       3.084s

Breaking down the text above, we pass the -bench flag to go test supplying a regular expression matching everything. You must pass a valid regex to -bench, just passing -bench is a syntax error. You can use this property to run a subset of benchmarks.

The first line of the result, PASS, comes from the testing portion of the test driver, asking go test to run your benchmarks does not disable the tests in the package. If you want to skip the tests, you can do so by passing a regex to the -run flag that will not match anything. I usually use

 1 go test -run=XXX -bench=.

The second line is the average run time of the function under test for the final value of b.N iterations. In this case, my laptop can execute Fib(10) in 509 nanoseconds. If there were additional Benchmark functions that matched the -bench filter, they would be listed here.

Benchmarking various inputs

As the original Fib function is the classic recursive implementation, we’d expect it to exhibit exponential behavior as the input grows. We can explore this by rewriting our benchmark slightly using a pattern that is very common in the Go standard library.

 123456789101112 func benchmarkFib(i int, b *testing.B) {         for n := 0; n < b.N; n++ {                 Fib(i)         } } func BenchmarkFib1(b *testing.B)  { benchmarkFib(1, b) } func BenchmarkFib2(b *testing.B)  { benchmarkFib(2, b) } func BenchmarkFib3(b *testing.B)  { benchmarkFib(3, b) } func BenchmarkFib10(b *testing.B) { benchmarkFib(10, b) } func BenchmarkFib20(b *testing.B) { benchmarkFib(20, b) } func BenchmarkFib40(b *testing.B) { benchmarkFib(40, b) }

Making benchmarkFib private avoids the testing driver trying to invoke it directly, which would fail as its signature does not match func(*testing.B). Running this new set of benchmarks gives these results on my machine.

 123456 BenchmarkFib1   1000000000               2.84 ns/op BenchmarkFib2   500000000                7.92 ns/op BenchmarkFib3   100000000               13.0 ns/op BenchmarkFib10   5000000               447 ns/op BenchmarkFib20     50000             55668 ns/op BenchmarkFib40         2         942888676 ns/op

Apart from confirming the exponential behavior of our simplistic Fib function, there are some other things to observe in this benchmark run.

Each benchmark is run for a minimum of 1 second by default. If the second has not elapsed when the Benchmark function returns, the value of b.N is increased in the sequence 1, 2, 5, 10, 20, 50, … and the function run again.
The final BenchmarkFib40 only ran two times with the average was just under a second for each run. As the testing package uses a simple average (total time to run the benchmark function over b.N) this result is statistically weak. You can increase the minimum benchmark time using the -benchtime flag to produce a more accurate result.

 123 % go test -bench=Fib40 -benchtime=20s PASS BenchmarkFib40        50         944501481 ns/op

Traps for young players

Above I mentioned the for loop is crucial to the operation of the benchmark driver. Here are two examples of a faulty Fib benchmark.

 123456789 func BenchmarkFibWrong(b *testing.B) {         for n := 0; n < b.N; n++ {                 Fib(n)         } } func BenchmarkFibWrong2(b *testing.B) {         Fib(b.N) }

On my system BenchmarkFibWrong never completes. This is because the run time of the benchmark will increase as b.N grows, never converging on a stable value. BenchmarkFibWrong2 is similarly affected and never completes.

A note on compiler optimisations

Before concluding I wanted to highlight that to be completely accurate, any benchmark should be careful to avoid compiler optimisations eliminating the function under test and artificially lowering the run time of the benchmark.

 12345678910111213 var result int func BenchmarkFibComplete(b *testing.B) {         var r int         for n := 0; n < b.N; n++ {                 // always record the result of Fib to prevent                 // the compiler eliminating the function call.                 r = Fib(10)         }         // always store the result to a package level variable         // so the compiler cannot eliminate the Benchmark itself.         result = r }

Conclusion

The benchmarking facility in Go works well, and is widely accepted as a reliable standard for measuring the performance of Go code. Writing benchmarks in this manner is an excellent way of communicating a performance improvement, or a regression, in a reproducible way.