Re: JavaMemoryModel: A memory model for the masses

From: Doug Lea (dl@altair.cs.oswego.edu)
Date: Wed Nov 10 1999 - 07:52:39 EST


First, another digression: Both as a cause and result of all the
pressure to make Java concurrency support faster, Java seems to be
turning into the language of choice for "server-side" concurrent
programming on MPs. Concurrent Java programs routinely outperform
concurrent POSIX/C programs these days. Not always, of course, but
often enough that, taken together with other advantages of Java, it
seems that at least as much "serious" concurrent programming is being
done in Java as any other language. (Bear in mind though that my views
stem from the very biased sample of people I talk to, which mainly
consists of exactly these people who have chosen to undertake
server-side systems in Java.) People building such systems tend to care
a lot about correctness, but (for better and worse) to care even more
about performance.

> based on my experience with programming MPs (as opposed to multithreaded
> UPs), i would contend that any language that exposes a weak memory model
> should also export access to atomic operations. they're incredibly
> useful for writing sophisticated concurrent algorithms (in my case, a
> concurrent GC).

I have some classes in util.concurrent (SynchronizedInt, etc) that
were originally designed so as to be amenable for alternative native
implementations using CAS etc. I think this is a productive way to go
about it. But because locking keeps getting faster, it is increasingly
hard to win here on some platforms using raw atomic operations. For
example, if a lock/unlock normally only requires one CAS, you don't
win all that much by going direct to the CAS. All the other operations
involved in the lock/unlock are very cheap compared to the cost of the
CAS itself on most machines.

On the other hand, stamdardizing on such classes would enable VM
providers to optimize implementations that selectively natively
override methods default implemented via synch locks (right Josh? :-)

As I realized only very recently (last week or so), native
implementations are especially unlikely to win for Multiword CAS
(as used in most of Greenwald's algorithms). On a sparc anyway, the
cost of simulating multiword CAS is basically indistinguishable from
doing it via a local lock. I bet this is true for IBM's locks as well.

Part of the problem here is the bad fit of CAS itself to java: CAS
takes an address of an arbitrary field. DCAS takes two of these, most
often of two fields of two different objects. Java has no mechanism
for passing addresses of fields.

Just for fun, consider fixing this by adding a syntatic construct such as:
      a ?= b ? c;
that is translated to:
      atomically { a = (a == b)? c : a; }
that is, a CAS. Further out, consider multiple-assignment versions.

Anyway, such thoughts lead me to agree with Bill's implicit view that
it would be most practical and useful to exploit atomic operations by
having a compiler somehow pattern-match to generate them inline when
the constructs arise.

-Doug

-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:22 EDT