ConcurrentHashMapV8

classic Classic list List threaded Threaded
77 messages Options
1234
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

David M. Lloyd-3
On 10/06/2011 04:39 PM, David M. Lloyd wrote:

> In one of my scratchpads I have a lockless* ConcurrentMap which does
> exactly this (have its entries implement Entry, that is) implemented in
> terms of an atomic ref array of (immutable) arrays of entries. I hope to
> have time to run it through some more testing in the next couple weeks,
> to see how it compares with what's on the table. So it's at least
> possible... we'll see about practical. :)
>
> The other extreme is the copy-on-write type of map where an iterator
> would reflect a snapshot and Entries would be immutable. But this is
> also easy to make well-defined for an arbitrary lifespan.
>
> * well, okay, it does lock to block writers during resize, so it's not
> 100% lockless.

I put this up in
https://github.com/dmlloyd/experimental-crap/branches/hashmaps if anyone
is interested, or just wants a good laugh.

--
- DML
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Doug Lea
In reply to this post by David M. Lloyd-3
On 10/06/11 17:39, David M. Lloyd wrote:

> -- we add some
>> time/space overhead to entrySet operations just to imperfectly
>> reinforce the questionable intuition that methods operate
>> directly on internal Entry objects that don't actually exist
>> (and need not actually exist wrt any other aspects of Map specs).
>
> But if the Entry actually *did* reflect the actual physical entry, then the
> contract for the Entry interface makes a lot more sense. You can retrieve the
> key always, and the value if it hasn't been removed (if it has you could give
> IllegalStateException as is allowed by spec).

We considered and rejected this approach back in JDK5 when deciding
upon iterator semantics for concurrent collections. If you allow
hasNext() to lie, claiming that an element exists but then throwing
an exception in next() because it no longer exists, then most
client iterator usages break. So instead we ensure that if
hasNext saw a valid element, then it is snapshotted as the one
returned in next(). Since these elements can concurrently come
and go at any time, receiving this (weakly consistent) snapshot
is as much as you can expect anyway. Even if you exported
a "live" entry, it could disappear as soon as client reads it
but before it acts upon it.

The underlying problem is that the non-atomic hasNext()/next()
pairing in Iterator is inherently concurrency-hostile.
But we didn't want to replace it with something else.
However, with upcoming lambdas and bulk operations, I'm
considering creating a variant of CHM that does not support
iterators at all, but instead several variants of
method forEach(entry -> action) etc.

-Doug

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

David M. Lloyd-3
On 10/07/2011 05:41 AM, Doug Lea wrote:

> On 10/06/11 17:39, David M. Lloyd wrote:
>> -- we add some
>>> time/space overhead to entrySet operations just to imperfectly
>>> reinforce the questionable intuition that methods operate
>>> directly on internal Entry objects that don't actually exist
>>> (and need not actually exist wrt any other aspects of Map specs).
>>
>> But if the Entry actually *did* reflect the actual physical entry,
>> then the
>> contract for the Entry interface makes a lot more sense. You can
>> retrieve the
>> key always, and the value if it hasn't been removed (if it has you
>> could give
>> IllegalStateException as is allowed by spec).
>
> We considered and rejected this approach back in JDK5 when deciding
> upon iterator semantics for concurrent collections. If you allow
> hasNext() to lie, claiming that an element exists but then throwing
> an exception in next() because it no longer exists, then most
> client iterator usages break. So instead we ensure that if
> hasNext saw a valid element, then it is snapshotted as the one
> returned in next(). Since these elements can concurrently come
> and go at any time, receiving this (weakly consistent) snapshot
> is as much as you can expect anyway. Even if you exported
> a "live" entry, it could disappear as soon as client reads it
> but before it acts upon it.

Yeah, but I think that's not outside of what should be reasonably
expected when you iterate a (non-COW) concurrent hash map.  As you say,
hasNext()/next() can be made consistent by actually getting a snapshot
ref to the next entry in hasNext(), but it doesn't have to be a copy of
the Entry, it can still be the literal Entry in the map.

Using a "real" Entry, if the user calls getValue() on the entry but it
has since been deleted, you'd get an ISE regardless of whether it came
from an array, iterator, or reflection right into the guts of the map,
which is very consistent behavior.

If we wanted to really follow the precedents that exist in the
collections lib, we'd have a ConcurrentEntry which had more atomic
operations on it, like setValueIfAbsent(), replaceValue(), remove(),
getValueIfPresent(), etc.  But I imagine that ship has sailed.

For the other set types, you'd probably wouldn't have to throw ISE
because the keys don't usually go anywhere and you can train the value
iterator to pass over missing entries and snapshot value refs, so even
if they're deleted in the meantime the behavior is as "nice" as can be
expected, if not more so.

> The underlying problem is that the non-atomic hasNext()/next()
> pairing in Iterator is inherently concurrency-hostile.
> But we didn't want to replace it with something else.
> However, with upcoming lambdas and bulk operations, I'm
> considering creating a variant of CHM that does not support
> iterators at all, but instead several variants of
> method forEach(entry -> action) etc.

Agreed that lambdas will greatly improve the situation, but I'm not sure
it warrants shooting down CHM iterators altogether.

--
- DML
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Mark Thornton-3
On 07/10/11 15:32, David M. Lloyd wrote:
> Yeah, but I think that's not outside of what should be reasonably
> expected when you iterate a (non-COW) concurrent hash map.  As you
> say, hasNext()/next() can be made consistent by actually getting a
> snapshot ref to the next entry in hasNext(), but it doesn't have to be
> a copy of the Entry, it can still be the literal Entry in the map.
I have several nonconcurrent map implementations which do not have Entry
instances internally --- they are created on the fly as needed to
satisfy the entrySet requirements. I usually do this where I can't
afford the space required by literal Entry instances.

Mark Thornton

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Adrian Tarau
Hi Mark,

Are those implementations open source or closed source? I need a
non-concurrent map which has minimum memory overhead per entry for a
cache with small payloads(store a mapping between small strings).

Thanks,
Adrian Tarau.

On 10/07/2011 10:45 AM, Mark Thornton wrote:

> On 07/10/11 15:32, David M. Lloyd wrote:
>> Yeah, but I think that's not outside of what should be reasonably
>> expected when you iterate a (non-COW) concurrent hash map.  As you
>> say, hasNext()/next() can be made consistent by actually getting a
>> snapshot ref to the next entry in hasNext(), but it doesn't have to
>> be a copy of the Entry, it can still be the literal Entry in the map.
> I have several nonconcurrent map implementations which do not have
> Entry instances internally --- they are created on the fly as needed
> to satisfy the entrySet requirements. I usually do this where I can't
> afford the space required by literal Entry instances.
>
> Mark Thornton
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Gregg Wonderly-2
In reply to this post by Mark Thornton-3
On 10/7/2011 9:45 AM, Mark Thornton wrote:

> On 07/10/11 15:32, David M. Lloyd wrote:
>> Yeah, but I think that's not outside of what should be reasonably expected
>> when you iterate a (non-COW) concurrent hash map. As you say, hasNext()/next()
>> can be made consistent by actually getting a snapshot ref to the next entry in
>> hasNext(), but it doesn't have to be a copy of the Entry, it can still be the
>> literal Entry in the map.
> I have several nonconcurrent map implementations which do not have Entry
> instances internally --- they are created on the fly as needed to satisfy the
> entrySet requirements. I usually do this where I can't afford the space required
> by literal Entry instances.

It is important for an iterator to snapshot if you can ask it for the next
entry.  What would be better, to avoid copying and to manage concurrency easier,
without the hasNext()/next() issue, would be to have iteration functionality in
an expression so that there was no hasNext()/next() pairing. But rather put the
collection in control of performing a call out to the "task" for the next
element in the collection.  As in something like

public interface IterationPoint<T> {
        public void iterateFor( T value );
}

public interface IterationProvider<T> {
        public int iterateOver( IterationPoint<T> point );
}

This would then allow complete freedom from hasNext()/next() pairing because
only if the collection found another value, would it need to reveal it to the
IterationPoint.

Lambdas would make this easy, but even with inner classes, it's still usable.

Gregg Wonderly

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Bob Lee-8
In reply to this post by Doug Lea
On Wed, Oct 5, 2011 at 6:11 AM, Doug Lea <[hidden email]> wrote:
To me, fixing the mis-feature is more important
than retaining pure compatibility for a usage
that probably didn't do what people expected anyway.
But if you've ever done anything relying on the old j.u.c
behavior, could you let us know? Thanks!

Is it correct to assume that "fixing" CHM.entrySet().toArray() requires more work on our part? If so, it's probably not worth the effort 

If we assume the user wants a snapshot of the entry set, here's the code using toArray():

    Set<Map.Entry<K, V>> original = map.entrySet();
    // This array isn't used outside of this code, so we can ignore the warning.
    @SuppressWarnings("unchecked")
    Map.Entry<K, V>[] array = original.toArray(
        (Map.Entry<K, V>[]) new Map.Entry[0]);
    // We erroneously get an "unchecked generic array creation" warning here. 
    @SuppressWarnings("unchecked")
    Set<Map.Entry<K, V>> copy = new HashSet<Map.Entry<K, V>>(
        Arrays.asList(array));

Yuck. It requires two unsafe operations. We actually shouldn't get a warning in the second case, and it'll go away either way with Java 7, but I do get a warning with my current setup. Copying entries from a concurrent map to an exact-length array is tricky and inefficient. The user can call size() and use it to create the passed-in array, but the array size could change. It can also change while copying the entries in which case toArray() may have to create a copy. If the size goes down, the array needs to be truncated. If the size goes up, any remaining entries are ignored.

It's simpler, safer, and more efficient for users to copy the entries manually:

    Set<Map.Entry<K, V>> copy = new HashSet<Map.Entry<K, V>>(map.size());
    for (Map.Entry<K, V> entry : map.entrySet()) {
      copy.add(new AbstractMap.SimpleEntry<K, V>(entry));
    }

Thanks,
Bob


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Doug Lea
On 10/07/11 16:52, Bob Lee wrote:

> On Wed, Oct 5, 2011 at 6:11 AM, Doug Lea <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     To me, fixing the mis-feature is more important
>     than retaining pure compatibility for a usage
>     that probably didn't do what people expected anyway.
>     But if you've ever done anything relying on the old j.u.c
>     behavior, could you let us know? Thanks!
>
>
> Is it correct to assume that "fixing" CHM.entrySet().toArray() requires more
> work on our part?

I'm not sure what you mean. The fix in V8 is to use non-write-through
Entry objects in entrySet.toArray to avoid unwanted side effects in
array[index].setValue().

The problematic use case is very rare, if it even exists.
In a google code search for the combination on ConcurrentHashMap,
entrySet, toArray, and setValue, I didn't see any. (Although
there are other possible ways to this encounter it.)
But because it is rare, it is a good idea to avoid surprises
when people do encounter it.

If you'd like to avoid the write-through side-effects without this
fix in existing CHM, you'd need to copy the elements of
entrySet().toArray() one by one into AbstractMap.SimpleEntry
(or some similar class) objects.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Bob Lee-8
On Sat, Oct 8, 2011 at 3:30 AM, Doug Lea <[hidden email]> wrote:
I'm not sure what you mean. The fix in V8 is to use non-write-through
Entry objects in entrySet.toArray to avoid unwanted side effects in
array[index].setValue().

If the user wants entries where setValue() doesn't modify the original map, it's simpler, safer, and more efficient for the user to copy the entries manually. It's also compatible across implementations. We needn't waste our time and bytes making EntrySet.toArray() do something "sensible" because users shouldn't use it anyway. Generics and arrays don't mix.

Bob

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Checking for Race Conditions in Concurrent Code

Nathan Reynolds-2
In reply to this post by Doug Lea
When writing concurrent code what are some good tools to check for race conditions?

I use Java Path Finder.  It allows for testing the Java code without converting it into some abstract model.  The challenge is writing useful tests which don't take forever to check all of the thread scheduling interleavings.  So, I am wondering what other tools exist out there that will run very quickly and are very easy to map Java to model.

Nathan Reynolds | Consulting Member of Technical Staff | 602.333.9091
Oracle PSR Engineering | Server Technology


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Checking for Race Conditions in Concurrent Code

Daniel Luo

IBM Multicore Software Development Kit(MSDK) is a full-feature toolkit to test, debug and profile Java multithreaded applications. It includes an effective and efficient runtime data race detector that may meet your need.

Sent from Daniel's HTC Android

在 2011-11-8 上午8:50,"Nathan Reynolds" <[hidden email]>写道:
When writing concurrent code what are some good tools to check for race conditions?

I use Java Path Finder.  It allows for testing the Java code without converting it into some abstract model.  The challenge is writing useful tests which don't take forever to check all of the thread scheduling interleavings.  So, I am wondering what other tools exist out there that will run very quickly and are very easy to map Java to model.

Nathan Reynolds | Consulting Member of Technical Staff | 602.333.9091
Oracle PSR Engineering | Server Technology


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Dr Heinz M. Kabutz
In reply to this post by Doug Lea
I would like to run some performance tests comparing CHMv8 to the CHM in
Java 7 and to Cliff Click's non-blocking hash map implementation.  
However, I do not have access to hardware that will do the test
justice.  Would any of you be able to run some tests for me on machines
in excess of 50 cores?  The more the better.  If so, please contact me
directly.

Regards

Heinz
--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun Java Champion
IEEE Certified Software Development Professional
http://www.javaspecialists.eu
Tel: +30 69 72 850 460
Skype: kabutz



On 10/7/11 1:41 PM, Doug Lea wrote:

> On 10/06/11 17:39, David M. Lloyd wrote:
>> -- we add some
>>> time/space overhead to entrySet operations just to imperfectly
>>> reinforce the questionable intuition that methods operate
>>> directly on internal Entry objects that don't actually exist
>>> (and need not actually exist wrt any other aspects of Map specs).
>>
>> But if the Entry actually *did* reflect the actual physical entry,
>> then the
>> contract for the Entry interface makes a lot more sense. You can
>> retrieve the
>> key always, and the value if it hasn't been removed (if it has you
>> could give
>> IllegalStateException as is allowed by spec).
>
> We considered and rejected this approach back in JDK5 when deciding
> upon iterator semantics for concurrent collections. If you allow
> hasNext() to lie, claiming that an element exists but then throwing
> an exception in next() because it no longer exists, then most
> client iterator usages break. So instead we ensure that if
> hasNext saw a valid element, then it is snapshotted as the one
> returned in next(). Since these elements can concurrently come
> and go at any time, receiving this (weakly consistent) snapshot
> is as much as you can expect anyway. Even if you exported
> a "live" entry, it could disappear as soon as client reads it
> but before it acts upon it.
>
> The underlying problem is that the non-atomic hasNext()/next()
> pairing in Iterator is inherently concurrency-hostile.
> But we didn't want to replace it with something else.
> However, with upcoming lambdas and bulk operations, I'm
> considering creating a variant of CHM that does not support
> iterators at all, but instead several variants of
> method forEach(entry -> action) etc.
>
> -Doug
>
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Nathan Reynolds-2
I've been thinking about running such a test on a dual Westmere system with a total of 24 logical cores.  I've been thinking about doing this for a long time so I wouldn't hold your breath.  I am definitely interested in your results.

Nathan Reynolds | Consulting Member of Technical Staff | 602.333.9091
Oracle PSR Engineering | Server Technology

On 12/23/2011 7:36 AM, Dr Heinz M. Kabutz wrote:
I would like to run some performance tests comparing CHMv8 to the CHM in Java 7 and to Cliff Click's non-blocking hash map implementation.  However, I do not have access to hardware that will do the test justice.  Would any of you be able to run some tests for me on machines in excess of 50 cores?  The more the better.  If so, please contact me directly.

Regards

Heinz

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Viktor Klang
We have a 48-core box (4 x Magny Cours)

Cheers,


On Fri, Dec 23, 2011 at 5:08 PM, Nathan Reynolds <[hidden email]> wrote:
I've been thinking about running such a test on a dual Westmere system with a total of 24 logical cores.  I've been thinking about doing this for a long time so I wouldn't hold your breath.  I am definitely interested in your results.

Nathan Reynolds | Consulting Member of Technical Staff | <a href="tel:602.333.9091" value="+16023339091" target="_blank">602.333.9091
Oracle PSR Engineering | Server Technology

On 12/23/2011 7:36 AM, Dr Heinz M. Kabutz wrote:
I would like to run some performance tests comparing CHMv8 to the CHM in Java 7 and to Cliff Click's non-blocking hash map implementation.  However, I do not have access to hardware that will do the test justice.  Would any of you be able to run some tests for me on machines in excess of 50 cores?  The more the better.  If so, please contact me directly.

Regards

Heinz

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




--
Viktor Klang

Akka Tech Lead
Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Dr Heinz M. Kabutz
OK, here is the test, done as simply as I could to increase the probability that Nathan could also run it :-)  Just untar the file and run ant.  If you don't have ant, then "java -cp classes CliffClickMapTest" would do it too (classes are compiled already).

Please email me the output and the version of Java that you're running it with.

It is Cliff Click's test from his NBHM, with the settings hardcoded into the file.

Thanks :-)
Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun Java Champion
IEEE Certified Software Development Professional
http://www.javaspecialists.eu
Tel: +30 69 72 850 460
Skype: kabutz 


On 12/23/11 6:23 PM, √iktor Ҡlang wrote:
We have a 48-core box (4 x Magny Cours)

Cheers,


On Fri, Dec 23, 2011 at 5:08 PM, Nathan Reynolds <[hidden email]> wrote:
I've been thinking about running such a test on a dual Westmere system with a total of 24 logical cores.  I've been thinking about doing this for a long time so I wouldn't hold your breath.  I am definitely interested in your results.

Nathan Reynolds | Consulting Member of Technical Staff | <a moz-do-not-send="true" href="tel:602.333.9091" value="+16023339091" target="_blank">602.333.9091
Oracle PSR Engineering | Server Technology

On 12/23/2011 7:36 AM, Dr Heinz M. Kabutz wrote:
I would like to run some performance tests comparing CHMv8 to the CHM in Java 7 and to Cliff Click's non-blocking hash map implementation.  However, I do not have access to hardware that will do the test justice.  Would any of you be able to run some tests for me on machines in excess of 50 cores?  The more the better.  If so, please contact me directly.

Regards

Heinz

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




--
Viktor Klang

Akka Tech Lead
Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

clifftest.tgz (212K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Dr Heinz M. Kabutz
From my first tests on my little 8-core system, it seems that for small table sizes, CHM v8 is the clear winner.

But if the table is a bit larger, say 1000000 entries, then Cliff Click's NonBlockingHashMap takes the lead.

It would be interesting to compare the results on a large system.

Also, the memory needs of the ConcurrentHashMap were quite high.  See here: http://www.javaspecialists.eu/archive/Issue193.html

Seems that for empty maps, the standard CHM with 4096 would need 16544 bytes and for the Version 8 of CHM would need 72 bytes.  It would be interesting to try out how the Version 8 CHM grows as we add more elements :-)  Another day ...
Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun Java Champion
IEEE Certified Software Development Professional
http://www.javaspecialists.eu
Tel: +30 69 72 850 460
Skype: kabutz 


On 12/23/11 7:51 PM, Dr Heinz M. Kabutz wrote:
OK, here is the test, done as simply as I could to increase the probability that Nathan could also run it :-)  Just untar the file and run ant.  If you don't have ant, then "java -cp classes CliffClickMapTest" would do it too (classes are compiled already).

Please email me the output and the version of Java that you're running it with.

It is Cliff Click's test from his NBHM, with the settings hardcoded into the file.

Thanks :-)
Regards

Heinz
-- 
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun Java Champion
IEEE Certified Software Development Professional
http://www.javaspecialists.eu
Tel: +30 69 72 850 460
Skype: kabutz 
  


On 12/23/11 6:23 PM, √iktor Ҡlang wrote:
We have a 48-core box (4 x Magny Cours)

Cheers,


On Fri, Dec 23, 2011 at 5:08 PM, Nathan Reynolds <[hidden email]> wrote:
I've been thinking about running such a test on a dual Westmere system with a total of 24 logical cores.  I've been thinking about doing this for a long time so I wouldn't hold your breath.  I am definitely interested in your results.

Nathan Reynolds | Consulting Member of Technical Staff | <a moz-do-not-send="true" href="tel:602.333.9091" value="+16023339091" target="_blank">602.333.9091
Oracle PSR Engineering | Server Technology

On 12/23/2011 7:36 AM, Dr Heinz M. Kabutz wrote:
I would like to run some performance tests comparing CHMv8 to the CHM in Java 7 and to Cliff Click's non-blocking hash map implementation.  However, I do not have access to hardware that will do the test justice.  Would any of you be able to run some tests for me on machines in excess of 50 cores?  The more the better.  If so, please contact me directly.

Regards

Heinz

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




--
Viktor Klang

Akka Tech Lead
Typesafe - Enterprise-Grade Scala from the Experts

Twitter: @viktorklang


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

JavaConcurrency-v0.1-11.PerformanceAndScalability.pdf (1M) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: ConcurrentHashMapV8

Doug Lea
On 12/24/11 15:09, Dr Heinz M. Kabutz wrote:
>  >From my first tests on my little 8-core system, it seems that for small table
> sizes, CHM v8 is the clear winner.
>
> But if the table is a bit larger, say 1000000 entries, then Cliff Click's
> NonBlockingHashMap takes the lead.

This is consistent with what I see. We have 6 test machines, 2 each
Intel, AMD, and Sparc, ranging from 8 to 128 hardware threads, that
we regularly run most of the approx 100 performance checks in
our CVS src/test/loops. (Plus accounts on other machines out there
for less frequent tests.) See near the end of
http://gee.cs.oswego.edu/dl/concurrency-interest/index.html
for notes on getting and using these. Cliff Click's test (that was the basis
of yours) isn't in our CVS but we occasionally run it too.

Testing performance of hash tables requires care.
There are many reasons that a single test program can be
uninformative. For example, some tests just amount to
measuring a platform's memory system throughput under
constant cache misses. Some have key types,
locality/non-locality of key or value use, or operation mixes that
are not representative of most uses.  For NON-concurrent hash table
benchmarks, there seems to be enough rough consensus about
what makes for representativeness that we put together
MapMicroBenchmark (in test/loops) that we mostly believe.
For concurrent ones, there still seems to be too much diversity
to treat any particular test program as definitive.
In general though, I've found that CHMV8 does better than
NonBlockingHashMap except in two cases: (1) When the table
is large and there is little locality of key use -- here,
NonBlockingHashMap's more compact key array representation
pays off; and (2) when the table needs to expand rapidly due
to insertions by multiple threads -- here, NonBlockingHashMap's
help-out approach can work better than CHMV8's approach of
a single resizer while the old table is concurrently usable.
Neither of these scenarios seems common enough to outweigh
the CHMV8's advantages in other cases.


> Seems that for empty maps, the standard CHM with 4096 would need *16544* bytes
> and for the Version 8 of CHM would need *72* bytes.  It would be interesting to
> try out how the Version 8 CHM grows as we add more elements :-)

It averages approximately 8 * N words (where N is number of elements),
with a large variance because table size expands only at powers of two.

It is worth noting though that probably the most consistent
finding across all sorts of performance tests for all sorts of
hash tables (and across all sorts of languages)
is that providing a good size estimate in constructor arguments
is the single best thing users can do to improve performance.
We employ many clever techniques to cope when there are no
estimates, but none of them are as effective as good user guidance.

-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
1234