Re: How to make this program more efficient?
On Sep 14, 5:00 pm, Jerry Coffin <jcof...@taeus.com> wrote:
In article <692dead8-f8f7-43d5-99c4-
58534dfff...@r15g2000prh.googlegroups.com>, billdavi...@gmail.com
says...
[ Please don't quote signatures ... ]
Sorry, I am still not so clear about what you mean. I am not
sure if it's a little like RCU algorithom mentioned by Jon
Harrop. But as I know RCU is also based on some lock. I can
collect the data into a separate map and try to copy it to
old map after update. But for readers, how could they know
the map is in updating or not if they don't try to check
some condition object (will fail to work if condition check
pass but map is updated during following access) or retrieve
a scoped_lock before they read data from map? Then it will
be almost same as the original lock solution I have said.
Yes, you still need a lock. All you're doing is shortening the
time during which the lock is needed -- while you're
collecting the data (which typically tends to be fairly slow)
the original map remains unlocked.
More correctly, it remains read-locked. You only need the write
lock when updating the image. Since many threads can acquire
the read lock simultaneously, however, this doesn't really slow
up the readers much.
Only after you've accumulated all the data for an update, you
lock the map, update it, and then unlock it. If accumulating
the data for an update is almost as fast as, or faster than,
updating the map itself, the gain is quite small. More often,
however, accumulating the data is fairly slow, and the update
itself is fairly fast, in which case this can gain quite a
bit.
To atomic swap, although I don't know how to implement it, I
still wonder if it's safe enough to the following scenario:
1) Thread 1 is reading data from the map via the old pointer of map,
then it is suspended by OS.
2) Thread 2 begin to update and swap the pointer to the map to a new
one.
Then can Thread 1 work well if it's copying data from the original map
when it's interrupted?
To stl::map or some other implementation of map, read the old map may
cause some memory access violation error.
The atomic swap was involved in an entirely separate solution.
You start by creating a copy of the original map. You then
update your copy. You then (and this is where the atomic swap
comes into play) substitute the newly updated map for the old
one.
To do that, you start with a pointer to the original map. You
then have a pointer to your modified map. You do an atomic
swap to exchange the two, updating the pointer to point to the
new map, and getting a pointer to the old map so you can
dispose of it.
This is the one point at which John Harrop's (otherwise
nonsensical) statements did give a glimmer of truth. Knowing
when you can dispose of the old map requires knowing when
nobody else is accessing it. You can do that a number of
different ways. One is to use garbage collection. This is
simple, but creates the possibility of a map existing long
after it's no longer really in use.
But only if no one else needs the memory it's using. Typically,
that's not a problem. However, I've argued strongly in favor of
garbage collection before, but in this case, the main difference
compared to reference counting is that it's already implemented.
Because you're not making many copies of the root pointer, and
only the root of the map (and not each individual allocated
block) needs to be reference counted, I doubt that garbage
collection will gain much other than the fact that the thread
safe implementation is already there. And since the upcoming
standard will almost certainly require a thread safe
implementation of boost::shared_ptr, that could really be a
viable alternative. (Another advantage of garbage collection
here is that the garbage collector I use was written by Hans
Boehm. Someone who really understands threading issues. I feel
a bit less sure about Boost---I'd like to be proven wrong, but
I've seen so many problems with supposedly thread safe solutions
to different problems, that I've become exceedingly sceptical.)
Another is to use something like reference counting so you can
determinstically dispose of the map as soon as it's no longer
in use. Depending on usage pattern, you can often reduce the
reference count to a single bit for each thread (basically a
mutex).
You'll have to explain that one to me. (I agree that this is a
pattern in which reference counting works extremely well, but
I'm pretty sure you still need more than a single bit to
implement it.)
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34