commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jack, Paul" <pj...@sfaf.org>
Subject RE: [Collections] StaticBucketMap integration
Date Thu, 15 Aug 2002 03:29:40 GMT
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>


Mime
View raw message