Test binary vs linear search on already sorted array, experiment suggests using linear up to < 16 elements

main.m

//
//  main.m
//  TestSearch
//
//  Created by Mikael Sand on 30/12/2017.
//  Copyright © 2017 Mikael Sand. All rights reserved.
//

#import <Foundation/Foundation.h>
#include <mach/mach_time.h>
#include <stdint.h>

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int maxSize = 64;
        int reps = 1024;
        NSMutableArray<NSMutableArray<NSNumber*>*>* arrs = [NSMutableArray arrayWithCapacity:maxSize];
        for (int size = 0; size < maxSize; size++) {
            NSMutableArray<NSNumber*>* arr = [NSMutableArray arrayWithCapacity:size];
            for (int i = 0; i < size; i++) {
                arr[i] = [NSNumber numberWithDouble:i];
            }
            arrs[size] = arr;
        }
        NSMutableArray<NSNumber*>* lin = [NSMutableArray arrayWithCapacity:maxSize];
        NSMutableArray<NSNumber*>* bin = [NSMutableArray arrayWithCapacity:maxSize];
        mach_timebase_info_data_t info;
        mach_timebase_info(&info);
        for (int size = 0; size < maxSize; size++) {
            NSMutableArray<NSNumber*>* arr = arrs[size];
            uint64_t startTime = mach_absolute_time();
            for (int r = 0; r < reps; r++) {
                for (int l = 0; l < size; l++) {
                    [arr
                       indexOfObjectPassingTest:^(NSNumber* length, NSUInteger index, BOOL * _Nonnull stop) {
                           BOOL contains = l <= [length doubleValue];
                           return contains;
                       }];
                }
            }
            uint64_t linTime = mach_absolute_time();
            for (int r = 0; r < reps; r++) {
                for (int l = 0; l < size; l++) {
                    [arr
                       indexOfObject:[NSNumber numberWithDouble:l]
                       inSortedRange:NSMakeRange(0, size)
                       options:NSBinarySearchingInsertionIndex
                       usingComparator:^(NSNumber* obj1, NSNumber* obj2) {
                           return [obj1 compare:obj2];
                       }];
                }
            }
            uint64_t binTime = mach_absolute_time();
            uint64_t elapsedLinMTU = linTime - startTime;
            uint64_t elapsedBinMTU = binTime - linTime;
            
            // Get elapsed time in nanoseconds:
            double elapsedLinNS = (double)elapsedLinMTU * (double)info.numer / (double)info.denom;
            double elapsedBinNS = (double)elapsedBinMTU * (double)info.numer / (double)info.denom;
            lin[size] = [NSNumber numberWithDouble:elapsedLinNS];
            bin[size] = [NSNumber numberWithDouble:elapsedBinNS];
        }
        
        for (int size = 0; size < maxSize; size++) {
            int linT = [lin[size] intValue];
            int binT = [bin[size] intValue];
            NSLog(@"%@", [NSString stringWithFormat:@"Size %d lin %d bin %d lin faster %d ", size, linT, binT, linT < binT]);
        }
    }
    return 0;
}