免费的狗食！

     在Google工作的好处之一，是有免费的午餐供应。不过不是每个幸运的混蛋都能被Google雇用，即便如此，我们这些不幸的混蛋也不必过度伤心，从四楼跳下，因为我们还有免费的狗食！现在我就来介绍一道免费狗食的制作方法。
  今天我们这道免费的狗食，叫“x86 Windows下基于C语言的并发非确定性计算”。名字很吓人，道理很简单。比如你在正常的C语言里写：
  x = y
  那么程序执行到这里，就把y的值放入变量x的位置，然后继续执行。有了非确定性计算，程序可以这样写（大意）：
  x = choose y1 y2 ... yn
  程序执行到这里就“分叉”了，其中一个分支把y1的值放入变量x的位置然后继续，另一个把y2的值放入变量x的位置然后继续，以此类推，有n个分支。而n个分支中，堆栈上其它变量的值都是一样的。这就给我们提供了一个并行运算的好机会－－如果我们的芯片是双核的，我们可以用两个线程分别执行x为y1和x为y2的分支，并且把其它分支暂时“冻结”起来，等某个线程完成手头的工作再取出来执行。这样就较平均的把计算任务分配到各个核上，而程序只需关注业务逻辑。
  
  要使用非确定性计算，首先请包含NativeContinuation.h头文件，构建程序的时候需要编译并链接入NativeContinuation.cpp。
  然后定义一个这样的非确定性计算函数，
  void __stdcall f()
  注意__stdcall不可以省略，这个函数不可以定义成cdecl或其它call convention。
  在这个函数里就可以使用前面提到的choose了（翠花，上狗饼干）。NativeContinuation.h声明了这样一个函数：
  size_t __stdcall AmbChoose(size_t* arrChoice, size_t szChoice);
  可以在一个数组的size_t值中进行选择。比如：
  int y[] = {1, 2, 3, 4};
  int x = (int)AmbChoose((size_t*)y, sizeof(y)/sizeof(y[0]));
  要运行这个非确定性函数时把其地址传递给：
  void RunAmb(int numThreads, void (__stdcall *ambFunc)());
  这个函数的第一个参数代表使用的线程数量，建议传递USE_NUM_OF_PROCESSORS，表示线程数量等于核的数量，比如在双核芯片上就自动使用两个线程，4核芯片就有4个线程。
  
  在看一个具体的例子之前，介绍一下实现方法。这个非确定性计算工具是用C++，Windows线程API和一点点嵌入的汇编实现的。它强烈依靠Visual C++编译器生成代码的方式，因此移植性较差（不然为什么叫狗食呢）。这个工具主要由以下三砣构成：
  1.一个线程安全的队列。AmbChoose可以一下子分出无限多支，而线程的数量是固定的，因此需要把来不及处理的分支放入队列。
  2.AmbChoose函数。AmbChoose负责“分叉”。它首先计算出调用AmbChoose前的EBP和ESP寄存器的值，在这两个指针之间的内存就是非确定性计算函数f（AmbChoose的调用者）的堆栈。AmbChoose复制这段堆栈，并获取调用AmbChoose的指令的下一个指令的地址（即在AmbChoose中执行ret指令后EIP将指向的地址），连同传给它的选择数组，一起放入前述队列中。AmbChoose返回选择数组的第一个元素，即当前线程执行第一个分支。
  3.线程函数。线程函数从队列中取出一个分支。其中包含三个信息：一个复制来的堆栈，一个EIP寄存器的值，一个选择数组的元素。线程函数将堆栈再次复制到自己的堆栈顶部，将选择元素放入EAX寄存器，然后跳转到记录的EIP值。这样做的效果，就相当于f在执行过程中，刚从对AmbChoose的调用返回，且返回的值是选择数组中的一个。为了让f执行完后线程函数再次得到控制权，线程函数做了一点手脚－－它在复制堆栈的时候把返回地址篡改成了跳转指令的下一个指令的地址，这样f一旦return控制就返回到线程函数了。如此循环，直到所有分支执行完毕。
  
  最后是一个稍微有点意义的例子，我们试图用非确定计算解决这个问题。为了节省篇幅，只说明一下核心部分。
  我们用回溯搜索找答案。试图把A，B，C，D，E从头填入数组Answer ans[]中，然后用函数
  bool check(Answer ans[], int assigned_end)
  检查填入的答案是否能符合题的要求，第二个参数是填入答案的数量，如果填满且符合要求，就找到了这个问题的一个解。你能看出来吗，以下C代码是一个并发回溯搜索！没有堆栈，没有递归，没有线程！
   enum Answer { A, FIRST_ANSWER = A, B, C, D, E, LAST_ANSWER = E, UNKOWN};
  
   const Answer choices[] = {A, B, C, D, E};
  
  void __stdcall SolvePuzzle()
  {
   Answer ans[NUM_CONSTRAINTS];
  
   for (int i=0; i<NUM_CONSTRAINTS; i++) {
   ans[i] = (Answer)AmbChoose((size_t*)choices, sizeof(choices)/sizeof(choices[0]));
   //OutputDebugStringA("choosed");
   if (!check(ans, i+1)) return; // bad choice
   // else this choice of ans[i] is good
  
   if (i==NUM_CONSTRAINTS-1) {
   // all answers are good
   dumpAnswers(ans);
   }
  
   }
  }
  使用这个工具时要注意：
  1.它只确保堆栈被原封不动的保存，但是各个分支对全局变量的影响是互相可见的
  2.turn off Buffer Security Check when compiling, using "/GS-"
  3.stack is shallow-copied, no C++ object semantics implemented, no user functions like cctors are called
  4.local pointers to local variables will be broken
  5.在这样的代码中
  g(h1(), AmbChoose(...), h2())
  如果g的call convention是正序压栈的，那每个分支都要调用h2()一次；如果逆序，每个分支将调用h1()一次
  6.损失效率的两个地方：每次要拷贝整个堆栈和线程安全队列中的线程锁
  
  最后谈谈这个工具可以怎么发展。要想解决诸多问题，有三条路可走：
  1.扩展语言。把AmbChoose作为一个keyword加入语言中。这需要改编译器。现在看来可行的办法有二个：一个是hack GCC，二是用Microsoft Phoenix这样的编译器工具包。
  2.在.NET上实现这个工具。这样我们就可以动态的检查metadata，获得编译器的能力。这样做也要损失效率，但应该是值得的。
  3.改用足够牛B的语言，要么有内置的continuation支持，要么有很强的编译时反射性。但是我觉得能在常规语言里加入并行不确定计算是个亮点。
  
  今天展示的这个非确定性计算只是一个“验证概念”版，由于上述的诸多问题和移植性、健壮性的限制，它不能应用于生产。我只希望用这个东西激发起大家继续研究的兴趣。谢谢观看！
  
  http://www.cnblogs.com/Files/yushih/NativeContinuation.zip