Implementation of a lock free queue using CompareAndSwap in Go

Question

Here is my implementation of a lock free queue using CompareAndSwap operation.

type LockFreeQueue struct {
 capacity int
 list []int
 top int32
 numPopOps int32
}
func (lfq *LockFreeQueue) Pop() (value int, empty bool) {
 for {
 top := atomic.LoadInt32(&lfq.top)
 if top == -1 {
 return -1, true
 }
 if top == atomic.LoadInt32(&lfq.top) {
 val := lfq.list[lfq.top]
 if atomic.CompareAndSwapInt32(&lfq.top, top, top-1) {
 atomic.AddInt32(&lfq.numPopOps, 1)
 return val, top-1 == -1
 }
 }
 }
}

The Pop function is working as I intend it to. Is there any improvements that I can do in the code to make it more efficient?

I have intentionally not posted the code for Push function as I think it is not needed for the context.

• pacmaninbw: Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. If you want a review of updated code please post a follow up question.
• Tauseef Ahmad: Thanks, I'll keep that in mind

Answer 1

• Could top-1 == -1 be replaced by top==0?
• top == atomic.LoadInt32(&lfq.top) is likely not needed: LoadInt was already done before and it could have changed before and it could have changed after this line anyways.

There is also API contract question: empty == true is returned when there was nothing to read... but also when the last element was read. I would propose that empty is replaced by "nothing_to_read" and return val, top-1 == -1 should become ..., false.

Is the assumption that Pop can be called from one thread only? If not then val := lfq.list[lfq.top] is not safe. lfq.top may be updated just before this line is executed to -1 which would result in out of bounds read. lfq.list[top] would probably work.

• Tauseef Ahmad: Yeah I remove the condition top == atomic.LoadInt32(&lfq.top) and it worked but there was a data race on val := lfq.list[lfq.top] so I changed it to val := lfq.list[top] which removed the data race