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
'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
----------------------
----------------------
----------------------Stream Compilation for Real-Time Embedded Systems
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.
// The open-paren char, '(', hex 0x28:
// 0 0 1 0 1 0 0 0
long res = ~b7 & ~b6 & b5 & ~b4 & b3 & ~b2
& ~b1 & ~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.
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;
}
}
(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)
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.]
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:
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.
=============================
compareAndSwap memory fence (New)
Andrew Trick (andrewtrick) - 2008-11-12 11:16
My interpretation of your slide-set/blog comments is that the NBHM state machine--ignore table copying for now--does not require any memory fences or store ordering. CAS_key, CAS_val gets the job done as long as your machine has atomic compare-exchange. Correct?
In fact, in NBHM source you bypass util.concurrent.atomic, calling Unsafe.compareAndSwapXXX presumably to avoid the memory fence. However, the Sun JDK and HotSpot assumes that Unsafe.compareAndSwapXXX enforces a full memory fence. So would it be fair to say that you've made Azul-specific changes to the JDK/JVM to optimize NBHM? Should Sun get rid of the full-fence semantics of Unsafe.compareAndSwap before more Java/JDK code begins to rely on it?
-Andy
By: Cliff Click (cliffclickProject Admin) - 2008-11-12 11:20
Yes, I need no fencing (ignoring table copy) for some kind of hashtable semantics. You DO need very carefully placed fences to get CHM semantics - which amount to 'volatile' semantics on values used in put & get calls.
I bypassed the Atomic classes to get the no-fencing CAS. The Unsafe calls specifically have weak no-fencing versions. On an X86 & Sparc you are stuck with the fencing anyways, but on Azul the weak no-fence version actually does not fence.
So I did not do any Azul-specific changes to the JDK here (Azul's JDK IS different from Sun's - but not here).
Cliff
Andrew Trick (andrewtrick) - 2008-11-12 19:05
Thanks for the reply and clarification.
The JDK does indeed have AtomicReference.weakCompareAndSet. Sorry to be pedantic about API details but... What I meant by "JDK assumes a fence" is that AtomicReference.compareAndSet for Sun is identical to weakCompareAndSet, so the underlying Unsafe.compareAndSwapObject must have a fence. What I meant by "HotSpot assumes a fence" is that the Unsafe.compareAndSwap intrinsic generates abstract memory barriers, which you would have to materialize as a real barrier on any machine that doesn't have implicit CAS fences.
But really I was just trying to understand the intention behind your NBHM source, which is pretty clear now. It's not important whether some careful JVM porting is needed to make it fast on certain h/w.
By: Cliff Click (cliffclickProject Admin) - 2008-11-12 21:35
Letsee...
- sun.misc.Unsafe does not specify any memory ordering properties for compareAndSet.
- AtomicReference.compareAndSet is doc'd to have volatile semantics, and operates on a volatile variable.
- AtomicReference.weakCompareAndSet is doc'd to NOT have volatile semantics.
A legit JDK implementation could then
- not fence for sun.misc.Unsafe
- but yes fence around volatile ops, including Unsafe ops on volatiles.
This is exactly the intent of the docs & implementation, and it specifically allows Azul to not fence on sun.misc.Unsafe & still meet the spec - which we do (on both fronts: not-fence and meet-the-spec). We also typically do not suffer from other peoples' bad assumptions here - where they expect Unsafe to fence and are surprised when it doesn't. I suspect Unsafe.CAS users are a rare breed.
Removing the fence for Unsafe ops is a tidy win for Azul on some highly parallel contention-heavy codes.
Cliff
That's all,
Cliff
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:
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.
Some (very raw) OOPSLA notes. As usual with these notes, it's my stream-of-conscious thinking with a heavy Cliff bias. Caveat Emptor.
========
I sat through some talks about new language designs/features over JVMs - they looked klunky. I liked this one: Mixing Source and Bytecode. Sorta like GNU ASM with C++, except for Java. The bytecodes are fully verifiable. This allows you to write, i.e., a naked monitorenter bytecode - something you can't do with pure Java. Useful, e.g., for hand-over-hand locking or read/write locks. Can nest Java & bytecodes so can use Java to build e.g. string constants to be used in 'ldc' bytecodes.
========
Tolerating Memory Leaks - Mike Bond - (graduating this fall, Go Mike!)
Great story about a memory leak in a 10000 line C# Darpa Grand Challenge vehicle - would run out of memory in 45minutes - Quick Fix: stop truck & reboot machine after 40 minutes. Alas, in the real challenge (and not the test bed) garbage accumulated faster & machine crashed after 28 minutes (while truck was still rolling and so IT ran off course & crashed).
I've reported on this before (Tool is called 'Melt') and liked it then as a Neat Idea. He basically pickles to disk stale "leaking" objects, and can tolerate leaks until he runs out of disk space. He's using software read barriers that are costing them 6% app slowdown using Jikes 2.9.2. The barrier is a bit-test, then if it's set they have to CAS it off:
b = a.f; // load object field
if( b & 1 ) { // low-bit is set?
b &= ~1; // clr low bit
if( b & 2 ) ...slow path...
CAS a.f,b // clr in memory as well; no need to retry failure
}
So this little-bitty read-barrier costs 6% at the app-level??? I suspect a failure to optimize in the JIT.
Cool - most leaks are in HashMaps - and by stale objects are never accessed again EXCEPT to re-hash(!?!?!) the table when it grows. Since the objects are actually accessed (by the re-hash logic) they appear to be live - but the only use is to re-hash them. Perhaps we'd like a HashMap where re-hash does not involve calling hashCode but just uses a cached prior copy of the hashCode, and we can avoid calling hashCode on a stale key (you still have to copy the K/V to the new table but that can be done without touching the Key again).
========
Jolt - Reducing Object Churn in Large Programs - Matthew Arnold (IBM labs)
(why not a simple Escape Analysis or a Gen-GC???)
(but also: this is why SBA 'works' - there IS lots of local churn)
Implemented in IBM's J9 & run on large programs. Better than Escape Analysis (EA) alone? Getting up to a 15% speedup. Some EA's do better: add context & go up call-stack.
Really it's doing a EA on the root of a call-tree that contains churn. Same as C2 (HotSpot's -server) would do after inlining. They are doing some fairly tricky analysis to decide where to run their more aggressive EA, using dynamic info to decide that they have a 'large enough' subprogram to get the right amount of context. Then they force inlining to get the right 'context' to get good a EA; inline children with the largest ratio of bytes-allocated to code-size (trying to avoid code-bloat blowout).
Looks a lot weaker than Azul's Escape Detection solution - we'd first let SBA identify places where stack-local objects are being churned, and then we'd inline & do a trivial EA. But IBM has a working solution (in the lab) for deciding what to inline to enable EA (and J9 has an existing compile-local EA which is working fine).
EA by itself in J9 - from 1% to 9% of objects eliminated. Just not enough context to do good EA. With JOLT seeing 5%-30% objects eliminated (30% is for SpecJBB2005). (Note: Azul's SBA sees 60-70% of all objects get stack-allocated).
========
QVM- Dynamic Analysis for Debugging - Matthew Arnold (IBM labs)
Two camps:
How far can we go with low-overhead but checking deep program properties. Ask user: "how much overhead is ok for this info?" Give as much info as possible within this budget - so may miss errors, etc. But approximately good info.
So have an "overhead manager" to meet users'budget. Then have 3 analysis that can be managed: Typestate properties, heap probes & assertions, and finally running some Java assertions. Overhead manager watches the sampling costs & adjusts sampling rate to keep costs within budget. Must have fine-grained timers, must have total CPU time across all things; must have direct access to RDTSC or else accumlative errors kill you. Total CPU was hard for them to get from Linux (I believe Azul has this via azps/aztop).
Different program points are sampled more or less heavy. Really, sample at 100% at each program point until the OHM starts to see bad overheads for some program point - then start lowering the samping rate. So init code gets 100% coverage, but hot loops maybe 1% or 0.1% sampling. Thus get very good coverage of rare events and "good enough" coverage for highly repetitive events.
Type-state sampling is performed not at the method-level, but at the object granularity (steal a bit in object header - set a bit to track an object).
Heap-profiling asserts, e.g. - "is_shared(Object o)" asks the GC "is Object o shared or am I the only Thread with a ptr to o". Requires a full heap traversal. Put it in the Overhead Manager, which throttles the full GC rate into budget.
Experiments: it works. Overhead IS kept within budget for these large apps & complex tests. Able to find several bugs in interesting large apps.
========
Contention-Aware Scheduler: Unlocking Execution Performance in Multithreaded Java Programs
Have a global per-thread lock-held-count. If it's above zero, hint to scheduler to avoid losing the quantum; allow up to 5 quantums to release all locks. 5 quanta is typically enough to release most Java locks. Also - raise priority of threads holding locks; more locks held ==> raise priority more.
ALSO - if T1 & T2 are sharing the same lock/object then schedule them on the same processor. Actually limit this heuristic to just simply enqueuing T1 & T2 on the same runqueue (if already all processors queues are busy). (You don't want to deny a runnable T2 a shot at an idle CPU, but if all CPUs are already time-slicing...)
Thread Clustering: record contended sync events in a per-thread ring buffer. Each time the ring-buffer wraps, summarize the per-thread per-lock counts and then compare them to other threads. Look for affinities; create clusters of threads sharing locks. Migrate whole thread clusters onto a single CPU's run-queue. Increasing the size of the per-thread ring buffer lowers the rate at which clusters are recomputed (so can adjust the overhead; using 2K; reports 2-3% overhead (but is that per-thread or only-when-blocked, etc)). Load balance threads not involved in clusters.
Bench'd on SpecJAppServer2005, ECPerf on JBoss4 (and others). Run on a 16-way AMD (8xdual). Seeing a 20% to 40% contention-reduction (what's that?) when using both scheduling notions (clusters of related threads, plus lock-aware quantums). Seeing overall perf improvement by 5 to 15% on these big app servers. Also seeing better scaling (up to their 16-way box); but not hugely better scaling. Azul clearly gets better scaling here - but we might get even better with this kind of lock-contention-aware scheduling.
Was pointed out that since threads sharing locks are now on the same CPU, it might be that the speedup is really because of cache locality of other shared objects (not just the locking ones).
We might could do better by tracking L2-to-L2 miss rate and associating the misses with the threads on the CPUs at the time - and come up with some sort of "these 2 threads are talking to each other" metric.
========
Dynamic Optimization for Efficient Strong Atomicity
(Yet Another STM Paper; can you tell I'm not fond of STM?)
Getting Strong Atomicity is expensive (well maybe or maybe not: see the Clojure model).
Looking at whole-program analysis to discover objects NOT being accessed inside transactions - plus some dynamic analysis to find that most objects do not participate in a transaction. Then the STM does not need to annotate/track accesses to these objects.
NOTE that Clojure gets this "for free".
They manage to get performance withOUT any XTN's (e.g. single-threaded SpecJVM98) to only be 10% slower. It's very complex - involving compiling with "phantom barriers" around most memory updates, then stop-the-world code-patching to install barriers as he discovers objects are being used in XTN's, etc.
========
Design and Implementation of Transactional Constructs for C/C++
Next talk is about Intel adding STM into C/C++ code - alas the new C/C++ memory model gives no semantics to racey programs and all large multi-threaded programs are racey. Indeed the authors had to hack the handful of XTN-friendly programs they had access too to remove races.
========
Renaming for Java
"isn't this solved already"?
All major Java IDE's implement renaming for Java; a very basic and very important refactoring. But all these IDE's have bugs. He gives short demos & spares no IDEs. Basically: renaming is hard. The lookup rules are complex. Gives a nice javac/JAST hack for doing it right (and sometimes you *must* give up, the renaming rules are so complex).
========
Java Performance Evaluation through Rigorous Replay Compilation
Show nice violin plots of 30 measurements of SpecJVM98 & DaCapo. About 10% variation overall, but more for e.g. mtrt. It's Standard Issue: samplers & tick counts (and scheduler variation) cause JIT compilations to occur at different times & places; so the basic code-gen is different. After this variant JIT compilation performance from run-to-run in the same VM is reliable faster or slower.
Attempts to remove variation by fixing compilation load. Replay compilation: 1st run, record compilation decisions. Later runs: read in the "replay" and compile exactly the same way (ala Marty's FAM). Actually, run the same benchmark over & over; during the 1st run do all the compilation (because you can't compile until classes load, and loading requires execution). Later runs in the same VM no longer are allowed to JIT.
Issues with choosing a good compilation play (pick plan giving best score, or majority plan or....) moves the non-deterimism from runtime to compilation-plan-choosing-time.
Show significant differences amongst compile plans (yes, well experienced by me; often I get "good" runs and "bad" runs based on stupid compiler decisions).
Run 'q' benchmark iterations for performance, and also 'p' VM invocations yielding 'p' compilation plans plus the statistical variation during the 'q' runs-per-plan. End up with p x q measurements (bleah! Lots and lots of runs to control for variations!).
Show violin plots for 10 plans for jython. A lot of variation is observed for most benchmarks; i.e. "the plan matters". Compile plans have little overlap on which methods are the 'root' of compilations.
Nice really good statistical analysis of the situation. Can show that picking different plans can significantly change the results of apparently unrelated experiments (i.e., which GC is better). Can show that about 10% of compile plan choices on jython will cause conflicting ("lying") results of which GC is better. i.e., if I pick plan A then I can show MarkSweep is better than GenMS, but if I picked plan B then instead GenMS appears better than MarkSweep.
Can do paired measurements: run GCxxx and GCyyy with plan A & diff the results. Diff the results for plan B, etc... Now I can see if picking a plan makes a difference. Show that it does about 85% of the time.
Really shows: you should pick more compile plans before running the benchmark more iterations. I.e., If my time budget requires me to pick between running the benchmark in the same harness 10 times vs 10-from-scratch runs, I need to do the from-scratch runs because this will capture the non-determinsm in the compilation plan.
========
Analysis & Reduction of Memory Inefficiencies in Java Strings
Trade6 - 40% of heap is strings. Many dup'd strings & many unused literals. Unused literals - due to error messaes for error paths never taken. (but I suspect unused literals are not important for Azul because their count is fixed with the application and does not scale with heap size). For Trade6 - about 1/2 of heap strings are wasted - 1/4 are dups and 1/4 are wasted in fragmentation. Azul does not suffer fragmentation because we don't share string bodies.
He proposes interning strings during GC (but this changes semantics ever so slightly - things that were not "==" before become "==" afterwards. Have a "tenured string" hash table - long lived strings go also into this table; then young-gen strings can be checked against the table by GC. Most of the experts in the audience want to claim that the change is ok - no self-respecting Java program will be broken by this change (myself included, but I don't want to put words in other peoples' mouths).
Note that Azul has already rewritten the String implementation to remove the offset & count fields and we don't share String bodies. This hack LOWERED our average String footprint by maybe 10% and brought us a similar speedup (10% smaller heap footprint means 10% smaller working set means 10% more effective D-cache usage, etc).
They also hacked the VM to deal with the large count of unused literals. Make a special version of String which holds the constant-pool index and a null char array. When exploding on the null-char-array access they look for this special String & lazily make the body as needed. Removes ~20,000 string literals from Trade6. But note he is using tiny heaps - and the literals will not scale with heap-size, but the dup'd strings will.
When run on SpecJVM98, DB becomes vastly faster but no change on the other benchmarks. Reduces live heap on DaCapo by 10% of heap. For Trade6 & Tuscany reduce live heap by 20%.
========
Analyzing the Perfomance of Code-Copying Virtual Machines
Interesting hack to speed up interpreter-only languages.
========
Performance of translated COBOL programs on a JVM
Some things translate nicely; can make all COBOL variables Java instance variables for thread-safety. COBOL divisions become Java classes, etc. COBOL "picture" clause specifies amount of storage to be allocated, but mostly has direct translation to e.g. Java's BigDecimal class or fixed-length Strings.
Can specify arrays-of-structs in COBOL; again fairly easy to make a Java struct array and fill in all structures (but lots of wasted space for Java object headers). Actually seeing lots of wastage - gives 7x space blowup example. Seeing vast wastage in practice.
Can '#include' COBOL header files, often done for just one or two fields in the header. But must eagerly construct all defined storage space.
COBOL subroutines include "open" and "closed" (normal) subroutines; open subroutines tend to be translated as ending with exception throws - result is most subroutines end in an exception throw.
Opt 1: share common init'd String, essentially interning all Strings of blanks.
Opt 2: Same thing for BigDecimal for value zero but with different scale/decimal-point values. Instead just return a common cached version.
Opt 3: All internal fields of structs & arrays are lazily constructed. Use getters/settings, and get'ers lazily convert null's to real storage only if asked for - for each array element or field value.
Opt 4: Remove extra throws; notice when calls just return normally and allow callee to just return.
Opt 5: Translator by default uses a lot of reflection, they now make class-specific versions of many things to avoid reflection.
Opt 6: Lots of time/date String manipulation. So made some custom date/string conversion functions to match the specific COBOL requirements instead of using the default Java Date-conversion libs.
Overall, seeing 10-20% perf improvement, with nearly 75% of objects no longer being allocated.