Queues in Go

Coming from a C background looking at the following Go implementation of a queue immediately raised a big question for me.

type Intqueue []int

func (q *Intqueue) Add(i int) {
  *q = append(*q, i)
}

func (q *Intqueue) Remove() (int, bool) {
  if len(*q) == 0 {
    return 0, false
  } else {
    i := (*q)[0]
    *q = (*q)[1:]
    return i, true
  }
}

The Add function just appends elements to the end of the slice. But if you look at the Remove function you see it returns a new slice with offset 1 within the original slice. If you would do something like this in C the underlying array would just keep on increasing in size (in C you would use something like a ring buffer).

In Go you can also easily implement a ring buffer. But I was wondering if the Go runtime was smart enough with slices that this would not be necessary. To test this I wrote the following simple program.

package main

import (
  "fmt"
  "time"
  "runtime"
)

func main() {
  t := time.Tick(time.Second)
  q := make(Intqueue, 0)

  for i := 1; i > 0; i++ {
    q.Add(i)
    i++

    if len(q) > 10 {
      q.Remove()
    }

    select {
    case <-t:
      var m runtime.MemStats
      runtime.ReadMemStats(&m)
      fmt.Printf("cap: %d, len: %d, used: %d\n", cap(q), len(q), m.Alloc)
    default:
    }
  }
}

As you can see it adds a new integer to the queue and if it’s bigger than 10 elements it removes on as well. It also prints the capacity of the slice, the number of used elements and the overall memory usage each second.

The output looks something like this:

cap: 14, len: 10, used: 303352
cap: 19, len: 10, used: 267640
cap: 19, len: 10, used: 305160
cap: 18, len: 10, used: 312680
cap: 17, len: 10, used: 278600
cap: 19, len: 10, used: 176040
cap: 17, len: 10, used: 271400
cap: 16, len: 10, used: 201480
cap: 18, len: 10, used: 307400
cap: 17, len: 10, used: 214920
...

Conclusion

As you can see the Go runtime is smart enough not to keep increasing the underlying array. Instead the slice capacity and memory usage keep quite constant.

For an update see: Faster queues in Go