Return-Path: Delivered-To: apmail-jakarta-commons-dev-archive@apache.org Received: (qmail 3199 invoked from network); 15 Aug 2002 19:05:36 -0000 Received: from unknown (HELO nagoya.betaversion.org) (192.18.49.131) by daedalus.apache.org with SMTP; 15 Aug 2002 19:05:36 -0000 Received: (qmail 13465 invoked by uid 97); 15 Aug 2002 19:06:00 -0000 Delivered-To: qmlist-jakarta-archive-commons-dev@jakarta.apache.org Received: (qmail 13326 invoked by uid 97); 15 Aug 2002 19:05:59 -0000 Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm Precedence: bulk List-Unsubscribe: List-Subscribe: List-Help: List-Post: List-Id: "Jakarta Commons Developers List" Reply-To: "Jakarta Commons Developers List" Delivered-To: mailing list commons-dev@jakarta.apache.org Received: (qmail 13283 invoked by uid 98); 15 Aug 2002 19:05:57 -0000 X-Antivirus: nagoya (v4198 created Apr 24 2002) Reply-To: From: "Berin Loritsch" To: "'Jakarta Commons Developers List'" Subject: RE: [Collections] StaticBucketMap integration Date: Thu, 15 Aug 2002 15:05:20 -0400 Message-ID: <000001c2448e$b3826ff0$ac00a8c0@Gabriel> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 Importance: Normal In-Reply-To: X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N Sounds good to me. I trust your judgement > -----Original Message----- > From: Jack, Paul [mailto:pjack@sfaf.org] > Sent: Wednesday, August 14, 2002 11:30 PM > To: 'Jakarta Commons Developers List' > Subject: RE: [Collections] StaticBucketMap integration > > > Ok, I checked in a new version of StaticBucketMap with the > size() improvement described below, plus collection views > that are backed by the map. I decided to deal with > iterator/bulk operation atomicity issues by ignoring them. > I think that's healthy. :) > > Also, there's a bizarre new atomic(Runnable) method that > can be used if you really need atomic operations... > > Let me know what you think. > > -Paul > > > > -----Original Message----- > > From: Jack, Paul [mailto:pjack@sfaf.org] > > Sent: Wednesday, August 14, 2002 5:41 PM > > To: 'Jakarta Commons Developers List' > > Subject: RE: [Collections] StaticBucketMap integration > > > > > > > I got you. > > > > > > I'm actually surprised that incrementing an int is not > atomic. Is > > > there any way to make it atomic? Or is that a problem with the > > > compiler? > > > > Well, I guess it's a problem with the Java Virtual Machine. > There's no > > way in Java bytecode to update a field in-place; you ALWAYS have to > > copy it to the local stack first, modify the local stack, > then write > > the new value to the field. > > > > Which in the present case is quite annoying. :) > > > > I have an idea here, though. What if we keep the separate m_locks > > array, but instead of using vanilla Objects, use this class: > > > > private Lock[] m_locks; > > > > private static class Lock { > > public int size; > > } > > > > Eg, each Lock instance, in addition to being the lock for > > a bucket, also keeps count of the number of mappings in that > > bucket. Then size() is somewhat faster: > > > > public int size() { > > int r = 0; > > for (int i = 0; i < m_buckets.length; i++) { > > r += m_locks[i].size; > > } > > } > > > > Happily, since the fetch of m_locks[i].size field IS > atomic, we don't > > need any synchronized blocks! There's still a loop but no monitor > > contention. > > > > -Paul > > > > > > > > > -----Original Message----- > > > > From: Jack, Paul [mailto:pjack@sfaf.org] > > > > Sent: Wednesday, August 14, 2002 6:40 PM > > > > To: 'commons-dev@jakarta.apache.org' > > > > Subject: [Collections] StaticBucketMap integration > > > > > > > > > > > > Avalon has made changes to StaticBucketMap since it was > > > > ported over to commons. The changes include: > > > > > > > > 1. Elimination of a separate array for monitors. Instead, > > > > the first (always empty) node in the bucket array is used as > > > > the monitor for that bucket. > > > > > > > > 2. Addition of a new volatile field that tracks the size > > > of the map. > > > > > > > > #1 should be easy enough to merge in. However, #2 is broken. > > > > Although Java guarantees atomic reads/writes of volatile int > > > > fields, the following single line of code: > > > > > > > > size++ > > > > > > > > actually represents three operations: > > > > > > > > > > > > > > > > > > > > > > > > Taken as a whole, size++ is not atomic. The executing thread > > > > can be preempted at any time after one of those three steps. > > > > If Thread A and Thread B are both executing BucketMap.put() > > > > and get to size++, > > > > the following can happen: > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > In this case, the size field would only be incremented by 1 > > > > even though two threads added something new to the map. > > > > > > > > So it's broken. Unfortunately I think we're stuck with the > > > > long tedious way of calculating the size each time it's > requested. > > > > > > > > (Please tell me somebody from Avalon is reading this so I > > > > don't have to cross-post...Berin? Anyone?) > > > > > > > > -Paul > > > > > > > > > > > > -- > > > > To unsubscribe, e-mail: > > > > unsubscribe@jakarta.apache.org> > > > > For > > > > additional commands, > > > > e-mail: > > > > > > > > > > > > > -- > > > To unsubscribe, e-mail: > > > > > > For additional commands, e-mail: > > > > > > > > > > -- > > To unsubscribe, e-mail: > > For additional commands, e-mail: > help@jakarta.apache.org> > > -- > To > unsubscribe, e-mail: > > For additional commands, e-mail: > help@jakarta.apache.org> > -- To unsubscribe, e-mail: For additional commands, e-mail: