Turn An Original/3G iPhone To A Video Recorder

Video recording is one of the most-wanted features of iPhone 3GS to me. My iPhone is still the 3G release and I don't plan on upgrading to 3GS, since I'm not qualified for a standard upgrade until next July. Before I will be able to upgrade to the rumored iPhone 4G, I think it would be cool to do some video recording with my current iPhone. Fortunately, there are several apps now doing this. I did some research and listed what I found here:

App	Resolution	Frame/Sec	Max Length	Features	Price
iVideoCamera	160x213	3	1 min	-	$0.99
Camcorder	320x426	3-7	No limit	-	$0.99
iVidCam (Free)	280x360	3-7	No limit	-	$0.00
iVidCam	320x427	3-7	No limit	Encode queue, File transfer	$0.99
3GS :)	640x480	30	No limit	Fast encoding, more formats	$499.00

I bought iVidCam. It is pretty good. I especially like its encoding queue feature, with which you can encode videos later when you want to record the next one immediately, and file transfer feature, with which you can transfer videos to computers. The quality is not good, of course, due to both the low frame rate and the low resolution of the camera on 3G, but it is better than nothing.

Understanding English Mistakes Made By Native Chinese Speakers

Everybody knows learning a new language is not easy. Learning English is especially hard for native Chinese speakers, because English and Chinese are so different in many ways. I think it might be an interesting idea to write down some common mistakes made by native Chinese speakers. It may more or less help native English speakers understand their Chinese speaking friends better. Most of these mistakes make their English looks or sounds strange, while they can usually be understood with enough context. But some of them may cause misunderstanding and confuse the audience. I make these mistakes all the time. I found it is hard to avoid them especially when I talk fast because my brain is not used to these language features. In the meantime, for the same reason, I tend to tolerate those mistakes. For example, I never pay attention to the speaker's using of "he" or "she". So even if the speaker uses the wrong pronouns, I can figure it out who the speaker refers to from the context. That is probably why Chinese people can easily understand each other even when they talk in English with these mistakes.  Many things could lead to language mistakes, but I will focus on mistakes related to the grammar differences between English and Chinese.

Using wrong gender of pronoun. This is the most common mistakes, because in Chinese, "she", "he" and "it" are pronounced in the exactly same way. The grammar differentiates "she", "he" and "it", but not very strict. So native Chinese speakers are not used to considering gender of pronouns, specially for "she" and "he". A few of my friends often complained to me that they got lost after I talk for a while, because I often randomly switch between "he" and "she" and they can not follow whom exactly I refer to.

Using wrong verb tense. In Chinese, tense is not used. Instead, people rely on context or some adverbs to figure out the time when the action takes place. For example:

吃 (eat)

烤鸭 (roast duck)

吃烤鸭 (eat roast duck)

吃完烤鸭了 (ate roast duck)

要去吃烤鸭 (will eat roast duck)

正在吃烤鸭 (be eating roast duck)

Misusing singular/plural forms of nouns and ignoring verb agreement. Chinese does not have grammatical number, which causes three common mistakes:

• Misusing singular/plural forms of nouns, like  "I have a computer", " I have two computer" or "I have many computer".
• Using uncountable nouns as countable nouns, like "bought some waters".
• Ignoring verb agreement, like "Mike drink milk", "there is apples on the table".

These mistakes could be very misleading when there is no enough context indicating the real quantity.

Mixing definite and indefinite articles. This is another very common mistake even when native Chinese speakers write in English, because in Chinese, we do not need to use articles. You may find native Chinese speakers tend to use "this", "these", "that" and "those" instead of articles, since these words are used in a similar way as articles in Chinese. The most common mistakes about articles are missing articles when they are needed or adding articles when they are not needed. I remember when I was in high school, a lot of questions in English exams are about articles. I would say most of them do not really help me understand how to use articles. This is an example:

Let’s go to ____ cinema-that’ll take your mind off the problem for ___ while.

A. the; the
B. the; a
C. a; the
D. a ; a

Not using subjunctive mood. Chinese grammar does not differentiate the indicative and subjunctive mood, so native Chinese speakers often use the indicative mood when the subjunctive mood should be used. This could be pretty confusing especially when the subjunctive mood should be used to express a hypothesis.

Using wrong prepositions or missing prepositions. In Chinese, prepositions are not very critical in grammar. One preposition could be used in many scenarios for different meanings. People often depend on the context and adverbs to decide the meaning of prepositions. For example, the preposition "在" can be used in these sentences:

在墙上 (on the wall)
在冰箱里 (in the refrigerator)
在床上 (in the bed)
在那本书里 (in that book)
在家 (at home)
在桌子下 (under the desk)
在北京 (in Beijing)

Many English verbs work with certain prepositions, such as "go to", "shoot at", "single out" and so on. This is not common in Chinese either. In many cases. prepositions are just not needed.

http://www.englishdaily626.com has some excellent examples of Chinese-style misusing prepositions:

Chinese Style: The sun rises from the East.
American Style: The sun rises in the East.

Chinese Style: The thief got in from the window.
American Style: The thief got in through the window.

Chinese Style: Let's begin from page 10.
American Style: Let's begin at ( on ) page 10.

Chinese Style: There is a limit in my patience.
American Style: There is a limit to my patience.

Chinese Style: Is your house insured for fire ?
American Style: Is your house insured against fire ?

Chinese Style: This is the key of my room.
American Style: This is the key to my room.

Chinese Style: He is a student of Harvard University.
American Style: He is a student at Harvard University.

Company Trip - Day #3

We visited great scene spots around Lake Tahoe.

We had lunch in Keys Cafe. It is a small place, but their food is quite nice.

We saw this, so we bought coffee there :-)

On the way back, Erik got me addicted to a really cute iPhone game - Doodle Jump. That's my second favorite iPhone game now, after Flight Control.

Company Trip - Day #2

Today is a very beautiful day, perfect to have snow sports.

We left our cabin around 9:45. Everybody was well armed and prepared for some fun.

The Heavenly Mountain Resort is less than 1 mile away from our cabin. It looks great.

Two of us tried snowboarding and the rest went for skiing. It is so much fun!

I will also like to feature two of the snow board players, Spiros and myself:

Steak chili is a popular choice for lunch toady.

At night, we played PISOP 2009 final table. Our CEO John Lovitt won the first PISOP bracelet!

Company Trip - Day #1

Sameer and myself caught a very early flight from Chicago to San Jose to meet the rest of the team.

We arrived 20 minute earlier than the schedule. As a Silicon Valley airport, San Jose airport offers free wifi access and computer operation tables with power plugs and USB power plugs. Pretty thoughtful, except that the USB plugs do not seem to work.

We had enough bad weather in Illinois, so San Jose stopped raining right after we arrived. What a warm welcome!

We got everybody together and had lunch at La Bamba, my favorite Mexican restaurant.

Although I already had lunch on the plane, I won't miss any chance I am here:

We left from Mountain View around 1:15pm. This is one of the cars in our fleet:

On the way, we saw a beautiful rainbow across the highway I-50. It is the first time in my life I see a rainbow this close:

Given that Pattern Insight have many coffee lovers, stopping by a coffee shop is necessary to make everybody happy.

South Lake Tahoe, our destination, snows a lot today. When we were close by, the road condition became very very bad.

Even the well-known fast driver, Spiros, drove with caution.

We finally safely arrived at our cabin. It is very nice house, spacial and comfortable.

We had a great dinner at Nepheles. The only thing that made it imperfect was that they do not have food for vegetarians, so Sameer did not have enough food. We went a grocery store and Sameer made some pretty good food by himself afterwards.  

PISOP (Pattern Insight Series of Poker) 2009 warm-up event was hold in the cabin after the dinner. We will have PISOP 2009 main event tomorrow.

Notify 2 - The best Gmail notifier on Mac

I have been struggling to look for a good Gmail notifier on Mac since forever. There are a lot of them, but no one was perfect. I used to use Google's official Gmail notifier on Mac. It is pretty good, but it only supports one account and it misses a few basic functionalities, such as letting the user decide how often to check emails. I asked Erik, who wrote Herald, to write a notifier for people who do not use Mail.App, but he did not have time.

Today, finally, Vibealicious released Notify 2 and I loved it! The previous version of Notify was not an option to me, because it did not support Google App accounts. But Notify 2 has almost everything I need:

• Multiple account support.
• Google App support.
• Basic operations in the app, such as to delete a message, mark as read and such.
• Be able to open a browser window.
• Be able to set up how often to check.

It can be further improved for a few things in my opinion:

• The icon on the menu bar is not pretty.
• It should support single-click disable/enable.
• It should show labels, or even use labels to filter notification.
• It should allow different configuration for different accounts.
• It should support multi-selection of mails.
• The interface is good and clean, but I think it could be cooler :-)

Notify 2 supports many other account types as well. If you want an email notifier on Mac, check it out.

Updates: Just found out that Notify uses MailCore, a framework to process emails via IMAP and SMTP, developed by my pal Matt Ronge.

Great job, Matt!

Should I just stay here? :-)

You Must Do Code Review And Do It Right

Our company started code review about one and half years ago. It is one of the smarted decisions we have made. It significantly improves the code quality and helps programmers learn from each other. Do code review, unless there is only one programmer in your company or you don't care about code quality. I just read a white paper about code review from Smart Bear. It is a very interesting paper. I also have a few tips myself to share.

First, stop sending patches through emails and pick the right tool for code review. As a start-up company, we always prefer free tools. We found Review Board really great. It was developed by a couple engineers in VMWare and used within VMWare originally. It makes the code review very convenient and efficient. We would not have started code review that early if there was no Review Board. With Review Board, all a submitter needs to do is to upload a diff. Review Board automatically pulls files from SCM systems, generates side-by-side diff view and highlights code differences and syntax. People can add conversations on any lines in the diff. Review Board works in an asynchronized way - you don't need to finish a complete review at once. You can do a review piece by piece at your own pace. Review Board also supports follow-up diff files, email notifications and many other cool features. Its interface has been improved significantly after the 1.0 release. If you are open to commercial tools, check out Code Collaborator from Smart Bear and Crucible from Atlassian. I'm not familiar with them.

Second, pick the right reviewer. The simple rule is to pick the people who know the background of your changes and have some time to do the review in the near future. Someone suggested to check the reviewer's schedule first, but I think it is too much for small companies. It would help if the review tool shows information about this. For example, the tool can show how many pending reviews the reviewer has right now and how large they are.

Third, submit reviews in the right size. According to the user study in CISCO, the white paper shows that 200-400 line changes is the right size for one review. The longer a review is, the fewer defects can be found and the more boring the review process will be. I absolutely agree with this. The longest code review I have done is about 80 files with thousands of lines of changed code. I had 3 shots of espresso to finish it and I don't think I did a good job. When a review is about 200-400 lines of changes, I feel that I can finish it in 30-60 minutes, so I can be more focus and careful to read every detail.

Forth, respect your reviewers. Keep in mind that a code review is a big favor your reviewer does you, so try to make it as easy as possible. Prepare the code review well, don't just throw a diff and let your reviewer struggle to understand it. I often review frontend code from one of our engineers. He always attaches screenshots and draws figures to explain the layout and relationship of UI components, which makes the review much easier. I think there are a few things that the submitter should always do:

• Explain the rationale behind the review and how it works
• Explain the reason why to change each of the files, which is usually not mentioned in comments in the code
• Guide the reviewer through the review, such as which files should be read first
• Attach additional documents if they help

Fifth, respect your submitters. When someone sends you a review, it shows that she trusts you. Do the review in a timely manner. If you can't do it in time, talk to the submitter and pass the review to others. More importantly, do the review with responsibility. Code review is the last step to find problems, assume that the submitter already fully tests the changes. After the review, the code will be committed to the repository. So try your best to find problems.

Sixth, a submitter should always address all comments and upload follow-up diffs. This is a ground rule in our company and it works really well. It makes sure that the submitter responds all problems and fixes them in the code. The reviewer won't give "Ship It!" until follow-up diffs are uploaded.

Seventh, code review is a good opportunity to check unit testing code. Submitters should submit unit testing code together with the functioning code and reviewers should be responsible to check if the unit testing code is good enough. Keep in mind that unit testing code is as important as functioning code, so it needs to be reviewed as well. Including unit testing code in code review has a few advantages:

• Code review covers all new code - perfect coverage.
• The reviewer gets very familiar with the changed code after reading the code, its the best time to review the unit testing code as well.
• The only chance to enforce writing unit testing code. Some testing coverage tools can also do this, but they are inflexible and not be able to find missed unit testing code in finer granularity. 
• Unit testing code help the reviewer understand the changes.

Last but not the least, build a positive code review culture. The white paper also mentions this. I think it is very important. We never had culture problems in our company, but we may have it in the future as we grow. There are a few things I think people should do.

• Everybody should realize code review is a win-win deal. Both reviewers and submitters learn something from it.
• As a reviewer, don't be harsh. Ask questions before make statements. Code review is not the stage where you show off.
• As a reviewer, don't force everybody else to write code in the exact some way as you write code. So don't fixating on small things if there is disagreement.
• As a reviewer, inject compliment when you see some cool snippets.
• As a submitter, don't be self-defensive. Remember that the review is about the code, not about people who write the code.
• As a submitter, respond to every comment, nicely. Speak out your reasons if you think some comments are not correct.

I'm happy to hear other good code review experiences.

By the way, Smart Bear also published a book, "Best Kept Secrets of Peer Code Review". I just requested for a free copy from here.


Updates on Dec. 1, 2009: modified the description of how Review Board was developed, as pointed out by one of the authors of RB: Christian Hammond. Thanks, Christian!

Peking University's New Tactic Will Not Work In Reality

(Picture is drawn by Xiaomo Tao. It is from www.jyb.cn)

In China, since 1977 the college entrance exam has been the only way for universities to select students. Although it is just a 3-day exam once every year, it significantly affects tens of millions of people's lives. I'm not exaggerating at all. 10.2 million students took college entrance exams in 2009. When somebody prepares for it, that will be the only thing her whole family care about for about a year.  I believe most of them are single-child, which make the number up to about 30 million. This single-exam policy has been criticized for many years, however, nobody could come up with better solutions.

One of the big changes is to give universities the power to select students, instead of depending on nation's Ministry of Education to do everything for everyone. This is good, because universities can use whatever they think is the best way to pick high school graduates. A few days ago, Peking University, one of the best universities in China, proposed a brave and new tactic. It chose 39 high school principals and let each of them recommend 1-5 students. If these students can pass an additional interview, they will have 30 "free" scores in the college entrance exam next year. This is a new attempt to change the current situation, but the question is - does it really work? Let's start with something I don't like about this plan.

First, one of the key points of this new policy is that the names of these 39 high school principals are public. I don't know how you feel about this, but I feel it is kinda of funny. I'm not sure what it infers. Does it mean that if referees' names are not public, they will not be trusted?

Second, it is not fair to pick certain high schools to recommend students. Does Peking University want to pick students, or another affiliated high school? On the other hand, this is probably a perfect commercial for those 39 high schools. It delivers this message: these 39 high schools are the best high schools in China, go there so you will have chance to be recommended to Peking University.

Third, I think teachers know students better than principals, so they should recommend students. Back to when I was in high school, I only talked to the principal in my high school once or twice. Besides teachers and principals, people outside of schools should also be able to recommend students.

Although I don't agree with all of above, I do understand why Peking University did it. They all boil down to one problem - people do not trust each other. If everybody is trustable, Peking University can simply take any recommendations into account. Unfortunately, they can only trust 39 people after letting everybody know their names. What they want to do is to make accountability very clear. If you have doubts on any of the recommended students, go ask those principals. This also enforces the supervise on referees, so they will not do bad things, such as taking bribes or recommending their friends or relatives.

So, it looks like a good plan, doesn't it? Unfortunately, I don't think it will work in reality. The execution of this new policy will turn to be formalism. Most of those high school principals will probably just recommend students who have best scores in exams - the traditional, but controversial, way to define best students. That is obviously the safest way to do it. Everybody is watching, they don't want to be questioned for doing something "new", or I would say "better". For example, this high school in Chongqing recommended three students who have the best scores in the recent four exams. These students can probably go to Peking University even without this so-called recommendation. There is nothing wrong with doing this, but if all of other 38 high schools do the same, this new policy does not make any sense, because its original goal is to give opportunities to students who are not usually considered as the best - those who do not have the best scores in exams. I'm very curious what other high schools will do next.

Just like many other problems related to education, how to pick students to colleges is a very hard problem. Having admission hinge on a single exam is definitely a bad idea, but it is probably the best way for now, given the realities in China. Things take time to change. If Peking University's new policy can more or less make a step further on the way, it is worth the effort.

Write Parallel Gomoku AI Programs With The Branch & Bound Pattern

In today's lecture, we learned the Branch & Bound Pattern. The main idea of this pattern is to explore huge search spaces with multiple threads/processes while applying bounding or pruning strategies to control the size of the search space. This is a very interesting pattern. It reminds me some fun time in high school. When I was in high school. a very popular game among computer geeks was to write programs to play Gomoku (Also names Five-in-a-row). We let programs to compete with each other to see who wrote the smarted programs. The basic rule of Gomoku is straightforward: two people place black/white pieces on a 19x19 Go board in turns. Whoever make five of her colors in a row wins the game. Branch & Bound Pattern is a perfect pattern to parallelize such gaming problems.

The basic idea to make a move in Gomoku games is to go from the current state of the board, explore as many steps in the future as possible, and pick the move with the highest possibility to win finally. For example, after the first white piece is placed, the search graph is something like this:

It's not hard to see that the search space can be huge. Let's think about the four operations in the Branch & Bound Pattern. We define a function G(state) for each state. G(state) indicates the chance for the program to win finally.

As for branching, it is straightforward. When the program makes a move, it needs to calculate the G(state) for each of the to-be states and pick the best choice. G(state) is actually a recursive function of G(state') where state' is the subsequent states of state. So we need to calculate all G(state') first.

As for evaluating. G(state) is used to evaluate states in the search.

As for bounding, Gomoku game is not as trivial as SAT or integer linear programming mentioned in the pattern. It is very hard to efficiently calculate the bonding value of G(state). What we can do here is to come up with an estimated Ge(state) according to the current state and/or Ge(state) of its sub-states. There are many ideas to calculate Ge(state). For example, we can consider how many three-in-a-row  cases in each side. The more three-in-a-row cases one side has, the more likely that side will win. Usually we use several strategies and give each of them a weight. The final Ge(state) is calculated as a function of all strategies.

As for pruning, if a state has been evaluated in other branches or a state's Ge(state) is worse than the current-best G(state), we can prune the branch started by this state. Of source, there can be many tricks to do smarter pruning than this.

To parallelize the searching process, structure-based parallelization is the best fit for this problem. Because all processors should process states in a single pool, we can use either Synchronized-Single-Pool (SSP) or Asynchronized-Single-Pool (ASP) with shared current-best state and visited states. I think the best-state-first strategy may work better then the depth-first strategy. We need to carefully limit the maximum depth to search regardless which search ordering strategy we use.

It is already close to the end of the class, otherwise I think it is a good idea to have a Parallelized Gomoky Program Contest in the class ;-)

Given That Deterministic Replay is Still Slow, What Should We Do for Parallel Debugging?

Debugging has been tough, and it becomes tougher these days. One of the reasons is that people write more parallel programs and introduce concurrency bugs. Concurrent bugs are especially hard to debug, because many of them do not always show up. There can be many things that make a bug hard to fix, not being reproduced is probably the worst one.

What is the ideal way to debug a parallel program? In my mind, a parallel debugging framework should provide the following:

• In the production run, records the execution with zero or very low overhead.
• In the debugging phase, let people deterministically replay what happened when the bug manifests. It is even better if the replay can go both forward and backward.
• Programmers can attach their favorite debuggers to the replay session.

This even sounds tempting to sequential debuggers, doesn't it? However, the real world is not ideal. The main problem is that recording introduces huge overhead in the production run. A lot of research has been done to make it faster, but still, there is no very realistic solutions yet, especially for applications that run on multi-processors. In this years SOSP, there are two papers on this topic: Do You Have to Reproduce the Bug at the First Replay Attempt? -- PRES: Probabilistic Replay with Execution Sketching on Multiprocessors and ODR: Output-Deterministic Replay for Multicore Debugging. They both send out three interesting messages:

• They are both software-only solutions.
• They both make compromise - push the complexity from recording to replaying.
• They both work on multiprocessors.

This trend shows that people become more realistic about this hard problem. First, software-only solutions are preferred, because they are easier to implement. Don't get me wrong. I'm not saying hardware-based or software-hardware-hybrid solutions are unrealistic, but they indeed take longer time to become real. Second, people compromise something that is less important to make more important things to be feasible. Third, multiprocessors are so common today, so a realistic solution should work with it.

The idea of PRES is to sacrifice the efficiency of replay. Instead of reproducing the buggy execution at the first try, it requires more than one attempts to reproduce it. Meanwhile, the reward of this is that it only needs to record much less information in the production run. One could think of it as PRES drawing a "sketch" in the production run, instead of a "finished paint". Although it may need to try several times to recover the "finished paint", but "sketch" is fast and enough to catch a rough idea about what happened. If painters use this idea, why can't we? Very smart! During replaying, PRES uses both the sketch from the production run and feedbacks from previously failed attempts. The idea is that when PRES encounter a data race that has not been recorded in the production run, it makes a random guess. As soon as PRES finds out the execution does not match the sketch any more, or does not reproduce symptoms in the buggy execution, what it will do is to roll back a bit, flip some data races and give it another try. This actually reminds me about another paper, Rx, which is one of the system research papers that I like the most.

The idea of ODR is to sacrifice the accuracy of replay. Instead of reproducing the buggy execution based on internal values, it tries to reproduce an execution that has the same output as the buggy one. Output includes segment fault, core dump, print out strings and such. The reproduced execution may be different from the buggy one, but the rationale behind this idea is that if it has the same output, it is very likely that the bug that appears in the buggy execution also manifests in the reproduced execution. If output-determinism is enough, why would we want value-determinism?

There are many other good papers about deterministic replay for debugging parallel programs. If interested, you can find more from the references of these two papers.

Besides academic research, VMWare's replay debugger is a production-class parallel debugger tool. Although it only works for single processor execution, it has almost everything an ideal parallel program debugger should have. I was really really impressed. E Lewis gave talk in Google about it:

Programming is not as easy as it sounds

(After reading "Teach Yourself Programming in Ten Years" by Peter Norvig)

I found this article after I read Prof. Johnson's blog post about it. All the points from this article are so true and I think every programmer should read it.

Back to when I was in college, many students in Computer Science major thought programming is easy and kind of boring. It only requires time but less skills. Many people who have been programming for years after school still think in the same way. I think the major reason is that as computer hardware, programming languages and development tools has been improving so fast in the past decades, writing runnable and reasonably fast programs requires lower and lower learning curve. Even if you know nothing about computers, you can probably write a piece of Python code to do quite something in one or two days. However, does it really mean that programming become no-brainer now? It certainly does not.  The superficial simplicity prevents people from thinking more about it. Just like Peter Norvig, I also have a few tips about how to teach yourself programming.

First thing first, make yourself interested in programming. Maybe programming is not one of your dream jobs, but if it is what you do now, try to become interested in it. This helps you kill the pains and have more enjoyable programming time.

If you did not know computers much, try to learn something about it. I strongly recommend a few books for basic concepts: Computer Organization and Design: The Hardware/Software Interface, Computer Architecture: A Quantitative Approach,  Modern Operating Systems and Computer Networks. These books are all very well written and teach you many things you should know when you write programs. Without this knowledge, you won't be able to understand many important aspects of programming, such as pointers, why buffered I/O streams are faster, how to use threads correctly to avoid concurrency bugs and so on. Additionally, Jeff Dean has a list of numbers he believes everybody should know:

(from the slides of Jeff Dean's talk

Designs, Lessons and Advice from Building Large Distributed Systems)

Read the Design Patterns book once a year. I personally think this is the best book about programming I have ever read. It opens a new door to think about programing. When you read this book, think more beyond patterns for OO programming. There are actually programming patterns everywhere and they are powerful weapons to conquer system design problems. The more patterns you know, the more choices and beautiful ideas you will have when you design a system.

Open your mind and learn more languages even if you do not need them for work. Learning a new language helps you re-think programming. For example, say you are a Java programmer originally, when you learn Python, the first thing you may think about is dynamic typing. It may make you feel uncomfortable at the beginning, because you are so afraid that you will make typing mistakes. But after a while, you may feel dynamic typing helps you write programs faster. OK, now what, is it good or bad after all?

Read other people's code. One of the best ways to learn is to learning by examples, either good examples or bad examples. You can read open source code or read code written by your colleagues. Remember it when you think their code is good and try to improve it when you think their code is not that good. Our company has very strict code review policy. I learned a lot by reviewing other people's code and letting them review my code.

Get familiar with software development tools. There is a Chinese epigram saying "sharpen your knife before you cut wood" (工欲善其事，必先利其器). Many great development tools can significantly improve efficiency and quality of software development. Take Java as an example. Java is famous for having many great tools. Just to name a few open-source tools:

• IDE: Eclipse, NetBeans
• Buidling: Ant, Maven
• Debugging: jdb, jhat (heap analysis), jconsole (monitoring), Eclipse integrated debugging features. 
• Profiling: jprof, NetBeans Profiler (I really like this)
• Static analysis tools: FindBugs, PMD
• Unit testing: JUnit framework, Emma (check unit testing coverage)

Always keep in mind that testing rocks, debugging sucks. I did not really realize this until I started working in the company. I would say making solid testing is one of the biggest lessons I learned in the real world. Good testing can totally change the quality of a program and "life quality" of programmers. Once you adopt test-driven development, you will never go back.

Think while you do. This is more about attitude. Even if you are in charge of just a small component of a large system, don't always bind your mind to that particular component. Think about big pictures, such as how the whole system works, what are good and what are bad, how to improve it and so on. If you think more, you will find you can learn a lot even if you are working on something that you thought was boring before.

Happy programming. :-)

When to learn a new language?

"A language that doesn't affect the way you think about programming, is not worth knowing."

-- Alan Perlis
(Epigrams on Programming)

I like this epigram so much. How did the languages you have learned affect the way you think about programming?

What does Steve Jobs say about design?

''People think it's this veneer -- that the designers are handed this box and told, 'Make it look good!' That's not what we think design is. It's not just what it looks like and feels like. Design is how it works.''

-- Steve Jobs

"Stress Testing On Concurrent Problems - CHESS

Testing concurrent problems, such as data races, deadlock and so on, could be very hard. This kind of problems only happen with certain input and highly depend on how threads/processes are scheduled. In order to have good coverage of threads/processes schedules, people need to run the same testing many times and keep their fingers crossed to run into concurrent problems if there is any. This doesn't work well for problems that happen very rarely. People sometimes also use stress testing, testing with very heavy workload, to find potential concurrent problems. But this doesn't work well either, because heavy workload may introduce more concurrent operations, but it does not mean to introduce the right concurrent operations/orders to trigger concurrent problems.

The CHESS project from Microsoft Research tried to solve this problem. CHESS uses model checking technologies to explore different concurrent schedules, more specifically - how threads interleaves with each other, to find the one with concurrent problem. Once the problematic schedule is found, CHESS is able to accurately reproduce it later and let programmers debug the program. As an example from their paper, CHESS reported a deadlock after executing 6,727 different schedules in about 20 seconds. This is apparently is one of those tricky current bugs that take days to find.

The most interesting part to me about CHESS is how it controls the state space. It is not hard to imagine that the number of different schedules of a multi-threading program can be huge. CHESS uses various technologies to shrink the search space. There are two major strategies. The first one is preemption bounding - to limit the number of preemptions and use them carefully. According their previous paper, it shows that if the schedule desides a part of the preemptions, the rest of the schedule is determined automatically. Basically a problematic schedule only depends on a few preemptions to happen at the right places. The experience shows that having at most 2 preemptions is enough to find serious concurrency bugs. The other approach CHESS uses is to cache visited program states to prune redundant search. The questions is that what can be used as program state in terms of concurrent behaviors? CHESS uses happens-before graphs. The rationale is that "two executions that generate the same happens-before graph only differ in the order of independent synchro-nizations operations".

Microsoft Research already integrated CHESS into Visual Studio 2008. It works for multi-threaded single-process application. If you are interested, download and give it a try. For latest updates about CHESS, check out its blog.

Refactor Java Loops With ParallelArray

(After reading "ReLooper: Refactoring for Loop Parallelism")

The ParallelArray Framework is a new feature in Java 7  that provides parallel operations on an array. For example, the programmers can apply a modification on each element of an array, map each element of an array to element of another array, reduce a set of element of an array to a value and so on. These operations will be parallelized by with ParallelArray Framework automatically. ReLooper is tool that helps programmer rewrite existing loops using ParallelArray to improve performance. It delivers 1.32-1.96x performance speedup on a 2-core machine.

Rewriting a loop to a parallelized version with ParallelArray is not hard. The hard part is make sure the new loop behaves correctly as the originally loop. Relooper uses several static analysis technologies to analyze a loop to make sure it can be safely parallelized with ParallelArray. If Relooper finds any potential problems, it warns the user before start refactoring. There are mainly three constraints that may prevent a loop from being parallelized.

First, the original loop should go through all elements in the array in order and there is no inter-iteration dependency. If the original loop is a for-loop. Relooper should check if the iteration variable is used as the index of the array and if the iteration variable changes from 0 to the length of the array. Relooper also checks if any control flow statements, such as break, return and continue, skip some array operations.

Second, Relooper checks if different iterations of the original loop access shared data. If there is any conflict accesses, the original loop can not be parallelized easily. This check if not trivial because of the complexity of memory reference analysis and method calls. Relooper develops an inter-procedure data-flow analysis to do the check.

Third, the original loop should not have blocking I/O operations. Because ParallelArray uses Fork/Join Framework to parallelize operations, blocking I/O can significantly hurt the performance.

These constraints make a lot of sense, but in my opinions, they do not completely kill the opportunity to parallelize a loop. It would be better if the paper can describe what should be done if any of them happen. Is there anything smart Relooper can do to still parallelize the code, or programmers have to be involved to make the decision or even adjust the code?

Relooper is implemented as an Eclipse plug-in and you can download it from its website. I really appreciate the author's effort to make it real and usable.

Refactor Java Programs To Take Advantage of Concurrency

(After reading "Refactoring sequential Java code for concurrency via concurrent libraries".)

There are more and more new libraries and language supports to help programmer write better concurrent code. They greatly benefit writing new code, but how about existing code? We probably need new code refactoring technologies to improve existing code.  This paper proposed a tool, CONCURRENCER, which can refactor existing sequential Java programs to take advantage of the java.util.concurrent (j.u.c) library. CONCURRENCER contains three main refactoring technologies.

First, it can convert usages of an int field into AtomicInteger. This can make sure that access to this field become thread-safe. Besides AtomicInteger, the j.u.c library also provides a few other atomic data types.

Second, it can convert usage of HashMap into ConcurrentHashMap. The traditionally way to make a map thread-safe is to use lock to protect every operation on this map, which introduce unnecessary contention.  ConcurrentHashMap is a pretty cool class in the j.u.c library to solve this problem. It uses a smarter locking mechanism to allow concurrent retrieval operations and partial-concurrent update operations. It divides the hash table into chunks and each chunk has its own update lock. So different chunks can be updated concurrently.

Third, the most complex, it can convert a recursive method to a new version based on the Fork/Join framework. To solve a divide-and-conquer problem, the Fork/Join Framework recursively solve one task by using multiple threads to solve its sub-tasks, wait all of them to finish and then aggregate the results for the original task. I wrote about this framework before. According to the experiments, this refactoring strategy can improve the average performance of a sequential recursive method to 2.97x (on 4-core systems).

I like this paper because I think it is practical. Each of these three refactoring ideas looks small, but if they can be correctly applied, they can much improve the code quality and performance of existing sequential programs. The authors also mentioned that they keep looking for refactoring opportunities to take advantage of other features in the j.u.c library.

One problem of CONCURRENCER is that it depends on the programmer to pick the code to refactor. It would be more helpful if it can collaborate with other static analysis tools to find this code automatically.

"Creeping Featurism is a Strength" if it is done right.

(Reading notes for Chapter 11 of "Beautiful Architecture" GNU Emacs: Creeping Featurism Is a Strength)

This chapter describes the software architecture of Emacs and discusses its creeping featurism "problem". Creeping featurism means that people tend to put more and more features into a system and eventually make it too complicated to manage. Many people think creeping featurism leads to no good, but if it can certainly become a strength if it is done right. Software becomes very complicated these days and people expect more and more from software. So a closed system is very hard to be very successful. We can see this tendency from desktop applications, like Firefox, iPhoto and so on, to enterprise software, like SplunkBase, to web-based applications, like Facebook.

Extension is especially important for open source software which usually has a lot of uncentralized developers and users.  I will talk about a few thoughts on how to make a software system open to extensions but in the meantime prevent creeping featurism.

Firstly, a system should have a fairly simple data model. The book chapter compares the data model of Emacs and the data model of Microsoft Word. I think this is a very good example. The simplicity of Emacs data model, strings of characters, makes it much easier to extend then MS Word, I'm not criticizing MS Word, after all, Emacs is an editor, not a word processor.

Secondly, the interface between the core part of a system and its other rich features should be clear and well defined. Emacs' MVC model is a good example again. Views are automatically updated once a relevant model change is detected. The core controller is written in C, but the controller code of most command we use is written in Emacs Lisp, which is also used as the major language to develop extensions. This design lets extensions integrated into the whole system naturally. Most extension code can be modified without recompiling the core Emacs, even without restarting Emacs.

Thirdly, a system should have a good default set of features that fit common needs. Most Emacs users only use a small subset of its features, but a complete installation of Emacs is already pretty big, it takes time to start and occupies quite some system resource when running. This is actually one of the major attacks from Vi advocators. To find the balance between efficiency and reasonable set of features is hard. This article presents one solution of having different sets of default features, like expert mode, normal mode, hardcore mode and such.

Fourthly, to make it very easy to install an extension. If it takes hours to install an extension, I don't believe people will do it at all. Emacs extensions are not trivial to install. For most of them, you need to modify your ".emacs" configuration file and copy package files to the right place. For some of them, it even requires compiling and/or installing new stuff. Software like Eclipse and Firefox do a better job on this.

Finally, to have a good platform for people to share and look for extensions is important. If a system is designed to be extend, extensions should be managed efficiently and provide good communication between people who write extensions and people to require new features.

Making enterprise software extendable and control its feature scale is quite different from to do so to open source software. I will probably write another post about that.

Why to implement a JVM in Java?

(Reading notes for Chapter 10 of "Beautiful Architecture" - The Strength of Metacircular Virtual Machine: Jikes RVM)

I heard about Jikes RVM before as popular in the Java runtime environment research community, but I didn't think through what exactly implementing a JVM in Java benefits research in particular, or in general. I still held this question before I read this chapter.

This chapter is pretty clear. I especially like the part talking about myths surrounding runtime environments. It would be better if the book can also compare Jikes with other metacircular architectures, not necessary JVMs. Combining this chapter and some other articles, I think the advantages to implement a JVM in Java are two folds. First of all, it offers an opportunity to have better understanding of the language, especially how applications talk with run time environment and performance-critical features. So we can implement them in a better way. Secondly, in terms of performance, this implementation moves the Java/non-Java boundary crossing overhead below JVM instead of above JVM, which opens doors to more efficient implementation ideas and dynamic optimization opportunities. However, the question is that whether it is desirable to build a production-class JVM in Java. I still doubt it.

As a big system fan, I'm interested on how Jikes bootstraps itself and communicates with hardware/OS. I went through some research literals and found this paper, Implementing Jalapeño in Java, is a must-read. Jalapeño is the predecessor of Jikes. This paper describes the original motivation of the Jalapeño project in IBM Research and the challenges they encountered at the early age. Very interesting. You can find answers for these questions:

• How do they implement the first few essence components of a JVM, a not-very-efficient baseline compiler, a dynamic class loader, a simple memory manager and a debugger?
• How do they generate a boot-strap image of these components and load it to start Jalapeño?
• How does Jalapeño interface the hardware - through a special class MAGIC.
• How does Jalapeño interface the operating system - via ~1000 line C code to invoke system calls through the standard C library.

One thing that would have made this paper even more interesting is to talk more about the trade-offs between different implementation alternatives.

From Thread.join(), to invokeAll(), to the Fork/join Framework

Fork/join Framework (FJF) is new in Java 7. It was developed by Doug Lea based on his paper "A Java Fork/Join Framework". Simply speaking, the Fork/join Framework helps parallelize divide-and-conquer algorithms by multi-threading. It divides a big chuck of work into smaller pieces, sends them to a set of threads to process, waits until all of them are done and aggregates the results.

This idea seems to be simple and straightforward, but there are a lot of things to think about to make it work well. Without too much thinking deeper, this idea can be implemented by just what Java Thread class provides. For each task, if it is small enough, solve directly; otherwise create several threads and let each new thread handle a smaller chuck. Then call join() method on each new threads to wait until all of them finish. Finally merge results. There are a few problems of this approach. First of all, creating threads is expensive. When a task is fairly small, the time spent in creating more threads is even longer than the computing time spent in solving the task itself. Second, there will be a lot of threads created. These threads compete for CPU cycles which result in worse performance. Third, programmer needs to write specific code for each divide-and-conquer algorithm. It makes code harder to write, read and maintain.

If you are familiar with the java.util.concurrency package introduced since Java 5, you may want to suggest to use a thread pool based executor and call invokeAll() to process divided tasks. This saves the overhead of creating threads and limits the number of threads - a big step ahead, but there is good odds that this idea will not work well either.

• The tasks queue, most likely an unbounded blocking queue, that is shared by all threads in an executor could become a bottleneck, because every thread needs to lock the queue when it gets tasks from the queue or puts new sub-tasks into the queue.
• What should happen when a thread is done its job? It may not be able to process the next queued task because that task may still be waiting for join its sub-tasks. In this case, how could this thread pick another task to continue instead of being idle?
• Programmers still have to write a fairly big amount of code in addition to the code that runs the algorithm itself.

The Fork/join Framework solves these problems. Each worker thread maintains its own tasks scheduling queue. This prevent one single shared queue from being a bottleneck. What should a thread do when its own tasks queue becomes empty?

Here comes the smartest trick in Fork/join Framework - the "work-stealing" strategy. A scheduling queue of each thread is a double-end queue. When a task needs to be divided into smaller tasks, it sends all its sub-tasks to one worker thread. So as the time goes, the head of a queue contains bigger tasks and the tail of a queue contains smaller tasks. For each thread, it processes tasks from the tail of its queue (FIFO fashion). This utilizes data locality and also tries to concentrate on all sub-tasks of one task as much as possible. When a worker thread finishes all its own tasks, it "steals" tasks from the head of other threads' queues (LIFO fashion). There is a good chance that this thread will pick a big task and thus it can further divide this tasks without affecting other on-going work. It won't need to "steal" again in the near future. For each double-end queue, one thread works on one end and other threads may work on the other end, but not very often. This is very good to prevent contention on queues.

Last but not the least, with the Fork/join Framework, programmers can focus on the code that tackles their own problems. The code could be much cleaner and easier to read.

In his paper, Doug also evaluates the Fork/join Framework by solving a few real problems. He mentioned that the performance can also be affected by garbage collection, memory locality and bandwidth, task synchronization and task locality. These aspects should be considered careful when design the algorithm to utilize the Fork/join Framework. I like this paper, it is a typical Doug-style paper and it is a lot of fun to read.

The Fork/join Framework is a part of JSR-166. It can be downloaded from the JSR-166 interest site.

Five Myths About RESTful Web Services

I will try to avoid comparison between REST and WS-*, because there are already a LOT of discussion  about it and some people get biased sometimes. I just want to describe some of my understanding about RESTful services in this post.

Myth #1, REST is a new technology.

REST is not a new technology, it is not a new standard either, at least for now. It is a new way to think about web-based application architecture. REST architecture can be implemented by existing technologies and it won't be hard to do it. I really like the idea of REST because it explicitly describes a good way to architect a system.

The very key of REST-style architecture is Resource Oriented Architecture (ROA), mainly as opposite to Service Oriented Architecture (SOA). Many advantages of REST-style web services are based on this key. For example, URLs becomes cleaner and bookmark-able in RESTful web services, because each URL always represents a certain resource.

Myth #2, REST is too new, so there is no good framework to use.

As stated in Myth #1, RESTful web services can be implemented by existing technologies. In the meantime, people develop framework to make developing RESTful services easier. Sun started working on JSR-311 since 2007 to provide standard APIs to help develop RESTful services. There are already a few server side framework to use, to name a few Java framework: Restlet, RESTEasy from JBoss, and Jersey from Glassfish.

Myth #3, REST is panacea. Any applications can be built in REST style.

I don't think this is true, although many people think it is. The real question is that is the application resource oriented or service oriented. Some applications are inherent SOA. If you make it RESTful, it will just look awkward. Take a simple banking system as an example. If we use service oriented style, a withdraw transaction can be described as:

withdraw(String accountNumber, float amount);

However, if we really want to make it resource oriented, it would be anti-intuitive, say what should be the resource, an account or an amount of money? Which HTTP method should we use?

Myth #4, as long as a service is invoked by an URL and responses XML, it is RESTful service.

Certainly not true. Take Flickr API as an example. Although Flickr API offers three different types of request format, REST, XML-RPC and SOAP, they can be called in the format as:

http://api.flickr.com/services/rest/?method=method-name&param1=value1&......

most of these APIs are essentially service oriented. They are not RESTful web services.

However, most of them can be modified to be RESTful. For example, there are three APIs that work on photo tags:

• flickr.photos.addTags
• flickr.photos.removeTag
• flickr.photos.setTags

If we consider tags as resource, we need one URL to identify them:

http://api.flickr.com/services/rest/v1/photo/photo-id/tag-name

A PUT method on this URL add this tag to this photo and a DELETE method on the URL removes this tag from this photo.

Myth #5: REST is easy.

I think REST is a very clean way to design a system. But I won't agree that REST is significantly easier than other ways. Developers still need to learn a lot of things to build a successful system. There are still many decisions to make and some of them can be tricky. Just to name a few:

• How to define resources and presentations?
• How to apply HTTP methods?
• How to use cache? What resources can be cache and what can not? When to invalidate cache?
• Be really careful about POST.
• Security?