Problems with DeviceVector allocation heuristic

[gabuzi]

Summary

I ran into some performance anomalies with IVFFlat indexes on GPU.
We are evaluating a scenario where we need to minimize index training & adding costs, thus we were looking at clustering with small numbers of centroids.

To my surprise, this started slowing things down at some point, and also caused a significant increase in memory (> 24GiB for 30M vectors of dim 40).

GPU profiling revealed significant activity for CudaMalloc, and I could narrow it down to the recently introduced new heuristic for DeviceVector allocation (#2691) in the regime where individual IVFLists are supposed to grow by 1.25.

I think I managed to isolate two separate but related issues:

1. in DeviceVector::resize() getNewCapacity_() is always called when the new size is bigger than the current number of elements. This works fine in the regime where the size is always rounded up to the next power of 2, as this results in the same capacity for all input arguments that are between two powers of 2. But in the recently added regime targeting 1.25 allocated space, two capacities that differ by just 1 byte will always get different new capacities, effectively triggering a reallocation for every resize call that grows the vector, even if it could have fit into the existing capacity. As far as I can see, this can be fixed by only calculating the new capacity if the new size is larger than the current capacity (not the current size) in

   faiss/faiss/gpu/utils/DeviceVector.cuh

   Lines 135 to 137 in f262011

   	if (num_ < newSize) {
   	mem = reserve(getNewCapacity_(newSize), stream);
   	}

   Since the call to reserve() is a no-op for sizes that are not bigger than the current capacity, this should not be a problem.
2. There's a typo in the calculation for 1.25x the allocation size:

   faiss/faiss/gpu/utils/DeviceVector.cuh

   Line 252 in f262011

   return preferredSize + (preferredSize << 2);

   The bit-shift should be >> instead of <<, as at the moment it actually returns 5x the requested allocation size.

I compiled with the mentioned changes, and no longer see the mentioned performance & memory problems.

Hope that helps, and thanks for the speedy library! 🚀

Platform

x86-64, intel
RTX 4090

OS: Ubuntu 20.04 LTS

Faiss version:
1.7.4
Installed from: anaconda, but also built myself

Running on:

• CPU
• GPU

Interface:

• C++
• Python

Reproduction instructions

Create a GPUIVFFlat index with L2 norm and d=40 and 100 centroids.
train with 10M vectors and add 10M vectors to it. Observe time for adding and memory use.

Repeat the same with 5000 centroids.
time for adding and memory use should be much lower.

[mdouze]

Thanks for the careful report. @wickedfoo would you mind taking a look?

[wickedfoo]

Thanks for noticing this!

#3256 should fix.

[wickedfoo]

should be fixed in the source tree
updated conda/etc packages will have to wait until we refresh those

[gabuzi]

Awesome, thanks!