Feature: Improve index_gt::search_for_one_ by avoiding entry-node locks for immutable index

[yoonseok-kim]

Hi.

Describe what you are looking for

USearch/include/usearch/index.hpp

Lines 3990 to 4008 in a2f1759

	template <typename value_at, typename metric_at, typename prefetch_at = dummy_prefetch_t>
	compressed_slot_t search_for_one_( //
	value_at&& query, metric_at&& metric, prefetch_at&& prefetch, //
	compressed_slot_t closest_slot, level_t begin_level, level_t end_level, context_t& context) const noexcept {
	visits_hash_set_t& visits = context.visits;
	visits.clear();
	// Optional prefetching
	if (!is_dummy<prefetch_at>())
	prefetch(citerator_at(closest_slot), citerator_at(closest_slot) + 1);
	distance_t closest_dist = context.measure(query, citerator_at(closest_slot), metric);
	for (level_t level = begin_level; level > end_level; --level) {
	bool changed;
	do {
	changed = false;
	node_lock_t closest_lock = node_lock_(closest_slot);
	neighbors_ref_t closest_neighbors = neighbors_non_base_(node_at_(closest_slot), level);

Currently, index_gt::search_for_one_ acquires a lock on the entry slot while traversing from the top level(begin_level) to the level above the base level(end_level), and it is used by the search, add, and update code paths.

USearch/include/usearch/index.hpp

Lines 3503 to 3509 in a2f1759

	/**
	* @brief Memory-maps the serialized binary index representation from disk,
	* @b without copying data into RAM, and fetching it on-demand.
	*/
	template <typename progress_at = dummy_progress_t>
	serialization_result_t view(memory_mapped_file_t file, std::size_t offset = 0,
	progress_at&& progress = {}) noexcept {

USearch/include/usearch/index.hpp

Line 3574 in a2f1759

viewed_file_ = std::move(file);

When index_gt is used as an immutable view, acquiring locks inside index_gt::search_for_one_ should not be necessary. In this case, the index structure is guaranteed not to change, so locking entry slots becomes unnecessary overhead.

USearch/include/usearch/index.hpp

Line 2297 in a2f1759

bool is_immutable() const noexcept { return bool(viewed_file_); }

Based on this, index_gt::search_for_one_ could be optimized by checking whether the index is immutable and skipping lock acquisition on the entry slot at each level. This is expected to improve search performance when index_gt is used as a view.

To apply this idea, the optional_node_lock_t that I previously introduced can be used to easily implement it.

I have submitted a PR(#689). I would appreciate it if you could take a look. :)

Can you contribute to the implementation?

• I can contribute

Is your feature request specific to a certain interface?

C++ implementation

Contact Details

kys910524@gmail.com

Is there an existing issue for this?

• I have searched the existing issues

Code of Conduct

• I agree to follow this project's Code of Conduct

[yoonseok-kim]

Thank you for approving my suggestion. :)