Test linear vs binary search speed

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define LIKELY(x)   __builtin_expect(!!(x), 1)
#define UNLIKELY(x) __builtin_expect(!!(x), 0)

// Linear search function
int linear_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (UNLIKELY(arr[i] == target))
            return i;
    }
    return -1;
}

int linear_search_no_branch(int arr[], int n, int target) {
    int mask = -1;
    for (int i = 0; i < n; i++) {
        mask = (arr[i] == target) ? i : mask;
    }
    return mask;
}

// Binary search function
int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

int binary_search_no_branch(int arr[], int n, int target) {
    int left = 0, length = n - 1, result = -1;
    while (length >= 1) {
        int mid = left + length / 2;
        result = (arr[mid] == target) ? mid : result;
        left = (arr[mid] < target) ? mid + 1 : left;
        length = length / 2;
    }

    return arr[left] == target ? left : result;
}

int binary_search_no_branch_depth(int arr[], int n, int target, int depth) {
    int left = 0, right = n - 1, result = -1;
    for (int i = 0; i < depth; i++) {
        int mid = left + (right - left) / 2;
        result = (arr[mid] == target) ? mid : result;
        left = (arr[mid] < target) ? mid + 1 : left;
        right = (arr[mid] > target) ? mid - 1 : right;
    }
    return result;
}

int binary_search_no_branch_8(int arr[], int target) {
    return binary_search_no_branch_depth(arr, 8, target, 4);
}

int binary_search_no_branch_16(int arr[], int target) {
    return binary_search_no_branch_depth(arr, 16, target, 5);
}

// Struct for benchmark configuration
typedef struct {
    int array_size;
    int repetitions;
    bool last;
} BenchmarkConfig;

// Benchmark function
void benchmark_search(int size, int repetitions, bool last) {
    int *arr = malloc(size * sizeof(int));
    if (!arr) {
        perror("Memory allocation failed");
        return;
    }

    // Seed random number generator
    srand((unsigned int)time(NULL));

    // Fill array with ascending numbers
    for (int i = 0; i < size; i++) {
        arr[i] = i * 100 + rand() % 10;
    }

    // Create array of targets to search
    int *targets = malloc(repetitions * sizeof(int));
    if (!targets) {
        perror("Target array allocation failed");
        free(arr);
        return;
    }

    for (int i = 0; i < repetitions; i++) {
        targets[i] = last ? 1000000 + rand() % 1000 : arr[rand() % size];
    }

    struct timespec start, end;
    int r = 0;

    // Linear search benchmark
    clock_gettime(CLOCK_MONOTONIC, &start);
    if (size == 8) {
        for (int i = 0; i < repetitions; i++) {
            r += linear_search(arr, 8, targets[i]);
        }
    } else if (size == 16) {
        for (int i = 0; i < repetitions; i++) {
            r += linear_search(arr, 16, targets[i]);
        }
    } else {
        for (int i = 0; i < repetitions; i++) {
            r += linear_search(arr, size, targets[i]);
        }
    }
    clock_gettime(CLOCK_MONOTONIC, &end);
    long linear_time_ns = (end.tv_sec - start.tv_sec) * 1e9 + (end.tv_nsec - start.tv_nsec);

    // Linear search no-br benchmark
    clock_gettime(CLOCK_MONOTONIC, &start);
    if (size == 8) {
        for (int i = 0; i < repetitions; i++) {
            r += linear_search_no_branch(arr, size, targets[i]);
        }
    } else if (size == 16) {
        for (int i = 0; i < repetitions; i++) {
            r += linear_search_no_branch(arr, 16, targets[i]);
        }
    } else if (size == 32) {
        for (int i = 0; i < repetitions; i++) {
            r += linear_search_no_branch(arr, 32, targets[i]);
        }
    } else if (size == 64) {
        for (int i = 0; i < repetitions; i++) {
            r += linear_search_no_branch(arr, 64, targets[i]);
        }
    } else {
        for (int i = 0; i < repetitions; i++) {
            r += linear_search_no_branch(arr, size, targets[i]);
        }
    }
    clock_gettime(CLOCK_MONOTONIC, &end);
    long linear_nb_time_ns = (end.tv_sec - start.tv_sec) * 1e9 + (end.tv_nsec - start.tv_nsec);


    // Binary search benchmark
    clock_gettime(CLOCK_MONOTONIC, &start);
    if (size == 8) {
        for (int i = 0; i < repetitions; i++) {
            r += binary_search(arr, size, targets[i]);
        }
    } else if (size == 16) {
        for (int i = 0; i < repetitions; i++) {
            r += binary_search(arr, size, targets[i]);
        }
    } else {
        for (int i = 0; i < repetitions; i++) {
            r += binary_search(arr, size, targets[i]);
        }
    }
    clock_gettime(CLOCK_MONOTONIC, &end);
    long binary_time_ns = (end.tv_sec - start.tv_sec) * 1e9 + (end.tv_nsec - start.tv_nsec);

    // Binary search NB benchmark
    clock_gettime(CLOCK_MONOTONIC, &start);
    if (size == 8) {
        for (int i = 0; i < repetitions; i++) {
            r += binary_search_no_branch_8(arr, targets[i]);
        }
    } else if (size == 16) {
        for (int i = 0; i < repetitions; i++) {
            r += binary_search_no_branch_16(arr, targets[i]);
        }
    } else {
        for (int i = 0; i < repetitions; i++) {
            r += binary_search_no_branch(arr, size, targets[i]);
        }
    }
    clock_gettime(CLOCK_MONOTONIC, &end);
    long binary_nb_time_ns = (end.tv_sec - start.tv_sec) * 1e9 + (end.tv_nsec - start.tv_nsec);


    // Print results
    // printf("  Array size: %d, repeats: %d\n", size, repetitions);
    printf(
        "Arr size %5d, %6d iters %6s. Time ns/search: linear %6.2f ns | lin no-brnc %6.2f | bin %6.2f | bin no-br %6.2f  r: %d\n",
        size,
        repetitions,
        last ? "last" : "random",
        (double)linear_time_ns / repetitions,
        (double)linear_nb_time_ns / repetitions,
        (double)binary_time_ns / repetitions,
        (double)binary_nb_time_ns / repetitions,
        r
    );

    // Cleanup
    free(arr);
    free(targets);
}

int main() {
    // Default benchmark configurations
    BenchmarkConfig configs[] = {
        {8, 200000, false},
        {16, 200000, false},
        {32, 100000, false},
        {64, 100000, false},
        {128, 100000, false} ,
        {256, 100000, false},
        {1024, 10000, false},
        {16384, 10000, false},
        {8, 200000, true},
        {16, 200000, true},
        {32, 100000, true},
        {64, 100000, true},
        {16384, 10000, true}
        // Add more configurations here as needed
    };

    int num_configs = sizeof(configs) / sizeof(configs[0]);

    for (int i = 0; i < num_configs; i++) {
        benchmark_search(configs[i].array_size, configs[i].repetitions, configs[i].last);
    }

    int numbers[] = { 0, 10, 20, 30, 40, 50, 60, 70 };
    int targets[] = { 0, 70, 50, 40, 30, 20, 60, 10, 1, 5, 100 };
    for (int i = 0; i < sizeof(targets)/sizeof(int); i++) {
        int target = targets[i];
        printf("Src %d - lin %d, lin NB %d, bin %d, bin NB %d, bin NB 8 %d\n",
            target,
            linear_search(numbers, 8, target),
            linear_search_no_branch(numbers, 8, target),
            binary_search(numbers, 8, target),
            binary_search_no_branch(numbers, 8, target),
            binary_search_no_branch_8(numbers, target)
        );
    }

    return 0;
}