Hacker News Reader

ANN search is usually memory bandwidth limited from a search speed prospective, so it doesn’t surprise me that the CPU has a few extra cycles to decompress without losing much latency

View on HN

Brute-force indices are usually arithmetic bound (e.g., GEMM). Cell-probe based indices are usually memory bandwidth bound (IVF, LSH bucketing, etc). Graph-based indices are usually memory latency bound (traversing linked lists / graph data structures).

(I wrote the GPU half of Faiss and work with the people who wrote this paper).

Why would that be true? Every approach I've seen needs to jump around in memory to find indices and then the coordinates. It's the polar opposite of being bound by memory bandwidth.

Yes the GP said “bandwidth” when they perhaps meant “latency” but the gist and spirit of their post was good. The cpu has a lot of spare cycles, particularly if it can be arranged to be without dependency so it can be crunched instead of stalling?

Reply on news.ycombinator.com