Re: [Boost-users] Thread-safe smart pointers, hashtables without locking

From: james.jones_at_[hidden]
Date: 2006-05-05 15:11:10

From: Ray Whitmer <ray_at_[hidden]>
>> This would be truly thread-safe but might perform better if you  
>> have lots of simultaneous readers/writers. I haven't tested this,  
>> but if you do, I'd be interested to hear the results.
> 
> I don't think it even begins to be thread-safe, because it doesn't  
> begin to deal with reallocation of the array itself...

That's certainly true. I guess I was thinking of a hashtable whose interface is that it is allocated with a fixed size and not reallocated (although it might be copy-constructed to a hashtable of a different size). If modern hashtables reallocate their storage, that would certainly have to be done in a thread-safe manner.

> Here is my first stab at a solution:
> 
> 2. Perform changes to the hashtable in a manner that, given atomic  
> loads or stores of aligned pointers, never leaving the table in a  
> state that simultaneous readers cannot use it.  This is very easy  
> compared to the allocation issues, and I have been doing this in Java  
> for years.  I would be happy to expand on this.  This write operation  
> may include releasing objects with ref-count 1, if this is supposed  
> to be a weak hashtable that does not keep unused objects in the index.

[rest snipped]

The algorithm makes sense, and if all these claims hold then it should work, I think. I'm still concerned about step (2), however, if only because of the assumption that what you write as a load/store in C++ maps to a load/store in ML. Will it? Always? I ask as a non-rhetorical question: does the C++ standard *guarantee* it? Because if it doesn't then it seems like a potential problem, but maybe I'm being too careful.

Have you read any of the literature on lock-free data structures, btw? There was articles in the October and December '04 C/C++ User Journal about them.

I realize that I haven't answered your original question about atomic_count, btw, and I'm sorry: the reason is simply that I don't know!

-
James Jones             Administrative Data Mgmt.
(v)732-510-1806         375 Raritan Center Pkwy, Suite A
(f)732-510-1855         Edison, NJ 08837
Visit us on the web at http://www.firstinvestors.com/