c - 带线程的递归 Fib，段错误？

Question

有什么想法为什么它适用于 0、1、2、3、4... 这样的值，而对于 >15 这样的值会出现段错误？
＃包括
＃包括
＃包括

void *fib(void *fibToFind);

main(){
pthread_t mainthread;

long fibToFind = 15;
long finalFib;

pthread_create(&mainthread,NULL,fib,(void*) fibToFind);

pthread_join(mainthread,(void*)&finalFib);

printf("The number is: %d\n",finalFib);
}


void *fib(void *fibToFind){
long retval;

long newFibToFind = ((long)fibToFind);

long returnMinusOne;
long returnMinustwo;

pthread_t minusone;
pthread_t minustwo;

if(newFibToFind == 0 || newFibToFind == 1)
return newFibToFind;

else{
long newFibToFind1 = ((long)fibToFind) - 1;
long newFibToFind2 = ((long)fibToFind) - 2;

pthread_create(&minusone,NULL,fib,(void*) newFibToFind1);
pthread_create(&minustwo,NULL,fib,(void*) newFibToFind2);

pthread_join(minusone,(void*)&returnMinusOne);
pthread_join(minustwo,(void*)&returnMinustwo);

return returnMinusOne + returnMinustwo;

}

}

Answer 1

内存不足(堆栈空间不足)或有效的线程句柄？

您需要大量线程，这需要大量堆栈/上下文。
Windows(和 Linux)有一个愚蠢的“大[连续]堆栈”的想法。

从关于 pthreads_create 的文档:
“在 Linux/x86-32 上，新线程的默认堆栈大小为 2 兆字节。”
如果您制造 10,000 个线程，则需要 20 Gb 的 RAM。
我构建了一个 OP 程序的版本，它被一些 3500 (p) 个线程轰炸了
在 Windows XP64 上。

有关为什么大堆栈是一个非常糟糕的主意的更多详细信息，请参阅此 SO 线程:
Why are stack overflows still a problem?

如果您放弃大堆栈，并使用堆分配实现并行语言
用于激活记录
(我们的 PARLANSE 是
其中之一)问题消失了。

这是我们在 PARLANSE 中编写的第一个(顺序)程序:

(define fibonacci_argument 45)

(define fibonacci
   (lambda(function natural natural )function 
   `Given n, computes nth fibonacci number'
      (ifthenelse (<= ? 1)
           ?
         (+ (fibonacci (-- ?))
              (fibonacci (- ? 2))
           )+
   )ifthenelse  
   )lambda
 )define

这是在 i7 上运行的执行:

 C:\DMS\Domains\PARLANSE\Tools\PerformanceTest>run fibonaccisequential
 Starting Sequential Fibonacci(45)...Runtime: 33.752067 seconds
 Result: 1134903170

这是第二个，它是并行的:

(define coarse_grain_threshold 30) ; technology constant: tune to amortize fork overhead across lots of work

(define parallel_fibonacci
   (lambda (function natural natural )function 
   `Given n, computes nth fibonacci number'
      (ifthenelse (<= ? coarse_grain_threshold)
           (fibonacci ?)
           (let (;; [n natural ] [m natural ]  )
                   (value (|| (= m (parallel_fibonacci (-- ?)) )=
                              (= n (parallel_fibonacci (- ? 2)) )=
                          )||
                          (+ m n)
                   )value
           )let
       )ifthenelse  
   )lambda
)define

使并行性显式也使程序更容易编写。

我们通过调用 (parallel_fibonacci 45) 测试的并行版本。这里
是在同一个 i7 上运行的(可以说它有 8 个处理器，
但它真的是 4 个超线程处理器，所以它真的不是 8 个
等效 CPU):

C:\DMS\Domains\PARLANSE\Tools\PerformanceTest>run fibonacciparallelcoarse
Parallel Coarse-grain Fibonacci(45) with cutoff 30...Runtime: 5.511126 seconds
Result: 1134903170

接近 6+ 的加速，对于不完全是 8 的处理器来说还不错。另一个
这个问题的答案运行了 pthreads 版本；花了“几秒钟”
(爆炸)计算 Fib(18)，这是 Fib(45) 的 5.5 秒。
这告诉你 pthreads
是进行大量细粒度并行性的根本不好的方法，因为
它有非常非常高的 fork 开销。 (PARLANSE 旨在
最小化 fork 开销)。

如果您将技术常量设置为零(每次调用时 fork )，则会发生以下情况
到 fib):

C:\DMS\Domains\PARLANSE\Tools\PerformanceTest>run fibonacciparallel
Starting Parallel Fibonacci(45)...Runtime: 15.578779 seconds
Result: 1134903170

您可以看到分摊 fork 开销是一个好主意，即使您有快速 fork 。

Fib(45) 产生大量的 Cereal 。堆分配
激活记录解决了 OP 的一阶问题(每个线程数以千计)
1Mb 的堆栈会燃烧 GB 的 RAM)。

但是还有一个二阶问题:2^45 PARLANSE“grains”也会烧掉你所有的内存
即使您的 Cereal 控制块很小，也只是跟踪 Cereal 。
因此，拥有一个调度程序可以帮助您在拥有“很多”时限制 fork
(对于“很多”的某些定义，明显少于 2^45) Cereal 以防止
用“粒度”跟踪数据结构淹没机器的并行性爆炸。
当 Cereal 数量低于阈值时，它必须取消 fork
同样，为了确保总是有很多逻辑的、并行的物理工作
CPU 来做。