[concurrency-interest] Tree{Map,Set}

Yechiel Feffer yechielf at gigaspaces.com
Tue Apr 5 05:46:48 EDT 2005

As I understand, jsr166x is an extention of jsr166. Where can I find jsr166x
docs ? 


-----Original Message-----
From: concurrency-interest-bounces at cs.oswego.edu
[mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of Doug Lea
Sent: Thursday, March 31, 2005 19:40
To: Kevin Bourrillion
Cc: concurrency-interest at altair.cs.oswego.edu
Subject: Re: [concurrency-interest] Tree{Map,Set}

Kevin Bourrillion wrote:
> Hi,
> I heard a rumor that in Mustang, TreeMap and TreeSet will be
> retrofitted to implement the fabulous new Navigable interfaces.

Yes. These should appear in Mustang builds reasonably soon for
those of you getting the early access snapshots. 

> If so, is it possible to include jsr166x.TreeMap/Set in jsr166x.jar so
> that we might start using them?

Probably. I'll check. (The integrated versions of our updated
java.util.Tree*, have Sun headers. It ought to be possible to get
Sun permission to distribute in jsr166x, although those of you
concerned about purity might not like the re-introduction of
mixed-license jars for jsr166x.)

> On the other hand: for a caller who needs just a general-purpose,
> non-concurrent, sorted set or map, would it be a bad idea for them to
> use ConcurrentSkipList*?  If it's not appreciably slower in this case,
> perhaps for our purposes we can just forget about Tree*?

It depends on what you mean by "appreciably".

If most of your uses are methods put() and get() and their variants,
and map sizes are not huge, you might not notice any difference.
In many these cases, ConcurrentSkipLists are often even slightly faster.

If you do a lot of deletions, Trees will be noticeably faster because
the deletion algorithm in concurrent skip lists has much more overhead
than redblack tree deletion.

If you mostly have very large maps (say, 100K+ elements), Trees will
be noticeably faster because of the algorithmic asymptotics -- as n
increases, redblack trees perform around log2(n) comparisons per get()
vs around 2*log2(n) for skip lists.

Concurrency-interest mailing list
Concurrency-interest at altair.cs.oswego.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20050405/76d7902e/attachment.htm

More information about the Concurrency-interest mailing list