Why my concurrentSkipListSet stucks while multi add?

Question

I want to test the performance of ConcurrentSkipListSet vs. ConcurrentLinkedQueue,so I make a test:

ConcurrentSkipListSet<Integer> concurrentSkipListSet=new ConcurrentSkipListSet<>((o1,o2)->{return 1;});
HashSet<Callable<Integer>> sets=new HashSet<>();
for(int i=0;i<1000;i++){
    final int j=i;
    sets.add(()->{concurrentSkipListSet.add(j);
        System.out.println(j);
            return null;
    });
}
Long c=System.currentTimeMillis();
System.out.println(c);
ExecutorService service=Executors.newFixedThreadPool(10);
try {
    service.invokeAll(sets);
}catch(Exception e){}
System.out.println(System.currentTimeMillis()-c);

I am so confused that the program stucks after sout about 20~50 j,and it won't finish in about an hour. If I change the i as i<10,it finished at 3 millis sometimes or stucks after sout about 4~5 j sometimes.

A newCachedThreadPool perfroms same as the newFixedThreadPool in IDEA and Eclipse.

Please help me to analyze it,3Q.

Now I think it is not the newCachedThreadPool's problem but that concurrentSkipListSet.add(j); when I changed SkipList to LinkedQueue or a synchronized HashSet, it worked well and finished in 168 millis or 170 millis.

Please help me to analyze it,3Q.

Answer 1

The problem may be in the comparator you're supplying to the ConcurrentSkipListSet constructor. It's always returning 1 which may lead to some kind of infinite loop in ConcurrentSkipListSet implementation. You could use ConcurrentSkipListSet constructor with no parameters to use natural ordering for Integer.

Consider what's going on when you're always returning 1 from a comparator:

Suppose we have two object A and B. A sorting algorithm at some point may ask your comparator "is A greater then B?" calling compare(A, B). You return 1 which means that indeed A > B and B should precede A in sorted order. Then at some point there's a chance that the algorithm will ask "is B greater then A?" and your compare(B, A) also will return 1 which means B > A and A should precede B in sorted order.

You can see that this comparator behavior is completely inconsistent. For some algorithms this may lead to infinite loops. For instance an algorithms may endlessly swap a pair of elements.