Here's an attempt to summarize the issues in the last week or so of
posts on related topics.
"Multiple reader parallelism", often associated with "concurrently
readable data structures" is a style of concurrent programming that
seems problematic for the proposed LC-based memory model. This is a
concern to me because it is the ONLY problem I know of with LC. In all
other respects, adopting an LC-based model seems to solve all known
problems with current JLS model in the best way I know.
The basic programming tactic here is:
* All data are always kept in a consistent enough state so that
they can be read at any time. If update(s) are in progress,
a reader will see either data reflecting the state before
one or more updates or after any one of them.
* Reader threads are only loosely coupled to updater threads.
There is no reason to synchronize a given read with any given
update for the sake of serializion/exclusion. (In other words, you
can tolerate certain data races.) However, there is still a need to
guarantee that the results of the read operation reflect
"recent" updates (see below).
* Not only is synchronization on reads unnecessary, it is undesirable,
for the sake of liveness and/or performance.
* There are two variant strategies (and a range of intermediate
options) for the implementing update operations: using full locking or
using CAS-like optimistic techniques.
The main problem is:
The proposed model does not have any analog of general read barriers
(except for those tied to locks). On machines that need them, read
barriers are used to make good on requirements for obtaining the most
recent committed data values upon onset of the read operation,
which is a semantically desirable way of defining recency.
This is not an everyday programming practice. The main people who use
it are people like me trying to create efficient libraries and
utilities at the java level, as well as people writing infrastructure
code -- I suspect that most MP VM developers use such techniques fairly
regularly (although surely in C, not Java).
Question 1: Is this kind of construction worth supporting at all?
Against:
* Accommodating it may complicate the memory model and/or the language.
* Support may introduce additional opportunities for programming errors.
* Concurrent readability is already assured for scalar volatiles.
We should challenge people to create algorithms that can
somehow live within existing constraints.
* On some machines, these techniques are likely to be slower
than use of lock-based algorithms. (However, they
may still apply when the main goal is to preserve liveness by
avoiding use of certain locks.)
For:
* Such algorithms would otherwise only be implementable via native code.
* There is otherwise no hook for strongly ordered machines
to optimize away the read barriers to improve performance.
* Concurrent readability, and the presence of barrier
instructions, is a defining property of shared memory
multiprocessors.
If most people think the answer here should be no, we should probably
just drop it.
But if you think that the answer should be yes, the next question is how.
None of the known options is very attractive:
1. Mandating that any read of any volatile reference/array be
preceeded by a memory barrier.
Advantages:
* No changes to the language.
Disadvantages:
* Adds unwanted overhead by disallowing implementation of
reads via atomic instructions.
* Complicates the memory model by adding operational
restrictions that I don't offhand see how to even state within
the proposed model.
* Disables some other otherwise legal optimizations for
volatiles.
* Because "volatile" applies to all uses of a field, not
just the places where a barrier is actually needed, this is
less controllable, and potentially results in slower code than
other options.
2. Introducing natively implmented barrier functions in JDK, as in:
class java.lang.MemoryBarrier { // or in class System
static void readBarrier();
}
(As mentioned before, you can add up to four flavors of
barrier here.)
Advantages:
* Relatively low impact on the language.
* At least some uses can be optimized to no-ops on some machines.
Disadvantages:
* Requires a change in java libraries, which will take a
while to adopt and implement.
* Adds unwanted overhead on uniprocessors.
* Complicates the memory model by forcing it to take account
of special library functions.
* Complicates the rules for optimizing code.
3. Introduce "scoped volatiles" :
volatile(anObject) {
// reads/writes
}
Advantages:
* The semantics seem to be readily definable within LC model.
* Usages seem amenable to mechanical sanity checking.
* Supports the most controllable and optimizable code of all
options.
Disadvantages:
* A major language change. Even if adopted, it would probably
take several years before you could write portable code employing it.
4. Scrap LC-based approach. If JLS approach is preserved, then
synchronized(new Object() { ... }
suffices here.
Advantages:
* At least it is somehow expressible.
Disadvantages:
* Relies on clever optimizers to reduce this construction
down to either a read barrier or no-op.
* Requires a different solution to all the problems with JLS
approach that LC solves.
I'm still hoping that there are better undiscovered options.
-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:23 EDT