mirror of
https://github.com/facebookresearch/faiss.git
synced 2026-10-12 02:13:36 +00:00
Alibek Zhakubayev
97d257433a
Summary: Pull Request resolved: https://github.com/facebookresearch/faiss/pull/5072 Fix correctness bugs in `NNDescent` `Nhood` copy/move operations and `gen_random` bounds. ## Bug 1: Broken Nhood copy constructor and copy assignment operator The copy constructor and copy assignment operator for `Nhood` were incomplete: - Copy assignment used `std::back_inserter` to append to `nn_new` instead of replacing it, leading to duplicate entries on reassignment and heap-use-after-free on self-assignment. - Neither operation copied `pool`, `nn_old`, `rnn_old`, or `rnn_new`, meaning copied `Nhood` objects had missing neighbor data. - This caused data loss when `std::vector<Nhood>` reallocated during `push_back`. Fixed both operations to properly copy all 6 data members. Added self-assignment guard (`if (this != &other)`) to the copy assignment operator. Changed the copy constructor to use a member initializer list in declaration order to avoid `-Wreorder` warnings. **Proof:** `NhoodCopy.CopyConstructorPreservesAllFields` and `NhoodCopy.CopyAssignmentPreservesAllFields` fail without the fix — `pool.size()` is 0 (expected 3), `nn_old`, `rnn_new`, `rnn_old` are all empty. `NhoodCopy.CopyAssignmentSelfAssign` triggers heap-use-after-free without the self-assignment guard. `NhoodCopy.VectorReallocationPreservesData` shows data loss during `std::vector<Nhood>` reallocation. ## Bug 2: Division by zero in `gen_random` When `size == N`, the expression `rng() % (N - size)` is a division by zero (undefined behavior). This occurs in `search()` when `search_L` or `topk` equals `ntotal`, because `L_2 = max(search_L, topk)` is passed to `gen_random(rng, init_ids.data(), L_2, ntotal)`. Added a precondition assertion (`size > 0 && size <= N`) and a Fisher-Yates shuffle for the `size == N` special case. **Proof:** `TestNNDescentGenRandom.test_search_L_equals_ntotal` crashes (process killed by SIGFPE) without the fix, passes with it. ## Performance: Added move constructor and move assignment operator Since `std::mutex` is neither copyable nor movable, the compiler cannot generate implicit move operations for `Nhood`. With user-defined copy operations, implicit move generation is suppressed entirely. Without explicit move operations, `std::vector<Nhood>::push_back(Nhood&&)` falls back to copy — 5 unnecessary vector allocations per element. Added `noexcept` move constructor and move assignment operator. `noexcept` is required for `std::vector` to prefer move over copy during reallocation. The move assignment operator is included for Rule of Five consistency. **Proof:** All tests pass both with and without move operations, confirming these are a performance optimization, not a correctness fix. ## Cleanup: Removed misleading `omp_get_thread_num()` The RNG seed in `nndescent()` was `random_seed * 6577 + omp_get_thread_num()`. This function is not inside any `#pragma omp parallel` region — the call chain is `IndexNNDescent::add()` -> `NNDescent::build()` -> `NNDescent::nndescent()`, all sequential. Per the OpenMP specification, `omp_get_thread_num()` returns 0 in sequential context. The `+ 0` is dead code. **Proof:** No behavioral change. The seed was always `random_seed * 6577`. Reviewed By: mnorris11 Differential Revision: D100155792 fbshipit-source-id: 042a7d0a53a7696915a96bf1e48a464507f044b3
88 lines
2.7 KiB
C++
88 lines
2.7 KiB
C++
/*
|
|
* Copyright (c) Meta Platforms, Inc. and affiliates.
|
|
*
|
|
* This source code is licensed under the MIT license found in the
|
|
* LICENSE file in the root directory of this source tree.
|
|
*/
|
|
|
|
#include <faiss/impl/NNDescent.h>
|
|
#include <gtest/gtest.h>
|
|
#include <random>
|
|
|
|
using namespace faiss::nndescent;
|
|
|
|
/// Helper: build a Nhood with known data in all fields.
|
|
static Nhood make_populated_nhood() {
|
|
std::mt19937 rng(42);
|
|
int N = 200;
|
|
Nhood nh(/*l=*/50, /*s=*/10, rng, N);
|
|
|
|
nh.pool.clear();
|
|
nh.pool.push_back(Neighbor(1, 0.1f, true));
|
|
nh.pool.push_back(Neighbor(2, 0.2f, false));
|
|
nh.pool.push_back(Neighbor(3, 0.3f, true));
|
|
|
|
nh.nn_old = {10, 20, 30};
|
|
nh.rnn_new = {40, 50};
|
|
nh.rnn_old = {60, 70, 80};
|
|
|
|
return nh;
|
|
}
|
|
|
|
TEST(NhoodCopy, CopyConstructorPreservesAllFields) {
|
|
Nhood original = make_populated_nhood();
|
|
Nhood copy(original);
|
|
|
|
EXPECT_EQ(copy.M, original.M);
|
|
EXPECT_EQ(copy.pool.size(), original.pool.size());
|
|
EXPECT_EQ(copy.nn_new, original.nn_new);
|
|
EXPECT_EQ(copy.nn_old, original.nn_old);
|
|
EXPECT_EQ(copy.rnn_new, original.rnn_new);
|
|
EXPECT_EQ(copy.rnn_old, original.rnn_old);
|
|
}
|
|
|
|
TEST(NhoodCopy, CopyAssignmentPreservesAllFields) {
|
|
Nhood original = make_populated_nhood();
|
|
Nhood assigned;
|
|
assigned = original;
|
|
|
|
EXPECT_EQ(assigned.M, original.M);
|
|
EXPECT_EQ(assigned.pool.size(), original.pool.size());
|
|
EXPECT_EQ(assigned.nn_new, original.nn_new);
|
|
EXPECT_EQ(assigned.nn_old, original.nn_old);
|
|
EXPECT_EQ(assigned.rnn_new, original.rnn_new);
|
|
EXPECT_EQ(assigned.rnn_old, original.rnn_old);
|
|
}
|
|
|
|
TEST(NhoodCopy, CopyAssignmentSelfAssign) {
|
|
Nhood nh = make_populated_nhood();
|
|
auto expected_pool_size = nh.pool.size();
|
|
auto expected_nn_new = nh.nn_new;
|
|
|
|
// Use a reference to avoid -Wself-assign-overloaded.
|
|
Nhood& ref = nh;
|
|
nh = ref;
|
|
|
|
EXPECT_EQ(nh.pool.size(), expected_pool_size);
|
|
EXPECT_EQ(nh.nn_new, expected_nn_new);
|
|
}
|
|
|
|
/// Simulates std::vector<Nhood> reallocation during push_back.
|
|
TEST(NhoodCopy, VectorReallocationPreservesData) {
|
|
std::vector<Nhood> vec;
|
|
// Do NOT reserve — force reallocation during push_back
|
|
for (int i = 0; i < 20; i++) {
|
|
Nhood nh = make_populated_nhood();
|
|
nh.pool[0].id = i;
|
|
vec.push_back(std::move(nh));
|
|
}
|
|
|
|
for (int i = 0; i < 20; i++) {
|
|
EXPECT_EQ(vec[i].pool[0].id, i) << "pool lost at index " << i;
|
|
EXPECT_EQ(vec[i].pool.size(), 3) << "pool truncated at index " << i;
|
|
EXPECT_EQ(vec[i].nn_old.size(), 3) << "nn_old lost at index " << i;
|
|
EXPECT_EQ(vec[i].rnn_new.size(), 2) << "rnn_new lost at index " << i;
|
|
EXPECT_EQ(vec[i].rnn_old.size(), 3) << "rnn_old lost at index " << i;
|
|
}
|
|
}
|