1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$ Commented May 12, 2023 at 13:35
  • \$\begingroup\$ Thanks, I'll keep that in mind \$\endgroup\$ Commented May 12, 2023 at 15:01

1 Answer 1

2
\$\begingroup\$
  • 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.

\$\endgroup\$
1
  • \$\begingroup\$ 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 \$\endgroup\$ Commented May 12, 2023 at 11:39

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.