Solved: Re: Non-blocking data structures vs. garbage collection - Page 2

Bartlomiej · ‎07-24-2009

Hello,

I'm not sure if it's the right forum to ask this question, but it seems so; sorry if I'm wrong.
I've been studying lock-free algorithms extensively for some time, read many papers, group discussions, etc.
My question is: is it in general possible to create lock-free dynamic data structures without garbage collection?

Let us consider the following simple example: a linked list.
struct elem {
//... some data
elem *nxt;
//... constructors, etc.
};

Now, any function, traversing through the list has to access an element having the hook to the previous one.
So, we have a pointer elem *tmp that points to an element of the list and we want to access tmp->nxt.
So, we check if (tmp->nxt != NULL) and... we still know nothing, because there is no way to assure other thread did not delete the element between the checking and another operation we do (whatever it is). Any form of reference counting, etc. keeps this race condition problem,

Do I overlook anything?
So? Is garbage collection inevitable?

Thanks in advance for any clarifications or comments.
Best regards

jimdempseyatthecove · ‎07-24-2009

Garbage collection is not required due to you trashing the list by ways of unprotected CAS/DCAS/other techniques.

Garbage collection is required _because_ although you can remove a node from the list (safely or unsafely) you won't know if the node is in use (without adding reference counters etc...).

Since you currently do not know if the node is in use, your recourse is to ONLY remove the node from the list, then at some time later determine the node is no longer in use (then delete - garbage collect)e.g. at position in code when you know the list is not in use or at a time when you know no thread could possibly contain a pointer to that node.

If you use a reference counter .AND. place the reference counter in the node, you cannot find the node and bump the reference count instantaneously.

You can use coding practices to circumvent this issue. (at a cost). Example:

Place reference counter in node.
Place "intending to bump reference counter" counter in list header.

Then

Bump "intending to bump reference counter" counter in list header
(return value tells you delete may be in progress so dec, back off and retry)

Search list for node

Bump referencecounter in node
(return value tells you if node is reserved for exclusive use, if so, dec, back off, retry)

Un-bump "intending to bump reference counter" counter in list header

This requires 2 interlocked inc and 1 interlocked dec to reference the node

Releasing the node requires 1 interlocked dec

This is 4 expensive interlocked operations simply because you want any and every thread to concurrently insert/delete nodes.

Now that you know how much this costs, you might be willing to accept a less expensive round about means for adding and/or deleting nodes. Possibly one without interlocks (or with one interlock) for n * insert/deletes.

Jim Dempsey

View solution in original post

Chris_M__Thomasson · ‎08-10-2009

Quoting - bartlomiej

Hello,

I'm not sure if it's the right forum to ask this question, but it seems so; sorry if I'm wrong.
I've been studying lock-free algorithms extensively for some time, read many papers, group discussions, etc.
My question is: is it in general possible to create lock-free dynamic data structures without garbage collection?

Let us consider the following simple example: a linked list.
[...]

Do I overlook anything?
So? Is garbage collection inevitable?

Traditional GC is not actually needed. IMVHO, it helps to think of a different concept: `User Application Assisted Object Lifetime Management. For instance, some application implementations do not really mind creating an explicit abstraction of `DWCAS that boil's down to native architecture instructions (e.g., `CMPXCHG8B' on IA-32, or perhaps `CASX' on SPARC 32); no garbage collection required.

You can even define so-called synchronization epoch(s) made up of, perhaps a plurality of critical points within youre applications infrastructure, and subsequently use those "given points in time" to create a robust specialized lifetime management system. Death might mean a completely different thing in your particular case.

First, try to think in terms of when youre application can _maximize_ the act of reusing objects for similar purposes. This simple act of recycling, resurrection, reincarnation or whatever can be beneficial even in a 100% pure GC environment.