|
锁定老帖子 主题：多线程是个不靠谱的东西
该帖已经被评为精华帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-05-08
引用 一个函数内，上下的关联度是很高，如果 b 是lazy，那么c 也lazy，涉及到c 的表达式都lazy，这跟没做计算有什么区别？
这个问题叫做strictness analysis.这种分析在编译器的前端都已经做掉了，那些东西Lazy,那些东西strict. 真正的求值器从最下端节点开始往上规约的时候，总是规约strict节点. 像C中 a=6+6 b=a*2; c=a+b; FP中都是这么写 f(x)= let a=x+x;b=a*2 in a+b 编译器分析的时候 就已经把let当中的两个表达式解析为子节点，把a=x+x解析为最左的子节点也就是strict节点。在这样一张图里，求值器没有机会spark其他的核心进行辅助求值。 但是你要是这么写 f(x)= let a=x+x;b=a*2； c=a+b in if g(c)>10000 then c else if h(c)>9999 then c*2 else f(c) 这里就会出现多个strict节点，因为g(c)，h(c)要做comparison 必须是strict的。而f(c)则是non-strict的。 这个时候，当前的reducer就会把g(c),h(c)切割到一个叫working pool的东西里去。自己发现没有可求值的东西就转到下一个表达式。如果这个时候有并行跑着的reducer，就会从working pool里面去拿表达式，进行求值。 这套方法，就如Elminster所说已经是烂熟了。 引用 理想是希望整个求值过程等于关键路径的耗时，不过前提是总有空闲的核可用，还不算任务创建切换等耗时
至于这个问题，涉及到granularity analysis。这个方面还属于hot-open problem.有几种方向，一种是complexity analysis。这一路基本上很难，成果很少。目前好像只能对小规模的程序进行编译分析. 还有一种是用上面的strictness analysis的结果来进行time analysis.但是这仅对于strict time analysis阶段可以在编译阶段进行复杂性分析。但是对于lazy time analysis目前还是一个比较难的问题. 我觉得这个问题其实和c++的inline很有些相似。除了理论上的研究的static automatic Annotation以外。一般都是腿而求其次,一种方法就是通过Annotation，类似于Pfor这样的语言的标签通过人工干预。另一种方法就是通过统计，也就是类似JIT处理method inline的方式，程序第一次运行未必会帮你全面并行化，但是经过一定时间的运行以后可以通过函数调用统计，分析出那些粒度过细，那些粒度正好合适. 还有另外一种方法也是在runtime的时候分析。主要通过work stealing来实现.当一个函数f()求值的时候会产生一批图节点,这个时候当前的reducer如果忙于对一个node求值，那么其他idle的reducer，就把其他未求值的node steal过来求值.比如说fib(1000),第一个reducer产生fib(999),fib(998),第二个reducer就会过来steal fib(998).第二个reducer又会unwind fib(997),fib(996),第三个reducer又来steal fib（996），以此类推. 但是这一切的一切，都基于一个前提，必须没有副作用. |
| 返回顶楼 | |
|
发表时间：2008-05-08
Trustno1 写道 但是你要是这么写 f(x)= let a=x+x;b=a*2； c=a+b in if g(c)>10000 then c else if h(c)>9999 then c*2 else f(c) 这里就会出现多个strict节点，因为g(c)，h(c)要做comparison 必须是strict的。而f(c)则是non-strict的。 这个时候，当前的reducer就会把g(c),h(c)切割到一个叫working pool的东西里去。自己发现没有可求值的东西就转到下一个表达式。如果这个时候有并行跑着的reducer，就会从working pool里面去拿表达式，进行求值。 收藏了. h(c) 为什么是 strict 的 ? 如果 g(c)>10000 条件满足了,就可以不用执行 h(c) 了吧? 有了comparison, 就一定是strict的吗? 有没有这方面的资料 link ? --------------------------------------- 问一个基础的问题. 编译器/VM处理Lazy Node的时候,最终会产生一个 Thunk 结构 (Lazy Singleton). 在运行的时候,这个Thunk结构,应该也会遇到和Lazy Singleton类似的同步锁问题.
Thunk {
value = null;
getValue() {
if value == null
value = calculate()
return value
}
}
这种情况下,VM是如何处理的? 如何才能够达到无副作用,无状态, 无并发竞争, 能够被并行调度? |
| 返回顶楼 | |
|
发表时间：2008-05-08
引用 h(c) 为什么是 strict 的 ?
如果 g(c)>10000 条件满足了,就可以不用执行 h(c) 了吧? 有了comparison, 就一定是strict的吗? 这里的确有些问题 h(c)应该还是lazy的 不过你这么写 if g(c)>h(c) then 那么就应该是strict的 comparison,其实和+一样，都是语言中的atomic 算符，遇到这种节点都是强迫求值的. 引用 Thunk {
value = null; getValue() { if value == null value = calculate() return value } } 这个value如果是arugment，那么strict analysis的时候自动会把它算做lazy,只有当value求值完成以后才能unwind到下一个节点. |
| 返回顶楼 | |
|
发表时间：2008-05-08
Trustno1 写道 引用 Thunk {
value = null; getValue() { if value == null value = calculate() return value } } 这个value如果是arugment，那么strict analysis的时候自动会把它算做lazy,只有当value求值完成以后才能unwind到下一个节点. e, 就是说, 只有strict node才可以被多核并行执行. Lazy node有可能涉及到状态,因此不能被多核并行执行. |
| 返回顶楼 | |
|
发表时间：2008-05-08
buaawhl 写道 Trustno1 写道 引用 Thunk {
value = null; getValue() { if value == null value = calculate() return value } } 这个value如果是arugment，那么strict analysis的时候自动会把它算做lazy,只有当value求值完成以后才能unwind到下一个节点. e, 就是说, 只有strict node才可以被多核并行执行. Lazy node有可能涉及到状态,因此不能被多核并行执行. 不明白，什么叫做lazy node 涉及状态 |
| 返回顶楼 | |
|
发表时间：2008-05-08
Trustno1 写道 buaawhl 写道 Trustno1 写道 引用 Thunk {
value = null; getValue() { if value == null value = calculate() return value } } 这个value如果是arugment，那么strict analysis的时候自动会把它算做lazy,只有当value求值完成以后才能unwind到下一个节点. e, 就是说, 只有strict node才可以被多核并行执行. Lazy node有可能涉及到状态,因此不能被多核并行执行. 不明白，什么叫做lazy node 涉及状态 只有当value求值完成以后才能unwind到下一个节点. 这个意思就是说, Lazy 的执行结点,必须遵守一定的执行顺序.这就涉及到了状态 (反映到具体实现,就是Thunk里面的那个value成员变量). Right ? 正是因为Thunk有状态, Lazy Node才不能并行执行. Right ? |
| 返回顶楼 | |
|
发表时间：2008-05-08
引用 只有当value求值完成以后才能unwind到下一个节点.
这个意思就是说, Lazy 的执行结点,必须遵守一定的执行顺序.这就涉及到了状态 (反映到具体实现,就是Thunk里面的那个value成员变量). Right ? 正是因为Thunk有状态, Lazy Node才不能并行执行. Right ? Lazy 节点在unwind之前根本不存在.跟状态有什么关系，一旦展开就说明value已经经过求值了. |
| 返回顶楼 | |
|
发表时间：2008-05-08
Trustno1 写道 Lazy 节点在unwind之前根本不存在.跟状态有什么关系，一旦展开就说明value已经经过求值了. Unwind的具体含义是 展开运行? Lazy节点是什么时候求值的呢? 是否说, 执行节点的执行方式有 unwind 和 wind 两种方式? Lazy节点只能在 wind 方式下运行? |
| 返回顶楼 | |
|
发表时间：2008-05-08
buaawhl 写道 Trustno1 写道 Lazy 节点在unwind之前根本不存在.跟状态有什么关系，一旦展开就说明value已经经过求值了. Unwind的具体含义是 展开运行? Lazy节点是什么时候求值的呢? 是否说, 执行节点的执行方式有 unwind 和 wind 两种方式? Lazy节点只能在 wind 方式下运行? 不是，strict和non-strict的区别仅在于，你从什么方向对图遍历。 比如说square(2+3),sqaure x=x*x. unwind出来就是这一颗树。 如果你bottom up，从最左边的child往上遍历，那么就必须展开square,就是strict的 如果你做top-down,从最右边的root往下遍历，那么就无需展开square,就是non-strict的. 如果你是一个non-strict的语言，那么编译器会分析这张图，然后发现square是non-strict sub-expression，2+3就是一个strict sub-expression.然后再run time的时候根据一定的策略，把所有已经分析出来的sub-expression并行求值. |
| 返回顶楼 | |
|
发表时间：2008-05-08
Trustno1 写道 不是，strict和non-strict的区别仅在于，你从什么方向对图遍历。 比如说square(2+3),sqaure x=x*x. unwind出来就是这一颗树。 如果你bottom up，从最左边的child往上遍历，那么就必须展开square,就是strict的 如果你做top-down,从最右边的root往下遍历，那么就无需展开square,就是non-strict的. 如果你是一个non-strict的语言，那么编译器会分析这张图，然后发现square是non-strict sub-expression，2+3就是一个strict sub-expression.然后再run time的时候根据一定的策略，把所有已经分析出来的sub-expression并行求值. 前面你写的内容,好像是说, Lazy语言执行是Top Down, Strict语言执行是Bottom Up. Top Down可以合并共享Node,因此可以规约为图. Trustno1 写道 (lambda x:x+3) (x+2) Apply alpha[x/y]: lambda z . (lambda y . y+z)) (x + 2) Apply beta: (lambda y . y + x + 2) 3 Apply beta: 3 + x + 2. 对于任何一个纯函数，都能表达为lambda式。对lambda 式可以使用树规约或者图规约. 前者是串行的而后者是天然并行的 比如说这是一个典型的bottom up树规约 ((2 + 2) + (2 + 2)) + (3 + 3) = ((2 + 2) + 4) + (3 + 3) = (4 + 4) + (3 + 3) = (4 + 4) + 6 = 8 + 6 = 14 或者构造一个的top down树规约 ((2 + 2) + (2 + 2)) + (3 + 3) = ((2 + 2) + (2 + 2)) + (6) = ((2 + 2) + 4) + 6 = (4 + 4) + 6 = 8 + 6 = 14 这两种规约都是一颗树
+
+ +
+ + 3 3
two two two two
树规约可以转化为图规约，图规约可以共享子表达式
+
+ +
? ? 3 3
+
two two
因此在图规约下，2+2和3+3互不依赖，可以并行执行. 执行的过程中,父节点需要依赖子节点的执行. 如果是 Bottom Up, 父节点就执行子节点进行求值. 如果是 Top Down, 父节点就是展开(Unwind)子节点. 我想知道的是, 在Top Down的过程中, 父节点展开(Unwind)子节点的时候, 如果遇到一个 Lazy Node, 那么就不会展开,而是直接进行求值.就是说Lazy Node的执行就是要遵守Bottom Up的方式了. 是这样吗? |
| 返回顶楼 | |
