I gave the talk at the JVM Language Summit, which itself was a lot of fun.
The talk is a repeat of one of the talks I did at JavaOne. I also gave two other talks, but the Sun JavaOne website appears to be unable to deliver the video right now. I also gave a short interview at JavaOne.
One of the talks I mentioned on the InfoQ video is also available here as a Google Tech Talk; Java on 1000 cores: Tales of Hardware/Software Co-Design. I also mentioned a talk Azul's Experiences with Hardware Transactional Memory, and my blog on that is here. Alas, I don't believe the HTM talk has been video'd for public consumption at any time. If you are interested in HTM support, you should also check out this short gem. The GC talk alluded too has slides all over the web; here's the original paper, but I could not find a public video presentation.
Cliff
And so on. If all the various fast-path attempts fail we eventually end up calling into the VM and blocking on the OS-provided mutex. Along the way we'll attempt a bunch of other tests (e.g. recursion & spin-waiting) and if all things fail we need to block, we'll also do a fast/short crawl of the call stack for profiling. There are a lot of other interesting issues here, including heuristics on when to make a lock not-biased by default (producer/consumer design patterns make objects which *always* change hands at least once), or when to deflate an inflated lock that has "settled" into a new thread (or unlocked state), or how to achieve a modicum of fairness under extreme contention. Since this blog is already getting long (and as raw Assembly code ta-boot!) I'll stick with a short discussion of the bias-lock revoke mechanism.
Suppose thread T1 holds the lock on Object O - via the very fast-path mechanism: O's header word contains the bits "xxT1xx00", and that thread T2 needs to acquire the lock on O. What kind of interactions are possible? For starters, assume T2 has failed the fast-path attempts (it's got the wrong thread ID!) and already entered the slower-paths in the VM. A simple inspection shows T2 that O is biased-locked to T1. What does T1 know about this situation? Turns out that thread T1 knows almost nothing:
- T1 may have acquired O's lock in the misty past and may not now have access to a pointer to O.
- T1 may be rapidly acquiring and releasing the lock on O, all without fencing or atomic operations. Moment by moment, cycle by cycle, the actual Java state for T1 may have it holding & releasing O's lock. T1 isn't really tracking this, he is just periodically observing that he holds the bias lock on O.
- T1 may be blocked in long latency I/O operations or on other locks.
- T1 may be a dead exited thread.
- The id for thread T1 may have been recycled to a new thread, T1', which has never seen a pointer to O cross it's JVM state, ever. Yet the lock for O is now biased to T1'!
What T2 can do is to ask T1 to reach a safepoint - a point in the code which matches some Java bytecode, and then decide if T1 really holds the lock on O or not. T2 does this by setting a self-service task on T1; T1 periodically polls for such tasks at safepoints, and when it sees the request it breaks out of it's normal execution and handles the task (periodic polling typically 1 or 2 cycles every few thousand instructions). T2 then waits for T1 to "do something" with the lock (but not really: what if thread T1 has already exited?).
Suppose T1 is still running and spots the poll request. It then does a self-stack-crawl to count the number of times it's supposed to hold the lock. JIT'd code includes annotations to describe what locks are held (and how often, if recursive), and the interpreter counts lock acquires in any case (with slow simple Base-1 counting but we don't care about speed in the interpreter). If this lock count is positive (T1 really holds the lock now!) T1 inflates the lock, slaps in the recursion count into the new ObjectMonitor struct, goes back to running... but now each unlock by T1 will lower the recursion count. When the lock is unlocked for the last time, T1 does the usual wakeup on T2 and T2 then competes to grab the now-free lock. If this lock count is zero (T1 holds the lock biased but not for-real) then it releases the lock and notifies T2 as normal. In any case, the bias on O is revoked and the lock reverts to a state where T2 is allowed to compete for ownership.
This is all great if T1 is actively running and polling for self-service tasks, but what if T1 is blocked or exited? After T2 prods T1 with the poll request, T2 then attempts to do the very same self-service task on T1's stack remotely. To do this T2 has to acquire the "lock" on T1's stack. All Azul threads unlock their stack whenever they block (or otherwise stop polling) - this same stack-lock mechanism is used by GC threads. If T2 can get T1's stack-lock, then T2 can safely crawl T1's stack (and T1 is not allowed to execute random Java code until he gets his own stack-lock back). If T2 canNOT get T1's stack-lock, it must be because T1 is busy executing Java code - and hence T1 is also polling for self-service tasks and will (shortly) get around to crawling his own stack. In any case either T1 or T2 will shortly get around to crawling T1's stack and discovering the proper lock recursion count for Object O.
And if T1 is exited, T2 can also detect this from T1's old thread-id (thread-id's map back to some type-stable per-thread data). In this case, T2 can just freely revoke the bias on O and bias O to himself.
Well, that's enough for now! Hope you enjoyed this (very long overly complex) discussion of our biased-locking implementation.
Cliff
[Sept 9: Still more good comments; I'll likely be folding replies into the main blog report all day]
[Sept 8: Editor: Given the number of high-quality comments, I've decided to edit the comments & replies into the main blog body. Let me know if you want your name attached to your comment.]
I just foolishly got caught in a You-Tube discussion on Java vs C
performance. Foolish because You-Tube comments are a lousy way to
present anything and because it's hard to keep the level of discourse
scholarly. And foolish especially for me because I've had this
discussion so many times and it always comes out the same way... so
here's my attempt at distilling my arguments into something I can point
people the *next* time I get caught in this silly discussion.
Is Java faster than C/C++? The short answer is: it depends.
Places where C/C++ beats Java for obvious reasons:
[MB: Any tool has its own advantages and disadvantages. You simply cannot say Java is superior to C/C++ because Java is written with C/C++ ;-).]
Actually there are several Java-in-Java's Out There and some are not too far off HotSpot's mark.
[FG: I think you're missing two important issues with Java. One is memory consumption. Java programs use at least twice as much memory as C++ programs because pointers (called references in Java) are used for everything and all strings are UTF-16.]
[AM: Java requires 2.5 times the memory a C++ program requires.]
Yes and no... Yes in general Java uses more memory than C++ but it's usually more due to coding styles and data structure choices than pointers-vs-primitives and fat strings. Whenever I see the 2x data bloat it's always due to *really bad* data structure choices. With reasonable choices the bloat is far far lower... and memory is cheap. I'd really like to see some hard evidence here: really equivalent implementations of larger apps in both C & Java.
[FG: It gets even worse on 64 bit CPUs. For some applications like in memory databases, in memory data analysis, etc, this leads to an orders of magnitude performance difference because the disk has to be touched more frequently.]
I assume you mean 64-bit JVMs and not just 64-bit CPUs...
I guess I'd argue that you just mentioned a strong point of Java: with 64 bit JVMs you can have heaps of 100's of Gigs of ram (and ram is cheap!) and cache all those DB accesses and touch disk less often. Azul Systems routinely sells gear to do exactly that. To be fair, the GCs on X86 JVMs do not handle such large heaps well. Some Day they will, and then you'll be delighted to have a 64-bit JVM, pay $49.99 for a few hundred Gigs of ram and skip the disk.
[FG: The second issue is cache locality. Obviously using only pointersinstead of values in all collections (other than arrays of primitives) leads to a lot more cache misses.]
64-bit VMs with 64-bit pointers get pointer-size bloat, and that appeared to cost Sparc about 15% in performance. X86-64 picks up double the number of GPRs which offsets the cache footprint lossage somewhat.
[IJ: Hey Cliff, Regarding the comments about memory usage on 64-bit JVMs, compressed references can help for heaps smaller than 32GB on HotSpot.]
[FG: So I would say C++ is a better choice for any application that benefits from keeping a lot of data in memory. By the way, C# is vastly better than Java for such applications due to its value types.]
Yes and no again... For many applications you'll pay only 1 more cache-miss per entire array. For arrays-of-small-structs (e.g. arrays of Complex), you are correct: Java's lousy there (and I added that to C's strengths). When doing performance sensitive arrays-of-small-structs I turn the implementation 90-degrees and implement a small-struct-of-arrays. It's clearly a work-around over a clunky language issue... but the performance is solidly there (both in memory footprint and in access speed).
Places where Java beats C/C++ for obvious reasons:
Places where C/C++ proponents claim C beats Java, but it doesn't appear (to me) to do so:
[AD: Given that most games use 'Optimizations beyond "gcc -O2"', and tend to have an interpreter or scripting language, and often require 'Direct machine access', plus plenty of tricky computationally intensive maths, that would put them squarely into the world of C++. Especially any game designed for a console, or handheld device.]
For PCs: I'm still thinking Java is up to the task. I've yet to see games that needed BLAS-style routines; simple 'saxpy' style loops should come really close to C performance (not heavily tested! But I've routinely talked people into testing Java FP performance and routinely had them come back with a positive report). If 'direct machine access' is limited to a handful of graphics-card calls per frame (so hundreds to thousands per second), then JNI can handle that no-problem. The games I worked on long ago didn't use any scripting; back then we would have used Java instead of scripting, so I don't have a feel for how crucial scripting is to game development.
For consoles & handhelds perhaps; I did games on console like devices a long time ago (20+ years) and my vague recollection is that if a modern JVM could be squeezed into such a device it would be able to do the job. I weakened my assertion to just PC games.
[TNT: A surprisingly large part of a game is performance sensitive and requires C code. Many games are CPU bound (not GPU bound as you suggest).
Ahhh, but exactly what I am showing here is you cannot equate 'performance sensitive' and 'requires C code'. Java is up to speed for most (if not all!) of the performance sensitive parts.
[AJ: AAA games now typically use middleware or custom physics engines that have highly-tune collision detection code (also used by game "AI") and custom nonlinear solvers. Both are often SIMDed, prefetched and cache blocked, with the CD sometimes doing bit-fiddly decompression, and the solvers sometimes using custom code gen (for derivatives and such).]
JVM: SIMDed: 1/2 yes, prefetched: yes, cache blocked: no. Perhaps closer than you think but probably not close enough.
[AJ: Some PC games push 5-10K draw calls per frame, with very roughly 4 additional state-setting calls per draw. So @60fps, that's something like 1.5-3M/sec. Games are often single-thread limited on this alone.]
The obvious fix is to batch the graphics calls per JNI call, but this starts to look like a hybrid C/Java solution and those rarely look pretty.
[AJ: PC games are also chew plenty of CPU with real-time decompression (unzip or custom) and sometimes recompression (say JPG->DXTC).]
Azul Systems can't use the X86 ZIP routines so we went with the Java ones: performance was about as good as 'gcc -O2' and it was easy to parallelize. After parallelization the Java version was as fast as we cared to add CPUs.
[JJJK: As for Java and games, it actually works better than most people think. No problem for indie games. But there are some issues:
GC pauses ruin everything. Smooth framerates are difficult to achieve with the usual Fully-OO-Java-Programming-Style. Also the resources on the GPU are not garbage collected, so you'll have some kind of paradigm-clash anyway.
If you want do do some transformations on vertex arrays on the CPU, you'll have to do them on direct byte buffers, since they are the only arrays that can be sent to the GPU. Or do them on java arrays and copy them into byte buffers, I have no idea what that does to performance though.
3D-Vector math in java is plain ugly. You can either make it readable or fast. And if you don't pay attention, it will be neither.
On the other hand, with more data and computation going to the GPU (and staying there for the most part), Java is at least becoming moderately attractive for games. I worked in a company which is now starting to release web-based 3D java games.]
"Flaws" in most Java-vs-C performance methodologies:
These are ways in which many many people (wrongly) claim Java/C/Ruby/etc is faster than C/Java/Python/etc. Sometimes these issues aren't flaws at all, but instead point out conflicting basic requirements that truly make one language superior to another for a particular task.
[SG: One thing I might suggest is dropping your local memory caches before performing. Java gets a obvious speed boost beacsuse the JVM code tends to be cached, and the C code also has the same.
sync && echo 3 > /proc/sys/vm/drop_caches
Then run each program twice. First one giving you the time it takes to access and load the JVM and other libraries included, and the second giving you what it takes once the libraries and everything is cached.]
No. Run at least *30* times to get a decent statistical regression. See the above papers on the 'run it twice' methodology is *seriously* flawed. However dropping the local memory caches probably helps. Here's a nice writeup on Java perf testing issues: http://www.ibm.com/developerworks/java/library/j-benchmark1.html.
Some Commonly Mentioned Non-Issues:
[AM: C++ stack allocation beats Java GC for allocation of small objects.]
Does not. You have evidence? I have evidence that small object allocation in Java is darned near free... but not totally free. So C++ might win here but not by any interesting amount. And HotSpot does stack allocation when it can. You should do some testing here to convince yourself.
[AM: Java apps have lots of dynamic casts in them.]
Yes,
and it's free. Really 90% of all casts are removed by the JIT and the
other 10% take a 'load/compare/branch' sequence which is entirely
predicted by X86 hardware and runs in 1 clock cycle.
[EXO: This is pretty off topic, but I'd like to know how you've reasoned that
a load/compare/branch sequence can be done in 1-cycle on x86. Of course
this varies by implementation, and I'm sure that there are x86's that
can handle the compare and branch in parallel despite having a
dependency chain on the flags, probably due to careful misalignment of
the relevant pipeline stages. But there's no way you can cmp on a
loaded value the same cycle it's loaded in. The L1 dcache's 2 or (more
likely) 3 cycle latency is going to get in your way.
Sure, the pipeline can be busy doing other independent things in the
meantime, but that's always the case and I don't think it's what you
were getting at.]
You're close: indeed the cmp happens many cycles after the load. Meanwhile the branch predicts - and correctly >>99.99% of the time- and X86 O-O-O dispatch carries on past the branch. As long as the load isn't a full miss to memory the whole ld/cmp/jne sequence will retire long before it causes the X86 pipeline to stall, and consume perhaps 1 clock of decode/exec/retire work.
[AM: Interface dispatch is slower than double dispatch through a vtable.]
Yes and nearly never taken. I've yet to see interface calls show up on any profile of any interface-heavy crazy Java programs. Inline-caches replace 99+% of all interface calls.
[TNT: Where does C# stand compared to the mentioned languages?]
Not that I track C# all that closely but... I believe the JIT produces substantially slower code than Java; Microsoft leans pretty heavily on static compilers (and have a better statically-compiled-code integration story than Java does). Also, Java's Memory Model is well tested & well used; C# equivalent appears to be not so robust in part because of the requirement to run all that old code. A real C# expert should chime in here, I'm not able to give C# a fair treatment.
[IK: C# would land in the same bucket as Java. It might be slightly slower because more money and man-years were put in JVM, or it might be slightly faster because of unsafe and structs and stuff.
"Slightly" means "a few benchmarks would be ruined". Like, I've
heard, CLR did NOT do interface-vs-implementation profiling, thus some
code gained 10x boost by replacing all occurences of "IList" with
"List" (it couldn't figure out how to dispatch calls to concrete List
class really fast when the slot type was IList).]
[PL: C# performance would fall into the roughly the same range as Java. I
have a RETE engine written in Java and C# and the java version is
faster. One area where CLR takes a performance hit is
autoboxing/unboxing. Atleast that's from my experience with my rule
engine. Aside from that, I would say the performance difference isn't
significant.]
Last round of anecdotal evidence I gathered (now 2 yrs old) showed Java JITs well ahead of C# JITs. Would love to see some hard numbers here.
[CC: I still don't understand why they do not cache the validated and optimized memory image for next time the application is launched. .NET can do this.]
It's a really hard problem for multi-threaded programs - which typically do parallel class loading - and lazy compilation -which typically inlines the classes that are loaded *at the moment*. Re-using previously JIT'd code will require, amongst other things, that your code loading order is the same, and the last code-load order you JIT'd from probably depended on stuff like network packet arrival order. Given that startup time for big User GUI apps is typically NOT the JIT (it's the DISK), I personally have not been very motivated to try and do cached code optimizations.
On purpose, I'm being sloppy in the numbers I report here... because I
don't want to spend my entire life beating this tired horse. But if
somebody reports something widely different from what I'm seeing, I'm
happy to dig in further - if the reporter is also. I don't have access
to every kind of compiler & system on the planet so I can't repro
other peoples' results easily. Also in my experience, the number one
reason for conflicting reports here is because the reporter has
something really simple wrong on their end and a short email session
will clear it up.
[WW: Here's a hint. Next time you write silly code for comparison, make them do something more useful than integer operations and basic maths... those will always be the same (or close) between a compiled language and an interpreted one with JIT.]
Sorry but I have a life outside outside endless blogging... and 100KLOC examples aren't useful in a blog format anyways.
String Hash Example:
Complete C++ code: http://pastebin.com/d280c1cd4
Complete Java code: http://pastebin.com/m541c4655
Here's a bit of code computing string hashes that looks ideal for a
static compiler (ala C/C++), yet Java is tied in performance. I used
fairly recent versions of 'g++ -O2' and 'java -server' on a new X86
(-server is the default for me, so no cmd-line argument needed). The
inner loop is:
int h=0;
for( int i=0; i<len; i++ )
h = 31*h+str[i];
return h;
Here I ran it on a new X86 for 100 million loops:
> a.out 100000000
100000000 hashes in 5.636362 secs
> java str_hash 100000000
100000000 hashes in 5.745 secs
Last year I ran the same code on an older version of both gcc & Java, and Java beat C++ by 15%. Today C++ is winning by 2%... so essentially tied. Back then the JVM did unrolling and "gcc -O2" did not, and this code pays off well when unrolled.
[TD: In the String Hash example, is the unrolling done by the JIT or javac?]
Done by the JIT.
Sieve of Erathosthenes:
Complete C++ code: http://pastebin.com/m3784c090
Complete Java code: http://pastebin.com/m4b414295
Here's a simple Sieve of Eratosthenes, again compiled
with g++ -O2 and run with java -server. Again this looks ideal for a
static C/C++ compiler and again Java is tied in performance:
bool *sieve = new bool[max];
for (int i=0; i<max; i++) sieve[i] = true;
sieve[0] = false;
sieve[1] = false;
int lim = (int)sqrt(max);
for (int n=2; n<lim; n++) {
if (sieve[n]) {
for (int j=2*n; j<max; j+=n)
sieve[j] = false;
}
}
I computed the primes up to 100million:
> a.out 100000000
100000000 primes in 1.568016 secs
> java sieve 100000000
100000000 primes in 1.548 secs
So again essentially tied.
[AJ: How do the sieve timings differ if you use an array of bits rather than of bytes?]
Good question, but I bet they're tied again. The JIT does fine with bit-twiddley stuff. Test it and let me know!
[AL: Note that your sieve is not a true one: http://lambda-the-ultimate.org/node/3127]
Cute! Just swap '2*n' for 'n*n'... but this doesn't change the C-vs-Java argument.
Profiling Enables Big Gains:
Complete C code:
vcall.cpp http://pastebin.com/m70dbe7d6
vcall.hpp http://pastebin.com/m13055a8c
A.cpp http://pastebin.com/m5aa1b232
B.cpp http://pastebin.com/m2e46ec23
Complete Java code:
vcall.java http://pastebin.com/m149bbdf0
A.java http://pastebin.com/m2e33d6df
B.java http://pastebin.com/m2b1d75bb
This bit of code makes a virtual-call in the inner loop of a simple vector-sum... and selects the v-call target based on a command-line argument. The JVM profiles, decides there's only 1 target and inlines ... and unrolls the loop and discovers a bunch of simple math that collapses in the optimizer. The C/C++ compiler can't do it because there really are 2 possible targets at static compile time. Delaying the compilation until after profiling can enable major optimizations downstream. I compiled the C++ version with 'g++ *cpp' and the java version as 'javac *java'.
int sum=0;
for (int i = 0; i < max; i++)
sum += val(); // virtual call
return sum;
Here I run it on the same X86:
> a.out 1000000000 0
1000000000 adds in 2.657645 secs
> java vcall 1000000000 0
1000000000 adds in 0.0 secs
The Java code is "infinitely" quick: after JIT'ing the -server compiler essentially deduces a closed-form solution for the answer and can report the correct result with a few bits of math... no looping. This example is ridiculous of course, but it points out the obvious place where dynamic compilation beats static compilation. This "make a virtual call into a static call" optimization is a major common frequent optimization JIT's can do that static compilers cannot.
[QB: If your compiler can reason that the virtual function is pure, then the entire loop can be folded into single vcall and multiply. ]
[ALJ: It's worth noting that you can achieve the same effect - with the compiler turning multiple additions into a single multiply - by using C++ templates.]
My example is perhaps too trivial; I can get the same performance benefits with a non-pure function (so no chance of using 'pure' in static setting). In practice, you get dozens to hundreds of Interfaces turned into concrete Classes, and hundreds to thousands of calls to such optimized... using a code-cloning technique like C++ templates is going to blow you out with exponential code.
[QB: Although initially expensive and not quite thread safe self modifying code will do the trick here. Alternatively, you could use existing dynamic recompilation techniques to make it thread safe, which I understand is probably veering off into dynamic compilation land...]
Exactly inline-caches are thread-safe self-modifying code... but they still look like a call (inline caches make vtable calls as cheap as plain calls). In this case the big gain comes from removing the call altogether, which means knowing there's only 1 implementation of the virtual.
I hope this clears up where I stand on this issue... and I'm (sorta) looking forward to the flamefest which is surely coming...
Cliff
(warning: no technical content)
Prior Friday: my Mom calls my sister & tells her my brother Eric (hiking the entire PCT this summer) is 2 days late/overdue. Sister calls me in a PANIC!!! I plan on Saturday driving 5 hrs to northern California to calm my Mom & help coordinate search & rescue. It's not like I can get on the trail and expect to cover 100miles in 4 days like my brother's been doing. I can't reach Mom (no doubt she's driving twisty mountain roads and is out of cell phone range). To make matters worse my wife has been sick all the prior week while trying to run Vacation Bible School (her and 8 kids got it from somebody who brung it; why do people bring their sick kids to School?); she's still recovering.
Saturday: no panic. Mom calls; Eric's been found and is not really late: he had told her he probably would not be able to call midway through the 100 mile stretch and indeed had no cell coverage the entire time. Mom had the local Sheriff out canvassing everything and almost ready to put up a Search&Rescue plane when she finds Eric (and the Sheriff really didn't want to do that because there was already almost 100 planes in the air fighting the local wildfires). Mom's too old to panic like that. Grrrrr.....
More Saturday: I take the kids to the beach while my wife sleeps off the cold; my eldest daughter needs to photo tidepools for her Bio project and we all need to relax. In the middle of the relaxation my Dad calls home (my folks are divorced so no relationship with my Mom anymore) and reaches my wife napping; Dad and new wife (of nearly 20 years) are in Stockton and will be arriving tomorrow. PANIC!!!! Wife's still recovering; the house is a total shambles AND her inlaws are arriving in less than 24 hrs.
Sunday: Inlaws arrive. Much grandparent fun.
Monday: I leave my folks to have a looong planned meeting with Intel. I arrive and PANIC!!! the power is out. We relocate to the break room which has floor-to-ceiling windows. Makes me feel like Azul is a high-powered got-act-together startup to host Intel folks in the dark. Dad & wife move on (an unannounced drive-by grand-parenting), as they are traveling the western US as part of their retirement.
Tuesday. I spend all day on training & mentoring, and recovering from repeated power failures. All boxes need rebooting and ..."PANIC!!!"... patches get installed, don't play nice together, need more patches, more screwing around. Things more or less functional again by late Tuesday. Of course a company wide demo coming on Thursday is hitting an unexpected new crash, so the demo gods are panic'ing and I can't help them all day because of power outage crapping out my machines.
Wednesday. Unrelated at-home PANIC keeps me busy all morning (plus bugs in high-scale-lib showing up a year late). I finally get the fires out around noon and my wife offers to go out to lunch w/me. First time we'd eaten together w/out kids in a month. Of course, the housekeeper has hid my scheduler book and there's something in it keeps nagging me. Just before we walk out the door I find it and stuff it in my briefcase un-inspected - because a rare lunch opportunity w/my wife is not to be missed. 5 minutes later Jeremy of Google calls: I missed my planned Google lunch w/ high-powered Java hackers and he wants to know if I'm still giving the tech-talk at 1? PANIC!!!! I turn the car around, drop off the wife, panic another 5 minutes trying to get latest slides on wife's tiny new netbook because the standard presentation laptop is sick before the laptop recovers and I grab it and roar out the door. I make it to Google just in time (no officer, I wasn't speeding I was just flying too low). The talk goes well. (slides are here)
Thursday. Demo goes OK. I actually get some work done. It's quite shocking.
Friday: Planning on some kind of panic but it hasn't happened yet. Got a concert planned tonight in Santa Cruz withOUT kids... so an hour drive away from any kind of rescue. We're making plans (got neighbors lined up, etc). In the end wife and I are so exhausted that we bail on the concert and settle for a nice dinner out without kids.
Saturday: We have a 7:30am Dr appointment for my youngest (no: I normally never hear of Dr's giving 7:30am Saturday appointments, but my youngest needs to see a serious specialist who happens also to be a really nice guy), then a long planned trip to SF zoo (In theory: more grist for the daughter's Bio project. In practice: she's got a long-distance romance going on with somebody who's 2 hours north of SF so they agreed to meet in the middle). We all get too much sun wandering the SF zoo in perfect weather. I finally come down with the dreaded VBS cold, and feel like crud the whole day but had a great time nonetheless.
Sunday: We're all recovering from massive sunburns and a week of madness. School starts tomorrow... plenty of time to panic then!!!
Cliff
PS- Concerned that there might be a correlation between PANIC!!!! and my receding hairline
Long delayed, but at last I found time to publish my notes.
I got a free all-expense paid trip to Italy, and all I had to do was give a keynote speech (slides) at 2009 ECOOP. It's a nice gig if you can get it. Travel to Genoa from San Francisco takes awhile; my 8:30am SF flight got me in Genoa about 2pm on the *next* day - plus 2 hrs lead time at SF, plus a 1hr drive to SF - I started my "day" at 6am on Friday and ended it at 8pm on Saturday. I managed to stay up till dinner (barely) then crashed pretty hard. Sunday was my day for sightseeing; I managed to wander pretty far all around Genoa; rode some funiculars; walked all over; took loads of pictures; ate weird food and generally acted like a typical American tourist.
There have been loads of sidewalk vendors; all Blacks aggressively selling fake designer purses and sunglasses laid out on sheets on the sidewalk. Monday afternoon I got to watch a bust go down; lots of yelling, they grabbed their sheet bundles and took off running with plain clothes police in hot pursuit. Somebody lost his wares and the police quit chasing to grab the loot. It's Tuesday evening and the Blacks haven't returned. I promised my wife I'd get her a cheap Gucci purse and now I'm regretting I didn't do it earlier.
Hotel Bristol is a nice older place (means: lots of paint chips and paint layers, big chandeliers, gold leaf trim, dark wood, creaky old elevators; rooms are a mix of really old and really new; follow the link and oogle at the pictures). My room is vast with 15ft ceilings (with chandelier of course) and a large jacuzzi tub; enough room to put up a basketball hoop. The conference food has been pretty nice (free good wine with every meal); lunches are served in the Palace Ducalle - historic summer residence of Doges. I can't do the setting enough justice; the website is nice but the pictures don't really tell the story. 50ft ceiling with 20ft chandeliers and a dozen 8ft marble statues; gold leaf trim on every fresco; stunning paintings the size of basketball courts... I totally laid down on the floor and stared at the ceiling for a good hour. The local restaurants, on the other hand, are a hit-or-miss affair; food is only served at certain hours; sometimes the food has been very good and sometimes no better than the local deli around the corner from Azul.
The ICOOOLPS workshop was on Monday; I got invited to talk there at the last minute. I had some misgivings but most of the papers at the workshop were pretty nice; I enjoyed myself. I'm still fighting jet-lag (today is Tuesday) pretty hard, so I'm writing this to try and stay awake until dinner. The papers are here.
1st up - The ICOOOLPS workshop. ECOOP notes are further down. As usual I abbreviate ruthlessly; skip some talks; take notes in a stream-of-consciousness style. Caveat Emptor. And before I forget:
The "Nick Mitchell SimpleDateFormat Challenge": parse a sample common SDF and JIT code to translate Date objects to ASCII efficiently. Similar to C/C++ compiler optimizations for 'printf' strings.
Let me know when you got something working.
Towards an Actor-based Concurrent Machine Model
"delegation based" machine model; dynamic separation of concerns "MDSOC"
Machine model: objects, msgs, delegation. High lvl objects represented as at least 2 low-level objects; a "proxy" and a real object. Indirection to allow message interception. All msg-sends get forwarded thru the proxy ("message" here is a java-lvl function call, not an OpenMPI msg - but could be either in a distributed system).
Aspect-Oriented-Programming - intercept msg-send links (between Class-proxy and methods in the actual Class-body), etc. How to do CHA with basically dynamic sub-class insertion? Just re-JIT in the new class hierarchy?
Ok - now new stuff... want concurrent in the delegation function. Actor is a collection of local objects (and ptrs to remote objects). Fcn calls between local objects are fast; fcn calls across actors are basically remote-msg send. Then receiving a msg invokes a co-routine in the remote actor.
Ugh, using 'yield' with the co-routines. Sounds buggy to me: semantics of dead-lock will depend on proper calling 'yield'.
(assuming a VM w/ actors not thread support)
An Efficient Lock-Aware Transactional Memory Implementation
Justin Gottschlich
Trying to integrate into the "boost" STM system.
Locks+TM break things.
But locks are prevalent - must be able to compose with them.
Example: Locks outside Transaction
- T1 runs lock; T2 runs transaction
Example: swap code. Works with only-locks or only-TMs but breaks if mixed
Locks inside Trans
- T1 runs trans, calls lock; T2 runs either trans or lock
Prior work: "full lock protection" - if you take a lock, then the XTNs are all stopped/aborted/etc and you only get locking behavior.
Offers a programmer solution: programmer lists lock/XTN conflicts and the XTN system deals when you take a conflicting lock. (I believe this is unrealistic).
Eric Jul? - Whiteboard not slides....
Blurring the line between compilers & runtimes
Gives some examples already done by hotspot
Nice discussion, but nothing new. Mostly trying to get a discussion going about crosing compilers/JITs & runtimes. He might not have been aware about what the JIT already does.
Trace-Based Type Specialization in JavaScript
Andreas Gal
Same basic talk as given at PLDI. TraceMonkey? FireFox 3.5
JavaScript & Flash instead of Java/C/C++
JS has been very slow (interpreted only). But is here to stay; very popular & growing. ActiveX & client-side Java dying out (not sure about client-side Java which was never popular in the 1st place).
Static typing makes life easy, but dynamic typing is required. More complex data types and more runtime tests. Tag bits to be checked; overflow to Double, etc.
Coming around to wanting a HotSpot like dynamic JIT'ing thing based on types that happen to be true at the moment. Basically, types in program traces remain stable over time.
- for( var i=0; i<100; ++i ) { /* nothing */}
loop:
if ( int(i) >= 100 ) break;
i = box(int(i)+1);
goto loop;
So trace can record, e.g. that 'i' has always been an 'int' so far. Trace has a guard on the input types, and are type-specific. Function calls are inlined in the traces, along with guard statements to check that you are taking the same control-flow.
Tracing loops, and can verify trace is type-stable across loop. So can remove e.g. boxing in the loop.
But real traces have many exits and the many exits are really taken. So trace along each exit. Build trace-trees, rooted at loop headers (exponential growth of trace trees as the loop DAG is split out?). Can only link back into original tree if types all match up - else need a new loop /tree header.
Suffering for lack of a language spec; JS programs are driving the language semantics (i.e., w/a new interpreter some JS programs fail so we call the interpreter buggy- even if it meets the loose "spec"). No nothing of a memory model or threading; lots of other holes in the language. Echo's of what Java went through: the popular implementations defined the spec.
Tracing the Meta-Level: PyPy's Tracing JIT Compiler
Carl Bolz
PyPy is a tracing JIT compiler. Now apply this tracing JIT to an interpreter.
Compiler "Restricted Python" RPython - can target C, Java, .Net
Various interpreters: python, prolog, smalltalk, scheme, etc
Basic idea:
trace loops; look for type-stable loop execution; look for similar code path loops.
But the dispatch loop in interpreters means you never execute the same loop code twice (because each time you are running a new different bytecode). Goal: trace user-mode program, not the language interpreter. Effective the tracing interpreter unrolls the bytecode dispatch loop. Provde 3 hints to laguange interpreter. - hint for position key; here is the language interpreter's BCI; here are backwards edges; here is the PC modification
Works fairly well to clean out the language interpreter from the traces.
Then get traces which are fairly clean & can JIT them.
Bears resemblance to partial evaluation, arrived at by different means. Future work: better optimization of traces; some escape analysis to remove boxing operations. Optimize frame objects, apply to larger programs.
Faster than C#: efficient implementation of dynamic languages on .NET
Antonio Cuni
Trying to make e.g. Python faster on .Net.
Looking at IronPython, Jython, JRuby, Groovy
(also Self, JavaScript/TraceMonkey/V8)
Why so slow? Hard to compile efficiently; lack of type info at runtime; VMs not optimized to run them. .Net is a multi-language VM, right (sure, as long as the language is C# - his quote, not mine!). JVM is in better shape, but still heavily optimized for Java.
JIT compiler? Wait until you know what you need; interleave compile-time and runtime; exploit runtime info. JIT layering; fight the VM...
PyPy; JIT compiler generator; Python semantics "for free". JIT frontend not limited to python; JIT backend: x86 or CLI/.NET backends. Fun games with partial eval: assume e.g. Python bytecodes to be constant & constant-prop them into the python interpreter.
Do even more fun with constants than HotSpot+OnStackReplacement - totally doing speculative constant value JIT'ing - if this argument is of value '3' then here is the JIT'd code. Trick is to pick which variable to constant- speculate on (and getting that spec value as well).
Not yet doing all of Python, but getting really great speedups.
Strata Virtual Machine
Software Dynamic Translation - read a binary, & translate it/jit the translated code.
Using a code-based hash-table lookup. Hash; jump to hash-table entry. Miss: jump to 'strata' interpreter
Hit: jump to bucket; bucket checks target (like HS inline cache, check at target)
HotSpot could use this to make more efficient v-calls? Hash; indirect jump to nearby code table; table jumps to target & checks target; expect no misses after warmup. Nah... still got indirect branch in there.
Looks like a standard binary dynamic translation type stuff (converting PPC instructions to Java bytecodes?)
Automatic Vectorization in JIKES RVM
Using SIMD ops on X86. Can't use BURS/BURG to pattern-match vector ops. Unroll loops to make the patterns more obvious.
Basically getting some SIMD stuff to work (but talk given by PC not by author, and PC believes this is not the right way to discover SIMD ops). I also believe this... it's not a clean fit to BURS.
Code emit via simple bitmask/shift/and/or.
JIT Compilation on ARM Processors
Michele Tartara
ARM - 31 32-bit GPRs, 16 available at a time?. SP, LNK, PC are GPRs. Fixed format 32-bit ops. Dynamic fast compilation (cell-phone targets). No BURS or tiling, just greedy rules. This is probably the right way to go always.
ECOOP 2009 Proper Starts
ECOOP is being held in the Piazzo Ducall (Ducal Palace) - the main conference presentation chamber has perhaps 40ft ceilings, acres of gold leaf on the walls in between the massive medieval paintings. The speaker dias was clearly meant to hold a throne or the orchestra; it's a circular marble dias perhaps 20ft in diameter with marble balustrade and marble railings. The high tech screen & projector setup in the middle is really anachronistic.
The adjacent formal ballroom is much larger; 50ft+ ceilings; chandeliers of at least 20ft tall and 30ft in diameter; paintings & gold leaf in plenty plus also perhaps a dozen 8ft marble statues with ancient greek themes.
Keynote - Classes, Jim, but Not as we Know Them
Simon P Jones
As usual for Simon, he gave a wonderful presentation.
History - Haskell is 20yrs old. Lots of fun with new languages & machines & ideas (Functional Programming). After Backus's Turing Award lecture opened the gates, a storm of new languages hit the field. Took 10 yrs before Haskell formed out of the chaos of new languages.
Lifetime of most programming languages:
Haskell might cross over into immortal language (100K+ programmers)? Hackage: user uploaded libs, reaching 300 new libs uploaded /month, and approaching 1million downloads.
Type Classes-
Shows examples of lots of things you want actions on a wide variety of types:
(so far sounds like Java interfaces)
For all 'a' such that 'a' is an instance of class 'Num'
square Num a ==> return a*a
Num classes have the following methods: +,-,*,/, etc.
The implementation of Num classes binds '+' to eq 'plusInt' or 'plusFloat'
Implementation is perhaps more clever than Java invokeinterface bytecode lookup: is passed in a vector of fcns, of the correct type of interface 'Num'. The fcn lookup happens on this particular 'vtable' - call it an itable, but it's really a unique v-table per interface.
For Haskell, this is all done with syntatic sugar over the basic Haskell. Which itself is very cool (e.g. Haskell compiler (javac equivalent) is doing interface calls w/syntatic sugar).
CLIFF NOTES: This is a faster way to do Java interface calls!!! Or maybe this is how they are impl'd? Find the i-table from a list of implemented interfaces, then pull out the correct fcn from the i-index. In his world the i-table is pulled out early and kept pulled out, which avoids the point-by-point lookup of interfaces. Ahhh.... he's statically computing the i-table ahead of time during compilation, using some combo of type unification and the closed-universe assumption. Not applicable to Java.
Able to handle fcns which themselves take arguments of fcns with any signature, as long as the fcn handles the correct interface.
Doing type-based dispatch instead of value-based dispatch. Not the same as Java interfaces...
In Haskell, can bind a value arg to multiple interfaces all at once.
In Haskell, existing classes can be made instances of new interfaces (duck typing)
Haskell has NO subtyping, but uses the interface (well: type class) notion instead.
Haskell: types are inferenced typically, type annotations occasionally needed
Java: types are declared explicitly; inference occasionally possible
Haskell does type unification, so things like Java's 'equal' call - which is normally a fcn of (Object,Object)=>Bool - in Haskell, we KNOW ahead of time that the 2 args are of the exact same type. Hence the implementations of various equals calls do not need to ask the "instanceof" question that all Java equals call implementations all start with.
Making Sense of Large Heaps
(Nick Mitchell, IBM)
Where does the memory go in large java apps.
Example from 2008, Cobol to Java. In Cobol: 600 bytes; in Java 4492 bytes.
Blow up from delegation, bulky collections, or too many data fields.
Size examples: 58M objects, 3Gig ram, 8000+ types.
Yeti Tool - does smart cluster of datatypes (String w/char[], or HashMap w/HashMapEntry[], HashMapEntry, HashMapEntrySet).
Yeti also does dominance of sharing; notices single-owner root/tree bits, and then breaks out the shared parts at the leaves. Also detect e.g., similar kinds of sharing, such as array B[] points to a set of B's; but also a linked list of Entry's points to the elements of B[] in turn. Really lumping together things with the same owner; maximal dominance w/same ownership relationship. Does nice heap shape summaries, followed by size info.
Picture is really alternate sandwich effect, alternating between the Collections you selected, and the user-data at that layer of the 'sandwich'. Edges hold the various sizes of things. They fold up collection 'backbones'.
If we get the data structures right, can easily shrink heaps by 2x to 10x!!! Huge speedups possible. Shows examples of people using CHM to hold 1 element (but programmer doesn't want to think about expected size usage, so does the easy thing and grabs CHM).
Scaling CFL-Reachability-Based Points-To Analysis Using Context Sensitive Must-Not-Alias Analysis
Basically computes a must-not-alias approximation; where it holds do not bother to run a more expensive pts-too analysis.
Some experiments are medium programs (SpecJVM - 7 progs, Dacapo - 4 progs, 8 other progs). Can compute pts-to graph in 2x to 5x smaller. Compute time for the pts-to analysis is 3x faster on average than prior work (but still in the several minutes range)... but what do you do with the info? (this is my standard question when presented with better/faster/new&improved points-to work: now that you have the info how much does it *really* help speed up programs? especially compared to having strong typing in the first place)
Nice presentation of a pts-to analysis, but hit right at my sleepy jet-lag afternoon siesta; had trouble staying awake.
Intel NePalTM - Design and Implementation of Nested Parallelism for Transactional Memory Systems. (Intel)
Issue is using locks instead a XTN; the locks are for the nested parallelism, but want the whole operation to be atomic. Azul makes no attempt to use the HTM to span across threads. Can't work for us, because the threads need to communicate through shared memory - and that shared memory will blow out the HTM.
This is Intel's compiler-gen'd STM system for C++. Handles either optimistic (read-friendly) or pessimistic (write-friendly) concurrency; roll-back & retry.
Sigh - shows basically no speedup over plain locking.
(and perhaps not the best name....)
Debugging Method Names
What's a naming bug? A mismatch between the name and what the code does.
Break names apart (CamelCase in Java), do some grammer abstraction.
getLastName ==> get - last - name ==> (verb) (adj) (noun), etc
Then also do semantic analysis of code. Look for things like: has a loop, has a incoming parm, returns a value (from multiple points), includes some run-time checks in the loop, etc. Decide it's a search loop, returning a result or NULL.
So come up with lots of data points for names & methods.
Then mine the rules from a large corpus of code.
E.g. a "contains-XXX" name method should NOT be a void return, because a "contains-XXX" name implies a question with an answer. In fact, in probably ought to return a bool.
Then with rules, apply rules to a program and report violations.
Turns out pretty easy to suggestion candidate replacement names.
Example:
public void isCaching(bool b) { this.caching=b; }
Method isn't asking a question, it's setting value.
Tool suggestions name should be "setCaching".
Example:
public bool equals( Object o) {
if( this==o ) return true;
if( o instanceof Value )
return equals((Value)o);
return equals(new Value(o.toString()));
}
So not really an 'equals' method, because it makes a new 'Value' object
More examples, ends up finding interesting bugs as well. Hard part is to decide whether or not to change the name or change the code. Sometimes the name is correct, but the code is 'wrong' here - and also wrong elsewhere. Basically finding a poor factoring of code.
Mapping & Recommending API usage Patterns
API, libraries - often complex, lots of classes & methods; complex; hard to use.
People use: books & docs, forums & newgroups; code search engines.
Example: we wish to add an item to Eclipse menu. Browse docs; find potential call: "appendToGroup". Google search finds 151 code snippets (at time of paper submission) and 287 code snippets (at time of talk). The returned code snippets at least 2 different API usages.
'MAPO' Tool does search; parses code; clusters snippets based on used; mines patterns; recommends final patterns. Tool needs to inline non-3rd-party methods (scattered implementation).
Examples hard to follow... I've been bit here before repeatedly (complex API & no way to learn how to use it easily). So very sad that it's so hard to follow his talk.
Supporting Framework Use via Automatically Extract Concept Implementation Templates
Another talk about finding & figuring out reuse of existing code.
Choice between Templates vs Documentation had much less impact on dev time than the task's concept complexity.
I skipped all the refactoring talks. Exhaustion is setting in, plus I've seen one or two of these talks before.
Went to a couple of talks attempting to deal better with constructors. Mostly it's issues like publishing objects before construction completes, or in Java call an overridden v-call from a constructor (which means the sub-class v-call executes before the sub-call constructor can work on the object). Final fields, read-only objects still being constructed; not-null field properties before you set the value; et al; there's a bunch of problems that stem from constructors not being instantly-quick - and if they take time, what does the object look like in that in-between state.
This is a general language issue with constructors. They are a nice notion, but unless they are instantly quick, you have to live with having objects which are not 'complete' or 'constructed' yet and hence do not meet the expected invariants for the object.
Inlining Security Policies
Want to inline code into the original program; the new program either runs or is truncated (if a security violation happens). Must show no *new* behaviors from the inlining, also all old behaviors are allowed (except the secuirty ones), etc. Single-threaded versions of these inlinings all exist and are well documented.
Multi-threaded is harder: general case isn't solvable (probably because the monitors themselves become non-deterministic). But if the monitor is race-free, (and some other easy properties), then you can do it. Monitor is normally a state-machine.
Cliff Click Talks About Azul
My keynote went well enough; lots of Q&A from the senior people in the audience afterwards. We had to stop the Q&A after running quite a bit over. I also got a lot of positive comments afterwards, so I think people really enjoyed the talk. I'll add that I enjoyed both Simon Jones' and Dave Ungars' keynotes also. This ECOOP was unusual in having 3 "gentleman hackers" give keynotes; we're all three both very scholarly and very prolific programmers. Doug Lea added in a later email:
"Cliff: definitely the best talk I've seen you give (which is quite a few). Someday you'll have to figure out how you packed in so much technical content yet still fully captured attention of people supposedly without the background to understand most of it."
High praise from Doug Lea, so I musta done something right. :-)
Trip home is uneventful, except for Paris's Charles DeGaul airport being the usual zoo. I get up at 4:30am and am in a Genova taxi by 5am for the 1/2hr drive to the airport. Except that there's no traffic at this hour and the driver thinks he's Mario Andretti. We make the trip in about 10 minutes.
So I'm way early into Genova's airport for a 7:10am flight. No power connections for my laptop, for-pay wi-fi (not worth it), no shops are open - not even coffee. No air-partnership; I cannot check in for my USAirways flight from the Air France desk in Genova. I blog for the next hour and a half. The flight leaves on-time and the two hours flying are very smooth. Kudos to Air France. Then we land at Charles DeGaul and the madness begins. We have to walk down the plane stairs and across the tarmac and about 1/4 mile more to the main terminal - but actually it's the small-plane terminal. After figuring out I'm not in Terminal's 1, 2 OR 3, I get instructions to take bus Number 3 to the automatic train and take it to Terminal 1. Of course the buses & bus stop are labeled- with LOTS and LOTS of numbers and plenty of French - takes a question of the drivers to figure out which is the #3 bus.
The bus ride is longish (for an airport bus) and uneventful and then I find the train. Thankfully the train is clearly marked and again a longer ride to Terminal 1 than I expect: Charles DeGaul is a really spread out airport. Terminal 1 is a total zoo; I see lines of people snaking out all over filling the large hall, hundreds of people long. Three times I ask people about which line they are in; none of the lines are marked and all snake back and forth through out the hall; there's a steady stream of people traffic cutting through all the lines and the lines branch and rejoin helter-skelter. Finally I find the 'entrance' to the line for flight #771 to Charlotte - just next to the line for Philly which clearly orbits the entire hall. The Charlotte line is actually fairly short, maybe 20 people long, and after 10 minutes I'm talking to the agent. No problem checking in and then I head off for gate 55 (cutting through the Philly line again). Then it's customs (another 10 minute line), and then a small shopping zone - I figure I'll come back to it for a snack (no breakfast yes; nothing was open in Genova). But then I discover there's yet another line for security. This one is about 20mins long and no way I'm going back for my snack and then back through security. I figure it's like US airports - once past security there will be food and such... WRONG! It's just the end of the lines; I'm in a seating area with about 10 gates and absolutely no way to get a drink or snack - or bathroom near as I can tell. It's now 10:10pm and it's taken me a solid hour to navigate Charles DeGaul to find my gate. As I type, I'm standing by a laptop charging station (no chairs nearby), in the hopes I can do a little something on the laptop during the next 8 hrs of flight.
Later: flight is fairly smooth. They serve some meals; I have another flight through Charlotte, NC to San Francisco. Home at last! For about 24 hrs that is, then I'm on vacation in Texas with my entire family. More plane flights for me! Yumm, I can already taste the small salty snacks they are going to serve...
Slides for my 2009 JavaOne talks:
I'd like to say more on JavaOne, but I'm (re)discovering that if you're a speaker at JavaOne it's really hard to get into the other talks & technology being presented. I had my head full with my 3 talks, making sure they looked good, were relevant, etc. To be sure, there were plenty of talks I wanted to attend, but I never seemed to find the time. :-(
And of course shortly after JavaOne, I went to 2009 ECOOP in Italy for a week, and now I'm on a long deserved vacation.
More blogging soon, on ECOOP at least,
Cliff
http://www.cs.tufts.edu/research/dacapoDaCapo is a small (but growing) research group focused on GC & Memory Management issues. They meet about every 9 months, and the meeting bounces around depending on who is hosting it. People mostly present work-in-progress, and the audience is up front with their critiques... often interrupting the speakers or getting sidetracked into loud off-topic conversations, i.e., it's a fun boisterous crowd.
Various pending goodies...
Pretty much all modern CPUs include some form of instruction for doing an atomic update - required for shared-memory multi-CPU machines (X86 has lots and lots!). There was a long period of debate in the CompSci community one what constituted the "minimal" needed instruction to do useful multi-CPU work. Eventually the community has decided that the Compare-And-Swap (CAS) instruction and the Load-Linked/Store-Conditional (LL/SC) instruction combo both are (1) sufficient to do useful work ("infinite concensus number") and (2) relatively easy to implement in real hardware. X86's, Sparc's and Azul's CPUs use CAS. IBM's Power, Alpha, MIPS & ARM6 all use LL/SC. ARM5 only has an atomic-swap.
LL/SC and CAS are slightly different in how they work, leading to subtly different requirements on algorithms. With LL/SC, you first Load-Linked a word. The hardware marks the cache line as "linked". You then manipulate the word (e.g. add 1 to implement a simple shared atomic counter). Finally you issue a Store-Conditional to the same address. If the cache line is still "linked", the store happens. If not, then not. The line remains linked as long as it does not leave this CPU's cache; e.g. no other CPU requests the line. Any attempt to take the line away causes SC failure (retry is up to the algorithm being implemented). "Weak" LL/SC implementations can easily lead to live-lock - if Load-Linked requests the cache line in exclusive mode (required to do the Store-Conditional), then each LL causes all other CPUs to lose their "link" - and their SC's will fail. I suspect most modern implementations of LL do not request the line in exclusive mode - avoiding the obvious live-lock failure. The downside is that a simple uncontended LL/SC on a word not in cache requires 2 cache-miss-costs: the original miss on the load, and a second miss to upgrade the line to exclusive for the SC.
With CAS, you typical first load a word with a normal load, then manipulate it. Finally you issue the CAS which compares the memory contents with the original loaded value: only if they match does the swap happen updating memory. CAS can succeed if the original cache line leaves the CPU and returns holding the same value - this allows the classic ABA bug. In some cases, Garbage Collection can nicely side-step the ABA bug; you can never find an aliased copy of an "A" pointer unless all copies of A die first - including the one loaded before the CAS. Similar to LL/SC, there can be 2 cache-miss costs: one for the original load and again to upgrade the line for the CAS. Azul has a load-exclusive instruction to avoid with this - a plain load but the line is loaded exclusively. With CAS you can issue any other instructions between the original load and the CAS; typically with LL/SC there's a small finite number of operations that can happen between the LL and the SC without losing the "link". E.g., guarding a one-shot init function by atomically moving pointer from NULL to not-NULL: with LL/SC you must load the line before the SC; with CAS no separate load is needed (e.g. an "infinite distance" between the original load and the CAS).
These atomic instructions only need to guarantee atomicity of update, not ordering w.r.t. other memory operations. Nothing in the academic literature requires any sort of global ordering on these atomic instructions. Instead the usual academic assumption is that all memory operations are strongly ordered - which is obviously not true on all modern hardware. Practitioners are required to insert memory fences as needed to achieve the desired ordering. Nonetheless most implementations of CAS include a strong ordering: X86 and Sparc certainly do. Azul's CAS does not, and this allows Azul to e.g. implement simple performance counters that do not drop updates and also do not force ordering w.r.t. to unrelated memory operations. (As an experiment, try writing a multi-threaded program to increment a simple shared counter in a tight loop without locking. Report back the %-tage of dropped counts and the throughput rate. Then try it with an Atomic counter. My simple tests show with a handful of CPUs it's easy to achieve a 99%+ drop-rate - which basically makes the counter utterly useless). I am less familiar with the fence properties of common LL/SC implementations. Any of my gentle readers wish to report back on the situation for Power, MIPs, ARM, etc?
Some time ago I reported on a build tool I've been using.
Currently 'build' is being used to build HotSpot internally to Azul. We've got it building 400+ files, plus build rules for building portions of the
JDK, compiling w/gcc & javac and also 'javah', tar, jar, strip,
binary signing, etc. In addition to the typical parallel-make functionality, it includes auto-discovery of c++ header files, intelligent load-balancing of big builds, etc. It's blazingly fast, it's easy to hack (being written in plain-olde Java). I hunted around awhile and couldn't find a good place to dump a medium-large blob of code, so here's a sample build.java in 4 parts:
No I didn't do it! This deserving grad student did it.
Here is the reference to the visualizer for the ideal graph of the
HotSpot server compiler:
http://ssw.jku.at/igv/master.jnlp
It is a JNLP application hosted on a university server
(http://ssw.jku.at/General/Staff/TW/ has also a test file to
download), but the easiest way to get a first impression.
The source code of the tool is hosted on http://kenai.com/projects/igv
The server compiler instrumentation is part of OpenJDK and also
included in Sun's weekly builds of Java 7.
I have strong arguments for nearly all orderings of our passes, so I'm
curious to know about your phase-ordering results.
The only obvious transform we might be missing is PRE, but our peephole
opts pretty nearly subsumes PRE (they are not mathematically equivalent
- I can write programs where either PRE or the peephole stuff makes
progress against the other). In practice, PRE will find essentially
nothing once the peephole opts are done. You'll notice that we do the
peephole pass alot; it's totally incremental and provably linear
bounded. In other words, if there's nothing to be gained then there's no
cost in trying. The peephole pass includes amongst other things
all pessimistic forms of copy propagation, value equivalence,
constant propagation (especially the null/not-null property), constant
test folding, repeated test folding, dead code elimination,
load-after-store opts (aliasing analysis is included for free during
building of SSA form), algebraic properties, and lots more.
For HotSpot, the optimization ordering is:
I got too much travel coming up!
Apr 30, May 1st - DaCapo in Boston. Favorite small group; GC & Java focused. Website: http://www.cs.tufts.edu/research/dacapo/. I had to turn down the invite to an SSA seminar in France because the dates conflicted. Very sad. I hope one of the attendees will post a trip report.
May 11-May 15. IFIP WG2.4 (International Federation of Information Processors, Working Group 2.4 - a *really* old European group with a random mix of industry & academia.) It's a nice group to preview JavaOne talks, and always the meetings are a week-long rambling discussion in some quaint resort.
June 2-June 5. JavaOne. I owe slides for 3 talks by end of this week. 'enuf said.
July 6-10th - ECOOP, as a paid-for invited speaker. A free vacation to Italy! :-)
Cliff