JDK java.util.concurrent.ConcurrentSkipListSet.equals(Object o) implementation efficiency

[Jason Mehrens]

Tenghuan He,

You are correct if 'this' is a SortedMap/Set and 'o' is a SortedMap/Set then both interfaces list a clause in the top level documentation of:
"This order is reflected when iterating over the sorted map's collection views" and "The set's iterator will traverse the set in ascending element order."

So it should be safe to do an ordered  'list' type element comparison if and only if you have determined that both sets/maps use the same ordering.
In your example code you are missing the check to make sure the comparators are both null or equal.

Seems like a worthwhile RFE.  In general, though I tend to think of use cases for ConcurrentSkipListSet as "wildly mutating" which means you never call Set equals
or equals fails pretty early due to the mutation.

Jason  

________________________________________
From: core-libs-dev <core-libs-dev-bounces at openjdk.java.net> on behalf of Tenghuan He <tenghuanhe at gmail.com>
Sent: Friday, May 26, 2017 9:21 AM
To: core-libs-dev at openjdk.java.net
Subject: JDK java.util.concurrent.ConcurrentSkipListSet.equals(Object o) implementation efficiency

Hi, all

I found that the equalsimplementation of
java.util.concurrent.ConcurrentSkipListSet in JDK as follows:

public boolean equals(Object o) {
    // Override AbstractSet version to avoid calling size()
    if (o == this)
        return true;
    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    try {
        return containsAll(c) && c.containsAll(this);
    } catch (ClassCastException unused) {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }}


Since ConcurrentSkipListSet extends NavigableSet which extends SortedSet,
the following equalsimplementation seems more reasonable for a compare
object which also extends SortedSet.

public boolean myEquals(Object o) {
        // Override AbstractSet version to avoid calling size()
        if (o == this)
            return true;
        if (!(o instanceof Set))
            return false;
        if (o instanceof SortedSet) {
            Iterator iter1 = ((SortedSet) o).iterator();
            Iterator iter2 = iterator();

            while (iter1.hasNext() && iter2.hasNext()) {
                if (!iter1.next().equals(iter2.next())) {
                    return false;
                }
            }
            return !(iter1.hasNext() || iter1.hasNext());
        }
        Collection<?> c = (Collection<?>) o;
        try {
            return containsAll(c) && c.containsAll(this);
        } catch (ClassCastException unused) {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }

A simple test has shown the performance improvement

public class Test {
    public static void main(String[] args) {
        ConcurrentSkipListSet<Integer> set1 = new
ConcurrentSkipListSet<Integer>();
        ConcurrentSkipListSet<Integer> set2 = new
ConcurrentSkipListSet<Integer>();

        for (int i = 0; i < 10000000; i++) {
            set1.add(i);
            set2.add(i);
        }

        long ts = System.currentTimeMillis();
        System.out.println(set1.equals(set2));
        System.out.println(System.currentTimeMillis() - ts);

        ts = System.currentTimeMillis();
        System.out.println(myset1.myEquals(myset2));
        System.out.println(System.currentTimeMillis() - ts);
    }}

Output result

true2713true589


Any ideas? (Related question on SO:
https://stackoverflow.com/questions/44198103/jdk-java-util-concurrent-concurrentskiplistset-equalsobject-o-implementation-e

Thanks & Best Regards

Tenghuan He