search

yahoojapan / NGT

Nearest Neighbor Search with Neighborhood Graph and Tree for High-dimensional Data
Apache License 2.0
1.26k stars 115 forks source link

Missing functions and types in the C API #141

Closed lerouxrgd closed 1 year ago

lerouxrgd commented 1 year ago

Hello,

While refactoring ngt-rs in order to have a strongly typed API, I noticed that a few functions and types are missing in the C API.

I should be able to try to implement those functions/types based on your work for #136, what do you think ?

NGT Index

Currently we can insert different kind of objects with ngt_insert_index_as_float, ngt_insert_index_as_uint8, and ngt_insert_index_as_float16.

As for batch insertion the available functions are:

The missing functions are:

Similarly, the struct NGTQuery and its search function are defined as follows:

The missing structs and functions are:

QG Index

Similarly, the struct NGTQGQuery and its search function are defined as follows:

The missing structs and functions are:

QBG Index

Similarly, the struct QBGQuery and its search function are defined as follows:

The missing structs and functions are:

masajiro commented 1 year ago

Hello, If these missing features are implemented, it would be beneficial not only to you but also to other users.

lerouxrgd commented 1 year ago

Hello @masajiro ,

I am working on implementing the missing features, so far I have implemented them for NGT and QG. You can see my current implementation here. Please let me know whether that looks good or not, any feedback is welcome !

As for QBG, I am facing some issue. Currently QBG::SearchContainer is holding a std::vector<float> objectVector, which is not generic, and it prevents me from defining uint8_t and float16 queries. I have tried to refactor it to use a NGT::Object *query instead, but it doesn't look simple due to the std::vector<float> &rotatedQuery used later. Do you have any opinion/advice about this issue ?

masajiro commented 1 year ago

Hello, I have just released v2.1.0. Since I have not updated C APIs much, it hardly affects your implementation. In any case, could you merge your repository with the latest NGT and check your implementation?

As for your implementation, NGTQGQuery should not be changed to keep compatibility. Instead of changing NGTQGQuery, you may want to add NGTQGQueryFloat.

Regarding your question about the QBG queries, std::vector<float> objectVector is supposed to be used, even if the original data type is uint8_t or float16.

lerouxrgd commented 1 year ago

In any case, could you merge your repository with the latest NGT and check your implementation?

I have rebased my branch on the latest main.

As for your implementation, NGTQGQuery should not be changed to keep compatibility. Instead of changing NGTQGQuery, you may want to add NGTQGQueryFloat.

I have changed it accordingly to your advice.

Regarding your question about the QBG queries, std::vector objectVector is supposed to be used, even if the original data type is uint8_t or float16.

Does that mean that in the case of qbg_search_index_uint8 I should:

  1. auto q = static_cast<float*>(query); where query is actually uint8_t*
  2. Construct a std::vector<float> vquery from it
  3. Use this vquery to call qbg_search_index_

Is this correct ?

masajiro commented 1 year ago

Does that mean that in the case of qbg_search_index_uint8 I should:

  1. auto q = static_cast<float*>(query); where query is actually uint8_t*
  2. Construct a std::vector<float> vquery from it
  3. Use this vquery to call qbg_search_index_

Is this correct ?

That means the following steps.

  1. std::vector<uint8_t> queryUint8(&query[0], &query[query_dim]); where query is uint8_t*
  2. std::vector<float> vquery(queryUint8.begin(), queryUint8.end());
  3. Use this vquery to call qbg_search_index_
lerouxrgd commented 1 year ago

@masajiro Thank you for the precision, I have implemented it as you suggested. You can still see my implementation here. I will make a PR after testing it through ngt-rs.

Besides, I wanted to run locally the sample code qg-capi to make sure everything is fine, but I ran into a SIGABRT. I have checked out separately the latest NGT main branch (without my changes) and the result is the same, I get a SIGABRT when trying to run qg-capi .

The gdb command gave me this backtrace:

save the index...
close the index...
quantize the index...
open the quantized index...
Fatal inner error! Invalid local centroid ID. ID=3:11296

Thread 1 "qg-capi" received signal SIGABRT, Aborted.
0x00007ffff6e9f26c in ?? () from /usr/lib/libc.so.6
(gdb) bt
#0  0x00007ffff6e9f26c in ?? () from /usr/lib/libc.so.6
#1  0x00007ffff6e4fa08 in raise () from /usr/lib/libc.so.6
#2  0x00007ffff6e38538 in abort () from /usr/lib/libc.so.6
#3  0x00007ffff7d2a1bc in NGTQG::QuantizedGraphRepository::construct(NGT::GraphRepository&, NGTQ::Index&, unsigned long) () from /home/rgd/dev/tmp/NGT/build/lib/NGT/libngt.so.2
#4  0x00007ffff7d0c807 in ngtqg_open_index () from /home/rgd/dev/tmp/NGT/build/lib/NGT/libngt.so.2
#5  0x0000555555558235 in main ()

Maybe version 2.1 introduced a bug ?

masajiro commented 1 year ago

Thank you for your feedback on this bug. I have released v2.1.1 which fixes the bug.

Your implementation looks fine, including compatibility.

lerouxrgd commented 1 year ago

Indeed it looks fine now !

I will test my implementation through ngt-rs before making a final PR.

lerouxrgd commented 1 year ago

Actually, if I run my usual tests against latest NGT main branch (with my changes, but I am not testing them yet), then I get some SIGABRT. Here are the gdb backtraces when I run them multiple times:

Thread 819 "qg::index::test" received signal SIGABRT, Aborted.
[Switching to Thread 0x7fff9cffa6c0 (LWP 104388)]
0x00007ffff7a9f26c in ?? () from /usr/lib/libc.so.6
(gdb) bt
#0  0x00007ffff7a9f26c in ?? () from /usr/lib/libc.so.6
#1  0x00007ffff7a4fa08 in raise () from /usr/lib/libc.so.6
#2  0x00007ffff7a38538 in abort () from /usr/lib/libc.so.6
#3  0x00007ffff6eb236d in __gnu_cxx::__verbose_terminate_handler () at /usr/src/debug/gcc/gcc/libstdc++-v3/libsupc++/vterminate.cc:50
#4  0x00007ffff6eb011c in __cxxabiv1::__terminate (handler=<optimized out>) at /usr/src/debug/gcc/gcc/libstdc++-v3/libsupc++/eh_terminate.cc:48
#5  0x00007ffff6eb0189 in std::terminate () at /usr/src/debug/gcc/gcc/libstdc++-v3/libsupc++/eh_terminate.cc:58
#6  0x00007ffff6eb03ed in __cxxabiv1::__cxa_throw (obj=<optimized out>, tinfo=0x7ffff7e0c3a0 <typeinfo for NGT::Exception>, dest=0x7ffff7c667c0 <NGT::Exception::~Exception()>)
    at /usr/src/debug/gcc/gcc/libstdc++-v3/libsupc++/eh_throw.cc:98
#7  0x00007ffff7c4ee0e in NGTQ::GenerateResidualObjectFloat::operator()(std::vector<float, std::allocator<float> >&, unsigned long, float*) [clone .constprop.0] [clone .cold] ()
   from ./target/debug/build/ngt-sys-2d50b7cde3cf40c4/out/lib/libngt.so.2
#8  0x00007ffff7d0ff20 in NGTQ::QuantizerInstance<unsigned short>::insert(std::vector<std::pair<std::vector<float, std::allocator<float> >, unsigned long>, std::allocator<std::pair<std::vector<float, std::allocator<float> >, unsigned long> > >&, NGT::Index*) [clone ._omp_fn.0] () from ./target/debug/build/ngt-sys-2d50b7cde3cf40c4/out/lib/libngt.so.2
#9  0x00007ffff7e4dc96 in gomp_thread_start (xdata=<optimized out>) at /usr/src/debug/gcc/gcc/libgomp/team.c:129
#10 0x00007ffff7a9d44b in ?? () from /usr/lib/libc.so.6
#11 0x00007ffff7b20e40 in ?? () from /usr/lib/libc.so.6

Another one:

Thread 318 "qg::index::test" received signal SIGABRT, Aborted.
[Switching to Thread 0x7fffaf7fe6c0 (LWP 107958)]
0x00007ffff7a9f26c in ?? () from /usr/lib/libc.so.6
(gdb) bt
#0  0x00007ffff7a9f26c in ?? () from /usr/lib/libc.so.6
#1  0x00007ffff7a4fa08 in raise () from /usr/lib/libc.so.6
#2  0x00007ffff7a38538 in abort () from /usr/lib/libc.so.6
#3  0x00007ffff6eb236d in __gnu_cxx::__verbose_terminate_handler () at /usr/src/debug/gcc/gcc/libstdc++-v3/libsupc++/vterminate.cc:50
#4  0x00007ffff6eb011c in __cxxabiv1::__terminate (handler=<optimized out>) at /usr/src/debug/gcc/gcc/libstdc++-v3/libsupc++/eh_terminate.cc:48
#5  0x00007ffff6eaf0aa in __cxa_call_terminate (ue_header=0x7ffd6c000e00) at /usr/src/debug/gcc/gcc/libstdc++-v3/libsupc++/eh_call.cc:54
#6  0x00007ffff6eaf82a in __cxxabiv1::__gxx_personality_v0 (version=<optimized out>, actions=6, exception_class=5138137972254386944, ue_header=<optimized out>, 
    context=0x7fffaf7fd690) at /usr/src/debug/gcc/gcc/libstdc++-v3/libsupc++/eh_personality.cc:688
#7  0x00007ffff7f8558a in _Unwind_RaiseException_Phase2 (exc=exc@entry=0x7ffd6c000e00, context=context@entry=0x7fffaf7fd690, frames_p=frames_p@entry=0x7fffaf7fd780)
    at /usr/src/debug/gcc/gcc/libgcc/unwind.inc:64
#8  0x00007ffff7f85cb2 in _Unwind_RaiseException (exc=0x7ffd6c000e00) at /usr/src/debug/gcc/gcc/libgcc/unwind.inc:136
#9  0x00007ffff6eb03de in __cxxabiv1::__cxa_throw (obj=<optimized out>, tinfo=0x7ffff706c0e8 <typeinfo for std::out_of_range>, 
    dest=0x7ffff6ec85c0 <std::out_of_range::~out_of_range()>) at /usr/src/debug/gcc/gcc/libstdc++-v3/libsupc++/eh_throw.cc:93
#10 0x00007ffff6ea0269 in std::__throw_out_of_range_fmt (__fmt=<optimized out>) at /usr/src/debug/gcc/gcc/libstdc++-v3/src/c++11/functexcept.cc:101
#11 0x00007ffff7d100b8 in NGTQ::QuantizerInstance<unsigned short>::insert(std::vector<std::pair<std::vector<float, std::allocator<float> >, unsigned long>, std::allocator<std::pair<std::vector<float, std::allocator<float> >, unsigned long> > >&, NGT::Index*) [clone ._omp_fn.0] () from ./target/debug/build/ngt-sys-2d50b7cde3cf40c4/out/lib/libngt.so.2
#12 0x00007ffff7e4dc96 in gomp_thread_start (xdata=<optimized out>) at /usr/src/debug/gcc/gcc/libgomp/team.c:129
#13 0x00007ffff7a9d44b in ?? () from /usr/lib/libc.so.6
#14 0x00007ffff7b20e40 in ?? () from /usr/lib/libc.so.6

Another one:

Thread 198 "qg::index::test" received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0x7fffcaffd6c0 (LWP 109359)]
0x00007ffff7d0ff69 in NGTQ::QuantizerInstance<unsigned short>::insert(std::vector<std::pair<std::vector<float, std::allocator<float> >, unsigned long>, std::allocator<std::pair<std::vector<float, std::allocator<float> >, unsigned long> > >&, NGT::Index*) [clone ._omp_fn.0] () from ./target/debug/build/ngt-sys-2d50b7cde3cf40c4/out/lib/libngt.so.2
(gdb) bt
#0  0x00007ffff7d0ff69 in NGTQ::QuantizerInstance<unsigned short>::insert(std::vector<std::pair<std::vector<float, std::allocator<float> >, unsigned long>, std::allocator<std::pair<std::vector<float, std::allocator<float> >, unsigned long> > >&, NGT::Index*) [clone ._omp_fn.0] () from ./target/debug/build/ngt-sys-2d50b7cde3cf40c4/out/lib/libngt.so.2
#1  0x00007ffff7e4dc96 in gomp_thread_start (xdata=<optimized out>) at /usr/src/debug/gcc/gcc/libgomp/team.c:129
#2  0x00007ffff7a9d44b in ?? () from /usr/lib/libc.so.6
#3  0x00007ffff7b20e40 in ?? () from /usr/lib/libc.so.6

Although these tests were fine before 2.1, maybe there is an issue in the Rust wrapper. I will investigate later.

lerouxrgd commented 1 year ago

I have updated ngt-rs accordingly, however some issues persist:

Firstly, the functions ngt_batch_append_index_as_{uint8,float16} don't work and send the error:

NGT/lib/NGT/Index.h:getIndex:549: NGT::Index::getIndex: Index is unavailable.

So it looks like getIndex return null there... As for ngt_batch_append_index (the original implementation using float) it still works fine. Note that all functions ngt_insert_index_as_{float,uint8,float16} also work fine. I wasn't able to narrow down the issue, do you happen to have some insight about it ?

Secondly, the tests for QG are still failing with some SIGABORT like the ones I mentioned above. I have realized that the following message is printed:

build-qg: Warning! Although rotation or repositioning is specified, turn off rotation and repositioning because of unavailable options.

Although I have defined NGTQG_NO_ROTATION=ON and NGTQG_ZERO_GLOBAL=ON in my cmake build (in ngt-sys/build.rs). Do you have an idea of what could be the issue ?

masajiro commented 1 year ago

Firstly, the functions ngt_batch_append_indexas{uint8,float16} don't work and send the error:

NGT has been updated as the latest commit to resolve the above issue.

Although I have defined NGTQG_NO_ROTATION=ON and NGTQG_ZERO_GLOBAL=ON in my cmake build (in ngt-sys/build.rs). Do you have an idea of what could be the issue ?

I don't think this message has anything to do with this issue.

lerouxrgd commented 1 year ago

Thank you for the update, I can confirm that it fixed the issue for the ngt_batch_append_index_as_{uint8,float16} functions.

As for QG failing tests, I will continue to investigate.

masajiro commented 1 year ago

Hello @lerouxrgd , I have fixed these issues and verified that the latest commit has passed all of your rust module tests.

lerouxrgd commented 1 year ago

Hello @masajiro ,

Thank you very much for the fixes ! I can also confirm that everything works fine on the Rust unit tests, I will send a PR now.