commons-dev mailing list archives

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


Mime
View raw message