Summary
The most important lesson of this chapter is that designing data structures for concurrency is hard, and you should take every opportunity to simplify it. Application-specific restrictions on the use of the data structures can be used to make them both simpler and faster.
The first decision you must make is which parts of your code need thread safety and which do not. Often, the best solution is to give each thread its own data to work on: any data used by a single thread needs no thread-safety concerns at all. When that is not an option, look for other application-specific restrictions: do you have multiple threads modifying a particular data structure? The implementation is often simpler if there is only one writer thread. Are there any application-specific guarantees you can exploit? Do you know the maximum size of the data structure upfront? Do you need to delete data from the data structure as well as add it at the same time, or can you separate these operations in...
