1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#include <vespa/searchlib/tensor/hnsw_nodeid_mapping.h>
#include <vespa/searchlib/tensor/hnsw_node.h>
#include <vespa/vespalib/gtest/gtest.h>
using namespace search::tensor;
using vespalib::datastore::EntryRef;
class HnswNodeidMappingTest : public ::testing::Test {
public:
using NodeidVector = std::vector<uint32_t>;
HnswNodeidMapping mapping;
HnswNodeidMappingTest()
: mapping()
{
mapping.assign_generation(10);
}
void expect_allocate_get(const NodeidVector& exp_ids, uint32_t docid) {
auto ids = mapping.allocate_ids(docid, exp_ids.size());
EXPECT_EQ(exp_ids, NodeidVector(ids.begin(), ids.end()));
expect_get(exp_ids, docid);
}
void expect_get(const NodeidVector& exp_ids, uint32_t docid) {
auto ids = mapping.get_ids(docid);
EXPECT_EQ(exp_ids, NodeidVector(ids.begin(), ids.end()));
}
};
TEST_F(HnswNodeidMappingTest, allocate_and_get_nodeids)
{
expect_allocate_get({}, 1);
expect_allocate_get({1}, 30);
expect_allocate_get({2, 3, 4}, 40);
expect_allocate_get({5, 6}, 50);
// Note that docid=2 has implicit no nodeids:
expect_get({}, 2);
}
TEST_F(HnswNodeidMappingTest, free_ids_clears_docid_entry_so_it_can_be_reused)
{
expect_allocate_get({1, 2, 3}, 1);
mapping.free_ids(1);
expect_get({}, 1);
expect_allocate_get({4, 5}, 1);
mapping.free_ids(1);
expect_get({}, 1);
}
TEST_F(HnswNodeidMappingTest, free_ids_puts_nodeids_on_hold_list_and_then_free_list_for_reuse)
{
expect_allocate_get({1, 2, 3}, 1);
expect_allocate_get({4, 5, 6}, 2);
mapping.free_ids(1); // {1, 2, 3} are inserted into hold list
mapping.assign_generation(11);
expect_allocate_get({7, 8}, 3); // Free list is NOT used
mapping.reclaim_memory(12); // {1, 2, 3} are moved to free list
expect_allocate_get({3, 2}, 4); // Free list is used
mapping.free_ids(2); // {4, 5, 6} are inserted into hold list
mapping.assign_generation(12);
mapping.free_ids(3); // {7, 8} are inserted into hold list
mapping.assign_generation(13);
mapping.reclaim_memory(13); // {4, 5, 6} are moved to free list
expect_allocate_get({6, 5}, 5); // Free list is used
expect_allocate_get({4, 1, 9}, 6); // Free list is first used, then new nodeid is allocated
mapping.reclaim_memory(14); // {7, 8} are moved to free list
expect_allocate_get({8, 7, 10}, 7); // Free list is first used, then new nodeid is allocated
}
TEST_F(HnswNodeidMappingTest, on_load_populates_mapping)
{
std::vector<HnswNode> nodes(10);
nodes[1].ref().store_relaxed(EntryRef(1));
nodes[1].store_docid(7);
nodes[1].store_subspace(0);
nodes[2].ref().store_relaxed(EntryRef(2));
nodes[2].store_docid(4);
nodes[2].store_subspace(0);
nodes[7].ref().store_relaxed(EntryRef(3));
nodes[7].store_docid(4);
nodes[7].store_subspace(1);
mapping.on_load(vespalib::ConstArrayRef(nodes.data(), nodes.size()));
expect_get({1}, 7);
expect_get({2, 7}, 4);
expect_allocate_get({3, 4, 5, 6, 8, 9}, 1);
}
TEST_F(HnswNodeidMappingTest, memory_usage_increases_when_allocating_nodeids)
{
expect_allocate_get({1, 2}, 1);
auto a = mapping.memory_usage();
EXPECT_GT(a.allocatedBytes(), 0);
EXPECT_GT(a.usedBytes(), 0);
EXPECT_GE(a.allocatedBytes(), a.usedBytes());
expect_allocate_get({3, 4}, 2);
auto b = mapping.memory_usage();
EXPECT_GT(b.usedBytes(), a.usedBytes());
}
GTEST_MAIN_RUN_ALL_TESTS()
|
