Zenn
Closed64

『並行プログラミング入門』をやっていく会

mohiramohira

README

公式情報

https://www.oreilly.co.jp/books/9784873119595/

https://github.com/oreilly-japan/conc_ytakano/

正誤表(PRでサッとコントリビューション可能！)↓↓
https://github.com/oreilly-japan/conc_ytakano/blob/main/errata.md

読書会の進め方

https://docs.google.com/presentation/d/1r54zmoTSlAsCl8SUgHjiq1ZBefYo19-NBBisy6DiO74/edit#slide=id.p

この本の推しポイント

  • 説明を正確にしていこうスタンスがビビットに感じられる
    • 必ずしも"理解しやすいかどうか"はわからないけど、理解できれば大丈夫だ！ という安心感
  • 並行処理の話題を包括的に扱っている(きっと誰が読んでも嬉しい)

関連する参考文献

全般

アクターモデル

mohiramohira

2021-09-08(水) 20:00-22:00

実績

  • はじめに 〜 1.3.2.1 応答速度とスループット まで
  • 10人くらいで交代音読した(2周ちょっと)
  • 参加メンバーの知識や興味はいい感じにバラバラ

次はどこから？

p.7 1.3.2.2 アムダールの法則（Amdahl's law）から

MEMO

話題がめちゃくちゃ広い！

  • 「本書の内容と読み進め方」を読もう

プロセス、そして並行性と並列性

  • 「プロセス」の定義
  • 「OSのプロセス」ではない
  • 並行性と並列性の厳密な定義
  • シングルコアの前提で読むといい感じ
  • 計算途中状態の定義が素晴らしいと思う

意外とあいまいワード集(いつかわかると嬉しい)

  • ファイルディスクリプタ
  • ユーザランド
  • カーネルランド
  • ネイティブスレッド
  • ユーザスレッド
  • コルーチン(Coroutine)
  • ゴルーチン(Goroutine)
  • スレッドのメモリ消費量
  • アクターモデル
  • Eralng
  • mmap / メモリマップトファイル
  • IO多重化
  • ミューテックス(Mutex; Mutual Exclusion) / 排他制御
  • CPUのインストラクション
  • クロック周波数
  • 命令サイクル

グっと来たところ

このような知識よりも、日々の積み重ねと、実際に 自分でコードを書いて動かしてみることが何よりも重要である。(はじめに v)

未解決

mmap

「ファイルを実メモリ空間として使うアイデア」という理解。

メモリ上のアドレス領域をファイル中の領域に対応付けることで、メモリ (中のアドレス) にアクセスするとファイルに読み書きする仕組み。
メモリにおさまりきらない巨大な空間をファイルとして実現したり、ファイルストリームを操作するのでなくメモリ上をランダムアクセスするように扱ったりできる。便利っちゃ便利。

mohiramohira

2021-09-16(木) 20:00-22:00

実績

  • p.7 1.3.2.2 アムダールの法則（Amdahl's law）から
  • 8人くらいで交代音読した(3周) + チャット参加3名くらい

次はどこから？

p.17 2.1.1アセンブリ言語の基本 から

MEMO

  • アムダールの法則
    • オーバーヘッドも考慮したアムダールの法則はいい感じ
    • 並列度
    • どれだけ並列処理が可能なのか
  • パイプライン処理
  • インストラクション並列性
  • データ並列性
  • シリコンウェハーとダイ
  • 製造コスト、発熱、消費電力、動作周波数、リーク電流
  • 「並行処理の複雑性を計算パス数爆発から考える」というアプローチが新鮮
  • 並列化のモチベーションは性能向上
  • CASL(キャスル)は教育用のアセンブリ言語的なやつ
  • いろんなハザード
    • 構造ハザード
    • データハザード
    • 制御ハザード

Cのvolatile(発音 【vάləṭl】(米国英語) 【vˈɔlətὰɪl】(英国英語))

C の volatile は、値が安定ではない変数。別スレッドで変更されているかもしれない共有変数とか、ハードウェア的に値が変化してしまったりするとか、そういうの。値を使う場面ごとにその値が変化している可能性を考えなければいけない (読み直さないといけない) ので、レジスタに乗せた値を使い回すみたいな最適化ができないとか、そういう並列性を阻害する要因になったりする。

mohiramohira

2021-09-30(木) 20:00-22:00

実績

  • p.17 2.1.1アセンブリ言語の基本 から 2.2.2 volatile修飾子 まで

次はどこから？

p.25 2.2.3 スタックメモリとヒープメモリ

MEMO

  • アセンブリ、アセンブラ、アセンブル
  • ニーモニックとオペコード
  • ニーモニックとオペコードは1対1とは限らない
  • デタッチスレッド
  • 最適化によるメモリアクセス回数の抑制
  • アセンブリコードで比較すると違いがわかる(楽しい)
  • .LBB0_2とかは「ラベル」←コードJUMPするときの目印
  • cbzは Condtion Branch Zero らしい。
    • この命令があるから、サンプルでは「非ゼロであーだこーだ」になっているのかな？
    • たとえば、メモリバリアの話も、cbzっぽい話があった → https://ja.wikipedia.org/wiki/メモリバリア

残念な最適化

// 実現したいコード
void wait_while_0(int *p) {
  while (*p == 0) { }
}

; 確かにメモリアクセス(つまり、 [x0]) は減っているけど
; LBB0_2から無限ループしちゃう(LBB0_2で、w8レジスタの値をチェックしてないので、抜け出せない==無限ループ)
wait_while_0:
  
  ldr w8, [x0] ; w8 にメモリから読み込み ❶ 
  cbz w8, .LBB0_2 ; if w8 == 0 then goto .LBB0_2 ❷
  ret 

.LBB0_2:
  b .LBB0_2 ; goto .LBB0_2

// Cだとこんな感じのコードになっちゃっている感じっぽい
// `*p`の値をチェックしてない！
int x = (*p == 0);  // ldr w8, [x0] ; w8 にメモリから読み込み ❶ 

while(x) {};
mohiramohira
#include <stdio.h>
#include <pthread.h> // ①
#include <unistd.h>

#define NUM_THREADS 3

// スレッド生成用関数
void *thread_func(void *arg) { // ②
    int id = (int) arg; // ③

    for (int i = 0; i < 5; i++) { // ④
        printf("id = %d, i = %d\n", id, i);
        sleep(1);
    }

    return "finished!";
}

int main() {
    pthread_t v[NUM_THREADS]; // ⑤

    // スレッド生成 ⑥
    for (int i = 0; i < NUM_THREADS; i++) {
        if (pthread_create(&v[i], NULL, thread_func, (void *) i != 0)) {
            perror("pthread_create");
            return -1;
        }
    }

    // スレッドの終了を待機 ⑦
    for (int i = 0; i < NUM_THREADS; i++) {
        char *ptr;
        if (pthread_join(v[i], (void **) &ptr) == 0) {
            printf("msg = %s\n", ptr);
        } else {
            perror("pthread_join");
            return -1;
        }
    }
    printf("main done");

    return 0;


}
mohiramohira

デタッチスレッドのモチベーション: 勝手に仕事してね！ 終わったら帰っていいよ！

  • 営業のメタファー
#include <stdio.h>
#include <pthread.h> // ①
#include <unistd.h>

// スレッド生成用関数
void *thread_func(void *arg) {
    for (int i = 0; i < 5; i++) {
        printf("i = %d\n", i);
        sleep(1);
    }

    return NULL;
}

int main() {
    // アトリビュート初期化 ①
    pthread_attr_t attr;

    if (pthread_attr_init(&attr) != 0) {
        perror("pthread_attr_init");
        return -1;
    }

    // デタッチスレッドに設定 ②
    if (pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED) != 0) {
        perror("pthread_attr_setdetachstate");
        return -1;
    }

    // アトリビュートを指定してスレッド生成
    pthread_t th;
    if (pthread_create(&th, &attr, thread_func, NULL) != 0) {
        perror("pthread_create");
        return -1;
    }

    // アトリビュート破棄
    if (pthread_attr_destroy(&attr) != 0) {
        perror("pthread_attr_destroy");
        return -1;
    }

    // MEMO: デタッチスレッドを使う時はmain関数が無限ループみたいなことが多いです
    // デタッチスレッドを使うモチベーション？ → 同期しない
    // →メモリリーク対策
    // しかし、joinできないとなると、同期できなくね？ → そもそも無限ループ的なところで使う？
    // https://discord.com/channels/508093437187457045/882639711447961710/893108272037494784
    sleep(7); // Q. joinじゃなくてデタッチスレッド使うから、sleepで無理やり待ち合わせ？

    // デタッチスレッド = 同期しなくて良いスレッド 👀 ←
    // 動いたら勝手に動いて勝手に止まってくれるスレッドを放置するときにデタッチ。
    // 勝手にぶん回ってくれて良くて、終了時に後始末さえしてくれてれば、それがいつ終わるかは関心の外、みたいな
    return 0;
}
mohiramohira

ARMとIntelの比較

  • レジスタとメモリアクセスの記法をおさえれば行ける気がする
int main() {
    int a = 10;
    int b = 0;
    int c = 0;

    b = a;
    c = a + b;

    return 0;
}

.arch armv8-a
    .file    "assemble.c"
    .text
    .align    2
    .global    main
    .type    main, %function
main:
.LFB0:
    .cfi_startproc
    sub    sp, sp, #16
    .cfi_def_cfa_offset 16
    mov    w0, 10
    str    w0, [sp, 12]
    str    wzr, [sp, 8]
    str    wzr, [sp, 4]
    ldr    w0, [sp, 12]
    str    w0, [sp, 8]
    ldr    w1, [sp, 12]
    ldr    w0, [sp, 8]
    add    w0, w1, w0
    str    w0, [sp, 4]
    mov    w0, 0
    add    sp, sp, 16
    .cfi_def_cfa_offset 0
    ret
    .cfi_endproc
.LFE0:
    .size    main, .-main
    .ident    "GCC: (Debian 8.3.0-2) 8.3.0"
    .section    .note.GNU-stack,"",@progbits

.file    "assemble.c"
    .text
    .globl    main
    .type    main, @function
main:
.LFB0:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    $10, -4(%rbp)
    movl    $0, -8(%rbp)
    movl    $0, -12(%rbp)
    movl    -4(%rbp), %eax
    movl    %eax, -8(%rbp)
    movl    -4(%rbp), %edx
    movl    -8(%rbp), %eax
    addl    %edx, %eax
    movl    %eax, -12(%rbp)
    movl    $0, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size    main, .-main
    .ident    "GCC: (Debian 8.3.0-6) 8.3.0"
    .section    .note.GNU-stack,"",@progbits
mohiramohira

2021-10-14(木) 20:00-22:00

実績

  • p.25 2.2.3 スタックメモリとヒープメモリから、p.32 2.3.2.1 let文 まで読んだ

次はどこから？

p.33 2.3.2.2 関数定義と呼び出し から

MEMO

雑談

  • エアコン自力分解と清掃
  • 魚をたべよう。Fishヘビロテ事件
  • 自炊の悩み(肉は良いのか悪いのか実験)

Enumは直和、Structは直積(Atsukiさんの説明がGreat)

  • Enumはそれぞれの値(Variant)が独立しているので直和的な感じ
  • で、Structは例えば、2つの属性をもつStructがとれる値の組み合わせは、総当たりだから、直積って感じ

集合Aが{0,1,2}、集合Bが{a,b,c}のとき、直和は{0,1,2,a,b,c}だからenum。直積は{{0,a},{0,b},...,{2,c}}だからstructということ？

Player {
  name string
  age  int
}

たとえば、こういう構造体があったときに、そのインスタンスは、nameの全通り x ageの全通り がありえる的な感じ。

実用上のコンパイラなら、レジスタに置くのがもう普通(スタックには置かない)

なお、コンパイラによる最適化が行われると、 a も b もスタックではなくレジスタに保存 されるだろうが、今回はコンパイラによる最適化は行われないものとする。
p.25

雑メモ(間違ってたら教えて下さい)
80年台) だったら、レジスタにおいて、メモリアクセスへらそうぞ
90年代) レジスタに置く流れ。
00年代) レジスタに置くようなプロセッサが主流

「文字集合」と「文字エンコード方式」を区別するのじゃ！

ただ、文字コードについては、『文字集合』の話をしてるのか『エンコード方式』の話をしてるのかを意識する癖を付ければ（そのうち無意識になるはず）、そこまで混乱することはないかもです。
バックスラッシュと円マーク問題などややこしい話もありますが、そのへんは枝葉の話なので。
https://discord.com/channels/508093437187457045/882639711447961710/898196642866536458

Rust の文字列は UTF-32 なのか UTF-8 なのか問題

結論としては、 char （文字）は UTF-32、 str , String （文字列）は UTF-8 でした。
https://discord.com/channels/508093437187457045/882639711447961710/898421666001072188

https://doc.rust-lang.org/std/primitive.char.html

char is a ‘Unicode scalar value’,

https://doc.rust-lang.org/std/string/struct.String.html

A UTF-8–encoded, growable string.

宿題: UTF-○ とか Unicodeとか、UTF-32を勉強しましょう！

参考文献

宿題: ○○積シリーズ

直積、デカルト積、アダマール積、外積、内積

ラムダ計算ってなんだろう？

いつか知りたいね。

rust の char は utf-32らしい

rust の char は UTF32らしいです。UTF32 は Unicode Scaler Point そのままの表現とのこと。
https://discord.com/channels/508093437187457045/882639711447961710/898180598529687593

型安全って何よ？

前述のように型安全性が具体的にどのようなものであるかはプログラミング言語や文脈に依存する。
https://ja.wikipedia.org/wiki/型システム

「型安全 is 何」ではなく、「型安全ではない is 何」で考えると、「私の中の型安全の定義」がしやすそう。

発音シリーズ

『プログラミング言語Rust（オライリー）』によれは、"mut"は「ミュート」と発音するそうです。
"let"は「れっと」でよかったはずです。
"fn"は、「ふぁん」とのことです。

その他

  • ダングリングポインタ
  • 英単語は画像検索しような
  • Enumのvariant
  • メモリリークのLeak感のなさ
  • トルコ語の hata は英語でいうと misstakeやfault的な意味
mohiramohira

はじめてのRust

fn let_example() -> u32 {
    let x = 100;
    let mut y = 20; // ①
    let z: u32 = 5;
    let w;

    y *= x + z;
    w = 8;

    y + w;
}

fn main() {
    println!("{}", let_example());
    println!("Hello, world!");
}

コンパイラのエラーメッセージがめっちゃ親切！

mohiramohira

2021-10-28(木) 20:00-22:00

実績

  • p.33 2.3.2.2 関数定義と呼び出し から p.36 2.3.2.8 関数ポインタ まで

次はどこから？

p.37 2.3.2.9 クロージャから

MEMO

Discordの開始地点
https://discord.com/channels/508093437187457045/882639711447961710/903246666646323230

雑談

  • 最近読んでいる技術書やマンガ
  • 浴室の乾燥機の自力分解で音が逆に大きくなった話
  • 魚で開眼！ 鱧！
  • ドイツ語たのしい
  • タンパク質補給計画

Rustでは、ifは文じゃなくて式; 式である嬉しさ

文は命令なので結果を返さず、式は演算なので結果を返す、的な違いだったかなと。
if文ではなくif式だと嬉しいのは、例えば分岐によって変数に入れる値が変わるときに、文だとと、一発で変数に代入できたりします。
https://discord.com/channels/508093437187457045/882639711447961710/903248905838399528

//typescript
let v: number

if (a) {
  v = 1
else if (b) {
  v = 2
else {
  v = 3
}

と、 mutable な変数の宣言が必要だけど、if式だと

# ruby
v = if a
  1
elsif b
  2
else
  3
end

上の例は typescript で、 typescript のifは文なので、分岐ごとに変数代入が必要です．
下の例は ruby で、rubyのifは式なので、if自体が最終的に値を返します。そのため、ruby では if の結果を直接変数へ代入でき、一時変数が不要になってます

if式は三項演算子の上位互換という考え方は新鮮

実際 Scala とか、 3項演算子がなかったりしますね。if式で十分実現できちゃうので。
if式は三項演算子の上位互換ですね。

これは、なるほど。いままでは「三項演算子はシンタックスシュガー」という感じの捉え方だった！

match式と、Option型とSomeとNone

  • Option<u32>型のvariantとして、NoneとSomeがある感じ
  • Some型とかNone型ではない
fn pred(v: u32) -> Option<u32> {
    if v == 0 {
        None
    } else {
        Some(v - 1)
    }
}


fn print_pred(v: u32) {
    match pred(v) {
        Some(w) => {
            println!("pred({}) = {}", v, w);
        }
        None => {
            println!("pred({}) is undefined", v);
        }
    }
}

fn main() {
    print_pred(1);  // pred(1) = 0
    print_pred(34);  // pred(34) = 33
    print_pred(0);  // pred(0) is undefined
    print_pred(-1);  // error[E0600]: cannot apply unary operator `-` to type `u32`
}

Stackoverflowになるコード実験 overflowでpanic

こちらを参照 → https://zenn.dev/link/comments/8ccd9dd7119e8b

fn pred(v: u32) -> Option<u32> {
    Some(v - 1)
}

// thread 'main' panicked at 'attempt to subtract with overflow', src/main.rs:2:10

fn main() {
    match pred(0) {
        Some(x) => {
            println!("some = {}", x);
        }
        None => {
            println!("none");
        }
    }
}

参照(reference)と参照外し(dereference)

fn mul(x: &mut u64, y: &u64) {
    // *x *= *x * y; // (*x) = (*x) * ((*x) * (*y)) という意味
    // *x *= x * *xy; // error[E0369]: cannot multiply `&mut u64` by `u64`
    *x *= x * y;  // error[E0369]: cannot multiply `&mut u64` by `&u64`


fn main() {
    let mut n = 10;
    let m = 20;

    println!("n = {}, m = {}", n, m); // n = 10, m = 20

    mul(&mut n, &m);

    println!("n = {}, m = {}", n, m); // n = 2000, m = 20
}

参照とポインタを区別する！

Rustでは、参照とポインタは区別されており、参照は、後に述べる所有権やライフタイムによって安全性が保証されているが、ポインタはその限りではない。

本質はポインタ。そして、ポインタは何でもできる！

何でもできるってことは危険なこともできたり、バグったりするわけで。

という背景からなのか、ポインタに制限をかけて安全に使えるようにしたのが「参照」という理解。

というか、区別したことなかった...

他のメンバーも区別したことが少なかった印象。逆に言えば、厳密な(？)区別をしなくても"使う分には困らん"的な話かも。

江添亮のC++入門 p.340 によると...

  • 参照はポインタの機能制限版
  • 参照は代入が出来ないが、ポインタは代入が出来る
  • 参照は必ず初期化しなければならない

Rustの公式Docによると...(スマートポインタだけど)

「スマートポインタ」 https://doc.rust-jp.rs/book-ja/ch15-00-smart-pointers.html

Rustでは、標準ライブラリに定義された色々なスマートポインタが、 参照以上の機能を提供します。

所有権と借用の概念を使うRustにおいて、参照とスマートポインタにはもう1つ違いがあります。参照はデータを借用するだけのポインタなのです。対照的に多くの場合、スマートポインタは指しているデータを所有します。

Q. 関数を「関数に渡す」ときにどういう挙動になっているんだろう？

Rust 以外でも、一般に「関数を渡す」というのは、関数の定義を指す参照なりポインタなりを渡すという挙動になっているんじゃないかしらと思います。それを言語がカバーしてくれているから、あたかも関数が数値や文字列と同じ値っぽく使えているだけで。
https://discord.com/channels/508093437187457045/882639711447961710/903261576189063178

Q. っていうか、関数を渡したときの挙動を調べる方法がわからないのだが？

調べ方がわからん！

デリファレンスメモ

Goだけど。やっぱ、アドレスとか参照とかポインタとかデリファレンスが曖昧なんだな〜

package main

import "fmt"

func main() {
	var a int = 123
	var x *int = &a

	fmt.Println(x) // 0xc000128008
	fmt.Println(&x) // 0xc00000e028
	fmt.Println(*x) // 123
}

package main

import "fmt"

type Vertex struct {
	X int
	Y int
}

func main() {
	v := Vertex{3, 4}

	fmt.Println(v) // {3 4}

	// Xのアドレス 0xc00012a010
	fmt.Println(&(v.X))
	fmt.Println(&v.X) 

	// Xの値(つまり、3)を取得する書き方
	fmt.Println(v.X) // .で楽にアクセスできる
	fmt.Println(*(&v.X)) // 明示的なデリファレンス(*)
	fmt.Println((&v).X) // 3
}

Q. println!がマクロなのはなぜ？ マクロじゃなくても良くない？

  • 可変長引数に対応するため？
  • Rustで可変長引数はできないから？

Rustでマクロがどうなっているかを展開するライブラリ

https://github.com/dtolnay/cargo-expand

$ cat src/main.rs

#[derive(Debug)]
struct S;

fn main() {
    println!("{:?}", S);
}

$ cargo expand

#![feature(prelude_import)]
#[prelude_import]
use std::prelude::v1::*;
#[macro_use]
extern crate std;
struct S;
#[automatically_derived]
#[allow(unused_qualifications)]
impl ::core::fmt::Debug for S {
    fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
        match *self {
            S => {
                let mut debug_trait_builder = f.debug_tuple("S");
                debug_trait_builder.finish()
            }
        }
    }
}
fn main() {
    {
        ::std::io::_print(::core::fmt::Arguments::new_v1(
            &["", "\n"],
            &match (&S,) {
                (arg0,) => [::core::fmt::ArgumentV1::new(arg0, ::core::fmt::Debug::fmt)],
            },
        ));
    };
}
philomagiphilomagi

Stackoverflowになるコード実験

として掲載されているコードですが、Stackoverflow を起こす意図のものではなかったです(実際、起こるのは算術オーバーフローであってスタックオーバーフローではないです)

書籍のサンプルコードについて、当時口頭で出ていた「なんでわざわざ分岐してOptionにラップしてるんだろう」という疑問に対して

u32 は符号無し整数なので、マイナスの範囲を取れないからというのもあるかと。 > Some でラップしてる理由

と回答していましたが、それ = 結果がマイナスになる計算をすると実際マズイ、ということを確認・実証するためのコードでした。
https://discord.com/channels/508093437187457045/882639711447961710/903252859137720350
↓から
https://discord.com/channels/508093437187457045/882639711447961710/903253988013662269
の流れ。

実行してみると、実際に overflow (とメッセージが出るが、正確にはアンダーフロー？)によってpanicが発生し、プログラムが停止してしまうことが確認できるかと。

サンプルコードは特に再帰を行っていないので、 stack overflow にはならないですね。

mohiramohira

2021-11-11(木) 20:00-22:00

実績

  • p.37 2.3.2.9 クロージャから p.42 2.3.4 ライフタイム まで

次はどこから？

  • p.43 2.3.5 借用から

MEMO

Discordの開始地点
https://discord.com/channels/508093437187457045/882639711447961710/908310043856891904

雑談

  • 最近読んでいる技術書やマンガ
    • 『ちはやふる』
    • 『トリリオンゲーム』
  • エアコンは会社ごとにちょっと違う話
  • ハモを鍋にぶちこむ
  • 肉はやっぱり必要だ
  • ガトーショコラの砂糖の量そして、砂糖と脂肪はうまい
  • こたつデプロイOK
  • 食あたりには気をつけよう

Box

Box というのはコンテナの一種で、ヒープ上にデータを配置したい場合に用いられる。
https://doc.rust-jp.rs/rust-by-example-ja/std/box.html

ポリモーフィズムを実現するための仕組みとしての、仮想関数テーブル(C++)

Animal型の具象クラスa があって、a.bark() としたときに、a は実際には Cat なりDogなりになる。

で、bark()がCatのbark()なのか、Dogのbark()なのかを区別できないのであれば、このポリモーフィズムが実現できない。

それを実現するための仕組みの1つの例が、「C++の仮想関数テーブル」

Q. トレイトって何？

TODO

Q. (メモ) クロージャでBoxを使っている意味 多分こうかも？(仮)

https://discord.com/channels/508093437187457045/882639711447961710/908323030537756722

Rustのキーワード

  • dyn: たぶん、Dynamicの略
  • impl
// 実行時に決まる
// fn mul_x(x: u64) -> dyn Box::<Fn(u64) -> u64> {
//     Box::new(move |y| x * y) // ②
// }

// Static dispatch: コンパイル時点で確定する
fn mul_x(x: u64) -> Fn(u64) -> u64 {
    move |y| x * y
}

fn main() {
    let f = mul_x(3);

    println!("f(5) = {}", f(5));
}

Q. doesn't have a size known at compile-time のsizeって何？

https://discord.com/channels/508093437187457045/882639711447961710/908324536808767519

線形論理

  • シークエント
  • -o: loli
  • `├: tee

線形論理ちょっとおもろいかも？ コンパイルの仕組みがみえてきそうかも

コンパイラ内部では、所有権の移動を線形論理式に変換して、その式が成り立たなければエラーにするということをしてそうですね。
https://discord.com/channels/508093437187457045/882639711447961710/908330858920960051

MoveセマンティクスとCopyセマンティクス

https://discord.com/channels/508093437187457045/882639711447961710/908333135014543401

// copyセマンティクスにすると、moveしなくてもいける
// というか、値をコピーして渡していそう
// コピーしちゃうので、でかい構造体を使うときとかはもったないかもしれない
#[derive(Clone, Copy)]
struct Apple {}

struct Gold {}

struct FullStomach {}

fn get_gold(a: Apple) -> Gold {
    Gold {}
}

fn get_full_stomach(a: Apple) -> FullStomach {
    FullStomach{}
}

fn main() {
    let a = Apple{};

    // copy
    let g = get_gold(a);

    let s = get_full_stomach(a);
}

#[derive(Clone)]
struct Apple {}

struct Gold {}

struct FullStomach {}

fn get_gold(a: Apple) -> Gold {
    Gold {}
}

fn get_full_stomach(a: Apple) -> FullStomach {
    FullStomach{}
}

fn main() {
    let a = Apple{};

    // [Clone]のみにすると、明示的なcloneすればOK(しないとコンパイルエラーになる)
    let g = get_gold(a.clone());

    let s = get_full_stomach(a);
}

Q. ライフタイム感あふれるサンプルコードがほしいね？

  • Q. スコープとライフタイムの違いがびみょい
  • Q. ライフタイムを体験したいのだが、いいサンプルコードはないか！
mohiramohira

2021-11-25(木) 20:00-22:00

実績

  • p.43 2.3.5 借用から 2.3.6 メソッド定義まで

次はどこから？

  • p.48 2.3.7 トレイト から

MEMO

Discordの開始地点
https://discord.com/channels/508093437187457045/882639711447961710/913383622617219072

雑談

  • オーバーホール 洗濯機編でのトラブル！ 次回に期待！
  • 一升炊きの炊飯器最高！
  • ブラックフライデー何狙う？
  • 生活の知恵が集まる勉強会
  • ホットサンドと良い包丁
  • 鉄パイプ整体と謎のイメージ
  • 「ゆめぴりか」が気になる話
  • Bluetoothに対応させたい話
  • コミットメッセージがHotTopic！
    • いつか語らおう！

2週間に1回ペースが良いという話

  • ちょうど人と話したいくらいの開催が良いという説
  • 読破までの時間はかかるけど、速攻で読む本でもないからいい感じな話
  • みんなで喋れるのがいいよね

借用の簡易モデルをベースにして、コードで実験する方法を理解した！

invalidな状態遷移を含むコードを書くと、ルートによって違ったエラーメッセージがでるっぽいので、意識的な学習がしやすいと思う！

コンパイラ任せもいけど、意識的な学習もあり！

状態遷移モデル(のび/たけし/スネ夫)

所有権とライフタイムとスコープの話がわかった感じ！？

所有権の実験 → https://discord.com/channels/508093437187457045/882639711447961710/913408437432516688

struct Vec2 {
  x: f64,
  y: f64,
}
impl Vec2 {
  fn new(x: f64, y: f64) -> Self {
    Vec2{x, y}
  }
  fn norm(&self) -> f64 {
    (self.x * self.x + self.y * self.y).sqrt()
  }
  fn set(&mut self, x: f64, y: f64) {
    self.x = x;
    self.y = y;
  }

  fn double(self) -> Self {
    Vec2::new(self.x * 2.0, self.y * 2.0)
  }
}

fn main() {
  let mut v = Vec2::new(10.0, 5.0);
  println!("v.norm = {}", v.norm());
  v.set(3.8, 9.1);
  println!("v.norm = {}", v.norm());
  // v.double();
  let v = v.double();
  println!("v.norm = {}", v.norm());
}

fn transform(self) -> AnotherSelf

アイデンティティを保存しながら複数は存在させない感じです
https://discord.com/channels/508093437187457045/882639711447961710/913425228116422716

struct Magikarp {
    hp: u32,
}
impl Magikarp {
    fn haneru(&self) {
        println!("No effect!")
    }
    fn evolve(self) -> Gyarados {
        println!("What? Magikarp is evolving!");
        Gyarados { hp: self.hp + 100 }
    }
}

struct Gyarados {
    hp: u32,
}
impl Gyarados {
    fn hydro_pump(&self) {
        println!("Critical hit!")
    }
}

fn main() {
    let zako = Magikarp { hp: 5 };
    zako.haneru();
    zako.evolve().hydro_pump()
}

未解決: selfを引数にもつメソッドの使い所は？

変換したあとに、変換前のオブジェクトをいじっちゃって事件になることない的な？

struct Vec2 {
    x: f64,
    y: f64,
}

impl Vec2 {
    fn new(x: f64, y: f64) -> Self {
        Vec2 { x, y }
    }
    fn norm(&self) -> f64 {
        (self.x * self.x + self.y * self.y).sqrt()
    }
    fn set(&mut self, x: f64, y: f64) {
        self.x = x;
        self.y = y;
    }

    fn double(self) -> Self {
        Vec2::new(self.x * 2.0, self.y * 2.0)
    }
}

fn main() {
    let mut v = Vec2::new(10.0, 5.0);

    println!("v.norm = {}", v.norm());

    v.set(3.8, 9.1);
    println!("v.norm = {}", v.norm());

    v.double();
    // let v = v.double();
    println!("v.norm = {}", v.norm());
}
mohiramohira

2021-11-25(木) 20:00-22:00

実績

  • p.48 2.3.7 トレイト から p.56 3.1 レースコンディションまで

次はどこから？

  • p.57 3.2 アトミック処理から

MEMO

Discordの開始地点
https://discord.com/channels/508093437187457045/882639711447961710/918459037480284170

雑談

  • 最近ゲームを買った話、やった話
    • パワポケR, Population ONE, アーマードコア2と3, FitnessBoxing, ダンガンロンパ2
  • 今年良かった本のシーズン
    • セキュア・バイ・デザイン, 組織の猫という働き方 などなど
  • インターネットが壊れたのでルーターをどうにかする話

2章おわり！ 嬉しい！

  • 2章のラストがスレッドだったので、並行処理感ができてテンション上がる！

Rustのトレイト

  • Javaでいうインターフェイスと、Haskellで型クラスのあわせ技っぽいやつ
  • 実装時(impl)に型を決めることができるInterfaceって感じの理解
  • 他の言語のトレイトとはちょっと違うかも？

?演算子 と unwrap関数

  • エラーハンドリング大事！
  • カジュアルな(？)コードなら、?で書くと楽っぽい

unwrapのコード例

https://discord.com/channels/508093437187457045/882639711447961710/918476183472078849

fn as_opt(v: u32) -> Option<u32> {
  if v < 100 {
    Some(v)
  } else {
    None
  }
}
fn get_opt(v: u32) -> Option<u32> {
  let a = as_opt(v)?;

  Some(a * 2)
}
fn main() {
  println!("getOpt = {}", get_opt(99).unwrap());
  println!("getOpt = {}", get_opt(100).unwrap());
}

Rustの強力さがワクワク

Rust言語では同期処理で陥りがちなミスを型システムにより防ぐことができる。

これマジでテンション上がる！

mohiramohira

2021-12-23(木) 20:00-22:00

実績

  • p.57 3.2 アトミック処理から p.64 まで

次はどこから？

  • p.64 3.3 ミューテックス

MEMO

Discordの開始地点
https://discord.com/channels/508093437187457045/882639711447961710/923534451819044936

雑談

  • 最近は「R」(パワポケR、R、Rust)
  • 雪が降って寒い@長野
  • 『わかりやすさの罪』
  • アロマオイルをたきはじめる。アロマオイルベンチマークが大事
  • セキスペの1点...!!!
  • 昇降デスクいいよね！
  • 『Cooking for Geeks 第2版――料理の科学と実践レシピ』(https://www.oreilly.co.jp/books/9784873117874/)
  • 来年もベストバイやろう！

アトミックはコンピュータのコア概念であって、DB特有の話題じゃないよ！

せや！

追記。

前回(第9回)、「アトミック」について、「他からの可視性」か「トランザクション(ロールバック可能)」かで、低レイヤと高レイヤで認識の相違があるよね、という話がありましたが、これについて再考したところ、やはり「他からの可視性」が(アトミック性の)本質であり、トランザクション（ロールバック）はその1手段に過ぎないということに気付きました。

例えば、「口座Aから口座Bへの100万円を送金する(が、失敗する)。」という以下のシナリオを考えてみます。
①口座Aから100万円を引き落とす。
②口座Bへ100万円入金しようとしたが、何らかのエラーが起きて、入金できない。
③ロールバックして、口座Aからの引き落としもなかったことにする。

ここで、なぜロールバックをする必要があるのかを考えてみると、
「『口座Aから引き落としたが、口座Bへは入金していない。』という状態を誰にも観測させない。」
ためのはずであり、「トランザクション（ロールバック）は、アトミック性（可視性）を保証するための手段であると言えます。

https://discord.com/channels/508093437187457045/882639711447961710/928635877150842961

「アトミック操作四天王」

  1. CAS: CompereAndSwap
  2. TAS: TestAndSet
  3. LL/CS: LoadLink/StoreCondtion
  4. FetchAndAdd ← 四天王の中でも最弱(最近そんな使われない的な雰囲気を感じる時がある)

Maurice Herlihy (1993年)は、フェッチ・アンド・アッドがコンペア・アンド・スワップよりも劣っていることを証明した。[(フェッチ・アンド・アッド（Fetch-and-Add）]https://ja.wikipedia.org/wiki/フェッチ・アンド・アッド)

CAS, TAS, LL/CSは「なんとなく3つくらい選んだ」というノリじゃない。

3.2.1〜3.2.3 の3つ(+FetchAndなんとか)の4つ、アセンブラ命令として登録されている！

アトミック操作の代表的な4命令。デザインパターン的な雰囲気。

たぶん、CPUアーキテクチャに依存しない話っぽい。

アトミックという性質から導かれることで、「観測できるか」が重要な話！

低レイヤだと、観測できるかどうかが重要で戻せるかどうかは考えないです。というか、低レイヤレベルでは復元自体ができない。

ロールバックだけだと思ってた！ マルチコアのときに、他のコアから見えるかどうかも大事！

この辺、仕事でも実際に「他コアから〇〇が観測できるようになる前に、△△が観測可能になっていること。」みたいな仕様は書きます。

仕様として書くってのはなるほど感ある。

Goのsync/atomicパッケージの命令の意味がだいぶつかめた説！

https://pkg.go.dev/sync/atomic

アセンブリの省略(？)用語

x86-64のアセンブラ命令の末尾のlは32ビットで、q(quadの意)が64ビットです。
xorl はxor longだと思います。longは操作対象のデータが32ビットという意味です。
Intel CPUは16ビットを基準と考えるので、4倍のquadです。

理解の解像度が上がる！

何の話かというと、「Cとかのソースコードの行」と「CPU命令」は1対1対応じゃない！
ソースコードの1行分が、複数のCPU命令を実行することになる。

ので、ソースコードだけだと、理解が甘くなりがち。
だけど、ソースコードから吐き出されたアセンブリを読むと、抽象度のレベル(というか、粒度？)が揃うので、より中身を理解しやすい。納得感がある。楽しい。

アセンブリは読めない部分も多いけど、注釈だったり、みんなで読めばなんとかなる。

Cは低級言語じゃないよ！

みんなCが高級言語ってことを忘れがちですね

アセンブリの話をみると、この話がよーくわかる。

mohiramohira

2022-01-06(木) 20:00-22:00

実績

p.64 3.3 ミューテックス 〜 p.72

次はどこから？

次回 p.72 3.4.2 POSIX セマフォ

typoとかみつけた

  1. 行番号あるのに言及がないぞ？ → https://discord.com/channels/508093437187457045/882639711447961710/928617172136235028
  2. typo: p.65 「代入してして」 → PR送った https://github.com/oreilly-japan/conc_ytakano/pull/66

大事なこと

今年で読破したい！

気持ち的に1年でおわらせたい雰囲気

余談のほうが(本文よりも)重要

余談はその瞬間にしか存在しないのだ！ 本文はいつでもそこにあるじゃないか！

「隙間」を意識することこそ重要

1行や1文が、最小単位だと思うなよ！(ﾃﾞﾃﾞｰﾝ!!!

いかに、隙間を意識できるか、あるいは、隙間に割って入られることを自然に想像できるか？

繰り返しっぽくなり、また、既におっしゃっていただいてますが。
高レイヤはある程度以上の経験はあるけど、低レイヤに慣れてないという方が、低レイヤの考えに慣れるのに一番大事なのは、やはり「隙間」を意識ことだと思います。
https://discord.com/channels/508093437187457045/882639711447961710/928633675749417040

見えるようになってきたのは、アトミック感というより非アトミック（≒隙間）感かも
一まとまり（アトミック）に見えるコードブロックが、実際には他プロセスが横から到達し得るもの（非アトミック）であることに気づきやすくなってきた、的な
https://discord.com/channels/508093437187457045/882639711447961710/928638976628236300

MEMO

最近どう？

  • 原神にハマる
  • 統計だったり、数学だったり、vimだったり、いろいろやったり
  • お家のリファクタリング ← CI回してる？
  • センター試験(共通テスト)の現代文をみんなでやってみよう
  • 2ヶ月で65万歩歩いた話
  • レーザーの痛みは剣山

「アトミック四天王」という言葉が便利！

4つあることも覚えられるぞ！

  1. CAS: CompereAndSwap
  2. TAS: TestAndSet
  3. LL/CS: LoadLink/StoreCondtion
  4. FetchAndAdd ← 四天王の中でも最弱(最近そんな使われない的な雰囲気を感じる時がある)

FetchAndAddは四天王の中でも最弱と見せかけて活躍する回。

セマフォの実装で使われているぞ！ (なんで前節で省略されていたんだろう？)

メモリを読み込んだあとに、← LoadLink
俺が書き込む ← Store
ただし、だれも書き込みをしていなければ、(読み込みはセーフ！) ← Conditional

※ アクセスでなく、書込みであることが重要

「アクセス」とか「触る」って言葉を使わないで、ちゃんと「読み込み」と「書き込み」は区別しような！

低レイヤの文脈にあわせた語彙を知るとよいぞ！

https://discord.com/channels/508093437187457045/882639711447961710/928631076539232257

fetch と read の違い

fetch: メモリから実行命令をとってくる

read: データの読み込みが普通。fetchと同等の意味で使うこともある。

逆に言えば、「データを読み込む」という表現をするために、fetchと言うことは少なそう。諸説あり。

おお、p.11 でも「命令読み込み（IF：Instruction Fetch）」だ

ミューテックスとセマフォの区分

mutexとsemaphoreを区分するときに、「ロックを獲得できるプロセス数」で考えちゃうと、混乱しちゃう。というか、同じものに見えちゃったりした。あるいは、排他制御だけを目的とすると、「競合状態が起きるうセマフォの存在意義なくね？」っておもっちゃった。

たしかに、実装上は特殊化/一般化というかんじだけど、モチベーションが違うのだ！ と思うといい感じな気がする。

mutex ← 競合状態を防ぎたーい！
semaphore ← 同時に実行できるプロセスを抑制したーい

Mutexとセマフォを実装するモチベーションはそのような感じですが、実装上は「Mutexが1つ」または「最大1のセマフォが1つ」あれば、任意の数のセマフォとMutexを実装することができます（性能は「直に実装した場合」よりは落ちますが。）。
https://discord.com/channels/508093437187457045/882639711447961710/928628030627274762

Gmailの実装の話。16スレッド制限していて、セマフォがあった話。

mutex
一度に走るプロセスが最大1でなくてはならないことを保証するための機構。排他制御。

semaphore
同時に複数のプロセスが走ってよいが、好き勝手に走らせるのではなく、一度のプロセス数を制御したい場合の機構。排他制御ではない。並行処理によってマシンリソースが食い尽くされないようにする時とかに使う、調整のための仕組み？
https://discord.com/channels/508093437187457045/882639711447961710/928625890517205033

「トイレのたとえ」がおもしろい。スピンロック

ロックを獲得したプロセスが、待機中になってるともったいないよねって話。

トイレ使ってないのに、トイレを占有している感じ

割り込み的には、「トイレに入って用足そうとしたら緊急Skype飛んできて身動き取れなくなった」的なシーンを想像した

トイレのドアだけ開けた感じ
座れない

一縷ののぞみをかけてノックし続けてる光景を想像した

whileを使って、TASの無駄を減らすテクニック

ぱっと見ると、何をやっているか、わかりにくいから、コメント書こうぜ！

void spinlock_acquire(volatile bool *lock) { // ❶
  for (;;) {
    while(*lock); // ❷
//////////// ここに隙間があるぞ！ //////////
    if (!test_and_set(lock))
      break;
    }
  }
}
mohiramohira

2022-01-20(木) 20:00-22:30

実績

p.72 3.4.2 POSIXセマフォ 〜 3.5 条件変数

Discord開始リンク

https://discord.com/channels/508093437187457045/882639711447961710/933680924506333184

次はどこから？

次回 p.77 3.6 バリア同期

大事な話

なにかしら話してみると良いことがある！ というか、それが集団で本を読むときの強み！

  • e.g. Redisの、Publisher-Subscriberの話をしてくれた
  • e.g. Producer-Consumerモデルで通知のシステムを実装した話をしてくれた
  • e.g. 過去に○○をやったことがあるけど、たぶん○○は☆☆に該当すると思う話をしてくれた

MEMO

最近どう？

  • 統計検定の話
  • 虚無感のある雪かき。雪かきは賽の河原説
  • Scala + Akka をいじりはじめた
  • 百問百答が切れ味良すぎてずっと笑ってる
    • Q. 簡単な本は読めるけど、専門書が理解できないです。頭が悪いから？
    • A. 頭が悪いからではなく、頭が固くせっかちで、理解できるようになる努力を怠っているから
  • おうちCI
    • ルンバが通れたらGREENという発想
  • おうち環境はサーバー環境と似ている。良い環境を作ると効率がバク上げ
  • Alder Lakeを使いたいが、Mini-ITXの配線が辛い！

キーワード

  • OSワイド = OS全体。プロセスをまたいで。

Producer-Consumerモデル と Publisher-Subscriberモデル は似ているけど違うよ

このメタファー天才か！？

https://stackoverflow.com/questions/42471870/publish-subscribe-vs-producer-consumer

Publish/Subscribe : Subscribers subscribe to the publisher. Each message the Publisher publishes is sent to all the subscribers. That is, all subscribers receive the same message. (Think of a newspaper or magazine subscription. All subscribers receive the same magazine or newspaper)

まじで、購読している。出版されたら、購読者全員に届く！ デアゴスティーニ！

Producer/Consumer : Each message the producer produces will be consumed by a single consumer. This is a mechanism to distribute the work load to multiple consumers. (Think of the several cash registers at the supermarket. Each customer goes to a single cash register. The customers are like the messages that are produced and the cash registers are the consumers)

消費者全員じゃない。データ1つにつき、1人しか食べられないよ。

Producer-Consumerモデル(結城さんの説明)

これはOS、マルチタスク、マルチスレッドの本などによく登場するパターンです。

https://www.hyuki.com/dp/dpinfo.html#ProducerConsumer

アトミック感を感じながら読めたので、成長性した説！

Producer-Consumerモデルの嬉しさ

push通知の実装の例

C「もっと仕事くださいよ〜」 → Pを増やす or Cを減らす

Pの数やCの数を個々に調整できる！

P を増減させるケースもありますよ。データを用意するのに時間がかかるけれど、消費は相対的にかんたんな場合。
例えば、P がネットからデータを取得してくると待ち時間がかかるので、並列に実行して、C はローカルに処理するので多少の処理でもすぐ終わる、みたいなのとか

逆に考えて、PとCを同時にやるのはかなり大変な気がする(パフォーマンスもつらそう)
実装がシンプルになるのも、直感的には理解できる感じがある。

条件変数むずかった....

管理すべき対象が多いので難しかった。というか、最終的に理解はできなかった！

が、丁寧に状態を追ったり、スレッドの状況を可視化してみたり、ともかく、ゆっくり考えれば辿り着けそうな気もする。ので、必要になったときにまた勉強しような！

参考になりそうなやつ↓↓

Goのやつだけど、語彙的な感じをみるに条件変数のはなしっぽい

https://lestrrat.medium.com/sync-cond-コンディション変数についての解説-dd2050cdfab7

https://zenn.dev/yohhoy/articles/multithreading-toolbox#📬条件変数(condition-variable)

ミューテックス(Mutex) は単純な共有資源アクセスの排他制御しか行えません。一方で典型的な並行・並列理設計では「共有資源としてのデータ構造が、特定の状態に変化するまで待機」したい状況がよくあります。例えば複数スレッド間でデータを安全に送受信する有限長のFIFO待ち行列データ構造を考えると、取出側は有効なデータが存在するまで待機、挿入側は空きができるまで待機する必要があります。

同期プリミティブとしての条件変数は、3つの基本操作を提供します。［角括弧内は操作名］

おーひらP、シグナルばらまき問題(問題?)

わろたw

この勉強会は、Pub-Sub実装だった……？

精神的な余裕があるから、せっかちにならずに本を読める

正直、並行プログラミングがわからなくて、(直近では)まず困らんしな！ だからこそ強気に、気軽に、読める

あー、「役に立たない」からこそ、じっくり腰を据えることができる、というのはありますよね。わかる

mohiramohira

2022-02-03(木) 20:00-22:30

実績

p.77 3.6 バリア同期〜p.82 スピンロックでのRWロック

Discord開始リンク

https://discord.com/channels/508093437187457045/882639711447961710/938752903982768138

次はどこから？

次回 p.83 3.7.2 PthreadsのRWのロックから

大事な話: 復習したらよさそう！

つよくてNewGame会！ 3月はこれをやるぞ！

  1. 音読したい人を決める
  2. ひたすら交代で読む
  3. くりかえす

黙読したい人もいると思うので、そういうようにVCを追加する。

ザクザク音読する。合宿的にやりたいな。ひたすら読む。

MEMO

最近どう？

  • 数理統計学
  • スタサプ！
  • オンライン英会話
  • プラモ作り
  • 仕事が忙しくなって、最近数学や読書がgdgd気味とみせかけて、やっぱ読んじゃう
  • 『ライティングの哲学』読んでみた

キーワード

  • バリア同期
  • メモリフェンス
  • RWロック
  • RWロックの3条件
  • たくぼさんクイズ
  • バリア同期はランデブー
  • レイヤーが違う話。レイヤーを意識すること。CPUとかのレイヤーかもしれないぞ？
  • 隙間に宿る話
  • スピンを使いこなしている
  • 借用、RWロック、(DBの)専有ロック
  • 並行処理は考慮をし続けろ

バリア動機とメモリフェンスは違うぞ！

RWロックが満たすべき3つの条件と借用がおなじやんけ！

Rustの「借用」とDBのロックと、RWロックが同じ話

育ってきた環境によっては、ロックの概念を知るレイヤーが違う(それはそう)

それがつながるのが気持ちいい！

よいまとめ

https://discord.com/channels/508093437187457045/882639711447961710/938779207205519380

- Readers-Writer ロック、DBの共有ロック/専有ロック、Rustの借用との類似点に対する指摘は個人的に発見だった
  - 類似点というか、Readers-WriterロックのアプローチをDBのトランザクションやメモリ管理の静的解析に応用した結果としてそれらが生み出された、という整理が適切そうかも
  - 温故知新的なアレ
- 各種操作とか、やはり前の部分結構忘れてきてるなーという感じ
  - 3章は、一周してからもう一周してみると用語が整理しやすそう
- 「隙間」とか「スピンロック」とか「アトミック」とか、観点や関心を表現する語彙が揃ってきた今、もう一度1章を読み返すと、だいぶ見える景色が変わりそう
mohiramohira

2022-02-17(木) 20:00-22:00

実績

p.83 3.7.2 PthreadsのRWのロックから p.91 まで

Discord開始リンク

https://discord.com/channels/508093437187457045/882639711447961710/943824433469091880

次はどこから？

次回 p.91 3.8.2 条件変数から

MEMO

最近どう？

  • オンライン英会話とモロッコの先生
  • 積ん読の消化。『コンピュータの数学』と『The Art of Computer Programming』
  • リフレッシュの仕方。コンテキストスイッチ。散歩しよ

キーワード

↓↓参照！

あべさんの追加実験！

https://zenn.dev/k_abe/articles/cc4909ab1a575e

philomagiphilomagi

スレッド数が増えていくと、Readロック、Writeロック、Mutexの実行速度がどのように変化していくか
https://discord.com/channels/508093437187457045/882639711447961710/943842248653692938
https://discord.com/channels/508093437187457045/882639711447961710/943843829612683295
https://discord.com/channels/508093437187457045/882639711447961710/943844482439319582

  • Readロック
    • 同時に複数のロックを取得できるので、ほとんど影響しない
  • Mutex
    • 同時に1スレッドしかクリティカルセクションを実行できないので、スレッド数が増えるほど影響が出る
  • Writeロック
    • Mutexと同様

ただし、Readロックでも、ループ数が少ない場合はロックのオーバーヘッドが上回り、性能に影響が出る（Mutexと大きく変わらない程度になる）

そもそも10,000も100,000もぶん回すようなコードってどうよ、というお話
https://discord.com/channels/508093437187457045/882639711447961710/943845485372932097

以上より、Read がほとんどの場合では、ミューテックスよりも RW ロックを使う方が実行速度 が向上することが実験からも明らかとなった。しかし、クリティカルセクション中に、10,000 程 度もの CPU クロックサイクルを消費するような記述は避けるべきであり、難しいところではある。

Siena.Siena.

気になったっぽいポイント:

  • Cのポインタ記号って、型と変数名のだいたいどっちにつけてもOK的なアレだったようないにしへの記憶
  • ワーカスレッド
  • ミューテックス振り返り
  • アムダールの法則と、並行数・同時実行制御方式と処理性能
    • アムダールの法則、ワーカが増えても線形には増えないというところがポイント

    • 以上より、Read がほとんどの場合では、ミューテックスよりも RW ロックを使う方が実行速度 が向上することが実験からも明らかとなった。しかし、クリティカルセクション中に、10,000 程 度もの CPU クロックサイクルを消費するような記述は避けるべきであり、難しいところではある。

  • Rust の所有権と move
  • (ライト)ロックとミューテックスの違い
    • ライトロックは、あるデータを変更してはだめ。ミューテックスは、同時に実行しちゃだめ。排他する粒度が違います。
  • ミューテックス v.s. バイナリセマフォ
mohiramohira

2022-03-02(木) 20:00-22:00

実績

p.91 3.8.2 条件変数からp.94 バリア同期 まで

Discord開始リンク

https://discord.com/channels/508093437187457045/882639711447961710/948898927330066492

次はどこから？

次回 p.95 セマフォから

復習回に関する具体的なアイデア

  • 「俺が勝手に説明するから、俺の間違いを正して！」会にする
    • みんな「mohiraにPRを送ったり、Approveしたりする」
    • レギュラー回とはべつにやる。

MEMO

最近どう？

  • 英語の勉強も継続中
  • 生物もソフトウェアというか、システムとして見る
  • macの調子が悪いっ！
  • 朝に散歩してダイエット順調！

初の12枠超え！！！

まさか、オーバーするなんて！

C言語(Pthreads)とのRustの実装を見比べると理解が深まる

Cだと、各ロックを動作させるための具体的な処理方法とか実現手順を把握できた一方で、詳細に圧倒されていた部分もだいぶありつつ。

その過程を経てからのRustだと、そうした詳細はより抽象化したAPIに隠蔽されているので具体的な処理はさておきつつ、それらのロックを使うことによってどんな効果が得られるのかに注目できた感じがしました。

詳細と抽象の両方を踏まえて、改めて各種ロックについて理解を深められたような気持ち（お気持ち）。
https://discord.com/channels/508093437187457045/882639711447961710/948929919386275930

条件変数

  • Cと見比べたらたぶんわかった！
  • 出力するメッセージを工夫するとさらにわかりやすい！

https://discord.com/channels/508093437187457045/882639711447961710/948916679331692565

use std::sync::{Arc, Mutex, Condvar};
use std::thread;

fn child(id: u64, p: Arc<(Mutex<u64>, Condvar)>) {
  let &(ref lock, ref cvar) = &*p;

  let mut started = lock.lock().unwrap();

  while *started < 5 {
    println!("child {} standby, started = {}", id, started);
    started = cvar.wait(started).unwrap();
    println!("child {} notififed, started = {}", id, started);
  }

  println!("child {}", id);
}

fn parent(p: Arc<(Mutex<u64>, Condvar)>) {
  let &(ref lock, ref cvar) = &*p;

  let mut started = lock.lock().unwrap();
  *started += 1;
  cvar.notify_all();

  println!("parent");
}

fn main() {
  let pair0 = Arc::new((Mutex::new(0), Condvar::new()));
  let pair1 = pair0.clone();
  let pair2 = pair0.clone();
  let pair3 = pair0.clone();
  let pair4 = pair0.clone();
  let pair5 = pair0.clone();
  let pair6 = pair0.clone();

  let c0 = thread::spawn(move || { child(0, pair0) });
  let c1 = thread::spawn(move || { child(1, pair1) });

  let p = thread::spawn(move || { parent(pair2) });
  let p1 = thread::spawn(move || { parent(pair3) });
  let p2 = thread::spawn(move || { parent(pair4) });
  let p3 = thread::spawn(move || { parent(pair5) });
  let p4 = thread::spawn(move || { parent(pair6) });

  c0.join().unwrap();
  c1.join().unwrap();

  p.join().unwrap();
  p1.join().unwrap();
  p2.join().unwrap();
  p3.join().unwrap();
  p4.join().unwrap();
}

RWロック

わかった！

バリア同期

これもたぶんいけた！

↓↓ 以降のスレッドによろしく頼んます！

mohiramohira

2022-03-16(木) 20:00-22:00

実績

p.95 セマフォから p.97まで

Discord開始リンク

https://discord.com/channels/508093437187457045/882639711447961710/953974650508038144

次はどこから？

次回 p.98 例3-18

MEMO

最近どう？

鼻から悪魔: 未定義と未規定; Undefined と Unspecified の違い

https://discord.com/channels/508093437187457045/882639711447961710/954003913214943272

コンピュータプログラミングにおいて、未定義動作（英: undefined behavior, UB）とは、コンピュータ言語が準拠する言語仕様において動作が予測できないと規定されたプログラムを実行した結果のことである。これに対して、言語仕様が動作結果を規定せず、プラットフォーム上の別のコンポーネントのドキュメント（ABIやトランスレータドキュメントなど）が処理系の実装を規定する動作のことを未規定動作（英: Unspecified behavior）と呼ぶ。

誤植: PR送ろう

セマフォ

ミューテックスはロックを獲得できるプロセスは最大で 1 つであったが、セマフォ（semaphore） では最大 N プロセスまで同時にロックを獲得できる。ただしここで N はプログラム実行前に自由 に決定できる値である。すなわち、セマフォはミューテックスをより一般化したもの、もしくは ミューテックスはセマフォの特殊なバージョンと考えることができる。

「型」の世界が広がった話

!Send とか！

rcはSendしてはならぬ

↓↓ 以降のスレッドによろしく頼んます！

mohiramohira

2022-03-31(木) 20:00-22:30

実績

p.98 例3-18 から p.102 パン屋のアルゴリズム

Discord開始リンク

https://discord.com/channels/508093437187457045/882639711447961710/959045685016154153

次はどこから？

次回: パン屋のアルゴリズム(2回目)

  • p.104の説明のところから
  • お絵かきと、用語の対応付をしっかりしたほうが良い
  • iPad用意しておく

おうちインターネットが不安定で体験が悪かった！

すまん！

MEMO

最近どう？

  • 工具の異音から異常検知
  • k8s勉強しよう(N年ぶりM回目)
  • エイプリルパラドックス！
  • ヤクルト1000 https://www.yakult.co.jp/yakult1000/
  • 勉強会は別腹
  • 『異端の数ゼロ』

Producer/Comsuerモデル(パターン)

生産者の能力が消費者よりも高く、チャネルのキューのサイズに制限が ない場合、キューのサイズが膨れ上がりメモリを限界まで消費していずれプログラムが停止してし まう。しかし、キューのサイズに制限を設けることでそのような事故を防ぐことができる。
満杯を超える生産ができないって感じ

チャネルの高速化手法としてはバルクデータ転送
複数のデータをバルク（一括）でエンキューすると転送スループットの向上が見込める
おぼんにジョッキを載せたほうがはやいやつ

Unixのパイプも、メモリのページサイズの4KB単位で送受してますね。

LL/SC

  • LL/SC最強説がある

LL/SCでは、ABA問題が起きないのです。
https://ja.wikipedia.org/wiki/ABA問題

https://discord.com/channels/508093437187457045/882639711447961710/943156931672023081

LL 〜〜〜〜〜〜〜 SC

　　　　　↑ 
　　この区間で書き込みがあるとSCが失敗する

パン屋のアルゴリズム

実装も含めて(実装があったから？)難しかった！

けど、大事なところは、ハードウェアのアトミック命令を使わずに同期処理するところ！

アウトオブオーダーとメモリフェンス

このように、アウトオブオーダ実行は IPS の向上に寄与するが、いくつか別の問題も引き起 こす。アウトオブオーダ実行に関する諸問題から保護するための処理がメモリバリア（memory barrier）であり、本節ではそのメモリバリアについて議論する。メモリバリアはメモリフェンス （memory fence）とも呼ばれ、Arm ではメモリバリア、Intel ではメモリフェンスと呼ばれる。

mohiramohira

2022-04-14(木) 20:00-22:10

実績

p.102 パン屋のアルゴリズム から: p.107 4.1 デッドロック の手前まで

Discord開始リンク

https://discord.com/channels/508093437187457045/882639711447961710/964119145849450498

次はどこから？

  • p.107 4.1 デッドロックから

過去一番議論が起きた気がする

そんな気がする！ なぜ！？ かはあんまりわからん。でもそれでいい。

MEMO

最近どう？

  • COCOAがうごいてた！
  • オンライン英会話とインターネット環境とモロッコの先鋭
  • いろんな植物を見たい話
  • ゲーミングモニタ144Hz
  • 書籍の断捨離はできない。そしてそれは伏線だった。スパゲッティデッドロック。

アトミック命令を使わずに、同期処理を実現すると性能が悪い話

一連の投稿を詠んでちょ。

https://discord.com/channels/508093437187457045/882639711447961710/964125337766219786

ハードウェアを神聖視しないという発見

なんか特別視していた

たとえ話

「待ちが発生する以上、ハードワイヤードしても速くならない。」という話を例えると、「F1カーであれ軽トラックであれ、渋滞している道を進む速度は同じになるよね。」という話です。

アトミック命令と「アルゴリズム的な同期」の速度の桁が違うというのは、イメージとしては「（アトミック命令は）路肩走行してよいという特権を持ってる」みたいにな感じですかね。

https://discord.com/channels/508093437187457045/882639711447961710/964130975363788831

Q. マクロで書くのと、関数で書くのとで、最適化をしなくなるのガチで？ ソースは？

https://discord.com/channels/508093437187457045/882639711447961710/964134757120245771


> 関数にするとコンパイラによる最適化が行われてしまう可能性がある

「マクロで書く => 最適化が起きない」と読めなくもないので、それってどうなの？ っていう感じがある
(マクロを使いたくなくなる方向になっちゃいそう？)

Q1. まず、本当なのか？ 本当であればソースは？
Q2. 本当だとして、それって「常に」なのか、「条件付き」なのか？ そして、その条件とはなにか？
Q3. 「最適化」っていうけれど、具体的にどういう最適化なのか？
Q4. Rustでマクロのコンパイルってどういう方式？
コンパイルの流れによっては、いろいろ変わってきそう。


Cの場合
・マクロで文字列置換
・そのあとでの、ソースコードでコンパイルされる ← 結局マクロも最適化の影響を受けるやん？

さて、Rustの場合は？


Q5. fenceが理由で何か、おかしな(？)ことがおきていたかもしれない
たとえば、関数のときだけ、fenceがおかしくなるという、バグがあるのかもしれないという説。

アトミック処理の性質を振り返る

定義：アトミック処理の性質

ある処理がアトミックである⇒その処理の途中状態はシステム的に観測することができず、 かつ、もしその処理が失敗した場合は完全に処理前の状態に復元される。

哲学者が気になりすぎて内容が頭に入ってこない話

  • スパゲッティはフォーク1つでいけるやろ
  • アルゴリズムには従うんかーい
  • 昨今の衛生面への考慮不足
mohiramohira

2022-04-28(木) 20:00-22:00

実績

p.107 4.1 デッドロック 〜 p.116 銀行家のアルゴリズムの手前

Discord開始リンク

https://discord.com/channels/508093437187457045/882639711447961710/969193143008374864

次はどこから？

  • p.116 4.3 銀行家のアルゴリズムから

MEMO

最近どう？

  • エラー処理
    • エラー処理ってどこから学ぶと良さそう？
    • try/catch OR Result/Either どっち使う？
  • コーヒー、 カフェオレ、 カフェイン切れ
  • Ubuntu -> Windows
  • 仕事漬けな2Weeks、自分は何をエンジンにしているか？ 「役割がある」という重要性
  • The経済学 → リアル経済学へ。FXのビギナーズラック

デッドロックとライブロックと飢餓の話

  • わりと理解しやすかった説！

振り返り

  • デッドロックとライブロックの厳密な定義があってよかった話
  • ステートマシンって便利ですね。
  • 日本語がややこしかったもしれない
  • 「ライブロック」というフレーズは現場であまりつかわないという話を聴けてよかった！
  • ライブロックは発見しづらそうという説
    • ライブロックは、パフォーマンス低下というかたちでは気づけそう？ でも、出会えなくない？
    • ちょっと早くなったり遅くなったりとかの現象できづけるか？ (無理じゃね？w
  • 猫がミルクの皿を奪い合うやつ。
  • 飢える哲学者と、哲学者を救うアルゴリズム

飢餓の元ネタは、マジで「腹ペコ」

スタベーションとは「飢餓」であり、この用語も「食事する哲学者の問題」のアナロジーに付随したジョークが起源である

https://ja.wikipedia.org/wiki/食事する哲学者の問題

キーワードかも

  • 資源割付グラフ
  • 資源管理表

コフマン条件、それはデッドロックの必要十分条件。4つからなるよ

https://scrapbox.io/yux3/Coffman条件_Coffman_conditions

mohiramohira

2022/05/26(木) 20:00-22:00

実績

  • p.116 4.3 銀行家のアルゴリズム

Discord開始リンク

次はどこから？

  • p.122 4.4 再帰ロック

MEMO

  • 1ヶ月ぶりの開催(前回はお休みだった)

最近どう？

  • メダロットS
  • シンセサイザーとか音声合成
  • 富士山の近くの辺鄙なところにある温泉宿らしき場所の温泉的なものの効用の高さ！
  • プログラミング好きだけど、何が好きなのだろう？
  • RISC-Vがpdf2枚という完全理解チャンス

写経しなかった(=実験をやらなかった)ことによる、写経の効果が改めてわかった

要はバランス

実務でなぜ、ライブロックを見ないのか。説。

  • ①ライブロックが起こる設計になってしまうこと自体が稀説
  • ②ライブロックは確率的にはいずれ解消されるので、観測されない説。（デッドロックは、永遠に続くので、観測されやすい。）
  • ③ライブロックが起こることに気づいても、ライブロックという語が出てこないから、ライブロックとは認知されない説。

変数とかindexとか、用語がマジでややこしかった！

  • たとえ話だったり、アルゴリズム上の役割する
  • 銀行のたとえ話でいうと、「複数種のリソース」の場合がマジでわからなくなる(勘違いする)
    • 「麦、米、水」みたいなのよかったし
    • 「複数種の通貨を借りたい」というケースもよかった(実際にあるし)

Q. 銀行家のアルゴリズムが適用できるシーンって少ない？

Q. 銀行家のアルゴリズムに必要な情報が分かることって多い? or 少ない？

組み込み(自動車とか)でいえば、リソースが既知であることは多いが、少なくとも銀行家のアルゴリズムの性能では、時間的な要求を満たせないだろう

→ つまり、理論上適用できるが、実際には使われない。

Q. 銀行家のアルゴリズムは、ライブロックを見逃すのでは？

https://discord.com/channels/508093437187457045/882639711447961710/979369184121196625

銀行家のアルゴリズムは、小さいケースで手計算(リソース割付表みたいなの書く？)をするともっと楽に理解できたかも？

あるいは、一般化されたカタチでプログラミングでの実装の難しさを理解できる話

Safe(安全)は専門用語だった！

Safe and unsafe states
https://en.wikipedia.org/wiki/Banker's_algorithm#Safe_and_unsafe_states
https://ja.wikipedia.org/wiki/銀行家のアルゴリズム

mohiramohira

2022/06/09(木) 20:00-22:00

実績

  • p.122 4.4 再帰ロック
  • 4.5 擬似覚醒
  • 4.6 シグナル

Discord開始リンク

次はどこから？

  • 次回: p.130のRustでのシグナル用スレッドの話から

MEMO

最近どう？

  • 線形代数やってたら数学がわかってきた話
  • AWSのいろんなサービス触って楽しい。特にDB系。
  • 悪魔学
  • 時間の比較社会学
  • シェイクスピアを読んでいこう
  • 組み込みの自動テスト

組み込みの自動テストは難しいけど、進んでいる話

https://discord.com/channels/508093437187457045/882639711447961710/984426296153112606
軽いものだとエミュレータで実行とか、実機だとJenkinsでローカルマシンを操作してアップデート実行+治具で電源ON/OFFからテストの実行をするとか

再帰ロック

  • あるプロセスが同じリソースに対して再度ロックをすること
  • デッドロックになる場合もあるし、そうならない(再入可能な)場合もある
// 再帰ロックはつまりこういう感じ
lock();
lock();

「再入可能」なミューテックス

p.125
単純なミューテックスの実 装では、このような呼び出しを行うとデッドロックになってしまうが、再入可能ミューテックスで は処理が続行する。

(おーひらの解釈)
単純なMutexだと、同じリソースに対してロックを獲得しようとすると、(誰がロックを獲得していようが)解放を待つことになる。
けど、再入可能にした場合、自分だからセーフ！ みたいな感じになる！

擬似覚醒、望まれない挙動ってこと

条件変数は、「プロセスがある条件を満たさない限りは、実行したくない(=待機していてほしい)」という話なのに、(なんやしらんけど)疑似覚醒しちゃう場合があるらしい(条件が満たされていないのに実行状態に移ってしまう)。

なので、いろいろ防ぎ方がある。

ほんで、じゃあ、疑似覚醒ってどういうときに起こるの？ ってのを調べていく。代表例がシグナル

シグナルと並行処理は相性が悪い(というか、気をつけないといけない)

ロックをするようなプログラムで、割り込まれてロックをしたりすると、そっりゃあ危ないよね的な発想。

一般的に、シグナルとマルチスレッド は相性が悪いとよく言われている。その理由は、どのタイミングでシグナルハンドラが呼び出され るかがわからないからである。

p.128 シグナルハンドラを用いたときにデッドロックとなる典型例

OKな場合
main: lock
main: unlock
↓(シグナルがとんできて)
handler: lock
handler: unlock

デッドロックな場合
main: lock
↓(シグナルがとんできて)
handler: lock
========= デッドロック！！！
main: unlock
handler: unlock

SIGUSR1とSIGUSR2は自由に使うシグナル

UNIX は多くのシグナルを定義しています（4.3BSD と SVR で 31）。 そのほとんどは特定の目的のために確保されていますが、 SIGUSR1 と SIGUSR2 の２つは、アプリケーションで自由に使えます。

シグナルをブロックする is 何？

めっちゃ良い資料 → https://qiita.com/Kernel_OGSun/items/e96cef5487e25517a576#6-シグナルブロック

(おーひらのイメージ)
ブロックしたからこそ、特定のスレッドにのみシグナルを飛ばすことができる。
ブロックすると、シグナルが、どこかに、たまっていく。でも、シグナルが消えるわけじゃない！
だから、なんつーか、シグナルをコントロール可能っていうか、シグナルに割り込まれて、いきなり処理を変えられちゃう、ことを防げる！

シグナルは溜まっていく。だから、あとでどうこうできる。

mohiramohira

2022/06/23(木) 20:00-22:15

実績

  • p.130のRustでのシグナル用スレッドの話から
  • p.131 4.7 メモリバリア

Discord開始リンク

次はどこから？

  • 次回: 5章 非同期プログラミング
    • 七夕なので、最初の自己紹介で願い事を言うコーナーを設ける(覚えてたら)

MEMO

https://discord.com/channels/508093437187457045/882639711447961710/989486598670385222

最近どう？

  • 箇条書きよりも、文章な気分(N回目)
  • さすがに冷房つけようぜな季節
  • AWSのDB系サービスを結構楽しんでいる話
  • エアコンをオーバーホールする季節(？)
  • 3ヶ月ぶりに参加！ ← これってとても良いことだと思う！
  • 英語の勉強を始めた話。無料体験から本契約にうつるでしょう。
  • 暗号通貨とFX ← そう言えば、暗号通貨の話が気になっています。

ネット環境悪めでも、画面共有なしなら結構いける

とはいえ、画面共有があったほうが良いのは間違いなさそう。お絵かきもできるし、今注目していることもわかるし、何よりおーひらの不安が減るから。

VSCodeLiveShareはかなりいい感じ

  • ブラウザからでもいける！(VSCodeなくてもいける)
  • 認証なしでもいける
  • 認証すれば、編集権限を付与できる

メモリバリア と バリア同期 は別モノ！

  • 「バリア」という言葉がややこしい？
  • バリア同期 → みんながそろうまで待ちます！
  • メモリバリア → メモリアクセスの順序を保証します！ 命令の実行順序を勝手に変えたりしないように保証します！

(機械語の)dmb命令は「Data Memory Barrier」の略！

DMB（データメモリバリア）命令
DMB! データ！ メモリ！ バリア！

メモリバリア命令の解釈は要復習！

まだ、わかってねぇ！

ヒント → https://discord.com/channels/508093437187457045/882639711447961710/989501293309620254

「バリアする」って語彙が全然一瞬で理解できない件

語彙、大事

Q. このへんのバリア命令を(人間が)考えて書くの大変そう...。実際、人間が書くの？

メモリバリア命令は、普通に書きます。
ただ、コーディング中にその場その場で考えるのではなく、設計（仕様策定）時点で「ここにこれ要るよなあ」と考えておくイメージ
https://discord.com/channels/508093437187457045/882639711447961710/989503829965938798

https://discord.com/channels/508093437187457045/882639711447961710/989507433430917181

単語帳

:word メモリオーダリング

:word オーダリング

:word リオーダリング

CPUアーキテクチャごとのメモリオーダリングの表の解釈

W→Wは機械語としてこうなっている

write1
write


で、

AArch64の場合は、リオーダリングされる。←左上のマスの✔
x86-64だと、リオーダリングされない (機械語の順序どおりに実行される)

https://discord.com/channels/508093437187457045/882639711447961710/989517247854829578

p.135 Pthreadsで起きていた問題をRustでは解決しているという話

https://discord.com/channels/508093437187457045/882639711447961710/989509351725211669
https://discord.com/channels/508093437187457045/882639711447961710/989511113207087124

ミューテックスをやりたいとする。
↓
pthreadsでやると、なんか問題があった。
でも、Rustだとその問題は解決できる
(ってのも、3.8.1とかで、見たという設定)

↓
その問題 is 何？ っていうと、2つあって、

  1. Ptheadsだと、保護対象データへは、ロック後でなくてもアクセスすることができちゃう！ これは危ない！人間は平気でミスるからね。 けど、Rustなら、保護対象データへは、ロック後でなければアクセスできない。
  2. Pthreadsだと、ロックの解放を自分でやらんと行けなかった。しかし、Rustならロックの解放が自動で行われるので、嬉しいね。

↓
で、Rustが 1) と 2)をどうやって実現しているかは、(たぶん前には説明していなかったので)、ここで、説明するよ

↓
具体的には、、スピンロックを題材にして、コードでみていくよ
↓
MEMO: むずかったので(というか、理解を一旦棚上げにしたので) Rustの機能と合わせて、またいつか帰ってこよう(ということにした)！

大事にしているものはなんですか？ という話

命令や作りたいアーキテクチャなのかに問わず、「それなんのために作っているか」のレベルで考えていこうね！ という話という解釈。

文字にするとふつーっぽく見えるけど、とっても大事だと思う。

PR

さて → されて

PRだした → https://github.com/oreilly-japan/conc_ytakano/pull/79

4.6のコードが動かん

https://github.com/oreilly-japan/conc_ytakano/blob/main/chap4/4.6/ch4_6_signal_rust/src/main.rs

なおした。

// MEMO: consts::signal 追加
use signal_hook::{iterator::Signals, consts::signal::SIGUSR1}; // <1>
use std::{error::Error, process, thread, time::Duration};

// https://crates.io/crates/signal-hook

fn main() -> Result<(), Box<dyn Error>> {
    // プロセスIDを表示
    println!("pid: {}", process::id());

    // MEMO: mutの追加
    let mut signals = Signals::new(&[SIGUSR1])?; // <2>
    thread::spawn(move || {
        // シグナルを受信
        for sig in signals.forever() { // <3>
            println!("received signal: {:?}", sig);
        }
    });

    // 10秒スリープ
    thread::sleep(Duration::from_secs(10));
    Ok(())
}

[package]
name = "concurrency-programming-book-rust"
version = "0.1.0"
edition = "2018"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
signal-hook = "0.3" ← 追加！
mohiramohira

2022/07/21(木) 20:00-22:15

実績

  • p.139 5章 非同期プログラミング から

Discord開始リンク

次はどこから？

  • 次回: p.145 「epollでは〜」

MEMO

最近どう？

  • 体調崩したりもどったり
  • 静的解析とSMTソルバー
  • 独学大全
  • https://github.com/danmayer/coverband
    • Coverbandで、あんまり使っていないコードを観測するの大事っぽいし、昔はよく使ったけど今はそうでもないとかありそう

epoll, kqueue, select は イベント監視するぜ軍団

個別にみるとよくわからんかったけど、ファイルディスクリプタ監視パーソンと考えると捉えやすい気がする

イベント監視は、つまるところ、ファイルディスクリプタ監視なのだ！

ファイルディスクリプタがあるOS(たとえばUNIX)の話であることに注意！

ファイルディスクリプタがないOSでは、別のやり方でイベント監視をしているでしょうね！ あとは
反例としては、車とか。

エッジトリガ、レベルトリガ

  • エッジトリガ → イベントが起きた瞬間に一度だけ通知が来る。
  • レベルトリガ → イベントによって変化した状態が維持されている限り、通知が来続ける。

エッジは 「ｸﾝｯ」の感じで、レベルは水平ってかんじ。たぶん。電圧とか由来！
野球のレベルスイングのレベルと多分同じ。

https://mackey-lab.hatenablog.com/entry/2015/04/22/005214

これはわかりやすいたとえ！

メールが着いた瞬間に、一度だけ通知音が鳴るのが、エッジトリガ。
相手が諦めるか自分が出るまで、電話が鳴り続けるのが、レベルトリガ。

大事だと思うこと

非同期とか並行とかいう文脈においては「順に」とか「順番」とか「待つ」とか「いつ？」とかはすげー大事。

かなりの具体性を考えないとあかん！

雑に、「イベントが起きた順で処理される」とかだと、実は結構曖昧なのでは！
epoll_waitの仕様にもよる！

「一般の話」か「特化の話」かを区別しようぜ！

ということです！(？)

Unixの話

https://discord.com/channels/508093437187457045/882639711447961710/999668725269667850
Unixは最初「全てがファイル！」という設計思想で作り始めたけど、Socketという例外（ファイルでないもの）が出て来たので、「全てはファイルディスクリプタ」ということになった。後年、Unixの設計者が新たに作ったPlan9というOSでは、ちゃんと「全てがファイル！」を達成した。
（なお、細かいところで間違いがあるかも。）

肉じゃがとカレーが同じ話

ぎりぎりまで料理を決めないまま調理する。
インタフェースに対するプログラミングだ...!!!!

全てがファイルだと、少ないシステムコール（主になるのはopen, read, write, close）だけで全てを操作できるので、使う人（アプリケーション・プログラ マという意味で、エンドユーザという意味ではない。）に易しいのです。
https://discord.com/channels/508093437187457045/882639711447961710/999670215807873074

ファイルとは？

例えば、Linuxでは、/dev/acpi/BAT0だか/proc/acpi/BAT0だかでバッテリー残量を読めたりします
https://discord.com/channels/508093437187457045/882639711447961710/999672515347628132

ところで

「組み込み」の世界における「OS」とかOS的な話を聞くの、めっっちゃおもろそう

mohiramohira

2022/08/04(木) 20:15-22:00

実績

  • p.145 「epollでは〜」

Discord開始リンク

次はどこから？

  • 次回: 5.2.2 スケジューリングから

MEMO

最近どう？

イテレータ、ジェネレータ、コルーチンあたりの用語を整理したいね！

このへん結構あいまいじゃない？

「ジェネレーターの実装のための、コルーチン」っていうのが発見。
無限リストとかに、「中断と再開」があることに、いま気づいた！

https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Generator

// 「ジェネレーター」で「無限イテレータ」を実装した例
function* infinite() {
    let index = 0;

    while (true) {
        yield index++;
    }
}

const generator = infinite(); // "Generator { }"

console.log(generator.next().value); // 0
console.log(generator.next().value); // 1
console.log(generator.next().value); // 2

対称コルーチン と 非対称コルーチン

  • 対称コルーチンは、人間による管理がヤバそう。ってか無理じゃね？ バグだらけじゃね？ あとは、フロー図にも起こしづらいでしょ。
  • 非対称コルーチンは、無限リストとかのやつ。わりと使いそう。

LexerとParserでコルーチン使って、交互に仕事するという発想賢い！

さっきのページでちらっと見えた「lexerとparserをコルーチンで交互に実行する」っていうの賢い。
https://discord.com/channels/508093437187457045/882639711447961710/1004722684262887444

lexer の出力を parser が即座に消費できるので、バッファに積んでおく量を抑えられ、さらに parser の後続処理にわたすのも早い段階からできるというのが利点。
当時は、とにかく省リソースが良かったはず。
https://discord.com/channels/508093437187457045/882639711447961710/1004723888913141831

「継続」というすごい概念

https://www.lambdanote.com/products/nmonthly-vol-3-no-1-2021

http://www.shido.info/lisp/scheme_cc.html

継続の利用例として代表的なのは、強力な制御機構の実現です。なぜかと言うと、 「例外」「コルーチン」「バックトラック」など、いろいろな制御機構が継続で実装で きてしまうからです。

コルーチンは並行処理の一つの手段で、継続は計算過程というものを抽象化する手段という違いかと。後者の方がより広い対象で、並行処理はその応用に過ぎない、と。
https://discord.com/channels/508093437187457045/882639711447961710/1004746107374551090

ふつうのやつらの上を行け！

http://practical-scheme.net/trans/beating-the-averages-j.html

コルーチンがある言語とない言語

  • ある: Pythonとか
  • ない: Rust ← 新しい言語だから？
  • 最近入った: C++20 ← 新しい言語だからとかカンケー内科？

イテレータとかジェネレーターとかをPythonで考えてみると良いと思う。

PEPとかみるといろいろ分かりそう。

コンパイラの本！

ドラゴンブック、タイガーブック、『言語実装パターン』が3大書だと思います。
和書では、中田先生の『コンパイラの構成と最適化』が至高。

コルーチンの説明はこの記事の図解がよさそう

https://zenn.dev/339/articles/6832decc5ef1b4a0821b

mohiramohira

2022/08/18(木) 20:15-22:00

実績

  • 5.2.2 スケジューリングから

Discord開始リンク

次はどこから？

  • 5.3.2 IO多重化とasync/await から

MEMO

最近どう？

  • 統計学でのダニングクルーガー効果
  • マイナポイント

文句: 図と実装がズレるの辛い！

そろえてほしい〜

Executor-Task-Wakerモデル は async/await の話じゃなくて、あくまで、コルーチンを使ったスケジューリングを実現するための実装アイデアって感じ。

たぶん、わかった！

  • どのチャネルが何に対応しているかを見ると良い
  • 鶏卵の一発目が、Spanwerが担当していることが分かればいける
  • 何より、スケジューリング感(≒コルーチンの操作(.__next__()を人間が書かなくても、Task単位で処理が勝手に進む)のが大事！

async/await はキーワードつけるだけで便利だが、非同期処理と動機処理の使い分けがますますわからなくなっちゃうのでは？

  • 非同期処理は計測や解析、予測がしづらい
  • 最適化の緒がつかめなくなる。
  • なんでもかんでも非同期にすれば良いというわけでもなさそうだし。
  • cf) Rust1.63の「キーワードジェネリクス」
    • 見かけは楽になるかもしれないけど、同期的とか非同期の使い分け、より雑になっていく危険性！

IO多重化とは？

なんかいっぱいファイルディスクリプタをあれこれできるやつ的な。

IOが多重化されていない状態をイメージすると考えやすいかも。

Future型のイメージは、ほんとにFutureな感じだった！

Future は、将来のいつかの時点で値が決まる（あるいは一定の処理が終了する）ことを示したデータ型

非決定的な感じの方が、非同期っぽさを捉えている気がする。

暗黙的=>{楽っぽい, 罠にハマりそう} だし、 明示的=>{めんどくさい, 細かく制御できる} っていう雰囲気。

Future 型を用いた記述方法には明示的に記述する方法と、暗黙的に記述する方法がある。暗黙 的に記述する場合、 Future 型は一般的な型と全く同じように記述されるが、明示的に記述する場 合は Future 型への操作はプログラマが記述しなければならない。

  • キーワードにすることで、いつものめんどくさい処理を書かなくて済む感じ-
  • キーワードが禁止されたらつらい世界観を想像するとわかりやすい説がある

明示的、暗黙的に記述するというのは、参照を考えてみるとわかりやすい。例えば、 &u32 型の変数 a の値を参照するためには、Rust では *a と明示的に参照外しをしなければならないが、 a と書く だけでコンパイラが自動的に参照外しを行うような言語設計も考えられる

なるほど〜〜〜

await()というAPIはよくあるらしい

Future が await() を持っているのは、いろんな言語のライブラリでよく目にするかな。
https://discord.com/channels/508093437187457045/882639711447961710/1009802126093979708

Rustのawaitはキーワードだった！

Future(という考え方)はコルーチンによって実装されるらしい

。一般的に Future はコルーチンによって実装 され、これにより「中断、再開可能な関数」から「将来に決定される値を表現したもの」へと意味 的な転換が行われる。

Rustにおけるasync/awaitはこれをみるとよさそう(ちょっと古いかもだけど)

https://async-book-ja.netlify.app/01_getting_started/04_async_await_primer.html

mohiramohira

2022/09/15(木) 20:05-22:45

実績

  • 5.3.2 IO多重化とasync/await から

Discord開始リンク

次はどこから？

  • 5.3.2.2 各種Futureの実装

MEMO

1周年！

最近どう？

  • ひさびさ！

コレ的な図。

ペアリーディングめっちゃよかった！

  • nice!!
  • thanks @philomgi

とっても大事なこと: めっちゃ勉強会のPowerが発揮された！

  • みんな、質問するといいぞ！ 意見するといいぞ！
  • 質問した人や意見した人は、その人が思っている以上に全体に貢献していることに気づくと最高！ ← ホンマに！

文句: 図と実装がズレるの辛い！

そろえてほしい〜

あと、モデルの実装と乖離がぴゃー

そろえて！！！

本の説明の仕方が怪しい説！

  • 触れられているから重要かと思いきやそうでもなかったりする
  • 実はRustじゃなくても良い説がある

難しい！

乙

難しいポイントは...

  • 登場人物が多い
  • 図解とコードが対応していないことがある(モデルの実装と乖離はあるけど、ぴゃー！ って感じ
  • 全体が見えにくい
  • (仕組みに注目したいけどRust面できつい)
  • もう少し小さなmain関数が複数あれば良さそう

今日はまとめらんねーぜ！

けど、謎の絵だけ置いておく。

ちなみに軽量スレッドとかの表記ゆれ

ちなみに、定義はこんな感じですかね。
・軽量スレッド（ファイバー、グリーンスレッドetc）：スケジューリングとコンテキストの切り替えがユーザー空間で行われるマルチコンテキストシステム内のコンテキスト。
・スレッド：互いにメモリ空間を共有するマルチコンテキストシステム内のコンテキスト。
・プロセス：互いにメモリ空間が分離されたマルチコンテキストシステム内のコンテキスト。
https://discord.com/channels/508093437187457045/882639711447961710/1019967619706650674

mohiramohira

2022/10/13(木) 20:10-22:22

実績

  • 5.4 非同期ライブラリ
  • 「5.3.2.2 各種Futureの実装」はテンション上がらなかったのでSKIP! 攻めのSKIP!

Discord開始リンク

次はどこから？

  • p. 172の最後の方から

MEMO

最近

  • ライブチケット当選！
  • オンライン英語学習継続中(1月〜) → OFFLINE英会話も！
  • 夜行バス実は快適説 vs 夜行バスしんどい説
  • スポーツのナイター観戦のあとは、実は夜行バスがらくかもしれない話
  • カメ環境改善！
  • カメもカメで工夫している話
  • エアレーション: 水槽内の水に酸素を送る装置です。気泡が登る様子から「ぶくぶく」と呼ばれることもあります。水面を揺らして酸素を取り込みやすくする効果があり、熱帯魚やエビなどの生き物の酸欠を防ぎ活性化させます。
  • リモートだとなんだかんだ働きすぎちゃう問題

攻めのSKIP! 大成功！

実際、テンション上がらなかったからね。

本の内容から派生した話をすると楽しい

「本の内容を無視している」というとネガティブっぽいけど、そうじゃない。
派生なり脱線をするということは「興味があることをちゃんと考える」ってことだから！ 楽しいね！

「無視している」というか、本の内容をトリガーに別のテーマへ発想を飛ばしてそっちの話題が盛り上がった = 複数のテーマをつなげることができた
的な

意見を言ったほうが面白いんだよね！

感想ではなく意見を言うためには、「私は◯◯は〜だと思う」といった何らかの主張を含む必要があるはずで、
主張を含めるためには「なぜ...ではなく〜なのか」等といった何らかの考察や分析が必要なはずなので、意見を作るのは大変、的なアレ

Rustの非同期ライブラリ tokio

今調べたら、TOKIOってフランス語とかドイツ語での東京って意味らしいです

へ〜

Discordのスレッドを活用するといいかもしれない

要練習。

マルチスレッドやマルチスレッドプログラミングってどう？

ウェブアプリを書いてるだけだと、自分のロジックでマルチスレッドを使うことはないですね。
データ処理とかに使うプログラムとか、GUIプログラムだと、ちょいちょい使う印象。
https://discord.com/channels/508093437187457045/882639711447961710/1030083761842425856

Cでソース書くことありますけど確かにCだとほいほいスレッド立てることはないですね。Cのスレッドは重いので、一応実行コストを気にしてることになるのか 🤔

非同期プログラミングの恩恵は頻繁に受けているけれど、仕組そのものを作ったりいじったりすることはほとんどなくて、その恩恵に与るぐらいになりがち、なアレ（自己紹介）

高並列性と言えば、Erlang/OTP のアクターばんざい

純粋な計算パフォーマンス向上のための非同期化では、OSスレッドを使うことはもうないんじゃないかと思います。

逆に言うと、昔はOSスレッドしかなかった？(ユーザーランドのスレッド技術が進化したってこと?)

Webサーバとかだと、むしろサービスそのものよりも、OSスレッドを作るコストの方が高いとかもある。

Goroutineは、OSのスレッドと比べてコストが安い

コストの話で言えば、Goroutineはスレッドとは比較にならないくらいコストが低いはず。（1000倍とかのオーダー？）

「スレッドプール」と「スレッドプーリング」は似て非なる言葉かもしれない(要検証)

スレッドプーリングとは、複数の実行スレッドを管理し、処理を各スレッドに分散させるためのテクニックである。場合によっては、同時実行制御などの機能も、スレッドプーリングの一部と考えられる。スレッドプーリングは、以下の処理を作業を行うのに適した方法である。

https://codezine.jp/article/detail/27

Q. スレッドプールは"先に"(≒タスクが来る前に)スレッドを作っておくのはわかるが、これの何が嬉しいの？

https://discord.com/channels/508093437187457045/882639711447961710/1030090077340172329

注文が来てから作るではなく、先に作っておいて注文を待つ。たこ焼き屋さんとかでも同じ。

処理が集中する = 実際に忙しくなるより先に、手が空いている内に面倒な処理 = スレッド生成は先に済ませておけば、「忙しい最中に面倒な仕事をする」を回避できる的なイメージ

よく考えたら、スレッドプールは飲食店よりも、駅前で待ってるタクシーの方が例えとして適当かも。

OSスレッドのコストが高い を もっとちゃんというと OSスレッドの生成や破棄はコストが高い

破棄のコストってイメージしにくいよね(？)

一度作ってしまうと捨てるのが大変のは、スレッドも人間が使う物も同じ。

スレッドプールの"ノリ"

スレッドの作成・破棄のコストが安くないので、先に作っておく。
だったけれど、加えて、「スレッドを処理要求に応じて無制限に作るのは却ってスレッド切替え のコストが大きくなりすぎたりして効率が悪いので、スレッド数の上限を設ける」ことになって、スレッド数の管理をすると複雑になるので最初から作っておいた方が楽になったりするという効用もある。
ような印象がある。

スレッドを要求に応じて無制限に作るのは却って切替えコストが大きくなりすぎたりして効率が悪いので、

「client からの request に応じて」という意味か！
スレッドプールの嬉しさを説明してくれていた！(おーひらが誤解した！
「予め」つくるなら、「じゃあ何個だよ？」「何個が効率言い訳？」っていう話になる

↓

だから、自然とスレッド数の上限も決められていくよね

ちなみに最近はセキュリティのために、消したスレッドが使ってたメモリは0クリアしないといけない。

たとえば、ブラウザが使っていたメモリには、パスワードとか入っていたりする。
なので、メモリ解放した後に、盗まれる可能性がある。

秘匿情報を扱う系のプロセス(スレッド)ならたいてい当てはまりそうな話題。

最近
昔、Windows2.0とかならやってなかったかもw

ともかく、現代のブラウザだったら、まず実装されている話。

async 中にブロッキングを行うようなコードを記述すると、 実行速度の劣化やデッドロックが起きてしまう。

実は、想像ツイてない件！

非同期 x ブロッキング というアイデアは危険という話

これまじで重要レビュー項目だな
静的解析したほうがいいんじゃにの？
コード上は些細な違いではあるが、重大な違いである。

async 中にブロッキングを行うようなコードを記述すると、 実行速度の劣化やデッドロックが起きてしまう。

ブロッキングとかノンブロッキングがちゃんとわかってないと、ダメだぞ！？

sleepはあくまで具体例。

↑
「えw sleepなんて別に書かないんだが？ww」というのはダメだよ

言葉をちゃんと使おう

「ワーカスレッドを占有」 = 「10秒間待つ、という処理を (他の処理に譲るのではなく) 実行し続ける 」なので、他の処理に CPU を譲らないままになってしまう、みたいの。

https://discord.com/channels/508093437187457045/882639711447961710/1030096119105081415

tokioはポイントガード; 試合を支配している

「SleepしたタスクをTOKIOが避けてくれる。」というような表現がありましたが、むしろTOKIOはすべてのスケジューリングを司っているので、「TOKIOのSleep関数を使うことで、TOKIOが行っているスケジューリングを阻害しないようにしよう」というのが適切かなと思いました。（本が言わんとしていることに忠実という意味で。）

OSスレッドをブロッキングすることで、ユーザースレッドが止まっちゃうのは、ユーザースレッドはOSスレッド上で生きているから的な！

これは、many-to-one モデル。

manyユーザースレッド が 1つのOSスレッドに対応するパターン。で、OSスレッドがブロっくされたら(ex: thread::sleep的な)、そのOSスレッドに紐付ているユーザースレッドも止まるよねっていうの納得できた。

mohiramohira

2022/10/27(木) 20:15-22:15

実績

  • p. 172の最後の方から

Discord開始リンク

次はどこから？

  • p.179 6章から

MEMO

最近

図5-5. 完全理解した！ のはよかった！ ← 最初わからんけど粘ったのが偉い！

lock_sleepがロックする
lock_sleep が await したことでキューに積み直される
lock_onlyが実行キューから取り出されてロック解放待ちになる
でもロック解放にはlock_sleepがまた実行キューから取り出さ

プリエンプション(preemption)

プリエンプションは、（一定時間経つと）スケジューラ側が無理やり実行権を取り上げ（て、他のタスクに切り替える）ることです。

6章がマルチタスクなので、絶対関係してくるやん！

https://discord.com/channels/508093437187457045/882639711447961710/1035160780024320022 のやりとりみて！

非同期ライブラリを使うときは、非同期ライブラリ用の命令を使うとだいたいOK!

sleepとか、spawnとか。

仕組みは謎だが、標準ライブラリ(というか、非同期用のライブラリじゃないと)事件が起きる。パフォーマンスが落ちたり、デッドロックになったり。

5章最後の消化不良感...!!!

spawn_blocking 関数でブロッキング用のスレッドを生成し、そこでこの関数を 呼び出しているため、デッドロックに陥ることはない。

なかみがきになるぜ！！

// 実験コード

// ブロッキング関数
async fn do_block(n: u64) -> u64 {
    let ten_secs = std::time::Duration::from_secs(10);
    std::thread::sleep(ten_secs);
    n
}

// async関数
async fn do_print() {
    let sec = std::time::Duration::from_secs(1);
    for _ in 0..20 {
        tokio::time::sleep(sec).await;
        println!("wake up");
    }
}

#[tokio::main]
pub async fn main() {
    // ブロッキング関数呼び出し
    let mut v = Vec::new();
    for n in 0..32 {
        let t = tokio::spawn(do_block(n)); // <1>
        v.push(t);
    }

    // async関数呼び出し。
    let p = tokio::spawn(do_print()); // <2>

    for t in v {
        let n = t.await.unwrap();
        println!("finished: {}", n);
    }

    p.await.unwrap()
}

キジの生息分布は？

そういえば、本物の野生のキジを見たいなと前々から思っているのですが、どこに居るのかわかりません。調べても、「気付かないだけで、どこにでもいる。」と書かれているだけです。

空気階段がおもしろい

半年以上続いてるムーブメント！？

mohiramohira

2022/11/10(木) 20:15-22:15

実績

  • p.179 6章から 〜 p.184 6.1.2.2 まで

Discord開始リンク

次はどこから？

  • p.179 6章から

MEMO

最近

  • インタプリタの実装おもろい
  • Next.jsのバージョンアップやWebフロントエンドの設計の思想の話
  • isomorphic というキーワードも一時期流行ったおもひで
  • 「所詮」と「所謂」、「楚蟹」と「顰蹙」とかですかね。 ＞ 境界が曖昧な漢字。
  • カメの冬眠設備 と 水槽アーキテクチャ
  • マラソン完走&目標達成！
  • 浮動小数点まわりの話

おーひら無言でも成立する話！

  • 今後も任せられる！
  • 工夫の余地もきっとあるけど、それは随時！

Q. はじめて触ったコンピュータのOSは？

  • PC-DOSとかDR-DOS
  • Windows95

知ってるけど知らない理論

  • アクターモデルとか
  • CSPとか

ジキルとハイドの話は余計だと思います！

強く思いました！

公平性は2つある話。が、むずい！

プロセスは実行されることが期待されているから生まれているはず。で、プロセスは複数作るのが普通だと思うので、それをどういう戦略で管理するかとか、どこまで保証するかは確かに重要テーマだ(いまさら！)

定義：弱い公平性
ある実行環境が弱い公平性を満たす
⇔
あるプロセスが、ある時刻以降で実行可能だが待機状態になるとき、最終的にそのプロセスは実行される。

定義：強い公平性

ある実行環境が強い公平性を満たす
⇔
あるプロセスが、ある時刻以降で、実行可能な待機状態と実行不可な待機状態の遷移を無限に繰り返すとき、最終的にそのプロセスは実行される。

(OSのプロセスの)コンテキストスイッチをコストって実際どれくらいなの？

OSのコンテキストスイッチのコストは、切替え前のタスクの

  • レジスタ数 x 「メモリにコピーするインストラクション」の実行コストと、
  • メモリ空間を切り替えるためのページテーブルの差し替え、
  • インストラクションポインタなどの待避、
  • などなど
    をして、切替後のタスクのそれを逆に使えるようにする、みたいなことをやるので、やること結構ありますね。
アプリケーション内の関数呼び出しでいうとマシン語でレジスタの待避をしたりするのをもっといろいろやる、みたいな感じ。だけど、その場合はどのレジスタを待避させれば十分なのかをプログラマが知っているので必須なものだけですませられるのに対して、汎用のタスクスイッチだと「影響がありえる」すべてのコンテキスト情報を待避させないとならないですね。
> https://discord.com/channels/508093437187457045/882639711447961710/1040261120776212540

コンテキスト(Context)とは？ 実は専門用語だったのか！

特定のタスクを実行するために固有の情報すべてが、コンテキスト情報です。レジスタの内容とか、↑に並べたような情報
https://discord.com/channels/508093437187457045/882639711447961710/1040262539428249610

Context は ◯◯屋さんによって言い方が変わったりする

  • コンテキスト = Process Control Blockと思っています
    • カーネル屋さんが使うらしい
  • task control block と呼ぶこともあるようです。
  • signalの情報
    • SIGXXXがきたよ
    • SIGYYYがきたら、何をするとか、無視しているとか(シグナルブロック)

『BSDカーネルの設計と実装―FreeBSD詳解 単行本』は名著

https://www.amazon.co.jp/dp/4756146791

  • 4.3と4.4ってやつは古いので注意。
mohiramohira

2022/12/01(木) 20:15-22:15

実績

  • p.184 6.2 協調的グリーンスレッドの実装から

Discord開始リンク

次はどこから？

  • 次回: p.188 6.2.2 コンテキスト から

MEMO

最近

  • Amazon Black Friday!
  • ポスター用の額縁を使うと、見た目も保存も良い感じになりそう
  • ブックスタンドで健康になろう
  • 仕事の現場での勉強会を始動させていく話
  • 浮動小数点数とみせかけて、MISRA C の話 https://ja.wikipedia.org/wiki/MISRA_C
  • 「MISRA C」はC言語のコーディング規約。自動車業界ではデファクトスタンダード
  • C言語の列挙型の罠 https://www.jpcert.or.jp/sc-rules/c-int09-c.html

preemptive という単語のニュアンス。先制攻撃じゃ！

https://www.nikkei.com/article/DGXMZO61253470X00C20A7PP8000/
preemptive strike なるほど…

non-preemptiveな時代の残念なOSの話

Windows 3.1 とかは、ノンプリエンプティブだった。
ので、タスク切り替えがごみなアプリがOSをかためることがしばしばだったよね。

グリーンスレッドの「グリーン」って何？

緑かと思いきや、開発チームの名前からとっているっぽい！

Etymology
Green threads refers to the name of the original thread library for the programming language Java (that was released in version 1.1 and then Green threads were abandoned in version 1.3 to native threads). It was designed by The Green Team at Sun Microsystems.[2]
Sun MicrosystemsのThe Green Teamによって設計された[2]。
https://en.wikipedia.org/wiki/Green_thread

Sun MicrosystemsのThe Green Teamによって設計された[2]。

Q. グリーンスレッドがOSのスレッドより"軽い"のは、なぜ？

グリーンスレッドは、OS のスレッド に比べて、スレッド生成と破棄のコストを小さくできるため、

雑に言えば、仕事が少ないから！

そもそも、システムコールが重たい。
管理する情報 (コンテキスト情報) の大きさも、プロセス全体とアプリ内のみとではぜんぜんちがう。
プロセスの切替だと、プロセス空間毎切替えるとか、いろいろと。

「仕事の量」を考えるときには、そもそもOSって何の存在しているの？ から考えるとよさそう！

https://discord.com/channels/508093437187457045/882639711447961710/1047842322823528519

殿堂入りのCPU本！

https://tatsu-zine.com/books/hajimete-yomu-486

こっちもおすすめ！

『初めて読む486』はやさしいと言っても説明対象自体（マルチタスク）が難しいのである程度は難しいですが、『はじめて読む8086』は本当にやさしいです

https://www.amazon.co.jp/dp/4871482456

コンテキストとはプロセスの実行状態に関する情報

いろいろあるね！

set_context関数 と 関数それ自体の仕組み とアレコレ(p.188)

👺 「やってほしいこと」から考えると良いですね！

👺 関数呼び出しの仕組みって「協調マルチタスク感」があるぞ...!!!

return で呼び出し元に戻る感じとか、協調じゃん！

そう考えると、対称コルーチンの yield とかも、協調じゃん！

上記は、協調的マルチタスクのデメリットである、「無限ループマンによって詰む」現象が起こるわけだし！

おーひらさんも指摘されている通り、関数呼び出し→コルーチン→グリーンスレッド→カーネルスレッド／カーネルプロセス→コンテナ型仮想マシン（で合ってましたっけ）は、相似形を形成していると言えそうですね。
https://discord.com/channels/508093437187457045/882639711447961710/1047862186707521606

その他

  • 『ざんねんないきもの辞典』ならぬ、『ざんねんなOS事典』
  • AT&TがUnix売り出そうとしてBSDから許諾料取ろうと画策した事件ですね
  • OS/2
mohiramohira

2022/12/15(木) 20:15-22:30

実績

  • p.188 6.2.2 コンテキスト から

Discord開始リンク

次はどこから？

  • 次回: p.192 の 真ん中辺りから

MEMO

最近

  • LIVE激アツ！
  • LIVEに行こう！
  • https://github.com/gorilla#gorilla-toolkit のアーカイブ
  • OSSは人が作っている
  • クレームはデータとして集積されやすいけど、「好き」とか「いいぞ！」はサイレントになっちゃうので。もっと言っていこう！
  • 勉強会、始動！ 音読は、時間がかかる(からといって、良し悪しは別の話)
  • Herokuの有料化と懐かしきレンタルサーバ
  • 新卒採用イベント
  • 「Q. 会社の雰囲気はどうですか？」という質問

ところで、この勉強会に何でくるの？ 何が価値なん？

  • 「わかったふりをするインセンティブがない」というのが重要かもしれない...!!
  • あるいは、「わかった」と言(わ|え)ないとまずい、みたいなプレッシャーが無いとも言える

似ているね？

  1. プロセスA と プロセスB の切り替え(コンテキストスイッチ)
  2. プロセスAの中で 関数F と 関数G の切り替え

関数呼び出しの仕組みちゃんとやろう！(N回目

まじでそれ！

Q. caller保存レジスタと callee保存レジスタ ってなんだっけ？

呼び出し/呼び出され の関係は相対的なもの。文脈があるよね。

レジスタの役割を分ける

何番のレジスタをどう使うかを決めておくと効率よいというか事件がおきにくそうだよね。

未解決

一般的にCの構造体は定義順とサイズでアライメントが決まるものですがRustの最適化はどういうものなんでしょう

osプロセスforkと似ているというか、なんつーか考え方が難しい！

次回、憶えていたら、「今年のGoodなお金の使い道」の話をしよう

そうしよう

mohiramohira

2022/12/29(木) 20:15-22:30

実績

  • p.192 の 真ん中辺りから

Discord開始リンク

次はどこから？

  • 次回 p.195 6.2.3 スレッド生成、破棄とスケジューリングから

MEMO

最近

  • 積ん読を解消したいと思いつつ、調べる沼へようこそ
  • お得なCPUを買った話
  • 困難は分割せよ(自分の肉体編)
  • 『相棒』の積ん読(@ABEMA)

「機能」と「規約」を区別しよう！

まじで大事。

制約とかもそう。自由なところと、そうでないところを区別すると、理解しやすくなる。

「アラインメント」という概念はすごいぞ！ いろんなところに効いてくる！

アラインメント（という用語）には色々無いけど、アラインメントが必要になる理由は色々ある

CPU理由、OSメモリ管理理由、ライブラリメモリ管理理由、アプリ都合理由。いろいろ。

アラインメントの気持ちを知るには、ハードウェアっていうか物理的な具体的な回路もイメージできるとかなりわかってきそう！

このサイトもおすすめ → http://www5d.biglobe.ne.jp/~noocyte/Programming/Alignment.html#CpuBasics

そうですね。今見てるページで言ってる方のアライメントの必要性は、CPUとメモリの接続回路のイメージがあると理解しやすいです。

ジキルとハイドの伏線

まじで！！！！

「ワード」という言葉は具体的なサイズはいろいろあるから注意

ワードはかなり曖昧な単語ですね
CPUレジスタが扱うサイズがワードと呼ばれるのが一般的な気がします

WORD は、CPU依存で効率よく扱える単位、が元の定義で、2バイトだったり 4バイトだったりする。

本の執筆は大変だ！

扱うテーマや、読者に対する前提、何を説明して、何を説明しないか。どんなたとえを使うか。

mrprotectを深堀り ガードページ

Cのmalloc()関数の進化的な話 → Rustのalloc

https://doc.rust-lang.org/alloc/alloc/trait.GlobalAlloc.html#tymethod.alloc

Cに慣れすぎてて、最初alloc()の引数はただの整数だと思い込んでいたけど、もっとインテリジェントなLayout情報を引数にとるのだなぁと。

インテリジェンスやら、呼び出し側に対して、どの知識をどれだけ要求するか的な感じ。

目的に立ち返ろう

いつものプログラミングじゃなくて、
システムプログラミングなので、メモリアドレスを意識しないといけない

mohiramohira

2023/01/12(木) 20:10-22:10

実績

  • p.195 6.2.3 スレッド生成、破棄とスケジューリングから

Discord開始リンク

次はどこから？

  • 次回 p.199 最後の段落から

MEMO

最近

main.rsを見て考えると、実際にグリーンスレッドで"協調的"に動くのを考えやすい！

https://github.com/oreilly-japan/conc_ytakano/blob/main/chap6/ch6_mult-x86_64-linux/src/main.rs

// https://discord.com/channels/508093437187457045/882639711447961710/1063086299059335218
queue , command  , stdout
G     , spawn    ,
G M   , spawn    ,
M G   , schedule ,
M G O , spawn    ,
G O M , schedule ,
G O M , print    , Gaia!
O M G , schedule , Gaia!
O M G , print    , Gaia! Ortega!
M G O , schedule , Gaia! Ortega!
M G O , print    , Gaia! Ortega! Mash!
G O M , schedule , Gaia! Ortega! Mash!

main.rsで大事なのが、GOMの順にしたいけど、spawn関数のなかでschedule()呼ぶので、GMOの順番でspawnしていく必要がある！

schedule()関数は、キューの状態変化としてはとてもシンプル。pop_front()して、push_back()するだけ。

で、「コンテキスト」という言葉で考えると、先頭のコンテキストをどっかに保存して、次のスレッドのコンテキストを呼び覚ます(レジスタを復元する)だけ。

勘違いポイント！ main.rsのspawn()内でschedule()が実行されないという勘違いをした！

この勘違いをしたままだと、Gaiaが2回先に呼ばれることになる。JSA失敗！

// https://discord.com/channels/508093437187457045/882639711447961710/1063089256005894174
queue , command  , stdout
G     , spawn    ,
G M   , spawn    ,
G M   , print    , Gaia! //<-spawn内でschedule()するので、本当はここでschedule()
M G   , schedule , Gaia!
M G O , spawn    , Gaia!
M G O , print    , Gaia! Mash!
G O M , schedule , Gaia! Mash!
G O M , print    , Gaia! Mash! Gaia!
O M G , schedule , Gaia! Mash! Gaia!
O M G , print    , Gaia! Mash! Gaia! Ortega!
M G O , schedule , Gaia! Mash! Gaia! Ortega!
M G O , print    , Gaia! Mash! Gaia! Ortega! Mash!

「コンテキストを切り替える」は結構抽象度が高い言葉！ だけど、結局、何かしら実行にまつわる情報をレジスタに保存したり、その情報をレジスタから復元してるだけ！

大したことないぜ！ レジスタは所詮読み書きしかできないのだ！
(というか、読み書きだけでそれができるのがすごいね)

ラウンドロビン方式以外のスケジューリング方法ってあるよね？

ジャンル的には「スケジューリング」

登場分野としては、OSとか負荷分散、待ち行列とかである。

  • FIFO
  • FCFS(First come, first served)
  • SJF(Shortest Job First)
  • 優先度付きのキュー(FIFO)とかもあるよね

個人的にはFIFOは先入先出のデータ構造を指すもので、FCFSは最初にキューに来たタスクを最後まで実行するというスケジューリングアルゴリズムと捉えています

FIFOはもうちょい一般的な処理アルゴリズムで、FCFSはFIFOを利用したスケジューリングアルゴリズム、みたいな印象

SJFが難しいのは事前にタスクの残り時間がわかっているケースはほぼないということですね。
実用的には残り時間を近似して求めます。

FIFOはデータ構造で、
FCFSはスケジューリングアルゴリズム。
FIFOじゃないデータ構造を使ってFCFSをやってもいい。
と、前の方をちらっと読んでおもいました。まる。

PRだしとこ。

p.192 「を」が抜けていると思う。
https://discord.com/channels/508093437187457045/882639711447961710/1063068981205934111

if (set_context(registers)==0) ... の動きがやっぱむずい！

要復習！ だれかに聞こう。

mohiramohira

2023/02/09(木)

実績

  • p.199 最後の段落から ◯◯ まで

Discord開始リンク

次はどこから？

  • 次回 p.211 7章から

MEMO

最近

  • いろんな勉強会で勉強会を勉強
  • 書き捨てブログからわかる季節の影響。寒いのは辛い。
  • 精読から速読へ。二刀流を目指して。「ちゃんと読む」とは。
  • 年明けこそ年貢の納め時。
  • 半導体の活用

ネットワーク＼(^o^)／ｵﾜﾀ

でも、会はふつーに生存。耐障害生だぜ！

Q. アドレスの高い方から低い方へってのは、なんで？

CPUがそういう作りだから。

実は、近時のCPUがそういう作りなのは、SWがスタックをそういう風に使うという習慣に合わせたという面も強いです。
根本的な理由を考えると、推測ですが、ヒープを低位から高位に、スタックを高位から低位に伸ばしていくことでメモリを無駄なく使えるとかではないなと。

更に推測ですが、（人間が頭の中で考えるとき）理論としてのスタックが「上に積んでいく」イメージで語られるので、その人間の思考に合わせたという側面もあるかもしれません。
https://discord.com/channels/508093437187457045/882639711447961710/1073211152072441896

spawn()したときに、schedule()も呼び出しているのがややこしいポイント

マジで厄介猪八戒

わからんかった

コンテキストスイッチ時のオーバーヘッドを軽減するために呼び出し規約を変更する方法もある。
Go言語では独自の呼び出し規約を用いており、汎用レジスタすべてを caller 保存レジスタ とし、 callee 保存レジスタをなくしている。
そうすると、コンテキストスイッチ時にはプログラムカウンタやスタックポインタなどのみ保存すれば良くなり、無駄なレジスタの保存をする必要がなくなる。しかし、これを実現するためにはコンパイラを修正する必要がある

どういうことだってばよ！？

たぶん、呼び出し側で退避させる場合は、原則としてすべてのレジスタをメモリに退避しないといけない。
呼び出される側で退避させる場合は、呼び出される側で使うレジスタだけ退避させれば十分なので、退避するレジス多数を少なくできる = インストラクションの実行数が少なくすむ、ので速くできる。
ということでないかしらん。
文脈違ったらごみん。

https://discord.com/channels/508093437187457045/882639711447961710/1073212851126280253

https://go.googlesource.com/proposal/+/refs/changes/78/248178/1/design/40724-register-calling.md

Caller-saveレジスタと Callee保存レジスタ で共有資源の責任を考える

https://freak-da.hatenablog.com/entry/2021/03/25/172248

関数を呼び出すとき，機械語レベルでは，レジスタをどう使うかが重要になります．スタックは関数ごとに独立してメモリを利用できますが，レジスタは共有資源なので関数の呼び出し元（caller）と呼び出し先（callee）で協調して利用する必要があります．

レジスタの使い方はパフォーマンスにめっちゃ影響するんですな〜という雑な理解

どれがアクター？ ってのが謎だ

Actor構造体とかないから、よくわからんってのがある。

p.204

「メッセージの受信時には、メッセージキューに自分宛のメッセージがある場合はそれを取り出し、ない場合は、実行キューから待機スレッドに自スレッドのコンテキストを移動させる。」という文はわかりにくいと思います。
「受信時」というのは、前の文との関連から「自身のメイルボックスにメッセージが入れらたとき」と解釈してしまいますが、実際には「recv()を呼び出したとき」という意味ですね。

未解決

アクターモデルは、なんとなくCSP(Communicating Sequential Process)とイコールだと解釈しているんですが、厳密な定義はどうなんでしょう？

アクターモデル(1973) → CSP(1978) かも？https://ja.wikipedia.org/wiki/アクターモデル

結局、アクターモデル、何が嬉しいの？

メッセージパッシングを追加してそれに合わせたスケジューリング機構に変えたという「実装の拡張」と、アクターモデルという「計算モデル（あるいは設計モデル）」をごっちゃに論ずる本書の構成もわかりにくさの原因ではないかと。

  • 何度でもrecv(), send() してよい説
  • 何度でも自分の家の郵便受けをみてもよい雰囲気
  • グローバルなキュー(郵便受け)よりも楽かもしれない？

アクターモデルやらCSPやらは、筑波大の新城研究室のページでメッチャ解説されてるーーーーーーーーーーーーーーーーーーーー！！！！！！！！！1

並行プログラミング言語、トランザクション/Concurrent Programming Languages

http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2016/2016-05-23/

http://www.cs.tsukuba.ac.jp/~yas/

動画も公開されている〜〜〜〜〜〜〜〜〜！

ここに資料と動画URLがセットである→ http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2021/

筑波大学 CS 並行システム 2021 / 動画 まとめはこれ。
https://vimeo.com/channels/1696369/videos

mohiramohira

2023/02/23(木)

実績

  • p.211 7章から p.215 まで

Discord開始リンク

次はどこから？

  • 次回 p.216の最終段落から(例7-4から)

MEMO

最近

  • Linux物理マシンをGETした話
  • 海外出張と英語

議論がわちゃわちゃたのしい！

最高

公平性のおさらい

Non-Uniform Memory Access（NUMA）

NUMAとは、複数のマイクロプロセッサ（MPU/CPU）を搭載した対称型マルチプロセッサ（SMP）構成のコンピュータで、全体で共有されているメモリへのアクセス速度がCPUとメモリ領域の組み合わせ次第で均等にならないもの。
https://e-words.jp/w/NUMA.html

7.1.1 (弱い)公平性はあるけど、別に重要性とかそういうわけじゃない感じ。

たぶん。

コンテンション(contention)

CPU獲得競争がおきると、リソース問題もあったらり。

ちなみにコンテンションはユーザースレッドとカーネルスレッドで違う用語が使われる場合があります。
ユーザースレッド間のコンテンション -> Process-Contention Scope (PCS)
カーネルスレッド間のコンテンション -> System-Contention Scope (SCS)

めも

  • 共有変数かどうかを見ておくのは設計上、だいじやな。それはそうだ。

stateが急に増えた！ ので、難しいし、公平性を担保するには大変だな〜。

いままで

  • ロック獲得したかどうか

今回

  • ロック獲得したかどうか
  • ロック獲得要求中かどうか
  • ロック獲得する権利があるかどうか

本に全パターン書いてほしいw

編年体 と 紀伝体

へ〜。

TTAS (Test And Test And Set)

https://en.wikipedia.org/wiki/Test_and_test-and-set
https://ja.wikipedia.org/wiki/テスト・アンド・セット#テスト・アンド・テストアンドセット

mohiramohira

2023/03/09(木)

実績

  • p.216の最終段落から(例7-4から)

Discord開始リンク

次はどこから？

  • 次回 p.219 7.1.3 MSCロック

次回までに

「並行プログラミング入門」ロールを払い出して、メンションできるようにする。

MEMO

最近

  • インターネット環境
  • 『アホリズム』の第2部まさかの再開
  • Haskellによる並行・並列プログラミング
  • 学会の話はまた聞こう
  • 久々の新規参加の方！
  • 中1回での参加が1ヶ月ぶり
  • さいきん春だね
  • 自作キーボードとか自作PCのパーツ
  • 冬眠は意外と危険な(？)生存戦略

ロックアルゴリズムの比較軸ってなんだ？ ってのに気づいた！

  • Fairに比較するのが難しい
  • Hintになりそう。共有資源へのアクセス頻度(≒コンテンション)とSpinするしないとか。
  • (あとは実装の複雑さ)

7.1.1のアルゴリズムと、チケットロックでは、Loop中でWriteするか否かの違いがあるので、それをコンテンションの違いだと言ってる可能性はありますが、7.1.1のアルゴリズムでも、毎ループWriteするわけでもないので有意差があるかは疑問です。
https://discord.com/channels/508093437187457045/882639711447961710/1083373785329184849

半導体業界の「地図」をつくっていきたい

  • 微細化、もう限界なのでは！？
  • 3D！？ そもそもの容積を増やす感じか
  • EUV
  • Extreme Ultra Violet？
  • 漏れ電流(Leak 電流)
  • 半導体の微細化をあきらめてない話、激アツ
  • 微細化が難しい理由の1つか

公平性の定義...!?

Q. 「実行可能な待機状態」とは？
Q. 「実行不可な待機状態」とは？

弱い公平性のアルゴリズム

  • チケットロック
  • MCSロック

気持ち

握手会で握手できるのがロック獲得だとして、

列に並ぶ(待機)
列から抜ける(不可状態

これはわかりやすい説がある(たとえ話はいろいろあるけど

弱い公平性: 「よし、目の前に3人いるから、3人待てば、オレの番だぞ...」
↓
でも、横から入ってきた人
↓
「抜かされたっ！」 ってなるかもしれない(ならないかもしれない)
待てばいつか握手できることは確定しているけど、それがいつになるかは予測できない。

強い公平性: 「よし、目の前に3人いるから、3人待てば、オレの番だぞ...」
↓
「よし、ちゃんと3人分だったな。よしよし。」

いろんな公平性？

  • プロセスの公平性
  • タスクの公平性
  • ロックの公平性
TakuboTakubo

2023/03/23(木)

実績

  • p.219 7.1.3 MSCロック から

Discord開始リンク

次はどこから？

  • 次回: P225

MEMO

最近

  • VtuberのグループLIVE！ おもろそう
  • 高速バスは、アカン！
  • これがおとなになるということ...!!!!
  • プロセスの標準化
  • 説明のバランス、ドキュメントを書いても読まれない…
  • 読んでもらうための営業活動と捉える
  • WBCぜんぜんみてないけど、優勝したのはなんか嬉しい
  • やはり盛り上がりの一番の要因は大谷かな…他国含めMLBの選手が沢山出てくれるのは嬉しかったです
  • スマホを車のキーにするシステム（無線、セキュリティ、座標計算）（イメージは電波飛ばして反射波で距離測る感じ）
  • イソバイドフードコーディネーターくるー？？？
  • 毎食イソバイドかレーズンかを食べない（飲まない）といけないなら？→ 選択の余地なく、イソバイド！
  • 今日の司会はようこさんです

その他の雑談

  • 半導体の再勉強「マスク」をつくって「ウェハー」上に転写するらしい
    波の干渉「十分に小さいものとする」の「十分」を満たしているやつだ！
  • オブジェクト指向の話
    違和感あり：x.add(y);
    違和感なし：add(x, y); dollar.to_yen();
    非可換なら違和感ないけど可換だと違和感ある？
  • Rustをもっと、わかりたい！

MCSロック

  • キャッシュのスラッシングなどの競合を回避するロック機構

（CPU間の）キャッシュのスラッシングとは？

  • キャッシュはCPUごとに持っている。
  • キャッシュの内容はメインメモリのコピー。コピーをCPUキャッシュに置くことで、素早くアクセスできるようにするのが目的。メインメモリへのアクセスは遅い。
  • コピーなので、キャッシュとメインメモリの内容と齟齬が生じないようにする（同期を取る）必要がある。
  • 複数のCPUがずっと同じアドレスにアクセスし続けると、常にメインメモリとの同期を取る必要があるので、キャッシュの効果が出なくなる。

MCSロックの動き

  • MCSロックの動きは、動画（アニメーション）でみたい。

  • 新しくロック待ちするスレッドは自分のMCSNodeを末尾に追加する

  • ロックを使い終わったら自分のNodeの次のNodeのlockedをfalseに設定する

  • キューへの追加時や、待ちスレッドがないときの解放で、競合は起きないのか？
    Nodeのnextとlastを矛盾のないように更新しないといけないはず

    • lastの更新さえアトミックに行えば、nextは後でのんびり更新したのでよい。
      • キューへの追加前に、nextはNULLに設定してある。
      • nextが非NULLになるまで、（前のスレッドは）drop関数内でループして待ってくれる。
        • next は書き込みが一度しか使われないので Atomic操作じゃなくてもいい

非アトミックな命令は分割されることはないの？

  • 例えば、次のようなことは起きない？
    • 4byte変数を読み出したときに、別のCPUがその変数へ書き込みを行ったことで、書き込み前後のbyteが混ざった値を読み出してしまう。
    • または、個々のビットが混ざった値を読み出してしまう。
  • そういうことは起きない。
    • 大体のCPUはatomic命令じゃなくても読み込みで書きかけのものを間違って読んでしまうことはない(保証されている)
    • アトミック命令でなくとも、個々のメモリアクセス（書き込み、または読み込み）はアトミックに実行される。

Issueを出す

  • P220「キャッシュが排他的に設定されてしまい」？？？
    （この節の文脈では）キャッシュはもともと排他的なはず。
ようこようこ

アトミック命令でなくとも、個々のメモリアクセス（書き込み、または読み込み）はアトミックに実行される。

アトミック命令は複数の操作(compare とswapとか)をアトミックに行うための命令であって、個別の操作自体は元々アトミックなんですね。長年ぼんやりしてたところがスッキリしました、ありがとうございます！

TakuboTakubo

2023/04/06(木)

実績

  • p.225 MCSLockの使用例 から

Discord開始リンク

次はどこから？

  • 次回: P231 7.2.3 TL2の実装

MEMO

  • 「Boyd-Wickizerらは、CPU コア数が 10 を超え たあたりから、チケットロックよりも MCS ロックの方が性能が良くなると報告している。」
    ⇨ 手法を選択する損益分岐点がある。
  • トランザクションメモリ、みんな知らなかった

最近

  • ビルの移転（梅田→梅田）。ビルの家賃3倍！
  • 5月から全出社。
  • ネットワークが午前10に遅くなる怪。
    ⇨ 近所に、引きこもりのハードゲーマーが住んでいる説。
  • 開発の正念場。速くするための突貫工事の改修。コードの崩れとの戦い。
  • テストの網羅性を上げる。
    ⇨ テスト設計の知識を持っている人が必要だと思う。テスト担当は刺身タンポポではない。
  • デジタルキー（スマホを車のキーにする機能）の仕事が楽しすぎて、ワーカホリック気味！
  • 今まではエンジン相手だったのが、人/ユーザビリティ/セキュリティについて考えるのが楽しい。
    bluetooth の仕組みが分かった！

最近

  • P227: lunch → launch. ミサイルがお昼ごはんになっている。
mohiramohira

主催者がいない勉強会

前回と併せて、図らずも勉強会運営OJTになった会

mohiramohira

2023/05/04(木) 20:15-21:45

実績

  • p.231 TL2の実装 から ← 7章おさらいになったのでページは進んでないよ！

Discord開始リンク

次はどこから？

  • 次回: p.231 TL2の実装 から
    • MEMO: 7.2.2 TL2のアルゴリズムを読んでからがオススメ！

MEMO

最近

  • 『ラーメン発見伝』
  • 中華街
  • 筋肉痛が流行っている LIVE → 山 → サッカー観戦 → 田植え
  • お米の評価基準とは？ 魚沼産コシヒカリが今でも最強なのか
  • 運動習慣、はじめました
  • Testing vs Checking / https://open.spotify.com/episode/09L3zpd9QBocguwox664ai

今日は7章をおさらいする会でした！

  • 解決したいことは、公平性とコンテンション
  • ソフトウェアトランザクショナルメモリ
  • ロックフリーなデータ構造

↓

  • 弱い公平性が担保されたアルゴリズム

↓

  • 「弱い公平性」を理論的に満たしているわけではないが、ロック獲得時の競合を減少させるようなアルゴリズム
  • チケットロック
  • MCSロック

↓

  • STM
    • トランザクション感はDBMSのトランザクションそれっぽい
  • TL2のアルゴリズム
  • アルゴリズムが怪しい
    • とくに、読み込みトランザクションのread-setはどうなるの？
    • 「読み込みのコミット」の違和感
  • TL2のアルゴリズムを実装とともに見ていって、理解を確かめましょ！
mohiramohira

2023/05/18(木) 20:30-

実績

  • p.231 TL2の実装 から

Discord開始リンク

次はどこから？

  • 次回: p.238 7.2.3.4 WriteTrans型 から
    • MEMO:

MEMO

最近

  • 最近はコンピュータサイエンスよりも、英語のモチベが高め！
  • GPTとGitHubCopilot
  • ダミーデータはかなりつよい
  • 「生成AIで腱鞘炎が減る！」
  • 仕様書をきっちりつくるやーつ

しっかり読み込めたのはえらい！

集団のPowerでもある!!

(知識の少なさを差し引いても)読みやすいわけではないが、読めばわかるということではある。

文章が時々分かりづらいという体験から、より検証しようとする姿勢で読んでいると思います。

STMの解説ブログ

https://kumagi.hatenadiary.org/entry/20111201/1322755572

readTrans メモリ読み込み前後のtest(ストライプのlock確認と、read_versionの確認)がないとどう困るの？

まぎさんのまとめが優秀！

一連のスレッドのURL → https://discord.com/channels/508093437187457045/882639711447961710/1108733236038877194

板書


余談

  • プレミア本
  • トレーサビリティなのか、関連の主張なのか？
  • トレーサビリティあってもトレースしなくね？ 問題
  • マイクロカーネル、モノリシックカーネル
  • 「よ〜す」だけがあっていればいい
  • 太陽が昇る方角は、バカボン経由で考える
mohiramohira

2023/06/01(木) 20:30-

実績

  • p.238 7.2.3.4 WriteTrans型から7.2.3.6 STM型 まで

Discord開始リンク

次はどこから？

  • 次回: 7.2.4 STMを用いた食事する哲学者問題

MEMO

最近

  • PCを新調した
  • ジムに通い始めた。(エンジニアだからか)マシンや力学に興味がでてくるかもしれない
  • BLUE GIANT の映画と漫画がいいぞ！
  • 『岳』
  • 三歩とかいうフィジカルお化け
  • 明日はGoConference2023
  • さっき起きた

STM(ソフトウェアトランザくなるメモリ)

  • トランザクショナルメモリ
    • ハードウェアトランザクショナルメモリ
    • ソフトウェアトランザクショナルメモリ
      • その実装例: TL2アルゴリズムをRustでやってる 👈

TL2アルゴリズムはなんとなくわかってきた

いや、わかってないけど、わかってきたのよ

fetch_add(というか、FetchAndAddは、変更前の値)を返す

https://doc.rust-lang.org/std/sync/atomic/struct.AtomicU64.html#method.fetch_add

Adds to the current value, returning the previous value.

アトミック命令では更新前の値を返すのが慣習だと思うので、それはいいと思いますが、inc_global_clock()という関数が更新前の値を返すのは不自然でわかりにくいと思います。
https://discord.com/channels/508093437187457045/882639711447961710/1113815706304258049

ミクロな話がわかっても、結局(？)STMという全体感がつかめていない問題！

それな！ で、どうする？

ダニングクルーガー曲線の最初の理解できたポイントにすら辿り着かせてもらえない感覚

Q. 逆に、どういう情報があると嬉しい？

それはそうと、8章に期待

むずいのは確定！ でも逆に色々楽しめるかも！

『Haskellによる並列・並行プログラミング』が良さげ

https://www.oreilly.com/library/view/haskell/9784873116891/?_gl=1s0fhz_gaNDE0OTg1MTAwLjE2ODMyMDEwNzc._ga_092EL089CH*MTY4NTYyNzUzMy4yLjEuMTY4NTYyNzU0OC40NS4wLjA.

mohiramohira

2023/06/15(木) 20:30-

実績

  • 7.2.3.6 STM型 から p.250 7.3 ロックフリーデータ構造とアルゴリズム

Discord開始リンク

次はどこから？

  • 次回: p.250 7.3 ロックフリーデータ構造とアルゴリズム

MEMO

最近

  • 『BLUE GIANT』は映画も漫画もよかった！
  • サントラはいろんなところであるぞ！
  • 同一の映画を複数回みるときのクールダウン
  • jazz barに行った話。
  • ジムは継続中！ 腰痛には気をつけて
  • 半導体講座。
  • 拡散方程式が半導体製造の過程で重要らしい。
  • 気圧の影響。梅雨は早く明けてほしい。

ミューテックス vs STM

観点

  • デッドロックする、しない
  • 人間的にわかりやすい、にくい → バグりにくいとかもある
  • ライブラリある、なし

STMの点: 複数の状態変更操作をグループ化し単一の不可分操作として実行できるようにすること

複数の状態変更操作をグループ化し単一の不可分操作として実行できるようにする

Atomicさがポイントな感じがとてもよい！

↓↓10章冒頭だけよもうぜ！

https://www.oreilly.co.jp/books/9784873116891/

ギアを回転させたあとで、逆回転させても過去には戻れない

組み込みの場合、STMは複雑で（たぶん）遅いので採用しずらい。
そもそも、組み込みは副作用を起こすのが目的なので、STMを採用検討できる場面自体が少ないですが。

「Retryがなければ、STMとはいえない」は偽だとおもう。

STMの合成可能性が大事っぽい！

不可分なグループA と不可分なグループB → [A+B]というあらたな不可分操作なグループ

https://www.oreilly.co.jp/books/9784873116891/

トランザクションの歴史。データベース分野でのトランザクション → ソフトウェアトランザクショナルメモリ

データベースの界隈で使われる「トランザクション」をメモリに適用して並行プログラムを書きやすくしようという研究です。
https://kumagi.hatenadiary.org/entry/20111201/1322755572

ここが盛り上がった

3つ目の改良点としては、オブジェクト単位で扱えるようにすることである。本実装はストライ プごとにバージョン管理をしていたが、実際にはオブジェクト単位の方が利便性がよい。しかし、 オブジェクト単位の実装はガベージコレクションのある言語だと容易だが、自前でメモリ管理を行 う言語だと難しい。

  • 「しかし」が何の逆説なのか謎。
  • トランザクションのなかでメモリの確保や解放をやることを想像すると、GCがない環境ではやばそう...!!!
  • とくに、Retryが絡んだりすると、自前でのメモリ管理は人間には地獄になりそう

今日は横道の議論がアツかった！

ほんとそれ！

おまけ

  • ミリしら
  • アド、爆アド
  • 1:1交換
  • バフ・デバフ
  • スタン落ち

typo

TakuboTakubo

2023/06/29(木)

実績

  • p.250 7.3 ロックフリーデータ構造とアルゴリズム から

Discord開始リンク

次はどこから？

  • 次回: P255 の 例 7-19 （コード）から。

MEMO

最近

正しく動かないロックフリースタック

  • StackBadのBadとは？
    ⇨ 正しく動かないからbadなのだろう。
  • なぜ、正しく動かないの？一見、正しく動きそうだが。
    ⇨ ABA問題（後述）が生じうるので、正しくない！

Boxとは （Discordコメントより）

  • Heapに確保されたメモリを表す構造体。
  • 構造体の先頭付近に管理領域があるのだろう。
  • なので、Boxへのポインタと、その中身へのポインタでは、（一般に）値が異なる。

compare_exchange_weakとは （Discordコメントより）

  • 比較が成功する場合でも、失敗とみなされることがありえる。
  • CASがないCPUアーキテクチャでは、LL/SCでCASをエミュレートするため。
  • そのような偽陽性を生じさせないためには、compare_exchange_strongを使用する。

ABA問題

「A を読み込んで B を読み込んで A を読み込んだ場合、最初と最後の A は同じ値でも意味的に異なっている場合がある。」という問題。

正しくないロックフリースタックで生じる問題

本書の例のスタック（実体はリンクトリスト）の場合、Nodeの一致確認をメモリアドレス値の比較のみで行っているので、メモリ領域が再利用されるなどにより、本問題が生じうる。
すなわち、異なるNodeがたまたま同じアドレスに配置された場合、それらは異なるNodeであるにも関わらず同じNodeあると判定されてしまう。結果として、スタックが更新されているにも関わらず、「スタックは更新されていない」とご判定してしまう。

解決方法

解決策としては、CAS命令ではなく、LL/SC命令を利用する方法がある。
この場合、なんと、正しくないロックフリースタック（CAS命令で実装）と正しいロックフリースタック（LL/SC命令で実装）の関係は、前述のcompare_exchange_weakとcompare_exchange_strongの関係と同じになるのである！

Issueを出すべきもの

7.3の第一段落 （Discordコメントより）

  • 「スタックに説明し」→「スタックについて説明し」
mohiramohira

2023/07/13(木) 20:30-

実績

  • p.250 7.3 ロックフリーデータ構造とアルゴリズムから、

Discord開始リンク

次はどこから？

  • 次回: P263 8章 並行計算モデル

MEMO

最近

  • ドキュメーテーション力、だいじだね！ 最重要課題として頑張るぞ！
  • 喋りながら書くのは慣れ
  • 画面共有するときは動き続ける、喋り続ける
  • 発散フェーズと、収束フェーズを分けて会議に参加する話
  • 腰痛や腰のヘルニアに注意！
  • 『エンジニアのためのドキュメントライティング』 👈 11章のコンテンツ削除と非推奨化が特に良いと思う。あとドキュメントのオーナーを作る発想
  • タネンバウム先生といえばコンピュータネットワークとオペレーティングシステム
  • OJT後の新人向けの読書案内。『図解入門TCP/IP』とか『ネットワークはなぜつながるのか』
  • ベガルタ仙台の応援団の存在。応援団不在でサポーターが困惑しているかもしれない。
  • 『Winnyの技術』と『Androidを支える技術』
  • 電子証明書
  • 数学書の流れ、ルベーグ積分やるぞ！

ABA問題

このように、A を読み込んで B を読み込んで A を読み込んだ場合、最初と最後の A は同じ値でも意味的に異なっている場合がある。このような問題のことを、ABA 問題と呼ぶ。

「意味的に異なる」の意味に注意！
本文では、ポインタの話ですよ！

ABA問題自体はポインタに限った問題ではない話(Discordリンク)

この本の例ではポインタでの問題ですが、ABA問題自体はポインタに限った問題ではないです。
ただ、ポインタ以外では実害まで出る状況は、すぐには思いつかないですが。
ポインタ以外のABA問題の例としてよく(?)挙げられるものとして、「整数の0と、IEEE浮動小数の0.0は、ビットパターンとしては同じに見える整数と浮動小数では、同じビットパターンでも異なる値を示す」というのがあります。

LL/SC命令がなくても、ロックフリーススタックというデータ構造は実現できるよ

x86-64 では LL/SC 命令が存在しないため、タグを用いた方法が用いられる。タグとは、ポインタのバージョン情報のことであり、破壊的な操作が行われる際にポインタのバージョンを更新していく。そうすることで同じアドレスを 指すポインタであっても、バージョンが異なるため CAS 命令で変更を検知することができる

LL/SC命令がなくても、ロックフリーススタックというデータ構造は実現できるよ

「タグ」というものを使った「バージョン管理」は、STMの実装例と一緒じゃね？ ちょー似ているよね？

ソフトウェアトランザクショナルメモリとロックフリーデータ構造のアプローチがとても似ているように見えてきた。混乱。

ダングリングポインタ(ぶら下がりポインタ)

解放されたオブジェクトを参照するポインタ。

脱法Rust

ロックフリーデータ構造を用いると再びマルチスレッドでの参照問題が発生する。

Rustでは所有権という仕組みがあるので、マルチスレッドでの参照問題は起きない。
↓
Rust上でロックフリースタックを実装しました
↓
そのロックフリースタックでは、なんと、マルチスレッドの参照問題が起きちゃう！
↓
対策は？
↓
GCがあれば大丈夫！
↓
GCがない場合は、いろいろ。たとえば、ハザードポインタを使いましょう。他にもたくさん研究されているそうです。

GCがない言語では、ハザードポインタを使う発想もある

ハザードポインタでは、スレッドローカルなストレージに現在アクセス中のアドレスを保存し、メモリ解放を行う際は、そのスト レージに該当アドレスが存在しないことを確認してから行う。

へ〜

銀の弾丸はないよね。並行処理はきっと難しい

3章のMutexロックやスピンロックの対比で、7章ではSTMやロックフリーデータ構造が紹介されているわけだけど、別に、7章での紹介されたアプローチが最強ってわけじゃないよ！ 期待しすぎないでね！

「ロックフリー」とかいう命名による混乱

悲しい。

英語名なら、単語レベルで区別されているのでちょっといいかもしれない。
排他ロックフリー（obstruction-freedom）
ロックフリー（lock-freedom）
ウェイトフリー（wait-freedom）

と、思ったけど、たとえば、wait-freedomでも、WAIT(待機時間)はあるので、悲しい。

『ゲームエンジンアーキテクチャ』を読むと良いかも

さっきの本でも「ロックフリープログラミングという用語の定義はルーズであり、Obstruction Free、Lock Free、Wait Freeを包括する技術的に正しい用語は非ブロッキングアルゴリズムである」と書いてありました

GCの定番本の目次を見ると、並列・並行なGCの説明も充実しているようです!(Discord Link)

19章のうち、6章が、並行処理の話題らしい。

第13章：並行処理の予備知識
第14章：並列ガベージコレクション
第15章：並行ガベージコレクション
第16章：並行マークスイープ
第17章：並行コピーと並行コンパクション
第18章：並行参照カウント

https://www.shoeisha.co.jp/book/detail/9784798134208

何が嬉しいの？ はいつでも問いかけましょう！

ロックフリースタックのところで、ループしてるところは実際どうなん？ 意味あるの？ 何が嬉しいの？ の議論がアツかった。

3章だったり、他の章をザーッとみることで、固めていきたい。

たぶんつくらないけど、「並行プログラミング入門」のクイズ作るか。

8月から8章、達成できそう！

やったぜ！

少しの余裕ってのが、いい感じ！

8章の節のタイトルだけみると、これを理解できたらHaskellを含む関数型言語の議論が理解できるようになるかも？

文字コードの話。ツール間の(リッチ？)テキストの互換がうまくいってほしい

「◯◯は◯◯という本に書いてありますよ」ではなく、「◯◯は◯◯という本に書いてあって、具体的には◯◯と記述されています」まで、言ってくれるの最高！

具体的な文章でないと、結局読まないから！ 特に、LIVEの勉強会だとそう。なぜなら興味があるのはその瞬間だけだから。明日には覚えてない。

また、仮に本を手に入れたとしても、該当文章の検索が高コストなので、やっぱり読むところまで行かない。

というわけで、引用していこう！ ありがとう！

mohiramohira

2023/07/27(木) 20:30-

実績

  • 8章 〜 8.2.5 まで

Discord開始リンク

次はどこから？

  • 次回: p.270 8.2.6 α変換

MEMO

最近

  • そういえば、全体で写経をしなくなった話
  • 営業に同行したりすることもある話
  • Hello 名刺交換
  • 性質は知っているけど、実は素性ゼロな勉強会
  • 人生で2回目のOSSコントリビュート！ SUGOI!!!
  • 会社に涼みにいっている
  • 新人エンジニア向けの読書案内アレコレと見せかけて強くなったのは自分という話
  • 第2次デスク片付けブーム
  • 体が元気！ 梅雨明け！
  • 『コンピュータ・システム』コンピュータシステムという本はカーネギーメロン大学のコンピュータサイエンスコースの教科書として使われているだけあって、なかなか網羅性高いです
  • 『インサイドWindows 第7版 上巻』『インサイドWindows 第7版 下巻』

議論が盛り上がってたのしい！

  • 知識の傾斜がない？ NotTeaching
  • 前のめり、ちゃんと止める、ナイスな態度

ラムダ計算とかいう、最強の"基礎"

こんにちは、ラムダ計算！

ラムダ計算をベースにして、アクターモデルやπ計算をやるらしい。

"音読殺し"の数学的記法

しゃあないね！ ペンで書いていきましょう

チューリング完全、チューリングマシン、オートマトン

Q. チューリング完全ではない計算モデルは？

有限オートマトン
？？？？
プッシュダウンオートマトン
チューリングマシン

『チューリングを読む』を読む

https://bookplus.nikkei.com/atcl/catalog/12/P83720/

キーワードたくさん！

  • 計算可能数
  • チューリング完全

issue起こしその1

https://discord.com/channels/508093437187457045/882639711447961710/1134094506350886942

issue起こしその2

https://discord.com/channels/508093437187457045/882639711447961710/1134095856958701568

手書きメモ

手書きメモのUploadデカすぎるからやめた！

うまいこと残せないけど、まーいいでしょ！

mohiramohira

2023/08/10(木) 20:30-

実績

  • 8.2.6 α変換 〜 8.2.9.3 Yコンビネータで階乗計算する例

Discord開始リンク

次はどこから？

  • 次回: 8.2.9.4 Zコンビネータで無限に再帰する例

MEMO

最近

  • Notionを頑張ろうな話
  • いよいよCGも深くやっていくか！
  • Greatな生育環境の構築。亀も元気です！
  • AC試遊会
  • 単純接触効果(ザイオンス効果)
  • 引く手あまたGOOOOOOOOOOOOOD
  • λで🍤を釣った話

正規順序の評価(Normal order evaluation)の「正規」のニュアンスを知りたい！

  • どのへんが NORMAL なのか？
  • 作用的順序の評価 が Applicative なのは、なんとなく分からんでもない。実践的というか、わかりやすいっぽい気はする。ただし、作用的順序の評価で生きてきたからそう思うだけなのかもしれない。

「正規順序の評価」と「作用的順序の評価」の違いが現れるラムダ式の例

α変換やα同値の嬉しさをもっと知りたい！

ラムダ式の計算(簡約や変換)の計算ドリルがあったらいいな！

Lx(x x) Lx (x x) の無限ループくんがすごそう

無限ループができるってなんかすごそう

関数の名前がないのに再帰できるのすごい

摩訶不思議アドベンチャーな雰囲気で、なんかしらんけど、うまくいってることだけはわかる。よくよく考えるとよくわからん。

Lx.Lx.Lx.Lx.Lx.xはラムダ式だと思うんですけど、あってますか？

だれかおしえて。

シャドーイングとかのおなじ話になる？

この例がおもしろくなる話もあればぜひ。

α同値を紹介する意味がわかった！

mohiraの解釈の仕方

出発点として、計算ステップを実行したーい！ ってのがある、要はベータ簡約したい

で、ベータ簡約を雑にやると誤った変換になること ← ex: p.273

で、困ったなぁ

このときに、ベータ簡約をする前に、アルファ変換をかませておけば、ベータ簡約はちゃんとできる！

👉 アルファ変換という操作を導入することで、すべてのラムダ式がベータ簡約できる。

〜〜〜ここまで昔の理解〜〜〜

しかし、アルファ変換したときに、「アルファ変換前のラムダ式」 と 「アルファ変換後のラムダ式」が同一のものでないならば、ベータ簡約が、計算ステップを実行したいという、当初の目的を果たしてない！

なので、 「アルファ変換前のラムダ式」 と 「アルファ変換後のラムダ式」が同一のものですよ！ っていう保証が必要。その保証が出揃ったときに初めて「ベータ簡約する前にアルファ変換をかませておけばOKですよ！」って言える。

で、その保証の話が、まさに、アルファ同値の話でした！

つまりこういうこと↓↓

α同値はβ変換すると意味が変わってしまう式にα変換をすると等しいλ式に変換できることの保証という気がします
β変換できない式にα変換するとβ変換できることが嬉しさ？
https://discord.com/channels/508093437187457045/882639711447961710/1139190176992727160

mohiramohira

2023/08/24(木) 20:30-

実績

  • 8.2.9.4 Zコンビネータで無限に再帰する例

Discord開始リンク

次はどこから？

  • 次回: 8.3.2アクターの生成

MEMO

最近

  • 元気、ならばよし！ 週の中に休みがほしいやつ！
  • ペアプロの連続による学びと緊張
  • 10年ぶりの新作 AC6
  • ネタバレとの戦いと情報の遮断。ピリピリ。
  • ID0000。origin
  • 「契約による設計」をやっていく気持ちの高まり
  • 超久々のOFFLINEでのLT！

前回のおさらい

  • 評価戦略は2つ。正規順序と作用的順序
  • Haskell = 関数型 = 正規順序 = すごそう みたいな感じで覚えている。思い出せる。

正規順序の評価を使う言語ってHaskell以外にある？

ただ、実を言うとCやC++のマクロは実質的に「正規順序の評価』なんですよね。
https://discord.com/channels/508093437187457045/882639711447961710/1144235928404099072

コンビネータ？

なにかしらの計算規則。なんかうまいことやるとすごい。

気づいたら謎に計算が成功するやつ。

不動点コンビネータ

コンビネータ界の特徴的なやつ。

無限ループや再帰のための仕掛け

YコンビネータとZコンビネータ

不動点コンビネータ界隈の2大巨頭。

ラムダ計算では、YコンビネータとZコンビネータを使って再帰を実現する。

評価戦略によって、YかZが決まる。

  • 正規順序 → Yコンビネータ
  • 作用的順序 → Zコンビネータ

(Y g)とか(Z g) で、うま〜〜〜く g を設定すると再帰できたりする

すごい。けど、若干騙されたという気持ちにもなるw

しかし、数理的に正しいので、信じるとか信じないとかの話ではない。

勉強会で割り込みが入るのは最高！

ただし、交通整理はむずい！ でも、いまさら破綻はしない関係性。新しい会とかだとグランドルールで制御かな？

多重割り込みの管理。組み込みでは重要。
https://discord.com/channels/508093437187457045/882639711447961710/1144246337873915945

Eは多重集合

多重集合は、重複を許可した集合。順序がないのは集合と同じ。
アクターモデルとしては、順序は考えてないのかもしれない。

求む！ アクターコンフィギュレーションの計算規則！

アクターモデルにおける計算は、各アクターの状態、環境を変更していくことで、実行されてい く。

でも、本に書いてないーーーーーーー！

たとえば、

  • recvをしたときに、環境Eがどう変化するか？
  • 受信するデータがないときにrecvするとどうなる？(失敗？待つ？

想像すると、待つんだろうなーとは思うものの、本文に書いてない！！！

式によって、並行計算のモデル計算できるの楽しすぎる！

それはそうって話だけど、すごい！

mohiramohira

2023/09/07(木) 20:30-23:15

実績

  • p. 284 8.3.2 アクターの生成 8.3.3 変数束縛と制約

Discord開始リンク

次はどこから？

  • 次回: p.287 8.3.4 操作的意味論

MEMO

最近

  • Miroを頑張ろう！
  • 境界値テストのLT、盛り上がった。カバレッジの話もしたいよな？
  • AC6、トロコン！
  • ARMORED CORE VI 縛りプレイもやっていくよ
  • (意外と)ライト向けという話もある！ マルチプラットフォーム！
  • マルチプラットフォームのリリースは大変。プラットフォームごとに審査期間が違ったり。
  • awkの知識の限界
  • 長く続いた在宅ワークを離れて雨の日の動きを忘れるかもしれない話
  • Coqだけじゃなくて、最近は Lean 4 で証明プログラミング

おさらい: send関数 と recv関数

send(x,b) -> null

送信します。データx を アクターb に。送信したら即座にnull。

< dst <== data >

宛先アクターdst に データを送信している状態。

recv(Ly.M) -> (Ly.M x)
この話はまだでてきてない...

おさらい: アクターコンフィグレーション

アクターモデルの計算は、結局ね、「各アクターの状態」と「環境」を更新していくだけ！

で、なんかの操作の実行をしていくだけ！

で、それを、アクターコンフィグレーションなるもので、記述するってだけ！

α(アルファ)は、「アクター名から式への写像」、なんつーか、「どのアクターが、何する？」って情報が集まってるだけって感じ。

で、

α(アルファ)内の手続きをやっていくことで、「環境E」をひたすら更新してく。

環境Eには、送信中のデータの情報が多重集合として格納されている。
< dst <== data >がいっぱい入ってるだけ！ キューっぽい感じある。

あとは、 p.283の定義見て！

Q. アクターモデルでは、新しいアクターを生成したとき(new関数が実行されたと)常に、受信状態になるのか？

新しく生成されたアクターは、 new関数の引数である式 M を用いて、即座に受信状態へと移行する。

言い換えると、いきなりrecv前提しかありえないの？

たとえば、sendだけするアクターは存在してもいいのでは？ そのsendだけするアクターが存在していいと思うわけで、そうなると、いきなり絶対recv状態前提はやっぱおかしいかもしれない？

アクターがずーっと recv 状態でも問題なさそう

スレッドと同じように考えても良いかも。

口をあけたまま待っているアクターが存在してるだけでも別に問題なさそう。

letrec が ムズイ！ が、Ocamlにも同じ文法がある(そう考えるとなぜ読める感じになる)

再帰呼び出し(recursive call)を行う関数の処理をインタープリタに追加する。
OCaml では、たとえば、階乗を計算するプログラムは以下のように定義できる。
ここで let factorial ではなく、 再帰を表す rec というキーワードをつけて、 let rec factorial となっている。
http://logic.cs.tsukuba.ac.jp/jikken/recursion.html

# Ocaml
let rec factorial x =
   if x = 0 then 1 else x * (factorial (x - 1))
in factorial 5

# アクター言語はこう！ 一緒だよね！
letrec factorial = Lx.if(
		    = (x, 1),
                    1,
                    * (x, fact( - (x, 1) ))
                   )
in factorial(5)

Q. seq(e1, e0) =def= let z = e0 in e1 (zは新規) の意味が謎！

「新規」とは？ z とは一体何者？
seq(e1, e0) =def= let z = e0 in e1 (zは新規)

右辺はアクター言語の世界だから、let式を使う以上、 z=の部分が必要。

zがとても重要とかそういうイメージというよりは、一時変数っぽいものでよさそう
(たとえば、zではなく、 「受け取るけど、使わないことを表す」 _みたいな記号だとスッキリ理解できたかもしれない)

やりたいのは、糖衣構文、つまり、もっと楽な記法であって、そう考えると z は不要だから、 seq(e1, e0)みたいなsyntaxSugerになっている的な雰囲気。
(いちいちzみたいな変数書かなくてもええやん)

アクターモデルの計算では、自由変数はすべてアクターになる。

条件 1 は、式中の自由変数は有効なアクター名であることを示しており

ラムダ計算では(THE数式で書いたとすると)
f(x) = x^2 + Ax + B
の AやBは自由変数で、ふつーに登場するけど、アクターモデルでは、そういうのはない的な感じ！

強い制約だ。けど、納得できる感じ。
(なぜなら、アクターモデルとは、誰かと誰か(Actor)がメッセージ(データ)をやりとりするだけだから)

memo: ebi) 普段、未定義の変数って気にしないよね、って話。
ラムダ計算とかいう超絶抽象。ぐにゃぐにゃ感。最強粘土。

要調査：

https://discord.com/channels/508093437187457045/882639711447961710/1149332061031776266

[new(M)]a || E → [a']a,[recv(M)]a || E
newされたアクターが実行するラムダ式の最外殻がrecvになっていることで、「当該アクターが勝手に終了している」ということがないことが保証される説。

糖衣構文の嬉しさがあんまりないかもしれない話

別にラムダ計算や、アクター構文のままでも良かったのでは！？

(rec(f)は嬉しそう)

mohiramohira

2023/09/21(木) 20:30-22:30

実績

  • p. 284 8.3.2 アクターの生成 8.3.3 変数束縛と制約

Discord開始リンク

次はどこから？

  • 次回: p.290 8.3.5 バリア同期

MEMO

最近

  • 何を隠そう、私がドキュメントオタクだ！
  • 実践Vim 思考のスピードで編集しよう!
  • 思いつく --X(ここでメモリクラッシュ(記憶喪失))--> メモる
  • GoogleKeepがいい感じ。付箋っぽさあるというか、一覧性がいい感じっぽいやつの感じのやつ(曖昧)
  • Re:イラストレーション。意外としんどいけど、意外と楽しめるという話
  • AC6、順調！ 縛りプレイの話。全身ギャグのような機体
  • ゲームデザインが優れている可能性。常に難所じゃなくて、難所のあとに平坦がくると楽しい説ある。
  • アクター言語をつくろう！の会がものすごくいい感じ

そういえば、この本はなんの本？

並行プログラミングの本。
しかし、最近(8章)は計算理論ばっかりだよね？

8章は並行プログラミングというより計算理論だよね？

Yes.

8章の冒頭をよく読んでみると、意外と書いてある。

以下、mohiraの見方
並行計算モデルにはラムダ計算の導入が必須というわけではない。
ちゃんとした議論、つまり、解釈のブレなく客観的な議論をするためにラムダ計算を導入している。

で、実際に、計算練習をしてみるとそれはとてもよくわかる。
要するに、紙とペンだけで、(並行)計算の議論ができる、記述できる。

一方で、THE並行プログラミングとは？ THE並行処理とは？ みたいな話だけなら8章は読まなくていい。

で、ある程度やってみたところ、実際、数学的な記法だったり、計算理論だったり、他の文献が読めるようになってきた。いや、読めるようになるの前段階かつ最重要である読もうとする気になったのは間違いない。

じゃあ、そのために、この本がおすすめか？ っていうと、それはNO.
OcamlとかSchemeみたいな言語とか、計算理論の入門書がいいと思うよ！

letrecの計算演習

この計算規則を使って、次の4つをちゃんと計算できればいいと思う！

letrec x = v in e ->λ e{ x |-> v { x |-> letrec x = v in v} }

この6つができればいいと思う！

  1. letrec x = 1 in 2 -> ??? 置換不要
  2. letrec x = 1 in x -> ??? x を参照する
  3. letrec x = x + 1 in x + 2 -> ??? vがxを含む式
  4. letrec f = f + 1 in f + 2 -> ??? x でない名前(規則ではxを使っていたが、fにすることで結構違う)
  5. letrec f = λx(x x) in f(f) -> ??? (vがラムダ抽象; 同じ形が繰り返される。再帰の一歩手前の気持ち; 穀潰し関数;)
  6. letrec fact = λx.if(=(x, 1), 1, *(x, (fact)(-(x, 1)))) in (fact)(2) -> ??? (俺たちのラスボス; vがラムダ抽象かつ自身を参照している; vが自体が長い)

Lv3まではクリア！



アクター言語のインタプリタを実装中

https://github.com/yokotateyoko/INTERPRETER_TEST

強い記述力を求めている話

だから計算理論に興味があるんじゃ！

一方、具体的な実装は、そのときでいいじゃん？ という立場もある

ホール表記とかラベル付き遷移とは何だったのか？

計算の手順をより厳密に記述するための記法。

  • ホール表記: 次に評価される式が何かを明らかにする
  • ラベル付き遷移
    • 「→」があるときに、どの計算規則を使っているかがはっきりする
    • 「→」があるときに、どのアクターがどの計算規則を使っているかがはっきりする

よかれと思って「遷移」という用語を導入しているけど、ここは「簡約」にしておいたほうが混乱が少ないのではと思う。状態といえば遷移だよねというコロケーションがあるから遷移にしたらしい。

mohiramohira

2023/10/19(木) 20:15-22:20

実績

  • 次回: p.290 8.3.5 バリア同期

Discord開始リンク

次はどこから？

  • 次回 p.294 8.4 π計算

MEMO

最近

  • Unity始めました。Not商用ならいろいろ安心っぽい。ちょっとした趣味ならダイジョブそうな雰囲気。
  • 体調を崩す秋、体調が快方に向かう秋
  • gotanda.rbで登壇！ 技術詳細を話せなかったからこそ、逆に広まった説がある。次回は詳細を目指していくかも！
  • 見えてたほうが痛いのか、見えないほうが痛いのか問題
  • 型理論や型推論、じわじわだけど、進捗がある話。
  • ドブランインデックス。Stringは実は実装しづらさがあったりする話。
  • lean4、チューリング完全でないので、停止することが確定しないといけないという制約がある。定理証明支援系だとそういうことがよくあるらしい
  • セッション参加はレポーティングもセットやで
  • EUVを使った次世代のリソグラフィ。「リソグラフィ」は石版印刷を意味する半導体製造の技術の1つ。光を使って転写するみたいな感じらしい。フォトリソグラフィの英語表記は、「photolithography」です。「フォト」と「リソグラフィ」を組み合わせた、その名のとおり、写真の現像技術を応用したパターン作成技術のことをいいます。
  • Extreme Ultra Violot。紫外線よりも更に波長が短い → かなりのエネルギーだ！
  • 光子がとても高価になっている 無駄にしないようにしないといけないよな！ 一方で、感度を高めすぎるとムラができるので、むずい！ うまくいくと、歩留まりが高くなる。半導体の性能というよりも、半導体の生産効率につながる話らしい。
  • AC6、縛りプレイXの合間に、縛りプレイYをするくらいハマっている！ ここまで研究が続くとは！
    • → 22:36 達成！！！ ラスボスクリア！ :tada: :tada: :tada:
  • 並行処理の怪しい実装に、すぐ反応できる、すぐに指摘できるようになってきている！
  • 生の潜水艦はスゴイぞ！
  • Ghidra(ギドラ) https://www.ghidra-sre.org/ バイナリの静的解析とか。secconはCTFとかそういう世界っぽいのやつ。

Q. p.290 seqはタイポでしょ。でも、seqがあってもいいんじゃね？

A. 多分ダメっぽい。というのは、seq は、2つを受け取るシグネチャになっているから。

barrier = let x = seq(recv(λx.x )) in
	      let y = seq(recv(λx.x )) in 
	      let z = seq(recv(λx.x )) in 
	      seq(send(_ , x), send(_ , y), send(_ , z))

でも、気持ちとしては、1個だけ実行なので、わかるといえばわかる。

lex x = e0 in e1 がスラスラ読めるようになれば、バリア同期の「バリア」感がわかる

let x = e0 in e1 ⇔ λx. e1(e0)

なので、 e0を先に処理(簡約)しないといけない

これが、バリア同期の「バリア感」の肝心なところ
[sync: a,b,x] は、1stepで(=同時に、同期的に)、簡約(遷移)がおきてるのがポイント！

barrier = let x = seq(recv(λx.x )) in
	      let y = seq(recv(λx.x )) in 
	      let z = seq(recv(λx.x )) in 
	      			seq(send(_ , x), send(_ , y), send(_ , z))

↑

seq(send(_ , x), send(_ , y), send(_ , z)) ← いわば後半？

をやるには、 xとyとzを先に処理する必要がある ← 待ってるじゃん！ バリアじゃん！

p.293の syncRecv(f)は誤植じゃね！

形式的な議論の価値を感じた話

このバリア同期方法には 1 つ問題がある。それは、 recvAck 中に応答以外のメッセージ を受信した場合、そのメッセージは破棄されてしまう。これは、この式中の式 M で必要だったか もしれないデータが破棄されることを意味しており、さらに、通信に損失があることを意味してい る。

「Aさん以外からのメッセージを受け取りません！」ってなっちゃう

ちゃぶ台がえし感はある。が、形式的な議論の価値を感じたなり

アクターモデルという非同期のモデルで、同期的なことを考えて、議論している感じがあるから。

mohiramohira

2023/11/02(木)

実績

  • 8章の最初から8.2.5の終わりまで読み直してました。

Discord開始リンク

次はどこから？

  • 次回 p.294 8.4 π計算

MEMO

mohira、結局、出席できず！

申し訳ないです！

会としては破綻しないのはよいこと！ みなさんのおかげ。

それはそれとして、態度をハッキリしないのはダメなのでそこは改善(イエローカード)

mohiramohira

2023/11/16(木)

実績

  • 8.4 π計算 から 8.4.4 α変換 まで

Discord開始リンク

次はどこから？

  • 次回: 8.4.5 操作的意味論

MEMO

最近

  • YAGNI的仕事術
  • Haskell流仕事術
  • ギリギリまでやらない vs めちゃくちゃ余裕をもってやる
  • 高まる数学力！
  • GitHub Copilot と Copilot Chat
  • リアルタイムレンダリング
  • めちゃくちゃ終盤から勉強会に参加！(ありがたい！)
  • 「AC6ができないので、AC6をすることにした」 ← ポルナレフ
  • そうだ、神戸に行こう

Discordのエコーかかる問題！

なんじゃこりゃ！！！

π計算は並行計算モデル

  • π計算は、円周率とは関係ないよ。
  • π計算は、並行計算モデルだよ
  • π計算は、ラムダ計算と等価だよ。チューリング完全だよ。

Hindley-Milner型推論 あるいは Damas-Milner 型システム

https://zenn.dev/ksrk/articles/5e4a6858c43d6f

形式的な記述の威力(3回目)

↑
これが
こうかける(Texで書きたかった)
↓

P + Q PとQの非決定的実行の解釈がむずい

P ＋ Q という記述は、プロセス P と Q の非決定的な実行を意味する。すなわち、 P → P かつ Q → Q と、P と Q の両方ともが遷移可能になった場合、 P + Q → P または P + Q → Q の どちらかに遷移する。

たとえば、 P -> P' の遷移が選ばれた場合、プロセスQは消える！(プロセスが消えるという言い方が正しいかは謎)

この文章での「または」は「どちらも起こりうる」ではなく、「どちらか一方のみ起こる」という日常生活会話の「または」という感じ。論理学の「または」とは違う。

p.298の「分配」の意味が実は特定できてない

結論としては、

(vc)(P+Q) と (vc)P + (vc)Q は等価ではないはず。同じチャネルができちゃうのは違うでしょ！ ってこと。

定義は冷静にゆっくり読むと上達するのでしっかりやるといいぞ！

そうだな！

mohiramohira

2023/11/30(木)

実績

  • 8.4.5 操作的意味論 から p.308 第1段落まで

Discord開始リンク

次はどこから？

  • 次回: p.308 第2段落から

MEMO

最近

  • 気温の乱高下で体調がイマイチ！
  • アドカレ締切迫る！
  • Copilot の威力。あやふやなことを調べる時間がゼロ！ 学習の難しさや負担の減少は技術選定に大きく影響する説
  • 英語の勉強も継続している

送信は txは、transmit/transmitter

変数名で、送信はtx、受信はrxとするのは慣習っぽい。

π計算の形式的な記述もなれてきて結構読めてきた

これはちゃんと読んでるからこそ。楽しいね。

Rustのコードは、形式的な記述のままって感じ！(Rustの文法はわからんけど！)

でも、π計算の意味というか掘り下げがほし〜い！

この本の範囲外なんだけどね。
この本はあくまで入門。

チャネルを使ったバリア同期なら共有変数が不要

1つは「共有変数をつくって、プロセスが完了するたびにインクリメント。共有変数が一定に達したら抜ける」ってやつ

チャネルの場合、ブロックする(？)から、これでもバリア同期を実現できる。

実現方法が複数わかるのも楽しいよね。

「チャネルa を使って チャネルs を渡す」がわかるといける

チャネルを通じて、チャネルも渡せる。

Goで書くと、コレを区別しましょうって話。

var x chan int
var y chan chan int

単項π計算で、多項π計算をエミュレートできる

p.304をちゃんと読めばわかる。

「逐次」と「同時」を区別するのが大事やな。

『リアルタイムレンダリング』

正規直交基底をつくるときに、「正規化」しなくていいらしい。そして、それにまつわる問題も今は解決されている。

投機的実行の話も絡んでくる…！

https://tyfkda.github.io/blog/2017/09/07/onb-revisited.html

Duff's Device

GNU AWKのハッシュ処理でダッフズデバイス使われてます。

AWKは庭。

次回で、全部おわりそう！？

お〜、感慨深い。

そして、来年以降はどうする？？？

隔週開催のペースがちょうどいい話

毎週はちょっとしんどい。
隔週くらいがちょうどいい。

隔週になると「近況」がおもしろくなるというのもある！

mohiramohira

2023/12/14(木)

実績

  • p.308 〜 8章ラストまで + あとがき → 完結！

Discord開始リンク

次はどこから？

  • Eps

MEMO

最近

  • ストレッチがつまらないので解剖学を勉強し始めたけど、結局ストレッチはしてない
    ‐ 梅田にバーガーキング出現！ バーガーキングに行ってみよう。
  • AC、AC、AC。まだまだ味のするガム。
  • 味がする → 味がなくなる → 無 → 無から有を生み出す!?!?
  • TAPLをTypeScriptでやる勉強会 https://tsplay.dev/W4J87N
  • みんな元気でえらい。物理を履修なう。偏微分方程式を解こう！

完結！ 2年3ヶ月の54回

今日の雑メモ

セッション型をやりました。

本の振り返り

  • 幅広い話題を扱っていて、よい。入門書という感じ。よい。
  • 特に、8章の並行計算モデル(ラムダ計算、アクターモデル、π計算)を扱っている最近の和書は(たぶん)存在していないので価値があると思う。
    • でも、理論をやったあとの話が載ってないので消化不良と言えばそう(入門書だから仕方ないけど)
  • すべてを理解したとはとても言えないけど、並行プログラミング領域の地図やらindexやらのイメージがかなり見えてきた感じ。
  • いろいろ忘れているけど、忘れたことは覚えている。それでいいのだ。
  • Rustを同時に学べる本ではない。
  • Rustだったり並行処理だったり何かをマスターしているとかなりスムーズに行けると思う
  • ツッコミどころはいろいろある
    • 私おーひら的には、文章と図解はイマイチなところが多いと思ってます！

typo ← 年内にPRおくりたい

その1

その2

このスクラップは4ヶ月前にクローズされました