[lockfree] how many items are queued?

lockfree.fifo provides the info if the queue is empty or not. is it possible to provide a function std::size_t size() const - returning how many items are queued at a specific timepoint? regards, Oliver -- Jetzt kostenlos herunterladen: Internet Explorer 8 und Mozilla Firefox 3 - sicherer, schneller und einfacher! http://portal.gmx.net/de/go/chbrowser

hi oliver,
lockfree.fifo provides the info if the queue is empty or not.
it is mainly done as debugging help, but it is not supposed to be used in concurrent code ...
is it possible to provide a function std::size_t size() const - returning how many items are queued at a specific timepoint?
there is no real way to implement it reliably, so i don't want to add this to the interface. if it would be implemented by iterating the internal linked list, objects could be inserted during the iteration (making the count incorrect). using an atomic integer, would also not be precise, since incrementing the integer and manipulating the fifo cannot be done atomically ... if you need to know, how many items are approximately in the queue, i'd suggest you use an atomic counter in your code, something like (pseudocode): fifo f; atomic_int c; ++c; bool enqueued = f.enqueue(); if (!enqueued) --c; ... bool dequeued = f.dequeue(); if (dequeued) --c; in this case, c is not the exact value of queue items, but an upper bound ... i don't really want to add more functions to the api, that are not thread-safe ... would this workaround fit your needs? cheers, tim -- tim@klingt.org http://tim.klingt.org Relying on the government to protect your privacy is like asking a peeping tom to install your window blinds. John Perry Barlow

Hello Tim,
hi oliver,
lockfree.fifo provides the info if the queue is empty or not.
it is mainly done as debugging help, but it is not supposed to be used in concurrent code ...
Because this function is available I thought it is safe to used it. What are the reasons that it is not supposed to be used?
is it possible to provide a function std::size_t size() const - returning how many items are queued at a specific timepoint?
i don't really want to add more functions to the api, that are not thread-safe ... would this workaround fit your needs?
I plan to use boost.lockfree in boost.task - the one-lock and two-lock queues provide size() returning how many items are queued. I think I'll drop this function so lockfree-fifo/stack will fit. so long, Oliver -- GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT! Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01

lockfree.fifo provides the info if the queue is empty or not.
it is mainly done as debugging help, but it is not supposed to be used in concurrent code ...
Because this function is available I thought it is safe to used it.
well, there is a warning in the docs, noting, that this function is not thread-safe :)
What are the reasons that it is not supposed to be used?
it may give you wrong results, because the check cannot be implemented in an atomic manner ... cheers, tim -- tim@klingt.org http://tim.klingt.org Relying on the government to protect your privacy is like asking a peeping tom to install your window blinds. John Perry Barlow

2009/9/4 Tim Blechmann <tim@klingt.org>:
lockfree.fifo provides the info if the queue is empty or not.
it is mainly done as debugging help, but it is not supposed to be used in concurrent code ...
Because this function is available I thought it is safe to used it.
well, there is a warning in the docs, noting, that this function is not thread-safe :)
I didn't look at your library, but I think that this decision is dangerous. I think that this debug functionalities should be enabled only if explicitly required by the user, who is assumed to know what is doing. Manuel Fiorelli

Manuel Fiorelli wrote:
2009/9/4 Tim Blechmann <tim@klingt.org>:
lockfree.fifo provides the info if the queue is empty or not.
it is mainly done as debugging help, but it is not supposed to be used in concurrent code ...
Because this function is available I thought it is safe to used it.
well, there is a warning in the docs, noting, that this function is not thread-safe :)
I didn't look at your library, but I think that this decision is dangerous. I think that this debug functionalities should be enabled only if explicitly required by the user, who is assumed to know what is doing.
There is precedence in form of shared_ptr<T>::use_count(). / Johan

lockfree.fifo provides the info if the queue is empty or not.
it is mainly done as debugging help, but it is not supposed to be used in concurrent code ...
Because this function is available I thought it is safe to used it.
well, there is a warning in the docs, noting, that this function is not thread-safe :)
I didn't look at your library, but I think that this decision is dangerous. I think that this debug functionalities should be enabled only if explicitly required by the user, who is assumed to know what is doing.
well, the user of the library has to make sure, that this function is not used in places, where a concurrent access to the queue is possible ... but, well, even _if_ it would be possible to atomically check, whether a stack/queue is empty, the result is not valid any more, at the time, when you use the result: fifo f; thread a: bool is_empty = f.empty(); // true thread b: f.enqueue(); thread a: if (is_empty) do_something(); // fifo is not empty any more so querying the state of lockfree data structures is always dangerous ... cheers, tim -- tim@klingt.org http://tim.klingt.org art is short - life is long Jack Kerouac

2009/9/4 Tim Blechmann <tim@klingt.org>:
well, the user of the library has to make sure, that this function is not used in places, where a concurrent access to the queue is possible ... but, well, even _if_ it would be possible to atomically check, whether a stack/queue is empty, the result is not valid any more, at the time, when you use the result:
Interesting observation: the result of empty() would be useless in any case. Manuel Fiorelli

Yes and no. empty() and esp size() are not generally useful in mutlti- threaded code, but they're not useless. There are some points in a threaded program where you *know* that no other thread can add or remove from a queue, because you design your application and know what your threads are doing. Perhaps you're (temporarily) under lock. And in those moments I don't see a problem with calling empty() or even size() (maybe you need it as a hint for dimensioning some buffers). And I wouldn't want to have a heavy-duty lock or other guarantee to make the result correct either. What's IMHO the correct response for empty(), size(), and other (non- thread-safe) functions is to document explicitly: bool empty() const; // Return whether a *snapshot* of this queue is empty. size_t size() const; // Return a *snapshot* of the size of this queue. And that's only if you can implement it atomically, of course. If you have to iterate or do a calculation, then even the documentation of size() could be wrong (there may never be a snapshot of the queue that has that size). And in that case, I wouldn't provide size() at all, fwiw. My $0.02, -- Hervé Brönnimann hervebronnimann@mac.com On Sep 4, 2009, at 5:46 AM, Manuel Fiorelli wrote:
2009/9/4 Tim Blechmann <tim@klingt.org>:
well, the user of the library has to make sure, that this function is not used in places, where a concurrent access to the queue is possible ... but, well, even _if_ it would be possible to atomically check, whether a stack/queue is empty, the result is not valid any more, at the time, when you use the result:
Interesting observation: the result of empty() would be useless in any case.
Manuel Fiorelli _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/ listinfo.cgi/boost

What's IMHO the correct response for empty(), size(), and other (non- thread-safe) functions is to document explicitly:
bool empty() const; // Return whether a *snapshot* of this queue is empty.
size_t size() const; // Return a *snapshot* of the size of this queue.
i see your point, but i doubt, it can be implemented correctly (at least with double-word cas primitives). the only possibility, that i see, is providing methods for upper and lower bounds using atomic integers that are incremented/decremented before/after the linearization points ... i will see, maybe it is possible to provide this facility based on template arguments. i don't want to add this to the default interface, since atomic operations require some hardware synchronization, which aren't really lightweight ... cheers, tim -- tim@klingt.org http://tim.klingt.org You don't have to call it music if the term shocks you. John Cage
participants (5)
-
Hervé Brönnimann
-
Johan Nilsson
-
Manuel Fiorelli
-
Oliver Kowalke
-
Tim Blechmann