V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
RoccoShi
V2EX  ›  Go 编程语言

新手问一个 go 实现并发素数筛的问题

  •  
  •   RoccoShi · 23 天前 · 1235 次点击
    func Filter(in <-chan int, out chan<- int, prime int) {
    	for {
    		i := <-in
    		if i%prime != 0 {
    			out <- i
    		}
    	}
    }
    
    func Generate(ch chan<- int) {
    	for i := 2; ; i++ {
    		ch <- i
    	}
    }
    
    func main() {
    	ch := make(chan int)
    	go Generate(ch)
    	// print the first 10 prime numbers
    	for i := 0; i < 10; i++ {
    		prime := <-ch
    		println("next prime = ", prime)
    		ch1 := make(chan int)
    		go Filter(ch, ch1, prime)
    		ch = ch1
    	}
    }
    

    func Filter(in <-chan int, out chan<- int, prime int) {
    	for {
    		i := <-in
    		if i%prime != 0 {
    			out <- i
    		}
    	}
    }
    
    func main() {
    	ch := make(chan int)
    	go func() {
    		for i := 2; ; i++ {
    			ch <- i
    		}
    	}()
    
    	for i := 0; i < 10; i++ {
    		prime := <-ch
    		println("next prime = ", prime)
    		ch1 := make(chan int)
    		go Filter(ch, ch1, prime)
    		ch = ch1
    	}
    }
    

    运行后发现上面的代码可以实现并发素数筛的功能, 但是下面的闭包写法就不行, 有没有大佬解释一下?

    9 条回复    2024-10-30 22:16:50 +08:00
    kkk9
        1
    kkk9  
       23 天前
    😅 func Filter(in int, out int, prime int) PLEASE!!!
    hingle
        2
    hingle  
       23 天前
    go func(ch chan<- int) {
    for i := 2; ; i++ {
    ch <- i
    }
    }(ch)
    mainjzb
        3
    mainjzb  
       23 天前
    ch = ch1
    这行导致的

    。。这写法
    RoccoShi
        4
    RoccoShi  
    OP
       23 天前
    @hingle 这样确实是可以的, 但是我想问的其实是原来错误的写法里, 闭包内部的这个 ch 的生命周期到底是什么样的😂
    RoccoShi
        5
    RoccoShi  
    OP
       23 天前
    顺便说一下, 源代码来自 rob pike 的一次分享:
    &t=821s

    以及可以在 reddit 上的这个回答查看正确版本的详细数据流分析: https://www.reddit.com/r/golang/comments/434zry/help_understanding_this_prime_sieve_concurrent/
    grzhan
        6
    grzhan  
       22 天前   ❤️ 1
    这应该单纯是个闭包问题:

    1. ch 变量本质上是个 *hchan ( https://github.com/golang/go/blob/ed035af7b7d7c1cd2e6f852e22a9b04fc2a2cc65/src/runtime/chan.go#L34 ),是指向 make(chan int) 也就是 runtime.makechan 创建的 hchan 的指针。

    2. 直接使用闭包引用 ch ,ch 发生了内存逃逸(因为是 go func ,我 -gcflags="-m" 看了下确实逃逸到了堆),你在闭包 go func 中使用 ch ,就是在操作 ch 指向的 hchan 。

    3. main 函数后续 ch = ch1 , 也就是 ch 指向了原本 ch1 指向的 hchan ,导致 go func 操作的 hchan 也发生了变化,进而整体程序没有按照预期执行。

    4. 而正确的实现 Generate(ch),以及 func(ch){...}(ch) ,是函数传参,是将 ch 变量值复制传入到了 Generate 或者 go func 里。

    如果你去看汇编,这次 ch 就分配在栈里( main.ch+40(SP) ),在运行 go func 之前就把它的值复制到寄存器里供函数使用了 ( MOVQ main.ch+40(SP), CX )。因此后续 main 里 ch 针对 hchan 的指向发生变化不会影响 go func 内部,值复制保证 go func 内部指向的 hchan 不变。


    感兴趣自己可以看下汇编研究下,我也只是大致看了下:go tool compile -S main.go > assembly.s
    RoccoShi
        7
    RoccoShi  
    OP
       22 天前 via iPhone
    @grzhan 👍👍解释的很清楚
    grzhan
        8
    grzhan  
       22 天前   ❤️ 2
    说起来这个 Rob Pike 的素数筛法应该思路就是当年 CSP 1978 这篇论文提到的素数算法,以前欧长坤老板做过 CSP 1978 论文解读的分享,里面就有素数筛法的例子,论文当然是自己的 CSP 语言,而他写了个 Go 版本:
    https://github.com/changkun/pkg/blob/f787593b4467793f8ee0b07583ea9ffde5adf2be/csp/csp.go#L833
    kingcanfish
        9
    kingcanfish  
       22 天前   ❤️ 2
    @grzhan #8 https://swtch.com/~rsc/thread/ 补充下 Russ Cox 的文章 顺便提一嘴 xv6 有个实验就是实现这样的素数筛
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1173 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 18:12 · PVG 02:12 · LAX 10:12 · JFK 13:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.