Cliff Click Jr.’s Blog

Category: Web/Tech | Permalink » | Comments (2) » | TrackBack (0) »

http://www.cs.tufts.edu/research/dacapo

Category: Web/Tech | Permalink » | Comments (1) » | TrackBack (0) »

Various pending goodies...

Load-Linked/Store-Conditional vs Compare-And-Swap

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?

build.java

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:

Part 1
Part 2
Part 3
Part 4

A "HotSpot -server" aka C2 compiler IR visualizer

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.

More C2 Goodies

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:

• Build an inline tree, including class hierarchy analysis.  This is the one pass I'd be willing to move, as it happens too early.
• (a single unified pass:) parse bytecodes, inline, build SSA form (the IR remains in SSA form always), do peephole opts over SSA form.  This pass typically costs 40% of compile-time budget.
• Fixed-point the peephole opts over SSA form, once all backedges are known after parsing.
• Loop opts round 1: "beautify loops" (force polite nesting of ill-structured loops), build a loop-tree & dominator tree, split-if (zipper-peel CFG diamonds with common tests, plus some local cloning where I can prove progress), peel loops (required to remove loop-invariant null checks)
• Fixed-point the peephole opts over SSA form
• Loop opts round 2: "beautify loops" (force polite nesting of ill-structured loops), build a loop-tree & dominator tree, lock coarsening, split-if & peel - but if these don't trigger because there's nothing to gain, the do iteration-splitting for range-check-elimination & a 1st loop unrolling.
• Fixed-point the peephole opts over SSA form
• Conditional Constant Propagation (the optimistic kind, instead of the pessimistic kind done by the peephole pass)
• Iterate loop (split-if, peel, lock coarsen - but these typically never trigger again and take very little time to check), unrolling & peephole passes, until loops are unrolled "enough".  On last pass, insert prefetches.  Typically this iterates once or twice, unless this is a microbenchmark and then unrolling might happen 8 or 16 times.
• Remove tail-duplication, and a bunch of other minor code-shaping optimizations e.g. absorb constant inputs into deoptimization-info in calls, or commuting Add ops so that 2-address machines can do update-in-place.
• Convert "ideal" IR into machine code IR.
• Build a real CFG for the 1st time, including a dominator tree, loop tree.  Populate with frequencies from earlier profiling.
• Global latency-aware (loop-structure-aware) scheduling.
• Replace null-checks with memory references where appropriate.
• Register allocate.  Internally this has many passes.  This pass typically costs 40% of compile-time budget.
• Sort basic blocks to get good control flow ordering (forward branches predicted not-taken, backwards predicted taken, etc)
• Some last-minute peephole opts.
• Emit code into a buffer, including OOP-maps & deoptimization info.

Travel Plans

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

Category: Web/Tech | Permalink » | Comments (10) » | TrackBack (0) »

'Tis the Season to be Conferencing...
Blah, I'd rather be hacking, but here goes...  

I went to EclipseCon, to CGO and back to EclipseCon.  Here's how it can down: I got invited out of the blue to talk at EclipseCon by Darin Wright, who had seen me speak earlier at the JVM Language Summit.  Like a dummy I accepted it instantly instead of checking my calander.  Naturally it conflicts with CGO - and I was on the CGO PC this year, so I felt obligated to attend CGO as well.  Turns out my talk at EclipseCon got scheduled for Wednesday, and I decided I could skip CGO on Monday (I think there was one talk I was interested in) - so I scheduled a 1-day only trip to Seattle.  Monday I wandered EclispeCon at the Santa Clara Convention Center, Tuesday I took the 1st plane up to Seattle and the last plane back, and Wednesday it was back to Santa Clara to give my talk and surf the EclipseCon booths.  The flights on Alaska Air were smooth and easy.  No WiFi at CGO - the Hotel wanted some totally outrageous price for conference WiFi (I think the local chair was saying $50/head prepaid?!?).  (Remember my grief over Hotel WiFi in the last blog?)  So over lunch break (which was Chinese food and I don't like Asian food of any kind) I headed over to Starbucks.  Turns out Starbucks will happily give you 2hrs of free WiFi a day from ATT - provided you register $5 on a Starbucks card with them.  Yes!!!  Suddenly I have a $5/month nation-wide WiFi plan!  I snacked on some salad'y thing, drank my triple-latte, and happily Surfed the Internet until show-time at CGO came 'round again.

1st up: EclispeCon, mostly cause I got nothing to say.  These guys are in a totally different ball park from where I live; they mostly deal with complexity control (or at least 1/2 the talks essentially amounted to adding, changing, or removing a control layer).  Makes me wonder if the cure is really better than the disease. I gave my talk, but it was too much talk in too little a time window.  Both me and the attendees would have been better off if I could have spent more time on the details.  C'est la vie.  Other thing of note: the web site for EclipseCon is vastly better than the usual academic conference I attend.  Also the staff was exceptional friendly and easy to work with.

Next up: CGO.  Despite my 1 day fly-in-fly-out I got a lot more out of CGO. 

----------------------

Keynote: Vikram Adve

Missed!  Arrived barely in time for the last 10 minutes.  That's the penalty for attempting a 1-day fly-by.  I hear he said something good about Azul systems (he did ping me the day before for some details).  Basically it's a Call To Arms for improving C compilers and C runtimes.  He does say that fully auto-parallelizing code is probably a bad idea, and that we need to change the language instead (something I very much agree with!).

----------------------

Revisiting Out-Of-SSA Translation

Cliff Notes: HotSpot "comes out of" SSA form during register allocation, where it really preserves SSA form throughout the entire compile process, but adds register annotations as part of reg alloc (and inserts live-range splits as part of spilling). So mostly this talk is about stuff HotSpot has been doing for years... but there's a key new piece.

Linear-time colaescing congruence classes; speed & memory footprints.
Why is coming out of SSA hard? (Cliff Notes: It's not!)

And now they show what HS has been using for years: insert copies as needed for a simple out-of-SSA translation, then aggressively coalesce away the extra copies. 

Nice diagrams for IFGs + copy-affinities.

Notices the value-equivalence property for defining IFGs (also done by HS).

Ok: here's what's new compared to HotSpot -server:

Fast interference test w/out building an IFG!
Only need to test against closest dominating var?
So scan the dom tree, with a stack-based DFS traverse of dom tree. 
Uses 2 sorted lists (?); more complexity for value-based IFG tests.
But no building (and rebuilding?) the quadratic IFG.
Claim 2x faster than Sreedhar for coming out of SSA.
Big memory footprint reduction, because no need for live-ness sets & IFG!!!

40% of HS's total JIT budget is in reg-alloc! A faster reg-alloc is definitely interesting. A large part of that 40% is building the liveness & IFG sets

----------------------

Wave Propagation and Deep Propagation for Pointer Analysis

----------------------

----------------------

----------------------

Category: Web/Tech | Permalink » | Comments (7) » | TrackBack (0) »

Once Again I Put Down my Hacker's Keyboard to Bring You This Trip Report... sigh, all good hacks must come to an end, or at least be put aside so Real Life can intervene.  I went to DC for the ASPLOS and VEE conferences and all you get is this lousy blog.

import java.lang.*;

class TextScan {

 static String test1 = "scan_for_some_token(like_this_open_paren";
 static String junk0 = "scan_for_some_token_like_this_open_paren";
 static String junk1 = junk0.concat(junk0);
 static String junk2 = junk1.concat(junk1);
 static String test2 = junk2.concat(test1);

 // A TextScan is a lite object that's really 8 longs representing
 // the bits of 64 bytes split 90-degrees from verticle.
 long b0,b1,b2,b3,b4,b5,b6,b7;

 public static void main( String args[] ) {
 TextScan[] bits = bit_split(test2);

 System.out.print("bits="+bits.length+"@(");
 for( int i = 0; i<bits.length; i++ )
 System.out.print(bits[i]);
 System.out.println(")");

 // Scan for byte 
 System.out.println("Scanning for byte "+(byte)'(' + (char)0x28);
 System.out.print("[");
 for( int i=0; i<bits.length; i++ ) {
 // bit pattern 0x28 - 0 0 1 0 1 0 0 0
 TextScan ts = bits[i];
 // The open-paren char, '(', hex 0x28:
 // 0 0 1 0 1 0 0 0
 long res = (~ts.b7) & (~ts.b6) & ts.b5 & (~ts.b4) & ts.b3 & (~ts.b2) & (~ts.b1) & (~ts.b0);
 // A non-zero res means a '(' is found, and the bit-number is
 // the index into the 64-byte array where it was found.
 System.out.print(Long.toHexString(res)+",");
 }
 System.out.println("]");
 }

 // Split a String into an array of 64-bit longs.
 // Parallel-split bits: bit 0 from 64 bytes go in 'b0',
 // bit 7 from 64 bytes go in 'b7', etc.
 public static TextScan[] bit_split( String s ) {
 int slen = s.length();
 TextScan[] bits = new TextScan[(slen+63)>>6];
 for( int i=0 ; i<bits.length; i++ ) {
 TextScan ts = bits[i] = new TextScan();
 // Suck 64 bytes into bytearray from String.
 for( int j=0; j<64; j++ ) {
	int idx = (i<<6) + j;
	byte b = idx<slen ? (byte)s.charAt(idx) : 0;
	if( (b&(1<<0)) != 0 ) ts.b0 |= (1L<<j);
	if( (b&(1<<1)) != 0 ) ts.b1 |= (1L<<j);
	if( (b&(1<<2)) != 0 ) ts.b2 |= (1L<<j);
	if( (b&(1<<3)) != 0 ) ts.b3 |= (1L<<j);
	if( (b&(1<<4)) != 0 ) ts.b4 |= (1L<<j);
	if( (b&(1<<5)) != 0 ) ts.b5 |= (1L<<j);
	if( (b&(1<<6)) != 0 ) ts.b6 |= (1L<<j);
	if( (b&(1<<7)) != 0 ) ts.b7 |= (1L<<j);
 }
 }
 return bits;
 }

 // --- toString
 // Reverse bit-swapping to a String.
 public String toString() {
 String s = "[";
 for( int i=0; i<64; i++ ) {
 byte b = 0;
 b |= ((b0>>i)&1) << 0;
 b |= ((b1>>i)&1) << 1;
 b |= ((b2>>i)&1) << 2;
 b |= ((b3>>i)&1) << 3;
 b |= ((b4>>i)&1) << 4;
 b |= ((b5>>i)&1) << 5;
 b |= ((b6>>i)&1) << 6;
 b |= ((b7>>i)&1) << 7;
 if( b == 0 ) break;
 s += (char)b;
 }
 s += "]";

 return s;
 }

}

Category: Web/Tech | Permalink » | Comments (4) » | TrackBack (0) »

(sorry for the long gap between postings; work's gotten interesting and I got busy)

I recently attended the Bay Area Workshop on Transactional Memory at Stanford generously hosted by HP.  Slides are here; my slides are helpfully titled "2009_TMW.pdf".  In this workshop I gave a brief overview of Azul Systems' Hardware Transactional Memory support plus our experiences in using it.  This was followed shortly by a blog posting from David Dice discussing Sun's HTM support in the Rock processor.

For Azul Systems' certainly (and to a lesser extent Rock), the name of the game is throughput: we appear to be generously over-provisioned with bandwidth, we can sustain 30G/sec allocation on 600G heaps with max pause times on the order of 10's of milliseconds (and unlike IBM's Metronome hard-real-time collector, our MMU past 20msec is 0.99; see MMU definition at bottom).  Each of our 864 cpus can sustain 2 cache-missing memory ops (plus a bunch of prefetches); a busy box will see 2300+ outstanding memory references at any time.  We have a lite microkernel style OS; we can easily handle 100K runnable threads (not just blocked ones).  Our JVM & GC scales easily to the whole box.  In short: the bottleneck is NOT the platform.  We need our users to be able to write scalable concurrent code.

The goal of our HTM has always been to accelerate "dusty deck" Java programs via Lock Elision.  (We've never been tempted to enter into the language wars and implement some form of full-blown transactional programming via an "atomic" keyword). We see a lot of defensive uses of the "synchronization" keyword; legacy libraries using "sync" on all methods or code maintainers sprinkling "sync" about liberally in order to squash some bug.  In practice, 99% of all locks are never contended - and these we run very fast (our CAS & FENCE instructions can hit in cache; an uncontended lock requires only a few clock cycles).  But the locks that are contended prevent parallel execution (Amdahl's Law and all that)- and we observed that much of the time the contention is on the lock itself and not on the data it protects.  So we added in HTM support in our first processors and this support has been shipping and turned on at all costumer sites for over 4 years now.  By now we have a lot of field experience with using HTM.

But first, a brief overview of our HTM support: we use a few extra bits on each L1 cache line to track "speculatively read" and "speculatively written" cache lines.  Each CPU can be put in a "speculate" mode; loads and stores then set these bits accordingly.  If a speculative line is evicted from the L1 for any reason then the transaction "aborts" (there is also an "abort" instruction).  Speculatively-written lines are marked invalid (meaning: they no longer cache any data) and speculatively-read lines have their spec-bit cleared.  Also the CPU branches to a fixed trap vector for software fixup. 

If the CPU makes it to a "commit" instruction then the spec bits are cleared - including the speculative-write bits - which atomically makes all those writes visible to other CPUs. In other words, the XTN commits.

Nothing aborts a transaction except the "abort" op or losing a speculative line out of L1.  We do not abort on function calls/returns, nor TLB misses, nor exceptions nor rain nor snow nor sleet nor dark of night...  Our XTNs are limited therefore by the size and associativity of the 16K 4-way L1 cache (and the shared inclusive L2).  We routinely see successful HTMs of many thousands of instructions with many hundreds of cache-hitting memory ops. (contrast this to what I can figure out about Rock: Rock appears to abort on function call/return, on running out of store-buffer depth (which limits an XTN to 16 stores?), on TLB misses, on L1 associativity, on common nested locking patterns (because of abort on function calls)). 

Software heuristics determine when to try the HTM (uncontended locks are much cheaper using a cache-hitting CAS).  The software measures the success/fail ratio of the HTM on contented locks and determines when to flip to a standard blocking implementation and when to use the HTM. 

While some apps get a nice 2x speedup (e.g. Trade6), most apps are speedup only slightly (we had lots of teething problems with the software heuristic that used to cause 10-20% slowdowns due to endless fail/retry loops, although these all appear to be fixed now).  We nearly always see a handful of locks using the HTM support, but these appear to only rarely be the "right" locks to get more CPUs really busy.  HTM failure appears to nearly always be due to conflict and not capacity.

Issues

In short, users' don't write "TM-friendly" code.  Neither do library writers.  For example the "modcount" field in Hashtable is bumped for every update in the Hashtable.  For a large Hashtable we can expect most mods to be in unrelated portions of the Hashtable.  i.e., without the modcount field update we would expect the HTM to allow parallel 'put' operations.  With the modcount field update, 'put' operations always have a true data conflict - and this aborts the HTM.  After some number of failed 'put' operations we have to start really locking the Hashtable (to allow the puts to make forward progress) and this now single-threads the 'get' operations as well.  This general pattern of updates to peripherial shared values (usually performance counters of one sort or another) is very common and it kills the HTM - because it presents a true data conflict.

Many times a small rewrite to remove the conflict makes the HTM useful.  But this blows the "dusty deck" code - people just want their old code to run faster.  The hard part here is getting customers to accept that a code rewrite is needed.  Once they are over that mental hump, once a code rewrite is "on the table" - then the customers go whole-hog.  Why make the code XTN-friendly when they can make it lock-friendly as well, and have it run fine on all gear (and not just HTM-enabled gear)?  Also locks have well understood performance characteristics, unlike TM's which generally rely on a complex and not-well-understood runtime portion (and indeed all the STMs out there have wildly varying "sweet spots" such that code which performs well on one STM might be really unusably slow on another STM). 

Really what the customers want to know is: "which locks do I need to 'crack' to get performance?".  Once they have that answer they are ready and willing to write fine-grained locking code.  And nearly always the fine-grained locking is a very simple step up in complexity over what they had before.  It's not the case that they need to write some uber-hard-to-maintain code to get performance.  Instead it's the case that they have no clue which locks need to be "cracked" to get a speedup, and once that's pointed out the fixes are generally straightforward. (e.g., replacing sync/HashMap with ConcurrentHashMap, striping a lock, reducing hold times (generally via caching), switching to AtomicXXX::increment, etc)

Summary

• Very modest gains for HTM; usually <10% (although 2x for some large apps)
• Rewrites of "dumb" direct contention (e.g. perf counters) would help a lot
• Azul did this for some common JDK pieces Out There (e.g. Hashtable), but there's just too much of it
• Customers not willing in general to touch code for HTM
  • If code is being hacked for performance, it will be with fine-grained locking instead of simply making it "HTM friendly". 

Thanks,
Cliff

[MMU is a common measure of GC performance and stands for "minimum mutator utilization".  It shows the worst-case amount of time a worker thread gets for a timeslice of a given length vs time spent in GC.  Thus an MMU graph plots utilization (a number from 0 to 1 where 1 is better) versus timeslice size.  A program using Metronome might see a max GC pause of 1microsecond; it's MMU at 1 microsecond is then zero because the mutator can do no work for that microsecond.  However the MMU at 1 second might be 70% showing that in the long run Metronome's GC exacts a 30% performance "tax" on mutator operations.  Contrast this to Azul's Pauseless GC: at 10msec our MMU is zero but at 1sec our MMU is 0.99; in the long run there is no GC "tax" but in the short run our max pauses are much larger than Metronome's.  Metronome is suitable for e.g. hard-real-time applications like audio-playback, whereas Azul Systems' is suitable for e.g. soft-real-time transactional apps with high throughput.]

Category: Web/Tech | Permalink » | Comments (11) » | TrackBack (0) »

Category: Web/Tech | Permalink » | Comments (11) » | TrackBack (0) »

A couple of interesting threads running on high-scale-lib's forums I thought I'd post to a wider audience.

Josh Dybnis (jdybnis) - 2008-11-10 11:46
I wrote an implementation of the non-blocking hash map in C. I put it up at http://code.google.com/p/nbds/

Cliff Click (cliffclickProject Admin) - 2008-11-10 17:59
I never know what to make of such statements -

- if the table has "almost no synchronization" then it's not non-blocking (but it might be highly concurrent). Non-blocking has a specific meaning to the academic community; if you say "non-blocking" you should also be able to say "no synch". If you are based on NBHM then you need to provide e.g. a non-blocking malloc and a way to reclaim storage. Both are things NBHM uses GC for, and are not-trivial to get non-blocking. NBHM does indeed do very little allocation - so the blocking embedded in "malloc" will probably never hurt you.

- No "C" program can ever implement any reasonable concurrent program, because "C" has no memory model (and the proposed model is a major punt and not much better than nothing). Instead you can implement NBHM using "C using gcc_ver_XXX on X86_model_YYY". If you change the "XXX" or the "YYY", then all bets are off, and the program can fail. In short, the "volatile" keyword in C does not have nearly the semantics as it does in Java, and C compilers routinely do things with "volatile" variables that Java does not allow. Changing the C compiler version or the underlying hardware can break things.  

Despite my complaints a C version of NBHM on X86 is surely a very useful and non-trivial thing.
Congrats!
Cliff

Josh Dybnis (jdybnis) - 2008-11-11 01:12
Thanks for the feedback. I really appreciate you sharing the algorithm. It's one of the most elegant pieces of work I've come across in a few years. 

- In theory, I agree 100% with you about writing concurrent programs in C. And people need to be clear about the limitations before attempting such a thing. In practice I think it is reasonable to do "porting" work for each platform/compiler. My implementation is targeted to gcc 4.x on 64-bit x86 (Intel does specify a memory model in their Software Developer's Manual). I think it could be ported to most other architectures without major modifications.

- My implementation includes a non-blocking malloc() and a method to do safe memory reclamation. 

- My statement about "almost no synchronization" was badly stated. I was referring to my malloc implementation and not the NBHM itself. Also I was also using "synchronization" to refer to x86 operations having the "lock" prefix, not any non-blocking property of the program.

- A couple of more caveats about my malloc and the safe memory reclamation. They aren't the most robust implementations. They need a bit of work. But they are non-blocking, and should be very low overhead on systems without too many cores (say less than 32). The malloc does call mmap() from multiple threads, it could block in there. So I guess technically it is not "non-blocking". But that is an artifact of the implementation. In theory one could use an asynchronous method of invoking the kernel to make it truly non-blocking. 

Josh

By: Cliff Click (cliffclickProject Admin) - 2008-11-11 07:41
How do you know when e.g. the NBHM Big Array is free?
Cliff

By: Josh Dybnis (jdybnis) - 2008-11-12 17:06
>How do you know when e.g. the NBHM Big Array is free? 
Missed this earlier. 
After I promote a new array the old one gets queued up for a deferred free. (The same with keys in the old array that are tombstoned and were not copied to the new array.) The frees actually happens at a later point when all the threads are guaranteed not to be holding references to the memory. I accomplish this using a technique from RCU. Each thread that might be holding a reference periodically announces that it is in a quiescent state. I have a way of detecting when every thread has made such an announcement. At that point I can safely free the array. My implementation of all that is not particularly robust. If a thread blocks, and never announces it is in a quiescent state nothing more will ever get freed. This is straightforward to fix with a more complex implementation. I'm having an on-going discussion about it on comp.programming.threads. http://groups.google.com/group/comp.programming.threads/browse_thread/thread/702aedc141b34fa1#

Also, one could also use GC in a C program too. Or one of the safe memory reclamation techniques documented in the academic literature (e.g. hazard pointers, smr, etc.). 

By: Cliff Click (cliffclickProject Admin) - 2008-11-12 17:21
Sounds good. Just was wondering.
Lack-of-GC generally brings about various broken attempts to free memory in concurrent programs.

Cliff

---------------------------

By: Cliff Click (cliffclickProject Admin) - 2008-11-11 13:52
> In theory, I agree 100% with you about writing concurrent programs in C..... I think it could be ported to most other architectures without major modifications. 

Itanium. :-)

Cliff


By: Josh Dybnis (jdybnis) - 2008-11-11 19:47
Yeah Itanium, the Alpha would be even worse. It is your NBHM algorithm though; I don't think there is anything dependent on having a strong memory model. You would just have to put memory barriers in the right places. I'm not saying that it would be easy to figure out the optimal solution, but it wouldn't require any major rework to the code. The lazy way to do it would be to change all the CAS calls to include a full memory fence. Doing it that way would constrict performance of course, but it would be correct, and probably still more scalable than a traditional lock-based hash table.

By: Cliff Click (cliffclickProject Admin) - 2008-11-11 21:25
The NBHM State Machine is "correct" independent of any memory model. I still need fences & a Memory Model around the promotion-logic & table-copy areas. It's here with an IA64 would cause you grief. If you didn't need table-copy (i.e., pre-made fixed-sized table), then it would be correct on any shared-memory machine. 

The NBHM as presented as stronger semantics than a minimalistic non-blocking hash table - Keys are treated with Java volatile semantics, so e.g. you can make & install a fresh Key on 1 thread, and have a 2nd thread see the Key from the table and also see the Key's contents so it can correctly run a Key compare. A naive C IA64 implementation can screw up there, although the X86 strong ordering saves it. Same issue happens with the returned Value (made in Thr1, returned in Thr2, but does Thr2 see the initialized contents of the Value?). 

Here's a sample IA64 table-copy screwup:

• - T1 copies last K/V from old table to new table.
• - T1 incrs the last count of copied values. Bug: No ordering between the stores.
• - T2 sees the last count (read of T1's 2nd store), 
• - T2 promotes (stores new table as default)
• - T3 sees the new table (read of T2's store)
• - T3 probes for K, but does not see T1's store.
• - T3 reports K as not-in-table, when in fact it is.

Cliff

---------------------------

By: Josh Dybnis (jdybnis) - 2008-11-12 16:36
What happens if a thread copies a slot and then dies before updating _copyDone? Does the copy never get promoted?

By: Cliff Click (cliffclickProject Admin) - 2008-11-12 16:39
The fall-back case is that some thread (all threads?) scan the entire array and discover that all things are copied, despite any failed counts. At this point the "discovering" thread can promote. 

Cliff


By: Josh Dybnis (jdybnis) - 2008-11-12 17:15
I'm missing where that is in the implementation. I see where a thread enters panic-mode and does the scan, but it looks like it always compares its workdone with _copyDone and the size of the array. So if every slot is copied, but a thread didn't get around to updating _copyDone, none of the panicking threads will ever terminate their scans.

By: Cliff Click (cliffclickProject Admin) - 2008-11-12 17:23
Welcome to the difference between algorithm and implementation. :-)

Feel free to post a fix. It should be a 1-liner.
Cliff


By: Josh Dybnis (jdybnis) - 2008-11-12 17:44
Heh. I have a similar bug in my implementation.

Category: Web/Tech | Permalink » | Comments (0) » | TrackBack (0) »

Or how I went to New England to view the Fall Colors in Perfect Weather,
and All You Got was this Lousy Blog

Azul sent me to Manhattan (my least favorite place on the planet) to speak at the NYC Java Users Group.  I discover that the earliest flight out of San Jose (plus 3 time zones) gets in NYC at 4pm - and that you can't get from a NYC airport to downtown Manhattan in 2hrs during rush hour - so I can't make a 6pm talk if I leave San Jose on the same day.  Sigh - it's the Red-Eye for me.

Wednesday: I end up on the red-eye from Tuesday the night before and arrive at JFK at a delightful 6:30am local time.  No sleep for me.  I've done the NYC subway system a number of times so it's not much problem for me to buy a MetroCard and make my way to downtown.  I arrive at the hotel at maybe 8am in the morning.  Lo!  The hotel is full and they have no room for me - and indeed have no room until 3pm. Certainly by then I am one shabby dude - unshaven for 36 hours, same clothes, no shower, no sleep - not quite up (down?) to the standards of the street people hanging around the hotel but definitely looking grubby.  And I'm exhausted.

3pm arrives and I finally get my room and my shower, change clothes, lay down.... bad mistake.  I barely scrape up enough brain cells to force myself out of bed, and stumble, shaking from sleep deprivation, to the clock: only 90 minutes gone in a blink.  I splash some water on my face and go to meet the JUG.

The talks go very well; lots of good questions from an animated audience.  I presented Challenges and Directions in Java Virtual Machines and Towards a Scalable Non-Blocking Coding Style, and I got quite animated myself - all in all very good.  Dinner was some close-by expensive steak joint, but excellent food.  NYC definitely does steaks well.  Finally the hotel bed looms... and dawn breaks.

Thursday: Today is 2 customer visits, one planned and one directly due to the JUG talk the evening before.  Alas the new customer has micro-second response time requirements; we can only provide millisecond response times (albeit with massive throughput).  The planned customer visit goes much better; it's a tools&libraries group looking for advice on scalable Collections.  After that I take a train to visit my Uncle's farm in Connecticut.  Penn Central is full of these little train ticket kiosks; I happily approach one.  It takes my credit card, works me down through the menus to New London, CT - then hangs.  I try another; this one takes 30sec before posting loudly "Out of Servce".  I'm 0 for 2 so I sigh and get in the infinite line to see a human.  The line takes a full hour to buy a ticket.  Then I go wait for my (now a full hour later) train.  Just when it gets near the head of the list of arriving trains, the train board reports my train as "delayed: 10 minutes".  This goes on for 20 minutes before it changes to "stalled", then finally "now on track #9".  But all goes well after that, my Uncle picks me up in New London and we drive off to the farm.

Friday, Sat, Sun: The next few days are a real delight. The weather is perfect - highs maybe 65, lows in the 50's, breezy, no clouds and the trees in full color.  My cousins are all married and with kids all the same ages as my kids so it's a great time to visit.  I go to a soccer game, the end of a 5K run, a local chocolate & wine tasting, buy from a craft fair and shop at the local antiques shops; help (interfere?) with some hay harvesting, take a stab at fixing 2 Windoze machines (bizarre XP SP3 things about not being able to install Beethoven.wm3 after about of hour of disk grinding), and just plain visiting.

Monday: I pack up my suitcase, both physical and mental, and prepare to jump back into the fray.  The flight to Nashville is easy - except for my last child is finally going off to public school (we've home-schooled all our kids for years with great success), and my wife is in a frenzy getting him ready - and I'm a thousand miles away.  So I get to hear about it between plane flights, in airports, in the cab, etc. The Nashville hotel is nice, and only $150/night for a room twice the size of the NYC $500/night room, and a much nicer neighborhood. 

Tuesday, Wednesday, Thursday: OOPSLA.  Paid $710 at the door - I forgot to pre-reg.  I had great a lunch conversation Doug Lea, Bill Pugh, & Ben Zorn.  I take lots of notes.  Lots of great hallway and dinner conversation covering reader/write locks, the state of the JCP & Exec Committee, whether Sun should drop the JCP process altogether, whether the market will implode & we should all run up our credit cards to the max, end of civilization, etc. Ben tries to convince me that Microsoft can be trusted as the sole holder of all my critical personal information (sorry Ben) and that totally transparent sync'ing of all my portable & desktop devices is coming Real Soon Now.  Perhaps - but I'm never going to trust my personal info to some single central server - even if it does get old-school Ma-Bell-land-line-style 5-9's reliability for both the server and the sync'ing.  Too many companies have said "it's safe with us" and been wrong.  Too much motivation for crooks if all the eggs are so close together.  Other conversations that stuck in my mind:

• Azul could Open Source or JCP our hacks for +UseLockedCollections (see about 1/2-way down the blog) and +UseCheckedCollections.  This could be a Good Thing for Azul as it will reduce the number of apps which fail "out of the box" on Azul as well as raise awareness of the issue.  Note that all major App-Servers (and many a large 3-letter-acronym company's major product) fail on Azul without +UseLockedCollections (and runs great with it) and the issue has nothing to do with Azul except we have more cores.  I.e., I predict these crashes will soon be coming to an X86 multi-core Near You!  I can hand out stack traces for any interested parties; email me for details (and yes, bug reports have been filed but between me and you I suspect most of them get filed into the round bin).
• Bill Pugh offers that at Google they have a 3rd option: log&continue.  The logging is only invoked where now I would throw a ConcurrentModificationException - but there's no standard JDK place for logging such things.  We certainly could add an Azul logging option where the output is available on a RTPM data-race screen.
• Doug Lea desperately needs 3 things to make his Fork-Join parallelism have a sane API - note that Fork-Join has a really nice approach to handling large complex parallel problems - there's no real limit on scaling plus it has a fantastic story on automatic load balancing which is typically really crucial for us.
  1. Tail-call optimization.  Part and parcel of the solution when doing recursive decomposition.
  2. Some kind of auto-boxing-removal story.  See also John Rose's DaVinci Machine.
  3. Some kind of forced inlining story, so that a complex F-J iterator gets cloned at the site where the loop-body is declared.  This will allow the (highly megamorphic) inner loop function to be specialized per call site, inlined into the iterator loop and decently optimized.
• Several people asked for a Weak-Key'd AND Weak-Value'd NonBlocking HashMap.  

Friday: I make last minute plans back to NYC to visit the tools & libraries customer group again.  It's a 6:45am flight out of Nashville, which means be at airport by 5:am so leave hotel at 4:30am and get up at 3:30am.  Sign, another day with no sleep.  The flight to NYC is rocky as all heck, the clouds have finally arrived to ruin my days.  We bump for 2hrs out of a 2:45hr flight.  Then it's AirTrain to Jamaca Station, Long Island Railroad to Penn Station, Subway#3 to Wall Street - I'm coming quit good at navigating NYC.  I'm almost an hour early to my customer visit - which is really an open-ended tutorial on Azul's profiling tool: RTPM.

These guys are doing some fun stuff.  They have their own versions of the standard JDK collections where the expected collection size is 1million to 10+million elements.  They have very efficient striped iterators (100x speedups on a 100-way Azul box) and are looking at Doug Lea's Fork-Join for describing their inner loop closures.  RTPM goes a long way to helping them figure out what's going on.

There's also a nifty in-memory DB thingy where we discover that turning on "-tiered" mode (contrast to HotSpot's -client and -server modes) is worth a stunning 5x speedup (Azul usually sees something like a 15% speedup for -tiered).  We try to make the in-memory DB run that fast under a ReadWriteLock.  The customer has a very light-weight roll-your-own version (new in Java6: lots of new features in the JDK ReentrantReadWriteLock class which slows it down by 50%).  The customers' lock doesn't stripe the reader-counts and instantly suffers massively on the highly contended single reader count word (which the JDK version does as well).  I step their engineer through details of reader-lock-striping; it's definitely ticklish stuff to get right.

Finally 5pm arrives and everybody is going home - although for me "home" is really a subway ride to Penn Station, then a train back to New London, CT for another weekend on the farm.  I am sooooo ready to be back in San Jose.

Saturday, Sunday: Another great weekend on the farm; I finally get to see some rain (it's not rainy season in San Jose yet so I haven't see rain since March).  The wind blows down a tree over the power lines and we lose power from 9pm Sat to 5am Sunday (when my room lights pop on and wake me up, grumble).  With the power out and the internet gone it really feels like a farm.  On Sunday I take the train in to Boston, then have dinner with David Bacon at Legal Seafoods & take the T to my hotel.  Gosh I almost feel like a savvy New England traveler. 

Monday is the 2009 VEE PC meeting.  Despite missing 1/3 of the PC members (two have new babies, one got food poisoning, several had other issues that made them dial-in only for a few minutes at a time), the meeting went very well.  We got done early and I got to take the new Boston T Silverline to the airport - it's labeled like a subway but it's really an electric bus (the long bendy kind) in it's own bus-sized tunnel.  Logan was easy, the flight was smooth and I made it home (finally) at 1am local time.  It's good to be home.

Continue reading "Cliff's New England Fall Travel Classic " »

Category: Web/Tech | Permalink » | Comments (11) » | TrackBack (0) »

I spent last week at the JVM Language Summit, a small conference focused on non-Java JVM-based languages.  It was populated almost solely by either JVM implementors or bytecodes-are-my-new-assembler types.  It was a very fun & geeky conference for me; some of the best technical discussions I've had in a long time.  My favorite philosophical talk was definitely Erik Meijer talking about Fundamentalist Functional Programming.  In the end, he's all for non-pure side-effecting programming BUT he wants the type system to "stop lying" about side-effects.  We both agreed that we'd love to see a functional programming language which had types for side-effects (e.g. Haskell's IO "sin bin"), but with more elaborate side-effects.  I.e., if I'm writing my program with few-to-none side effects I might want to track them exactly (e.g. this function has type 'side-effects field _code') but if I call into the Swing or AWT libs I might want a type like 'side-effects all Java variables'.

My favorite techy/JVM talk was Bernd's Maxine VM.   I think he's got a really good nearly pure-Java layer figured out for generating ASM code.  You want something that looks like running plain Java code (and does field reads & writes) that guaranteed must inline down to where the JIT turns it into atomic machine code loads & stores.  He's missing lots & lots of major features (e.g. good JIT, good GC) but the framework looks nice.  If we ever are to get a true JVM-in-JVM (and skip bootstrapping your JVM via a C++ compiler which is what HotSpot does), I think Maxine has the best chance.

Most desired JVM feature: invokedynamic; this would cut huge chunks of evil code out of most JVM-based languages (but not Clojure & JPC, both of which target 1.5 JVMs more closely).
Most needed JVM feature without changing the spec: a trivial Escape Analysis suitable for dealing with endless Fixnum/BigNum math.  Most of these non-Java JVM languages do fixnum/bignum math (automatically overflowing fixed-int math into bignums) - which means every trivial bit of integer math creates a new Fixnum object.

I showed off Azul's RTPM and got lots of oooo's and aahhhh's.  I convinced lots of people to sign up for academic accounts mostly for access to RTPM.  I was able to quickly diagnose a big problem w/JRuby (failure to inline a key trampoline, masked by +PrintInlining lying), and also got 20% speedup on the ASM library - the core bytecode parsing library in widespread use.

My own talk was well received:

Brian Goetz wrote:

your talk was both the most popular and highest rated, according to the comment cards. 

The slides are here although the postscript conversion mostly screwed up my transparent ovals.  Mostly I ran this trivial program on Azul's JVM using these languages: Scala, Clojure, Jython, JRuby, JavaScript/Rhino, & JPC. I profiled them using RTPM and report on the profiling.  See the slides for the in-depth discussion.  3 things popped out:

1. Clojure, JRuby, Jython, Javascript/Rhino all using fixnum/bignums for every trivial piece of math - which ends up allocating new FixNums for each simple integer operation. A major fix for this would be to implement the simplest possible Escape-Analysis. You'll still end up with the overflow checks but the major cost here is the Fixnum allocation (and NOT the GC costs; the fixnums trivally die in the young-gen; direct GC costs are quite modest).
2. JRuby was thinking that a key trampoline function was inlining - and it wasn't.  See the slides for details, but hopefully we'll see a JRuby with a substantial performance boost soon.
3. I ran Clojure's STM Traveling Salesman Problem using 600 worker 'ants' to optimize the path.  It ran straight-up without a hitch, no tweaks - and with great scaling (it did allocate about 20Gig/sec on a 200Gig heap but this is easy for an Azul box to cope with).  There may be hope for STM's after all - IF the set of STM variables is limited to a handful of named shared variables, and not for dusty-desks that must assume all-is-shared.

Cliff

Category: Web/Tech | Permalink » | Comments (17) » | TrackBack (0) »