diff options
Diffstat (limited to '2023/08/15/poll-error-attribute-in-OCaml/index.html')
| -rw-r--r-- | 2023/08/15/poll-error-attribute-in-OCaml/index.html | 232 |
1 files changed, 232 insertions, 0 deletions
diff --git a/2023/08/15/poll-error-attribute-in-OCaml/index.html b/2023/08/15/poll-error-attribute-in-OCaml/index.html new file mode 100644 index 00000000..0cc7776a --- /dev/null +++ b/2023/08/15/poll-error-attribute-in-OCaml/index.html @@ -0,0 +1,232 @@ +<!DOCTYPE html> +<html lang="en"> + <head> + <meta charset="UTF-8"> +<meta name="viewport" + content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0"> +<meta http-equiv="X-UA-Compatible" content="ie=edge"> + + <meta name="author" content="韩暮秋"> + + + <meta name="subtitle" content="暮秋小屋"> + + + <meta name="description" content="不卑不亢的码农， 朴素的民谣诗人"> + + + <meta name="keywords" content="韩暮秋,MuqiuHan"> + + + + +<title>使用 [@poll error] 实现线程安全的数据结构 | 暮秋小屋</title> + + + + + +<style> + @import url('https://fonts.googleapis.com/css2?family=Inter:wght@300;400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&family=Roboto+Mono&display=swap'); +</style> + + + + <!-- stylesheets list from _config.yml --> + + <link rel="stylesheet" href="/css/style.css"> + + + + + + <!-- scripts list from _config.yml --> + + <script src="/js/frame.js"></script> + + + + + + <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script> + <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script> + + + + + + + + <!-- hexo injector head_end start --> +<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css"> + +<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/style.css"> +<!-- hexo injector head_end end --><meta name="generator" content="Hexo 6.3.0"></head> + <body> + <div class="mask-border"> + </div> + + <div class="wrapper"> + + <div class="header"> + <div class="flex-container"> + <div class="header-inner"> + <div class="site-brand-container"> + <a href="/"> + + 暮秋小屋 + + </a> + </div> + <div id="menu-btn" class="menu-btn" onclick="toggleMenu()"> + Menu + </div> + <nav class="site-nav"> + <ul class="menu-list"> + + + <li class="menu-item"> + <a href="/">主页</a> + </li> + + + + <li class="menu-item"> + <a href="/tags/Technique/">技术</a> + </li> + + + + <li class="menu-item"> + <a href="/categories/gallery/">日记本</a> + </li> + + + + <li class="menu-item"> + <a href="/about">关于</a> + </li> + + + + </ul> + </nav> + </div> + </div> +</div> + + + <div class="main"> + <div class="flex-container"> + <article id="post"> + + + <div class="post-head"> + <div class="post-info"> + <div class="tag-list"> + + + <span class="post-tag"> + <a href="/tags/Technique/"> + Technique + </a> + </span> + + <span class="post-tag"> + <a href="/tags/OCaml/"> + OCaml + </a> + </span> + + + </div> + <div class="post-title"> + + + 使用 [@poll error] 实现线程安全的数据结构 + + + </div> + <span class="post-date"> + Aug 15, 2023 + </span> + </div> + <div class="post-img"> + + <div class="h-line-primary"></div> + + </div> +</div> + <div class="post-content"> + <p>OCaml的标准库提供了许多mutable的数据结构，比如Hashtbl, Queue, Stack之类的，但是这些数据结构都不是线程安全的。在 OCaml 4 和 OCaml 5 中，单个Domain中一次只能运行一个线程。换句话说，单个Domain中的线程仍然不会并行运行，除非在不同所的Domain中。</p> +<p>而在单个Domain中 OCaml 的 runtime 是通过在safe point期间半抢占式的切换线程。也就是说，线程切换只会发生在safe point期间。例如内存分配就是是safe point。这意味着在没有safe point的代码块内，可以在Domain内原子性地进行多次读写或访问操作，因为线程没被切换。</p> +<p>OCaml 编译器提供了一个名为 <a target="_blank" rel="noopener" href="https://github.com/ocaml/ocaml/pull/10462"><code>[@poll error]</code></a> 的annotation，可以在函数中使用它来确保该函数不包含safe point。</p> +<p>所以通过使用 <code>[@poll error]</code> 就可以创建在Domain内原子性执行的函数，也就是说，基于此特性可以实现单个Domain内线程安全的数据结构，例如 thread-table 便是使用这个特性实现的 Hash Table。可以看看它的 add 函数的实现:</p> +<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span>[@poll error] add_atomically t buckets n i before after =</span><br><span class="line"> t.rehash = <span class="number">0</span> && buckets == t.buckets</span><br><span class="line"> && before == <span class="type">Array</span>.unsafe_get buckets i</span><br><span class="line"> && <span class="keyword">begin</span></span><br><span class="line"> <span class="type">Array</span>.unsafe_set buckets i after;</span><br><span class="line"> <span class="keyword">let</span> length = t.length + <span class="number">1</span> <span class="keyword">in</span></span><br><span class="line"> t.length <- length;</span><br><span class="line"> <span class="keyword">if</span> n < length && n < max_buckets_div_2 <span class="keyword">then</span> t.rehash <- n * <span class="number">2</span>;</span><br><span class="line"> <span class="literal">true</span></span><br><span class="line"> <span class="keyword">end</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">let</span> <span class="keyword">rec</span> add t k' v' =</span><br><span class="line"> <span class="keyword">let</span> h = <span class="type">Mix</span>.<span class="built_in">int</span> k' <span class="keyword">in</span></span><br><span class="line"> maybe_rehash t;</span><br><span class="line"> <span class="keyword">let</span> buckets = t.buckets <span class="keyword">in</span></span><br><span class="line"> <span class="keyword">let</span> n = <span class="type">Array</span>.length buckets <span class="keyword">in</span></span><br><span class="line"> <span class="keyword">let</span> i = h <span class="keyword">land</span> (n - <span class="number">1</span>) <span class="keyword">in</span></span><br><span class="line"> <span class="keyword">let</span> before = <span class="type">Array</span>.unsafe_get buckets i <span class="keyword">in</span></span><br><span class="line"> <span class="keyword">let</span> after = <span class="type">Cons</span> (k', v', before) <span class="keyword">in</span></span><br><span class="line"> <span class="keyword">if</span> not (add_atomically t buckets n i before after) <span class="keyword">then</span> add t k' v'</span><br></pre></td></tr></table></figure> + +<p>相比使用 Stdlib.Mutex，这种无锁实现会有更好的性能（特别是对于只读操作），并且还允许例如信号处理之类的上下文操作。</p> + +</div> + +<script> + window.onload = detectors(); +</script> + <div class="post-footer"> + <div class="h-line-primary"></div> + <nav class="post-nav"> + <div class="prev-item"> + + <div class="icon arrow-left"></div> + <div class="post-link"> + <a href="/2023/08/15/tick-thread%E5%9C%A8Multicore-OCaml%E4%B8%AD%E7%9A%84%E4%BD%9C%E7%94%A8/">Prev</a> + </div> + + </div> + <div class="next-item"> + + <div class="icon arrow-right"></div> + <div class="post-link"> + <a href="/2023/08/15/Typed-Design-Patterns-for-the-Functional-Era/">Next</a> + </div> + + </div> + </nav> +</div> + + + <div class="post-comment"> + + + + + + + +</div> + + +</article> + </div> + </div> + + <div class="footer"> + <div class="flex-container"> + <div class="footer-text"> + + + | + + + 希望路过的人可以添点柴火让这里暖和点 + + </div> + </div> +</div> + + </div> + + + + + </body> +</html> |