Parrot源代码分析之海贼王

我们的目的是找到speedup-example在使用Parrot加速的原因，假设仅仅说它源于Context Switch的降低，有点简单了，它究竟为什么降低了？除了Context Switch外是否还有其它的performance counter也对提速有帮助？这些都是值得去思考的问题。先来看一下我们用来探索Parrot奥秘的程序speedup-example.cpp。

前言：RRScheduler::getTurn&RRScheduler::wait_t::wait

speedup-example.cpp

[cpp] view
plaincopy

1. /* Copyright (c) 2013,  Regents of the Columbia University
2. * All rights reserved.
3. *
4. * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
5. *
6. * 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
7. *
8. * 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other
9. * materials provided with the distribution.
10. *
11. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
12. * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
13. * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
14. * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
15. * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
16. * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
17. */
18. #include <pthread.h>
19. #include <stdio.h>
20. #include <stdlib.h>
21. #include <errno.h>
22. #include <assert.h>
23. //#include "tern/user.h"
24. #define N 4
25. //#define M 30000
26. #define M 30000*10
27. //int nwait = 0;
28. volatile long long sum;
29. volatile long long sum_2;
30. long loops = 6e3;
31. pthread_mutex_t mutex;
32. pthread_cond_t cond;
33. pthread_barrier_t bar;
34. void set_affinity(int core_id) {
35. cpu_set_t cpuset;
36. CPU_ZERO(&cpuset);
37. CPU_SET(core_id, &cpuset);
38. assert(pthread_setaffinity_np(pthread_self(), sizeof(cpu_set_t), &cpuset) == 0);
39. }
40. void* thread_func(void *arg) {
41. set_affinity((int)(long)arg);
42. for (int j = 0; j < M; j++) {
43. //pthread_mutex_lock(&mutex);
44. //nwait++;
45. for (long i = 0; i < loops; i++) // This is the key of speedup for parrot: the mutex needs to be a little bit congested.
46. {
47. sum += i;
48. sum_2 += i;
49. }
50. //pthread_cond_wait(&cond, &mutex);
51. //printf("being in the lock is: %lu\n", pthread_self());
52. //pthread_mutex_unlock(&mutex);
53. //soba_wait(0);
54. //pthread_barrier_wait(&bar);
55. for (long i = 0; i < loops; i++)
56. {
57. sum += i*i*i*i*i*i;
58. }
59. //fprintf(stderr, "compute thread %u %d\n", (unsigned)thread, sched_getcpu());
60. }
61. }
62. int main(int argc, char *argv[]) {
63. set_affinity(23);
64. //soba_init(0, N, 20);
65. pthread_t th[N];
66. int ret;
67. //pthread_cond_init(&cond, NULL);
68. //pthread_barrier_init(&bar, NULL, N);
69. for(unsigned i=0; i<N; ++i) {
70. ret  = pthread_create(&th[i], NULL, thread_func, (void*)i);
71. assert(!ret && "pthread_create() failed!");
72. }
73. /*for (int j = 0; j < M; j++) {
74. while (nwait < N) {
75. sched_yield();
76. }
77. pthread_mutex_lock(&mutex);
78. nwait = 0;
79. //fprintf(stderr, "broadcast %u %d\n", (unsigned)pthread_self(), sched_getcpu());
80. pthread_cond_broadcast(&cond);
81. pthread_mutex_unlock(&mutex);
82. }
83. */
84. for(unsigned i=0; i<N; ++i)
85. pthread_join(th[i], NULL);
86. // test the validity of results
87. printf("sum_2 = %lld\n", sum_2);
88. //printf("sum = %lld\n", sum);
89. exit(0);
90. }

导师曾教导我——

Which approach are you going to use in order to ensure that you will do the right experiments and wont' mess up with the results? 

所以为了不出现实验和实验数据混乱。我这样去做：

1. 仅仅保留speedup-example.cpp一个文件。每次仅仅对这一个文件进行改动，那怎样保证改动过程的正确性，除了反复三次检查改动的地方外，借助以下的记录。
2. 改动记录表：记录改动信息，包含改动文件及行号、是否保存、是否恢复和备注等。

（附链接：

http://bluecloudmatrix.github.io/jekyll_demo/PARROT%E6%BA%90%E7%A0%81%E6%94%B9%E5%8A%A8%E8%AE%B0%E5%BD%95.xlsx）

我们要通过它弄清楚Parrot的执行。以下是我们的始发地。之所以从它開始是受导师的指点——

How many times the sched_yield() in RRScheduler::wait_t::wait() is called within one execution? Have you figured out the relationship between the number of context switches
and sched_yield()?

我们想这应该是最接近答案的入口，于是先尝试直接去探究它。

xtern/lib/runtime/record-scheduler.cpp

[cpp] view
plaincopy

1. void RRScheduler::getTurn()
2. {
3. int tid = self();
4. assert(tid>=0 && tid < Scheduler::nthread);
5. waits[tid].wait();
6. dprintf("RRScheduler: %d gets turn\n", self());
7. SELFCHECK;
8. }

self()返回当前线程的tid。来自xtern/include/tern/runtime/scheduler.h中的struct TidMap：

[cpp] view
plaincopy

1. /// tern tid for current thread
2. static int self() { return self_tid; }

RRScheduler::getTurn是RRScheduler::wait_t::wait的唯一入口。

getTurn的作用是让一个线程执行。而让其它线程等待，实现串行化。

实际上getTurn最早见于struct Serializer，所以这里引出一些重要类的继承关系。

接下来要弄明确是哪里调用了getTurn，以及它在RR调度中起的作用。

在34次直接调用getTurn()的共同拥有五处：

• xtern/lib/runtime/record-runtime.cpp: line 337: SCHED_TIMER_START（共调用30次）
• xtern/lib/runtime/record-runtime.cpp: line 272: RecorderRT<_S>::idle_sleep （共调用1次）
• xtern/lib/runtime/record-scheduler.cpp: line 372: RRScheduler::wait（共调用1次）
• xtern/lib/runtime/record-runtime.cpp: line 376: RecorderRT<_S>::printStat （共调用1次）
• xtern/lib/runtime/record-runtime.cpp: line 286: RecorderRT<_S>::idle_cond_wait（共调用1次）

而调用SCHED_TIMER_START的函数有（它们都在xtern/lib/runtime/record-runtime.cpp）：

• RecorderRT<_S>::threadBegin(void)
• RecorderRT<_S>::threadEnd(unsigned ins)
• RecorderRT<_S>::pthreadCreate
• RecorderRT<_S>::pthreadJoin
• RecorderRT<_S>::pthreadMutexInit
• RecorderRT<_S>::pthreadMutexDestroy
• RecorderRT<_S>::pthreadMutexLock
• RecorderRT<_S>::__pthread_rwlock_rdlock
• RecorderRT<_S>::__pthread_rwlock_wrlock
• RecorderRT<_S>::__pthread_rwlock_tryrdlock
• RecorderRT<_S>::__pthread_rwlock_trywrlock
• RecorderRT<_S>::__pthread_rwlock_unlock
• RecorderRT<_S>::__pthread_rwlock_destroy
• RecorderRT<_S>::__pthread_rwlock_init
• RecorderRT<_S>::pthreadMutexTryLock
• RecorderRT<_S>::pthreadMutexTimedLock
• RecorderRT<_S>::pthreadMutexUnlock
• RecorderRT<_S>::pthreadBarrierInit
• RecorderRT<_S>::pthreadBarrierWait
• RecorderRT<_S>::pthreadBarrierDestroy
• RecorderRT<_S>::pthreadCondWait
• RecorderRT<_S>::pthreadCondTimedWait
• RecorderRT<_S>::pthreadCondSignal
• RecorderRT<_S>::pthreadCondBroadcast
• RecorderRT<_S>::semWait
• RecorderRT<_S>::semTryWait
• RecorderRT<_S>::semTimedWait
• RecorderRT<_S>::semPost
• RecorderRT<_S>::semInit
• RecorderRT<_S>::lineupInit
• RecorderRT<_S>::lineupDestroy
• RecorderRT<_S>::lineupStart
• RecorderRT<_S>::lineupEnd
• RecorderRT<_S>::nonDetStart()
• RecorderRT<_S>::symbolic
• RecorderRT<RecordSerializer>::pthreadBarrierWait
• RecorderRT<RecordSerializer>::pthreadCondWait
• RecorderRT<RecordSerializer>::pthreadCondTimedWait
• RecorderRT<RecordSerializer>::pthreadCondSignal
• RecorderRT<RecordSerializer>::pthreadCondBroadcast
• RecorderRT<_S>::__fork
• RecorderRT<_S>::__execv
• RecorderRT<_S>::schedYield
• RecorderRT<_S>::__sleep
• RecorderRT<_S>::__usleep
• RecorderRT<_S>::__nanosleep

我们须要确定以上函数究竟哪些被调用。假设一个一个函数去測，显得笨重并且easy出错，这使得从getTurn入手剖析源代码这条路不得不停止，只是我们通过getTurn已经挖掘出了一些关键信息。比方主要类的继承关系，还算不是白费力气，我想我们终于会回到getTurn，进行一番彻底的探索。接下来我打算从执行源头看整个调用链，看一看是哪里调用了getTurn，我感觉这会是speedup-example提速的原因所在。

第一回：初涉伟大航路

首先从“东海颠倒山”__libc_start_main（xtern/dync_hook/spec_hooks.cpp: line 73）開始我们的旅行（还是寻宝比較给劲儿^-^）。

通过“永久指针”printf我们来到了“伟大航路”上的 __tern_prog_begin（xtern/lib/runtime/helper.cpp: line  123）岛。让我们在它上面寻找我们想要的东西吧。果然有宝物tern::InstallRuntime()，顺着它我们找了对于我们这个大航海至关重要的伙伴Runtime::the
= new RecorderRT<RRScheduler>（xtern/lib/runtime/record-runtime.cpp: line 183）。伙伴the是师承东海的Runtime和王下七武海的RRScheduler的一名剑客（RecorderRT）。

下一站在the的指引下我们来到了the的老师身为王下七武海的RRScheduler的领地，我们要向他请求一样东西。但是RRScheduler并没有，只是在他的帮助下我们通过他师父（Scheduler）的师父（Serializer）的师父（TidMap），锁定了宝物的位置。它藏在xtern/include/tern/runtime/scheduler.h中TidMap(pthread_t main_th) { init(main_th); }中的init里。果然我们最终在init里面找到了宝物create()。

宝物create告诉我们。之前我们找到的宝物tern::InstallRuntime()须要和一件宝物相接，而这件宝物应该在我们发现tern::InstallRuntime()的地方的附近。没办法。仅仅好返回 __tern_prog_begin（xtern/lib/runtime/helper.cpp: line  123）岛。在printf("liuqiushan8019\n")和printf("liuqiushan8020\n")的夹逼下。我们将地点锁定到了tern_thread_begin();
// main thread begins。这时the使出了大招百八十烦恼风Runtime::the->threadBegin()，击败敌人后。最终夺得了宝物SCHED_TIMER_START。

事实上上面两个宝物对于我们的大航海并没有什么作用。但通过它们我们開始一点一点了解Parrot源代码的运行过程。

第二回：两种顺序

上回说到我们得到一个宝物叫create()，它由一个兄弟，我们顺着这条线：__libc_start_main->__tern_prog_begin->tern_pthread_create，发如今tern_pthread_create中有一个岛屿叫Runtime::the->pthreadCreate，在它上面果然又有一个create()。但眼下我们不知道它的作用，仅仅知道它印有idle。

这让我想探究一下create()的家室。看看它到底还有多少个兄弟，每一个create()又肩负着如何的使命。我们之所以一開始就朝着create使劲，是由于我们一開始就有一个明白的目的：探究四个子线程的创建和运行过程。在进一步从源代码这样的微观角度进行分析之前，让我们从一个宏观的角度看一看到底四个子线程的运行顺序如何，这样方便我们推測和找到入手点。

如今我们要弄明确的是创建的四个子线程的运行顺序是什么样的，是一个线程先完毕任务，再让还有一个线程运行，还是A-B-C-D这样不断循环，终于近乎一块结束？在有LD_PRELOAD时（即使用Parrot）。创建四个子线程，M=30000。loops=6e3，奇异的现象出现了：当有pthread_mutex_lock(&mutex)和pthread_mutex_unlock(&mutex)时。四个子线程的运行顺序是A-B-C-D循环M次；当没有mutex时。四个子线程的运行顺序是A运行完自己全部的任务，然后B開始运行，再C，再D。并且没有mutex不影响结果的准确。

让我们请出大神VTune，帮助我们分析一下这两种顺序的差异和原因。

这是我们大航海面临的第一个强敌，不可大意，在此我下达船长命令：全体船员准备战斗。

有mutex：

无mutex：

在VTune的数据中。最令我诧异的是在无mutex的情况。在第一个子线程执行时，到底是什么让其它三个子线程憋住不执行。是压根没创建，还是仅仅有当第一个子线程结束后才被唤醒去执行，这里要特别点出：我们的重点是有mutex的情况，无mutex的情况仅仅是我们的一个帮手。接下来让我们从源代码的角度看一看这四个子线程是怎样被创建出来的。在上面寻找印有idle的create时，我们发现了tern_pthread_create。我猜想它就是创建idle和其它四个子线程的入口。

奇怪的是那里调用了tern_pthread_create？PARROT中仅仅有两处调用了tern_pthread_create，但经鉴定都不是，当中一处位于xtern\lib\runtime\record-runtime.cpp:
line 2183。它在整个过程中未执行；还有一处位于xtern\lib\runtime\helper.cpp: line 152。它是用来创建一開始的idle线程的。我们将它注掉，并不影响speedup-example的执行。

所以我们大胆猜想：依据LD_PRELOAD的原理，在speedup-example.cpp中我们使用了pthread_create，尽管在Parrot中在xtern\eval\rand-intercept\rand-intercept.c: line 251中有同名函数pthread_create。但它并未被使用。所以我们猜想是tern_pthread_create替换了speedup-example.cpp中的pthread_create。

这样我们大致弄清楚了程序一開始到创建四个子线程这段过程中到底Parrot在干什么——

（A）程序開始运行到创建四个子线程之前

简单地说就是初始化了Runtime::the。然后main thread begins。再然后创建了一个idle线程。眼下还不知道其作用。

（B）利用tern_pthread_create创建四个子线程。

在第三回中我们来探索一下tern_pthread_create都干了些什么。

第三回：tern_pthread_create

上回说到我们遇到了第一个强敌“两种顺序”，在首回交锋中，他使出了大招“用tern_pthread_create来创建子线程”。接下来看我们怎样破。

这就是大招的原理分解图。

在分析RecorderRT<_S>::pthreadCreate时。发现有提示：

[cpp] view
plaincopy

1. /// The pthread_create wrapper solves three problems.
2. ///
3. /// Problem 1.  We must assign a logical tern tid to the new thread while
4. /// holding turn, or multiple newly created thread could get their logical
5. /// tids nondeterministically.  To do so, we assign a logical tid to a new
6. /// thread in the thread that creates the new thread.
7. ///
8. /// If we were to assign this logical id in the new thread itself, we may
9. /// run into nondeterministic runs, as illustrated by the following
10. /// example
11. ///
12. ///       t0        t1           t2            t3
13. ///    getTurn();
14. ///    create t2
15. ///    putTurn();
16. ///               getTurn();
17. ///               create t3
18. ///               putTurn();
19. ///                                         getTurn();
20. ///                                         get turn tid 2
21. ///                                         putTurn();
22. ///                            getTurn();
23. ///                            get turn tid 3
24. ///                            putTurn();
25. ///
26. /// in a different run, t1 may run first and get turn tid 2.
27. ///
28. /// Problem 2.  When a child thread is created, the child thread may run
29. /// into a getTurn() before the parent thread has assigned a logical tid
30. /// to the child thread.  This causes getTurn to refer to self_tid, which
31. /// is undefined.  To solve this problem, we use @thread_begin_sem to
32. /// create a thread in suspended mode, until the parent thread has
33. /// assigned a logical tid for the child thread.
34. ///
35. /// Problem 3.  We can use one semaphore to create a child thread
36. /// suspended.  However, when there are two pthread_create() calls, we may
37. /// still run into cases where a child thread tries to get its
38. /// thread-local tid but gets -1.  consider
39. ///
40. ///       t0        t1           t2            t3
41. ///    getTurn();
42. ///    create t2
43. ///    sem_post(&thread_begin_sem)
44. ///    putTurn();
45. ///               getTurn();
46. ///               create t3
47. ///                                         sem_wait(&thread_begin_sem);
48. ///                                         self_tid = TidMap[pthread_self()]
49. ///               sem_post(&thread_begin_sem)
50. ///               putTurn();
51. ///                                         getTurn();
52. ///                                         get turn tid 2
53. ///                                         putTurn();
54. ///                            sem_wait(&thread_begin_sem);
55. ///                            self_tid = TidMap[pthread_self()]
56. ///                            getTurn();
57. ///                            get turn tid 3
58. ///                            putTurn();
59. ///
60. /// The crux of the problem is that multiple sem_post can pair up with
61. /// multiple sem_down in different ways.  We solve this problem using
62. /// another semaphore, thread_begin_done_sem.
63. ///

顿时剑法的一些关键招数四处浮如今眼前：pthread_create wrapper，assign a logical tid to a new thread，holding turn，getTurn...

看来是上乘剑法。

我们眼下不能立即理解它，先留着，以后慢慢破。

有了招数分解图和一部分剑谱还是费解，那么先来看一下我们的伙伴厨师top探得的消息：

情景一：./speedup-example（有mutex，四个子线程。M=30000*10，没使用Parrot）

情景二：./run_example_tern（有mutex，四个子线程，M=30000*10，使用Parrot）

情景三：./run_example_tern（没有mutex，四个子线程。M=30000*10，使用Parrot）

通过top。我们发现——

• 情景二和情景三相比于情景一。id列（绿色部分）为0.0%，而情景一的id列则占领了较大的百分比。
• 情景三较之于情景二，sy列（橙色部分）为0.0%。而情景二的sy列占领了近乎一半。
• 情景一和情景二的四个core（Cpu0,1,2,3）都是一起执行，而情景三是一个接着一个执行（Cpu0->Cpu1->Cpu2->Cpu3）。

通过上面的实验我们明显看出情景二和情景三明显与没有使用Parrot的情景一不同。我们做这个实验的目的是要更仔细地查看子线程的创建和运行顺序以及一些指标（如id，sy）。我们想探究一下在情景二和情景三下四个子线程的创建顺序是什么样的。

先设想一下：情景二是四个子线程近乎同一时候创建。而情景三是一開始先近乎同一时候创建两个子线程，此后每当一个子线程完毕自己的任务结束时再创建一个新的子线程。通过以下的实验来验证此猜想。

情景四：./run_example_tern（有mutex，八个子线程，M=30000*10，使用Parrot）

情景五：./run_example_tern（没有mutex，八个子线程，M=30000*10。使用Parrot）

对于情景五的行为。有点匪夷所思，为什么一開始要近乎同一时候创建两个子线程，而不是一个一个的创建，当创建的子线程完毕任务。再创建新的子线程？（在第四回会有初步解释）情景四的行为符合常理，与没有使用Parrot的状况是一致的（宏观上如此，实际上它与情景五是一种机制，在第四回中会有答案）。在第二回中我们提到了第一个强敌“两种顺序”。而眼下我们得到的情报也许能对战胜它有帮助。事实上在这众多的信息中。我们仅仅要铭记一点（它的代号为“crocodile”）——解释有mutex时的顺序：四个子线程在近乎同一时候创建出来后，到底是什么让它们保持A-B-C-D这样恒定的运行顺序循环M次。

让我们再次回到源代码。

第四回：让源代码告诉我们crocodile的答案

当我们再次回想tern_pthread_create这个的流程。我们发现能做到控制子线程创建和运行顺序的可能性最大的是sem_post(&thread_begin_sem)和sem_wait(&thread_begin_done_sem)。在经过一番printf之后，我们探得关于信号量thread_begin_sem和thread_begin_done_sem的一些蛛丝马迹：

这让我们意识到在tern_pthread_create创建子线程的同一时候，通过对信号量thread_begin_sem和thread_begin_done_sem的sem_post和sem_wait操作。便有可能做到了对子线程顺序的控制。

我们发现。实际上创建的子线程要运行的函数并非speedup_example.cpp中的thread_func，而是位于xtern/lib/runtime/helper.cpp: line 61的__tern_thread_func。thread_func成了__tern_thread_func的參数，让我们来看一下这位大神的庐山面目：

[cpp] view
plaincopy

1. static void *__tern_thread_func(void *arg) {
2. #ifdef XTERN_PLUS_DBUG
3. if (idle_th != pthread_self())
4. Runtime::__detach_self_from_dbug(__FUNCTION__);
5. #endif
6. void **args;
7. void *ret_val;
8. thread_func_t user_thread_func;
9. void *user_thread_arg;
10. args = (void**)arg;
11. user_thread_func = (thread_func_t)((intptr_t)args[0]);
12. user_thread_arg = args[1];
13. // free arg before calling user_thread_func as it may not return (i.e.,
14. // it may call pthread_exit())
15. delete[] (void**)arg;
16. tern_thread_begin();
17. ret_val = user_thread_func(user_thread_arg);
18. tern_pthread_exit(-1, ret_val); // calls tern_thread_end() and pthread_exit()
19. assert(0 && "unreachable!");
20. }

參数arg实际上就是thread_func，我们能够看到在运行thread_func（即语句ret_val = user_thread_func(user_thread_arg)）之前，要运行tern_thread_begin()，再来看一下tern_thread_begin（位于xtern/lib/runtime/hooks.cpp: line 70）：

[cpp] view
plaincopy

1. void tern_thread_begin(void) {
2. assert(Space::isSys() && "tern_thread_begin must start in sys space");
3. int error = errno;
4. // thread begins in Sys space
5. Runtime::the->threadBegin();
6. Space::exitSys();
7. errno = error;
8. assert(Space::isApp() && "tern_thread_begin must end in app space");
9. }

看来还得继续，Runtime::the->threadBegin()（位于xtern/lib/runtime/record-runtime.cpp: line 374）

[cpp] view
plaincopy

1. template <typename _S>
2. void RecorderRT<_S>::threadBegin(void) {
3. pthread_t th = pthread_self();
4. unsigned ins = INVALID_INSID;
5. if(_S::self() != _S::MainThreadTid) {
6. sem_wait(&thread_begin_sem);
7. _S::self(th);
8. sem_post(&thread_begin_done_sem);
9. }
10. assert(_S::self() != _S::InvalidTid);
11. SCHED_TIMER_START;
12. app_time.tv_sec = app_time.tv_nsec = 0;
13. Logger::threadBegin(_S::self());
14. SCHED_TIMER_END(syncfunc::tern_thread_begin, (uint64_t)th);
15. }

瞧瞧我们发现了什么，sem_wait(&thread_begin_sem)。绝对的宝物。还记得在pthreadCreate（位于xtern/lib/runtime/record-runtime.cpp: line 467）

[cpp] view
plaincopy

1. template <typename _S>
2. int RecorderRT<_S>::pthreadCreate(unsigned ins, int &error, pthread_t *thread,
3. pthread_attr_t *attr, void *(*thread_func)(void*), void *arg) {
4. int ret;
5. SCHED_TIMER_START;
6. ret = __tern_pthread_create(thread, attr, thread_func, arg);
7. assert(!ret && "failed sync calls are not yet supported!");
8. _S::create(*thread);
9. SCHED_TIMER_END(syncfunc::pthread_create, (uint64_t)*thread, (uint64_t) ret);
10. sem_post(&thread_begin_sem);
11. sem_wait(&thread_begin_done_sem);
12. return ret;
13. }

对于第一个子线程，先运行了pthreadCreate中的sem_post(&thread_begin_sem)，才使得接下来运行threadBegin中的sem_wait(&thread_begin_sem)时不会堵塞，进而能继续运行下去，并能在threadBegin之后紧接着运行speedup_example,cpp中的thread_func。

可问题出现了——

按理说在第一个子线程在运行threadBegin之后应该立即运行thread_func，但是我们发现了例如以下现象:

我猜想在第一个子线程运行threadBegin之后。有个东西触发了第二个子线程。第二个子线程的创建过程開始启动（注意仅仅是启动，当第一个子线程运行完第一次临界区中的任务时。才让第二个子线程去运行threadBegin及临界区中的任务），当第二个子线程运行完自己的threadBegin时。该东西又触发了子线程3的启动。

• 在上面的实验之后，我们想弄清楚一点——

在speedup_example.cpp有pthread_mutex_lock(&mutex)并使用Parrot时。在第一个子线程运行第一次循环后，是什么让子线程2開始运行自己的函数__tern_thread_func。这是上面的探索留给我们的一个眼下还无法解释的问题。事实上截至眼下的探索对我们找到speedup-example加速的原因并没有什么帮助，仅仅只是是从源头了解一下源代码的运行过程。我们的目的是要找到speedup-example加速的原因。要学会舍弃对此没用的探索，眼下我们仅仅须要知道四个子线程的创建和运行顺序。将“为什么”先放在一边，专注我们的最初目的。

尽管截至眼下的探索对了解加速原因没有直接帮助，但它却是第七回中从源代码角度了解原因的前提准备工作。

我们眼下还没发回答crocodile的原因。毕竟crocodile是我们通向终于答案的关键，我们尝试在第七回中进行解释。

• 这里要再次提醒一下，我们的最初的目的是要找出speedup_example在使用Parrot后速度加快的原因。

• 本来我们能够在以下一回中接着上面，继续分析四个子线程在创建之后在执行中发生了什么。但更重要的是，要利用VTune探得能影响执行时间的除了synchronization context switches。还有哪些cpu performance counters，这是我们的关键，也是导师一再强调的。伟大航路之行一定要铭记。

第五回：来自论文的cpu performance counters

在探索其它的performance counters之前（由于我们不能乱撞），先来重读一下论文。从论文中看看Parrot到底做了哪些工作。它的原理是什么。

事实上我们无法肯定加速的原因仅仅来自于context switches的降低，实际上依据导师google docs的实验数据，有的获得加速的程序的context switches反而添加了，而docs中列出的全部加速的程序（除了phoenix string_match-pthread）的migration都降低了，通过向Intel的技术人员请教。cpu-migration也是一项performance counters——

CPU-migrations：表示进程 t1 执行过程中发生了多少次 CPU 迁移，即被调度器从一个 CPU 转移到另外一个 CPU 上执行。

先让我们来研究一下migration吧——

导师给出的逻辑：

if performance number X go up and two factors A and  B also go up, so either A or B or both could affect X. The way to verify the hypothesis is thinking about fixing A, and only let B go up, and see whether X is affected as B goes up. In the parrot
task, A or B could be the synchronization context switches or some other cpu performance counters, and X could be the performance of running a program with Parrot. And in order to play with A or B, you first have to figure out which lines of code A or B come
from (maybe by using vtune).





regarding the preemption context switches and sync context switches, have you figured out their differences to performance? In order to do this, you should figure out where the preemption context switches come from (for both with and without parrot), and control
the number of these context switches by modifying code or any other possible ways. Similar things should happen for sync context switches, and maybe other cpu performance counters.





Now X is the execution time, and you see performance gain when running speedup-example.cpp with Parrot. Let say, in this gain, three performance counters A, B, and C are different from the ones running without Parrot.

So, either A, B, C, or some of them, or all of them may affect performance X. Right?

Your report should fix all the other two, and let only one (let say A) change, and see whether the change of A will affect the performance X. If so, then A should be the one that affect performance.





Could you take this program, some some other programs that have similar results as pbzip2, figure our whether the preemption context switches and sync context switches come from, and figure our their differences in performance impact

我们先如果Parrot能减少migration。

实际上在我们的程序speedup-example.cpp中有set_affinity(23)和set_affinity((int)(long)arg)。它们会让子线程固定在一个core上，但这样并没有让speedup-example提速（这都是在没有使用Parrot的情况）。

（A）以下是没有使用Parrot。但使用了set_affinity(23)和set_affinity((int)(long)arg)，speedup-example子线程使用core的情况：

（B）下图是将set_affinity(23)和set_affinity((int)(long)arg)注掉，并在没有使用Parrot的情况下，speedup-example子线程使用core的情况：

（C）我们先将set_affinity(23)和set_affinity((int)(long)arg)注掉，看看Parrot是否能取代它们，让子线程固定在一个core上。以下是使用了Parrot，没有set_affinity(23)和set_affinity((int)(long)arg)的情况：

从上面的实验能够看到，Parrot会将子线程固定在一个core上。

这样speeup-example在使用Parrot后加速，context switches降低，cpu-migration降低。

但A和B告诉我们，即使固定住，也不会起到加速的作用。这样来看的话，尽管Parrot能降低cpu-migration，但speedup-example的加速应该不是得益于migration的降低，看起来似乎没有必要去研究Parrot下的migration。元芳你怎么看？元芳：导师的google
docs有记录显示。有的程序被加速了，但context switches却增多了。反而migration却降低了，context switches增多普通情况下会添加执行时间。要想解释提速的原因，看来仅仅能从migration入手了。大人请看实验数据。

Parrot还有这个功能。能减少migration？并且这有可能故意于提速。先来解答这样一个问题：migration到底会不会添加执行时间？

第六回：迷茫的migration

从Parrot论文，《Identifying OS thread migration using Intel® VTune™
Amplifier XE》。

key=0AmNhZTitrIuAdG1YZzJQbVpjMWVPeWtVY2w5WHpOLXc#gid=13" style="text-decoration:none; color:rgb(12,137,207)">Parrot google docs

， VTune和Parrot源代码入手。

“This poses a problem to the newer computing architectures as this SW thread
migration disassociates the thread from data that has already been fetched into the caches resulting in longer data access latencies.”这句话告诉我们，当一个程序非常依赖cache时（即子线程常常从cache读写数据），假设发生子线程频繁得在core间迁移，那么子线程就不得不从memory中又一次读取数据装载cache，这有可能导致程序执行时间添加。而speedup-example不属于cache依赖型。它的四个子线程所做的仅仅是对sum进行加和乘。将它放在寄存器中就可以。

元芳提到的四条数据，stable_sort，mismatch，equal和linear
regression都是cache依赖的。这也许就解答了为什么它们在使用Parrot后Context Switch添加反而提速了。由于migration降低了。这也仅仅是初步的结论。

我们须要通过实验来验证。首先要弄明确五个问题——

• 问题6.1：migration怎样測得详细数值（VTune似乎不能測migration的详细数值。而又无法用perf）？
• 问题6.2：在探究migration是否会影响到performance时，如果我们能够让使用Parrot后的Context Switch大致与没有使用Parrot时的相当（即让Context Switch不变，这也许要改动Parrot的源代码）。但怎样同一时候让Parrot保持降低migration的作用，同理，在探究Context Switch是否会影响performance时，又怎样让migration不变，让Context Switch变？这都须要我们知道究竟Parrot的哪部分做到了降低migration。哪部分做到了降低Context
  Switch。
• 问题6.3：找到在使用Parrot后migration和Context Switch都降低，且降低migration对performance有提升（不是speedup-example那样的）的程序。
• 问题6.4：解释以下为什么migration和Context Switch都降低了，并且幅度非常大，但执行时间反而添加了？

• 问题6.5：假使我们探究出了migration对performance的影响，我们仍然不能肯定提速仅仅与Context Switch和migration有关，会不会还有其它原因（如以下附中的Preemption Context Switches）。似乎没有尽头？

第七回：重回源代码之路tern_pthread_mutex_lock——终于的答案

至此我们发现。不论是要解决migration的五个问题。还是进一步分析speedup-example的加速原因。还是透彻了解Parrot源代码的运行流程，都须要我们重回源代码进行分析。所以在历经上面几回后我们须要进行回归。事实上第一、二、三、四回都在分析Parrot源代码的运行流程，在第四回的结束时为第五回讲migration开了个头。让我们接着第四回继续分析speedup-example在运行临界区时Parrot都做了些什么。

先从这入手：当第一个子线程创建后，開始运行pthread_mutex_lock时，第二个线程開始创建，那我们就来分析一下第一个线程在运行pthread_mutex_lock时，是否会对第二个子线程的创建有影响。

这样如果的原因是在没有pthread_mutex_lock时，speedup-example的运行流程是当第一个子线程将自己全部的任务都完毕时，第二个子线程才開始自己的任务。

请看第三回中的情景五，一開始第一和第二子线程都创建了。但仅仅有第一子线程在运行自己的任务，并且在第一子线程结束任务后马上创建了第三子线程，随后一段时间第二子线程完毕自己的任务。这都让我们猜想有什么东西在背后控制子线程的创建和运行顺序。就像第四回我们猜想在四个子线程的创建过程中似乎也被规定了顺序。而不是简单的for顺序。

当然这仅仅是推測。接下来通过进一步的源代码分析来

• 问题7.1：确定之前的推測——四个子线程在创建时是否通过某些机制控制了创建顺序？
• 问题7.2：探究出四个子线程在运行任务期间是怎样维持顺序的？
• 问题7.3：维持顺序是在降低竞争吗？
• 问题7.4：降低了竞争会提高性能吗？
• 问题7.5：那个高效的类似spin-lock的lock在哪里?

我想，仅仅要我们能解答第六回和第七回中的十个问题，我们就能得到终于的彻底的答案。

来看一下tern_pthread_mutex_lock——

经过一番打探。我们连分析带推測，觉得对于没有获得锁的三个子线程都通过

[cpp] view
plaincopy

1. while (!wakenUp) {
2. sched_yield();
3. }

的方式在等待，获得锁的子线程在释放锁后要再次訪问pthread_mutex_lock时会做三件事：

1. 通过waitq.push_back(tid)将自己放入等待队列的尾端
2. 通过next函数中的waits[next_tid].post()唤醒下一个应该获得锁的线程（位于runq头部的线程）
3. 通过getTurn函数中的RRScheduler::wait_t::wait()使自己进入等待状态

综上我们先尝试得出下面结论：

眼下来看speedup-example加速的原因之中的一个是Context Switch的大幅度降低和锁竞争降低。以下是具体原因——

• 当A线程要去得到锁，而锁正在被线程B占领着。假设没有使用Parrot，A会将状态转成idle。这样当A得到机会时，就不得不花点时间进行上下文切换将状态由idle转成执行，但使用Parrot就不一样了，A会一致保持执行状态（类似于spin-lock。但却不同于pthread_spin_lock。使用pthread_spin_lock时。top命令下us列会达到100%，而使用Parrot，100%近乎由us列和sy列平分，这是由于Parrot加上了sched_yield()，这是个系统调用），轮到A时，立刻获得锁，这样便降低了上下文切换的花销，但假设是这样。按理说不用Parrot，仅仅用pthread_spin_lock也能起到相同幅度的加速效果，实际上pthread_spin_lock提高性能的前提是锁竞争不激烈【1】。在speedup-example中临界区较大，锁竞争激烈。用pthread_spin_lock反而会添加执行时间。并且使用pthread_spin_lock时的Context
  Switch已经降得和使用Parrot一样少，这就说明不是Context Switch降低了就能提速，一定要满足锁竞争不激烈这个前提。所以Parrot提速的原因绝不仅如此。定有能降低锁竞争的前提。
• 通过上面不太全面的源代码探索，这个降低锁竞争的前提就隐藏在四个子线程那固定的运行顺序，我们猜想四个子线程不仅在创建时通过信号量保持住固定顺序，并且在运行任务时，也可能是通过tid。队列和信号量保持住类似B->A->C->D的顺序，进一步说，当一个子线程运行完临界区释放锁后，这个子线程不是再去要锁（假设是再去要锁，这就和其他被唤醒子线程发生了锁竞争）。而是唤醒下个一该运行的子线程，之后让自己等待，能做到这样有秩序得益于前面提到的它们通过一些机制保持住B->A->C->D这种顺序，这样在随意时刻都仅仅有一个子线程尝试获取锁。这就变成了非竞争锁【2】。锁竞争降低。这就是Parrot论文中所说的——PARROT’s
  round-robin scheduling reduced contention【3】。

除此之外。我们在第六回中的五个问题也是我们最应该去啃的地方（speedup-example也许还与其他类似migration的performance counter有关。仅仅让A变，其他不变，来探究speedup-example的性能是否与A有关），接下来就去做这些。

关于migration对speedup-exmaple的影响，在第五回中我们已经给出了答案——

“speedup-example.cpp中有set_affinity(23)和set_affinity((int)(long)arg)，它们会让子线程固定在一个core上，但这样并没有让speedup-example提速（这都是在没有使用Parrot的情况）”

假设migration对speedup-example有影响，为什么在用set_affinity后（此时Context没有变，但migration降低），speedup-example没有性能上的变化，这说明起码对于speedup-example来说migration并没有对提速有所影响。至于是否会有其他的performance counter，在我们分析源代码的运行流程后，我们能够发现Parrot的贡献在于让四个子线程从创建到运行变得有秩序，以及摆脱了pthread_mutex_lock要产生大量的上下文切换的弊端。所以从这个角度来说。Parrot应该不会再去影响其他的performance
counter。

如今来解答一下对于一些程序为什么在使用Parrot后Context Switch大幅度添加，而执行时间反而基本不变的情况，同一时候解答一下第六回中的问题6.5。为此我们找到了stl中的find_first_of_found，以下是使用Parrot和没有使用Parrot的对照：

• 不使用Parrot：

• 使用Parrot：

我们能够发现。二者的执行时间基本同样，但使用Parrot后。synchronization context switch基本不变，而preemption context switch大幅度添加。尽管我们无法精确度量migration。但从Core/Thread/Function/Call Stack大致能够看到二者migration基本持平（另外，从google doc【4】上我们也能够看到二者的migration基本一致），加上synchronization context switch基本持平。这时尽管preemption
context switch大幅度添加，但性能基本未发生变化，在不考虑很多其它未知performance counter影响时。能够觉得preemption context switch并不会影响到性能。

在对speedup-example中Preemption Context Switch的来源探究中（附：speedup-example中Preemption Context Switches的来源探究），我们发现preemption
context switch是执行时间的附属品，而不是左右者，意思是preemption context switch随着执行时间变长而增多。而不是执行时间随着preemption context switch的增多而变长。

尽管这并不能用于解释上面的find_first_of_found。但从还有一个角度我们能够觉得Preemption Context Switch并不会影响到性能。

引用：

【1】Pthreads并行编程之spin lock与mutex性能对照分析

http://www.parallellabs.com/2010/01/31/pthreads-programming-spin-lock-vs-mutex-performance-analysis/

【2】怎样聪明地使用锁

http://www.ibm.com/developerworks/cn/java/j-lo-lock/

【3】Heming Cui, Jiri Simsa, Yi-Hong Lin, Hao Li, Ben Blum, Xinan Xu, Junfeng Yang, Garth Gibson, and Randy Bryant. "Parrot: a Practical Runtime for Deterministic, Stable, and Reliable Threads". Proceedings of the 24th ACM Symposium on Operating Systems Principles
(SOSP ’13)

http://www.cs.columbia.edu/~junfeng/papers/parrot-sosp13.pdf

【4】Google docs——xtern performance evaluation

https://docs.google.com/spreadsheet/ccc?key=0AmNhZTitrIuAdG1YZzJQbVpjMWVPeWtVY2w5WHpOLXc#gid=13

附录：

speedup-example.cpp（用pthread_spin_lock取代pthread_mutex_lock）

[cpp] view
plaincopy

1. /* Copyright (c) 2013,  Regents of the Columbia University
2. * All rights reserved.
3. *
4. * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
5. *
6. * 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
7. *
8. * 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other
9. * materials provided with the distribution.
10. *
11. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
12. * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
13. * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
14. * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
15. * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
16. * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
17. */
18. #include <pthread.h>
19. #include <stdio.h>
20. #include <stdlib.h>
21. #include <errno.h>
22. #include <assert.h>
23. //#include "tern/user.h"
24. #define N 4
25. #define M 30000
26. //#define M 30000*10
27. //int nwait = 0;
28. volatile long long sum;
29. volatile long long sum_2;
30. long loops = 6e3;
31. //pthread_mutex_t mutex;
32. pthread_spinlock_t mutex;
33. //pthread_cond_t cond;
34. //pthread_barrier_t bar;
35. void set_affinity(int core_id) {
36. cpu_set_t cpuset;
37. CPU_ZERO(&cpuset);
38. CPU_SET(core_id, &cpuset);
39. assert(pthread_setaffinity_np(pthread_self(), sizeof(cpu_set_t), &cpuset) == 0);
40. }
41. void* thread_func(void *arg) {
42. set_affinity((int)(long)arg);
43. for (int j = 0; j < M; j++) {
44. //pthread_mutex_lock(&mutex);
45. pthread_spin_lock(&mutex);
46. //nwait++;
47. for (long i = 0; i < loops; i++) // This is the key of speedup for parrot: the mutex needs to be a little bit congested.
48. {
49. sum += i;
50. sum_2 += i;
51. }
52. //pthread_cond_wait(&cond, &mutex);
53. //printf("being in the lock is: %lu\n", pthread_self());
54. //pthread_mutex_unlock(&mutex);
55. pthread_spin_unlock(&mutex);
56. //soba_wait(0);
57. //pthread_barrier_wait(&bar);
58. for (long i = 0; i < loops; i++)
59. {
60. sum += i*i*i*i*i*i;
61. }
62. //fprintf(stderr, "compute thread %u %d\n", (unsigned)thread, sched_getcpu());
63. }
64. }
65. int main(int argc, char *argv[]) {
66. set_affinity(23);
67. //soba_init(0, N, 20);
68. pthread_t th[N];
69. int ret;
70. pthread_spin_init(&mutex, 0);
71. //pthread_cond_init(&cond, NULL);
72. //pthread_barrier_init(&bar, NULL, N);
73. for(unsigned i=0; i<N; ++i) {
74. ret  = pthread_create(&th[i], NULL, thread_func, (void*)i);
75. assert(!ret && "pthread_create() failed!");
76. }
77. /*for (int j = 0; j < M; j++) {
78. while (nwait < N) {
79. sched_yield();
80. }
81. pthread_mutex_lock(&mutex);
82. nwait = 0;
83. //fprintf(stderr, "broadcast %u %d\n", (unsigned)pthread_self(), sched_getcpu());
84. pthread_cond_broadcast(&cond);
85. pthread_mutex_unlock(&mutex);
86. }
87. */
88. for(unsigned i=0; i<N; ++i)
89. pthread_join(th[i], NULL);
90. // test the validity of results
91. printf("sum_2 = %lld\n", sum_2);
92. //printf("sum = %lld\n", sum);
93. pthread_spin_destroy(&mutex);
94. exit(0);
95. }