CODEWITHSUNDEEP
iosobjective-cperformanceloopsiteration
Hendrik
Hendrik

Reputation: 3

unexpected iteration performance drops

I'm currently developing a clustering framework for points of interests on a map view. To generate the clusters i am currently using a slow, but very precise algorithm.

while(self.clusteringData.count>=2){
    minDistance = DBL_MAX;
    for (ClusterAnnotation *objectA in self.clusteringData) {
        for (ClusterAnnotation *objectB in self.clusteringData) {
            if (objectA != objectB) {

                locationA.latitude = objectA.latitude;
                locationA.longitude = objectA.longitude;
                locationB.latitude = objectB.latitude;
                locationB.longitude = objectB.longitude;

                CLLocationDistance distance = [ClusterBuilder distanceBetweenLocation:locationA andLocation:locationB];
                if(distance < minDistance){
                    minDistance = distance;
                    left = objectA;
                    right = objectB;

                    if(minDistance == 0.0){
                        break;
                    }
                }
            }
        }
        if(minDistance == 0.0){
            break;
        }
    }
    [self notifyDelegateClusteringProgress:((float)i/(float)j)];

    ClusterTree* newRoot = [[ClusterTree alloc] initWithLeftClusterAnnotation:left rightClusterAnnotation:right];
    [newRoot setDistance:minDistance];
    [self.clusteringData addObject:newRoot];

    [self.clusteringData removeObject:left];
    [self.clusteringData removeObject:right];

    left = nil;
    right = nil;
    root = newRoot;
}

The first iterations are pretty fast - even though they should be the slowest. However the performance gets worse with each iteration and then gets better as the items left to cluster decrease.

I know i cant expect good performance when using an O(n^3)-Algorithm, but the first iteration takes about 0.009 seconds and that time increases with each iteration (even though it should decrease because the algorithm decreases the data by 1 item each iteration). I can't explain to myself why that happens.

I mesured the time each iteration of the while loop takes for 1000 items. http://pastebin.com/8XsZuEks

The clustering thread runs on DISPATCH_QUEUE_PRIORITY_HIGH and uses 99% of the CPU throughout the whole clustering process. Running the process on the main cue, did not fix the performance drop. So i guess its not a GCD/priority issue.

Upvotes: 0

Views: 69

Answers (2)

Putz1103
Putz1103

Reputation: 6211

Your iteration loop has breaks built into it, meaning that it doesn't always complete the full array every time. The performance changes are due to your populated array and the breaks.

Just think if you didn't have those breaks and every iteration took over 1.3 seconds (like your worst case in your link)...

Upvotes: 1

drhr
drhr

Reputation: 2281

Try printing the number of objects in the list along with the iteration time. Maybe something weird is happening with the number of objects?

Other than that, obviously profiling is important before you do any optimization work.

With only 1000 objects, this might be a waste of time, but you might consider replacing the Objective-C message call in the inner loop body with an IMP function pointer call. Regular C calls I believe are ~4-5x faster than messaging. Not a huge difference, in terms of clock cycles, but if your data has potential to grow in magnitude, it might be worth it.

Upvotes: 0

Related Questions