You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by "Jack, Paul" <pj...@sfaf.org> on 2002/06/25 22:12:36 UTC

[Collections] StaticBucketMap not thread safe

Ugh.  StaticBucketMap has double-checked-locking-esque problems.

Since access to the node array (m_buckets) isn't synchronized,
different processors can disagree as to whether an element in
that array is null or not.

Worse, the reference to a Node placed in that array can be
written before the Node is fully constructed, because compilers/
pipelines can feel free to reorder those instructions.  Almost every
operation on a StaticBucketMap can therefore fail in unexpected
ways.

Only way to fix it is to synchronize every access to m_buckets.
I'm not sure how badly that will affect performance but it definitely
wouldn't be as optimized.

-Paul

--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>


Re: [Collections] StaticBucketMap not thread safe

Posted by Juozas Baliuka <ba...@centras.lt>.
Hi,
doe's somebody tried to test StaticBucketMap for performance without
synchronization ?
I think we need to implement not thread safe, but "fast" map first and try
to synchronize it
after it will be "fast" ( as fast as java.util.HashMap is). I tired to
implement "fast" set,
but I see performace more depends on "loadFctor" and "initialCapacity" not
on implementation or algorythm and  hash functions are "good" and "bad" at
the
same time (all depend on input).



> > From: Berin Loritsch [mailto:bloritsch@apache.org]
> >
> > > From: Jack, Paul [mailto:pjack@sfaf.org]
> > >
> > > Ugh.  StaticBucketMap has double-checked-locking-esque problems.
> > >
> > > Since access to the node array (m_buckets) isn't
> > > synchronized, different processors can disagree as to whether
> > > an element in that array is null or not.
> > >
> > > Worse, the reference to a Node placed in that array can be
> > > written before the Node is fully constructed, because
> > > compilers/ pipelines can feel free to reorder those
> > > instructions.  Almost every operation on a StaticBucketMap
> > > can therefore fail in unexpected ways.
> > >
> > > Only way to fix it is to synchronize every access to
> > > m_buckets. I'm not sure how badly that will affect
> > > performance but it definitely wouldn't be as optimized.
> >
> > What about making the m_buckets volatile?  Wouldn't that
> > help?
>
> On second thought, a better approach would be to merge the
> m_locks[] and m_buckets[].
>
> The empty array should always have one node available--however
> the node is empty.  We synchronize on the first node in the
> bucket.  When we have something to put in the empty node, we
> set its values.
>
> That way we don't run into the problem of having a lock separate
> from what we really want to synchronize on.  I have a feeling
> that this is where the double-checked-locking-esque issues
> are coming from.
>
>
> --
> To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.o
rg>
> For additional commands, e-mail:
<ma...@jakarta.apache.org>
>


--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>


RE: [Collections] StaticBucketMap not thread safe

Posted by Berin Loritsch <bl...@apache.org>.
> From: Berin Loritsch [mailto:bloritsch@apache.org] 
> 
> > From: Jack, Paul [mailto:pjack@sfaf.org]
> > 
> > Ugh.  StaticBucketMap has double-checked-locking-esque problems.
> > 
> > Since access to the node array (m_buckets) isn't
> > synchronized, different processors can disagree as to whether 
> > an element in that array is null or not.
> > 
> > Worse, the reference to a Node placed in that array can be
> > written before the Node is fully constructed, because 
> > compilers/ pipelines can feel free to reorder those 
> > instructions.  Almost every operation on a StaticBucketMap 
> > can therefore fail in unexpected ways.
> > 
> > Only way to fix it is to synchronize every access to
> > m_buckets. I'm not sure how badly that will affect 
> > performance but it definitely wouldn't be as optimized.
> 
> What about making the m_buckets volatile?  Wouldn't that
> help?

On second thought, a better approach would be to merge the
m_locks[] and m_buckets[].

The empty array should always have one node available--however
the node is empty.  We synchronize on the first node in the
bucket.  When we have something to put in the empty node, we
set its values.

That way we don't run into the problem of having a lock separate
from what we really want to synchronize on.  I have a feeling
that this is where the double-checked-locking-esque issues
are coming from.


--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>


RE: [Collections] StaticBucketMap not thread safe

Posted by Berin Loritsch <bl...@apache.org>.
> From: Jack, Paul [mailto:pjack@sfaf.org] 
> 
> Ugh.  StaticBucketMap has double-checked-locking-esque problems.
> 
> Since access to the node array (m_buckets) isn't 
> synchronized, different processors can disagree as to whether 
> an element in that array is null or not.
> 
> Worse, the reference to a Node placed in that array can be 
> written before the Node is fully constructed, because 
> compilers/ pipelines can feel free to reorder those 
> instructions.  Almost every operation on a StaticBucketMap 
> can therefore fail in unexpected ways.
> 
> Only way to fix it is to synchronize every access to 
> m_buckets. I'm not sure how badly that will affect 
> performance but it definitely wouldn't be as optimized.

What about making the m_buckets volatile?  Wouldn't that
help?

I can tell you this much--if you have to synchronize on
every access to m_buckets then you lose all advantage of
BucketMap and you would actually be better off working
with a synchronized map via Collections.synchronizedMap().

What will end up happening is essentially the same as
every access will be synchronized at the same point.


--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>