Vectorized euclidian and angular distance and verctorized dot product

Angular

Adding items
Building index
Building took 53.623s
Searching took 15.394 ms
Searching took 14.526 ms
Searching took 14.187 ms
Searching took 14.201 ms
Searching took 13.615 ms
Searching took 14.154 ms
Searching took 14.527 ms
Searching took 15.878 ms
Searching took 14.599 ms
Searching took 13.783 ms
Done
Adding items
Building index
Building took 55.126s
Searching took 14.255 ms
Searching took 13.622 ms
Searching took 13.773 ms
Searching took 13.697 ms
Searching took 13.639 ms
Searching took 13.695 ms
Searching took 14.218 ms
Searching took 14.564 ms
Searching took 14.203 ms
Searching took 13.72 ms
Done
Adding items
Building index
Building took 55.073s
Searching took 14.268 ms
Searching took 13.968 ms
Searching took 14.522 ms
Searching took 13.989 ms
Searching took 13.737 ms
Searching took 13.822 ms
Searching took 14.15 ms
Searching took 14.771 ms
Searching took 14.108 ms
Searching took 13.841 ms
Done
Adding items
Building index
Building took 55.906s
Searching took 14.373 ms
Searching took 13.791 ms
Searching took 13.956 ms
Searching took 13.693 ms
Searching took 13.725 ms
Searching took 13.806 ms
Searching took 14.401 ms
Searching took 14.721 ms
Searching took 14.084 ms
Searching took 13.661 ms
Done
Adding items
Building index
Building took 54.552s
Searching took 14.133 ms
Searching took 13.574 ms
Searching took 13.672 ms
Searching took 13.562 ms
Searching took 13.54 ms
Searching took 13.599 ms
Searching took 14.021 ms
Searching took 14.426 ms
Searching took 13.888 ms
Searching took 13.686 ms
Done

Angular AVX optimized

using AVX
Adding items
Building index
Building took 35.696s
Searching took 9.835 ms
Searching took 11.473 ms
Searching took 11.431 ms
Searching took 9.436 ms
Searching took 9.457 ms
Searching took 9.758 ms
Searching took 9.434 ms
Searching took 10.181 ms
Searching took 9.694 ms
Searching took 9.391 ms
Done
Adding items
Building index
Building took 35.152s
Searching took 9.577 ms
Searching took 9.684 ms
Searching took 9.063 ms
Searching took 8.742 ms
Searching took 9.124 ms
Searching took 10.148 ms
Searching took 9.241 ms
Searching took 9.777 ms
Searching took 9.681 ms
Searching took 9.165 ms
Done
Adding items
Building index
Building took 33.971s
Searching took 9.452 ms
Searching took 9.733 ms
Searching took 8.817 ms
Searching took 8.866 ms
Searching took 9.356 ms
Searching took 10.004 ms
Searching took 9.26 ms
Searching took 9.944 ms
Searching took 9.738 ms
Searching took 9.129 ms
Done
Adding items
Building index
Building took 34.034s
Searching took 9.592 ms
Searching took 9.619 ms
Searching took 8.856 ms
Searching took 8.807 ms
Searching took 9.103 ms
Searching took 9.807 ms
Searching took 9.213 ms
Searching took 9.667 ms
Searching took 9.915 ms
Searching took 9.115 ms
Done
Adding items
Building index
Building took 34.78s
Searching took 10.096 ms
Searching took 10.656 ms
Searching took 9.351 ms
Searching took 9.4 ms
Searching took 9.409 ms
Searching took 10.038 ms
Searching took 9.826 ms
Searching took 11.29 ms
Searching took 10.574 ms
Searching took 11.139 ms
Done

Euclidian

Adding items
Building index
Building took 47s
Searching took 13.156 ms
Searching took 12.981 ms
Searching took 12.801 ms
Searching took 12.753 ms
Searching took 12.77 ms
Searching took 12.801 ms
Searching took 12.8 ms
Searching took 12.873 ms
Searching took 12.687 ms
Searching took 12.802 ms
Done
Adding items
Building index
Building took 45.948s
Searching took 13.225 ms
Searching took 13.054 ms
Searching took 12.813 ms
Searching took 12.744 ms
Searching took 12.841 ms
Searching took 12.871 ms
Searching took 12.746 ms
Searching took 12.828 ms
Searching took 12.731 ms
Searching took 12.736 ms
Done
Adding items
Building index
Building took 47.08s
Searching took 13.228 ms
Searching took 13.067 ms
Searching took 12.872 ms
Searching took 12.835 ms
Searching took 12.792 ms
Searching took 12.913 ms
Searching took 12.765 ms
Searching took 12.791 ms
Searching took 12.665 ms
Searching took 12.811 ms
Done
Adding items
Building index
Building took 45.884s
Searching took 13.321 ms
Searching took 13.08 ms
Searching took 12.84 ms
Searching took 12.783 ms
Searching took 12.816 ms
Searching took 12.84 ms
Searching took 12.827 ms
Searching took 12.828 ms
Searching took 12.754 ms
Searching took 12.779 ms
Done
Adding items
Building index
Building took 46.238s
Searching took 13.243 ms
Searching took 13.031 ms
Searching took 12.793 ms
Searching took 12.763 ms
Searching took 12.775 ms
Searching took 12.859 ms
Searching took 12.81 ms
Searching took 12.833 ms
Searching took 12.731 ms
Searching took 12.818 ms
Done

Euclidian AVX optimized

using AVX
Adding items
Building index
Building took 25.607s
Searching took 9 ms
Searching took 8.981 ms
Searching took 9.106 ms
Searching took 8.318 ms
Searching took 8.572 ms
Searching took 8.999 ms
Searching took 8.673 ms
Searching took 8.445 ms
Searching took 8.352 ms
Searching took 9.246 ms
Done
Adding items
Building index
Building took 25.972s
Searching took 8.563 ms
Searching took 9.06 ms
Searching took 8.923 ms
Searching took 8.328 ms
Searching took 8.701 ms
Searching took 8.434 ms
Searching took 8.113 ms
Searching took 8.201 ms
Searching took 8.193 ms
Searching took 8.335 ms
Done
Adding items
Building index
Building took 24.636s
Searching took 8.669 ms
Searching took 9.098 ms
Searching took 9.177 ms
Searching took 9.398 ms
Searching took 9.2 ms
Searching took 8.686 ms
Searching took 8.079 ms
Searching took 8.585 ms
Searching took 9.087 ms
Searching took 8.643 ms
Done
Adding items
Building index
Building took 25.134s
Searching took 9.167 ms
Searching took 9.536 ms
Searching took 9.099 ms
Searching took 8.202 ms
Searching took 8.339 ms
Searching took 8.565 ms
Searching took 8.313 ms
Searching took 8.3 ms
Searching took 8.18 ms
Searching took 8.069 ms
Done
Adding items
Building index
Building took 24.344s
Searching took 8.632 ms
Searching took 8.715 ms
Searching took 9.304 ms
Searching took 8.19 ms
Searching took 8.346 ms
Searching took 8.539 ms
Searching took 8.538 ms
Searching took 8.375 ms
Searching took 8.256 ms
Searching took 8.03 ms
Done

main.cc

//#define NO_MANUAL_VECTORIZATION

#include <iostream>
#include <iomanip>
#include "../src/kissrandom.h"
#include "../src/annoylib.h"
#include <chrono>
#include <map>

int main(int argc, char **argv) {

#ifdef USE_AVX
    printf("using AVX\n");
#endif
#ifdef USE_SSE
    printf("using SSE\n");
#endif

    for (int i = 0; i < 5; i++) {
        int f = 100;
        int n = 100000;
        int prec_n = 10;

        std::chrono::high_resolution_clock::time_point t_start, t_end;

        std::default_random_engine generator;
        std::normal_distribution<float> distribution(0.0, 1.0);

//        AnnoyIndex<int, float, Euclidean, Kiss32Random> t = AnnoyIndex<int, float, Euclidean, Kiss32Random>(f);
        AnnoyIndex<int, float, Angular, Kiss32Random> t = AnnoyIndex<int, float, Angular, Kiss32Random>(f);

        std::cout << "Adding items" << std::endl;
        for (int i = 0; i < n; ++i) {
            auto *vec = (float *) malloc(f * sizeof(float));
            for (int z = 0; z < f; ++z) {
                vec[z] = (distribution(generator));
            }
            t.add_item(i, vec);
        }
        std::cout << "Building index" << std::endl;
        t_start = std::chrono::high_resolution_clock::now();
        t.build(2 * f);
        t_end = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t_end - t_start).count();
        std::cout << "Building took " << (duration / 1000.0) << "s" << std::endl;

        int K = 100;

        for (int i = 0; i < prec_n; ++i) {
            std::vector<int> closest;

            t_start = std::chrono::high_resolution_clock::now();
            t.get_nns_by_item(i, K, n, &closest, nullptr);
            t_end = std::chrono::high_resolution_clock::now();
            duration = std::chrono::duration_cast<std::chrono::microseconds>(t_end - t_start).count();
            std::cout << "Searching took " << (duration / 1000.0) << " ms" << std::endl;
        }

        std::cout << "Done" << std::endl;
    }

    return 0;
}