瑞典Ericsson总部Master Thesis面试回忆录

2009 May 5th:

晚上刚从超市回来就发现Gtalk弹出新邮件的消息,第一眼就看见标题中Interview的字眼,立刻欣喜若狂,急急忙忙打开仔细一看,竟然是我最早申请的职位的Interview!我是April 24th投的这个职位(Master Thesis),另外还投了若干Summer Job(其中就包括我当天刚刚投完的Nema Labs的Summer job,后面会详叙),Volvo的Master Thesis以及其他几个Ericsson的Thesis Position。

因为这个是我投出去的第一份申请,当时完全没有任何经验,而且Cover Letter和CV都不是最好,现在回想之所以能够拿到这个Interview,主要因为以下几点原因:

1. 专业对口,GPA够。职位是做Sensor Network的,我的专业是Networks and Distributed Systems,正好对口,而且我在刚刚结束的课程Project中正好做过Sensor Network的一个项目,可谓牛头对上了马嘴,不亦乐乎。另外GPA也是Ericsson非常看重的,很多职位写明必须4.0(满分5.0)以上,个人觉得4.3以上比较保险。

2. 简历虽然有些小纰漏,但是因为当时也有针对职位的要求进行修改,所以还是能给人第一眼的好印象的。

3. Cover Letter写得也还凑合。除了常规介绍外还重点说了说自己对那个Thesis的看法,扯了扯自己的本科毕设。[…]

阅读全文>>

前言:去年4月份我申请过一些6月份开始的毕业设计和暑假实习,最终拿到了Ericsson的master thesis offer和另一个哥德堡小公司的summer intern,Volvo在我拿到summer intern后也给了interview。现在应该已经有不少一年级的同学要开始找暑假实习了,我觉得你们可以考虑申请6月份开始的毕设(等毕设结束后再回学校把剩下的课程修完)。下面是我去位于Kista的Ericsson总部面试的经历,希望对大家有用。Summer Intern总体上来讲难度比thesis大很多,因为很多瑞典人也要竞争这种职位,而且那些提供summer intern的小公司也不太喜欢招foreigner。

2009 May 5th:

晚上刚从超市回来就发现Gtalk弹出新邮件的消息,第一眼就看见标题中Interview的字眼,立刻欣喜若狂,急急忙忙打开仔细一看,竟然是我最早申请的职位的Interview!我是April 24th投的这个职位(Master Thesis),另外还投了若干Summer Job(其中就包括我当天刚刚投完的Nema Labs的Summer job,后面会详叙),Volvo的Master Thesis以及其他几个Ericsson的Thesis Position。

因为这个是我投出去的第一份申请,当时完全没有任何经验,而且Cover Letter和CV都不是最好,现在回想之所以能够拿到这个Interview,主要因为以下几点原因:

1. 专业对口,GPA够。职位是做Sensor Network的,我的专业是Networks and Distributed Systems,正好对口,而且我在刚刚结束的课程Project中正好做过Sensor Network的一个项目,可谓牛头对上了马嘴,不亦乐乎。另外GPA也是Ericsson非常看重的,很多职位写明必须4.0(满分5.0)以上,个人觉得4.3以上比较保险。

2. 简历虽然有些小纰漏,但是因为当时也有针对职位的要求进行修改,所以还是能给人第一眼的好印象的。

3. Cover Letter写得也还凑合。除了常规介绍外还重点说了说自己对那个Thesis的看法,扯了扯自己的本科毕设。

发信人是后来面试我的Dr. V.,我一查竟然是UCxx的出身,心想又是UCxx啊!不禁由衷的仰慕,立刻对之后的Interview十分的向往。事后证明Dr. V.人真的非常的nice,虽然有些许龅牙,但是至少英语听起来比较舒服啊!

之后的信件往来就是确定面试时间之类,定下下下周五之后立刻跟身在Kista的yoan师兄联系商量借住事宜(在此对师兄的热情相助表示深深感谢!是你让我在Kista感受到家的温暖啊!还顺带连累你熬了个通宵 囧),然后就是买往返的火车票之类。一切定好后剩下的两个礼拜就开始拼命准备,囫囵吞枣扫了些论文,再跟着看了些英文面试的资料,甚至还去了Career Office做了一次咨询。

这其中发生了一件比较逗的事情。因为哥德堡到斯德的来回火车票加起来600多SEK,我心想这一趟下去怎么的也得1000块了,要不问问看他们能不能给报销?再加上外国公司以往报销路费的事听了不少,我就借着发信问问题的机会顺带来了句:“I am wondering whether you will undertake my travel fee for this interview?” 猜猜人家怎么回的?

“it’s not possible to 报销路费, so我们只能电话Interview了”,我心想,大哥我这菜鸟要电话面试不就相当于直接管你要据信么,再说我票都定了大不了当去旅游好了,于是连忙给他发信解释说没关系云云。

2009 May 14th

早上6点的火车去Stockholm,4点半起的,等5点的第一班tram去Central Station。顺利等到4路电车,心想时间肯定来得及,耽误不了。但是不幸恰恰在心情放松麻痹大意的情况下发生了。我在离火车站还有两站路的时候突发奇想拿出口语书开始模拟英语面试,自己边模拟面试官边想着怎么回答,简直就是左右互搏,天人合一,不亦乐乎,十分忘我。练了5,6分钟后我发现不对了:怎么窗外还能看见火车啊?我仔细一看,我靠!还真是Central Station的火车,其中就有我要坐的x2000!我心中大叫不好,刚刚停的那站就是火车站,我给错过了!!我赶紧收拾东西站在门口准备在下站下车赶紧再坐回去,结果老天真给我开了个大玩笑:过了上一站之后Tram就进入郊区了,开了至少5分钟才到下一站!那5分钟简直就是我人生最漫长的一段时间之一,脑子100%运转,不停看表计算时间,同时储备体力随时准备狂奔。

5分钟后终于到达下一站了,赶紧下车,到对面站台看反方向的车几点到:5分钟以后!这意味着我到火车站后离发车只剩10分钟不到!!!而且我还从来没去过火车站都不知道火车在哪!天无绝人之路,我发现旁边竟然还有一个车站!赶紧对了下时间,Tram7马上就到,又多出了5分钟!老天保佑,我心急如焚的等着不紧不慢的7路小电车,来了!上车!走!到!门开的一霎那,我真是卯足了劲往站台冲啊!事后回想我大概只用了1分钟不到就找到了X2000的站台。这还多亏瑞典的火车站不像国内的那么大,还要进候车厅再排队检票上下楼梯什么的,站台离车站正门也就2-3分钟的路,而且上车后再检票。我悬着的心终于放下来了,事后回想就算当天没赶上我也可以再买下一班的,大不了先上车后补票,还好是我之前订的就是周四走周五面试。虽然我这不叫大难不死,但也算是必有后福啊!

顺利到达Stockholm。斯京的火车站和地铁站是连在一起的,下火车后直接就去地铁售票处买了张24h的通票(100SEK),直奔Kista。话说这个Kista号称瑞典最大的科技园区,里面不仅有Ericsson全球总部,华为瑞典分舵等众多IT公司,KTH也有一个分校区在那边。出了Kista地铁站直接就是一个大型Shopping Mall,在把正补觉的师兄吵醒之后顺利放下行李。中午吃了师兄做的红烧肉拌面,话说那个红烧肉确实很够味,真是赞!

下午就出去Kista园区去寻我明天面试的地点去了。来了Kista我最大的感受就是,整个Kista到处都是Ericsson的人。不管是在Shopping Mall里的Restaurant还是在工业园区的大街上,到处都是挂着蓝色Ericsson牌子的人,简直就是Ericsson大山寨。后来听到一个说法,Ericsson这样的国民企业其实更应该被看做一个Community,在Kista的shopping mall里面甚至有专门的Ericsson员工价,由此可见一般。顺便说一句,上次回国刚下飞机在机场大巴上,坐我旁边的竟然是个瑞典小哥,仔细一聊竟然也是学CS的,从Stockholm来中国找他中国女朋友,于是我就问“你是不是给Ericsson工作”,结果竟然猜对了。由此可见爱立信有多庞大。

事实也确实如此。一开始我找到的最显眼的是一栋白色的大型Ericsson办公楼,整个楼占了一个广场的大小,气势直逼瑞典皇宫了(当然更现代点),真不愧是世界级大公司的全球总部啊。于是我就去reception问我的面试官是不是在这栋楼办公,结果人家告诉我:“不好意思,你找的人在对面那栋楼办公,出门后直走就到了”。等我出去仔细一看,原来Ericsson Research是另一栋大红楼。我猜可能那栋大白楼里面应该都是Ericsson负责工业产品的部门吧。踩点完毕后就回家继续做准备去了。Tips:对面试要提前踩点,特别是去不熟悉的地方更要多做准备,因为瑞典人很忌讳迟到(瑞典交通发达,地铁非常准时,也没什么堵车,所以没有迟到的理由)。

虽然最后我拿到了这个Offer,但是说实话在面试之前我还是非常紧张的。这可是我第一次英文面试,两个面试官都是顶尖大学的PHD,还顶着Ericsson总部的光环。我做的主要准备如下:

1)根据Position Description看了几篇该领域的综述型Paper,以到达快速入门的目的;

2)仔细研究该Position的Requirement,结合自己的CV自己进行了若干次模拟面试

3)准备了自己本科毕设的资料(一页A4插图,直观明了)和,因为这个跟该Thesis有点相关

4)给面试专门准备了一份CV,突出了自己项目经验跟该position的相关性

面试的流程大致如下:

跟两份面试官打过招呼后直接把CV和Transcript递上(省了人家自己打印的功夫,而且给你第一印象就是你准备的很充分。“我把简历都给你带过来了,上面的都是你们需要的”)。Dr.V.人非常好的先给我介绍了一下该Thesis的大致背景,很好的帮助我消除了紧张情绪并帮助我快速进入状态。在了解到项目的大致框架后我适时的接过话题(适时把握话题的主动性,不是被人牵着鼻子走。“我对这个很熟,请听听我的想法”),抛出了我对这个项目的具体实现的想法(虽然有些当时我的想法有些许错误,但是很好的表现出自己对这个项目的兴趣,就像是说:“你看,我自己脑子里已经有一个实现了,我很有可能能把这个项目完成的很好”)。

再聊了一些项目的话题后面试官就开始问我的简历上的项目经验了。我就一个一个跟他们解释(“我做过的东西跟这个Thesis都很相关,我很有竞争力”),其中有几个他们比较熟悉的项目他们就会问你一些技术问题或者算法问题。不过只要自己对项目的背景知识和本身的实现比较熟悉基本没什么问题,而且就算真的不会直接说不会也没关系。我其中就有2个问题直接说了不会,很可能他们因为看重我其他的背景和我的学习能力所以没影响我拿offer。

我感觉我整个面试过程中最出彩的地方在介绍我的本科毕设部分。回想当年在白混了3年之后,心想最后一个毕设怎么的也得拿个A做出点像样的东西来,要不大学白过了,于是狠命搞了半年终于如愿以偿。正好毕设跟这个Thesis很相关,当我拿出我做的prototype的照片并向他们介绍它的功能的时候,我分明的感觉到两位Ericsson Researcher都被我打动了(“给我Offer吧!本科毕设我都拿A了,你们这个Thesis我肯定不会让你们失望的!”)。

最后Dr. V.非常Nice的送我下楼,我在电梯里又跟他聊起不能报销差旅费的事情,最后我对他说了我生平最有打动人的效果的一句英语:“I just want to let you know my serious and positive attitude for this position.”结果Dr.V.非常配合的笑着对我说:“Yes!You have!”

The End:May 19th下午正准备跟妞妞mixi,突然接到一个010开头的电话,我还奇怪难道是北京打来的?后来才知道在瑞典Stockholm的区号也是010。也许大家都猜到了,其实就是另一位面试官打来的Offer电话。

P.S. 虽然因为种种原因没去Ericsson,但是我仍然深深的被Ericsson HQ的魅力所吸引,它向我展现了一个世界电信巨头的风采。而Stockholm,它的美丽更是让我留恋。希望下一次妞妞能跟我再一次同游斯德。

P.S.S. 猜猜Kista最大的中国人群体里在哪?不错,就是华为!华为真是牛逼,我问过好几个瑞典人了,华为真的是一个爱立信强有力对手的存在,直接把分舵开到Ericsson老家,有点新东方把分舵开始ETS总部的意思。在此祝华为越来越牛逼!早日出台Kista华为员工价!

Pthreads并行编程之spin lock与mutex性能对比分析

POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段,其中最典型的应用就是用Pthreads提供的锁机制(lock)来对多个线程之间共 享的临界区(Critical Section)进行保护(另一种常用的同步机制是barrier)。

Pthreads提供了多种锁机制:
(1) Mutex(互斥量):pthread_mutex_***
(2) Spin lock(自旋锁):pthread_spin_***
(3) Condition Variable(条件变量):pthread_con_***
(4) Read/Write lock(读写锁):pthread_rwlock_***

Pthreads提供的Mutex锁操作相关的API主要有:
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的与Spin Lock锁操作相关的API主要有:
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

从实现原理上来讲,Mutex是属于sleep-waiting类型 的锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。当线程A想要 pthread_mutex_lock操作去得到一个临界区的锁时,如果这个锁正被线程B所持有,那么线程A就会被阻塞(bolcking),Core0 会在此时进行上下文切换(Context Switch),这样Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它是属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。

阅读全文>>

POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段,其中最典型的应用就是用Pthreads提供的锁机制(lock)来对多个线程之间共 享的临界区(Critical Section)进行保护(另一种常用的同步机制是barrier)。

Pthreads提供了多种锁机制:
(1) Mutex(互斥量):pthread_mutex_***
(2) Spin lock(自旋锁):pthread_spin_***
(3) Condition Variable(条件变量):pthread_con_***
(4) Read/Write lock(读写锁):pthread_rwlock_***

Pthreads提供的Mutex锁操作相关的API主要有:
pthread_mutex_lock (pthread_mutex_t *mutex);
pthread_mutex_trylock (pthread_mutex_t *mutex);
pthread_mutex_unlock (pthread_mutex_t *mutex);

Pthreads提供的与Spin Lock锁操作相关的API主要有:
pthread_spin_lock (pthread_spinlock_t *lock);
pthread_spin_trylock (pthread_spinlock_t *lock);
pthread_spin_unlock (pthread_spinlock_t *lock);

从实现原理上来讲,Mutex属于sleep-waiting类型的锁。例如在一个双核的机器上有两个线程(线程A和线程B),它们分别运行在Core0和Core1上。假设线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁,而此时这个锁正被线程B所持有,那么线程A就会被阻塞(blocking),Core0 会在此时进行上下文切换(Context Switch)将线程A置于等待队列中,此时Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然,它属于busy-waiting类型的锁,如果线程A是使用pthread_spin_lock操作去请求锁,那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求,直到得到这个锁为止。

如果大家去查阅Linux glibc中对pthreads API的实现NPTL(Native POSIX Thread Library) 的源码的话(使用”getconf GNU_LIBPTHREAD_VERSION”命令可以得到我们系统中NPTL的版本号),就会发现pthread_mutex_lock()操作如果没有锁成功的话就会调用system_wait()的系统调用(现在NPTL的实现采用了用户空间的futex,不需要频繁进行系统调用,性能已经大有改善),并将当前线程加入该mutex的等待队列里。而spin lock则可以理解为在一个while(1)循环中用内嵌的汇编代码实现的锁操作(印象中看过一篇论文介绍说在linux内核中spin lock操作只需要两条CPU指令,解锁操作只用一条指令就可以完成)。有兴趣的朋友可以参考另一个名为sanos的微内核中pthreds API的实现:mutex.c spinlock.c,尽管与NPTL中的代码实现不尽相同,但是因为它的实现非常简单易懂,对我们理解spin lock和mutex的特性还是很有帮助的。

那么在实际编程中mutex和spin lcok哪个的性能更好呢?我们知道spin lock在Linux内核中有非常广泛的利用,那么这是不是说明spin lock的性能更好呢?下面让我们来用实际的代码测试一下(请确保你的系统中已经安装了最近的g++)。

// Name: spinlockvsmutex1.cc
// Source: http://www.alexonlinux.com/pthread-mutex-vs-pthread-spinlock
// Compiler(spin lock version): g++ -o spin_version -DUSE_SPINLOCK spinlockvsmutex1.cc -lpthread
// Compiler(mutex version): g++ -o mutex_version spinlockvsmutex1.cc -lpthread
#include <stdio.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <errno.h>
#include <sys/time.h>
#include <list>
#include <pthread.h>

#define LOOPS 50000000

using namespace std;

list<int> the_list;

#ifdef USE_SPINLOCK
pthread_spinlock_t spinlock;
#else
pthread_mutex_t mutex;
#endif

//Get the thread id
pid_t gettid() { return syscall( __NR_gettid ); }

void *consumer(void *ptr)
{
    int i;

    printf("Consumer TID %lun", (unsigned long)gettid());

    while (1)
    {
#ifdef USE_SPINLOCK
        pthread_spin_lock(&spinlock);
#else
        pthread_mutex_lock(&mutex);
#endif

        if (the_list.empty())
        {
#ifdef USE_SPINLOCK
            pthread_spin_unlock(&spinlock);
#else
            pthread_mutex_unlock(&mutex);
#endif
            break;
        }

        i = the_list.front();
        the_list.pop_front();

#ifdef USE_SPINLOCK
        pthread_spin_unlock(&spinlock);
#else
        pthread_mutex_unlock(&mutex);
#endif
    }

    return NULL;
}

int main()
{
    int i;
    pthread_t thr1, thr2;
    struct timeval tv1, tv2;

#ifdef USE_SPINLOCK
    pthread_spin_init(&spinlock, 0);
#else
    pthread_mutex_init(&mutex, NULL);
#endif

    // Creating the list content...
    for (i = 0; i < LOOPS; i++)
        the_list.push_back(i);

    // Measuring time before starting the threads...
    gettimeofday(&tv1, NULL);

    pthread_create(&thr1, NULL, consumer, NULL);
    pthread_create(&thr2, NULL, consumer, NULL);

    pthread_join(thr1, NULL);
    pthread_join(thr2, NULL);

    // Measuring time after threads finished...
    gettimeofday(&tv2, NULL);

    if (tv1.tv_usec > tv2.tv_usec)
    {
        tv2.tv_sec--;
        tv2.tv_usec += 1000000;
    }

    printf("Result - %ld.%ldn", tv2.tv_sec - tv1.tv_sec,
        tv2.tv_usec - tv1.tv_usec);

#ifdef USE_SPINLOCK
    pthread_spin_destroy(&spinlock);
#else
    pthread_mutex_destroy(&mutex);
#endif

    return 0;
}

该程序运行过程如下:主线程先初始化一个list结构,并根据LOOPS的值将对应数量的entry插入该list,之后创建两个新线程,它们都执行consumer()这个任务。两个被创建的新线程同时对这个list进行pop操作。主线程会计算从创建两个新线程到两个新线程结束之间所用的时间,输出为下文中的”Result “。

测试机器参数:
Ubuntu 9.04 X86_64
Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz
4.0 GB Memory

从下面是测试结果:

gchen@gchen-desktop:~/Workspace/mutex$ g++ -o spin_version -DUSE_SPINLOCK spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ g++ -o mutex_version spinvsmutex1.cc -lpthread
gchen@gchen-desktop:~/Workspace/mutex$ time ./spin_version
Consumer TID 5520
Consumer TID 5521
Result - 5.888750

real    0m10.918s
user    0m15.601s
sys    0m0.804s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex_version
Consumer TID 5691
Consumer TID 5692
Result - 9.116376

real    0m14.031s
user    0m12.245s
sys    0m4.368s

可以看见spin lock的版本在该程序中表现出来的性能更好。另外值得注意的是sys时间,mutex版本花费了更多的系统调用时间,这就是因为mutex会在锁冲突时调用system wait造成的。

但是,是不是说spin lock就一定更好了呢?让我们再来看一个锁冲突程度非常剧烈的实例程序:

//Name: svm2.c
//Source: http://www.solarisinternals.com/wiki/index.php/DTrace_Topics_Locks
//Compile(spin lock version): gcc -o spin -DUSE_SPINLOCK svm2.c -lpthread
//Compile(mutex version): gcc -o mutex svm2.c -lpthread
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/syscall.h>

#define        THREAD_NUM     2

pthread_t g_thread[THREAD_NUM];
#ifdef USE_SPINLOCK
pthread_spinlock_t g_spin;
#else
pthread_mutex_t g_mutex;
#endif
__uint64_t g_count;

pid_t gettid()
{
    return syscall(SYS_gettid);
}

void *run_amuck(void *arg)
{
       int i, j;

       printf("Thread %lu started.n", (unsigned long)gettid());

       for (i = 0; i < 10000; i++) {
#ifdef USE_SPINLOCK
           pthread_spin_lock(&g_spin);
#else
               pthread_mutex_lock(&g_mutex);
#endif
               for (j = 0; j < 100000; j++) {
                       if (g_count++ == 123456789)
                               printf("Thread %lu wins!n", (unsigned long)gettid());
               }
#ifdef USE_SPINLOCK
           pthread_spin_unlock(&g_spin);
#else
               pthread_mutex_unlock(&g_mutex);
#endif
       }
       
       printf("Thread %lu finished!n", (unsigned long)gettid());

       return (NULL);
}

int main(int argc, char *argv[])
{
       int i, threads = THREAD_NUM;

       printf("Creating %d threads...n", threads);
#ifdef USE_SPINLOCK
       pthread_spin_init(&g_spin, 0);
#else
       pthread_mutex_init(&g_mutex, NULL);
#endif
       for (i = 0; i < threads; i++)
               pthread_create(&g_thread[i], NULL, run_amuck, (void *) i);

       for (i = 0; i < threads; i++)
               pthread_join(g_thread[i], NULL);

       printf("Done.n");

       return (0);
}

这个程序的特征就是临界区非常大,这样两个线程的锁竞争会非常的剧烈。当然这个是一个极端情况,实际应用程序中临界区不会如此大,锁竞争也不会如此激烈。测试结果显示mutex版本性能更好:

gchen@gchen-desktop:~/Workspace/mutex$ time ./spin
Creating 2 threads...
Thread 31796 started.
Thread 31797 started.
Thread 31797 wins!
Thread 31797 finished!
Thread 31796 finished!
Done.

real    0m5.748s
user    0m10.257s
sys    0m0.004s

gchen@gchen-desktop:~/Workspace/mutex$ time ./mutex
Creating 2 threads...
Thread 31801 started.
Thread 31802 started.
Thread 31802 wins!
Thread 31802 finished!
Thread 31801 finished!
Done.

real    0m4.823s
user    0m4.772s
sys    0m0.032s

另外一个值得注意的细节是spin lock耗费了更多的user time。这就是因为两个线程分别运行在两个核上,大部分时间只有一个线程能拿到锁,所以另一个线程就一直在它运行的core上进行忙等待,CPU占用率一直是100%;而mutex则不同,当对锁的请求失败后上下文切换就会发生,这样就能空出一个核来进行别的运算任务了。(其实这种上下文切换对已经拿着锁的那个线程性能也是有影响的,因为当该线程释放该锁时它需要通知操作系统去唤醒那些被阻塞的线程,这也是额外的开销)

总结
(1)Mutex适合对锁操作非常频繁的场景,并且具有更好的适应性。尽管相比spin lock它会花费更多的开销(主要是上下文切换),但是它能适合实际开发中复杂的应用场景,在保证一定性能的前提下提供更大的灵活度。

(2)spin lock的lock/unlock性能更好(花费更少的cpu指令),但是它只适应用于临界区运行时间很短的场景。而在实际软件开发中,除非程序员对自己的程序的锁操作行为非常的了解,否则使用spin lock不是一个好主意(通常一个多线程程序中对锁的操作有数以万次,如果失败的锁操作(contended lock requests)过多的话就会浪费很多的时间进行空等待)。

(3)更保险的方法或许是先(保守的)使用 Mutex,然后如果对性能还有进一步的需求,可以尝试使用spin lock进行调优。毕竟我们的程序不像Linux kernel那样对性能需求那么高(Linux Kernel最常用的锁操作是spin lock和rw lock)。

2010年3月3日补记:这个观点在Oracle的文档中得到了支持:

During configuration, Berkeley DB selects a mutex implementation for the architecture. Berkeley DB normally prefers blocking-mutex implementations over non-blocking ones. For example, Berkeley DB will select POSIX pthread mutex interfaces rather than assembly-code test-and-set spin mutexes because pthread mutexes are usually more efficient and less likely to waste CPU cycles spinning without getting any work accomplished.

p.s.调用syscall(SYS_gettid)和syscall( __NR_gettid )都可以得到当前线程的id:)

转载请注明来自: www.parallellabs.com

How to do performance analysis on your parallelized program efficiently?

Be a scientist: Gather data. Analyze it. Especially when it comes to parallelism and scalability, there’s just no substitute for the advice to measure, measure, measure, and understand what the results mean. Putting together test harnesses and generating and analyzing numbers is work, but the work will reward you with a priceless understanding of how your code actually runs, especially on parallel hardware—an understanding you will never gain from just reading the code or in any other way. And then, at the end, you will ship high-quality parallel code not because you think it’s fast enough, but because you know under what circumstances it is and isn’t (there will always be an “isn’t”), and why.

Herb Sutter

阅读全文>>

Be a scientist: Gather data. Analyze it. Especially when it comes to parallelism and scalability, there’s just no substitute for the advice to measure, measure, measure, and understand what the results mean. Putting together test harnesses and generating and analyzing numbers is work, but the work will reward you with a priceless understanding of how your code actually runs, especially on parallel hardware—an understanding you will never gain from just reading the code or in any other way. And then, at the end, you will ship high-quality parallel code not because you think it’s fast enough, but because you know under what circumstances it is and isn’t (there will always be an “isn’t”), and why.

Herb Sutter

doubanclaim5959b1bcd330f270

09年感悟

上半年顺风顺水,有付出也有收获,良好的状态持续到暑假实习结束。下半年压力陡增,主要包括就业压力和毕设压力。一个是因为国内就业竞争的激烈,另一个是因为十分具有挑战性的毕设课题。

压力。有压力是好事,在恰当的时候它能转换为我的动力,督促我的行为,间接促进我的进步。但是对待压力也要心态平和,不要过于焦虑、消沉,否则会陷入非常被动的局面。看过一句话,压力大就是因为自信心不足。自信心是建立在刻苦的努力之上的。所以最好的状态还是Take it easy,找准最需要下功夫的地方,多勤奋一点,多努力一点,付出的比别人多自然就有丰厚的回报,而且随着一点一滴的积累,自信心自然也就来了。

定位。首先是找到并持续的激发自己的兴趣点,从事自己真正发自内心喜欢并且觉得有意义的事情,这往往是成功的第一步。不要被所谓的“热潮”牵着鼻子走,分散了自己的注意力不说,这些不是自己最感兴趣的事情往往也不太适合自己。最好的学习和工作状态是每天早晨睁开眼就很兴奋很期待今天要做的事情,不管是它能给他人带来很积极的影响,或是能提升自己的专业技能,都能给自己带来满足感、成就感。最怕的就是对事情只有三分钟热情,当几天过去热情不在,或是碰到困难后就放弃,这样往往最后就是竹篮打水一场空。其次就是对症下药,先找自己最薄弱的环节并积极去弥补它。不要左一下右一下,结果等到面对问题的时候那些最需要的技能还没准备好那就完了。这里引出了另一个话题,专注。

阅读全文>>

上半年顺风顺水,有付出也有收获,良好的状态持续到暑假实习结束。下半年压力陡增,主要包括就业压力和毕设压力。一个是因为国内就业竞争的激烈,另一个是因为十分具有挑战性的毕设课题。

压力。有压力是好事,在恰当的时候它能转换为我的动力,督促我的行为,间接促进我的进步。但是对待压力也要心态平和,不要过于焦虑、消沉,否则会陷入非常被动的局面。看过一句话,压力大就是因为自信心不足。自信心是建立在刻苦的努力之上的。所以最好的状态还是Take it easy,找准最需要下功夫的地方,多勤奋一点,多努力一点,付出的比别人多自然就有丰厚的回报,而且随着一点一滴的积累,自信心自然也就来了。

定位。首先是找到并持续的激发自己的兴趣点,从事自己真正发自内心喜欢并且觉得有意义的事情,这往往是成功的第一步。不要被所谓的“热潮”牵着鼻子走,分散了自己的注意力不说,这些不是自己最感兴趣的事情往往也不太适合自己。最好的学习和工作状态是每天早晨睁开眼就很兴奋很期待今天要做的事情,不管是它能给他人带来很积极的影响,或是能提升自己的专业技能,都能给自己带来满足感、成就感。最怕的就是对事情只有三分钟热情,当几天过去热情不在,或是碰到困难后就放弃,这样往往最后就是竹篮打水一场空。其次就是对症下药,先找自己最薄弱的环节并积极去弥补它。不要左一下右一下,结果等到面对问题的时候那些最需要的技能还没准备好那就完了。这里引出了另一个话题,专注。

专注。提高学习效率最有效的办法就是专注。首先从生活习惯上改善,每天划出几大块完整的学习时间段有助于保持专注。把学习的精力集中在能提升自己核心竞争力的技能上,而不是“花拳绣腿”,看上去新鲜实际上没啥用处。其次,注意任务切换(Context Switch)是要花费时间和精力的。这体现在学习的过程中,例如你学着学着突然想上下网,结果这一上就是十几二十分钟,等你再切回学习这个进程,你得先花十几分钟找回刚刚学习的感觉,才能继续开始,这样宝贵的三十分钟就没了。解决办法就是尽量减少Context Switch的次数。

计划。短期来看,给事情安排好优先级,给每天的工作都制定好计划;长期来看,给职业生涯做好规划。这样能有效的减少学习时的无所事事的(idle)时间(参考暗时间一文),有效的提升productivity。以前我不相信我可以同时做好两三件大事,但是2010年我想挑战一下自己,从每天的时间安排做起,争取高效率快节奏的同时把两到三件事情给同时做好,因为我导师就是这么干的。我问过我导师你这么忙胆识还能把事情安排的井井有条(又是搞研究开会又是开公司)是不是因为你已经成功的把自己并行化了,他笑说他希望他有One million cores,这样他就能把所有的事情都处理的来。当然了,其实我发现一个重要原因是因为他有严格的时间管理方法,以小时为单位来详细安排自己每天的行程。

思考。如果每天只是忙忙碌碌但是不进行足够深入的思考并总结自己得到的经验教训,所能得到的进步就会不够多。每天起床吃饭学习然后睡觉,但是不思考,就会停滞在一个思维水平上,往往不能得到大突破。刘未鹏的博客有很多关于“思考”的好文,今年我的目标就是多思考,多总结,从而多进步。

宠辱不惊。心智的成熟体现在“不以物喜,不以己悲”,抗压能力,调整能力等等上。我现在这个阶段,开始从校园走向社会,各方面的压力会迎面而来。这个时候更需要自己有良好的心态,积极的调整自己,善于化解压力,善于自我激励,时刻把握住自己的目标,不迷失自己的方向。

眼光。眼光放长远些,明年的目标只是第一步,五年乃至十年的目标才是更值得关注的。当然,第一步的起点如果够高会很有帮助。

09年大事记:

09 Jan – 09 Mar

TDA297 Distributed Systems II, EDA281 Parallel Computer Organization and Design

09 Mar – 09 May

TIN092 Algorithm, EDA203 Unix Internal, Internship Applications & Interviews

09 Jun – 09 Jul

Summer Intern at Nema Labs

09 Aug

Summer vacation in China

09 Sep – 09 Oct

TDA381 Concurrent Programming (pending), DAT145 Advanced topic in NDS

09 Oct – 09 Dec

DAT105 Computer Architecture, Master Thesis

10年计划:

09 Jan – 09 Mar

TDA231 – Algorithms for machine learning and inference

09 Jan – 09 Sep

Master Thesis

09 Jun – 09 Aug

Summer Internship

09 Fall

To be continued.

Proposal for the “Search and sort” competition of Findwise

In this April I took part in a competition hold by Findwise and Mriday which is about search technology.

Search and Sort | Findwise

Current, Search and Sort | Findwise April 25th, 2009

We are constantly acquiring innovative ideas and solutions in the field of search technology. Therefore we have created the following contest to discover people who are interested in joining Findwise and build next generation’s search technology.

Project overview

The name of this contest is called Search and Sort. We can start by looking at an example which everybody is familiar with, Google. The Google search engine is the most used search engine on the Web. The search results generated from it includes webpages, PDF, Word documents, Excel spreadsheets, Flash, videos etc. For any query, up to the first 1000 results can be shown with a maximum of 100 displayed per page.

阅读全文>>

In this April I took part in a competition hold by Findwise and Mriday which is about search technology.

Search and Sort | Findwise

Current, Search and Sort | Findwise April 25th, 2009

We are constantly acquiring innovative ideas and solutions in the field of search technology. Therefore we have created the following contest to discover people who are interested in joining Findwise and build next generation’s search technology.

Project overview

The name of this contest is called Search and Sort. We can start by looking at an example which everybody is familiar with, Google. The Google search engine is the most used search engine on the Web. The search results generated from it includes webpages, PDF, Word documents, Excel spreadsheets, Flash, videos etc. For any query, up to the first 1000 results can be shown with a maximum of 100 displayed per page.

Despite all this power, it is still sometimes time consuming to find the exact piece of information you are looking for. This is because although the different results are ranked, they are not well organized. For the average user, wouldn’t it be neat if different types of search results are categorized and displayed in different
groups?

Submission

Your submission for this contest should contain two parts

Think of a search engine based on the concept of Search and Sort. Come up with a user interface design including two pages. One welcome page with the search box (and whatever else you think is suitable), and one page with the different types of results categorized, sorted, and presented in a userfriendly fashion. There is no strict requirements on exactly how the results will be categorized. It is entirely up to you to decide the types of categories. In fact, this will be a key deciding factor when your contest submission is being reviewed.

The second part of the contest is to discuss the framework behind your graphical user interface. What programming language and platform do you suggest for building the system? How would you extract information from different types of results and use that information to categorize them? Describe the plan to develop and implement it. The key for this part is to show a good understanding of the basics of a search engine, and a passion to innovate new ideas.

Searching has become the standard way for Internet users to find information. This contest gives you the chance to take Searching to the next level. If you are interested in search technology and would like to join the leading vendor independent company within this segment in Sweden, then send us your ideas. We will carefully review your submission and provide feedback. Your submission should be in PDF or DOC format.

The deadline for submission is 2009-04-30

Reward

The top 5 submissions will be invited to Findwise and receive a learning session about the company and the future of search technology. The most outstanding submission will receive a monetary reward of 10 000 SEK. Job offers will be presented to qualified individuals if requirements are met.

I spent a whole Sunday to write down a proposal for this topic. That’s the first time for me to write down something on “search technology” which is a very interesting and hot area nowdays. Even though this paper looks a lit bit naive now, I still like it since I enjoy the feeling of writing down something interesting very much.

You can find and download my proposal from the link below:

Search and sort.pdf

在瑞典打甲流疫苗

如果在哥德堡想打甲流H1N1疫苗的话可以参考这里

在页面左侧栏列出了哥德堡不同的地区的Vårdcentraler,离Chalmers最近的Vårdcentraler是属于Centrum地区。我去的是Vårdcentralen Gibraltargatan,就在图书馆旁边。打开Vårdcentralen Gibraltargatan的页面后有专门的接种时间等信息:

Våra vaccinationstider

För information om influensan och vaccineringen

一般他们都是8点开门,但是疫苗现在还是比较抢手,昨天11点到的时候已经没有了,所以今天我是早上8点到的,排到了24号,等了半个多小时轮到了我。等待时填了个人信息表,然后进去打针,打完后医生会给你写好一个小卡片让你留底。但是个人信息表是瑞典语的,以下是粗略翻译(仅供参考):

underlag för pandemivaccination (pandemrix)

för patienten

inför vaccinationen mot den pandemiska influensan ber vi dig svara på följande frågor

1. har du tidigare fatt nagon allvarlig reaktion (som yrsel, svimning, andnod eller utslag)

ja/nej/vet ej

2. ar du allergisk mot agg

3. medicinerar du med nagon blodfortunnande medicin, t.ex. waran eller fragmin? (galler ej trombyl)

4. har du nagon sjukdom eller medicin som påverkar ditt immunforsvar

5. har du nyligen (inom 1 manad) fatt nagot annat vaccin

6. tillhor du nagon medicinsk riskgrupp for den pandemiska flu

———————————

basis for pandemic vaccination (Pandemrix)
the patient

for vaccination against pandemic influenza, please answer the following questions
1. have you ever had any severe reaction (such as dizziness, fainting, shortness of breath or a rash)
yes/no/do not know
2nd Are you allergic to eggs
3rd medication you with any blood-thinning medicine, such as warfarin or Fragmin? (Not Trombyl)
4th you have an illness or medication that affects your immune system
5th have you recently (within 1 month) received any other vaccine
6th you belong to any medical risk groups for pandemic flu

An interesting algorithm problem: the longest plateau

Recently I met an interesting algorithm problem:

Problem:

Given an array, try to develop an efficient algorithm which can compute the length of the longest plateau. A plateau is a consecutive segment of an array with equal contents. For example, if x[] = {1, 2, 3, 4, 4, 4, 5, 5, 6}, then we have six plateaus which are 1, 2, 3, 4-4-4, 5-5 and 6. And obviously the length of the longest plateaus is 3.

Analysis:

Well, a straightforward idea is try to firstly compute all the length of different plateaus from left to right and then select the longest length. The pseudo-code is like this:

for each element in the array a[]
     if a[i] is equal to a[i-1]
          add 1 to the length for the current plateau
          check whether the current length is the longest one so far
     else
          reset length to 1 // plateau length is at least 1

Whether we need line 5&6 depends on whether we need to store the length of every plateau. If we just want to calculate the longest length then we can keep the code and use the “length” as a temp variable which is only used inside the loop. On the other hand, if we need to keep track of the length of all plateaus, we need to use an array of “length[]” to store the needed information.

/*
 * input: an array a[], the length of the array n
 * output: the length of the longest plateau
 */
int longestPlateau (int a[], int n)
{
	if (n == 0)
 		return 0;

	int length = 1;
	int longestLength = 1;

	for (int i = 1; i<n; i++)
 	{
		if (a[i] == a[i-1])
 		{
 			length++;
			longestLength = max(longestLength, length);
 		}
 		else
 			length = 1;
	}
	return longestLength;
}

Some more:

What if the given array is sorted (in the increasing order) already?

Actually if the array is sorted, the algorithm can be much simpler:

assume the longest length now is L, then we just need to compare a[i] and a[i-L], if they are equal then all the elements between them are also equal (since this is a sorted array!), and we can add 1 to the current longest length. The code looks like this:

/*
 * input: an sorted array a[] (increasing order), the length of the array n
 * output: the length of the longest plateau
 */
int longestPlateau (int a[], int n)
{
	if (n == 0)
 		return 0;

	int length = 1;
	for (int i = 1; i<n; i++)
 	{
		if (a[i] == a[i-length])
 			length++;
	}
	return length;
}

Launched my master thesis finally

Today I talked with my supervisor again and finally and officially launched my Master Thesis!

The next coming 12 months I will focus on developing a methodology on analyzing the performance bottleneck of large-scale multi-threaded software. I am really excited in the challenging problem about how to find the performance bottleneck when we are moving to many-core systems with hundreds of threads running concurrently. There will be a lot of fun and I believe I can learn a lot from it.

Another fun thing is, in the project plan written by my supervisor, the total budget is written as “81 000 KSEK” incorrectly, I hope Ericsson will not notice that mistake and if so, they have to pay a lot of  money to us since they have approved this project:)