Subject: Re: [boost] [lockfree::fifo] Review
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2010-01-20 18:51:31
"Helge Bahmann" <hcb_at_[hidden]> wrote in message
news:alpine.DEB.1.10.1001191553030.25332_at_m65s28.vlinux.de...
> On Mon, 18 Jan 2010, Chris M. Thomasson wrote:
>
>> "Helge Bahmann" <hcb_at_[hidden]> wrote in message
>> news:201001181953.33044.hcb_at_chaoticmind.net...
>>> Am Saturday 16 January 2010 03:15:44 schrieb Chris M. Thomasson:
>>>> FWIW Helge, here is a new proxy garbage collector algorithm of mine
>>>> that I
>>>> am currently experimenting with:
>>>>
>>>> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/a
>>>> 53f24de178b419f
>>>
>>> interesting concept, but AFAICT it shares two undesirable properties
>>> with my
>>> implementation: Reclamation can be delayed indefinitely if
>>>
>>> - one thread is "stuck" within the critical section (e.g. scheduled
>>> away)
>>
>> Well, if a thread actually deadlocks or "permanently livelocks" within
>> the critical section, then no reclamation can occur.
>
> this means that reclamation (and by extension writing with bounded amount
> of memory) is not wait-free (this is not a problem I think, just pointing
> out)
Yes; very good point Helge. I simply _failed_ to clarify that the wait-free
properties come from the fact that I am not using loops (e.g., CAS loop) to
acquire/release a reference to a collector object. This has been a point of
interest in the past over on `comp.programming.threads'. Previous collectors
used CAS-loop to either acquire and/or release a reference. This does not
work out to well for a reader-writer pattern because only one reader thread
can gain access while the others fail their CAS and have to try again. This
lock-free property can result in fairly poor performance for readers.
Therefore, we have been coming up with wait-free techniques to allow readers
to gain access without looping around in software.
>>> - threads interlock such that at least one thread is always within the
>>> critical section
>>
>>> Right?
>>
>> No. My proxy algorithm is N = 2, while yours is N = 1 where N is the
>> number of collector objects. This means that you only have a _single_
>> reference count. During periods of load, this single reference count
>> might never reach zero and the garbage will keep piling up.
>
> [snip explanation]
>
> Okay thanks for your explanation, I did not understand your code correctly
> the first time, but now things are much more clear.
That's great! :^)
> The concept is very nice indeed, and I agree that N=1 and N=2 makes quite
> a difference. I *think* that your approach is much more valuable as a
> building block for "object-local RCU" for data structures with long-lived
> read access than ABA prevention for producer/consumer data structures
> (where the read-side critical section is very short).
I think I agree with that statement.
> Thanks for sharing the code,
You are welcome! If you can think of any optimizations I would LOVE to hear
all about them. One thing I can think of would be to remove the need for
threads to actually destroy objects. This can be moved to a separate thread
or the objects can simply be stuck in a cache to be reused. For instance, if
the `proxy::release(...)' procedure was turned into a function which
returned a pointer to a stack of nodes that are in a quiescent state, then
the thread could decide what to do with them. I think that this would make
the algorithm more flexible.
Please note that this is only an initial implementation and it's more of a
proof-of-concept than anything. There are probably many improvements that
can be made...
;^)
> I can already think of an application for this in my own code :)
Cool. IMVHO, the proxy collector is fairly generic in that you can use it to
solve memory reclamation in many different types of non-blocking algorithms
and *usage patterns. I think that if Boost does include a non-blocking
library, then something along the lines of the collector algorithm should
probably be included.
[*] - I am experimenting with the collector using the following usage
pattern. Imagine a database server that get very many sustained query on a
regular basis. Now, reader threads receive search requests and then execute
the query on a dynamic shared data-structure. Here is high-level pseudo-code
of how I am constructing the logic of the reader threads:
__________________________________________________________________
#define SYNC_INTERVAL 256
#define DEFER_THRESHOLD 128
typedef proxy<DEFER_THRESHOLD> proxy_type;
static proxy_type g_proxy;
void reader_thread()
{
proxy_type::collector* c = &g_proxy.acquire();
for (unsigned i = 1 ;; ++i)
{
query_type* q = try_to_get_a_query_request();
if (! q)
{
g_proxy.release(*c);
q = wait_for_a_query_request();
c = &g_proxy.acquire();
}
execute_query(q);
if (! (i % SYNC_INTERVAL))
{
g_proxy.release(*c);
c = &g_proxy.acquire();
}
}
g_proxy.release(*c);
}
__________________________________________________________________
Instead of acquiring/releasing a collector object for every single execution
of a query this technique instead attempts to amortize the number of times a
reader thread needs to acquire/release a collector.
Now, I can think of a possible optimization/enhancement to the proxy
algorithm itself. Take note that an odd reference count denotes that a
collection cycle is in progress. Therefore, if a reader thread can simply
test if the reference count of it's acquired collector object is even, then
it simple does not actually "need" to release a reference to it. If it's
odd, then a release is necessary in order to move along the current
collection process. This would allow the reader threads acquire/release
pattern to be amortized across the actual garbage deferment threshold. I
think I am going to alter the algorithm in order to support the following
usage pattern:
__________________________________________________________________
#define DEFER_THRESHOLD 256
typedef proxy<DEFER_THRESHOLD> proxy_type;
static proxy_type g_proxy;
void reader_thread()
{
proxy_type::collector* c = &g_proxy.acquire();
for (;;)
{
query_type* q = try_to_get_a_query_request();
if (! q)
{
g_proxy.release(*c);
q = wait_for_a_query_request();
c = &g_proxy.acquire();
}
execute_query(q);
if (c->is_collecting())
{
g_proxy.release(*c);
c = &g_proxy.acquire();
}
}
g_proxy.release(*c);
}
__________________________________________________________________
This would allow reader threads to curn along during periods of load with
fairly low overhead. I say this because the only time the readers would have
to release their collector object and re-acquire it is when they must
explicitly wait for query requests, or when the garbage threshold was
reached and a collection cycle was initiated by a writer thread. There are
some fairly promising enhancements I think I can make to the collector, and
that is one of them.
Humm...