microsoft / DiskANN

Graph-structured Indices for Scalable, Fast, Fresh and Filtered Approximate Nearest Neighbor Search
Other
1.06k stars 215 forks source link

only move the queue items if the new item index is less than size #498

Open SMovaghati opened 9 months ago

SMovaghati commented 9 months ago

What does this implement/fix? Briefly explain your changes.

Before, it used to always move the queue items, but that is not necessary if the item to add is at the end of the queue (and queue still has capacity).

mmthomas commented 8 months ago

The code as is currenly correct; there is no rush to merge this change. However, it does allocate extra memory in the vector to support the current insertion strategy, and it keeps track of its own size and capacity.

We have a larger improvment to this whole class that simplifies the logic, reduces the memory requried, and removes the need for and explicit memmove, allowing std:vector to manage the insertion optimally.

@SMovaghati we should bring in all of our changes to this class instead of this small change.