DevilKing's blog

原文链接

Because all product decision authority rests with the “Product Owner”, Scrum disallows engineers from making any product decisions and reduces them to grovelling to product management for any level of inclusion in product direction.

poor design/lack of motivation

Scrum is very management heavy. Typical teams have Product Owners, Scrum Masters, and Team Leads. Innovative, motivated teams operate better with less management, not more.

可能是强调scrum磨灭了工程师自主选择的能力，无法进行相关事情的管理

原文链接

由于golang中的go是非常方便的，加上函数又非常容易隐藏go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

package main

import(
    "time"
    "fmt"
    "math/rand"
)

func main() {
    start := time.Now()
    var t *time.Timer
    t = time.AfterFunc(randomDuration(), func() {
        fmt.Println(time.Now().Sub(start))
        t.Reset(randomDuration())
    })
    time.Sleep(5 * time.Second)
}

func randomDuration() time.Duration {
    return time.Duration(rand.Int63n(1e9))
}

time.AfterFunc是会另外启动一个goroutine来进行计时和执行func()。 由于func中有对t(Timer)进行操作(t.Reset)，而主goroutine也有对t进行操作(t=time.After)。 这个时候，其实有可能会造成两个goroutine对同一个变量进行竞争的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

runtime  go run -race race1.go
a is  3
==================
WARNING: DATA RACE
Write by goroutine 5:
  main.func·001()
      /Users/yejianfeng/Documents/workspace/go/src/runtime/race1.go:11 +0x3a

Previous write by main goroutine:
  main.main()
      /Users/yejianfeng/Documents/workspace/go/src/runtime/race1.go:13 +0xe7

Goroutine 5 (running) created at:
  main.main()
      /Users/yejianfeng/Documents/workspace/go/src/runtime/race1.go:12 +0xd7
==================
Found 1 data race(s)
exit status 66

通过race的参数，检测相关参数的竞争问题

原文链接

go语言初始化过程

这里解释一下本地线程存储。比如说每个goroutine都有自己的控制信息，这些信息是存放在一个结构体G中。假设我们有一个全局变量g是结构体G的指针，我们希望只有唯一的全局变量g，而不是g0，g1，g2…但是我们又希望不同goroutine去访问这个全局变量g得到的并不是同一个东西，它们得到的是相对自己线程的结构体G，这种情况下就需要本地线程存储。g确实是一个全局变量，却在不同线程有多份不同的副本。每个goroutine去访问g时，都是对应到自己线程的这一份副本。针对goroutine部分，

1
2
3
4
5
6
7
8
9
10

CLD                // convention is D is always left cleared
CALL    runtime·check(SB) //检测像int8,int16,float等是否是预期的大小，检测cas操作是否正常
MOVL    16(SP), AX        // copy argc
MOVL    AX, 0(SP)
MOVQ    24(SP), AX        // copy argv
MOVQ    AX, 8(SP)
CALL    runtime·args(SB)    //将argc,argv设置到static全局变量中了
CALL    runtime·osinit(SB)    //osinit做的事情就是设置runtime.ncpu，不同平台实现方式不一样
CALL    runtime·hashinit(SB)    //使用读/dev/urandom的方式从内核获得随机数种子
CALL    runtime·schedinit(SB)    //内存管理初始化，根据GOMAXPROCS设置使用的procs等等

go关键字的调用协议：先将参数进栈，再被调函数指针和参数字节数进栈，接着调用runtime.newproc函数。所以这里其实就是新开个goroutine执行runtime.main

1
2
3

找到一个等待运行的g
如果g是锁定到某个M的，则让那个M运行
否则，调用execute函数让g在当前的M中运行

1
2
3
4
5
6
7
8
9
10
11
12
13

func M() {
    for {
        sched.lock.Lock()    //互斥地从就绪G队列中取一个g出来运行
        if sched.allg > 0 {
            g := sched.allg[0]
            sched.allg = sched.allg[1:]
            sched.lock.Unlock()
            g.Run()        //运行它
        } else {
            sched.lock.Unlock()
        }
    }
}

退出goroutine

1
2
3
4
5
6
7
8

func exitsyscall() {
    if len(allm) >= GOMAXPROCS {
        sched.lock.Lock()
        sched.allg = append(sched.allg, g)    //把g放回到队列中
        sched.lock.Unlock()
        time.Sleep()    //这个M不再干活
    }
}

内存管理

在多线程方面，很自然的做法就是每条线程都有自己的本地的内存，然后有一个全局的分配链，当某个线程中内存不足后就向全局分配链中申请内存。这样就避免了多线程同时访问共享变量时的加锁。 在避免内存碎片方面，大块内存直接按页为单位分配，小块内存会切成各种不同的固定大小的块，申请做任意字节内存时会向上取整到最接近的块，将整块分配给申请者以避免随意切割。

分配器的数据结构包括:

• FixAlloc: 固定大小(128kB)的对象的空闲链分配器,被分配器用于管理存储
• MHeap: 分配堆,按页的粒度进行管理(4kB)，用于直接分配较大(>32kB)的内存空间
• MSpan: 一些由MHeap管理的页
• MCentral: 对于给定尺寸类别的共享的free list
• MCache: 用于小对象的每M一个的cache

我们可以将Go语言的内存管理看成一个两级的内存管理结构，MHeap和MCache。

非阻塞io

底层非阻塞io是如何实现的呢？简单地说，所有文件描述符都被设置成非阻塞的，某个goroutine进行io操作，读或者写文件描述符，如果此刻io还没准备好，则这个goroutine会被放到系统的等待队列中，这个goroutine失去了运行权，但并不是真正的整个系统“阻塞”于系统调用。

后台还有一个poller会不停地进行poll，所有的文件描述符都被添加到了这个poller中的，当某个时刻一个文件描述符准备好了，poller就会唤醒之前因它而阻塞的goroutine，于是goroutine重新运行起来

原文链接

动态规划中，状态和状态转移方程

1
2
3
4
5
6
7
8
9

Set Min[i] equal to Infinity for all of i
Min[0] = 0

For i = 1 to S
For j = 0 to N-1
	if (Vj<=i AND Min[i-Vj]+1]<Min[i])
Then Min[i] = Min[i-Vj] + 1

Output Min[S]

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

func upper_bound(arr []int, s, e, key int) int {
	if arr[e] < key {
		return e + 1
	}
	mid := 0
	for s < e {
		mid = s + (e-s)/2
		if arr[mid] < key {
			s = mid + 1
		} else {
			e = mid
		}
	}
	return s
}

func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	end := make([]int, 0)
	end = append(end, nums[0])
	l := 1

	for i := 1; i < len(nums); i++ {
		pos := upper_bound(end, 0, len(end)-1, nums[i])
		if pos > len(end)-1 {
			end = append(end, nums[i])
			l++
		} else {
			end[pos] = nums[i]
		}
	}

	return l
}

二维的DP问题

状态S[i][j]表示我们走到(i, j)这个格子时，最多能收集到多少个苹果。那么， 状态转移方程如下：

1

S[i][j]=A[i][j] + max(S[i-1][j], if i>0 ; S[i][j-1], if j>0)

其中i代表行，j代表列，下标均从0开始；A[i][j]代表格子(i, j)处的苹果数量。

带额外条件的DP问题

无向图G有N个结点，它的边上带有正的权重值，过路最短问题

迪杰斯特拉，最短路径问题

当阅读一个题目并且开始尝试解决它时，首先看一下它的限制。 如果要求在多项式时间内解决，那么该问题就很可能要用DP来解。遇到这种情况， 最重要的就是找到问题的“状态”和“状态转移方程”。(状态不是随便定义的， 一般定义完状态，你要找到当前状态是如何从前面的状态得到的， 即找到状态转移方程)如果看起来是个DP问题，但你却无法定义出状态， 那么试着将问题规约到一个已知的DP问题(正如“高级”一节中的例子一样)。

原文链接

1
2
3
4
5
6
7

query {
  players(name:”Lionel Messi”) {
    name
    dob
    allGoals
  }
}