Benefits of this library?

[jshnaidman]

What's the advantage, if any, of using this in place of standard slice?

Taken from Marwan Burelle's example on SO:

queue := make([]int, 0)
// Push to the queue
queue = append(queue, 1)
// Top (just get next element, don't remove it)
x = queue[0]
// Discard top element
queue = queue[1:]
// Is empty ?
if len(queue) == 0 {
    fmt.Println("Queue is empty !")
}

Does deque offer any benchmarks comparing it to standard slice implementations?

[gammazero]

The advantage is to keep adding and removing without needing to allocate more space or move items in the slice.

If you keep appending to a slice and removing items from the front, the slice will need to grow its underlying memory. In your example, queue = append(queue, 1) will allocate more memory and copy the underlying memory from the old to the new. Also queue = queue[1:] will move the start of the slice but will not allow the old queue[0] to be reused in the slice.

Also, suppose you want to insert items to the front of the queue. This means you will need to make more room in the queue or create a new larger queue, and then move all the items one place towards the back, then add the new item at position 0.

The deque avoids all that allocating and copying by using a circular buffer that keeps moving the head and tail inside the same slice as data is written and read. https://github.com/gammazero/deque/wiki#deque-diagram

[woodliu]

Hi, gammazero. I run a benchmark to compare the slice append and deque PushFront/PushBack with int and string type, i hope deque operation should fast than slice operation, but it doesn't, here is the code:

func BenchmarkSliceAppendInt(b *testing.B) {
	var s []int
	for i := 0; i < b.N; i++ {
		s = append(s, i)
	}
}

func BenchmarkPushFrontInt(b *testing.B) {
	var q Deque[int]
	for i := 0; i < b.N; i++ {
		q.PushFront(i)
	}
}

func BenchmarkPushBackInt(b *testing.B) {
	var q Deque[int]
	for i := 0; i < b.N; i++ {
		q.PushBack(i)
	}
}

func BenchmarkSliceAppendString(b *testing.B) {
	var s []string
	for i := 0; i < b.N; i++ {
		s = append(s, "hello")
	}
}

func BenchmarkPushFrontString(b *testing.B) {
	var q Deque[string]
	for i := 0; i < b.N; i++ {
		q.PushFront("hello")
	}
}

func BenchmarkPushBackString(b *testing.B) {
	var q Deque[string]
	for i := 0; i < b.N; i++ {
		q.PushBack("hello")
	}
}

And here is the result:

goos: darwin
goarch: arm64
pkg: github.com/gammazero/deque
BenchmarkSliceAppendInt
BenchmarkSliceAppendInt-8      	100000000	        10.50 ns/op
BenchmarkPushFrontInt
BenchmarkPushFrontInt-8        	143916168	        11.31 ns/op
BenchmarkPushBackInt
BenchmarkPushBackInt-8         	100000000	        11.27 ns/op
BenchmarkSliceAppendString
BenchmarkSliceAppendString-8   	42217932	        30.71 ns/op
BenchmarkPushFrontString
BenchmarkPushFrontString-8     	81312292	        31.59 ns/op
BenchmarkPushBackString
BenchmarkPushBackString-8      	67633578	        35.78 ns/op

I ran it on my mackbook, with golang 1.21.0

[woodliu]

And here is another benchmark to compare the golang standard container/list with it, here is the code:

package deque

import (
	"container/list"
	"testing"
)

func BenchmarkListPushFrontInt(b *testing.B) {
	l := list.New()
	for i := 0; i < b.N; i++ {
		l.PushFront(i)
	}
}

func BenchmarkPushFrontInt(b *testing.B) {
	var q Deque[int]
	for i := 0; i < b.N; i++ {
		q.PushFront(i)
	}
}

func BenchmarkListPushBackInt(b *testing.B) {
	l := list.New()
	for i := 0; i < b.N; i++ {
		l.PushBack(i)
	}
}

func BenchmarkPushBackInt(b *testing.B) {
	var q Deque[int]
	for i := 0; i < b.N; i++ {
		q.PushBack(i)
	}
}

func BenchmarkListPushFrontString(b *testing.B) {
	l := list.New()
	for i := 0; i < b.N; i++ {
		l.PushFront("hello")
	}
}

func BenchmarkPushFrontString(b *testing.B) {
	var q Deque[string]
	for i := 0; i < b.N; i++ {
		q.PushFront("hello")
	}
}

func BenchmarkListPushBackString(b *testing.B) {
	l := list.New()
	for i := 0; i < b.N; i++ {
		l.PushBack("hello")
	}
}

func BenchmarkPushBackString(b *testing.B) {
	var q Deque[string]
	for i := 0; i < b.N; i++ {
		q.PushBack("hello")
	}
}

func BenchmarkListInsert(b *testing.B) {
	l := list.New()
	for i := 0; i < b.N; i++ {
		l.PushBack(i)
	}
	e4 := l.PushBack(4)
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		l.InsertBefore(l.Len()/2, e4)
	}
}

func BenchmarkInsert(b *testing.B) {
	q := new(Deque[int])
	for i := 0; i < b.N; i++ {
		q.PushBack(i)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		q.Insert(q.Len()/2, -i)
	}
}

func BenchmarkListYoyo(b *testing.B) {
	l := list.New()
	for i := 0; i < b.N; i++ {
		for j := 0; j < 65536; j++ {
			l.PushBack(j)
		}
	}
}

func BenchmarkYoyo(b *testing.B) {
	var q Deque[int]
	for i := 0; i < b.N; i++ {
		for j := 0; j < 65536; j++ {
			q.PushBack(j)
		}
	}
}

And here is the result:

goos: darwin
goarch: arm64
pkg: github.com/gammazero/deque
BenchmarkListPushFrontInt
BenchmarkListPushFrontInt-8      	24749220	        71.06 ns/op
BenchmarkPushFrontInt
BenchmarkPushFrontInt-8          	170587078	         6.116 ns/op
BenchmarkListPushBackInt
BenchmarkListPushBackInt-8       	18711698	        61.20 ns/op
BenchmarkPushBackInt
BenchmarkPushBackInt-8           	153760459	        10.11 ns/op
BenchmarkListPushFrontString
BenchmarkListPushFrontString-8   	22249174	        58.63 ns/op
BenchmarkPushFrontString
BenchmarkPushFrontString-8       	90458510	        32.04 ns/op
BenchmarkListPushBackString
BenchmarkListPushBackString-8    	21515786	        49.91 ns/op
BenchmarkPushBackString
BenchmarkPushBackString-8        	91012513	        33.46 ns/op
BenchmarkListInsert
BenchmarkListInsert-8            	19552266	        53.17 ns/op
BenchmarkInsert
BenchmarkInsert-8                	  111536	    122618 ns/op
BenchmarkListYoyo
BenchmarkListYoyo-8              	     354	   3928389 ns/op
BenchmarkYoyo
BenchmarkYoyo-8                  	    5184	    829642 ns/op

It really fast than container/list except the Insert benchmark, but there is a note in dequeu Insert that this is not the issue with it.

// Important: Deque is optimized for O(1) operations at the ends of the queue,
// not for operations in the the middle. Complexity of this function is
// constant plus linear in the lesser of the distances between the index and
// either of the ends of the queue.

So i think dqueue should compare with the container/list, they are both double chain and support the similar functions.

[gammazero]

Using a slice will always be faster per operation. Deque uses a slice internally, but keeps track of what elements in the slice are used and which are free for re-use. The advantage with Deque is reducing GC over time, particularly with long-running queue/dequeue activity.

Benchmarks that only write to the Deque and then only read from the Deque wiil not show any advantage. This is because Deque's internal memory is never being reused, it is only filled and drained.

Note: Deque now has a Grow function to pre-allocate space for n additional items, to avoid multiple resizes when adding many items. Also, setting the base capacity to something reasonable for your usage will improve performance. This can be set anytime by calling SetBaseCapacity- set it to the current capacity to prevent resizing down when removing a number of items and set back to default when done.

[MokoshHydro]

Maybe something changed, but when I rerun @woodliu benchmarks, I've got different results:

goos: darwin
goarch: arm64
pkg: supervend.com/vending/tmp/dequeu
cpu: Apple M2 Max
BenchmarkListPushFrontInt-12       	24672702	        55.98 ns/op	      55 B/op	       1 allocs/op
BenchmarkListPushBackInt-12        	27989072	        51.59 ns/op	      55 B/op	       1 allocs/op
BenchmarkListPushFrontString-12    	29431180	        47.96 ns/op	      48 B/op	       1 allocs/op
BenchmarkListPushBackString-12     	36967632	        39.58 ns/op	      48 B/op	       1 allocs/op
BenchmarkListInsert-12             	29758798	        43.07 ns/op	      56 B/op	       2 allocs/op
BenchmarkListYoyo-12               	     393	   3165393 ns/op	 3667968 B/op	  130816 allocs/op
BenchmarkPushFrontInt-12           	371926376	         3.638 ns/op	      23 B/op	       0 allocs/op
BenchmarkPushBackInt-12            	411165542	         3.230 ns/op	      20 B/op	       0 allocs/op
BenchmarkPushFrontString-12        	88007994	        14.48 ns/op	      48 B/op	       0 allocs/op
BenchmarkPushBackString-12         	91170972	        14.10 ns/op	      47 B/op	       0 allocs/op
BenchmarkInsert-12                 	  117538	    119331 ns/op	      17 B/op	       0 allocs/op
BenchmarkYoyo-12                   	    4737	    241895 ns/op	 1813370 B/op	       0 allocs/op
BenchmarkPushFrontInt2-12          	489135834	         2.469 ns/op	       8 B/op	       0 allocs/op
BenchmarkPushBackInt2-12           	463968122	         2.561 ns/op	       9 B/op	       0 allocs/op
BenchmarkPushFrontString2-12       	357804555	         4.007 ns/op	      24 B/op	       0 allocs/op
BenchmarkPushBackString2-12        	363913341	         3.418 ns/op	      23 B/op	       0 allocs/op
BenchmarkInsert2-12                	  115701	    118634 ns/op	      18 B/op	       0 allocs/op
BenchmarkYoyo2-12                  	    4896	    251254 ns/op	 1754466 B/op	       0 allocs/op
BenchmarkSliceAppendInt-12         	729748897	         5.161 ns/op	      46 B/op	       0 allocs/op
BenchmarkSliceAppendString-12      	46989243	        24.43 ns/op	      84 B/op	       0 allocs/op

The BenchmarkXXX2 have q.SetBaseCap(b.N) before entering bench loop. Looks like dequeu is always faster compared to both slice and list.