Skip to content

Commit 366a814

Browse files
Gufan Yinfacebook-github-bot
Gufan Yin
authored and
facebook-github-bot
committed
Revert D55723390: Support for Remove ids from IVFPQFastScan index
Differential Revision: D55723390 Original commit changeset: 0017b556bd79 Original Phabricator Diff: D55723390 fbshipit-source-id: 58d61467b30dd11d27398f9f825162f598896845
1 parent 7657e81 commit 366a814

4 files changed

Lines changed: 20 additions & 77 deletions

File tree

‎faiss/invlists/BlockInvertedLists.cpp‎

Lines changed: 7 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,6 @@
99

1010
#include <faiss/impl/CodePacker.h>
1111
#include <faiss/impl/FaissAssert.h>
12-
#include <faiss/impl/IDSelector.h>
1312

1413
#include <faiss/impl/io.h>
1514
#include <faiss/impl/io_macros.h>
@@ -55,9 +54,7 @@ size_t BlockInvertedLists::add_entries(
5554
codes[list_no].resize(n_block * block_size);
5655
if (o % block_size == 0) {
5756
// copy whole blocks
58-
memcpy(&codes[list_no][o * packer->code_size],
59-
code,
60-
n_block * block_size);
57+
memcpy(&codes[list_no][o * code_size], code, n_block * block_size);
6158
} else {
6259
FAISS_THROW_IF_NOT_MSG(packer, "missing code packer");
6360
std::vector<uint8_t> buffer(packer->code_size);
@@ -79,29 +76,6 @@ const uint8_t* BlockInvertedLists::get_codes(size_t list_no) const {
7976
return codes[list_no].get();
8077
}
8178

82-
size_t BlockInvertedLists::remove_ids(const IDSelector& sel) {
83-
idx_t nremove = 0;
84-
#pragma omp parallel for
85-
for (idx_t i = 0; i < nlist; i++) {
86-
std::vector<uint8_t> buffer(packer->code_size);
87-
idx_t l = ids[i].size(), j = 0;
88-
while (j < l) {
89-
if (sel.is_member(ids[i][j])) {
90-
l--;
91-
ids[i][j] = ids[i][l];
92-
packer->unpack_1(codes[i].data(), l, buffer.data());
93-
packer->pack_1(buffer.data(), j, codes[i].data());
94-
} else {
95-
j++;
96-
}
97-
}
98-
resize(i, l);
99-
nremove += ids[i].size() - l;
100-
}
101-
102-
return nremove;
103-
}
104-
10579
const idx_t* BlockInvertedLists::get_ids(size_t list_no) const {
10680
assert(list_no < nlist);
10781
return ids[list_no].data();
@@ -128,6 +102,12 @@ void BlockInvertedLists::update_entries(
128102
const idx_t*,
129103
const uint8_t*) {
130104
FAISS_THROW_MSG("not impemented");
105+
/*
106+
assert (list_no < nlist);
107+
assert (n_entry + offset <= ids[list_no].size());
108+
memcpy (&ids[list_no][offset], ids_in, sizeof(ids_in[0]) * n_entry);
109+
memcpy (&codes[list_no][offset * code_size], codes_in, code_size * n_entry);
110+
*/
131111
}
132112

133113
BlockInvertedLists::~BlockInvertedLists() {

‎faiss/invlists/BlockInvertedLists.h‎

Lines changed: 0 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,6 @@
1515
namespace faiss {
1616

1717
struct CodePacker;
18-
struct IDSelector;
1918

2019
/** Inverted Lists that are organized by blocks.
2120
*
@@ -48,8 +47,6 @@ struct BlockInvertedLists : InvertedLists {
4847
size_t list_size(size_t list_no) const override;
4948
const uint8_t* get_codes(size_t list_no) const override;
5049
const idx_t* get_ids(size_t list_no) const override;
51-
/// remove ids from the InvertedLists
52-
size_t remove_ids(const IDSelector& sel);
5350

5451
// works only on empty BlockInvertedLists
5552
// the codes should be of size ceil(n_entry / n_per_block) * block_size

‎faiss/invlists/DirectMap.cpp‎

Lines changed: 1 addition & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,6 @@
1515
#include <faiss/impl/AuxIndexStructures.h>
1616
#include <faiss/impl/FaissAssert.h>
1717
#include <faiss/impl/IDSelector.h>
18-
#include <faiss/invlists/BlockInvertedLists.h>
1918

2019
namespace faiss {
2120

@@ -149,12 +148,8 @@ size_t DirectMap::remove_ids(const IDSelector& sel, InvertedLists* invlists) {
149148
std::vector<idx_t> toremove(nlist);
150149

151150
size_t nremove = 0;
152-
BlockInvertedLists* block_invlists =
153-
dynamic_cast<BlockInvertedLists*>(invlists);
151+
154152
if (type == NoMap) {
155-
if (block_invlists != nullptr) {
156-
return block_invlists->remove_ids(sel);
157-
}
158153
// exhaustive scan of IVF
159154
#pragma omp parallel for
160155
for (idx_t i = 0; i < nlist; i++) {
@@ -183,9 +178,6 @@ size_t DirectMap::remove_ids(const IDSelector& sel, InvertedLists* invlists) {
183178
}
184179
}
185180
} else if (type == Hashtable) {
186-
FAISS_THROW_IF_MSG(
187-
block_invlists,
188-
"remove with hashtable is not supported with BlockInvertedLists");
189181
const IDSelectorArray* sela =
190182
dynamic_cast<const IDSelectorArray*>(&sel);
191183
FAISS_THROW_IF_NOT_MSG(

‎tests/test_merge_index.py‎

Lines changed: 12 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -246,45 +246,19 @@ def test_merge_IDMap2(self):
246246

247247
class TestRemoveFastScan(unittest.TestCase):
248248

249-
def do_fast_scan_test(self,
250-
factory_key,
251-
with_ids=False,
252-
direct_map_type=faiss.DirectMap.NoMap):
249+
def do_fast_scan_test(self, factory_key, size1):
253250
ds = SyntheticDataset(110, 1000, 1000, 100)
254-
index = faiss.index_factory(ds.d, factory_key)
255-
index.train(ds.get_train())
256-
257-
index.reset()
251+
index1 = faiss.index_factory(ds.d, factory_key)
252+
index1.train(ds.get_train())
253+
index1.reset()
258254
tokeep = [i % 3 == 0 for i in range(ds.nb)]
259-
if with_ids:
260-
index.add_with_ids(ds.get_database()[tokeep], np.arange(ds.nb)[tokeep])
261-
faiss.extract_index_ivf(index).nprobe = 5
262-
else:
263-
index.add(ds.get_database()[tokeep])
264-
_, Iref = index.search(ds.get_queries(), 5)
265-
266-
index.reset()
267-
if with_ids:
268-
index.add_with_ids(ds.get_database(), np.arange(ds.nb))
269-
index.set_direct_map_type(direct_map_type)
270-
faiss.extract_index_ivf(index).nprobe = 5
271-
else:
272-
index.add(ds.get_database())
273-
index.remove_ids(np.where(np.logical_not(tokeep))[0])
274-
_, Inew = index.search(ds.get_queries(), 5)
255+
index1.add(ds.get_database()[tokeep])
256+
_, Iref = index1.search(ds.get_queries(), 5)
257+
index1.reset()
258+
index1.add(ds.get_database())
259+
index1.remove_ids(np.where(np.logical_not(tokeep))[0])
260+
_, Inew = index1.search(ds.get_queries(), 5)
275261
np.testing.assert_array_equal(Inew, Iref)
276262

277-
def test_remove_PQFastScan(self):
278-
# with_ids is not support for this type of index
279-
self.do_fast_scan_test("PQ5x4fs", False)
280-
281-
def test_remove_IVFPQFastScan(self):
282-
self.do_fast_scan_test("IVF20,PQ5x4fs", True)
283-
284-
def test_remove_IVFPQFastScan_2(self):
285-
self.assertRaisesRegex(Exception,
286-
".*not supported.*",
287-
self.do_fast_scan_test,
288-
"IVF20,PQ5x4fs",
289-
True,
290-
faiss.DirectMap.Hashtable)
263+
def test_remove(self):
264+
self.do_fast_scan_test("PQ5x4fs", 320)

0 commit comments

Comments
 (0)