ConcurrentLinkedQueue question

[Joe Seigh]

Does anyone know if the implementation of ConcurrentLinkedQueue uses
version numbering per the original Michael and Scott algorithm to
safely recycle nodes or are using GC to collect dequeued nodes? I'm
referring to the internal nodes, not the returned dequeued values.
If so, did anyone ever run performance measurements to confirm this?
This may have been part of the JSR-166 rationale but since you'd have
to implement it first before you could even try it, they may have
decided leaving it in wouldn't hurt things.

 

[Robert Klemme]

Does anyone know if the implementation of ConcurrentLinkedQueue uses
version numbering per the original Michael and Scott algorithm to
safely recycle nodes or are using GC to collect dequeued nodes? I'm
referring to the internal nodes, not the returned dequeued values.
If so, did anyone ever run performance measurements to confirm this?
This may have been part of the JSR-166 rationale but since you'd have
to implement it first before you could even try it, they may have
decided leaving it in wouldn't hurt things.

You can look up the implementation in sources.jar provided you have the
JDK installed (easy with Eclipse for example, just browse to the class).
My guess is that they do not recycle but let GC do its work.

Kind regards

robert

 

[Tom Hawtin]

You can look up the implementation in sources.jar provided you have the

^^^^^^^^^^^src.zip

JDK installed (easy with Eclipse for example, just browse to the class).

Or you can go to the original sources at Doug Lea's site (it's under the
creative commons license).

http://g.oswego.edu/cgi-bin/viewcvs...va/util/concurrent/ConcurrentLinkedQueue.java

Tom Hawtin

 

[Joe Seigh]

Or you can go to the original sources at Doug Lea's site (it's under the
creative commons license).

http://g.oswego.edu/cgi-bin/viewcvs...va/util/concurrent/ConcurrentLinkedQueue.java

Ok, thanks. That saved having to install the source. It looks like they
use GC to avoid the ABA problem. Interesting. All this time I was thinking
they were using versioning to avoid thrashing the GC on high throughput queues.

 

[Chris Uppal]

Ok, thanks. That saved having to install the source.

Just curious: is there a reason why you want to avoid having the source
available ?

-- chris

 

[Joe Seigh]

Joe Seigh wrote:




Just curious: is there a reason why you want to avoid having the source
available ?

I'm not currently working with Java, though I will be in the near future,
so I don't have the source around and didn't know off hand how easy it
was to get a hold of. There'd be a license involved and in the past Sun
usually wanted you to register to get that kind of stuff. Actually I
did download the source and checked to see if the license was problematic.
There's a "no taint" clause which is good. Unfortunately, the Java on
my windows box is a bit back dated and doesn't understand the newer
jar formats, ie. it can't execute a jar file the way the README file
wants. So it's download a newer Java SDK or try it out on one of
linux boxes which has a more recent version of Java. Fortunately
there was some source online.

The background on this was a question on c.p.t on whether implementing
the Michael and Scott algorithm in C# using GC to avoid the ABA
problem was as efficient as Java's. Apparently it is. Which
kind of obviates the 2 different ways I figured out how to avoid
using GC for node recycling when you don't have AtomicStampedReference.
The is for unbounded queues. The original Michael and Scott algorithm
is either bounded or expandable only (you can't shrink the node pool).

I'll probably have to go on the concurrency-interest mailing list
sometime and ask them why they thought node recycling wouldn't
be needed. They may have discussed it before but the archive
isn't searchable as far as I can tell.

 

[Mike Schilling]

I'm not currently working with Java, though I will be in the near future,
so I don't have the source around and didn't know off hand how easy it
was to get a hold of.

Very. When you download a JRE, a jar of source files comes with it.

 

[Daniel Pitts]

Very. When you download a JRE, a jar of source files comes with it.

Actually, when you download the JDK, a the J2SE Java source files come
with it.

 

[Mike Schilling]

Actually, when you download the JDK, a the J2SE Java source files come
with it.

Yes, thank you. The JRE and JDK are different things, and the source jar is
part of the JDK only.

 

[Robert Klemme]

The background on this was a question on c.p.t on whether implementing
the Michael and Scott algorithm in C# using GC to avoid the ABA
problem was as efficient as Java's. Apparently it is. Which
kind of obviates the 2 different ways I figured out how to avoid
using GC for node recycling when you don't have AtomicStampedReference.
The is for unbounded queues. The original Michael and Scott algorithm
is either bounded or expandable only (you can't shrink the node pool).

If you are looking for how GC works in current JVM's and why it is so
fast you can have a look here:

http://www-128.ibm.com/developerworks/library/j-jtp01274.html

There is a bit more background on history and evolution here

http://www-128.ibm.com/developerworks/java/library/j-jtp10283/

And if you want to play with options here's another interesting article:

http://www-128.ibm.com/developerworks/ibm/library/i-gctroub/

Regards

robert


PS: Tom, thanks for correcting the source file name, I didn't have a JDK
handy on the machine I posted the other day.

 

[Joe Seigh]

If you are looking for how GC works in current JVM's and why it is so
fast you can have a look here:

http://www-128.ibm.com/developerworks/library/j-jtp01274.html

I knew some of that already. I agree that the Java GC sucks much
less than it used to. I suspect that I'm going to have to code
up alternate implementations implementations and run performance
tests myself. There are some other issues raised as well. I'm
going to take this offline. c.l.j.p probably isn't the appropiate
place to raise java design and rationale issues.

 

[Robert Klemme]

I knew some of that already. I agree that the Java GC sucks much
less than it used to. I suspect that I'm going to have to code
up alternate implementations implementations and run performance
tests myself. There are some other issues raised as well. I'm
going to take this offline. c.l.j.p probably isn't the appropiate
place to raise java design and rationale issues.

My 0.02 EUR, since this all seems pretty theoretical at the moment,
create your application using library classes, profile and optimize then
if and only *if* there is an issue. Creating your own test cases is not
the same as profiling the application exactly because the JVM is a
highly complex beast nowadays and it likely behaves different with
artificial test cases than with the real thing.

Regards

robert