commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Berin Loritsch" <blorit...@apache.org>
Subject RE: [Collections] StaticBucketMap integration
Date Thu, 15 Aug 2002 19:05:20 GMT
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:
> > > > 
> > > >    <fetch value of field, push onto thread local stack>
> > > >    <increment the top int on the thread local stack>
> > > >    <pop top value of stack, write back to field>
> > > > 
> > > > 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:
> > > > 
> > > >    <A: fetch value>
> > > >    <B: fetch value>
> > > >    <A: increment thread local top>
> > > >    <B: increment thread local top>
> > > >    <A: write value>
> > > >    <B: write value>
> > > > 
> > > > 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:   
> > > > <mailto:commons-dev-> unsubscribe@jakarta.apache.org>
> > > > For
> > > > additional commands, 
> > > > e-mail: <mailto:commons-dev-help@jakarta.apache.org>
> > > > 
> > > 
> > > 
> > > --
> > > To unsubscribe, e-mail:   
> > > <mailto:commons-dev-unsubscribe@jakarta.apache.org>
> > > For additional commands, e-mail:
> > > <mailto:commons-dev-help@jakarta.apache.org>
> > > 
> > 
> > --
> > To unsubscribe, e-mail:   
> <mailto:commons-dev-unsubscribe@jakarta.apache.org>
> For additional commands, e-mail: 
> <mailto:commons-dev-> help@jakarta.apache.org>
> 
> --
> To 
> unsubscribe, e-mail:   
> <mailto:commons-dev-unsubscribe@jakarta.apache.org>
> For additional commands, e-mail: 
> <mailto:commons-dev-> help@jakarta.apache.org>
> 


--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message