Monday, February 27, 2006

Why a ConcurrentHashMap is so fast

We all know a ConcurrentHashMap is nearly as fast as a HashMap plus provided concurrency like a Hashtable. Some very ingenious coding has made this possible. To understand the hows and whys the key is the structure of the ConcurrentHashMap itself.

A ConcurrentHashMap contains a final array of Segment objects. Each segment extends ReentrantLock, and contains a transient volatile array of HashEntry objects. Each HashEntry object is made of final key, hash and next variables and a volatile content variable.

Every get/put/remove/add operation involves creating an index from the hashkey that maps to one of the available segment objects. The call is then delegated to the obtained segment instance.

Let take put call. The segment first locks itself (since extends from ReentrantLock). Then proceeds to check if the hashkey already exists, if it does, it updates the value of the volatile value field in the HashEntry object. Since it is a volatile variable, the new value is guaranteed to be seen by other threads in the jvm without any explicit need for synchronization. Voila ! Now if the key is not present then a new HashEntry object is created and added to the head of the existing list. Since there are an array of Segments, the writes can be spread and not all threads might lock on the same segment leading to more concurrent writes.

Consider a get call. Get the first HashEntry and iterator till the end and if found return the value. No locking at all. Same as a HashMap but unlike a Hashtable. So all reads work at nearly same speed as HashMap.

There are 2 things that make this possible

1) The new JMM guarantees that Volatile reads are not re-ordered with volatile writes and all reads after a write will get the updated contents without synchronization. Variable that holds value reference in HashEntry is volatile. Plus the whole HashEntry array in each segment is volatile. So any changes to value or every newly added HashEntry object(or key-value pair) is visible to all threads after they are assigned without any syncronization.


2) Final fields initialization safety, all threads will see the values for its final fields that were set in its constructor.Further, any variables that can be reached through a final field of a properly constructed object, such as fields of an object referenced by a final field, are also guaranteed to be visible to other threads as well. So if a new key-value pair is added and is instantly accessed by another thread the key, hashkey and next pointer will have proper values and never null.


These ensure that any add in any thread instantly reflects in other threads, without any flushing of memory. Does this mean no locking at all ? None in the java code but the jvm implementation will have to do some locking to ensure that volatile variable reads return latest written values. Since its a very lower level it should be more faster.

Never seen an API that uses the features of the JMM to this extent. Hats off to Doug Lea who made this all possible.

Subscribe to comments for this post

2 comments:

Anonymous said...

[u][b]Xrumer[/b][/u]

[b]Xrumer SEO Professionals

As Xrumer experts, we have been using [url=http://www.xrumer-seo.com]Xrumer[/url] quest of a large leisure for the time being and grasp how to harness the colossal power of Xrumer and adapt it into a Banknotes machine.

We also provender the cheapest prices on the market. Assorted competitors see fit order 2x or consistent 3x and a a pile of the term 5x what we pervade you. But we have faith in providing gigantic help at a low affordable rate. The unbroken direct attention to of purchasing Xrumer blasts is because it is a cheaper variant to buying Xrumer. So we aim to support that mental activity in recollection and outfit you with the cheapest censure possible.

Not simply do we take the most successfully prices but our turnaround time payment your Xrumer posting is wonderful fast. We drive take your posting done to come you certain it.

We also outfit you with a sated log of successful posts on different forums. So that you can notice seeking yourself the power of Xrumer and how we get harnessed it to help your site.[/b]


[b]Search Engine Optimization

Using Xrumer you can expect to apprehend thousands upon thousands of backlinks exchange for your site. Many of the forums that your Location you intent be posted on have great PageRank. Having your join on these sites can deep down mitigate strengthen up some top rank recoil from links and as a matter of fact aid your Alexa Rating and Google PageRank rating utterly the roof.

This is making your put more and more popular. And with this better in popularity as superbly as PageRank you can keep in view to appreciate your area definitely superiority high-pitched in those Search Motor Results.
Above

The amount of traffic that can be obtained by harnessing the power of Xrumer is enormous. You are publishing your situation to tens of thousands of forums. With our higher packages you may still be publishing your position to HUNDREDS of THOUSANDS of forums. Imagine 1 collection on a popular forum disposition inveterately get 1000 or so views, with communicate 100 of those people visiting your site. At once create tens of thousands of posts on fashionable forums all getting 1000 views each. Your see trade liking go because of the roof.

These are all targeted visitors that are interested or curious nearly your site. Imagine how innumerable sales or leads you can execute with this titanic gang of targeted visitors. You are truly stumbling upon a goldmine bright to be picked and profited from.

Retain, Above is Money.
[/b]

GET YOUR INFERIOR ERUPTION TODAY:


http://www.xrumer-seo.com

Anonymous said...

Predilection casinos? sift this unsophisticated [url=http://www.realcazinoz.com]casino[/url] circumvent and wing it denigrate online casino games like slots, blackjack, roulette, baccarat and more at www.realcazinoz.com .
you can also put an end our untrained [url=http://freecasinogames2010.webs.com]casino[/url] orientate at http://freecasinogames2010.webs.com and be given curb of valid folding deviation !
another blowhard [url=http://www.ttittancasino.com]casino spiele[/url] sight is www.ttittancasino.com , pro german gamblers, organization manumitted online casino bonus.

 
Clicky Web Analytics