Boost logo

Boost :

From: Borgerding, Mark A. (MarkAB_at_[hidden])
Date: 2000-03-03 16:20:48


> -----Original Message-----
> From: Miki Jovanovic [mailto:miki_at_[hidden]]
> Sent: Friday, March 03, 2000 3:00 PM
> To: boost_at_[hidden]
> Subject: [boost] Re: llinked_ptr in the vault
>
>
>
> Hi Mark,
>
> Smart pointers in my apps are not copied many times, so I am really
> interested in your linked pointers.
>
> I just have couple of small issues with linked_ptr. I'll try to keep
> them brief. They all seem to be related to synchronisation...
>
> - Small issue is having Windows specific code.

Unfortunately, there are not many platform independent synchronization
packages. I have tried to hide any platform specific code behind
appropriate #ifdefs.
Would anyone be interested in working on a cross-plaatform synchronization
library? I know Win32 pretty well, but I know very little about pthreads or
other methods.

>
> - Big issue is that all linked_ptr's share the same critical section.
> This means that all pointer assignments will be serialised accross
> threads and even processors on multi processor machines.

True, but the section of code is pretty short. The only viable alternative
(that I can see) would be to have a critical section associated with each
ptr, which would quickly eat up far more time than serializing assignments.
It would also bloat the sizeof(linked_ptr). I suspect you would have to
scale to hundreds of processors to make up for the overhead of having
separate synchronization objects for each ptr.

Ooh, I just thought of another possibility!

Suppose that there were a fixed number of synchronization objects (call them
mutexes to remain more platform-objective).
In a given assignment, hash the ptr, and mod-divide by the number of
mutexes. Thus, all the linked_ptrs that control a given heap object would
use the same mutex. By tuning the number of available mutexes according to
the number of processors, you could minimize unnecessary contention.

One problem with this: since a given linked_ptr object would be moving
between two linked rings, the neighbors in both rings could be operating in
other threads. I think you would need to lock the mutexes for both rings.
Perhaps this could be a conditional compile also?

Hmmm, at any rate, I doubt the contention would matter with less than around
4 processors.

>
> - Also huge issue, you protect the left, right pointers, however, you
> do not protect ptr. In your setup, left, right AND ptr, must
> be changed
> together, or inconsistency will occur. Examine ptr1 = ptr2 and ptr1 =
> ptr3 executing in parallel.

I don't think this is an issue. Even with primitive pointers, the above
case for primitive pointers would have undefined results. ptr1 could end up
with the value of ptr2, ptr3, or something else entirely could happen
(crash?). The same thing is true for linked_ptr. As far as synchronization
issues, the case for dumb pointers basically boils down to the same thing as
if they were dumb pointers.

I think a more reasonable scenario is ptr2 = ptr1 and ptr3 = ptr1 executing
in parallel.
I believe you will find that is safe.

I basically wanted to give the same level of thread safety that is given
with dumb pointers.
My main intent was to protect the following cases
1) ptr1 and ptr2 point to the same object && ptr1 is in use in a different
thread than ptr2.
2) two parallel threads have const (non-mutating) access to a given
linked_ptr object

>
> - Sorry for not compiling your code, but will it compile with a static
> variable declaration without the corresponding .cpp file where it is
> defined?

It is declared static (and defined) within the scope of the function. As
long as that function does not somehow end up with multiple definitions, I
think it should be okay.

Mark Borgerding


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk