xii CONTENTS 7.2 Examples of lock-free data structures 184 Writing a thread-safe stack without locks 184"Stopping those pesky leaks:managing memory in lock-free data structures 188 Detecting nodes that can't be reclaimed using hazard pointers 193 Detecting nodes in use with reference counting 200"Applying the memory model to the lock-free stack 205 Writing a thread-safe queue without locks 209 7.3 Guidelines for writing lock-free data structures 221 Guideline:use std::memoryorder seq_cst for prototyping 221 Guideline:use a lock-free memory reclamation scheme 221 Guideline:watch out for the ABA problem 222 Guideline:identify busy-wait loops and help the other thread 222 7.4 Summary 223 Designing concurrent code 224 8.1 Techniques for dividing work between threads 225 Dividing data between threads before processing begins 226 Dividing data recursively 227"Dividing work by task type 231 8.2 Factors affecting the performance of concurrent code 233 How many processors?234Data contention and cache ping-pong235·False sharing237·How close is your data？238·Oversubscription and excessive task switching 239 8.3 Designing data structures for multithreaded performance 239 Dividing array elements for complex operations 240 Data access patterns in other data structures 242 8.4 Additional considerations when designing for concurrency 243 Exception safety in parallel algorithms 243 Scalability and Amdahl's law 250Hiding latency with multiple threads 252 Improving responsiveness with concurrency 253 8.5 Designing concurrent code in practice 255 A parallel implementation of std::for_each 255"A parallel implementation of std::find 257"A parallel implementation of std::partial sum 263 8.6 Summary 272xii CONTENTS 7.2 Examples of lock-free data structures 184 Writing a thread-safe stack without locks 184 ■ Stopping those pesky leaks: managing memory in lock-free data structures 188 Detecting nodes that can’t be reclaimed using hazard pointers 193 Detecting nodes in use with reference counting 200 ■ Applying the memory model to the lock-free stack 205 ■ Writing a thread-safe queue without locks 209 7.3 Guidelines for writing lock-free data structures 221 Guideline: use std::memory_order_seq_cst for prototyping 221 Guideline: use a lock-free memory reclamation scheme 221 Guideline: watch out for the ABA problem 222 Guideline: identify busy-wait loops and help the other thread 222 7.4 Summary 223 8 Designing concurrent code 224 8.1 Techniques for dividing work between threads 225 Dividing data between threads before processing begins 226 Dividing data recursively 227 ■ Dividing work by task type 231 8.2 Factors affecting the performance of concurrent code 233 How many processors? 234 ■ Data contention and cache ping-pong 235 ■ False sharing 237 ■ How close is your data? 238 ■ Oversubscription and excessive task switching 239 8.3 Designing data structures for multithreaded performance 239 Dividing array elements for complex operations 240 Data access patterns in other data structures 242 8.4 Additional considerations when designing for concurrency 243 Exception safety in parallel algorithms 243 ■ Scalability and Amdahl’s law 250 ■ Hiding latency with multiple threads 252 Improving responsiveness with concurrency 253 8.5 Designing concurrent code in practice 255 A parallel implementation of std::for_each 255 ■ A parallel implementation of std::find 257 ■ A parallel implementation of std::partial_sum 263 8.6 Summary 272