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