Subj : Re: Best locking methods
To   : comp.programming.threads
From : Uenal Mutlu
Date : Thu Apr 07 2005 05:56 am

"Chris Thomasson" wrote
> > What is the best (fastest) method to synchronize access
> > to a memory block which is shared by say 5 reader threads
> > and 5 writer threads?
>
> Depends...
>
> 1. Do you receive a "lot" more reads than writes, or vise versa?

Say, it is a sorted vector of structures. The vector has to grow
when new items need to be inserted.
Usually the reads are more often than writes (and the writers also
need first some reading for locating the element and to test for dupe etc).
But I can imagine applications where the opposite can also be true.
So the method should be generally applicable.

> 2. How is the average contention level? When reader thread(s) decide to
> access the data-structure will they more than likely be in contention with
> writer thread(s)?

Say each item consists of a key and value. The task of the writers is
to update the value of each item when new data is available. If a new
key is not present yet in the list then it needs to be inserted.

The readers perform either sequential access by iterating over all
elements, or do a direct access to an element using the key and bsearch
to get the latest value of the item.

> 3. Is this a "performance sensitive" data-structure in your application?

Yes, it is "realtime" data of say of some hi-speed sensors, but data is
delivered only if there is a change, so there is not a fixed frequency,
and also the order of the data is not predictable.
Say there are about 50,000 keys, and their values change about 5 times
a second on average. To keep it general, the list cannot be pre-filled;
it must be done on demand, ie. when a new key is received by the writers.

> There are different solutions to your problem ranging from simple mutexs all
> the way to fairly complicated lock-free algorithms. We need a bit more info
> from you...
> :)

As said: it is just one volatile pointer pointing to a memory block which
must be reallocd for inserting new items into the sorted vector (this is
done using a "buffered" method, ie. 10% or 25% more space is reallocd
and that gets used till the next realloc)

Each item is a fixlen structure consisting of a unique key, plus its data.
Obviosly the writer threads are those who update the list.
The readers are free how they access the list; besides using a Find(key)
function they can also walk sequentially in the list, ie. in a for loop.
Access to an item is done via baseptr + the physical element number ("record
number").

This works fine using Critical Section's, but since there seem to be many
methods available I wondered whether there's maybe a significantly faster
method.  What would others use for such a task?

.