golang 高效低精度定时器实现

时间:2021-12-30 21:32:20

    golang默认定时器是通过time模块提供的,不管是golang,libev,libevent也好,定时器都是通过最小堆实现的,导致加入定时器时间复杂度为O(lgn),在需要大量定时器时效率较低,所以Linux提供了基于时间轮的实现,我们本次提供的

定时器实现就是标准的Linux时间轮实现方式。当然,我是把Skynet(https://github.com/cloudwu/skynet/blob/master/skynet-src/skynet_timer.c)的定时器移植了过来,偷窃无罪。。。


贴一张Linux时间轮的数据结构,如果比较陌生的话可以参考一下两篇文章:

1.http://www.ibm.com/developerworks/cn/linux/l-cn-timers/

2.http://blog.csdn.net/lonewolfxw/article/details/8034395

golang 高效低精度定时器实现


先看一下如何使用

package timer
import (
"fmt"
"sync/atomic"
"testing"
"time"
)

var sum int32 = 0
var N int32 = 300
var tt *Timer

func now() {
fmt.Println(time.Now().Format("2006-01-02 15:04:05"))
atomic.AddInt32(&sum, 1)
v := atomic.LoadInt32(&sum)
if v == 2*N {
tt.Stop()
}

}

func TestTimer(t *testing.T) {
timer := New(time.Millisecond * 10)
tt = timer
fmt.Println(timer)
var i int32
for i = 0; i < N; i++ {
timer.NewTimer(time.Millisecond*time.Duration(10*i), now)
timer.NewTimer(time.Millisecond*time.Duration(10*i), now)
}
timer.Start()
if sum != 2*N {
t.Error("failed")
}
}

timer := New(time.Millisecond * 10)我们定义了一个tick为0.01s的定时器,循环了300次每次启动2个timeout,回调中将sum+1,所以最后sum应该等于600。

这是我golang的处女作,可能代码不是很规范,有空请多review review

github地址:https://github.com/Skycrab/code/blob/master/Go/timer/timer.go


package timerimport (	"container/list"	"fmt"	"sync"	"time")//referer https://github.com/cloudwu/skynet/blob/master/skynet-src/skynet_timer.cconst (	TIME_NEAR_SHIFT  = 8	TIME_NEAR        = 1 << TIME_NEAR_SHIFT	TIME_LEVEL_SHIFT = 6	TIME_LEVEL       = 1 << TIME_LEVEL_SHIFT	TIME_NEAR_MASK   = TIME_NEAR - 1	TIME_LEVEL_MASK  = TIME_LEVEL - 1)type Timer struct {	near [TIME_NEAR]*list.List	t    [4][TIME_LEVEL]*list.List	sync.Mutex	time uint32	tick time.Duration	quit chan struct{}}type Node struct {	expire uint32	f      func()}func (n *Node) String() string {	return fmt.Sprintf("Node:expire,%d", n.expire)}func New(d time.Duration) *Timer {	t := new(Timer)	t.time = 0	t.tick = d	t.quit = make(chan struct{})	var i, j int	for i = 0; i < TIME_NEAR; i++ {		t.near[i] = list.New()	}	for i = 0; i < 4; i++ {		for j = 0; j < TIME_LEVEL; j++ {			t.t[i][j] = list.New()		}	}	return t}func (t *Timer) addNode(n *Node) {	expire := n.expire	current := t.time	if (expire | TIME_NEAR_MASK) == (current | TIME_NEAR_MASK) {		t.near[expire&TIME_NEAR_MASK].PushBack(n)	} else {		var i uint32		var mask uint32 = TIME_NEAR << TIME_LEVEL_SHIFT		for i = 0; i < 3; i++ {			if (expire | (mask - 1)) == (current | (mask - 1)) {				break			}			mask <<= TIME_LEVEL_SHIFT		}		t.t[i][(expire>>(TIME_NEAR_SHIFT+i*TIME_LEVEL_SHIFT))&TIME_LEVEL_MASK].PushBack(n)	}}func (t *Timer) NewTimer(d time.Duration, f func()) *Node {	n := new(Node)	n.f = f	t.Lock()	n.expire = uint32(d/t.tick) + t.time	t.addNode(n)	t.Unlock()	return n}func (t *Timer) String() string {	return fmt.Sprintf("Timer:time:%d, tick:%s", t.time, t.tick)}func dispatchList(front *list.Element) {	for e := front; e != nil; e = e.Next() {		node := e.Value.(*Node)		go node.f()	}}func (t *Timer) moveList(level, idx int) {	vec := t.t[level][idx]	front := vec.Front()	vec.Init()	for e := front; e != nil; e = e.Next() {		node := e.Value.(*Node)		t.addNode(node)	}}func (t *Timer) shift() {	t.Lock()	var mask uint32 = TIME_NEAR	t.time++	ct := t.time	if ct == 0 {		t.moveList(3, 0)	} else {		time := ct >> TIME_NEAR_SHIFT		var i int = 0		for (ct & (mask - 1)) == 0 {			idx := int(time & TIME_LEVEL_MASK)			if idx != 0 {				t.moveList(i, idx)				break			}			mask <<= TIME_LEVEL_SHIFT			time >>= TIME_LEVEL_SHIFT			i++		}	}	t.Unlock()}func (t *Timer) execute() {	t.Lock()	idx := t.time & TIME_NEAR_MASK	vec := t.near[idx]	if vec.Len() > 0 {		front := vec.Front()		vec.Init()		t.Unlock()		// dispatch_list don't need lock		dispatchList(front)		return	}	t.Unlock()}func (t *Timer) update() {	// try to dispatch timeout 0 (rare condition)	t.execute()	// shift time first, and then dispatch timer message	t.shift()	t.execute()}func (t *Timer) Start() {	tick := time.NewTicker(t.tick)	defer tick.Stop()	for {		select {		case <-tick.C:			t.update()		case <-t.quit:			return		}	}}func (t *Timer) Stop() {	close(t.quit)}

    熟悉skynet的童鞋看这段代码应该很熟悉,期待出现了golang大牛也写个牛逼的游戏服务器框架,这应该是很多人的心声吧。