我已经修补BSP树已有一段时间了，并且还在玩线程。将三角形添加到BSP树中时，就有机会创建一个新线程以并行处理数据。

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    insert(frontpiece, bspnode.front)
    insert(backpiece, bspnode.back)
  }
  ....
}

上面的两个插入操作可以由两个线程执行，并且由于它们不修改相同的数据，因此可以使用便宜的同步。

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    handle = beginthread(insert(backpiece, bspnode.front))
    insert(frontpiece, bspnode.back)
    if(handle)
    {
      waitforthread(handle)
    }
    else
    {
      insert(backpiece, bspnode.front)
    }
  }
  ....
}

此新方法尝试创建一个线程以并行完成操作，但是如果无法创建该线程，则该方法不应失败(它将简单地还原为原始算法)。

这是一种良好的编程习惯，还是我使用线程的方式不正确？我没有找到有关此技术的任何文献。我喜欢它趋向于充分利用我的CPU(2个内核)，并且理论上可以扩展到任意数量的可用处理器。我不喜欢这在CPU和内存上可能是非常浪费的。

解决方案

如果处理的某些部分正在外部(用户输入，I / O，某些其他处理)上等待，则线程很棒，正在等待的线程可以继续等待，而没有等待的线程则在继续前进。

但是，对于处理密集型任务，实际上比处理器更多的线程会产生开销。看来线程正在完成所有" CPU工作"，所以我会坚持每个核心测试一个线程来找到最佳数量。

创建的最大开销来自上下文切换(冻结一个线程并加载下一个线程的执行上下文)，以及线程执行具有不同内存的任务时(如果线程可以有效地使用CPU缓存)缓存丢失。

最好的选择是创建一个线程池，然后"透明地"使用它来添加节点。

例如，在程序启动时创建2个线程，让它们等待信号量或者事件。当我们有要添加的节点时，可以将数据弹出到队列中，然后触发信号量。这将唤醒其中一个线程，该线程将数据弹出队列并执行处理。 (确保对队列的访问是线程安全的，并且与关键部分完全同步是最好的)。

在将数据复制到队列中并运行额外的线程时，应用程序的整体性能会变慢，因为我们有更多的开销，但是如果我们以前在单个内核上运行，则现在将在2上运行。如果线程化，则效果最好处理很昂贵。

当然，例如，Quicksort可以很容易地编程为多线程，并在多核系统上获得了较大的性能提升，而在非多线程系统上则获得了一些小的性能损失。请记住，我们现在要增加两次开销，一次是在堆栈上保存递归，另一次是在线程上保存，因此，如果要进行大量递归，那么与非多线程方法相比，它可能使系统崩溃更快。