ConcurrentSkipSet CompareTo Instant infinite loop

Question

I am creating a java.util.concurrent.ConcurrentSkipListSet with a comparator. My comparator compares an Instant field in the object to determine the order. This is the comparator:

public int compare(myObj first, myObj second) {
        if (first == null || first.getTime() == null) {
            return 1; 
        }
        if (second == null || second.getTime() == null) {
            return -1;
        }
        
        if ( first.getTime().isBefore(second.getTime()) {
            return -1;
        }
        else { 
            return 1;
        }
    }

When I use the above compartor 5/10 times it is stuck in an infinite loop. First is always after second , so the program always reach the else and return 1, however in some runs it just loops, it reaches the else but is just stuck constantly running the comparator... I can see this when I run in debug mode and also when adding extra logging. To clarify the 2 objects are not the same when it is stuck, so the issue isn't trying to add duplicated. When I switch isBefore to isAfter like so, I don't get that behaviour, it runs as expected each time. My question is why would this happen?

    public int compare(myObj first, myObj second) {
        if (first == null || first.getTime() == null) {
            return 1; 
        }
        if (second == null || second.getTime() == null) {
            return -1;
        }
        
        if ( first.getTime().isAfter(second.getTime()) {
            return 1;
        }
        else { 
            return -1;
        }
    }

Adding to the list implementation (boiled down for simplicity)

My concurrent skip set logic is very simple, I create the set with the compartor above, then myObj instant is initiated to now() + a predetermines number of minutes (hard coded so this calculation will not fail) then my obj is added to the concurrentskipset

private ConcurrentSkipListSet<MyObj> skipSetImpl= new ConcurrentSkipListSet<>(new MyObj.MyobjComp()); 

// added in a method, using Java Instant
foo.setTime( now.plus(60, ChronoUnit.SECONDS) ); 

this.skipSetImpl.add(foo); // add to concurrentSkipSet

Answer 1

You are not fulfilling the contract of Comparator.compare(). Whether this is the source of the problem you are asking about, without your ConcurrentSkipSet code we can’t tell, but it could very well be.

If two MyObj either are both null, one is null and the other has a null instant or both have a null instant, then your comparator cannot decide their order. If your skip set calls compare(a, b), a should come last, but if next it calls compare(b, a), suddenly b should come last. Could this cause it to loop? In any case it’s no nice property of a comparator to be inconsistent, and it will surely lead to problems with other classes that use a Comparator.

The documentation of the compare method says:

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y. (This implies that compare(x, y) must throw an exception if and only if compare(y, x) throws an exception.)

This is the part you are breaking. Your skip set should be able to rely on you keeping the contract.

You said:

they can't be equal with my logic and the way the program works they should never be equal

If so, you need to decide one order for any two MyObj. One solution is to disallow nulls (throw an exception if a null occurs). Another is to decide that nulls are equal.

A terse way of defining a comparator that puts nulls last is through Comparator.nullsLast() and Comparator.comparing() (since Java 8):

    Comparator<MyObj> comp = Comparator.nullsLast(Comparator.comparing(
            MyObj::getTime, Comparator.nullsLast(Instant::compareTo)));

Comparator.nullsLast() gives you a comparator that sorts nulls last and compares non-null objects using the comparator supplied as argument. I am also using the two-arg comparing​(Function<? super T,? extends U> keyExtractor, Comparator<? super U> keyComparator). The first argument, MyObj::getTime, tells it to compare the instants, and the second argument is the comparator used to compare the instants — in this case again putting nulls last. The resulting comparator does fulfil the contract of Comparator.comparing(). Corner case: it will put null MyObj references before MyObj objects having a null instant, which is different from what your comparator did.

When I recommend the Java 8+ way of defining comparators, it’s not so much because it’s brief. It’s more because it is much harder to get wrong, including that it is hard to break the contract of the compare method.

Link: Documentation of Comparator.compare()