[concurrency-interest] RFC -- Java7 java.util.concurrent plans

Roman Elizarov elizarov at devexperts.com
Thu Dec 11 02:30:58 EST 2008


Hello Doug!

On Wednesday, December 10, 2008 11:17:35 PM you wrote:

DL> Thanks for the reminder! As a follow-on about some fence
DL> issues, I had put together  AtomicReferenceArrayUpdater:
DL> http://gee.cs.oswego.edu/dl/jsr166/dist/docs/java/util/concurrent/atomic/AtomicReferenceArrayUpdater.html
DL> Would this suffice? The same could be done for at least
DL> Int and Long versions.

Reference, Int and Long versions should suffice. The API looks
somewhat superfluous, though:

* eagerGet and lazySet are simple wrappers on plain array access and
  their presense in API, IMHO, is just confusing.
* Constuructors for this classes should not be exposed at all. I would
  prefer a singleton pattern with a static generic "getInstance" method.
  Not only this is cleaner (each user does not define its own
  instance), but it also integrates with Java generic type inference.

Now, I belive that core libraries need more efficient ready-to-use
array based algorithms. Due to better memory locality and cache
utilization array-based algorithms typically outpeform linked
structures by a significant factor on all modern arhitectures. I know
that research is somewhat lagging there, especially into the
dynamically sized councurrent array-based structures. But even simple
optimizations to the existing structures can have huge benefit. For
example, many linked data strucutures get an immediate performance
boost when you unroll them.

One of my students recently studied a combination of Michael&Scott
concurrent queue (the underlying algorithm for ConcurrentLinkedQueue)
and unrolled list. While still fully lock-free, it significantly
outperforms ConcurentLinkedQueue on addition, removal and iteration.
We don't currently have access to migh-multi-core machines, so I
cannot relly comment on its scalability under high contetion vs
existing ConcurrentLinkedQueue implementation.

Btw, the implementation of ConcurrentLinkedQueue (being based of
Michael&Scott paper) implements their algorithm almost "verbatim".
Original M&S paper assumed that the memory is being managed by the
code itself, while in Java this is done by GC. The obvious benefit of
having no ABA problem is already being used by ConcurrentLinkedQueue.
However, there are some other checks in M&S code that are superflous
in the presence of GC (they were incuded into M&S code only because
they had to make sure that the memory they are attempting to modify
was not already reclaimed by the other thread). Thus,
ConcurrentLinkedQueue can be slighltly sped up simply by removing
those superfluous checks. Speedup can be significant on some
architectures, since it reduces the number of volatile reads per
operation.

Sincerely,
Roman Elizarov

P.S. I've noticed AtomicReferencePair class. What use does it have if
it does not provide any methods for atomic snapshot or atomic update
of both references at the same time?




More information about the Concurrency-interest mailing list