Re: question about mpmc queue

[Dmitry Vyukov]

On Sat, Aug 20, 2016 at 7:28 AM, Gabi Melman <gmel...@gmail.com> wrote:
> Hi Dmitry,
>
> I am the the author of spdlog (https://github.com/gabime/spdlog) lib which
> use your mpmc queue (a siglhly modified version:
> https://github.com/gabime/spdlog/blob/master/include/spdlog/details/mpmc_bounded_q.h)
>
> I have quetion My about what would be the best/accurate way to get the size
> of the queue.
> I came up with :
>
>
> size_t approx_size()
> {
> size_t first_pos = dequeue_pos_.load(std::memory_order_relaxed);
> size_t last_pos = enqueue_pos_.load(std::memory_order_relaxed);
> return last_pos > first_pos ? last_pos - first_pos : 0;
> }
>
> but I am not sure it is accurate or whether it could be replaced with
> something better.

+lock-free group

Hi Gabi,

Your code is a reasonable approximation on the queue size. You can
also cap it by maximum capacity, because you can read dequeue_pos_,
then lots of items are pushed/popped, then you read enqueue_pos_ and
the result can be arbitrary large.

If you want more precise size, you can get an atomic snapshot using
the following technique. It will yield some actual size of the queue
while size operation runs. Here is an example from Go runtime:
https://github.com/golang/go/blob/master/src/runtime/proc.go#L4005
And here is a similar one from TensorFlow runtime:
https://bitbucket.org/eigen/eigen/src/cd5824eb9fb275e5b0edc8a7af95e8af85fe9231/unsupported/Eigen/CXX11/src/ThreadPool/RunQueue.h?at=default&fileviewer=file-view-default#RunQueue.h-155
In both these cases that size does not spuriously return 0 if the
queue never become empty while the operation runs.
In either case I would suggest to write some stress tests. For
example, you can write a test where the queue never becomes empty and
ensure that size never returns 0. Of you can maintain size between 5
and 10 and ensure that size returns values in that range.

[Dmitry Vyukov]

If dequeue returns false, the queue is empty.


On Sat, Aug 20, 2016 at 11:46 AM, Gabi <gmel...@gmail.com> wrote:
> Thanks for your response! I will look into these examples.
> Is there an alternative way to just determine if the queue is empy?
>
> Gabi

--
Dmitry Vyukov

All about lockfree/waitfree algorithms, multicore, scalability,
parallel computing and related topics:
http://www.1024cores.net