4

I am building a model with a number of autonomous agents. They make decisions on which object to choose within their immediate environment or "neighborhood". They do this retrieving the objects, add them to a list, sort the list based on preferences, and choose the top choice every iteration. The decision determines their movement.

Unfortunately, once the population of agents becomes too high, the program slows down massively.

I use a compare method (below), which is relatively short, but uses a lot of memory, to compare the objects. I am wondering if there are any other methods you guys know of that might be more computationally efficient?

class ObjectComparator implements Comparator <Tree> {

    @Override
    public int compare(Object object1, Object object2) {
        return new CompareToBuilder()
            .append(object1.getTYPE(), object2.getTYPE())
            .append(object2.getDBH(), object1.getDBH())
            .append(object1.getDistanceFrom(), object2.getDistanceFrom())
            .append(object2.isIdeal(), tree1.isIdeal()).toComparison();
    }
}
Taylor Marie
  • 357
  • 1
  • 15

2 Answers2

3

Some points that may be useful (note that I didn't use repast-simphony so some of the points may be already implemented by this framework):

  1. Measure - is comparison/sorting the bottle-neck? You said that it uses a lot of memory - that doesn't automatically make the program run slower (are there GC overhead issues maybe? Experiment with the VM args). And of course before measuring - warm up the JVM (so that the JIT can catch up with normal operating conditions for your code, etc.). Find out what's going on with jvisualvm.

  2. I don't know what are the objects that you're passing to append method, but consider the case that you can maybe return faster than comparing objects like you do now. Try to use the knowledge of your specific domain model.

  3. You've said that agents "retrieve the objects, add them to a list" and sort. Maybe it will be beneficial to store already sorted list of neighbors and if something will change maybe (that's a guess) there will be a little change in the list - so it's almost completely sorted. Use sorting algorithm that handles "almost sorted lists" lists very quickly and compare results with the default Java sorting algorithm. That, of course, depends on how often does your model of neighbors change. If your model won't change (I suppose that TYPE won't change) then the sorting issue will be non-existent.

  4. Consider using plain Java code to CompareToBuilder - if you have millions of objects the object creation might be a big overhead (if it lies on a critical path/bottle-neck).

  5. Do you utilize concurrency? Maybe it will speed up if you run your algorithm in a parallel way.

Many of the other optimizations depends on your specific object structure and relations. E.g. you have Tree as the type in the generics - maybe this tree is not ballanced, maybe you could use AVL, Heap, or change LinkedList to ArrayList, etc. Experiment & Measure.

I hope that will help a little.

Xeon
  • 5,949
  • 5
  • 31
  • 52
0

I had exactly the same problem. It may seem to be elegant to use this apache-commons builder however the compareTo method can be called a lot and when you have a lot of data it will be called even more. The objects are pretty light but there are so many generated in the short amount of time that it causes a big GC pressure and bigger pauses eventually giving an impression that the service is stale.

I wanted to come with something that is both reusable and does not allocate any memory and replaced the CompareToBuilder with the following util:

/**
 * Utility for implementing null safe and efficient {@link Comparable#compareTo(Object)}.
 *
 * Note: it does not use vararg for a performance reason.
 *
 * @author aleksanderlech
 */
public final class ComparingUtils {

    public static <T1 extends Comparable<T1>, T2 extends Comparable<T2>, T3 extends Comparable<T3>> int compare(int upstreamComparision, T1 o1v1, T1 o2v1, T2 o1v2, T2 o2v2, T3 o1v3, T3 o2v3) {
        return compare(compare(compare(upstreamComparision, o1v1, o2v1), o1v2, o2v2), o1v3, o2v3);
    }

    public static <T1 extends Comparable<T1>, T2 extends Comparable<T2>> int compare(int upstreamComparision, T1 o1v1, T1 o2v1, T2 o1v2, T2 o2v2) {
        return compare(compare(upstreamComparision, o1v1, o2v1), o1v2, o2v2);
    }

    public static <T1 extends Comparable<T1>> int compare(int upstreamComparision, T1 v1, T1 v2) {
        if(upstreamComparision == 0) {
            if(v1 == v2) {
                return 0;
            }
            if(v1 == null) {
                return 1;
            } else if(v2 == null) {
                return -1;
            }
            return v1.compareTo(v2);

        }

        return upstreamComparision;
    }

    private ComparingUtils() {}
}

the usage is as follows:

@Override
public int compareTo(Name o) {
    return compare(super.compareTo(o), this.english, o.english, this.arabic, o.arabic);
}
Aleksander Lech
  • 1,105
  • 12
  • 16