I can't help but comment on the efficient hashtable question (I'm really
just a lurker on this list but my research involves the memory model and I
strive to understand it more). It seems that some hashtables that act as
caches don't nescessarily need any sort of synchronization to be correct.
Goal: provide a "cache" for mappings that cannot be changed. This includes
all mathematical formulas (given a set of values, one value is produced),
and many data structures (e.g. add once lists, maps where the mapping of
a key is not changed after the key is added).
The simple hashtable depends on the fact that a single store can be used
to update it and a single load can be used to query it. On most (all?)
architectures, loads and stores of words are atomic in themselves,
although a series of loads and stores may not be. The property of this
value is such that "if" the hashtable contains a key, then the value is
the correct value, otherwise their is a "miss" in the hashtable and you
must go to the next level of computation (look up in a more complicated
data structure, or do a complicated computation). In this way the
hashtable is a cache.
Remapping (or invalidating) a key is not a valid operation for this
hashtable, as it cannot be done atomically without synchronization (of
course, it can be allowed if a write barrier is used upon updates and
ivalidates, they just become expensive operations for this structure).
Admitedly, the usefulness of this data structure is mainly caching, but
since it doesn't need synchronization (it is not important if the data
read is old or new wrt correctness).
Example:
class SinCacheEntry {
final Float key;
final Float value;
}
class SinAlgo {
final SinCacheEntry cache[] = new SinCacheEntry[CACHE_SIZE];
public Float doit(Float key) {
Float answer;
{
// our single allowed load.
SinCacheEntry sce = this.cache[key.hashCode() % this.cache.length];
if (sce != null) {
if (sce.key.equals(key)) return sce.value;
}
}
answer = sin_impl(key);
// our single allowed store
this.cache[key.hashCode() % this.cache.length] =
new SinCacheEntry(key, answer);
return answer;
}
}
Assuming that sin_impl is thread safe, I'm willing to say that the method
doit should also be thread safe (at least under some reasonably safe
model). This is without any synchronization at all.
Are my assumptions reasonable? I'm working with cases that must remain
atomic with no synchronization.
- Sean
mcdirmid@cs.utah.edu
O (801) 581-4280
H (801) 466-8446
--WEB http://www.cs.utah.edu/~mcdirmid
On Sun, 24 Oct 1999, Bill Pugh wrote:
> >The problem isn't with sleep. The problem is that the way load/read/use are
> >defined (don't have the book at home, so I can't quote it) it is completely
> >legal and even encouraged to write code that polls a variable modified by
> >another thread without synchronization.
>
> The existing JMM doesn't mention sleep, so it isn't completely clear.
> A loop that simply busy waits to see a change from another thread,
> with no synchronization inside the busy wait loop, is definitely
> broken under the old memory model (and would be under my new model,
> and I think any reasonable model).
>
> The question is what does sleep do? Is it simple a most cost
> effective way of waiting for a certain number of milliseconds than a
> timing loop, or does it has synchronization semantics?
> >
> >
> >Unsynchronized readers are required in Java because it provides no read locks,
> >only write locks. This is probably due to its heritage as a language for
> >embedded machines, which are mostly uniprocessors. On MPs, you need multiple
> >reader/single writer concurrency control.
>
> Unsynchronized readers are not guaranteed to work under the old memory model.
> The fact that they often work is an accident.
> >
> >I won't be able to make OOPSLA and the JMM BOF, but I do have one suggestion:
> >see if you can implement an efficient (concurrent reader) hash table on an MP
> >in whatever models you propose.
>
> Sounds reasonable. But whatever solution we come up with will require
> that readers perform some kind of synchronization operation (either
> locking or reading a volatile variable). Otherwise, it is impossible
> to force the required communication on an SMP.
>
> Another reason why Java should have a weak memory model, and not
> allow unsynchronized reads or unsynchronized sleep loops: Any data
> race detection tool is going to decide that an unsynchronized read,
> or an unsynchronized sleep loop, is a data race. I don't see how a
> tool could not flag them and still flag most errors. The only way
> data race detection tools will be useful is if few, if any,
> recommended idioms get flagged as data races.
>
> Bill
>
> -------------------------------
> JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
>
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:21 EDT