runtime
- go struct能不能比较
同一个struct的2个实例能否比较
1.成员变量带有了不能比较的成员，== 会报错 mismatched types
2.指针类型可以比较，就是比较指针中存储的地址
3.成员变量没有不能比较的成员，== 会比较每个字段的值
不同的结构体，如果可以强制转换，强制转换之后，如果成员变量不含有不可比较成员变量，可以比较
可排序的数据类型有三种，Integer，Floating-point，和String
可比较的数据类型除了上述三种外，还有Boolean，Complex，Pointer，Channel，Interface和Array
不可比较的数据类型包括，Slice, Map, 和Function
struct必须是可比较的，才能作为map的key，否则编译时报错
DeepEqual
Two values of identical type are deeply equal if one of the following cases applies.
Values of distinct types are never deeply equal.
1.Array values are deeply equal when their corresponding elements are deeply equal.
2.Struct values are deeply equal if their corresponding fields, both exported and unexported, are deeply equal.
3.Func values are deeply equal if both are nil; otherwise they are not deeply equal.
4.Interface values are deeply equal if they hold deeply equal concrete values.
5.Map values are deeply equal when all of the following are true:
they are both nil or both non-nil,
they have the same length,and either they are the same map object or their corresponding keys (matched using Go equality) map to deeply equal values.
Pointer values are deeply equal if they are equal using Go's == operator or if they point to deeply equal values.
Slice values are deeply equal when all of the following are true: they are both nil or both non-nil, they have the same length,
and either they point to the same initial entry of the same underlying array (that is, &x[0] == &y[0]) or their corresponding elements (up to length) are deeply equal. Note that a non-nil empty slice and a nil slice (for example, []byte{} and []byte(nil)) are not deeply equal.
func DeepEqual(x, y interface{}) bool {
if x == nil || y == nil {
return x == y
}
v1 := ValueOf(x)
v2 := ValueOf(y)
if v1.Type() != v2.Type() {
return false
}
return deepValueEqual(v1, v2, make(map[visit]bool), 0)
}
// Tests for deep equality using reflected types. The map argument tracks
// comparisons that have already been seen, which allows short circuiting on
// recursive types.
func deepValueEqual(v1, v2 Value, visited map[visit]bool, depth int) bool {
if !v1.IsValid() || !v2.IsValid() {
return v1.IsValid() == v2.IsValid()
}
if v1.Type() != v2.Type() {
return false
}
// if depth > 10 { panic("deepValueEqual") } // for debugging
// We want to avoid putting more in the visited map than we need to.
// For any possible reference cycle that might be encountered,
// hard(v1, v2) needs to return true for at least one of the types in the cycle,
// and it's safe and valid to get Value's internal pointer.
hard := func(v1, v2 Value) bool {
switch v1.Kind() {
case Map, Slice, Ptr, Interface:
// Nil pointers cannot be cyclic. Avoid putting them in the visited map.
return !v1.IsNil() && !v2.IsNil()
}
return false
}
if hard(v1, v2) {
addr1 := v1.ptr
addr2 := v2.ptr
if uintptr(addr1) > uintptr(addr2) {
// Canonicalize order to reduce number of entries in visited.
// Assumes non-moving garbage collector.
addr1, addr2 = addr2, addr1
}
// Short circuit if references are already seen.
typ := v1.Type()
v := visit{addr1, addr2, typ}
if visited[v] {
return true
}
// Remember for later.
visited[v] = true
}
switch v1.Kind() {
case Array:
for i := 0; i < v1.Len(); i++ {
if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
return false
}
}
return true
-
client如何实现长连接
-
主协程如何等其余协程完再操作
-
slice，len，cap，共享，扩容
-
list的实现，arrayList
// List holds the elements in a slice
type List struct {
elements []interface{}
size int
}
// Add appends a value at the end of the list
func (list *List) Add(values ...interface{}) {
list.growBy(len(values))
for _, value := range values {
list.elements[list.size] = value
list.size++
}
}
// Expand the array if necessary, i.e. capacity will be reached if we add n elements
func (list *List) growBy(n int) {
// When capacity is reached, grow by a factor of growthFactor and add number of elements
currentCapacity := cap(list.elements)
if list.size+n >= currentCapacity {
newCapacity := int(growthFactor * float32(currentCapacity+n))
list.resize(newCapacity)
}
}
func (list *List) resize(cap int) {
newElements := make([]interface{}, cap, cap)
copy(newElements, list.elements)
list.elements = newElements
}
// Remove removes the element at the given index from the list.
func (list *List) Remove(index int) {
if !list.withinRange(index) {
return
}
list.elements[index] = nil // cleanup reference
copy(list.elements[index:], list.elements[index+1:list.size]) // shift to the left by one (slow operation, need ways to optimize this)
list.size--
list.shrink()
}
// Shrink the array if necessary, i.e. when size is shrinkFactor percent of current capacity
func (list *List) shrink() {
if shrinkFactor == 0.0 {
return
}
// Shrink when size is at shrinkFactor * capacity
currentCapacity := cap(list.elements)
if list.size <= int(float32(currentCapacity)*shrinkFactor) {
list.resize(list.size)
}
}
- linkedList
- map如何顺序读取
按照插入顺序读取，实现java的LinkedHashMap
// Map holds the elements in a regular hash table, and uses doubly-linked list to store key ordering.
type Map struct {
table map[interface{}]interface{}
ordering *doublylinkedlist.List
}
// Put inserts key-value pair into the map.
// Key should adhere to the comparator's type assertion, otherwise method panics.
func (m *Map) Put(key interface{}, value interface{}) {
if _, contains := m.table[key]; !contains {
m.ordering.Append(key)
}
m.table[key] = value
}
// Values returns all values in-order based on the key.
func (m *Map) Values() []interface{} {
values := make([]interface{}, m.Size())
count := 0
it := m.Iterator()
for it.Next() {
values[count] = it.Value()
count++
}
return values
}
- map如何排序
treeMap，用红黑树 - 实现set
// Set holds elements in go's native map
type Set struct {
items map[interface{}]struct{}
}
var itemExists = struct{}{}
// Add adds the items (one or more) to the set.
func (set *Set) Add(items ...interface{}) {
for _, item := range items {
set.items[item] = itemExists
}
}
- arrayList实现的stack
// Stack holds elements in an array-list
type Stack struct {
list *arraylist.List
}
// New instantiates a new empty stack
func New() *Stack {
return &Stack{list: arraylist.New()}
}
// Push adds a value onto the top of the stack
func (stack *Stack) Push(value interface{}) {
stack.list.Add(value)
}
// Pop removes top element on stack and returns it, or nil if stack is empty.
// Second return parameter is true, unless the stack was empty and there was nothing to pop.
func (stack *Stack) Pop() (value interface{}, ok bool) {
value, ok = stack.list.Get(stack.list.Size() - 1)
stack.list.Remove(stack.list.Size() - 1)
return
}
// Peek returns top element on the stack without removing it, or nil if stack is empty.
// Second return parameter is true, unless the stack was empty and there was nothing to peek.
func (stack *Stack) Peek() (value interface{}, ok bool) {
return stack.list.Get(stack.list.Size() - 1)
}
- linkedList实现的stack
// Stack holds elements in a singly-linked-list
type Stack struct {
list *singlylinkedlist.List
}
// New nnstantiates a new empty stack
func New() *Stack {
return &Stack{list: &singlylinkedlist.List{}}
}
// Push adds a value onto the top of the stack
func (stack *Stack) Push(value interface{}) {
stack.list.Prepend(value)
}
// Pop removes top element on stack and returns it, or nil if stack is empty.
// Second return parameter is true, unless the stack was empty and there was nothing to pop.
func (stack *Stack) Pop() (value interface{}, ok bool) {
value, ok = stack.list.Get(0)
stack.list.Remove(0)
return
}
// Peek returns top element on the stack without removing it, or nil if stack is empty.
// Second return parameter is true, unless the stack was empty and there was nothing to peek.
func (stack *Stack) Peek() (value interface{}, ok bool) {
return stack.list.Get(0)
}
-
堆，优先级队列
-
A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues.[1]:162–163 The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.[2]
-
A binary heap is defined as a binary tree with two additional constraints:[3]
-
Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
-
Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.
// Heap holds elements in an array-list
type Heap struct {
list *arraylist.List
Comparator utils.Comparator
}
// NewWith instantiates a new empty heap tree with the custom comparator.
func NewWith(comparator utils.Comparator) *Heap {
return &Heap{list: arraylist.New(), Comparator: comparator}
}
// Push adds a value onto the heap and bubbles it up accordingly.
func (heap *Heap) Push(values ...interface{}) {
if len(values) == 1 {
heap.list.Add(values[0])
heap.bubbleUp()
} else {
// Reference: https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
for _, value := range values {
heap.list.Add(value)
}
size := heap.list.Size()/2 + 1
for i := size; i >= 0; i-- {
heap.bubbleDownIndex(i)
}
}
}
// Pop removes top element on heap and returns it, or nil if heap is empty.
// Second return parameter is true, unless the heap was empty and there was nothing to pop.
func (heap *Heap) Pop() (value interface{}, ok bool) {
value, ok = heap.list.Get(0)
if !ok {
return
}
lastIndex := heap.list.Size() - 1
heap.list.Swap(0, lastIndex)
heap.list.Remove(lastIndex)
heap.bubbleDown()
return
}
// Performs the "bubble up" operation. This is to place a newly inserted
// element (i.e. last element in the list) in its correct place so that
// the heap maintains the min/max-heap order property.
func (heap *Heap) bubbleUp() {
index := heap.list.Size() - 1
for parentIndex := (index - 1) >> 1; index > 0; parentIndex = (index - 1) >> 1 {
indexValue, _ := heap.list.Get(index)
parentValue, _ := heap.list.Get(parentIndex)
if heap.Comparator(parentValue, indexValue) <= 0 {
break
}
heap.list.Swap(index, parentIndex)
index = parentIndex
}
}
// Performs the "bubble down" operation. This is to place the element that is at the index
// of the heap in its correct place so that the heap maintains the min/max-heap order property.
func (heap *Heap) bubbleDownIndex(index int) {
size := heap.list.Size()
for leftIndex := index<<1 + 1; leftIndex < size; leftIndex = index<<1 + 1 {
rightIndex := index<<1 + 2
smallerIndex := leftIndex
leftValue, _ := heap.list.Get(leftIndex)
rightValue, _ := heap.list.Get(rightIndex)
if rightIndex < size && heap.Comparator(leftValue, rightValue) > 0 {
smallerIndex = rightIndex
}
indexValue, _ := heap.list.Get(index)
smallerValue, _ := heap.list.Get(smallerIndex)
if heap.Comparator(indexValue, smallerValue) > 0 {
heap.list.Swap(index, smallerIndex)
} else {
break
}
index = smallerIndex
}
}
- Go的反射包怎么找到对应的方法
// MethodByName returns a function value corresponding to the method
// of v with the given name.
// The arguments to a Call on the returned function should not include
// a receiver; the returned function will always use v as the receiver.
// It returns the zero Value if no method was found.
func (v Value) MethodByName(name string) Value {
if v.typ == nil {
panic(&ValueError{"reflect.Value.MethodByName", Invalid})
}
if v.flag&flagMethod != 0 {
return Value{}
}
m, ok := v.typ.MethodByName(name)
if !ok {
return Value{}
}
return v.Method(m.Index)
}
func (t *rtype) MethodByName(name string) (m Method, ok bool) {
if t.Kind() == Interface {
tt := (*interfaceType)(unsafe.Pointer(t))
return tt.MethodByName(name)
}
ut := t.uncommon()
if ut == nil {
return Method{}, false
}
// TODO(mdempsky): Binary search.
for i, p := range ut.exportedMethods() {
if t.nameOff(p.name).name() == name {
return t.Method(i), true
}
}
return Method{}, false
}
// Method returns a function value corresponding to v's i'th method.
// The arguments to a Call on the returned function should not include
// a receiver; the returned function will always use v as the receiver.
// Method panics if i is out of range or if v is a nil interface value.
func (v Value) Method(i int) Value {
if v.typ == nil {
panic(&ValueError{"reflect.Value.Method", Invalid})
}
if v.flag&flagMethod != 0 || uint(i) >= uint(v.typ.NumMethod()) {
panic("reflect: Method index out of range")
}
if v.typ.Kind() == Interface && v.IsNil() {
panic("reflect: Method on nil interface value")
}
fl := v.flag & (flagStickyRO | flagIndir) // Clear flagEmbedRO
fl |= flag(Func)
fl |= flag(i)<<flagMethodShift | flagMethod
return Value{v.typ, v.ptr, fl}
}
code
- 实现消息队列（多生产者，多消费者）
- Go怎么做深拷贝。
基于序列化和反序列化来实现对象的深度拷贝
或者 反射
反射：https://github.com/jinzhu/copier
参考：https://toolchain.dexscript.com/golang-deep-copy.html
- Map是线程安全的吗？怎么解决并发安全问题？
不是，读的时候会检查hashWriting标志， 如果有这个标志，就会报并发错误。
var counter = struct{
sync.RWMutex
m map[string]int
}{m: make(map[string]int)}
- sync.Map 怎么解决线程安全问题？
type Map struct {
// 当涉及到dirty数据的操作的时候，需要使用这个锁
mu Mutex
// 一个只读的数据结构，因为只读，所以不会有读写冲突。
// 所以从这个数据中读取总是安全的。
// 实际上，实际也会更新这个数据的entries,如果entry是未删除的(unexpunged), 并不需要加锁。如果entry已经被删除了，需要加锁，以便更新dirty数据。
read atomic.Value // readOnly
// dirty数据包含当前的map包含的entries,它包含最新的entries(包括read中未删除的数据,虽有冗余，但是提升dirty字段为read的时候非常快，不用一个一个的复制，而是直接将这个数据结构作为read字段的一部分),有些数据还可能没有移动到read字段中。
// 对于dirty的操作需要加锁，因为对它的操作可能会有读写竞争。
// 当dirty为空的时候， 比如初始化或者刚提升完，下一次的写操作会复制read字段中未删除的数据到这个数据中。
dirty map[interface{}]*entry
// 当从Map中读取entry的时候，如果read中不包含这个entry,会尝试从dirty中读取，这个时候会将misses加一，
// 当misses累积到 dirty的长度的时候， 就会将dirty提升为read,避免从dirty中miss太多次。因为操作dirty需要加锁。
misses int
}
Load,Store,Delete
想一想，mysql加锁，是不是有表级锁、行级锁，前文的sync.RWMutex加锁方式相当于表级锁。
而sync.Map其实也是相当于表级锁，只不过多读写分了两个map，本质还是一样的。
既然这样，那就自然知道优化方向了：就是把锁的粒度尽可能降低来提高运行速度。
思路：对一个大map进行hash，其内部是n个小map，根据key来来hash确定在具体的那个小map中，这样加锁的粒度就变成1/n了。
网上找了下，真有大佬实现了
参考：https://colobu.com/2017/07/11/dive-into-sync-Map/
参考：https://juejin.im/post/6844903895227957262
- Go里面一个协程能保证绑定在一个内核线程上面的。
LockOSThread
当然只能绑定用户态线程，不能绑定内核态线程
我们知道golang的scheduler可以理解为公平协作调度和抢占的综合体，他不支持优先级调度。当你开了几十万个goroutine，并且大多数协程已经在runq等待调度了, 那么如果你有一个重要的周期性的协程需要优先执行该怎么办？
可以借助runtime.LockOSThread()方法来绑定线程，绑定线程M后的好处在于，他可以由system kernel内核来调度，因为他本质是线程了。
参考：http://xiaorui.cc/archives/5320
- defer A ; defer B ; defer panic("") A和B能不能执行到
func main() {
defer func() {
panic("err")
}()
defer func() {
println("a")
}()
defer func() {
println("b")
}()
defer func() {
panic("err")
}()
println("c")
}
c
b
a
panic: err
panic: err
goroutine 1 [running]:
main.main.func1()
/Users/xushuangfu/go/src/github.com/shuff1e/code-review/Temp/test/143.go:5 +0x39
panic(0x1060240, 0x1083ca0)
/usr/local/go/src/runtime/panic.go:969 +0x166
main.main.func4()
/Users/xushuangfu/go/src/github.com/shuff1e/code-review/Temp/test/143.go:14 +0x39
main.main()
/Users/xushuangfu/go/src/github.com/shuff1e/code-review/Temp/test/143.go:17 +0xa4
Process finished with exit code 2
- Go切片和数据之间的区别,切片怎么扩容,扩容过程中需不需要重新写入
memmove
扩容就是为切片分配一块新的内存空间并将原切片的元素全部拷贝过去
- copy是操作符还是内置函数
内置函数
- Go的协程可以不可以自己让出cpu，一个协程挂起换入另外一个协程是什么过程？
runtime.Gosched，暂停，释放线程去执行其他任务。当前任务被放回队列，等待下次调度时恢复执行。
运行时会主动向长时间运行(10ms）的任务发起抢占调度。
协作式调度
我们在设计原理中介绍过了 Go 语言基于协作式和信号的两种抢占式调度，在这里我们介绍 Go 语言中的协作式调度。runtime.Gosched 就是主动让出处理器，允许其他 Goroutine 运行。该函数无法挂起 Goroutine，调度器会在自动调度当前 Goroutine：
func Gosched() {
checkTimeouts()
mcall(gosched_m)
}
func gosched_m(gp *g) {
goschedImpl(gp)
}
func goschedImpl(gp *g) {
casgstatus(gp, _Grunning, _Grunnable)
dropg()
lock(&sched.lock)
globrunqput(gp)
unlock(&sched.lock)
schedule()
}
经过连续几次跳转，我们最终在 g0 的栈上调用 runtime.goschedImpl 函数，运行时会更新 Goroutine 的状态到 _Grunnable，让出当前的处理器并将 Goroutine 重新放回全局队列，在最后，该函数会调用 runtime.schedule 重新触发调度。
另外 参考：http://interview.wzcu.com/Golang/goroutine.html
- 什么情况下 M 会进入自旋的状态？
（M 是系统线程。为了保证自己不被释放，所以自旋。这样一旦有 G 需要处理，M 可以直接使用，不需要再创建。M 自旋表示此时没有 G 需要处理）
在Go的调度中，m一旦被创建则不会退出。在系统调用、cgocall、lockOSThread时，为了防止阻塞其他g的执行，Go会新建或者唤醒m(os线程)执行其他的g，所以可能导致m的增加。
如何保证m数量不会太多，同时有足够的线程使p(cpu)不会空闲？主要的手段是通过多路复用和m的spinning。多路复用解决网络和文件io时的阻塞(与net poll类似，Go1.8.1的代码中为os.File加了poll接口)，避免每次读写的系统调用消耗线程。
而m的spinning的作用是尽量保证始终有m处于spinning寻找g(并不是执行g，充分利用多cpu)的同时，不会有太多m同时处于spinning(浪费cpu)。不同于一般意义的自旋，m处于自旋是指m的本地队列、全局队列、poller都没有g可运行时，m进入自旋并尝试从其他p偷取(steal)g，每当一个spinning的m获取到g后，会退出spinning并尝试唤醒新的m去spinning。
所以，一旦总的spinning的m数量大于0时，就不用唤醒新的m了去spinning浪费cpu了。
参考：http://interview.wzcu.com/Golang/goroutine.html
- go 里的 syncLock 和 channel 的性能有区别吗？
mutex性能略好，但chan更go化，更推荐。
- Golang slice 不断 append，是如何给它分配内存的？slice 如果分配的 capacity 是 10，那当容量到多大的时候才会扩容？8、9、10？
扩容会发生在slice append的时候，当slice的cap不足以容纳新元素，就会进行growSlice
网上很多博客也有提到，slice扩容，cap不够1024的，直接翻倍；cap超过1024的，新cap变为老cap的1.25倍。
- g0栈
由于m是实际执行体，m的整个代码逻辑基本上就是整个调度逻辑。
类似于Linux的内核栈和用户栈，Go的m也有两类栈：一类是系统栈(或者叫调度栈)，主要用于运行runtime的程序逻辑；另一类是g栈，用于运行g的程序逻辑。
每个m在创建时会分配一个默认的g叫g0，g0不执行任何代码逻辑，只是用来存放m的调度栈等信息。当要执行Go runtime的一些逻辑比如创建g、新建m等，都会首先切换到g0栈然后执行，而执行g任务时，会切换到g的栈上。在调度栈和g栈上不断切换使整个调度过程复杂了不少。
- top k 有没有 O(k) 的方法？
桶排序
冒泡排序，堆排序，快速排序等都是基于比较的排序，时间复杂度下限为O(nlogn)。
而有一些排序的时间复杂度可以是O(n), 比如桶排序和基数排序。
但是这类排序有较为苛刻的限制条件：元素须是数值类型。
同时，如果是桶排序的话，范围不能太大，否则需要的桶太多，空间复杂度无法接受。
桶排序的元素不一定要是整数，有时候浮点数也可以。
比如，如果数据取值范围在[0, 100.0], 并且只有两位小数, 可以这么解：
private static float[] pickTopKByBucketSort(float[] a, int k) {
int[] bucket = new int[10000];
for (int i = 0; i < a.length; i++) {
int index = Math.round(a[i] * 100f);
bucket[index]++;
}
float[] r = new float[k];
int p = 0;
for (int i = bucket.length - 1; i >= 0 && p < k; i--) {
int c = bucket[i];
while (c > 0 && p < k) {
r[p++] = i / 100f;
c--;
}
}
return r;
}
取一万个桶，将每个元素乘以100，四舍五入为整数（有一些小数在计算机二进制中无法精确表示，同时直接强转成int的话是向下取整），
放到对应的桶中；
然后从最大的桶开始检索，收集100个元素。
时间复杂度跟数据量和桶数量（取决于数据的大小范围）有关。
在数据量远大于桶数量时，时间复杂度为O(n)。
- 快排的时间复杂度是 O(nlogn)，你有哪些优化时间复杂度的方法吗？比如空间换时间
桶排序
private int indexFor(int a, int min, int step) {
return (a - min) / step;
}
public void bucketSort(int[] arr) {
int max = arr[0], min = arr[0];
for (int a : arr) {
if (max < a)
max = a;
if (min > a)
min = a;
}
// 該值也可根據實際情況選擇
int bucketNum = max / 10 - min / 10 + 1;
List buckList = new ArrayList<List<Integer>>();
// create bucket
for (int i = 1; i <= bucketNum; i++) {
buckList.add(new ArrayList<Integer>());
}
// push into the bucket
for (int i = 0; i < arr.length; i++) {
int index = indexFor(arr[i], min, 10);
((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
}
ArrayList<Integer> bucket = null;
int index = 0;
for (int i = 0; i < bucketNum; i++) {
bucket = (ArrayList<Integer>) buckList.get(i);
insertSort(bucket);
for (int k : bucket) {
arr[index++] = k;
}
}
}
// 把桶內元素插入排序
private void insertSort(List<Integer> bucket) {
for (int i = 1; i < bucket.size(); i++) {
int temp = bucket.get(i);
int j = i - 1;
for (; j >= 0 && bucket.get(j) > temp; j--) {
bucket.set(j + 1, bucket.get(j));
}
bucket.set(j + 1, temp);
}
}
- 协程的栈空间大小有限制吗？会主动扩展吗？
无限大，受到系统内存的限制
会主动扩展
参考：https://studygolang.com/articles/1744
- 协程如果像你说的这么牛逼，为什么只有Go支持呢，其他语言为什么这一两年才开始有协程库？协程这个概念好多年前就有了不是吗？（从cpu的角度回答，这个问题当时确实问得我有点懵，腾讯总监问的，应该从多核发展的角度去考虑，另外结合线程/协程的调度特点）。
想像一下如果没有thread，也没有ThreadLocal，@Transactional不起作用了，又没有等价的工具，是不是很郁闷？这么看来怎么着都不是个划算的事情。我想Oracle对此并不会有太大兴趣。
网友评论