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 not thread safe
Date Wed, 26 Jun 2002 18:54:29 GMT
BTW, I just committed a threaded testcase (to avalon CVS). It
defaults to 10,000 iterations (5,000 puts and 5,000 gets) with
100 threads.  I tested it against 1,000 iterations and 1,000
threads simltaneously.  The BucketMap held a constant test time
while the synchronized HashMap grew in time due to the thread
contention.

The good news is that thread contention is not as expensive as
it used to be in JDK 1.4.  The bad news is it still plays a major
part.


----
TESTCASE: 10,000 iter, 100 thread

BucketMap (5001 buckets) took 2273ms
Thats 0.002273ms per operation
Unsized BucketMap (255 buckets) took 4807ms
Thats 0.004807ms per operation
Synchronized HashMap took 7170ms
Thats 0.00717ms per operation


---
TESTCASE: 1,000 iter, 1,000 thread

BucketMap (501 buckets) took 2524ms
Thats 0.002524ms per operation
Unsized BucketMap (255 buckets) took 2353ms
Thats 0.002353ms per operation
Synchronized HashMap took 11817ms
Thats 0.011817ms per operation


----------------

Conclusions:

BucketMap could be better fitted with a different storage
approach.  The Double-Hashing approach somebody came up with
is probably the best bet.

BucketMap is adversely affected when the number of entries
is significantly more than the number of available buckets
(like 20:1).  It is also more performant when there are fewer
hash collisions.  The second test showed this authoritatively.
The fact that the BucketMap with fewer entries (2:1) was
consistently more performant than the "properly sized" one
shows that it had a better distribution of entries.

However, in both cases, the BucketMap did outperform the
Synchronized HashMap by as much as a factor of ~2 (I know
it is a little less).

The BucketMap is a good place to start, but it can definitely
be improved.

Suggested improvements:

* Keeping the "bucket" concept, implement double-hashing
* Improve the hashing algorithm (it is basically a hack anyways)

This *can* be the server side programmer's best friend :)


--
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