Performance improvement hascode and compareTo

[tdurieux]

If you store CtClass in a set, map, ... (for example 256 ctClass) the performance are really bad.

This is due to:

• [x] to much hash code collision
• [x] bad performance of the EqualVisitor (string comparison) [#674]
• [ ] comparaTo in CtElement

[leventov]

I resolved this issue locally (written a better EqualsVisitor and HashCodeVisitor, the latter even already showed up -- https://github.com/INRIA/spoon/pull/601#issuecomment-212035743)

But I'm severely overhelmed... I hope I will find time to push changes over a week.

[tdurieux]

@GerardPaligot has almost finished a new EqualsVisitor (without reflection) that resolves the equals issue.

[leventov]

@tdurieux In this case I will just post my version -- @GerardPaligot might incorporate something into his version.

[leventov]

BiScanner.java

/**
 * Copyright (C) 2006-2015 INRIA and contributors
 * Spoon - http://spoon.gforge.inria.fr/
 *
 * This software is governed by the CeCILL-C License under French law and
 * abiding by the rules of distribution of free software. You can use, modify
 * and/or redistribute the software under the terms of the CeCILL-C license as
 * circulated by CEA, CNRS and INRIA at http://www.cecill.info.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the CeCILL-C License for more details.
 *
 * The fact that you are presently reading this means that you have had
 * knowledge of the CeCILL-C license and that you accept its terms.
 */
package spoon.reflect.visitor;

import spoon.reflect.declaration.CtAnnotation;
import spoon.reflect.declaration.CtElement;
import spoon.reflect.reference.CtTypeParameterReference;
import spoon.reflect.reference.CtTypeReference;

import java.lang.annotation.Annotation;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import static spoon.reflect.visitor.BiScanner.ScanResult.CONTINUE;
import static spoon.reflect.visitor.BiScanner.ScanResult.TERMINATE;

public class BiScanner {

    public enum ScanResult {
        CONTINUE,
        TERMINATE
    }

    public static class CollectingScanner extends CtScanner {
        private List<CtElement> elements;
        private List<Collection<?>> collections;
        private List<Object> values;

        @Override
        public final void scan(CtElement element) {
            if (elements == null) {
                elements = new ArrayList<CtElement>();
            }
            elements.add(element);
        }

        @Override
        public final void scan(Collection<? extends CtElement> elements) {
            if (collections == null) {
                collections = new ArrayList<Collection<?>>();
            }
            collections.add(elements);
        }

        @Override
        public final void scan(Object o) {
            if (values == null) {
                values = new ArrayList<Object>();
            }
            values.add(o);
        }

        private void reset() {
            elements = null;
            collections = null;
            values = null;
        }

        @Override
        public <A extends Annotation> void visitCtAnnotation(CtAnnotation<A> annotation) {
            enter(annotation);
            scan(annotation.getAnnotationType());
            scan(annotation.getAnnotations());
            scan(annotation.getValues().isEmpty() ? Collections.emptyList()
                    : new ArrayList<Object>(annotation.getValues().values()));
            exit(annotation);
        }

        @Override
        public void visitCtTypeParameterReference(CtTypeParameterReference ref) {
            enter(ref);
            scan(ref.getPackage());
            scan(ref.getDeclaringType());
            scan(ref.getActualTypeArguments());
            scan(ref.getAnnotations());
            if (ref.isUpper()) {
                scan(ref.getBoundingType()); // upper bounding type
                scan((CtTypeReference) null); // lower bounding type
            } else {
                scan((CtTypeReference) null); // upper bounding type
                scan(ref.getBoundingType()); // lower bounding type
            }
            exit(ref);
        }
    }

    private CollectingScanner collectingScanner;

    public BiScanner() {
    }

    public BiScanner(CollectingScanner collectingScanner) {
        this.collectingScanner = collectingScanner;
    }

    private CollectingScanner getCollectingScanner() {
        if (collectingScanner == null) {
            collectingScanner = new CollectingScanner();
        }
        return collectingScanner;
    }

    public ScanResult inspect(Object left, Object right) {
        if (left instanceof CtElement) {
            return inspectElements((CtElement) left, (CtElement) right);
        } else if (left instanceof Collection) {
            return inspectCollections((Collection<?>) left, (Collection<?>) right);
        } else {
            return inspectValues(left, right);
        }
    }

    public ScanResult inspectElements(CtElement left, CtElement right) {
        CollectingScanner scanner = getCollectingScanner();
        if (left != null) {
            left.accept(scanner);
        }
        List<CtElement> leftElements = scanner.elements;
        List<Collection<?>> leftCollections = scanner.collections;
        List<Object> leftValues = scanner.values;
        scanner.reset();

        if (right != null) {
            right.accept(scanner);
        }
        List<CtElement> rightElements = scanner.elements;
        List<Collection<?>> rightCollections = scanner.collections;
        List<Object> rightValues = scanner.values;
        scanner.reset();

        // First traverse values, then elements, then collections -- because in CompareTo and Equals applications
        // this is the perceived order of importance, also inspecting values and elements might give result faster
        // (i. e. we will figure out that elements are not equal faster)
        if (traverse(leftValues, rightValues) == TERMINATE) {
            return TERMINATE;
        }
        if (traverse(leftElements, rightElements) == TERMINATE) {
            return TERMINATE;
        }

        return traverse(leftCollections, rightCollections);
    }

    public ScanResult inspectCollections(Collection<?> lefts, Collection<?> rights) {
        return traverse(lefts, rights);
    }

    public ScanResult inspectValues(Object left, Object right) {
        return CONTINUE;
    }

    protected ScanResult traverse(Iterable<?> lefts, Iterable<?> rights) {
        lefts = lefts != null ? lefts : Collections.emptyList();
        rights = rights != null ? rights : Collections.emptyList();
        Iterator<?> leftIt = lefts.iterator();
        Iterator<?> rightIt = rights.iterator();
        while (true) {
            boolean moreLefts = leftIt.hasNext();
            boolean moreRights = rightIt.hasNext();
            if (!moreLefts && !moreRights) {
                break;
            }
            Object left = moreLefts ? leftIt.next() : null;
            Object right = moreRights ? rightIt.next() : null;
            if (inspect(left, right) == TERMINATE) {
                return TERMINATE;
            }
        }
        return CONTINUE;
    }
}

[leventov]

EqualScanner.java

/**
 * Copyright (C) 2006-2015 INRIA and contributors
 * Spoon - http://spoon.gforge.inria.fr/
 *
 * This software is governed by the CeCILL-C License under French law and
 * abiding by the rules of distribution of free software. You can use, modify
 * and/or redistribute the software under the terms of the CeCILL-C license as
 * circulated by CEA, CNRS and INRIA at http://www.cecill.info.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the CeCILL-C License for more details.
 *
 * The fact that you are presently reading this means that you have had
 * knowledge of the CeCILL-C license and that you accept its terms.
 */
package spoon.reflect.visitor;

import spoon.reflect.declaration.CtElement;
import spoon.reflect.declaration.CtNamedElement;
import spoon.reflect.reference.CtReference;

import java.util.Arrays;
import java.util.Collection;
import java.util.List;
import java.util.Set;

import static spoon.reflect.visitor.BiScanner.ScanResult.CONTINUE;
import static spoon.reflect.visitor.BiScanner.ScanResult.TERMINATE;

public class EqualScanner extends BiScanner {

    private final boolean customScanner;

    public EqualScanner() {
        customScanner = getClass() != EqualScanner.class;
    }

    /**
     * This constructor could be used to check elements for equality ignoring some parts of AST, e. g. compare
     * type references ignoring annotations: <pre><code>
     * EqualScanner equalScanner = new EqualScanner(new CollectingScanner() {
     *    {@literal @}Override
     *    {@code public <A extends Annotation> void visitCtAnnotation(CtAnnotation<A>} annotation) {
     *          // do nothing
     *     }
     * });
     * equalScanner.inspectElements(ref1, ref2);
     * </code></pre>
     * @param collectingScanner
     */
    public EqualScanner(CollectingScanner collectingScanner) {
        super(collectingScanner);
        customScanner = collectingScanner.getClass() != CollectingScanner.class && getClass() != EqualScanner.class;
    }

    private boolean result = true;

    public boolean getResult() {
        return result;
    }

    @Override
    public ScanResult inspectElements(CtElement left, CtElement right) {
        if (left == right) {
            // Including both are nulls.
            return CONTINUE;
        }
        if (left == null || right == null || left.getClass() != right.getClass()) {
            return fail();
        }
        if (left instanceof CtNamedElement) {
            String leftName = ((CtNamedElement) left).getSimpleName();
            String rightName = ((CtNamedElement) right).getSimpleName();
            if (!leftName.equals(rightName)) {
                return fail();
            }
        }
        if (left instanceof CtReference) {
            String leftName = ((CtReference) left).getSimpleName();
            String rightName = ((CtReference) right).getSimpleName();
            if (!leftName.equals(rightName)) {
                return fail();
            }
        }
        return super.inspectElements(left, right);
    }

    /**
     * Sets equal result to {@code false} and returns {@link ScanResult#TERMINATE}.
     * @return {@link ScanResult#TERMINATE}
     */
    protected ScanResult fail() {
        result = false;
        return TERMINATE;
    }

    @Override
    public ScanResult inspectCollections(Collection<?> lefts, Collection<?> rights) {
        if (lefts == rights) {
            // Including both are nulls.
            return CONTINUE;
        }
        // TODO assuming that Spoon always translates nulls to empty collections in setXxx() methods. Otherwise
        // we should keep in mind that null might be equal to empty list or set (but it makes impossible to implement
        // Equals entirely correctly in this case)
        if (lefts == null || rights == null) {
            return fail();
        }
        if (lefts.size() != rights.size()) {
            return fail();
        }
        if (lefts instanceof List && rights instanceof List) {
            return traverse(lefts, rights);
        }
        if (lefts instanceof Set && rights instanceof Set) {
            if (!customScanner) {
                if (lefts.equals(rights)) {
                    return CONTINUE;
                }
            } else {
                // It's important not to call just lefts.equals(rights) because if custom CollectingScanner is specified
                // in constructor, we should use it when comparing collections' elements.
                iterateLefts:
                for (Object left : lefts) {
                    for (Object right : rights) {
                        if (inspect(left, right) == CONTINUE) {
                            // comparing left with "wrong" right returned TERMINATE and potentially set result to false
                            result = true;
                            continue iterateLefts;
                        }
                    }
                    return fail();
                }
            }
            return CONTINUE;
        }
        checkIsListOrSet(lefts);
        checkIsListOrSet(rights);
        // List + Set or Set + List, means that when filling collectionLists, left or right element has skipped
        // adding some part of state (a List or a Set), i. e. they are not equal
        return fail();
    }

    private static void checkIsListOrSet(Collection<?> c) {
        if (!(c instanceof List || c instanceof Set)) {
            throw new IllegalStateException(
                    "Expect only lists or sets in any elements sub-structures, not " + c.getClass());
        }
    }

    @Override
    public ScanResult inspectValues(Object left, Object right) {
        if (left == right) {
            // Including both are nulls.
            return CONTINUE;
        }
        if (left == null || right == null || left.getClass() != right.getClass()) {
            return fail();
        }
        if (left.getClass().isArray()) {
            // Arrays appear as annotation values.
            if (!Arrays.deepEquals(new Object[] {left}, new Object[] {right})) {
                return fail();
            }
        }
        if (!left.equals(right)) {
            return fail();
        }
        return CONTINUE;
    }
}

[leventov]

CompareToScanner.java

/**
 * Copyright (C) 2006-2015 INRIA and contributors
 * Spoon - http://spoon.gforge.inria.fr/
 *
 * This software is governed by the CeCILL-C License under French law and
 * abiding by the rules of distribution of free software. You can use, modify
 * and/or redistribute the software under the terms of the CeCILL-C license as
 * circulated by CEA, CNRS and INRIA at http://www.cecill.info.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the CeCILL-C License for more details.
 *
 * The fact that you are presently reading this means that you have had
 * knowledge of the CeCILL-C license and that you accept its terms.
 */
package spoon.reflect.visitor;

import spoon.reflect.declaration.CtElement;
import spoon.reflect.declaration.CtNamedElement;
import spoon.reflect.reference.CtReference;

import java.util.Arrays;
import java.util.Collection;
import java.util.List;

import static spoon.reflect.visitor.BiScanner.ScanResult.CONTINUE;
import static spoon.reflect.visitor.BiScanner.ScanResult.TERMINATE;

public class CompareToScanner extends BiScanner {

    private int result = 0;

    public int getResult() {
        return result;
    }

    @Override
    public ScanResult inspectElements(CtElement left, CtElement right) {
        if (left == right) {
            // Including both are nulls.
            return CONTINUE;
        }
        if (left == null) {
            result = -1;
            return TERMINATE;
        }
        if (right == null) {
            result = 1;
            return TERMINATE;
        }
        if (left instanceof CtNamedElement && right instanceof CtNamedElement) {
            String leftName = ((CtNamedElement) left).getSimpleName();
            String rightName = ((CtNamedElement) right).getSimpleName();
            result = leftName.compareTo(rightName);
            if (result != 0) {
                return TERMINATE;
            }
        }
        if (left instanceof CtReference && right instanceof CtReference) {
            String leftName = ((CtReference) left).getSimpleName();
            String rightName = ((CtReference) right).getSimpleName();
            result = leftName.compareTo(rightName);
            if (result != 0) {
                return TERMINATE;
            }
        }
        if (left.getClass() != right.getClass()) {
            return compareClasses(left.getClass(), right.getClass());
        }
        return super.inspectElements(left, right);
    }

    @Override
    public ScanResult inspectCollections(Collection<?> lefts, Collection<?> rights) {
        if (lefts == rights) {
            // Including both are nulls.
            return CONTINUE;
        }
        if (lefts == null) {
            result = -1;
            return TERMINATE;
        }
        if (rights == null) {
            result = 1;
            return TERMINATE;
        }
        if ((lefts instanceof List && rights instanceof List)) {
            return traverse((List<?>) lefts, (List<?>) rights);
        }
        // Set + List, Set + Set, or any other collections -- compare just by size.
        result = lefts.size() - rights.size();
        return result == 0 ? CONTINUE : TERMINATE;
    }

    @Override
    public ScanResult inspectValues(Object left, Object right) {
        if (left == right) {
            // Including both are nulls.
            return CONTINUE;
        }
        if (left == null) {
            result = -1;
            return TERMINATE;
        }
        if (right == null) {
            result = 1;
            return TERMINATE;
        }
        if (left.getClass() != right.getClass()) {
            return compareClasses(left.getClass(), right.getClass());
        }
        if (left.getClass().isArray()) {
            String leftS = Arrays.deepToString(new Object[]{left});
            String rightS = Arrays.deepToString(new Object[]{right});
            result = leftS.compareTo(rightS);
        } else {
            if (!(left instanceof Comparable)) {
                throw new IllegalStateException(
                        "Values could be java (boxed) primitives, strings, enum constants or arrays, not "
                                + left.getClass());
            }
            result = ((Comparable) left).compareTo(right);
        }
        return result == 0 ? CONTINUE : TERMINATE;
    }

    private ScanResult compareClasses(Class<?> leftClass, Class<?> rightClass) {
        result = leftClass.getName().compareTo(rightClass.getName());
        if (result == 0) {
            throw new IllegalStateException("Two not equal classes have the same name " + leftClass.getName());
        }
        return TERMINATE;
    }
}

[leventov]

CtElementImpl.java

    /** the ordering  between CtElement is lexicographic,
     * based on the deep representation
     * which is also used in {@link #equals(Object)}.
     */
    public int compareTo(CtElement o) {
        if (this == o) {
            return 0;
        }
        CompareToScanner compareToScanner = new CompareToScanner();
        compareToScanner.inspectElements(this, o);
        int scannerRet = compareToScanner.getResult();
        return scannerRet;
    }

    private String getDeepRepresentation(CtElement elem) {
        EqualVisitor prThis = new EqualVisitor();
        prThis.scan(elem);
        return  prThis.getRepresentation();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        boolean ret = false;
        if ((o instanceof CtElement)) {
            EqualScanner equalScanner = new EqualScanner();
            equalScanner.inspectElements(this, (CtElement) o);
            ret = equalScanner.getResult();
        }
        // neat online testing of core Java contract
//      if (ret && this.hashCode() != o.hashCode()) {
//          throw new IllegalStateException("violation of equal/hashcode contract between \n" + getDeepRepresentation(this) + "\nand\n" + getDeepRepresentation((CtElement) o) + "\n");
//      }
        return ret;
    }

[leventov]

But well, to make it work, a lot of other changes also should be pushed... that's the problem.

[tdurieux]

I tested 4 different hashCode with mainTest:

Nb equals: The number of call of equals Nb true equality: The number of equals object (o1.equals(o2)) Nb collision: The number of hashCode collision (o1.hashCode() == o2.hashCode())

As you see, the original hashcode has the second better collision number and the execution cost of Leventov hashcode is too high.

Results

Original HashCode (2m 2s 216ms): Nb equals: 88396350 Nb true equality: 205792 0% Nb collision: 2810840 3%

Element ClassName HashCode (1m 50s 108ms): Nb equals: 88430927 Nb true equality: 205803 0% Nb collision: 2811121 3%

Literal HashCode (1m 50s 620ms) : Nb equals: 88396518 Nb true equality: 205810 0% Nb collision: 2810864 3%

Literal + ClassName HashCode (2m 6s 884ms): Nb equals: 88431095 Nb true equality: 205821 0% Nb collision: 2811145 3%

Leventov HashCode (2m 48s 768ms): Nb equals: 88422706 Nb true equality: 206393 0% Nb collision: 2246817 3%

[leventov]

Any chance for this to be merged or pushed forward? I've posted a working impl of compareTo

[monperrus]

Do you mean that of https://github.com/INRIA/spoon/issues/716#issue-160846546?

[leventov]

@monperrus I mean in comments in this issue. But it doesn't really matter, who's code or even make CtElements not comparable as suggested in comments in #716. Just don't convert ctElements to string unless from toString or printSignature methods themselves.

[monperrus]

Your biggest problem is a performance issue with compareTo? In which situation?

[leventov]

@monperrus right now my biggest problem is https://github.com/INRIA/spoon/issues/827, which happens somewhere inside compareTo()