Faiss: low query speed performance for binary index

[zhaolili]

Summary

The query speed for binary vector is incredibly slow.
The indexing was built using IndexBinaryFlat with 100,000 128-dimensional binary vector.
The average query speed for a single binary vector is around 0.05 seconds. And query with batch doesn't improve much.
Does this make sense for current faiss version?

Platform

OS: Ubuntu16.04

Faiss version: compile from source, latest code from github

Faiss compilation options: default options

Running on:

• [ ] CPU
  below shows CPU details
  

Interface:

• [ ] Python

Reproduction instructions

below shows the python code used to do profiling.

db_volume = 100000
rs = np.random.RandomState(67)
x = rs.randint(256, size=(db_volume, 128/8)).astype('uint8')
index = faiss.IndexBinaryFlat(128)
index.add(x)

query = np.array([[174, 224, 111, 153,  83,  78, 253, 164,  96, 208,  68,  49,  55, 195,  2,  84]]).astype(np.uint8)

beg = time.time()
dists, ids = index.search(query, 10)
end = time.time()

print "search time: ", end-beg, "seconds"   #taking around 0.05 secs
print dists, ids

[mdouze]

Please see http://math-atlas.sourceforge.net/faq.html#utone on how to submit proper bug reports.

https://gist.github.com/mdouze/98ac88fa02ef12cf504b2dc6c261edc4

--> querying 10k vectors in 128D should take ~14us.

[zhaolili]

@mdouze Thanks for your REPLY. I know the official number is around ~x us, while in fact my profiling number is ~50ms. I am posting here in case anyone ever met similar problem so that he/she can figure out why.
This a not a bug report.

[mdouze]

If your measure is 50ms then it is a bug, so it would be useful if you posted how to reproduce it.

[zhaolili]

@mdouze thanks. Updated issue description with profiling code and CPU details.

[mdouze]

Takes ~0.2 ms for me.
https://gist.github.com/mdouze/93372de31edb30f1452209cabda82fb5
How did you compile Faiss? My guess is that the -mpopcnt flag was omitted.

[MTCloudVision]

In this case,we found the problem is we run this code on a ubuntu server and we hadn't set the environment OMP_NUM_THREADS to 1 which leads the retrieval speed very slow. It works all right now. cheers a lot.@mdouze

[mdouze]

Closing issue.