Critical sections limit performance by constraining parallel execution and adding overhead. What features should a critical section have for improving performance?

  • $\begingroup$ I have no idea what you are asking about. Critical sections are for correctness not performance. $\endgroup$ – Wandering Logic May 4 '15 at 13:03
  • $\begingroup$ @WanderingLogic Did the edit help? I am guessing that lio wants to know what makes a critical section slow down a program and how such can be avoided. $\endgroup$ – Paul A. Clayton May 4 '15 at 17:04

As noted in the question, the performance impact of critical sections has two components: the limiting of parallelism and the overhead in providing the isolation guarantees.

The limiting of parallelism can be addressed by minimizing the context, frequency, and duration of the critical section. Using finer-grained locking or transactional memory allows independent operations to be executed in parallel by reducing the context in which isolation must be guaranteed.

Reducing coupling of operations can reduce the context and frequency of critical sections. The use of redundant data structures can provide localization of data such that critical sections can be avoided (reducing their frequency) or the potential contention reduced. For example, instead of updating a single accumulator a tree of accumulators could be used.

(While the fastest critical section is the one that does not exist, one must be careful that overheads in avoiding critical sections are not higher than the cost of using a critical section.)

The duration of a critical section can be reduced by keeping work out of the critical section. While this is relatively obvious, moving work before or after the critical section may require that more work be done (at least in some cases) or may interfere with other design considerations. Speculatively performing work before a critical section can shorten a critical section at the cost of detecting and handling incorrect speculation.

One subtle form of work is the handling of cache misses and state updates (primarily acquiring ownership of a cache block). Avoiding false sharing is a well-known technique, but somewhat less commonly mentioned (in part because of tradeoffs of complexity and runtime overheads with the performance benefit) are localization of true sharing and prefetching. Temporal localization of sharing exploits patterns of reading and updating to use warm data. In some cases, it may even be worthwhile to increase the duration of a critical section to reduce the amount of work within critical sections by taking advantage of a warmed-up cache.

Sharing can also be localized within the memory system. Not all communication between threads has equal cost. Physical proximity of communication and read-sharing can exploit sharing of a level of cache to keep warm data in cache (incidentally avoiding replication), to prefetch data (if cross-thread accesses can have temporal locality either naturally or by clever scheduling), or to reduce the bandwidth or latency of communication. NUMA-optimizations can also reduce bandwidth and latency by locating users, especially modifiers, of data near the home of the data. NUMA-optimizations can even apply to last level cache slices when a cache block has a single home partition within the last level cache which can be accessed with less overhead by one or more processing elements.

Using finer-grained locking can also reduce the isolation overhead by avoiding cache line ping-pong. The ultimate in fine-grained locking is lockless updating using atomic operations. Knowing what facilities the targeted hardware provides and the tradeoffs in their use can also be helpful in reducing isolation overhead. For example, if the targeted hardware transactional memory system supports low overhead retry under certain conditions, it may be less important to avoid contention leading to a transient transaction failure than to make sure those conditions are satisfied.

Approximation can also exploited in some cases to reduce overhead. Statistical information such as software performance counters can often tolerate losing some updates, allowing removal from the critical section and the use of less expensive non-atomic operations. Similarly, some information only needs to be conservatively maintained for correctness. For example, a reference counter could afford to lose a decrement if the information is only used for earliest release of a resource (another layer of resource management might handle such leaks).

The basic principle for critical sections is that they should be as small (context and duration) and as infrequent as possible.

  • $\begingroup$ This is not my area of expertise, but this answer might provide at least some of what the OP was seeking (though it is probably excessively broad and is clearly very incomplete and somewhat less than ideally organized). $\endgroup$ – Paul A. Clayton May 4 '15 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.