关于golang:go内存队列的实现-list-VS-slice

golang 中没有队列这种数据结构，通常须要本人实现，常见的能够通过 list 或 slice 实现。

go 队列的实现形式

list 是 ”container/list” 中的数据结构，用双向链表实现，能够用来做队列：

// 入队
func (l *List) PushBack(v interface{}) *Element

// 出队：先 Front() 获得头，而后 Remove() 删除
func (l *List) Front() *Element
func (l *List) Remove(e *Element) interface{}

slice 实现队列的形式：

var s []obj
s = append(s, obj)     // 入队
s = s[1:]             // 出队 

benchmark 测试比拟

benchmark 测试代码: 队列中存入 object 对象

type EventMsg struct {
    Id  string
    Msg string
}

func BenchmarkQueue_ListObject(b *testing.B) {var l = list.New()
    for i := 0; i < b.N; i++ {
        l.PushBack(EventMsg{Id:  strconv.Itoa(i),
            Msg: "1:abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz",
        })
        l.PushBack(EventMsg{Id:  strconv.Itoa(i),
            Msg: "1:opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn",
        })
        l.Remove(l.Front())
    }
}

func BenchmarkQueue_SliceObject(b *testing.B) {var q []EventMsg
    for i := 0; i < b.N; i++ {
        q = append(q, EventMsg{Id:  strconv.Itoa(i),
            Msg: "1:abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz",
        })
        q = append(q, EventMsg{Id:  strconv.Itoa(i),
            Msg: "1:opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn",
        })
        q = q[1:]
    }
}

benchmark 测试代码：队列中存入 Object 指针对象

func BenchmarkQueue_ListObjPtr(b *testing.B) {var l = list.New()
    for i := 0; i < b.N; i++ {
        l.PushBack(&EventMsg{Id:  strconv.Itoa(i),
            Msg: "1:abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz",
        })
        l.PushBack(&EventMsg{Id:  strconv.Itoa(i),
            Msg: "1:opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn",
        })
        l.Remove(l.Front())
    }
}
func BenchmarkQueue_SliceObjPtr(b *testing.B) {var q []*EventMsg
    for i := 0; i < b.N; i++ {
        q = append(q, &EventMsg{Id:  strconv.Itoa(i),
            Msg: "1:abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz-abcdefghijklmnopqrstuvwxyz",
        })
        q = append(q, &EventMsg{Id:  strconv.Itoa(i),
            Msg: "1:opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn-opqrstuvwxyzabcdefghijklmn",
        })
        q = q[1:]
    }
}

benchmark 测试后果

# go test -bench=BenchmarkQueue -count=1 -benchmem -cpu 4
BenchmarkQueue_ListObject-4      1000000              1423 ns/op             175 B/op          5 allocs/op
BenchmarkQueue_ListObjPtr-4      1000000              1124 ns/op             175 B/op          5 allocs/op
BenchmarkQueue_SliceObject-4     1000000              1574 ns/op             357 B/op          1 allocs/op
BenchmarkQueue_SliceObjPtr-4     1831449               662.7 ns/op           161 B/op          3 allocs/op
PASS
ok      github.com/go_list/bench_test       6.144s

论断：

• 不论用 list 还是 slice，队列中存储对象指针的性能，要好于间接存储对象；
• slice 实现的队列，存储指针对象时性能最好；
• list 实现的队列，不论是存储对象还是指针对象，其性能差别不是太大；

Open-falcon 的队列实现

open-falcon 应用 list 和 mutex 实现了一个协程平安的内存队列。
实现代码：https://github.com/toolkits/c…

type SafeList struct {
    sync.RWMutex
    L *list.List
}
func NewSafeList() *SafeList {return &SafeList{L: list.New()}
}
// 入队
func (this *SafeList) PushFront(v interface{}) *list.Element {this.Lock()
    e := this.L.PushFront(v)
    this.Unlock()
    return e
}
// 出队
func (this *SafeList) PopBack() interface{} {this.Lock()
    if elem := this.L.Back(); elem != nil {item := this.L.Remove(elem)
        this.Unlock()
        return item
    }
    this.Unlock()
    return nil
}

参考：

1.https://blog.wolfogre.com/pos…