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
I say go for it.  Let commons surpass the Avalon implementation,
but PLEEAASSEE make a release soon.  That way I can safely deprecate
the Avalon collections project.

> -----Original Message-----
> From: Jack, Paul [mailto:pjack@sfaf.org] 
> Sent: Wednesday, August 14, 2002 8: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