Re: concurrency and starting a synchronized block
On Fri, 2005-02-11 at 16:53 -0800, David Graham wrote: > --- Stephen Colebourne <[EMAIL PROTECTED]> wrote: > > > From: "Torsten Curdt" <[EMAIL PROTECTED]> > > >Regarding the FastHashMap: since the > > use is more or less discouraged ...why > > not deprecate it? > > > > Because it works on everything that its been tried on. > > It's more like no one has ever noticed it breaking. I'm not certain > whether we know it actually works. In fact, it's more like "no-one has ever been sure enough that FashHashMap has broken their app to file a bug report". If an application misbehaves once in a while, it's almost impossible to determine what the cause was, and therefore no bug report would ever get filed. I think FastHashMap should definitely be deprecated if there is a possibility of intermittent failure. Regards, Simon - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
--- Stephen Colebourne <[EMAIL PROTECTED]> wrote: > From: "Torsten Curdt" <[EMAIL PROTECTED]> > >Regarding the FastHashMap: since the > use is more or less discouraged ...why > not deprecate it? > > Because it works on everything that its been tried on. It's more like no one has ever noticed it breaking. I'm not certain whether we know it actually works. > No-ones ever > reported > a bug, its just that with all the double-checked locking theoretical > ideas > we have to be cautious. > > I believe that other parts of commons, including some used by struts, > use > FastHashMap for example. Unfortunately, Commons Validator still uses FastHashMap in some protected instance variables where changing them to Map references might break subclasses. We have deprecated their usage and will be removing them in future releases. David > > Stephen > __ Do you Yahoo!? Yahoo! Mail - Find what you need with new enhanced search. http://info.mail.yahoo.com/mail_250 - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
From: "Torsten Curdt" <[EMAIL PROTECTED]> Regarding the FastHashMap: since the use is more or less discouraged ...why not deprecate it? Because it works on everything that its been tried on. No-ones ever reported a bug, its just that with all the double-checked locking theoretical ideas we have to be cautious. I believe that other parts of commons, including some used by struts, use FastHashMap for example. Stephen - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
Guys, thanks everyone for the useful input! Since this part of the code is really(!) a hotspot I am really careful with any additional overhead. ...but looks like I need to have a closer look into the concurrent package then. Regarding the FastHashMap: since the use is more or less discouraged ...why not deprecate it? ...and I know for commons stuff we want to have as less dependencies as possible ...but since the concurrent package comes with 1.5. What about using the stuff in commons? ...or the backport? ...just some RT. cheers -- Torsten signature.asc Description: OpenPGP digital signature
Re: concurrency and starting a synchronized block
On Thu, 2005-02-10 at 21:59 -0500, WHIRLYCOTT wrote: > There's also the original version here: > > http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html > > What does the backport offer that the original util.concurrent lib > doesn't offer? The JSR process made some minor alterations to the API provided by the original lib, left out a few minor classes, etc. By using the backport, updating to the "real" java.util.concurrent is just a matter of changing the import statements in your code. Coding to Doug's original API means your code isn't quite compatible with the java.util.concurrent implementation provided by java 1.5. The site you reference also implies that performance was improved in some places in the java.util versions. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
There's also the original version here: http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html What does the backport offer that the original util.concurrent lib doesn't offer? phil. Kevin A. Burton wrote: WHIRLYCOTT wrote: I guess this thread should end soon, but while we're still having some fun ... ;) ConcurrentHashMap can do concurrent put() operations and concurrent get() operations... and that's the tricky part. I just love all that stuff that Doug Lea has done. For those who haven't looked at util.concurrent, I recommend it. Sounds like others do as well. I know... its good stuff. I blogged about it: http://www.peerfear.org/rss/permalink/2004/12/19/TheJavaUtilConcurrentPackageAndThreadConcurrency/ All the fun toys that are available ;) Kevin -- Whirlycott Philip Jacob [EMAIL PROTECTED] http://www.whirlycott.com/phil/ - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
WHIRLYCOTT wrote: I guess this thread should end soon, but while we're still having some fun ... ;) ConcurrentHashMap can do concurrent put() operations and concurrent get() operations... and that's the tricky part. I just love all that stuff that Doug Lea has done. For those who haven't looked at util.concurrent, I recommend it. Sounds like others do as well. I know... its good stuff. I blogged about it: http://www.peerfear.org/rss/permalink/2004/12/19/TheJavaUtilConcurrentPackageAndThreadConcurrency/ All the fun toys that are available ;) Kevin -- Use Rojo (RSS/Atom aggregator). Visit http://rojo.com. Ask me for an invite! Also see irc.freenode.net #rojo if you want to chat. Rojo is Hiring! - http://www.rojonetworks.com/JobsAtRojo.html If you're interested in RSS, Weblogs, Social Networking, etc... then you should work for Rojo! If you recommend someone and we hire them you'll get a free iPod! Kevin A. Burton, Location - San Francisco, CA AIM/YIM - sfburtonator, Web - http://peerfear.org/ GPG fingerprint: 5FB2 F3E2 760E 70A8 6174 D393 E84D 8D04 99F1 4412 - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
I guess this thread should end soon, but while we're still having some fun ... ;) ConcurrentHashMap can do concurrent put() operations and concurrent get() operations... and that's the tricky part. I just love all that stuff that Doug Lea has done. For those who haven't looked at util.concurrent, I recommend it. Sounds like others do as well. phil. Kevin A. Burton wrote: Torsten Curdt wrote: Guys, forgive me if this too off topic... ...but I thought it is somehow related to collections that's why I am bringing it up here anyway. I bet someone of you will know Ignore what everyone else says on this list topic. ha. Use a ReentrantReadWriteLock from JDK 1.5. There's a backport to JDK 1.4 out on the net. Google for "backport concurrent oswego" or something Then you can do a lock.readLock().lock() on our gets and then do a writeLock on your puts. the writeLock will backup the readlock but if you only have readlocks they can all happen at once. Normally though its not too big a deal since gets() on a hashtable are O(1) Kevin -- Whirlycott Philip Jacob [EMAIL PROTECTED] http://www.whirlycott.com/phil/ - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
Torsten Curdt wrote: Guys, forgive me if this too off topic... ...but I thought it is somehow related to collections that's why I am bringing it up here anyway. I bet someone of you will know Ignore what everyone else says on this list topic. ha. Use a ReentrantReadWriteLock from JDK 1.5. There's a backport to JDK 1.4 out on the net. Google for "backport concurrent oswego" or something Then you can do a lock.readLock().lock() on our gets and then do a writeLock on your puts. the writeLock will backup the readlock but if you only have readlocks they can all happen at once. Normally though its not too big a deal since gets() on a hashtable are O(1) Kevin -- Use Rojo (RSS/Atom aggregator). Visit http://rojo.com. Ask me for an invite! Also see irc.freenode.net #rojo if you want to chat. Rojo is Hiring! - http://www.rojonetworks.com/JobsAtRojo.html If you're interested in RSS, Weblogs, Social Networking, etc... then you should work for Rojo! If you recommend someone and we hire them you'll get a free iPod! Kevin A. Burton, Location - San Francisco, CA AIM/YIM - sfburtonator, Web - http://peerfear.org/ GPG fingerprint: 5FB2 F3E2 760E 70A8 6174 D393 E84D 8D04 99F1 4412 - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
[collections] provides two Map implementations of interest in this discussion: FastHashMap - this map copies the whole map internally every timeput is called. This avoids most of the synchronization issues, and gets are not synchronized. However, we do not recommend its use because it _may_ not work on some JVMs (no example of a failure has ever been reported, but...) StaticBucketMap - this map synchronizes at a very fine grained level (each bucket). In theory this should mean that the map still works in very very multi threaded programs. However, bulk operations like putAll don't work as expected, and in general its slower than a normal HashMap. My recommendation is to just synchronize synchronized(map) { Object o = map.get(key); if (o == null) { map.put(key,new Object()); } } It is very unlikely that this is your performance bottleneck. PS. I believe JDK 1.5 has an implementation of Doug Leas special concurrent hash map Stephen From: "David Graham" <[EMAIL PROTECTED]> FastHashMap states it is not portable in its javadoc so it should never be used. Using non-portable classes defeats the entire purpose of using Java. - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
Exactly - most books and documentation about resource exclusion about this make it abundantly clear that synchronized methods shouldn't call each other for this very reason. Thanks for adding that point. phil. Oliver Zeigermann wrote: On Thu, 10 Feb 2005 13:09:14 -0500, WHIRLYCOTT <[EMAIL PROTECTED]> wrote: 2) synchronize on the containing object's monitor: ... public synchronized whatever(Object arg1) {...} public synchronized something() {...} ... Blindly doing this can easily lead to deadlocks. Consider thread #1 in method whatever accesses another synchronized object and needs to wait for thread #2 to release the lock on it. Now thread #2 tries to access method something and - of course - needs to wait for thread #1 to release the lock on that first objec. Now both threads mutually wait for each other and you have a deadlock. Oliver - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED] -- Whirlycott Philip Jacob [EMAIL PROTECTED] http://www.whirlycott.com/phil/ - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
On Thu, 10 Feb 2005 13:09:14 -0500, WHIRLYCOTT <[EMAIL PROTECTED]> wrote: > 2) synchronize on the containing object's monitor: > > ... > public synchronized whatever(Object arg1) {...} > public synchronized something() {...} > ... > Blindly doing this can easily lead to deadlocks. Consider thread #1 in method whatever accesses another synchronized object and needs to wait for thread #2 to release the lock on it. Now thread #2 tries to access method something and - of course - needs to wait for thread #1 to release the lock on that first objec. Now both threads mutually wait for each other and you have a deadlock. Oliver - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
I spent a whole bunch of time looking into how various caches/collections handled this issue when I was designing Whirlycache [1] and the cleanest solution that is available today, as others have pointed out, is Doug Lea's util.concurrent package. The high-level explanation of how Doug Lea's ConcurrentHashMap works is that it has 32 internal buckets and a fast hashing algorithm. It only synchronizes internally on the bucket that is being modified, thereby leaving the other n buckets free to do whatever they need. So you can conceivably have 32 concurrent threads reading and/or writing depending on how the hashing algorithm causes the buckets to be synchronized. It's a lot faster than a java.util.HashMap when you have many threads reading and writing. I think the 32 fixed bucket size limit was removed when these classes were ported to JDK 1.5. Depending on what you are doing, you basically have 3 choices when you're dealing with multithreaded access/modification to a collection: 1) don't synchronize and watch failures happen 2) synchronize on the containing object's monitor: ... public synchronized whatever(Object arg1) {...} public synchronized something() {...} ... 3) use more granular synch locks, if possible: ... private Object whatever = new Object(); private Object something = new Object(); public whatever(Object arg1) { synchronized (whatever) { ... } } public something(Object arg1) { synchronized (something) { ... } } Making the locks more granular can make a huge difference, but it's only possible if your particular case will allow for it. But it's definitely worth investigating rather than blindly using 'synchronized' in method signatures... which turns out to be not-that-slow anyway. YMMV. phil. [1] http://whirlycache.dev.java.net/ Torsten Curdt wrote: Guys, forgive me if this too off topic... ...but I thought it is somehow related to collections that's why I am bringing it up here anyway. I bet someone of you will know Consider this code... Object o = map.get(key); if (o == null) { synchronized(map) { map.put(key,new Object()); } } 99% of the time the "get"s on the map are going to return an object. That's why I would like to avoid synchronizing the "get" access. Now since a "put" might corrupt the data it has to be synchronized. Since the "get", the comparison and the "put" are not in a synchronized block I might loose objects ...but for this particular usecase that's ok. Now what really got me thinking is the concurrent sychronized and non-synchronized access. What happens when Thread A is in doing a "get" while Thread B is entering the sychronized block for the "put"? I assume that since the map object is not locked it will go straight into the "put" and bang ...right? Somehow this looks like the optimal usecase for the FastHashMap from collections ...but since this code needs to be very portable this might be a problem because of the double-checked locking idiom. Another option would be using the StaticBucketMap. What do you guys think? If you consider this too OT please reply off list. cheers -- Torsten -- Whirlycott Philip Jacob [EMAIL PROTECTED] http://www.whirlycott.com/phil/ - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
This is the save and obvious solution - I agree. But I thought Torsten wanted something less restrictive where there could be any number of concurrent reads, but only a single write that also does not allow for any concurrent reads. This is exactly what a read/write lock does and is available from Doug Lea's package. Oliver P.S.: It is also avaliable from commons transaction, but if you only want a read/write lock Doug's stuff for sure is more suitable. On Thu, 10 Feb 2005 06:33:04 -0800 (PST), David Graham <[EMAIL PROTECTED]> wrote: > A call to Map.get() may depend on state that can be corrupted by a > concurrent call to Map.put(). You don't know without learning the > implementation details of get(). So, you need to synchronize around both > operations: > > synchronized(map) { > Object o = map.get(key); > if (o == null) { > map.put(key,new Object()); > } > } > > Have you identified this one synchronized block as a bottleneck in your > application with performance testing? If not, then why are you worrying > about making micro optimizations that may or may not benefit the > application? > > FastHashMap states it is not portable in its javadoc so it should never be > used. Using non-portable classes defeats the entire purpose of using > Java. > > David > > --- Torsten Curdt <[EMAIL PROTECTED]> wrote: > > > Guys, forgive me if this too off topic... > > > > ...but I thought it is somehow related to > > collections that's why I am bringing it up > > here anyway. I bet someone of you will know > > > > Consider this code... > > > > Object o = map.get(key); > > if (o == null) { > > synchronized(map) { > > map.put(key,new Object()); > > } > > } > > > > 99% of the time the "get"s on the map are going > > to return an object. That's why I would like > > to avoid synchronizing the "get" access. > > Now since a "put" might corrupt the data it > > has to be synchronized. > > > > Since the "get", the comparison and the "put" > > are not in a synchronized block I might loose > > objects ...but for this particular usecase > > that's ok. > > > > Now what really got me thinking is the > > concurrent sychronized and non-synchronized > > access. > > > > What happens when Thread A is in doing a > > "get" while Thread B is entering the > > sychronized block for the "put"? > > > > I assume that since the map object is not > > locked it will go straight into the "put" > > and bang ...right? > > > > Somehow this looks like the optimal usecase > > for the FastHashMap from collections ...but > > since this code needs to be very portable > > this might be a problem because of the > > double-checked locking idiom. > > > > Another option would be using the StaticBucketMap. > > > > What do you guys think? > > > > If you consider this too OT please reply off list. > > > > cheers > > -- > > Torsten > > > > > ATTACHMENT part 2 application/pgp-signature name=signature.asc > > > __ > Do you Yahoo!? > The all-new My Yahoo! - Get yours free! > http://my.yahoo.com > > > - > To unsubscribe, e-mail: [EMAIL PROTECTED] > For additional commands, e-mail: [EMAIL PROTECTED] > > - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
A call to Map.get() may depend on state that can be corrupted by a concurrent call to Map.put(). You don't know without learning the implementation details of get(). So, you need to synchronize around both operations: synchronized(map) { Object o = map.get(key); if (o == null) { map.put(key,new Object()); } } Have you identified this one synchronized block as a bottleneck in your application with performance testing? If not, then why are you worrying about making micro optimizations that may or may not benefit the application? FastHashMap states it is not portable in its javadoc so it should never be used. Using non-portable classes defeats the entire purpose of using Java. David --- Torsten Curdt <[EMAIL PROTECTED]> wrote: > Guys, forgive me if this too off topic... > > ...but I thought it is somehow related to > collections that's why I am bringing it up > here anyway. I bet someone of you will know > > Consider this code... > > Object o = map.get(key); > if (o == null) { > synchronized(map) { > map.put(key,new Object()); > } > } > > 99% of the time the "get"s on the map are going > to return an object. That's why I would like > to avoid synchronizing the "get" access. > Now since a "put" might corrupt the data it > has to be synchronized. > > Since the "get", the comparison and the "put" > are not in a synchronized block I might loose > objects ...but for this particular usecase > that's ok. > > Now what really got me thinking is the > concurrent sychronized and non-synchronized > access. > > What happens when Thread A is in doing a > "get" while Thread B is entering the > sychronized block for the "put"? > > I assume that since the map object is not > locked it will go straight into the "put" > and bang ...right? > > Somehow this looks like the optimal usecase > for the FastHashMap from collections ...but > since this code needs to be very portable > this might be a problem because of the > double-checked locking idiom. > > Another option would be using the StaticBucketMap. > > What do you guys think? > > If you consider this too OT please reply off list. > > cheers > -- > Torsten > > ATTACHMENT part 2 application/pgp-signature name=signature.asc __ Do you Yahoo!? The all-new My Yahoo! - Get yours free! http://my.yahoo.com - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
Consider this code... Object o = map.get(key); if (o == null) { synchronized(map) { map.put(key,new Object()); } } 99% of the time the "get"s on the map are going to return an object. That's why I would like to avoid synchronizing the "get" access. Now since a "put" might corrupt the data it has to be synchronized. then get() twice: since 99% of the time it will not enter the block, the second lookup does not matter ... that's true ...but that's not the problem :) as I said: I don't mind if I loose an instance but the problem is that the "get" is not synchronized while the "put" is. So I asssume that the "get" is not checking for a lock on the "map" object which means that a concurrent "get" and "put" might clash. The above code would only be safe for two concurrent "put" calls. ...at least that's what I assume cheers -- Torsten signature.asc Description: OpenPGP digital signature
RE: concurrency and starting a synchronized block
On Thu, 2005-02-10 at 14:20 +0100, Jörg Schaible wrote: > Torsten Curdt wrote on Thursday, February 10, 2005 2:07 PM: > > > Guys, forgive me if this too off topic... I think this list is a perfectly good place to ask this sort of thing.. > > > > ...but I thought it is somehow related to > > collections that's why I am bringing it up > > here anyway. I bet someone of you will know > > > > Consider this code... > > > > Object o = map.get(key); > > if (o == null) { > > synchronized(map) { > > map.put(key,new Object()); > > } > > } > > > > 99% of the time the "get"s on the map are going > > to return an object. That's why I would like > > to avoid synchronizing the "get" access. > > Now since a "put" might corrupt the data it > > has to be synchronized. > > then get() twice: > > Object o = map.get(key); > if (o == null) { > synchronized(map) { > o = map.get(key); > if (o == null) { > map.put(key,new Object()); > } > } > } > > since 99% of the time it will not enter the block, the second lookup does not > matter ... > > Regards, > Jörg Well, I personally would be very reluctant to adopt this kind of solution. Firstly, I believe that if you never synchronise on the get, then there is no guarantee the reading thread will ever see data put into the map by other threads. Having a synchronize around the get forces the cpu to synchronise its cache or some-such. And secondly, I believe there are many other traps out there for code that tries to play tricks with synchronization. Synchronisation is a fiendishly difficult subject, involving CPU cache coherence mechanisms, etc., and there are many traps to fall into. Many of these are described in the articles about why "double checked locking" is broken. I think someone mentioned just a week or two ago on this list that Doug Lea's concurrency library is available under a BSD-ish license. If that's the case, I would look there for a fast hashmap implementation first... Cheers, Simon - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: concurrency and starting a synchronized block
On Feb 10, 2005, at 8:20 AM, Jörg Schaible wrote: en get() twice: Object o = map.get(key); if (o == null) { synchronized(map) { o = map.get(key); if (o == null) { map.put(key,new Object()); } } } since 99% of the time it will not enter the block, the second lookup does not matter ... Is that still enough to not be double-checked locking (which is broken in java..) http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html -pete - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
RE: concurrency and starting a synchronized block
Torsten Curdt wrote on Thursday, February 10, 2005 2:07 PM: > Guys, forgive me if this too off topic... > > ...but I thought it is somehow related to > collections that's why I am bringing it up > here anyway. I bet someone of you will know > > Consider this code... > > Object o = map.get(key); > if (o == null) { > synchronized(map) { > map.put(key,new Object()); > } > } > > 99% of the time the "get"s on the map are going > to return an object. That's why I would like > to avoid synchronizing the "get" access. > Now since a "put" might corrupt the data it > has to be synchronized. then get() twice: Object o = map.get(key); if (o == null) { synchronized(map) { o = map.get(key); if (o == null) { map.put(key,new Object()); } } } since 99% of the time it will not enter the block, the second lookup does not matter ... Regards, Jörg - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]