Graph-based Approximate Nearest Neighbor Search

I am attempting to move over to the new v0.5.0 release but am encountering this error while trying to get it setup:

$ pip install -e git://github.com/granne/[email protected]#egg=granne
Obtaining granne from git+git://github.com/granne/[email protected]#egg=granne
  Updating /home/gabe/Envs/granne-test/src/granne clone (to revision v0.5.0)
  Running command git fetch -q --tags
  Running command git reset --hard -q 662656d2cb0aa43558d826e7f1e7568afb2ea36d
  Installing build dependencies ... done
  Getting requirements to build wheel ... done
  Installing backend dependencies ... done
    Preparing wheel metadata ... done
Installing collected packages: granne
  Running setup.py develop for granne
    ERROR: Command errored out with exit status 1:
     command: /home/gabe/Envs/granne-test/bin/python3 -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/home/gabe/Envs/granne-test/src/granne/setup.py'"'"'; __file__='"'"'/home/gabe/Envs/granne-test/src/granne/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' develop --no-deps
         cwd: /home/gabe/Envs/granne-test/src/granne/
    Complete output (123 lines):
    running develop
    running egg_info
    writing granne.egg-info/PKG-INFO
    writing dependency_links to granne.egg-info/dependency_links.txt
    writing top-level names to granne.egg-info/top_level.txt
    writing manifest file 'granne.egg-info/SOURCES.txt'
    running build_ext
    running build_rust
           Fresh autocfg v1.0.0
           Fresh cfg-if v0.1.10
           Fresh lazy_static v1.4.0
           Fresh scopeguard v1.1.0
           Fresh regex-syntax v0.6.17
           Fresh smallvec v1.2.0
           Fresh ppv-lite86 v0.2.6
           Fresh adler32 v1.0.4
           Fresh itoa v0.4.5
           Fresh stable_deref_trait v1.1.1
           Fresh either v1.5.3
           Fresh thread_local v1.0.1
           Fresh lock_api v0.3.3
       Compiling granne v0.5.0 (/home/gabe/Envs/granne-test/src/granne)
         Running `/home/gabe/Envs/granne-test/src/granne/target/debug/build/granne-3065d63cc7adb6bb/build-script-build`
           Fresh libc v0.2.68
           Fresh maybe-uninit v2.0.0
           Fresh byteorder v1.3.4
           Fresh ryu v1.0.3
           Fresh serde v1.0.105
           Fresh memchr v2.3.3
           Fresh crc32fast v1.2.0
           Fresh num-traits v0.2.11
           Fresh getrandom v0.1.14
           Fresh num_cpus v1.12.0
           Fresh time v0.1.42
           Fresh parking_lot_core v0.7.0
           Fresh memmap v0.7.0
           Fresh madvise v0.1.0
           Fresh miniz_oxide v0.3.6
           Fresh owning_ref v0.4.1
           Fresh crossbeam-utils v0.7.2
           Fresh memoffset v0.5.4
           Fresh crossbeam-queue v0.2.1
           Fresh rand_core v0.5.1
           Fresh rand_chacha v0.2.2
           Fresh ordered-float v1.0.2
           Fresh aho-corasick v0.7.10
           Fresh crossbeam-epoch v0.8.2
           Fresh pbr v1.0.2
           Fresh parking_lot v0.10.0
           Fresh flate2 v1.0.14
           Fresh stream-vbyte v0.3.2
           Fresh serde_json v1.0.48
           Fresh fxhash v0.2.1
           Fresh regex v1.3.5
           Fresh crossbeam-deque v0.7.3
           Fresh rand v0.7.3
           Fresh rayon-core v1.7.0
           Fresh rayon v1.3.0
           Fresh python3-sys v0.4.1
           Fresh cpython v0.4.1
         Running `rustc --crate-name granne --edition=2018 src/lib.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type lib --emit=dep-info,metadata,link -C debuginfo=2 --cfg 'feature="default"' -C metadata=7d4dec9265969171 -C extra-filename=-7d4dec9265969171 --out-dir /home/gabe/Envs/granne-test/src/granne/target/debug/deps -C incremental=/home/gabe/Envs/granne-test/src/granne/target/debug/incremental -L dependency=/home/gabe/Envs/granne-test/src/granne/target/debug/deps --extern byteorder=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libbyteorder-0a48faa69a27c0a8.rmeta --extern flate2=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libflate2-5c9df00987ebb4d3.rmeta --extern fxhash=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libfxhash-a9584c0803658a1c.rmeta --extern madvise=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libmadvise-2bff7c02f1d9a0f6.rmeta --extern memmap=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libmemmap-3467cfb5935cea6b.rmeta --extern ordered_float=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libordered_float-49b58c9dad452031.rmeta --extern owning_ref=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libowning_ref-88449d183d98535d.rmeta --extern parking_lot=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libparking_lot-e29d0e72287e3d37.rmeta --extern pbr=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libpbr-df0b03d13e7090cb.rmeta --extern rand=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/librand-34f070eb1e7a7deb.rmeta --extern rayon=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/librayon-da71c033c21c80ff.rmeta --extern serde_json=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libserde_json-5fd5b5f28b6a28d5.rmeta --extern stream_vbyte=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libstream_vbyte-92918a05764be3c1.rmeta`
    error[E0308]: mismatched types
      --> src/elements/dense_vector.rs:86:17
       |
    86 |                 Self(self.0.into_owned())
       |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
       |
      ::: src/elements/angular.rs:53:1
       |
    53 | dense_vector!(f32);
       | ------------------- in this macro invocation
       |
       = note: expected struct `elements::angular::Vectors<'static>`
                  found struct `elements::angular::Vectors<'a>`
    note: the lifetime `'a` as defined on the impl at 40:14...
      --> src/elements/dense_vector.rs:40:14
       |
    40 |         impl<'a> Vectors<'a> {
       |              ^^
       |
      ::: src/elements/angular.rs:53:1
       |
    53 | dense_vector!(f32);
       | ------------------- in this macro invocation
       = note: ...does not necessarily outlive the static lifetime
       = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
    
    error[E0308]: mismatched types
      --> src/elements/dense_vector.rs:86:17
       |
    86 |                 Self(self.0.into_owned())
       |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
       |
      ::: src/elements/angular_int.rs:17:1
       |
    17 | dense_vector!(i8);
       | ------------------ in this macro invocation
       |
       = note: expected struct `elements::angular_int::Vectors<'static>`
                  found struct `elements::angular_int::Vectors<'a>`
    note: the lifetime `'a` as defined on the impl at 40:14...
      --> src/elements/dense_vector.rs:40:14
       |
    40 |         impl<'a> Vectors<'a> {
       |              ^^
       |
      ::: src/elements/angular_int.rs:17:1
       |
    17 | dense_vector!(i8);
       | ------------------ in this macro invocation
       = note: ...does not necessarily outlive the static lifetime
       = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
    
    error: aborting due to 2 previous errors
    
    For more information about this error, try `rustc --explain E0308`.
    error: could not compile `granne`.
    
    Caused by:
      process didn't exit successfully: `rustc --crate-name granne --edition=2018 src/lib.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type lib --emit=dep-info,metadata,link -C debuginfo=2 --cfg 'feature="default"' -C metadata=7d4dec9265969171 -C extra-filename=-7d4dec9265969171 --out-dir /home/gabe/Envs/granne-test/src/granne/target/debug/deps -C incremental=/home/gabe/Envs/granne-test/src/granne/target/debug/incremental -L dependency=/home/gabe/Envs/granne-test/src/granne/target/debug/deps --extern byteorder=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libbyteorder-0a48faa69a27c0a8.rmeta --extern flate2=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libflate2-5c9df00987ebb4d3.rmeta --extern fxhash=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libfxhash-a9584c0803658a1c.rmeta --extern madvise=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libmadvise-2bff7c02f1d9a0f6.rmeta --extern memmap=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libmemmap-3467cfb5935cea6b.rmeta --extern ordered_float=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libordered_float-49b58c9dad452031.rmeta --extern owning_ref=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libowning_ref-88449d183d98535d.rmeta --extern parking_lot=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libparking_lot-e29d0e72287e3d37.rmeta --extern pbr=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libpbr-df0b03d13e7090cb.rmeta --extern rand=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/librand-34f070eb1e7a7deb.rmeta --extern rayon=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/librayon-da71c033c21c80ff.rmeta --extern serde_json=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libserde_json-5fd5b5f28b6a28d5.rmeta --extern stream_vbyte=/home/gabe/Envs/granne-test/src/granne/target/debug/deps/libstream_vbyte-92918a05764be3c1.rmeta` (exit code: 1)
    cargo rustc --lib --manifest-path py/Cargo.toml --features cpython/extension-module cpython/python3-sys --verbose -- --crate-type cdylib
    error: cargo failed with code: 101
    
    ----------------------------------------
ERROR: Command errored out with exit status 1: /home/gabe/Envs/granne-test/bin/python3 -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'/home/gabe/Envs/granne-test/src/granne/setup.py'"'"'; __file__='"'"'/home/gabe/Envs/granne-test/src/granne/setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(__file__);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' develop --no-deps Check the logs for full command output.

I don't know rust so I'm a little lost with how to debug this.

Done:

• Use default toolchain, instead of nightly (because cpython=0.6 doesn't requires nightly)
• Get rid py35, add py38, py39, py310
• Replace manylinux1_x86_64 -> manylinux2010_x86_64
• Bump version to 0.5.2

Hello, I'm wondering what the intended use for the reorder method of Granne is. I would like to take advantage of better cache locality but I'm not quite sure when/how to use it. How can I incorporate this into my indexing workflow which currently looks like:

DIMENSION = 512
ELEMENT_TYPE = "angular"

builder = granne.GranneBuilder("angular")
metadata = []
for _ in range(100000):
    metadata.append("some metadata about this element")
    vec = np.random.rand(DIMENSION) - 0.5
    builder.append(vec)

builder.build()
builder.save_index(fname_idx)
builder.save_elements(fnames_elem)

First of all: Great work with Granne, absolutely impressive performance!

Unfortunately I have been getting an error trying to build the Python module with the latest commits.

error[E0308]: mismatched types
      --> src/elements/dense_vector.rs:86:17
       |
    86 |                 Self(self.0.into_owned())
       |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
       |
      ::: src/elements/angular.rs:53:1
       |
    53 | dense_vector!(f32);
       | ------------------- in this macro invocation
       |
       = note: expected struct `elements::angular::Vectors<'static>`
                  found struct `elements::angular::Vectors<'a>`
    note: the lifetime `'a` as defined on the impl at 40:14...
      --> src/elements/dense_vector.rs:40:14
       |
    40 |         impl<'a> Vectors<'a> {
       |              ^^
       |
      ::: src/elements/angular.rs:53:1
       |
    53 | dense_vector!(f32);
       | ------------------- in this macro invocation
       = note: ...does not necessarily outlive the static lifetime
       = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
    
    error[E0308]: mismatched types
      --> src/elements/dense_vector.rs:86:17
       |
    86 |                 Self(self.0.into_owned())
       |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
       |
      ::: src/elements/angular_int.rs:17:1
       |
    17 | dense_vector!(i8);
       | ------------------ in this macro invocation
       |
       = note: expected struct `elements::angular_int::Vectors<'static>`
                  found struct `elements::angular_int::Vectors<'a>`
    note: the lifetime `'a` as defined on the impl at 40:14...
      --> src/elements/dense_vector.rs:40:14
       |
    40 |         impl<'a> Vectors<'a> {
       |              ^^
       |
      ::: src/elements/angular_int.rs:17:1
       |
    17 | dense_vector!(i8);
       | ------------------ in this macro invocation
       = note: ...does not necessarily outlive the static lifetime
       = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)
    
    error: aborting due to 2 previous errors
    
    For more information about this error, try `rustc --explain E0308`.
    error: could not compile `granne`.

I could narrow it down to 7de618b09b8b68d04270d4ac9036b392dc098e6a. It seems that there is an issue with using nightly, as cargo +nightly bench gives a similar error already with earlier commits. I would love to get deeper into this but alas my knowledge of Rust is definitely only superficial.

When running the build_and_search.py example I get the following error after changing the configuration to

DIM = 256
NUM_VECTORS = 100000
NUM_LAYERS = 100

Saving to disk
thread '<unnamed>' panicked at 'assertion failed: metadata.len() <= METADATA_LEN', /tmp/pip-req-build-xonb6jzo/src/hnsw/io.rs:71:5
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.37/src/backtrace/libunwind.rs:88
   1: backtrace::backtrace::trace_unsynchronized
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.37/src/backtrace/mod.rs:66
   2: std::sys_common::backtrace::_print_fmt
             at src/libstd/sys_common/backtrace.rs:76
   3: <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt
             at src/libstd/sys_common/backtrace.rs:60
   4: core::fmt::write
             at src/libcore/fmt/mod.rs:1030
   5: std::io::Write::write_fmt
             at src/libstd/io/mod.rs:1412
   6: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:64
   7: std::sys_common::backtrace::print
             at src/libstd/sys_common/backtrace.rs:49
   8: std::panicking::default_hook::{{closure}}
             at src/libstd/panicking.rs:196
   9: std::panicking::default_hook
             at src/libstd/panicking.rs:210
  10: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:473
  11: std::panicking::begin_panic
  12: granne::hnsw::io::save_index_to_disk
  13: granne::hnsw::HnswBuilder<Elements,Element>::save_index_to_disk
  14: granne::HnswBuilder::save_index
  15: cpython::objects::string::<impl cpython::conversion::RefFromPyObject for str>::with_extracted
  16: std::panicking::try::do_call
  17: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:80
  18: cpython::function::handle_callback
  19: granne::HnswBuilder::create_instance::init::wrap_instance_method
  20: PyCFunction_Call
  21: PyEval_EvalFrameEx
  22: <unknown>
  23: PyEval_EvalCode
  24: <unknown>
  25: PyRun_FileExFlags
  26: PyRun_SimpleFileExFlags
  27: Py_Main
  28: main
  29: __libc_start_main
  30: _start
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
Traceback (most recent call last):
  File "examples/py/build_and_search.py", line 32, in <module>
    builder.save_index(INDEX_PATH)
SystemError: Rust panic

I guess a separate question is how to choose an appropriate number of layers.

When running granne/examples/py/build_and_search.py I get the following error:

thread '<unnamed>' panicked at 'assertion failed: metadata.len() <= METADATA_LEN', /tmp/pip-req-build-3bq0acsr/src/hnsw/io.rs:71:5
---------------------------------------------------------------------------
SystemError                               Traceback (most recent call last)
<ipython-input-8-1b56a13d105e> in <module>()
     30 
     31 print("Saving to disk")
---> 32 builder.save_index(INDEX_PATH)
     33 builder.save_elements(ELEMENTS_PATH)
     34 

SystemError: Rust panic

I'm on Ubuntu 18.04. Let me know what other debug info would be useful.

Is there a way, from Python, to query the distance between any two arbitrary elements? I know I can retrieve the vectors and compute the distance myself but I want to be sure the distance is computed with exactly the same metric that granne uses internally.

A lock guard needs to be assigned to a binding that's not _ because doing otherwise creates a guard that's dropped immediately, releasing the lock. In other words:

let _ = my_lock.write().unlock();

is equivalent to

my_lock.write().unwrap();

I noticed this purely by accident while exploring this repo a bit, after seeing it linked from https://0x65.dev/blog/2019-12-06/building-a-search-engine-from-scratch.html

Dear granny team,

This is Jianshu, a bioinformatics phd student at Georgia Tech. I am writing to you to ask your interest to form a new collaboration. Specifically, applying HNSW into genome classification problems, that is to find the closest genome in a big genome database to see the close related ones in the database so that enivronmental microbiologist can tell what taxonomy the query genome is. This will have a very big impact on the field and will definitely have a lot of citations. I want to completely rely on rust for this project without using any other language considering the advantages compared to C++ and python. I am not an expert in rust but have been using it for 2 years. The biology needed and taxonomy related information will be my strong part. I also know all the classification software in this field and have benign using/modifying them for my master and half of my Ph.D I am confident that HNSW in rust will greatly improved the speed of genome classifiers. Hopefully we can come up with a paper in the end. My email is [email protected]

Let me know if you are interest and if something I mentioned above is not clear.

Many thanks,

Jianshu

On master setup.py imports Binding and RustExtension on line 2 even though setuptools_rust is a dependency of granne so it is not guaranteed it will be installed yet.

This caused the the following error for me:

pip install -e .
    Complete output (5 lines):
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "/home/gabe/code/granne/setup.py", line 2, in <module>
        from setuptools_rust import Binding, RustExtension
    ImportError: No module named 'setuptools_rust'
    ----------------------------------------
ERROR: Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.

I'll submit a PR with a fix shortly.

Is there a recommended best practice for storing an ID along with a vector?

My use case is sentence embedding. I have many passages of text, and I'd like to be able to search that embedding.

However, the problem is I'm trying to think of an optimal strategy to link a vector back to the original text. Near as I can tell, the IDs returned when running a search() are related to the order of insertion (i.e. first inserted index 0, second has index 1, etc.).

Some ideas I thought of:

• storing the vector ID in another database to provide mapping, but this would be a lot of boilerplate and complexity. I expect to need to remove items from the index from time to time as well which further complicates.
• add a column in my embedding vector to store a numerical ID (but this might affect accuracy, if there's stray data)

Any recommendations?

Hello granne team, I am wondering whether the angular distance by default can be any other metric distance like L1, L2, Cosine, Jaccard, Hamming distance? Another HNSW implementation provide such distances:https://github.com/jean-pierreBoth/hnswlib-rs

Thanks,

Jianshu

I got an deadlock on index building using python bindings on pytest. This reproduced only with specific test order (that's wired).

I can't share full tests (sorry for that), but can mention important parts

Granne version: 0.5.2 Python version: 3.8

Code called in both tests looks like

import granne

index_builder = granne.GranneBuilder('angular', 500)
for v in vectors:  # no matters how much `vectors` or dimensions
    index_builder.append(v)

index_builder.build()  # < - deadlock happens here

I traced them using py-spy and got stack that looks like

Thread 73895 (idle): "MainThread"
    pthread_cond_wait@@GLIBC_2.3.2 (libpthread-2.31.so)
    core::sync::atomic::atomic_load::h40d363a33a87228c (atomic.rs:2353)
    core::sync::atomic::AtomicBool::load::h98755e393c876abe (atomic.rs:378)
    std::sys_common::poison::Flag::get::hf277343eec2966e7 (poison.rs:44)
    std::sync::condvar::Condvar::wait::h14c20325128edf7e (condvar.rs:189)
    rayon_core::latch::LockLatch::wait_and_reset::h1c8244bf740f09b9 (latch.rs:240)
    rayon_core::registry::Registry::in_worker_cold::_$u7b$$u7b$closure$u7d$$u7d$::hc01231cc1f5776b3 (registry.rs:475)
    std::thread::local::LocalKey$LT$T$GT$::try_with::hcb9dc379c39268fa (local.rs:272)
    std::thread::local::LocalKey$LT$T$GT$::with::h340944f8b882cf1f (local.rs:248)
    rayon_core::registry::Registry::in_worker_cold::hd65bc2a269d982ed (registry.rs:458)
    rayon_core::registry::in_worker::ha625d863b1ab5202 (registry.rs:877)
    rayon::iter::plumbing::bridge_producer_consumer::helper::h161e56cd8915cee0 (mod.rs:436)
    _$LT$$LT$rayon..iter..skip..Skip$LT$I$GT$$u20$as$u20$rayon..iter..IndexedParallelIterator$GT$..with_producer..Callback$LT$CB$GT$$u20$as$u20$rayon..iter..plumbing..ProducerCallback$LT$T$GT$$GT$::callback::hbff8b682fd113b73 (skip.rs:85)
    _$LT$$LT$rayon..iter..enumerate..Enumerate$LT$I$GT$$u20$as$u20$rayon..iter..IndexedParallelIterator$GT$..with_producer..Callback$LT$CB$GT$$u20$as$u20$rayon..iter..plumbing..ProducerCallback$LT$I$GT$$GT$::callback::h12880f40ae46697b (enumerate.rs:79)
    _$LT$alloc..raw_vec..RawVec$LT$T$C$A$GT$$u20$as$u20$core..ops..drop..Drop$GT$::drop::h3a55feac6c8e7771 (raw_vec.rs:498)
    core::ptr::drop_in_place$LT$alloc..raw_vec..RawVec$LT$lock_api..rwlock..RwLock$LT$parking_lot..raw_rwlock..RawRwLock$C$$RF$mut$u20$$u5b$u32$u5d$$GT$$GT$$GT$::hc1e4faf2b4194c14 (mod.rs:179)
    core::ptr::drop_in_place$LT$alloc..vec..Vec$LT$lock_api..rwlock..RwLock$LT$parking_lot..raw_rwlock..RawRwLock$C$$RF$mut$u20$$u5b$u32$u5d$$GT$$GT$$GT$::hb58aa88a82306982 (mod.rs:179)
    granne::index::GranneBuilder$LT$Elements$GT$::index_elements::h00507be69e0b3db2 (mod.rs:783)
    granne::index::GranneBuilder$LT$Elements$GT$::index_elements_in_last_layer::h0c3bc587b9a5cb50 (mod.rs:693)
    _$LT$granne..index..GranneBuilder$LT$Elements$GT$$u20$as$u20$granne..index..Builder$GT$::build_partial::hd77479376bbc9da5 (mod.rs:392)
    granne::GranneBuilder::build::ha4747e7418026a87 (lib.rs)
    granne::GranneBuilder::create_instance::init::wrap_instance_method::_$u7b$$u7b$closure$u7d$$u7d$::h5afe2b0665ab803c (members.rs:99)
    cpython::function::handle_callback::_$u7b$$u7b$closure$u7d$$u7d$::h403681d837d8438a (function.rs:218)
    std::panicking::try::do_call::h62939ca7a79bd0c1 (panicking.rs:379)
    std::panicking::try::h38c9f96318d0de5c (panicking.rs:343)
    std::panic::catch_unwind::h814cfa00d891a4c7 (panic.rs:431)
    cpython::function::handle_callback::hc27b96a79fdcc7de (function.rs:215)
    granne::GranneBuilder::create_instance::init::wrap_instance_method::hcadb94cd6edba93c (members.rs:103)
    ...
    <..... HIDDEN ........>
    ...
    _process_worker (concurrent/futures/process.py:239)
    run (multiprocessing/process.py:108)
    _bootstrap (multiprocessing/process.py:315)
    _launch (multiprocessing/popen_fork.py:75)
    __init__ (multiprocessing/popen_fork.py:19)
    _Popen (multiprocessing/context.py:277)
    start (multiprocessing/process.py:121)
    _adjust_process_count (concurrent/futures/process.py:608)
    _start_queue_management_thread (concurrent/futures/process.py:584)
    submit (concurrent/futures/process.py:645)
    ...
    <..... HIDDEN ........>
    ...
    call_fixture_func (_pytest/fixtures.py:791)
    pytest_fixture_setup (_pytest/fixtures.py:936)
    _multicall (pluggy/callers.py:187)
    <lambda> (pluggy/manager.py:84)
    _hookexec (pluggy/manager.py:93)
    __call__ (pluggy/hooks.py:286)
    execute (_pytest/fixtures.py:894)
    _compute_fixture_value (_pytest/fixtures.py:587)
    _get_active_fixturedef (_pytest/fixtures.py:502)
    getfixturevalue (_pytest/fixtures.py:479)
    _fillfixtures (_pytest/fixtures.py:469)
    fillfixtures (_pytest/fixtures.py:296)
    setup (_pytest/python.py:1468)
    prepare (_pytest/runner.py:362)
    pytest_runtest_setup (_pytest/runner.py:116)
    _multicall (pluggy/callers.py:187)
    <lambda> (pluggy/manager.py:84)
    _hookexec (pluggy/manager.py:93)
    __call__ (pluggy/hooks.py:286)
    <lambda> (_pytest/runner.py:198)
    from_call (_pytest/runner.py:226)
    call_runtest_hook (_pytest/runner.py:197)
    call_and_report (_pytest/runner.py:173)
    runtestprotocol (_pytest/runner.py:87)
    pytest_runtest_protocol (_pytest/runner.py:78)
    _multicall (pluggy/callers.py:187)
    <lambda> (pluggy/manager.py:84)
    _hookexec (pluggy/manager.py:93)
    __call__ (pluggy/hooks.py:286)
    pytest_runtestloop (_pytest/main.py:271)
    _multicall (pluggy/callers.py:187)
    <lambda> (pluggy/manager.py:84)
    _hookexec (pluggy/manager.py:93)
    __call__ (pluggy/hooks.py:286)
    _main (_pytest/main.py:250)
    wrap_session (_pytest/main.py:206)
    pytest_cmdline_main (_pytest/main.py:243)
    _multicall (pluggy/callers.py:187)
    <lambda> (pluggy/manager.py:84)
    _hookexec (pluggy/manager.py:93)
    __call__ (pluggy/hooks.py:286)
    main (_pytest/config/__init__.py:82)
    <module> (pytest:8)

Deadlock related to https://github.com/granne/granne/blob/fe2fe5aca4be879be8cbaf4fc34a5abf6ed2593d/src/index/mod.rs#L774 par_iter call (not itself call, but rayon usage) and most probably related to https://github.com/rayon-rs/rayon/issues/592.

After I set default = ["singlethreaded"] in https://github.com/granne/granne/blob/master/Cargo.toml#L26, deadlock goes away

Unfortunately, I can't provide fully reproducible code sample for that, but will be glad to answer to any question.

Hi folks, seeing the below error when I add granne = "0.5.0" to my Cargo.toml. No code, just a failure to install the package. Settings:

Brads-MacBook-Pro:thistle bradwindsor$ rustup show
Default host: x86_64-apple-darwin
rustup home:  /Users/bradwindsor/.rustup

installed toolchains
--------------------

stable-x86_64-apple-darwin (default)
nightly-x86_64-apple-darwin

active toolchain
----------------

stable-x86_64-apple-darwin (default)
rustc 1.51.0 (2fd73fabe 2021-03-23)

Error:

error[E0308]: mismatched types
  --> /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/dense_vector.rs:86:17
   |
86 |                 Self(self.0.into_owned())
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
   | 
  ::: /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/angular.rs:53:1
   |
53 | dense_vector!(f32);
   | ------------------- in this macro invocation
   |
   = note: expected struct `angular::Vectors<'static>`
              found struct `angular::Vectors<'a>`
note: the lifetime `'a` as defined on the impl at 40:14...
  --> /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/dense_vector.rs:40:14
   |
40 |         impl<'a> Vectors<'a> {
   |              ^^
   | 
  ::: /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/angular.rs:53:1
   |
53 | dense_vector!(f32);
   | ------------------- in this macro invocation
   = note: ...does not necessarily outlive the static lifetime
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0308]: mismatched types
  --> /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/dense_vector.rs:86:17
   |
86 |                 Self(self.0.into_owned())
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
   | 
  ::: /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/angular_int.rs:17:1
   |
17 | dense_vector!(i8);
   | ------------------ in this macro invocation
   |
   = note: expected struct `angular_int::Vectors<'static>`
              found struct `angular_int::Vectors<'a>`
note: the lifetime `'a` as defined on the impl at 40:14...
  --> /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/dense_vector.rs:40:14
   |
40 |         impl<'a> Vectors<'a> {
   |              ^^
   | 
  ::: /Users/bradwindsor/.cargo/registry/src/github.com-1ecc6299db9ec823/granne-0.5.0/src/elements/angular_int.rs:17:1
   |
17 | dense_vector!(i8);
   | ------------------ in this macro invocation
   = note: ...does not necessarily outlive the static lifetime
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

error: aborting due to 2 previous errors

For more information about this error, try `rustc --explain E0308`.
error: could not compile `granne`

Paper 1:GRIP Paper 2:Zoom

The recently published paper GRIP:Multi-Store capacity-optimized high-performace nearest neighbor search for vector search engine.

When going to build an index I experienced the following:

thread '<unnamed>' panicked at 'assertion failed: `(left == right)`
  left: `4294967295`,
 right: `1`', /rustc/38114ff16e7856f98b2b4be7ab4cd29b38bed59a/src/libstd/macros.rs:16:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Traceback (most recent call last):
  File "xxx", line 292, in <module>
    builder.build()
SystemError: Rust panic

Unfortunately this doesn't seem to be happening reproducibly. @jacktasia