index_of.c

// Compile with "-mavx2 -std=c99 -flax-vector-conversions -O3"

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <immintrin.h>
#include <time.h>
#include <sys/time.h>

#define TEST_ITER 10000
#define SIZE 2000000
//#define PRINT

static int linear(const int *a, int n, int key) {
    for(int i = 0; i < n; i++) {
        if(a[i] == key) {
            return i;
        }
    }

    return -1;
}

static int binary(const int *a, int n, int key) {
    int l = 0, h = n;
    while(l <= h) {
        int m = (l + h) >> 1;
        if(a[m] < key) {
            l = m + 1;
        } else if(a[m] > key) {
            h = m - 1;
        } else {
            return m;
        }
    }

    return -1;
}

static int intrinsic_search (const int *arr, int n, int key)  {
    __m256i *arr256 = (__m256i*) arr;
    __m256i key256 = _mm256_set1_epi32(key);

    int res = -1, i = 0;
    for (i = 0; i < n / 8; i++) {
        __m256i tmp = _mm256_cmpeq_epi32(key256, arr256[i]);
        int result = _mm256_movemask_epi8(tmp);

        if(result != 0) {
            return i * 8 + __builtin_ctz(result) / 4;
        }
    }

    return -1;
}

static long long current_time() {
    struct timeval te;
    gettimeofday(&te, NULL); // get current time
    long long milliseconds = te.tv_sec*1000LL + te.tv_usec/1000; // caculate milliseconds
    // printf("milliseconds: %lld\n", milliseconds);
    return milliseconds;
}

int main() {
    // Test data
    int a[SIZE];
    for(int i = 0; i < SIZE; i++) {
        a[i] = i;
    }

    // Keys to search
    int key[TEST_ITER];
    for(int i = 0; i < TEST_ITER; i++) {
        key[i] = a[rand() % SIZE];
    }

    int r;
    long long start, end;

    // Intrinsic
    start = current_time();
    for(int i = 0; i < TEST_ITER; i++) {
        r ^= intrinsic_search(a, SIZE, key[i]);

#ifdef PRINT
        printf("INTRINSIC %d\n", r);
#endif

    }
    end = current_time();
    long long tintrinsic = end - start;

    // Linear search
    start = current_time();
    for(int i = 0; i < TEST_ITER; i++) {
        r ^=  linear(a, SIZE, key[i]);

#ifdef PRINT
        printf("LINEAR %d\n", r);
#endif

    }
    end = current_time();
    long long tlinear = end - start;

    // Binary search
    start = current_time();
    for(int i = 0; i < TEST_ITER; i++) {
        r ^= binary(a, SIZE, key[i]);

#ifdef PRINT
        printf("BINARY %d\n", r);
#endif

    }
    end = current_time();
    long long tbinary = end - start;

    printf("%d\n", r);
    printf("INTRINSIC = %lld LINEAR = %lld BINARY = %lld\n", tintrinsic, tlinear, tbinary);

    return 0;
}