Typed Design Patterns for the Functional Era

From 108719207c81b85360ca63eebbf64ab7cdee60e2 Mon Sep 17 00:00:00 2001 From: muqiuhan Date: Tue, 15 Aug 2023 05:30:55 +0000 Subject: deploy: c5a7c0e217a91c05e60b492bc0e944ce73531c17 --- .../index.html" | 5 + .../index.html | 225 ++++++++++++++++++++ .../08/15/poll-error-attribute-in-OCaml/index.html | 232 +++++++++++++++++++++ .../index.html" | 224 ++++++++++++++++++++ archives/2023/08/index.html | 54 +++++ archives/2023/index.html | 60 +++--- archives/2023/page/2/index.html | 60 +++--- archives/2023/page/3/index.html | 54 +++++ archives/index.html | 62 +++--- archives/page/2/index.html | 62 +++--- archives/page/3/index.html | 66 +++--- archives/page/4/index.html | 68 +++--- archives/page/5/index.html | 215 +++++++++++++++++++ page/5/index.html | 185 ++++++++++++++++ tags/OCaml/index.html | 54 +++++ tags/Technique/index.html | 54 +++++ 16 files changed, 1490 insertions(+), 190 deletions(-) create mode 100644 2023/08/15/Typed-Design-Patterns-for-the-Functional-Era/index.html create mode 100644 2023/08/15/poll-error-attribute-in-OCaml/index.html create mode 100644 "2023/08/15/tick-thread\345\234\250Multicore-OCaml\344\270\255\347\232\204\344\275\234\347\224\250/index.html" create mode 100644 archives/page/5/index.html create mode 100644 page/5/index.html diff --git "a/2023/08/01/\344\272\214\343\200\207\344\272\214\344\270\211\345\271\264\345\205\253\346\234\210\344\270\200\346\227\245/index.html" "b/2023/08/01/\344\272\214\343\200\207\344\272\214\344\270\211\345\271\264\345\205\253\346\234\210\344\270\200\346\227\245/index.html" index bdfb5486..a942ea86 100644 --- "a/2023/08/01/\344\272\214\343\200\207\344\272\214\344\270\211\345\271\264\345\205\253\346\234\210\344\270\200\346\227\245/index.html" +++ "b/2023/08/01/\344\272\214\343\200\207\344\272\214\344\270\211\345\271\264\345\205\253\346\234\210\344\270\200\346\227\245/index.html" @@ -161,6 +161,11 @@

+ Prev +

diff --git a/2023/08/15/Typed-Design-Patterns-for-the-Functional-Era/index.html b/2023/08/15/Typed-Design-Patterns-for-the-Functional-Era/index.html new file mode 100644 index 00000000..f8939841 --- /dev/null +++ b/2023/08/15/Typed-Design-Patterns-for-the-Functional-Era/index.html @@ -0,0 +1,225 @@ + + + + + + + + + + + + + + + + + + + + + +Typed Design Patterns for the Functional Era | 暮秋小屋 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ +

+ + + 暮秋小屋 + + +

+ + +

+ +

+ + + Typed Design Patterns for the Functional Era + + +

+ + Aug 15, 2023 + +

+ +

+ + + + + +

+ + + + + + + +

+ + +

+ + + +

+ + + + + + 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 @@ + + + + + + + + + + + + + + + + + + + + + +使用 [@poll error] 实现线程安全的数据结构 | 暮秋小屋 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ +

+ + + 暮秋小屋 + + +

+ + +

+ +

+ + + 使用 [@poll error] 实现线程安全的数据结构 + + +

+ + Aug 15, 2023 + +

+ +

OCaml的标准库提供了许多mutable的数据结构，比如Hashtbl, Queue, Stack之类的，但是这些数据结构都不是线程安全的。在 OCaml 4 和 OCaml 5 中，单个Domain中一次只能运行一个线程。换句话说，单个Domain中的线程仍然不会并行运行，除非在不同所的Domain中。

而在单个Domain中 OCaml 的 runtime 是通过在safe point期间半抢占式的切换线程。也就是说，线程切换只会发生在safe point期间。例如内存分配就是是safe point。这意味着在没有safe point的代码块内，可以在Domain内原子性地进行多次读写或访问操作，因为线程没被切换。

OCaml 编译器提供了一个名为 [@poll error] 的annotation，可以在函数中使用它来确保该函数不包含safe point。

所以通过使用 [@poll error] 就可以创建在Domain内原子性执行的函数，也就是说，基于此特性可以实现单个Domain内线程安全的数据结构，例如 thread-table 便是使用这个特性实现的 Hash Table。可以看看它的 add 函数的实现:

let[@poll error] add_atomically t buckets n i before after =
  t.rehash = 0 && buckets == t.buckets
  && before == Array.unsafe_get buckets i
  && begin
       Array.unsafe_set buckets i after;
       let length = t.length + 1 in
       t.length <- length;
       if n < length && n < max_buckets_div_2 then t.rehash <- n * 2;
       true
     end

let rec add t k' v' =
  let h = Mix.int k' in
  maybe_rehash t;
  let buckets = t.buckets in
  let n = Array.length buckets in
  let i = h land (n - 1) in
  let before = Array.unsafe_get buckets i in
  let after = Cons (k', v', before) in
  if not (add_atomically t buckets n i before after) then add t k' v'

+ +

相比使用 Stdlib.Mutex，这种无锁实现会有更好的性能（特别是对于只读操作），并且还允许例如信号处理之类的上下文操作。

+ +

+ + + + + +

+ + + + + + + +

+ + +

+ + + +

+ + + + + + diff --git "a/2023/08/15/tick-thread\345\234\250Multicore-OCaml\344\270\255\347\232\204\344\275\234\347\224\250/index.html" "b/2023/08/15/tick-thread\345\234\250Multicore-OCaml\344\270\255\347\232\204\344\275\234\347\224\250/index.html" new file mode 100644 index 00000000..de11afdd --- /dev/null +++ "b/2023/08/15/tick-thread\345\234\250Multicore-OCaml\344\270\255\347\232\204\344\275\234\347\224\250/index.html" @@ -0,0 +1,224 @@ + + + + + + + + + + + + + + + + + + + + + +tick thread在Multicore OCaml中的作用 | 暮秋小屋 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ +

+ + + 暮秋小屋 + + +

+ + +

+ +

+ + + tick thread在Multicore OCaml中的作用 + + +

+ + Aug 15, 2023 + +

+ +

Multicore OCaml的程序在启动时会运行一个 tick thread，其实现如下:

/* The tick thread: posts a SIGPREEMPTION signal periodically */

static void * caml_thread_tick(void * arg)
{
  struct timeval timeout;
  sigset_t mask;

  /* Block all signals so that we don't try to execute an OCaml signal handler*/
  sigfillset(&mask);
  pthread_sigmask(SIG_BLOCK, &mask, NULL);
  while(! caml_tick_thread_stop) {
    /* select() seems to be the most efficient way to suspend the
       thread for sub-second intervals */
    timeout.tv_sec = 0;
    timeout.tv_usec = Thread_timeout * 1000;
    select(0, NULL, NULL, NULL, &timeout);
    /* The preemption signal should never cause a callback, so don't
     go through caml_handle_signal(), just record signal delivery via
     caml_record_signal(). */
    caml_record_signal(SIGPREEMPTION);
  }
  return NULL;
}

+ +

这是因为Multicore OCaml的GC目前需要一个进程（或一个Domain）中的所有线程一起参与以避免并发访问。如果一个线程在system call上被阻塞，那么整个Domain就会被卡住，直到该线程可以参与当前的垃圾收集。为了避免这个问题，tick 线程可以代替被阻塞的线程执行垃圾收集操作。

+ +

+ + + + + +

+ + + + + + + +

+ + +

+ + + +

+ + + + + + diff --git a/archives/2023/08/index.html b/archives/2023/08/index.html index 385fd541..27ca5aa7 100644 --- a/archives/2023/08/index.html +++ b/archives/2023/08/index.html @@ -128,6 +128,60 @@

2023

+ + + tick thread在Multicore OCaml中的作用 + + +

+ + Aug 15, 2023 +

+ + + + + + + +

+ + + 使用 [@poll error] 实现线程安全的数据结构 + + +

+ + Aug 15, 2023 +

+ + + + + + + +

+ + + Typed Design Patterns for the Functional Era + + +

+ + Aug 15, 2023 +

+ + + + + + +

diff --git a/archives/2023/index.html b/archives/2023/index.html index 4477e224..9ad3eff8 100644 --- a/archives/2023/index.html +++ b/archives/2023/index.html @@ -130,14 +130,14 @@

- + - 二〇二三年八月一日 + tick thread在Multicore OCaml中的作用

- Aug 1, 2023 + Aug 15, 2023

@@ -148,14 +148,14 @@

- + - 二零二三年七月三十日 + 使用 [@poll error] 实现线程安全的数据结构

- Jul 30, 2023 + Aug 15, 2023

@@ -166,14 +166,14 @@

- + - 二〇二三年七月二十六日 + Typed Design Patterns for the Functional Era

- Jul 26, 2023 + Aug 15, 2023

@@ -184,14 +184,14 @@

- + - 二〇二三年六月二十九日 + 二〇二三年八月一日

- Jun 29, 2023 + Aug 1, 2023

@@ -202,14 +202,14 @@

- + - OOP Visitors在Polymorphic情况下的类型错误 + 二零二三年七月三十日

- Jun 28, 2023 + Jul 30, 2023

@@ -220,14 +220,14 @@

- + - 隐藏一些OCaml Effect的机制，让其语法在精神上更接近delimcc + 二〇二三年七月二十六日

- Jun 28, 2023 + Jul 26, 2023

@@ -238,14 +238,14 @@

- + - caml_release_runtime_system导致的死锁问题 + 二〇二三年六月二十九日

- Jun 28, 2023 + Jun 29, 2023

@@ -256,14 +256,14 @@

- + - 灯笼草 + OOP Visitors在Polymorphic情况下的类型错误

- Jun 22, 2023 + Jun 28, 2023

@@ -274,14 +274,14 @@

- + - 发热及超高热危象 + 隐藏一些OCaml Effect的机制，让其语法在精神上更接近delimcc

- Jun 17, 2023 + Jun 28, 2023

@@ -292,14 +292,14 @@

- + - 二零二三年六月十日 + caml_release_runtime_system导致的死锁问题

- Jun 10, 2023 + Jun 28, 2023

diff --git a/archives/2023/page/2/index.html b/archives/2023/page/2/index.html index 509a509a..2ca3e586 100644 --- a/archives/2023/page/2/index.html +++ b/archives/2023/page/2/index.html @@ -130,14 +130,14 @@

- + - 二零二三年四月二十五日 + 灯笼草

- Apr 25, 2023 + Jun 22, 2023

@@ -148,14 +148,14 @@

- + - 二零二三年四月二十二日 + 发热及超高热危象

- Apr 22, 2023 + Jun 17, 2023

@@ -166,14 +166,14 @@

- + - 螺内酯片 + 二零二三年六月十日

- Mar 14, 2023 + Jun 10, 2023

@@ -184,14 +184,14 @@

- + - 呋塞米 + 二零二三年四月二十五日

- Mar 14, 2023 + Apr 25, 2023

@@ -202,14 +202,14 @@

- + - 替米沙坦 + 二零二三年四月二十二日

- Mar 13, 2023 + Apr 22, 2023

@@ -220,14 +220,14 @@

- + - 奥司他韦 + 螺内酯片

- Mar 5, 2023 + Mar 14, 2023

@@ -238,14 +238,14 @@

- + - 金匮要略 + 呋塞米

- Mar 4, 2023 + Mar 14, 2023

@@ -256,14 +256,14 @@

- + - 气胸 + 替米沙坦

- Mar 1, 2023 + Mar 13, 2023

@@ -274,14 +274,14 @@

- + - 纯牛奶可以加点啥 + 奥司他韦

- Mar 1, 2023 + Mar 5, 2023

@@ -292,14 +292,14 @@

- + - 二零二三年二月二十六日 + 金匮要略

- Feb 26, 2023 + Mar 4, 2023

diff --git a/archives/2023/page/3/index.html b/archives/2023/page/3/index.html index 73807c59..4fdca286 100644 --- a/archives/2023/page/3/index.html +++ b/archives/2023/page/3/index.html @@ -128,6 +128,60 @@

2023

+ + + 气胸 + + +

+ + Mar 1, 2023 +

+ + + + + + + +

+ + + 纯牛奶可以加点啥 + + +

+ + Mar 1, 2023 +

+ + + + + + + +

+ + + 二零二三年二月二十六日 + + +

+ + Feb 26, 2023 +

+ + + + + + +

diff --git a/archives/index.html b/archives/index.html index b0f51cd6..51c29fc9 100644 --- a/archives/index.html +++ b/archives/index.html @@ -130,14 +130,14 @@

- + - 二〇二三年八月一日 + tick thread在Multicore OCaml中的作用

- Aug 1, 2023 + Aug 15, 2023

@@ -148,14 +148,14 @@

- + - 二零二三年七月三十日 + 使用 [@poll error] 实现线程安全的数据结构

- Jul 30, 2023 + Aug 15, 2023

@@ -166,14 +166,14 @@

- + - 二〇二三年七月二十六日 + Typed Design Patterns for the Functional Era

- Jul 26, 2023 + Aug 15, 2023

@@ -184,14 +184,14 @@

- + - 二〇二三年六月二十九日 + 二〇二三年八月一日

- Jun 29, 2023 + Aug 1, 2023

@@ -202,14 +202,14 @@

- + - OOP Visitors在Polymorphic情况下的类型错误 + 二零二三年七月三十日

- Jun 28, 2023 + Jul 30, 2023

@@ -220,14 +220,14 @@

- + - 隐藏一些OCaml Effect的机制，让其语法在精神上更接近delimcc + 二〇二三年七月二十六日

- Jun 28, 2023 + Jul 26, 2023

@@ -238,14 +238,14 @@

- + - caml_release_runtime_system导致的死锁问题 + 二〇二三年六月二十九日

- Jun 28, 2023 + Jun 29, 2023

@@ -256,14 +256,14 @@

- + - 灯笼草 + OOP Visitors在Polymorphic情况下的类型错误

- Jun 22, 2023 + Jun 28, 2023

@@ -274,14 +274,14 @@

- + - 发热及超高热危象 + 隐藏一些OCaml Effect的机制，让其语法在精神上更接近delimcc

- Jun 17, 2023 + Jun 28, 2023

@@ -292,14 +292,14 @@

- + - 二零二三年六月十日 + caml_release_runtime_system导致的死锁问题

- Jun 10, 2023 + Jun 28, 2023

@@ -308,7 +308,7 @@

diff --git a/archives/page/2/index.html b/archives/page/2/index.html index b8140026..870d19b2 100644 --- a/archives/page/2/index.html +++ b/archives/page/2/index.html @@ -130,14 +130,14 @@

- + - 二零二三年四月二十五日 + 灯笼草

- Apr 25, 2023 + Jun 22, 2023

@@ -148,14 +148,14 @@

- + - 二零二三年四月二十二日 + 发热及超高热危象

- Apr 22, 2023 + Jun 17, 2023

@@ -166,14 +166,14 @@

- + - 螺内酯片 + 二零二三年六月十日

- Mar 14, 2023 + Jun 10, 2023

@@ -184,14 +184,14 @@

- + - 呋塞米 + 二零二三年四月二十五日

- Mar 14, 2023 + Apr 25, 2023

@@ -202,14 +202,14 @@

- + - 替米沙坦 + 二零二三年四月二十二日

- Mar 13, 2023 + Apr 22, 2023

@@ -220,14 +220,14 @@

- + - 奥司他韦 + 螺内酯片

- Mar 5, 2023 + Mar 14, 2023

@@ -238,14 +238,14 @@

- + - 金匮要略 + 呋塞米

- Mar 4, 2023 + Mar 14, 2023

@@ -256,14 +256,14 @@

- + - 气胸 + 替米沙坦

- Mar 1, 2023 + Mar 13, 2023

@@ -274,14 +274,14 @@

- + - 纯牛奶可以加点啥 + 奥司他韦

- Mar 1, 2023 + Mar 5, 2023

@@ -292,14 +292,14 @@

- + - 二零二三年二月二十六日 + 金匮要略

- Feb 26, 2023 + Mar 4, 2023

@@ -308,7 +308,7 @@

diff --git a/archives/page/3/index.html b/archives/page/3/index.html index 19558e2b..f425e105 100644 --- a/archives/page/3/index.html +++ b/archives/page/3/index.html @@ -130,14 +130,14 @@

- + - 二零二三年二月二十五日 + 气胸

- Feb 25, 2023 + Mar 1, 2023

@@ -148,14 +148,14 @@

- + - 二零二三年二月二十四日 + 纯牛奶可以加点啥

- Feb 24, 2023 + Mar 1, 2023

@@ -166,14 +166,14 @@

- + - 二零二三年二月二十二日 + 二零二三年二月二十六日

- Feb 22, 2023 + Feb 26, 2023

@@ -184,14 +184,14 @@

- + - 二零二三年二月二日 + 二零二三年二月二十五日

- Feb 2, 2023 + Feb 25, 2023

@@ -202,14 +202,14 @@

- + - 二零二三年二月一日 + 二零二三年二月二十四日

- Feb 1, 2023 + Feb 24, 2023

@@ -220,14 +220,14 @@

- + - 二零二三年一月二十一日 + 二零二三年二月二十二日

- Jan 21, 2023 + Feb 22, 2023

@@ -235,19 +235,17 @@ -

2022

- + - 二零二二年十二月三十一日 + 二零二三年二月二日

- Dec 31, 2022 + Feb 2, 2023

@@ -258,14 +256,14 @@

- + - 二零二二年十一月月三日 + 二零二三年二月一日

- Nov 3, 2022 + Feb 1, 2023

@@ -276,14 +274,14 @@

- + - 二零二二年十月一日 + 二零二三年一月二十一日

- Oct 1, 2022 + Jan 21, 2023

@@ -291,17 +289,19 @@ +

2022

- + - 二零二二年九月二十二日 + 二零二二年十二月三十一日

- Sep 22, 2022 + Dec 31, 2022

@@ -310,7 +310,7 @@

diff --git a/archives/page/4/index.html b/archives/page/4/index.html index c15e5184..31de8c56 100644 --- a/archives/page/4/index.html +++ b/archives/page/4/index.html @@ -130,14 +130,14 @@

- + - 二零二二年八月二十一日 + 二零二二年十一月月三日

- Aug 21, 2022 + Nov 3, 2022

@@ -148,14 +148,14 @@

- + - 二零二二年三月十四日 + 二零二二年十月一日

- Mar 14, 2022 + Oct 1, 2022

@@ -166,14 +166,14 @@

- + - 二零二二年一月一日 + 二零二二年九月二十二日

- Jan 1, 2022 + Sep 22, 2022

@@ -181,19 +181,17 @@ -

2021

- + - 二零二一年三月二十七日 + 二零二二年八月二十一日

- Mar 27, 2021 + Aug 21, 2022

@@ -204,14 +202,14 @@

- + - 二零二一年三月十五日 + 二零二二年三月十四日

- Mar 15, 2021 + Mar 14, 2022

@@ -222,14 +220,14 @@

- + - 二零二一年二月十六日 + 二零二二年一月一日

- Feb 16, 2021 + Jan 1, 2022

@@ -237,17 +235,19 @@ +

2021

- + - 二零二一年二月十四日 + 二零二一年三月二十七日

- Feb 14, 2021 + Mar 27, 2021

@@ -255,19 +255,17 @@ -

2020

- + - 二零二零年十二月二十六日 + 二零二一年三月十五日

- Dec 26, 2020 + Mar 15, 2021

@@ -278,14 +276,14 @@

- + - 二零二零年十二月九日 + 二零二一年二月十六日

- Dec 9, 2020 + Feb 16, 2021

@@ -296,14 +294,14 @@

- + - 二零二零年十二月八日 + 二零二一年二月十四日

- Dec 8, 2020 + Feb 14, 2021

@@ -312,7 +310,7 @@

diff --git a/archives/page/5/index.html b/archives/page/5/index.html new file mode 100644 index 00000000..35aa1bf6 --- /dev/null +++ b/archives/page/5/index.html @@ -0,0 +1,215 @@ + + + + + + + + + + + + + + + + + + + + + +Archive | 暮秋小屋 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ +

+ + + 暮秋小屋 + + +

+ + +

+ + + + + + +

2020

+ + +

+ + + 二零二零年十二月二十六日 + + +

+ + Dec 26, 2020 +

+ + + + + + + +

+ + + 二零二零年十二月九日 + + +

+ + Dec 9, 2020 +

+ + + + + + + +

+ + + 二零二零年十二月八日 + + +

+ + Dec 8, 2020 +

+ + +

+ +

+ + + +

+ + + + + + diff --git a/page/5/index.html b/page/5/index.html new file mode 100644 index 00000000..2721ac77 --- /dev/null +++ b/page/5/index.html @@ -0,0 +1,185 @@ + + + + + + + + + + + + + + + + + + + + + +暮秋小屋 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

+ +

+ + + 暮秋小屋 + + +

+ + +

+ +

+ 暮秋小屋 +

+ 这里是暮秋小屋，思念和灵感的寄存处 +

+ +

+ 归档 +

+ +

+ 计算机科学 +

+ +

+ 医学 +

+ +

+ 生活 +

+ +

+ 日记本 +

+ +

+ 关于我 +

+ +

+ + + +

+ + + + + + diff --git a/tags/OCaml/index.html b/tags/OCaml/index.html index 463af888..3cce34bc 100644 --- a/tags/OCaml/index.html +++ b/tags/OCaml/index.html @@ -135,6 +135,60 @@

2023

+ + + tick thread在Multicore OCaml中的作用 + + +

+ + Aug 15, 2023 +

+ + + + + + + +

+ + + 使用 [@poll error] 实现线程安全的数据结构 + + +

+ + Aug 15, 2023 +

+ + + + + + + +

+ + + Typed Design Patterns for the Functional Era + + +

+ + Aug 15, 2023 +

+ + + + + + +

diff --git a/tags/Technique/index.html b/tags/Technique/index.html index af21e990..1ae251ee 100644 --- a/tags/Technique/index.html +++ b/tags/Technique/index.html @@ -135,6 +135,60 @@

2023