Go 队列性能比较

使用 Go 语言以来,一直有个疑问,为什么大家都喜欢用 slice 的方式简单地实现队列?当不断地出入队的时候,不就会造成底层数组的重新分配和数据的复制吗?而且 container/list 包实现了双向链表,也可以用作队列,不香吗?最近碰巧遇到一个地方要实现环形队列,那么我们来比较比较这些方案的性能表现。

实现

环形队列

这个环形队列使用 slice 保存数据,额外记录队头head、队尾tail和数量count。当队头或者队尾索引值到达数组上限时,使用模运算来实现折返,d.head = (d.head + 1) % len(d.data)。并且在队列满时扩容至原来队列长度的2倍,在元素数量只有队列长度的1/4时缩小长度至原来的1/2。

package main

type Deque struct {
	head  int
	tail  int
	data  []interface{}
	count int
	init  int
}

func NewDeque(c int) *Deque {
	if c <= 0 {
		panic("init len of deque can not be 0")
	}
	return &Deque{
		data: make([]interface{}, c),
		init: c,
	}
}

func (d *Deque) Enqueue(item interface{}) bool {
	if d.Full() {
		return false
	}
	d.data[d.tail] = item
	d.tail = (d.tail + 1) % len(d.data)
	d.count++
	d.grow()
	return true
}

func (d *Deque) Dequeue() (interface{}, bool) {
	if d.Empty() {
		return nil, false
	}
	item := d.data[d.head]
	d.data[d.head] = nil
	d.head = (d.head + 1) % len(d.data)
	d.count--
	d.shrink()
	return item, true
}

func (d *Deque) Head() (interface{}, bool) {
	if d.Empty() {
		return nil, false
	}
	return d.data[d.head], true
}

func (d *Deque) Tail() (interface{}, bool) {
	if d.Empty() {
		return nil, false
	}
	return d.data[d.tail], true
}

func (d *Deque) Empty() bool {
	return d.count == 0
}

func (d *Deque) Full() bool {
	return d.count == len(d.data)
}


func (d *Deque) grow() {
	if !d.Full() || d.Empty() {
		return
	}
	old := d.data
	data := make([]interface{}, len(d.data)*2)
	if d.head == 0 {
		copy(data, old)
	} else {
		n := copy(data, old[d.head:])
		copy(data[n:], old[:d.head])
	}
	d.data = data
	d.head = 0
	d.tail = d.count
}

func (d *Deque) shrink() {
	l := len(d.data) / 4
	if l < d.count {
		return
	}
	if l < d.init {
		return
	}

	old := d.data
	data := make([]interface{}, len(d.data)/2)
	if d.tail > d.head {
		copy(data, old[d.head:d.tail])
	} else {
		n := copy(data, old[d.head:])
		copy(data[n:], old[:d.tail])
	}
	d.data = data
	d.head = 0
	d.tail = d.count
}

使用 slice 实现队列

入队时使用 append,出队时去掉队头元素 d.data = d.data[1:]

package main

type DequeSlice struct {
	data []interface{}
}

func NewDequeSlice(c int) *DequeSlice {
	return &DequeSlice{
		data: make([]interface{}, 0, c),
	}
}

func (d *DequeSlice) Enqueue(item interface{}) {
	d.data = append(d.data, item)
}

func (d *DequeSlice) Dequeue() (interface{}, bool) {
	if len(d.data) == 0 {
		return nil, false
	}
	item := d.data[0]
	d.data = d.data[1:]
	return item, true
}

使用 container/list 包实现队列

container/list 实现了一个双向队列,可以作为队列使用。使用 queue.PushBack(item) 入队,使用 queue.Remove(queue.Front()) 出队

比较

对这3种实现的入队、出队进行 Benchmark 测试。

package main

import (
	"container/list"
	"testing"
)

func BenchmarkDeque_Enqueue(b *testing.B) {
	d := NewDeque(100)
	for n := 0; n < b.N; n++ {
		d.Enqueue(d)
	}
}

func BenchmarkDequeSlice_Enqueue(b *testing.B) {
	d := NewDequeSlice(100)
	for n := 0; n < b.N; n++ {
		d.Enqueue(d)
	}
}

func BenchmarkLinkedList_Enqueue(b *testing.B) {
	d := list.New()
	for n := 0; n < b.N; n++ {
		d.PushBack(d)
	}
}

func BenchmarkDeque_Dequeue(b *testing.B) {
	d := NewDeque(10000)
	for i := 0; i < 1000; i++ {
		d.Enqueue(i)
	}
	b.ResetTimer()
	for i := 0; i < 1000; i++ {
		d.Dequeue()
	}
}

func BenchmarkDequeSlice_Dequeue(b *testing.B) {
	d := NewDequeSlice(10000)
	for i := 0; i < 1000; i++ {
		d.Enqueue(i)
	}
	b.ResetTimer()
	for i := 0; i < 1000; i++ {
		d.Dequeue()
	}
}

func BenchmarkLinkedList_Dequeue(b *testing.B) {
	d := list.New()
	for i := 0; i < 1000; i++ {
		d.PushBack(i)
	}
	b.ResetTimer()
	for i := 0; i < 1000; i++ {
		d.Remove(d.Front())
	}
}

func BenchmarkDeque_Enqueue_Dequeue(b *testing.B) {
	d := NewDeque(1)
	for i := 0; i < 1000; i++ {
		//1 2 4 8 16 ... 2^n
		for j := 0; j < 50; j++ {
			d.Enqueue(j)
		}
		for k := 0; k < 50; k++ {
			d.Dequeue()
		}
	}
}

func BenchmarkDequeSlice_Enqueue_Dequeue(b *testing.B) {
	d := NewDequeSlice(1)
	for i := 0; i < 1000; i++ {
		//1 2 4 8 16 ... 2^n
		for j := 0; j < 50; j++ {
			d.Enqueue(j)
		}
		for k := 0; k < 50; k++ {
			d.Dequeue()
		}
	}
}

func BenchmarkLinkedList_Enqueue_Dequeue(b *testing.B) {
	d := list.New()
	for i := 0; i < 1000; i++ {
		//1 2 4 8 16 ... 2^n
		for j := 0; j < 50; j++ {
			d.PushBack(j)
		}
		for k := 0; k < 50; k++ {
			d.Remove(d.Front())
		}
	}
}

func BenchmarkDeque_Enqueue_Then_Dequeue(b *testing.B) {
	d := NewDeque(8)
	for i := 0; i < 6; i++ {
		d.Enqueue(i)
	}
	b.ResetTimer()
	for j := 0; j < b.N; j++ {
		if j%2 == 0 {
			d.Enqueue(j)
		} else {
			d.Dequeue()
		}
	}
}

func BenchmarkDequeSlice_Enqueue_Then_Dequeue(b *testing.B) {
	d := NewDequeSlice(8)
	for i := 0; i < 6; i++ {
		d.Enqueue(i)
	}
	b.ResetTimer()
	for j := 0; j < b.N; j++ {
		if j%2 == 0 {
			d.Enqueue(j)
		} else {
			d.Dequeue()
		}
	}
}

func BenchmarkLinkedList_Enqueue_Then_Dequeue(b *testing.B) {
	d := list.New()
	for i := 0; i < 6; i++ {
		d.PushBack(i)
	}
	b.ResetTimer()
	for j := 0; j < b.N; j++ {
		if j%2 == 0 {
			d.PushBack(j)
		} else {
			d.Remove(d.Front())
		}
	}
}

结论

go_deque $ go version
go version go1.13.4 darwin/amd64


go_deque $ go test -bench=.
goos: darwin
goarch: amd64
pkg: go_deque
BenchmarkDeque_Enqueue-8                     	 96.3 ns/op
BenchmarkDequeSlice_Enqueue-8             	     97.9 ns/op
BenchmarkLinkedList_Enqueue-8                	202 ns/op
BenchmarkDeque_Dequeue-8                     	  0.000018 ns/op
BenchmarkDequeSlice_Dequeue-8                	  0.000003 ns/op
BenchmarkLinkedList_Dequeue-8                	  0.000005 ns/op
BenchmarkDeque_Enqueue_Then_Dequeue-8        	 24.6 ns/op
BenchmarkDequeSlice_Enqueue_Then_Dequeue-8   	 19.4 ns/op
BenchmarkLinkedList_Enqueue_Then_Dequeue-8   	 34.9 ns/op
PASS
ok  	go_deque	9.444s

入队

执行入队操作时,环形队列和 slice 实现性能一致,因为底层的操作大致一样的。双向链表在入队方面性能最差。

因为环形队列和 slice 都是将元素放到数组中,在数组无法再容纳更多元素时扩容数组至原来的2倍,然后将数据从旧数组复制到新数组,而双向链表是将元素插入到链表中,因此前两者占用更多的内存。

出队

执行出队操作时,slice 和双向链表表现相差无几,因为都是简单地移除元素在数组中的引用而已,而环形队列的表现则差一些,原因在于环形队列需要在元素数量不足数组数量1/4时缩减数组,也正是这个原因使得环形队列占用更少的内存,但也需要耗费更多的时间。

重复出入队

当出队、入队交替执行时,环形队列性能最好,slice次之,链表最差。原因在于环形队列不触发底层数组的重新分配,只需要修改队头和队尾索引值,而slice则随着运行需要不断重新分配底层数组。

简言之

考虑到实际我们使用队列的场景,如果队列中元素数量经常忽大忽小,可以考虑用 slice,如果队列中元素数量比较稳定在一个范围,可以考虑用环形队列避免内存分配。至于双向链表,emmmm……

最后

水平有限,或有错漏,烦请斧正。

文中代码已传 Github