Saturday, December 30, 2006
Reader mail: Urban performance legends
In response to Urban Performance Legends, Revisited, an anonymous reader wrote that I was "too enthusiastic" about the JVM's ability to inline virtual method calls:
Unfortunately, this is a common myth about optimization in Java (and other dynamically compiled languages): that if a method could be overridden by a class that has yet to be loaded, then the compiler cannot optimize away the virtual function call. This is just plain wrong (as is the rest of what this reader says), and today's JVMs can devirtualize and inline through virtual calls using a number of techniques.
One such technique is called monomorphic call transformation, where the compiler observes that for a given method foo(), there is no class loaded right now that overrides it, so calls to foo() can be compiled (speculatively) as direct calls instead of virtual calls. If a class is loaded later that makes foo() polymorphic, the compiler can invalidate the speculatively optimized code. This is covered in detail in Dynamic Compilation and Performance Measurement. There are other techniques as well, such as inline virtual caching.
The myth that final has any effect on method invocation performance for monomorphic methods was well-exploded by Cliff Click's 2003 and 2005 JavaOne presentations.
Java (as well as other managed languages, like C#) is not C. Dynamic compilers are smarter than you think.
Moreover, the example provided is misleading: inlining in java can be generally done for private or final methods. Non-final public and protected methods can't be automatically inlined because they can be overidden by a subclass. The actual type of the object may be unknown at compile time and at load time. The only way to inline them is to analyse the code to find every use of the class and perform type inference. This can be done sometimes with inner classes that have limited scope, but not with public classes that must be compiled indipendentely from each other.
Unfortunately, this is a common myth about optimization in Java (and other dynamically compiled languages): that if a method could be overridden by a class that has yet to be loaded, then the compiler cannot optimize away the virtual function call. This is just plain wrong (as is the rest of what this reader says), and today's JVMs can devirtualize and inline through virtual calls using a number of techniques.
One such technique is called monomorphic call transformation, where the compiler observes that for a given method foo(), there is no class loaded right now that overrides it, so calls to foo() can be compiled (speculatively) as direct calls instead of virtual calls. If a class is loaded later that makes foo() polymorphic, the compiler can invalidate the speculatively optimized code. This is covered in detail in Dynamic Compilation and Performance Measurement. There are other techniques as well, such as inline virtual caching.
The myth that final has any effect on method invocation performance for monomorphic methods was well-exploded by Cliff Click's 2003 and 2005 JavaOne presentations.
Java (as well as other managed languages, like C#) is not C. Dynamic compilers are smarter than you think.
Reader mail: making tasks noncancelable, and polling for interruption
I frequently get e-mail feedback on my articles on IBM developerWorks. Unfortunately, I can rarely reply to them because no one ever leaves their e-mail address. The majority of e-mails I get are erroneous corrections (not that I don't make mistakes -- I make plenty, and those get pointed up too -- its just there are even more people out there who are really really sure they're always right, but aren't), which I'd be happy to respond to if anyone ever left their e-mail... Here's one from Dealing with InterruptedException. Listing 6 shows an example of how to make an operation noncancelable by deferring interruptions until the operation completes.
public Task getNextTask(BlockingQueue queue) {
boolean interrupted = false;
try {
while (true) {
try {
return queue.take();
} catch (InterruptedException e) {
interrupted = true;
// fall through and retry
}
}
} finally {
if (interrupted)
Thread.currentThread().interrupt();
}
}
The anonymous reader asks: shouldn't this be "while (!interrupted)"? Won't the loop never terminate? The idea behind this example was to address the problem of "what if we have an operation that should not be interruptible, but is composed using interruptible steps?" We will have to ignore the interruptions when they occur and retry the interrupted operation -- but the key is we want to remember if there has been an interruption, so we can restore the interrupted status after we complete our noncancelable operation. That way, we don't throw away the information that someone requested cancellation, we just defer the cancellation request until after the noncancelable operation operation completes.
A related issue that is often asked is how often we should check for interruption. Listing 3 shows a typical interruptible operation wrapped in a Runnable. When this happens, in order to not throw away the evidence that an interruption was requested, we have to re-set the interrupted status with Thread.currentThread().interrupt().
public class TaskRunner implements Runnable {
private BlockingQueue queue;
public TaskRunner(BlockingQueue queue) {
this.queue = queue;
}
public void run() {
try {
while (true) {
Task task = queue.take(10, TimeUnit.SECONDS);
task.execute();
}
}
catch (InterruptedException e) {
// Restore the interrupted status
Thread.currentThread().interrupt();
}
}
}
It is often asked: shouldn't the loop header be while (!Thread.currentThread().isInterrupted()), instead of while(true)? This one is a little more subtle. We can look at this from several perspectives: correctness, responsiveness and performance.
From a correctness perspective, the existing code is correct, because (reasonably coded) interruptible blocking methods check if the interrupted status is set on method entry, and immediately throw InterruptedException() if it is. Similarly, the existing approach is effectively as responsive as the suggested alternative, because the first step in the while loop is to call an interruptible blocking method. (If substantial computation occurred between loop entry and the first interruptible blocking method call, responsiveness might give us a reason to test the interrupted status in the loop header as well -- and maybe other places throughout the loop too.)
What about performance? As with most performance questions of this sort, the answer is "We don't have enough information to tell". Testing the interrupted status in the loop header costs a little more (because the test is repeated in the loop header and in the blocking take() call), but in the case that the interrupted status is set, saves us the cost of instantiating and catching the exception thrown from take() when it finds the interrupted status set on entry. Which is a performance win will depend on how often the operation is actually interrupted -- and we usually don't have this information when coding general-purpose library code.
When in doubt, do the thing that makes the code simplest, cleanest, and most readable.
public Task getNextTask(BlockingQueue queue) {
boolean interrupted = false;
try {
while (true) {
try {
return queue.take();
} catch (InterruptedException e) {
interrupted = true;
// fall through and retry
}
}
} finally {
if (interrupted)
Thread.currentThread().interrupt();
}
}
The anonymous reader asks: shouldn't this be "while (!interrupted)"? Won't the loop never terminate? The idea behind this example was to address the problem of "what if we have an operation that should not be interruptible, but is composed using interruptible steps?" We will have to ignore the interruptions when they occur and retry the interrupted operation -- but the key is we want to remember if there has been an interruption, so we can restore the interrupted status after we complete our noncancelable operation. That way, we don't throw away the information that someone requested cancellation, we just defer the cancellation request until after the noncancelable operation operation completes.
A related issue that is often asked is how often we should check for interruption. Listing 3 shows a typical interruptible operation wrapped in a Runnable. When this happens, in order to not throw away the evidence that an interruption was requested, we have to re-set the interrupted status with Thread.currentThread().interrupt().
public class TaskRunner implements Runnable {
private BlockingQueue queue;
public TaskRunner(BlockingQueue queue) {
this.queue = queue;
}
public void run() {
try {
while (true) {
Task task = queue.take(10, TimeUnit.SECONDS);
task.execute();
}
}
catch (InterruptedException e) {
// Restore the interrupted status
Thread.currentThread().interrupt();
}
}
}
It is often asked: shouldn't the loop header be while (!Thread.currentThread().isInterrupted()), instead of while(true)? This one is a little more subtle. We can look at this from several perspectives: correctness, responsiveness and performance.
From a correctness perspective, the existing code is correct, because (reasonably coded) interruptible blocking methods check if the interrupted status is set on method entry, and immediately throw InterruptedException() if it is. Similarly, the existing approach is effectively as responsive as the suggested alternative, because the first step in the while loop is to call an interruptible blocking method. (If substantial computation occurred between loop entry and the first interruptible blocking method call, responsiveness might give us a reason to test the interrupted status in the loop header as well -- and maybe other places throughout the loop too.)
What about performance? As with most performance questions of this sort, the answer is "We don't have enough information to tell". Testing the interrupted status in the loop header costs a little more (because the test is repeated in the loop header and in the blocking take() call), but in the case that the interrupted status is set, saves us the cost of instantiating and catching the exception thrown from take() when it finds the interrupted status set on entry. Which is a performance win will depend on how often the operation is actually interrupted -- and we usually don't have this information when coding general-purpose library code.
When in doubt, do the thing that makes the code simplest, cleanest, and most readable.
Sunday, September 10, 2006
Farewell Quiotix, hello Sun!
I've been self-employed for fifteen years; I founded Quiotix in 1992 to pursue some short-term consulting opportunities after getting laid off from my last job, and I never looked back. I like the flexibility, and I don't mind the stress of not knowing what my income is going to be in any given month. I like not having to ask permission to take a day off, or buy a new monitor, or attend a conference that looks interesting. So in the past, when offered full-time positions, my response has usually been "Why would I want that?" (This can be very perplexing to someone offering you a job; they're used to getting a very different response.)
So, those of you who know me well may be a little surprised to learn that as of September, I will be joining Sun Microsystems as a Sr. Staff Engineer / Technical Evangelist in the Java SE engineering organization. I'll be involved in a lot of things, including a lot of the same things I've been doing as an independent -- like writing technical papers on JVM internals and speaking at conferences. I'll also be involved with the Java SE engineering, QA, and education efforts. I have a feeling I'm going to be pretty busy.
To the customers, colleagues, business partners, and employees I've worked with at Quiotix, I offer thanks for fifteen good years and the best of luck in the future.
So, those of you who know me well may be a little surprised to learn that as of September, I will be joining Sun Microsystems as a Sr. Staff Engineer / Technical Evangelist in the Java SE engineering organization. I'll be involved in a lot of things, including a lot of the same things I've been doing as an independent -- like writing technical papers on JVM internals and speaking at conferences. I'll also be involved with the Java SE engineering, QA, and education efforts. I have a feeling I'm going to be pretty busy.
To the customers, colleagues, business partners, and employees I've worked with at Quiotix, I offer thanks for fifteen good years and the best of luck in the future.
Wednesday, August 9, 2006
Thursday, June 15, 2006
Memories of iceberg metaphors past
In his Dancing About Architecture blog, Eric Lunt calls JCiP a "two copy" book -- one for home, one for work. I like the way he thinks.
He describes concurrency as an "iceberg" subject:
And he's more right than he realizes! At one point we were going to put an iceberg on the cover, and the introduction was even titled "Under the waterline" (though the metaphor does not appear in the final version of the book at all.) But then we realized that leading with something so depressing might not be the best strategy.
From an earlier draft of the introduction:
He describes concurrency as an "iceberg" subject:
Concurrency in Java is a very difficult, iceberg subject, and I guarantee your intution will fail you more often than not.
And he's more right than he realizes! At one point we were going to put an iceberg on the cover, and the introduction was even titled "Under the waterline" (though the metaphor does not appear in the final version of the book at all.) But then we realized that leading with something so depressing might not be the best strategy.
From an earlier draft of the introduction:
Icebergs typically have only ten to twenty percent of their volume above the waterline ??? the rest is hidden from view, lurking underwater. Concurrency is sort of like an iceberg ??? the explicit elements (synchronization, notification) are above the waterline and are clearly labeled, but in order to avoid an unpleasant collision, you must also be aware of what is below the waterline ??? and there???s a lot down there. Below the waterline lies all of the implicit policies and agreements that govern how these mechanisms are intended be used and mean in specific situations within your program. While it may sound trivial, it is not enough to simply use synchronization to ensure thread safety ??? you have to use synchronization correctly and consistently. Describing how to craft and document sensible under-the-waterline policies for the effective use of Java???s built-in concurrency constructs is the central goal of this book. Fortunately, it is not prohibitively difficult to develop a strategy that encompasses the submerged elements ??? as long as you take them into account from the beginning.
All concurrency constructs (such as synchronization, notification, or interruption) involve more than one thread. One of the reasons that writing and maintaining concurrent code in Java is so difficult is that all of the major concurrency constructs involve some degree of implicit agreement between multiple parties as to how the concurrency construct is to be used or interpreted . The concurrency constructs provided by the language are low-level mechanisms, but they are used in applications to enforce application-level concurrency policies or protocols. The tricky part is that policies are defined by the developer and can vary across programs or classes; the same mechanism can be used to enforce a variety of policies. These policies are not captured anywhere in the code (if you???re lucky, it???s captured in documentation, but more often it is not), and therefore it is difficult to automatically (or manually) verify or validate that a program is using the concurrency mechanisms correctly.
Each of the mechanisms for concurrency ??? such as synchronization, notification, and interruption ??? involves cooperation between two or more threads, and each involves an implicit and explicit component. With synchronization, the act of taking and releasing the lock is explicit, but the reason for taking and releasing the lock ??? because the lock guards a particular set of shared state variables ??? is implicit. Similarly, the act of waiting or notifying on a condition variable is explicit, but why you are waiting ??? that you are waiting for a specific condition predicate to become true ??? is implicit.
Thursday, June 8, 2006
Summer backyard fun
Check out http://eepybird.com/dcm1.html, for an amazing demonstration of what happens when Mentos and Diet Coke mix, along with an example of what happens when geeks have too much time on their hands.
I tried this in the backyard with the kids the other day, and it works! I found that the "crown" technique, where you punch a ring of holes around the top of the bottle, works particularly well (got a big cheer from the neighbors.) The "coke hose" technique works well too, where you don't bother with the cap and just dump some broken mentos in, but you have to do it quick...
I thought the video spoke for itself, but apparently it didn't, as I got this e-mail from someone who shall remain nameless (but whose initials are WMR) but who should have known better...
I tried this in the backyard with the kids the other day, and it works! I found that the "crown" technique, where you punch a ring of holes around the top of the bottle, works particularly well (got a big cheer from the neighbors.) The "coke hose" technique works well too, where you don't bother with the cap and just dump some broken mentos in, but you have to do it quick...
I thought the video spoke for itself, but apparently it didn't, as I got this e-mail from someone who shall remain nameless (but whose initials are WMR) but who should have known better...
You failed to mention that this should only be done outdoors...OOPS! BTW, this really does work! Now, if you excuse me, I have a huge mess to clean up in the kitchen... :(
JCiP sells through its first printing
Java Concurrency in Practice sold through its first printing (5000 copies) in less than a month. If you're waiting for your copy, be patient -- more are being printed!
Rumor has it it that Chinese and Japanese translations are underway.
Rumor has it it that Chinese and Japanese translations are underway.
Saturday, May 20, 2006
JCiP best-selling book at JavaOne!
Java Concurrency in Practice was the best selling book at the JavaOne bookstore!
Tuesday, May 16, 2006
JavaOne, day 1
JavaOne seemed better attended this year than last; business conditions are picking up. Once again, they rewrote the Schedule Builder application, and once again, it sucked. How hard is it to write a data-driven web application? Shouldn't that be a slam-dunk for Sun?
In an attempt to manage class sizes better, signup for each talk was mandatory. This means they had to scan your RFID badge for every talk, which created a huge bottleneck as there were typically only four scanning stations and they wanted to move a thousand people into the room in a five to ten minute window. No one seemed happy about this.
In an attempt to manage class sizes better, signup for each talk was mandatory. This means they had to scan your RFID badge for every talk, which created a huge bottleneck as there were typically only four scanning stations and they wanted to move a thousand people into the room in a five to ten minute window. No one seemed happy about this.
Tuesday, May 9, 2006
India wrap-up
Overall, I didn't get a chance to see as much as I would have liked; the already compressed schedule got further compressed by arriving a day late, and the very hot weather (42-45).
I was _very_ impressed with the caliber of students in my class. They were bright, well educated, and motivated -- this made for a great class experience, and we had a lot of fun. The food was good, and all the people I met (well, except for the shopkeepers and hawkers) were very nice. Indians seem very protective of Westerners; they expressed
constant concern that the weather or the food might be hotter than I could take.
I was truly impressed with the industriousness and resilience of the Indian people. No matter how poor, it seemed everyone was working hard to raise their situation. Everyone is a businessman; we could learn a thing or two about capitalism from them. And my god, there are a lot of people there. Everywhere you went, even outside the city, it seemed to have the population density of Grand Central Station.
The roads are mind boggling. A mix of cars, scooters, bikes, bicycle taxis, mini taxis, and cows, all going different speeds and sometimes different directions. Clearly they play this game by different rules.
I took a day trip to Agra and saw the Taj and the Agra Fort, and got one afternoon in Delhi to do some additional sightseeing and shopping. Unfortunately, I managed to get a spot of Delhi Belly on the last day, which lessened my motivation to leave the hotel for further sightseeing. And man, was it hot. 42-45C (110-115F) in the shade. Power outages were frequent; every day the paper reported the net power shortfall.
I was _very_ impressed with the caliber of students in my class. They were bright, well educated, and motivated -- this made for a great class experience, and we had a lot of fun. The food was good, and all the people I met (well, except for the shopkeepers and hawkers) were very nice. Indians seem very protective of Westerners; they expressed
constant concern that the weather or the food might be hotter than I could take.
I was truly impressed with the industriousness and resilience of the Indian people. No matter how poor, it seemed everyone was working hard to raise their situation. Everyone is a businessman; we could learn a thing or two about capitalism from them. And my god, there are a lot of people there. Everywhere you went, even outside the city, it seemed to have the population density of Grand Central Station.
The roads are mind boggling. A mix of cars, scooters, bikes, bicycle taxis, mini taxis, and cows, all going different speeds and sometimes different directions. Clearly they play this game by different rules.
I took a day trip to Agra and saw the Taj and the Agra Fort, and got one afternoon in Delhi to do some additional sightseeing and shopping. Unfortunately, I managed to get a spot of Delhi Belly on the last day, which lessened my motivation to leave the hotel for further sightseeing. And man, was it hot. 42-45C (110-115F) in the shade. Power outages were frequent; every day the paper reported the net power shortfall.
Tuesday, May 2, 2006
Dysentery roulette
The health advisories I read before leaving all warn strongly of avoiding the local water supply. Of course, this is nearly impossible -- dishes are washed in water, food prep staff washes their hands before touching the food (you hope), etc. So while its easy to say "don't drink the water", in reality it is pretty hard not to. So every time I eat something, I am playing a game of "dysentery roulette" -- it might be yummy, it might make me sick. Kind of makes everything just a little more exciting.
Something surprising
Today, I saw a man riding an elephant on a city street! I'm not in Kansas any more...
Sunday, April 30, 2006
Arrived, eventually
Well, the best laid plans...
I was supposed to get onto the nonstop from NY to Delhi, but the feeder flight from Burlington was delayed 2.5 hours and it was clear that I was not going to make my connection. So they rebooked me for the next day, but at that point the nonstop was full, and I had to be booked onto a connecting flight with a 4hr layover in NY and a 4h layover in Amsterdam at 7AM (and which got into Delhi several hours later.) So, instead of the 17h trip I planned, I effectively had a 44 hour trip.
Once on the ground, things went smoothly. There were about 300 drivers waiting with name placards outside of baggage claim, but I eventually found mine and got to the hotel around 1:00AM local time. The hotel facilities and the service are very nice.
Traffic here is mind boggling. The roads are a free-for-all with cars, trucks, motorcycles, bicycles, pedestrians, and cows, often going vastly different speeds and sometimes different directions.
I was supposed to get onto the nonstop from NY to Delhi, but the feeder flight from Burlington was delayed 2.5 hours and it was clear that I was not going to make my connection. So they rebooked me for the next day, but at that point the nonstop was full, and I had to be booked onto a connecting flight with a 4hr layover in NY and a 4h layover in Amsterdam at 7AM (and which got into Delhi several hours later.) So, instead of the 17h trip I planned, I effectively had a 44 hour trip.
Once on the ground, things went smoothly. There were about 300 drivers waiting with name placards outside of baggage claim, but I eventually found mine and got to the hotel around 1:00AM local time. The hotel facilities and the service are very nice.
Traffic here is mind boggling. The roads are a free-for-all with cars, trucks, motorcycles, bicycles, pedestrians, and cows, often going vastly different speeds and sometimes different directions.
Wednesday, April 26, 2006
Heading to India
I'm heading to India on Friday, to teach my Java for C++ Programmers class. One of my training customers has offices all over the world, and the India office is next on the rotation. I feel like I've won the outsourcing lottery -- outsourcing is now putting money in my pocket.
Fortunately, my customer is springing for a business class ticket (which is effectively a first class ticket, as the only airline that runs a nonstop from the US to Delhi, Continental, merged their business class and first cabins into "BusinessFirst", and on the international flights BusinessFirst compares to first on other airlines.) The nonstop NY-DEL is approximately 14 hours, which shaves 5h off the "change planes in Europe" options.
A business class ticket to India costs approximately 6K; a coach ticket costs 1-1.5K. If I had the choice of buying the coach ticket and pocketing the difference, would I? Not sure. On the one hand, I wouldn't pay 4.5K out of my own pocket to upgrade, but on the other hand I might just not go if it meant flying coach. It's a long trip.
Getting a visa turned out to be somewhat of a hassle. Apparently, standard procedure for getting a visa involves sending your ORIGINAL passport to the foreign consulate, and hoping that they send it back in time (and don't lose it.) I used an expediter service to process it, which reduced the hassle factor, and they also rented me a local cell phone to take with me, which was pretty convenient.
After the training is over, I should have about three days to sightsee. That gives me a day each in Agra, Jaipur, and Delhi. I don't know what to expect, but it should be interesting.
Fortunately, my customer is springing for a business class ticket (which is effectively a first class ticket, as the only airline that runs a nonstop from the US to Delhi, Continental, merged their business class and first cabins into "BusinessFirst", and on the international flights BusinessFirst compares to first on other airlines.) The nonstop NY-DEL is approximately 14 hours, which shaves 5h off the "change planes in Europe" options.
A business class ticket to India costs approximately 6K; a coach ticket costs 1-1.5K. If I had the choice of buying the coach ticket and pocketing the difference, would I? Not sure. On the one hand, I wouldn't pay 4.5K out of my own pocket to upgrade, but on the other hand I might just not go if it meant flying coach. It's a long trip.
Getting a visa turned out to be somewhat of a hassle. Apparently, standard procedure for getting a visa involves sending your ORIGINAL passport to the foreign consulate, and hoping that they send it back in time (and don't lose it.) I used an expediter service to process it, which reduced the hassle factor, and they also rented me a local cell phone to take with me, which was pretty convenient.
After the training is over, I should have about three days to sightsee. That gives me a day each in Agra, Jaipur, and Delhi. I don't know what to expect, but it should be interesting.
Tuesday, April 18, 2006
An even better quote
From the preface of Pragmatic Ajax (Gehtland, Almaer, and Galbraith), on book writing:
"Writing a book is a lot like (we imagine) flying a spaceship too close to a black hole. One second you're thinking "Hey, there's something interesting over there" and a picosecond later, everything you know and love has been sucked inside and crushed."
Indeed.
"Writing a book is a lot like (we imagine) flying a spaceship too close to a black hole. One second you're thinking "Hey, there's something interesting over there" and a picosecond later, everything you know and love has been sucked inside and crushed."
Indeed.
Monday, April 17, 2006
The beast is slain
I turned in final PDF today for Java Concurrency in Practice. Books should be ready by JavaOne. Woohoo!
The final tally: 425 pages, and sixteen months.
Not quite sure what to do with myself now.
The final tally: 425 pages, and sixteen months.
Not quite sure what to do with myself now.
Friday, March 3, 2006
Churchill on writing
Ted Neward pointed me to this quote the other day, which I'd not seen before, but which characterizes the writing process quite well:
I'm gaining the upper hand over the monster. Public humiliation of it, or me, is imminent.
Writing a book is an adventure. To begin with, it is a toy and an amusement; then it becomes a mistress, and then it becomes a master, and then a tyrant. The last phase is that just as you are about to be reconciled to your servitude, you kill the monster, and fling him out to the public.
Winston Churchill
I'm gaining the upper hand over the monster. Public humiliation of it, or me, is imminent.
Subscribe to:
Posts (Atom)
