Stories with Tag Multithreading

• Five Kinds of Nondeterminism

  permalink

  Posted: 2025-02-19 20:36:32

  Verbose tl;dr

  Hillel Wayne's post dissects the concept of "nondeterminism" in computer science, arguing that it's often used ambiguously and encompasses five distinct meanings. These are: 1) Implementation-defined behavior, where the language standard allows for varied outcomes. 2) Unspecified behavior, similar to implementation-defined but offering even less predictability. 3) Error/undefined behavior, where anything could happen, often leading to crashes. 4) Heisenbugs, which are bugs whose behavior changes under observation (e.g., debugging). 5) True nondeterminism, exemplified by hardware randomness or concurrency races. The post emphasizes that these are fundamentally different concepts with distinct implications for programmers, and understanding these nuances is crucial for writing robust and predictable software.

  Hillel Wayne's blog post, "Five Kinds of Nondeterminism," delves into the nuanced meanings of "nondeterminism" across different computational contexts, meticulously dissecting the term beyond its common association with randomness. Wayne argues that using the term vaguely can lead to confusion and miscommunication, especially in discussions about security and formal methods. He proposes a typology of five distinct categories of nondeterminism, providing clarity and precision to the concept.

  The first type is implementation-defined nondeterminism. This arises from specifications leaving certain aspects of a system's behavior deliberately unspecified, allowing for variation across different implementations. While the behavior isn't random for a specific implementation, it is unpredictable a priori without knowing the implementation details. Examples include the order of elements returned from a hash table or the specific optimizations a compiler chooses.

  Next, don't care nondeterminism emerges when a specification explicitly allows multiple valid outcomes for a given input, without preference for any specific outcome. The system can choose any of the allowed outcomes, and this choice does not affect the correctness of the system. This is often used in hardware design where certain signal transitions are irrelevant.

  Third, demonic nondeterminism pertains to situations where an adversary or malicious actor can influence the behavior of the system within the constraints of its specification. Formal methods, such as model checking, often utilize this type of nondeterminism to analyze worst-case scenarios and guarantee robustness against adversarial manipulation. A critical example involves assessing the security of a system against various attack vectors.

  The fourth category, probabilistic nondeterminism, is the type most commonly associated with the term "nondeterminism" in everyday usage. Here, system behavior is governed by probabilities, with different outcomes having specific likelihoods. Random number generators and stochastic processes are prime examples of this type. While individual outcomes are unpredictable, the overall distribution of outcomes is often known or can be statistically characterized.

  Finally, scheduler nondeterminism relates specifically to the order of execution in concurrent systems. Multiple processes or threads compete for resources, and the scheduler determines which process gets to execute at a given time. The precise interleaving of execution steps can influence the overall outcome, leading to nondeterministic behavior. This type of nondeterminism poses significant challenges for designing and debugging concurrent systems, necessitating careful synchronization mechanisms to avoid race conditions and other concurrency bugs.

  In conclusion, Wayne emphasizes that understanding these different facets of nondeterminism is essential for clear communication and accurate reasoning about complex systems. He provides concrete examples for each type, illustrating their distinct properties and implications. By disambiguating the term "nondeterminism," Wayne equips readers with a more sophisticated and nuanced understanding of the concept and its various manifestations in different computational domains.

  • nondeterminism
  • programming
  • Computer Science
  • concurrency
  • Parallelism
  • software engineering
  • determinism
  • Multithreading
  • distributed systems
  • randomness
  • Uncertainty
  • Semantics
  • formal methods

  Summary of Comments ( 17 )
  https://news.ycombinator.com/item?id=43107317

  Verbose tl;dr

  Hacker News users discussed various aspects of nondeterminism in the context of Hillel Wayne's article. Several commenters highlighted the distinction between predictable and unpredictable nondeterminism, with some arguing the author's categorization conflated the two. The importance of distinguishing between sources of nondeterminism, such as hardware, OS scheduling, and program logic, was emphasized. One commenter pointed out the difficulty in achieving true determinism even with seemingly simple programs due to factors like garbage collection and just-in-time compilation. The practical challenges of debugging nondeterministic systems were also mentioned, along with the value of tools that can help reproduce and analyze nondeterministic behavior. A few comments delved into specific types of nondeterminism, like data races and the nuances of concurrency, while others questioned the usefulness of the proposed categorization in practice.

  The Hacker News post titled "Five Kinds of Nondeterminism" linking to an article on buttondown.com has generated several comments discussing various aspects of nondeterminism in computer systems.

  Several commenters discuss the nuances and overlaps between the different categories of non-determinism outlined in the article. One commenter points out the difficulty in cleanly separating these categories in practice, arguing that many real-world systems exhibit characteristics of multiple types simultaneously. They use the example of a distributed database, which can have both implementation-defined (order of messages) and essential (concurrent user actions) non-determinism.

  Another commenter focuses on the performance implications of non-determinism, specifically in the context of compiler optimizations. They suggest that eliminating certain kinds of non-determinism can allow for more aggressive optimizations and improved performance predictability.

  The concept of "Heisenbugs" is brought up, with one commenter explaining how these elusive bugs are often a direct consequence of unintended non-determinism. They further link this to the increasing complexity of modern systems and the difficulty in controlling all sources of non-deterministic behavior.

  One commenter delves into the philosophical implications of non-determinism, touching upon the free will vs. determinism debate. They propose that the classification of non-determinism in the article could be applied to this philosophical discussion, offering a new perspective on the nature of choice.

  There's also a discussion about the role of testing and debugging in the presence of non-determinism. One commenter advocates for designing systems that minimize essential non-determinism, arguing that it simplifies testing and makes debugging easier. Another suggests techniques for reproducing and isolating non-deterministic bugs, emphasizing the importance of logging and careful analysis of system behavior.

  A few commenters offer specific examples of non-determinism in different programming languages and systems, illustrating the practical relevance of the article's categorization. They mention issues related to thread scheduling, memory allocation, and network communication, providing concrete examples of how non-determinism manifests in real-world scenarios.

  Finally, some commenters express appreciation for the article's clear explanation of a complex topic, finding the categorization helpful for understanding and addressing non-determinism in their own work. They also suggest potential extensions to the article, such as exploring the relationship between non-determinism and formal verification methods.

• 0+0 > 0: C++ thread-local storage performance

  permalink

  Posted: 2025-02-17 11:18:29

  Verbose tl;dr

  Thread-local storage (TLS) in C++ can introduce significant performance overhead, even when unused. The author benchmarks various TLS access methods, demonstrating that even seemingly simple zero-initialized thread-local variables incur a cost, especially on Windows. This overhead stems from the runtime needing to manage per-thread data structures, including lazy initialization and destruction. While the performance impact might be negligible in many applications, it can become noticeable in highly concurrent, performance-sensitive scenarios, particularly with a large number of threads. The author explores techniques to mitigate this overhead, such as using compile-time initialization or avoiding TLS altogether if practical. By understanding the costs associated with TLS, developers can make informed decisions about its usage and optimize their multithreaded C++ applications for better performance.

  The blog post "0+0 > 0: C++ thread-local storage performance" by Yosef Kreinin explores the performance implications of using thread-local storage (TLS) in C++. Kreinin begins by establishing the context that accessing thread-local variables can introduce performance overhead, potentially negating the benefits of multithreading. He sets out to investigate the extent of this overhead and identify the contributing factors.

  The investigation starts with a simple benchmark that measures the time taken to perform a trivial arithmetic operation (0+0) within a loop, both with and without declaring a thread-local variable. Surprisingly, the benchmark reveals that the version with the thread-local variable is significantly slower, even though the variable is never accessed. This indicates that the mere presence of a thread-local variable introduces overhead.

  Kreinin then delves into the potential reasons for this performance degradation. He explains that TLS is typically implemented using a hidden global data structure accessed indirectly through thread-local storage pointers. Each thread maintains its own pointer to its respective slot in this structure. The access to a thread-local variable involves retrieving the thread-local storage pointer, which can be a relatively expensive operation depending on the platform and implementation. Furthermore, the added complexity can disrupt compiler optimizations, hindering performance.

  The post examines several scenarios and their corresponding assembly code to demonstrate how thread-local variables impact performance. These scenarios include cases where the variable is initialized with a constant, initialized with a non-constant expression, and cases where the variable is accessed or not accessed within the loop. The analysis of the generated assembly code illuminates the underlying mechanisms responsible for the observed performance differences. It highlights the additional instructions required for thread-local variable access, compared to regular global or local variables.

  Kreinin further investigates how different compilers and operating systems handle TLS. He observes variations in performance across different platforms, suggesting that the overhead associated with thread-local variables is not uniform. This emphasizes the importance of understanding the specific implementation details when working with TLS.

  The post then explores strategies for mitigating the performance impact of thread-local variables. One such strategy involves reducing the number of thread-local variables by grouping related variables into a structure. This technique minimizes the number of indirect accesses required, potentially improving performance. Another approach involves caching the value of a thread-local variable in a local variable within a tight loop, thereby avoiding repeated access to the TLS mechanism.

  The blog post concludes by summarizing the findings and emphasizing the importance of considering the performance implications of thread-local storage when designing multithreaded C++ applications. It advises developers to be mindful of the potential overhead and to employ appropriate optimization techniques when necessary. The key takeaway is that while thread-local storage provides a valuable mechanism for managing thread-specific data, its usage should be carefully considered in performance-critical sections of code.

  • C++
  • performance
  • Thread-Local Storage
  • TLS
  • Multithreading
  • concurrency
  • optimization
  • benchmarking

  Summary of Comments ( 10 )
  https://news.ycombinator.com/item?id=43077675

  Verbose tl;dr

  The Hacker News comments discuss the surprising performance cost of thread-local storage (TLS) in C++, particularly its impact on seemingly unrelated code. Several commenters highlight the overhead introduced by the TLS lookups, even when the TLS variables aren't directly used in a particular code path. The most compelling comments delve into the underlying reasons for this, citing issues like increased register pressure due to the extra variables needing to be tracked, and the difficulty compilers have in optimizing around TLS access. Some point out that the benchmark's reliance on rdtsc for timing might be flawed, while others offer alternative benchmarking strategies. The performance impact is acknowledged to be architecture-dependent, with some suggesting mitigations like using compile-time initialization or alternative threading models if TLS performance is critical. A few commenters also mention similar performance issues they've encountered with TLS in other languages, suggesting it's not a C++-specific problem.

  The Hacker News post titled "0+0 > 0: C++ thread-local storage performance," linking to an article about C++ thread-local storage performance, has a moderate number of comments discussing various aspects of the topic.

  Several commenters discuss the complexities and nuances of thread-local storage (TLS) implementation across different compilers and platforms. One commenter points out the variability in performance characteristics of TLS, noting how different compilers (like GCC and Clang) and operating systems might handle TLS access differently, impacting performance. This commenter also highlights how the use of dynamic libraries can further complicate the situation, leading to potential performance hits if TLS isn't implemented optimally within the dynamic loading process.

  Another commenter delves into the specifics of how TLS is handled on Windows, mentioning the use of "Thread Local Storage (TLS) callbacks," which are functions executed upon thread creation or destruction that manage the TLS data. This introduces overhead, especially in scenarios with frequent thread creation and destruction. The commenter contrasts this with the __thread keyword (supported by GCC and Clang), which is often faster but less portable.

  One commenter mentions the difficulties in measuring the performance of TLS accurately, emphasizing the importance of factors such as CPU caching and benchmarking methodology. They also point out the impact that the surrounding code and its interaction with the TLS access can have on overall performance.

  The discussion also touches upon the performance implications of different TLS access patterns. One commenter suggests that accessing TLS frequently within tight loops can indeed be a performance bottleneck, echoing the article's findings. Another comment highlights the overhead associated with the initial access to a TLS variable in a thread's lifetime, as opposed to subsequent accesses.

  Finally, a few comments provide alternative solutions or approaches to consider when dealing with performance-sensitive multithreaded code. One commenter mentions using thread pools to minimize the overhead of thread creation and destruction, thus indirectly reducing the impact of TLS management. Another commenter suggests exploring alternative data structures or algorithms that might minimize the need for frequent TLS access altogether.

• Ruby “Thread Contention” Is Simply GVL Queuing

  permalink

  Posted: 2025-02-03 08:43:13

  Verbose tl;dr

  The post argues that the term "thread contention" is misused in the context of Ruby's Global VM Lock (GVL). True thread contention involves multiple threads attempting to modify the same shared resource simultaneously. However, in Ruby with the GVL, only one thread can execute Ruby code at any given time. What appears as "contention" is actually just queuing: threads waiting their turn to acquire the GVL. The post emphasizes that understanding this distinction is crucial for profiling and optimizing Ruby applications. Instead of focusing on eliminating "contention," developers should concentrate on reducing the time threads hold the GVL, minimizing the queueing time and improving overall performance.

  The blog post "Ruby “Thread Contention” Is Simply GVL Queuing" by Peter Cooper argues that the common phrase "thread contention" is often misused in the context of Ruby's multi-threading performance limitations, leading to confusion and misdiagnosis of performance issues. Instead of actual contention, where multiple threads are actively competing for the same shared resource simultaneously, the performance bottleneck in Ruby's multi-threaded applications typically stems from the Global Virtual Machine Lock (GVL).

  Cooper elaborates that the GVL, a core mechanism in the standard implementation of Ruby known as CRuby, serializes execution of Ruby code. While multiple operating system (OS) threads can exist within a Ruby process, only one Ruby thread can execute Ruby bytecode at any given instant due to the GVL. Other threads wishing to execute Ruby code are placed in a queue managed by the GVL. This queuing mechanism is what frequently gets misinterpreted as "thread contention."

  The author meticulously distinguishes between true contention and GVL queuing. True contention occurs when multiple threads attempt to access and modify the same shared resource, such as a shared memory location or a file, simultaneously. This leads to race conditions and requires synchronization primitives like mutexes or semaphores to ensure data integrity and prevent unexpected behavior. However, in Ruby, the GVL inherently prevents true contention within Ruby code itself because it restricts execution to a single thread at a time.

  Therefore, what appears as "contention" in Ruby profiling tools is actually the overhead of the GVL's queuing mechanism. Threads wait their turn to acquire the GVL, creating a queue of waiting threads. This queuing and dequeuing process, along with the context switching between threads managed by the operating system, contributes to the perceived performance bottleneck. Cooper emphasizes that this is not true contention for resources, but rather a queuing delay imposed by the GVL's serialization of Ruby code execution.

  The post further clarifies that true contention can still occur in Ruby in scenarios involving non-Ruby code, particularly when interacting with external libraries or system calls. For example, if multiple Ruby threads simultaneously attempt to write to the same file descriptor, true contention can occur at the operating system level, outside the scope of the GVL.

  In summary, Cooper advocates for more precise language when discussing Ruby's multi-threading performance. He argues that using the term "GVL queuing" instead of "thread contention" provides a more accurate description of the performance bottleneck in CRuby, highlighting the role of the GVL and its queuing mechanism as the primary source of performance limitations in multi-threaded Ruby applications and facilitating more effective diagnosis and optimization of such applications.

  • ruby
  • threads
  • GVL
  • Global Interpreter Lock
  • concurrency
  • Parallelism
  • performance
  • Queuing
  • programming
  • Software Development
  • CRuby
  • MRI
  • Multithreading

  Summary of Comments ( 38 )
  https://news.ycombinator.com/item?id=42916203

  Verbose tl;dr

  HN commenters generally agree with the author's premise that Ruby's "thread contention" is largely a misunderstanding of the GVL (Global VM Lock). Several pointed out that true contention can occur in Ruby, specifically around I/O operations and interactions with native extensions/C code that release the GVL. One commenter shared a detailed example of contention in a Rails app due to database connection pooling. Others highlighted that the article might undersell the performance impact of the GVL, particularly for CPU-bound tasks, where true parallelism is impossible. The real takeaway, according to the comments, is to understand the GVL's limitations and choose the right concurrency model (e.g., processes, async I/O) for the specific task, rather than blindly reaching for threads. Finally, a few commenters discussed the complexities of truly removing the GVL from Ruby, citing the challenges and potential breakage of existing code.

  The Hacker News post titled "Ruby “Thread Contention” Is Simply GVL Queuing" has generated several comments discussing the nuances of Ruby's Global VM Lock (GVL) and its impact on concurrency.

  One commenter points out the distinction between "true contention" and mere queuing for the GVL. They argue that while multiple threads might appear to be contending for resources, the actual bottleneck is often the serialized execution enforced by the GVL. This commenter further emphasizes that profiling tools might misrepresent this queuing as contention, leading developers to misdiagnose performance issues. They suggest that a more accurate term would be "GVL contention" or "GVL queuing" to reflect the underlying mechanism.

  Another commenter concurs, adding that while the GVL doesn't eliminate all forms of contention (e.g., contention for shared memory), it does significantly influence how threads interact with resources. They highlight the importance of understanding this distinction when optimizing Ruby code for multi-threaded environments.

  A further comment delves into the complexities of the GVL's implementation, noting that its behavior can vary across different Ruby interpreters (e.g., MRI, JRuby, TruffleRuby). This commenter emphasizes the need to consider the specific interpreter when analyzing GVL-related performance characteristics. They also mention the potential benefits and drawbacks of using alternative concurrency models, such as fibers and actors, in Ruby.

  Another discussion thread focuses on the practical implications of the GVL for Ruby developers. Commenters share their experiences with debugging and optimizing multi-threaded Ruby applications, offering advice on how to mitigate the performance limitations imposed by the GVL. Specific techniques, such as using asynchronous I/O operations and carefully managing shared resources, are discussed.

  One commenter offers a contrasting perspective, arguing that the term "thread contention" is still relevant in the context of the GVL. They explain that even though the GVL serializes execution, threads are still competing for the opportunity to acquire the lock. This competition, they contend, can still be considered a form of contention, albeit one mediated by the GVL.

  Overall, the comments on the Hacker News post provide a rich discussion on the intricacies of the GVL in Ruby. They highlight the importance of understanding the GVL's impact on concurrency, the potential for misinterpreting profiling data, and the strategies developers can employ to optimize their multi-threaded Ruby code. The comments also reveal the ongoing debate about the appropriate terminology for describing the GVL's effects on thread behavior.