Xiao Ma's Blog

Facebook acts just like any other monopoly

2010-05-22T16:25:00.000-07:00

Facebook started with a brilliant idea, just like any other monopoly.

Although Facebook didn't invent social networking, it did a terrific job to execute the idea, grow insanely fast and beat its competitors, just like any other monopoly.

Since Facebook got to a great position, it started doing something, which usually early-age start-ups try hard to avoid - pissing off users, just like any other monopoly. More specifically, as you already knew, it keeps ignoring users' privacy.

One important thing that backs it up is its business, social networking. Social networking is one of those businesses that once you use it, it is way too complicated and expensive to switch to other alternatives. If you already have hundreds of friends on Facebook, how could you easily shutdown your account and create another network somewhere else (which is nowhere for now, unfortunately)? Another good example is Microsoft's territory in enterprise software. Most companies don't even want to get rid of IE6 due to the cost, let along Windows and Office.

The whole philosophy behind Facebook's privacy policy changes is two folds, in my opinion.

First, Facebook is betting that 90% of its users don't realize that they should check the policy, or they don't care. So it makes the default setting to share as much as possible. 90% of the rest of users won't check the policy in detail if it is too complicated to understand. So it makes its policy implicit and complicated and makes policy setting interface extremely difficult.

Second, with its dominant position, Facebook can experiment kicking off bad policies without worrying much of losing users. Think about it, even if the policy doesn't work out eventually, what's the worst thing that could happen? Facebook can just roll back the changes and apologize. It will still have its, I don't know exactly, hundreds of millions of users, even if tens of thousands of them are pissed off so badly and quit. Again, this is just like any other monopoly.

Don't get me wrong. I don't completely hate Facebook. With no doubt, Facebook changed the way we share. On the day any of us created Facebook accounts, we admitted that we want to more or less share something. I also really like a few ideas from Facebook, such as Facebook Development APIs and Facebook Connect. I especially believe Open Graph is a great idea, if it is done right. While Google is aggregating information from the web, Facebook is aggregating information from our lives and our minds. This is HUGE. With this information, Facebook has big potential to really build better web to help people. For instance, I'm a big fan of Aardvark, which I think is a perfect example with which Facebook could make huge difference based on its user base and information. I'm actually surprised when Aardvark was bought by Google but Facebook, maybe Facebook has already started building its own.

It's not very fair to blame Facebook for everything. Its whole business model is based on the number of users and the amount of information users are willing to share, or are forced to share, or share without even being aware of it. Facebook wants to grow and it does what it is meant to do. It depends on the user to accept it or not. When there are no other options, Facebook wins. What Facebook really needs is competitors, good competitors, just like any other monopoly.

Tough Waiting

2010-04-03T21:53:00.000-07:00

Mar. 30th - Received the shipping notification from Apple.

Mar. 31st - Found the package left from Shenzhen, China.

Apr. 1st - The package arrived in the U.S.

Apr. 2nd - I do not want to ship it to my home, for some reason, so package is shipped to the building where my office is. Since the building is closed on Saturdays, I called UPS several times to make sure it will be delivered. I asked if the delivery person can call me once he comes by the building, the answer is that they do not carry phones. I asked if I can pick it up in local customer center, the answer is "we made special deal with Apple, we cannot change anything before the first attempt of delivery". So I decided to wait at the door for the UPS delivery tomorrow.

Apr. 3rd 8:30 AM - Found on the UPS tracking page that the package arrived in Decatur at 5:45am, which is about one hour away from Urbana. Right on track!

Apr. 3rd 8:50AM - I went to the office and sit at the door of the building. It is nice that there is a power plug next to the door, so I can do some work while waiting.

Apr. 3rd 9:30 AM - Called UPS to check again. There is a voice message about iPad delivery, which says that all pre-ordered iPad packages will arrive by the end of the day. I talked with a representative, she told me that the normal Saturday delivery schedule, packages are delivered before noon, does not apply to iPad deliveries today. She can not help me locate or contact the delivery person, but she's sorry that I need to wait at the door.

Apr. 3rd 9:53 AM - Refreshed the UPS tracking page again, found the package actually has arrived in Urbana at 8AM. Nice!

Apr. 3rd 11:09 AM - It stopped raining. I got some work done. A big goose dropped by.

Apr. 3rd 11:30 AM - The status of the package still hasn't changed into "Out For Delivery", so I called UPS again to double check if they deliver packages to business addresses on Saturdays. This time I was told that they do not. So I decided to have lunch first. If the status changes to "Out For Delivery", I will come back.

Apr. 3rd 11:50 AM - Left the office.

Apr. 3rd 12:50 PM - Found the status of the package became "12:03 AM - Exception: THE RECEIVER'S LOCATION WAS CLOSED ON THE 1ST DELIVERY ATTEMPT. A 2ND DELIVERY ATTEMPT WILL BE MADE". So I called a supervisor in UPS. He promised to contact the local UPS center and make the second attempt today, in about 2 hours.

Apr. 3rd 1:10PM - Went back to the building and sit at the door.

Apr. 3rd 1:40 PM - Got the iPad.

Although the waiting is not that pleasant, iPad is so awesome! She is so surprised.

iPad is Not a Toy. You Do the Math

2010-01-30T19:18:00.000-08:00

Apple released iPad. Not too much surprise. It is a tablet and it is a lot like what the rumors said. Did I expect too much? Yes. Am I disappointed by iPad? Not really. Do I lose faith in iPad? Absolutely no! iPad is a great product. It is not just a big iPhone. It is not just a toy. It started changing how a computer should work for most of the things we use computers for.

During his presentation, Steve Jobs clearly defined the market of iPad - it is a "third category" mobile device between smart phones and laptops. This definition again brings back the question that everybody asked before - why do we need a third category mobile device? As for Steve Jobs' answer, the reason is that we need to do "key things" in a "far better" way. I totally buy this rationale. We really need this "third category". It covers the most important tasks, including reading emails, browsing the Web, listening to musics, watching videos, playing games and reading ebooks. It also covers a lot of scenarios where the first two categories are not good enough. These scenarios add up to a significant amount of time of using a computer. All these boil down to a simple math problem:

The reality is that "A" is becoming bigger and bigger and "C" is becoming smaller and smaller. Obviously, this leads to a more and more significant difference. So do the math, then you will realize that iPad is not just a toy, it is a serious and useful device for everybody.

One could certainly argue that even if the difference becomes bigger, I can still use either a smart phone or a laptop to cover it. Yes, of course you can, but iPad just makes it far better than a smart phone or a laptop. It is fast. It is convenient. It has a new human-computer interface, which matters the most.

The keyboard-mouse-monitor interface has not changed for decades. It has been working pretty well, but it is certainly not the ideal one. What iPad provides is a much better interface. In my opinion, the human-computer interface should be as similar as possible to what we do things in the real world, meanwhile leverage computing power to help us do things better. Take the photo app on iPad as an example. It makes photo piles and lets the user to spread/stack up a pile of photos. It is better than how iPhoto works. It is more natural and fun. In the meantime, it helps people share photos, make photo books, organize photos by tags, geographic information, faces and such, which traditional photo albums can not do. This is how a computer should work.

Many people think iPad is a content consumer. I don't think it is true. It is brilliant for Apple to port iWork to iPad, which makes iPad much more than a content consumer. iWork significantly enlarges the use case space of iPad. For example, think about high school students, or even college students. They can use iPad to take notes, read text books, write reports and make presentations. How cool is that?

Is iPad good enough for everything? One can easily come up with thousands of things that iPad can not do. It's true. I can come up with thousands of things that a laptop, or even a desktop can not do as well. Does it prevent me from buying a laptop instead of a super computer? No. Because a laptop is good enough for most tasks. The just unveiled iPad is not intended to replace everything. But for average computer users, it does most of their tasks in a much better way. As for the next generation, or the generation after... I think iPad will become the first thing to think about when somebody needs to buy a computer.

Thirty years ago, nobody could imagine that a computer can be put on a desk, until Apple released Apple II and soon IBM released 5150. Ten years ago, nobody believed that a laptop could be as powerful as a desktop. Today, most of my friends have only a laptop and a big monitor at home. It is way too early to conclude that iPad, tablets in general, won't be the next mainstream personal computing device. Give it time, things will change. iPad has no doubt just started this change now.

What To Expect When You Are Expecting - Apple Tablet

2010-01-16T16:04:00.000-08:00

As the rumored release date is coming, "Apple Tablet" (let's call it this for now) has stimulated heated discussion and a lot of speculation. It is just a lot of fun to think about what Apple will do.

Just like many other products, two fundamental keys of Apple Tablet are the price and the market. The biggest market problem of Apple Tablet is that it more or less overlaps with existing Apple product lines. The first question people will ask themselves is that if I already have a desktop and a smartphone, maybe also a laptop, why should I buy a tablet? When and where will I use it? Will it be very useful or just sort of useful? What price would I accept to buy a widget that is "sort of useful" or even just a fancy expensive toy? These are all valid questions. So what should we expect from Apple Tablet? Before we think about what to expect, let's start with what not to expect.

Apple Tablet will not be a traditional browser-only netbook. First of all, Apple's strength is not making Web browsers, although Safari is great. Apple's strength is design and user experience. So there must be awesome client applications besides a Web browser. Second of all, 99.99% of the current web sites are not touch-screen friendly. They are not designed for touch screens at all. Even in the future, I don't think websites can easily provide as good user experience as client applications can (note that I did not say desktop applications). I always prefer client applications even if most of the storage and computation is thrown to the cloud, with only a few exceptions of Google's great products, namely Gmail and Google Reader.

Apple Tablet will not be an e-reader. This is not only because Steve Jobs said "people don't read anymore", it just does not make sense for Apple to make a dedicated reading device, because it will need to make another device to provide more later. Kindle is a great innovation and I have been hesitating between buy or not buy a kindle for a long long time. But what Kindle can do is just a small part of personal computing. Maybe Apple Tablet will not be as good as Kindle in terms of reading book, but it will be a reasonable e-reader plus a lot more.

Apple Tablet will not be a Macbook with a touch screen. Apple Tablet will be smaller, lighter and may provide less computing power. It will be easier to carry around. Maybe not much easier than Macbook, but let me give you one scenario for instance: using Macbook when you were in the restroom is awkward, but Apple Tablet will fit nicely. Apple Tablet will also be easier to use, and most importantly, thanks to new possibilities in interface design, it will be more fun!

What should we expect then? In my guess, Apple Tablet will be a revolution that changes the way how mainstream people use computers, including both desktops and laptops. Fortunately, Apple is a company that is capable to do such a thing.

I drew a picture of four main products lines in Apple. iPhone is irreplaceable, because it is the only one you can carry with you all the time. Apple Tablet is under "Fit In Pocket", together with Macbook and iMac, but it is way portable than iMac and better than Macbook. Apple Tablet is just cross the "Enough For Most User" line, which makes it capable to say no to both Macbook and iMac.

John Gruber thought Apple Tablet will be a kind of a replacement of Macbook. When people want to by a portable device from Apple, they will consider either a Macbook or an Apple Tablet, but not likely to get both. I agree with him, but I think Apple Tablet is more ambitious than this - most people will only need an Apple Tablet, maybe plus an iPhone.

First of all, why must we have a desktop and a laptop? For most people, the border between desktops and laptops is vague and there is no need to have both, because the mobile hardware is so advanced and more and more computation and storage is being moved to the cloud. You can store your documents on the cloud, your pictures, and even your musics and videos - remember that Apple has the best online streaming service for movies, TV shows and it recently acquired Lala to stream musics. So in my opinion, the next generation of personal computing should be always portable, even in a house, I want to move my computer wherever I want. High-performance desktop will be only needed for people who want to edit a movie or something.

Why must we use a keyboard and a mouse to talk with the computer? I feel sorry that my mom has to struggle with typing when she starts using computers. There must be some ways that are more natural and easier to interact with computers. This is actually the most exciting thing I would expect from Apple Tablet - a phenomenal brand new user interface. Imagine you could dance your finger on the screen to organize your pictures and emails. Imagine you could make a picture by "drawing" them with your hands. Imagine when you read a book, you could flip a page by sliding your figures on its corner, you could highlight/circle the interesting part by move your finger across them and you could write down your comments and even draw a sketch. Now this comes to what Apple is good at. Trust me, it will change everything.

Ok, talking the keyboard, a really big topic. Not sure if Apple Tablet will have a real keyboard, probably not. If there will be only an on-screen keyboard, I think Apple will make it resizable, so it can fit hands in different sizes. You can also move it to any place on the screen. Once you settle down at home, you can use a wireless keyboard or mouse if you want to. I think this would be enough, except for people who needs to type a lot a lot, like programmers or writers.

Talking about the screen. It will be multi-touch, no doubt. I hope it will be pressure-sensitive as well. In terms of size, 10 inches is the most accepted speculation. I don't care the size that much, since it won't fit into my pocket anyway. Kindle is too small to me. 10 inches is a nice size for reading, at least to me. One big question is how it will make reading books easier. People will definitely expect to use it for reading. I have tons of PDF books and I hate to read them on my laptop. Pixel Qi's multi-purpose screen seems to be a really good idea.

As for network, will Apple Tablet have only WiFi or support 3G, iPhone-like 3G or Kindle-like 3G? If it supports wireless data plan, it must be optional, and probably more expensive than the iPhone plan. I highly doubt it though. AT&T is already struggling to support iPhone users. With Apple Tablet, it's like Hulu@iPhone, I don't think any providers will want to run that risk. How about peripherals? What if you really need a real keyboard and mouse, or a big screen monitor, or a printer? It's easy, you can plug the tablet into a station and most stuff won't even need a cable.

Finally, the price. Price, to be more specific, low price, is very important if Apple wants massive success of the new device. This goes back to the two keys I mentioned in the beginning, market and price. I want to use the "vitamin v.s. pain killer" metaphor, which my advisor often uses to judge research papers. If the product is a "pain killer", high price may be acceptable. But if it is just "vitamin", well, I won't buy it if it is too expensive. Although I believe Apple Tablet will be capable let most people just have one device, the reality is that many people already have laptops and/or desktops. To convince them to switch, the price should make them happy.

Enough is enough. I vividly remember the Macworld 2007 Keynote by Steve Jobs where he introduced iPhone, which absolutely redefined the smartphone industry. Apple Tablet will redefine the game again: personal computing should be like this. I can't wait to see it, can you?

Updates:

Jan. 18th: Apple issues invitation to a media event on the 27th.

Because of the colorful splatter paint in the post, people start thinking the new device will focus on art creating. Did I expect too much?

Google Leaves, Baidu Laughs, Users Suffer

2010-01-12T22:26:00.000-08:00

Triggered by cyber attacks from China, Google started reviewing the feasibility of doing business in China. Google decides not to continue censoring search results any more. If Chinese government can not accept this, Google will stop running Google.cn and may close the Chinese office as well.

I am shocked that such a brilliant company is finally kicked out. Giving up Chinese market must be a very tough decision for Google. All difficulties aside, China is a huge market. Google made such a decision, I think Google is finally fed up. I'm sorry for Google. Last year when CCTV (a television network speaking for the government) criticized Google.cn for suggesting pornographic search queries. I thought that is just to send out a warning message to all websites. By the way, that was one of the biggest jokes in 2009. Google's suggestion is nothing more than top content in other Chinese websites. If CCTV thinks the suggested queries are pornographic, please just go ahead find those websites and quit making fake interviews to judge Google.

Kaifu Li left Google China last September. His timing couldn't be better. Imagine how people would think if he is still in Google China today. Did Kaifu already foresee what will happen? Anyway, people may not blame him, since he did a great job before he left. He improved Google's market share in China from 16.1% to 31%. But it seems to be an impossible mission to make Google the market leader in China. But will he fight with Google executives to keep Google.cn if he is still with Google now? After Kaifu left, people started leaving too. If Google.cn is gone, even if Google wants to keep the Google China office, more people will leave I think.

Let's think about what will happen in China if Google really leaves? First of all, it is a big shrink-back signal to companies that want to enter China. Well, this probably gives some people in China the time to copy good ideas from oversea companies, or maybe even icons and source code? Baidu.com can finally celebrate on eliminating the biggest competitor to split the big Internet advertising cake in China. Remember, no competitors, no improvement. How about Internet users? They will have to use Baidu.com, a search engine that censors information, is not capable to correct tiny English misspellings with errors in edit-distance of 1, while still suggests "pornographic" search queries:

(Search queries suggested by "Baidu.com" for the query "mm" ("beautiful girl" in Chinese), including "naked pictures of sexy girls in bed", "teenage girls sleeping naked" and such. The screenshot was taken when I published this post inspired by this post.)

CCTV, will you criticize Baidu and push it to the end-road as well, or just leave it alone because it is a local company, or politically friendly? The rule seems to be: as long as you do not criticize the authority, it is fine to provide "pornographic" content.

Anyway, I feel sorry for Internet users in China, "happy" searching without Google.

Turn An Original/3G iPhone To A Video Recorder

2009-12-30T12:20:00.001-08:00

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

2009-12-27T15:42:00.000-08:00

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

2009-12-15T20:43:00.000-08:00

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

2009-12-14T16:42:00.000-08:00

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

2009-12-13T11:48:00.000-08:00

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

2009-12-08T22:33:00.001-08:00

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? :-)

2009-12-04T07:43:00.000-08:00

You Must Do Code Review And Do It Right

2009-11-29T15:09:00.000-08:00

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

2009-11-26T10:59:00.000-08:00

(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

2009-11-12T22:45:00.000-08:00

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?

2009-11-07T15:24:00.000-08:00

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

2009-10-31T21:46:00.000-07:00

(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?

2009-10-25T21:59:00.000-07:00

"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?

2009-10-17T16:12:00.000-07:00

''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

2009-10-14T10:40:00.000-07:00

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

2009-10-08T19:50:00.000-07:00

(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

2009-10-07T17:01:00.000-07:00

(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.

2009-10-02T16:47:00.000-07:00

(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?

2009-09-29T13:17:00.000-07:00

(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

2009-09-27T22:01:00.000-07:00

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.