An article whose URL was posted to the lock-free thread caught my eye. It's at MSDN Concurrent Access.
The basic idea is one I "discovered" on my own several years ago. The two extremes of ensuring exclusive access to data items within a collection are 1) lock the entire collection of data for a single thread, or 2) lock individual elements as threads need them. The former can lead to threads waiting idle as the one thread allowed access to the data holds up other threads that may not interfere with each other; the latter can use a lot of memory as each item in the data set has to have a lock object as part of it's memory allocation (i.e. 10000 locks for 10000 items to be used by 8 threads).
A good compromise is something in the middle. Specifically, use a fixed number of locks (256 in the paper cited above), then hash a key (or other unique identifier of data items) to determine the corresponding lock that must be held by a thread to access the data. The probability of two threads contending on the same lock will be the reciprocal of the number of locks used (assuming a good hash function).
For those fans of lock-free algorithms, this scheme can be easily implemented as a stopgap measure to quickly implement mutual exclusion until a lock-free solution can be devised. But does this scheme work in all data access cases? Are there some operations of data access that might not be correctly or adequately protected with this low contention scheme?
Anyone else have any thought or ideas on the utility of using a fixed number of locks for protecting access to large data collections?