Improve performance of IndexPQFastScan and IndexIVFPQFastScan on aarch64 and non-AVX2 devices

[matsui528]

Summary

Dear @mdouze and all,

Currently, IndexPQFastScan and IndexIVFPQFastScan are optimized only for AVX2. Thus, the algorithms are not much fast in non-AVX2 environments.

Our team (@vorj, @n-miyamoto-fixstars, @LWisteria, and @matsui528) has accelerated the above two algorithms for the following two environments:

• for non-AVX2 environment (e.g., old x86 computer w/o AVX2)
  • We optimized simdlib_emulated.h, enabling 4x speedup for SIFT1M.
• for aarch64 (e.g., Rasberry Pi)
  • We implemented simdlib_neon.h, which is a NEON counterpart of simdlib_avx2.h.
  • This achieved 60x faster performance on SIFT1M.

If you are likely to merge, we plan to submit a PR for the above changes. What do you think? The changes are mainly in the above header files and do not significantly change the faiss codebase.

Kind regards,

Platform

OS: Ubuntu 20.04.2 LTS (GNU/Linux 5.4.0-1038-aws aarch64)

Faiss version: fe7b061

Installed from: compiled by myself

Faiss compilation options: cmake -DFAISS_ENABLE_GPU=OFF -DFAISS_OPT_LEVEL=aarch64 -DCMAKE_BUILD_TYPE=Release

Running on:

• CPU
• GPU

Interface:

• C++
• Python

Reproduction instructions

We only post the results. If you need more detailed information, please let me know.

• Evaluated on an AWS EC2 ARM instance (c6g.4xlarge)
• original is the current code
• improved-emulated is the result of optimizing simdlib_emulated.h, which is faster than original
• neon is the result by simdlib_neon.h, which is much faster than original

The above image illustrates the ratio of speedup.

• In the best case, neon is approx. 60x faster than original (M=32, nbits=4, nprobe=16)
  • original: 4.5 ms
  • neon: 0.077 ms

[mdouze]

That looks great! Thanks so much for working on this. Of course, we would welcome this as a PR.

[matsui528]

Glad to hear that! Could you review the following two PRs when you're available? Best,
#1814 #1815

[matsui528]

Thank you for merging the PRs! We would be honored if you could include our names (@vorj, @n-miyamoto-fixstars, @LWisteria, and @matsui528) as contributors in README.md or CHANGELOG.md or somewhere else.

[mdouze]

That's a good point, we don't have a dedicated place to thank Faiss contributors outside the core Faiss developers (other than https://github.com/facebookresearch/faiss/graphs/contributors).
@beauby where could we do that?

[mdouze]

From now on we will add CHANGELOG entries with the names of (external) contributors.

[matsui528]

Thank you 😄