Optimization results

main.cpp

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

int main(int argc, char **argv) {
    int f = 96;
    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);

    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;
} 

nosetests.txt

running nosetests
running egg_info
writing annoy.egg-info/PKG-INFO
writing dependency_links to annoy.egg-info/dependency_links.txt
writing top-level names to annoy.egg-info/top_level.txt
reading manifest file 'annoy.egg-info/SOURCES.txt'
reading manifest template 'MANIFEST.in'
writing manifest file 'annoy.egg-info/SOURCES.txt'
building 'annoy.annoylib' extension
gcc -pthread -Wno-unused-result -Wsign-compare -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -fPIC -I/home/rene/.pyenv/versions/3.6.4/include/python3.6m -c src/annoymodule.cc -o build/temp.linux-x86_64-3.6/src/annoymodule.o -O3 -ffast-math -fno-associative-math -march=native
cc1plus: warning: command line option ‘-Wstrict-prototypes’ is valid for C/ObjC but not for C++
src/annoymodule.cc: In function ‘int py_an_init(py_annoy*, PyObject*, PyObject*)’:
src/annoymodule.cc:148:12: warning: converting to non-pointer type ‘int’ from NULL [-Wconversion-null]
     return NULL;
            ^
g++ -pthread -shared -L/home/rene/.pyenv/versions/3.6.4/lib -L/home/rene/.pyenv/versions/3.6.4/lib build/temp.linux-x86_64-3.6/src/annoymodule.o -o build/lib.linux-x86_64-3.6/annoy/annoylib.cpython-36m-x86_64-linux-gnu.so
copying build/lib.linux-x86_64-3.6/annoy/annoylib.cpython-36m-x86_64-linux-gnu.so -> annoy
/home/rene/repositories/annoy/.eggs/nose-1.3.7-py3.6.egg/nose/config.py:435: DeprecationWarning: Use of multiple -w arguments is deprecated and support may be removed in a future release. You can get the same behavior by passing directories without the -w argument on the command line, or by using the --tests argument in a configuration file.
  DeprecationWarning)
......F.FFF
======================================================================
FAIL: test_large_index (euclidean_index_test.EuclideanIndexTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/rene/repositories/annoy/test/euclidean_index_test.py", line 69, in test_large_index
    self.assertEqual(i.get_nns_by_item(j, 2), [j, j+1])
AssertionError: Lists differ: [6, 4454] != [6, 7]

First differing element 1:
4454
7

- [6, 4454]
+ [6, 7]

======================================================================
FAIL: test_precision_10 (euclidean_index_test.EuclideanIndexTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/rene/repositories/annoy/test/euclidean_index_test.py", line 97, in test_precision_10
    self.assertTrue(self.precision(10) >= 0.98)
  File "/home/rene/repositories/annoy/test/euclidean_index_test.py", line 87, in precision
    self.assertEqual(nns, sorted(nns))  # should be in order
AssertionError: Lists differ: [0, 1, 2, 3, 4, 5, 7, 6, 8, 9] != [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

First differing element 6:
7
6

- [0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
?                       ---

+ [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
?                    +++


======================================================================
FAIL: test_precision_100 (euclidean_index_test.EuclideanIndexTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/rene/repositories/annoy/test/euclidean_index_test.py", line 100, in test_precision_100
    self.assertTrue(self.precision(100) >= 0.98)
  File "/home/rene/repositories/annoy/test/euclidean_index_test.py", line 87, in precision
    self.assertEqual(nns, sorted(nns))  # should be in order
AssertionError: Lists differ: [0, 1[22 chars] 9, 11, 10, 12, 13, 14, 16, 15, 17, 19, 22, 18[314 chars] 104] != [0, 1[22 chars] 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20[314 chars] 104]

First differing element 10:
11
10

Diff is 1113 characters long. Set self.maxDiff to None to see it.

======================================================================
FAIL: test_precision_1000 (euclidean_index_test.EuclideanIndexTest)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/rene/repositories/annoy/test/euclidean_index_test.py", line 103, in test_precision_1000
    self.assertTrue(self.precision(1000) >= 0.98)
  File "/home/rene/repositories/annoy/test/euclidean_index_test.py", line 87, in precision
    self.assertEqual(nns, sorted(nns))  # should be in order
AssertionError: Lists differ: [0, 1[34 chars]12, 14, 13, 15, 17, 16, 19, 20, 18, 22, 23, 21[4827 chars]1064] != [0, 1[34 chars]12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23[4827 chars]1064]

First differing element 13:
14
13

Diff is 16557 characters long. Set self.maxDiff to None to see it.

----------------------------------------------------------------------
Ran 11 tests in 5.319s

FAILED (failures=4)
python setup.py nosetests -w test/euclidean_index_test.py  8.22s user 0.88s system 105% cpu 8.645 total

results.txt

f=96
Function manually optimized
Adding items
Building index
Building took 33.94s
Searching took 10.102 ms
Searching took 9.222 ms
Searching took 8.694 ms
Searching took 9.772 ms
Searching took 10.022 ms
Searching took 9.034 ms
Searching took 9.668 ms
Searching took 8.923 ms
Searching took 9.857 ms
Searching took 9.277 ms
Done

f=96
Function not manually optimized
Adding items
Building index
Building took 44.009s
Searching took 13.134 ms
Searching took 13.463 ms
Searching took 13.718 ms
Searching took 13.314 ms
Searching took 13.637 ms
Searching took 12.986 ms
Searching took 13.579 ms
Searching took 12.681 ms
Searching took 12.71 ms
Searching took 12.828 ms
Done

f=100
Function manually optimized
Adding items
Building index
Building took 37.088s
Searching took 9.02 ms
Searching took 8.755 ms
Searching took 8.62 ms
Searching took 8.549 ms
Searching took 8.697 ms
Searching took 8.601 ms
Searching took 8.836 ms
Searching took 9.683 ms
Searching took 9.039 ms
Searching took 8.858 ms
Done

f=100
Function not manually optimized
Adding items
Building index
Building took 47.327s
Searching took 15.212 ms
Searching took 13.992 ms
Searching took 13.62 ms
Searching took 14.959 ms
Searching took 15.717 ms
Searching took 14.335 ms
Searching took 20 ms
Searching took 15.597 ms
Searching took 13.994 ms
Searching took 15.152 ms
Done