FULL PRODUCT VERSION :
java version "1.6.0-rc"
Java(TM) SE Runtime Environment (build 1.6.0-rc-b104)
Java HotSpot(TM) 64-Bit Server VM (build 1.6.0-rc-b104, mixed mode)


ADDITIONAL OS VERSION INFORMATION :
Linux RHEL 4

A DESCRIPTION OF THE PROBLEM :
Performance of ConcurrentHashMap when running a simple test is poor on java 6 compared to java 5.

The basic problem appears to be with the "supplemental" hashing algorithm inside the ConcurrentHashMap class in java 6. When applied to the hashCode of relatively small integers (which is just the value) this returns, well.... basically the original value.

This is exacerbated by the algorithm used to determine the segment in which to store the integer. Because for small integers so many of the top bits in the "supplemented" hash continue to be zero, all of the keys are mapped into a single segment and you get horrible contention which then explains the performance degradation.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Compile and run the attached source. I ran it as

java -Xmx6g -Xms6g -verbose:gc CHM

on a 64-bit JVM.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
On 1.5.0_09 this gave:

jdk1.5.0_09/bin/java -Xmx6g -Xms6g -verbose:gc CHM
[GC 1572864K->831061K(6029312K), 2.7360780 secs]
[GC 2403925K->1316653K(6029312K), 1.6569750 secs]
[GC 2889517K->1900751K(6029312K), 1.6231660 secs]
[GC 3473615K->2247047K(6029312K), 2.4905310 secs]
[GC 3819911K->2588263K(6029312K), 2.2804910 secs]
[GC 4161127K->2922287K(5155584K), 2.2536550 secs]
[GC 3621423K->3086143K(5592448K), 1.2750620 secs]
[GC 3785279K->3220407K(5592448K), 1.5142950 secs]
[GC 3919543K->3335087K(5592448K), 1.6740890 secs]
[GC 4034223K->3443063K(5592448K), 1.7367300 secs]
[GC 4142199K->3574359K(5592448K), 1.4082950 secs]
[GC 4273495K->3735167K(5592448K), 1.0626740 secs]
[Full GC 3735167K->2106499K(5592448K), 16.0496230 secs]
Elapsed time = 64038 msecs

ACTUAL -
On jdk 6 it java:

jdk1.6.0/bin/java -Xmx6g -Xms6g -verbose:gc CHM 1
[GC 1572864K->828413K(6029312K), 2.7983680 secs]
[GC 2401277K->1334757K(6029312K), 2.9499190 secs]
[GC 2907621K->1945757K(6029312K), 2.6088650 secs]
[GC 3518621K->2307797K(6029312K), 2.8401080 secs]
[GC 3880661K->2638397K(6029312K), 2.3686200 secs]
[GC 4211261K->2955357K(5155584K), 2.2537560 secs]
[GC 3654493K->3110077K(5592448K), 1.3336820 secs]
[GC 3809213K->3234677K(5592448K), 1.6970660 secs]
[GC 3933813K->3338621K(5592448K), 1.7949220 secs]
[GC 4037757K->3448277K(5592448K), 1.8651310 secs]
[GC 4147413K->3582725K(5592448K), 1.7257750 secs]
[GC 4281861K->3746469K(5592448K), 1.3348600 secs]
[Full GC 3746469K->2204555K(5592448K), 15.2973700 secs]
Elapsed time = 100252 msecs


REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.*;
import java.util.concurrent.*;

public class CHM extends Thread {
        static ConcurrentHashMap<Integer, String> chm;
        static Integer[] ints;
        int thrNum;

        CHM(int thrNum) {
                this.thrNum = thrNum;
        }

        public void run() {
                Random rnd = new Random();
                for (int i=0; i<10000000; i++) {
                        Integer key = ints[rnd.nextInt(10000000)];
                        String value = chm.get(key);
                        if (value != null) {
                                chm.replace(key, value, new String("This is thread #" + thrNum));
                        } else {
                                chm.putIfAbsent(key, new String("This is thread #" + thrNum));
                        }
                }
        }

        public static void main(String[] args) throws Exception {
                chm = new ConcurrentHashMap<Integer, String>(10000000, 0.75f, 4);
                CHM[] threads = new CHM[4];

                ints = new Integer[10000000];
                for (int i=0; i<10000000; i++) {
                        ints[i] = new Integer(i);
                }

                long startTime = System.currentTimeMillis();
                for (int i=0; i<4; i++) {
                        threads[i] = new CHM(i);
                        threads[i].start();
                }
                for (int i=0; i<4; i++) {
                        threads[i].join();
                }
                long endTime = System.currentTimeMillis();
                System.out.println("Elapsed time = " + (endTime-startTime) + " msecs");
        }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Use java 5 or modify the hashCode() in Integer to return more "bitty" than just the int value.