Another Speed Boost Possible?

Question

Thanks to the respondents on this question (http://stackoverflow.com/questions/1396949/this-loop-is-very-slow-i-think-because-i-create-a-lot-of-intermediate-strings-h) I was able to speed up my code many orders of magnitude.

I think I can probably do a bit better though. Is it possible to avoid the creation of a bunch of NSString's here, and instead split the big NSString (routeGeom) into a bunch of char buffers and iterate through those?

I have never done any C programming, so if you know how to get this done, it would be much appreciated!

NSTimeInterval start = [NSDate timeIntervalSinceReferenceDate];

NSString *routeGeom = [pieces objectAtIndex:1];
NSArray *splitPoints = [routeGeom componentsSeparatedByString:@"],["];

routePoints = malloc(sizeof(CLLocationCoordinate2D) * ([splitPoints count] + 1));

int i=0;
for (NSString* coordStr in splitPoints) {

  char *buf = [coordStr UTF8String];
  sscanf(buf, "%f,%f,", &routePoints[i].latitude, &routePoints[i].longitude);

  i++;

}

Answer 1

char *buf = [routeGeom UTF8String];
int bestGuess = 1 << (whatever);
routePoints = malloc(sizeof(CLLocationCoordinate2D) * bestGuess);
for (int i = 0; buf != NULL; buf = strchr(buf+1,'['), ++i) {
  if (i >= bestGuess) {
      bestGuess <<= 1;
      routePoints = realloc(routePoints, sizeof(CLLocationCoordinate2D) * bestGuess);
  }
  sscanf(buf+1, "%f,%f,", &(routePoints + i)->latitude, &(routePoints + i)->longitude);
}

Pick a good starting value for (whatever) so that 2^whatever is representative of an average number of points in a route. If you can't, you could try guessing the number based on the length of the string. Otherwise, if you want to be exact, you could parse the string twice, first counting, then create routePoints, then parse the data, in which case you wouldn't need the realloc section.

Edit:

Another option. This assumes that CLLocationCoordinate2D is simply a struct of 2 floats, in the same order as the data in the string.

char *buf = [routeGeom UTF8String];
int bestGuess = 1 << (whatever);
float *tmpFloats = (float *)malloc(sizeof(float) * bestGuess);
float *index = tmpFloats;
for (int i = 0; buf != NULL; buf = strchr(buf+1,'['), ++i, index += 2) {
  if (i >= bestGuess) {
    bestGuess <<= 1;
    tmpFloats = (float *)realloc(tmpFloats, sizeof(float) * bestGuess);
  }
  sscanf(buf+1, "%f,%f,", index, index + 1);
}
CLLocationCoordinate2D *routePoints = (CLLocationCoordinate2D *)tmpFloats;

Answer 2

You should really be using NSScanner for this task -- bitbanging for miniscule performance increases really isn't worth the time.

Answer 3

Remove the realloc, theres a better way to do it. Also you shouldnt iterate over a loop using arrayname[index]. Instead use a pointer, ie

int array[5000];
int* intPointer = &array;
for(int i=0;i<5000;i++,intPointer++)
    *intPointer = something

Doing &routePoints[i] forces the CPU to do a '&routePoints + i*sizeof(CLLocationCoordinate2D)" multiple times per loop.

I would strongly recommend you get a book on C and learn it. You will benefit in the long run.

I know this answer does not immediately help you, but taking a really long string and breaking it up into smaller strings using C is actually a very common and simple thing to do (in a very fast and efficient way).