itsbonczek/kingpin — pull request #20 by stanislaw (2014-03-07 13:39:34+00:00)
Title: 10-12x faster tree build

Hello.

This was the following comment that recently draw my attention:

```
//TODO: build the tree without sorting at every level
```

This pull request addresses this issue and brings the following performance improvements for kingpin (I have Mac Air mid-2012 and tested on iOS simulator with `kNumberOfTestAnnotations = 20000`):

Results for current kingpin:
```
The block have been run 5 times. Average is: 890.800232 milliseconds
The block have been run 5 times. Average is: 887.177490 milliseconds
```

Results for kingpin with this PR on top:
```
The block have been run 5 times. Average is: 74.901153 milliseconds
The block have been run 5 times. Average is: 76.188117 milliseconds
```

----

Sorry for the following TLDR but, I promise, it is worth reading.

Here are modifications and improvements I've made to address this goal:

1. Kingpin now implements the what is described as "A novel tree-building algorithm" (follow these lines on http://en.wikipedia.org/wiki/K-d_tree). Sorting of original array by x and y is now done only once before building a tree.

2. A large number of needless branching: "X or Y" is eliminated. This is done in both building methods and the search method. As a result of this, the method `-buildTree:annotationsY:count: level:` may seem like having a two pieces of very similar code - __it is done intentionally__ to eliminate "if (X or Y)" checks inside both of these similar pieces.

3. MKMapPointForCoordinate is now calculated only once for each annotation right before building of a tree. I did separate performance measuments for this - this obvious optimization step did also bring small speedup and DIY: both logical and operational.

4. C level struct `kp_internal_annotation` is introduced to make possible the what is described in previous 3: these structs serve as containers for both `id ` annotations and their once-precalculated MKMapPoints. Also these structs and arrays of them allow to eliminate NSObject-based allocations (NSArray and NSIndexSet) and more importantly: __they allow to skip allocations of corresponding containers on every level of depth__.

5. KP_LIKELY macros, based on __builtin_expect, is used for branch prediction. The performance gain from this is expected to be very small, but it is still logically good to predict branches which are likely to occur often and often.

6. KPTreeController now has `Benchmark` method that can allow you measure the performance. I find this method very helpful in many situations, so I hope it would not be completely irrelevant for you as well.

----

P.S. I really hope that I didn't miss or overlook something that might make this PR corrupted.