scann-core 0.2.1

Rust bindings for scann-core: ScaNN's approximate nearest-neighbour vector search core as a standalone library (derived from Google's ScaNN; not an official Google product)
Documentation
// Copyright 2026 The Google Research Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Modified in 2026 by Elias Benali (@ebenali) and TheCleaners for
// scann-core (a derived work of ScaNN, not an official Google product);
// see NOTICE.

#include "scann/tree_x_hybrid/internal/utils.h"

#include "absl/container/btree_map.h"
#include "absl/flags/flag.h"
#include "absl/types/span.h"

#ifdef __x86_64__
#include <x86intrin.h>
#endif

#include <algorithm>
#include <cstdint>

#include "scann/utils/common.h"

namespace research_scann {

#ifdef __x86_64__
SCANN_AVX2_OUTLINE size_t Avx2GatherCreateLeafLocalAllowlist(
    RestrictAllowlistConstView global_allowlist,
    RestrictAllowlistMutableView leaf_view,
    ConstSpan<DatapointIndex> leaf_local_to_global) {
  enum : size_t {
    kDatapointIndicesPerRegister = 256 / (sizeof(DatapointIndex) * 8),
    kSizetBits = sizeof(size_t) * 8
  };
  const size_t num_full_iters =
      leaf_local_to_global.size() / kDatapointIndicesPerRegister;
  for (size_t i : Seq(num_full_iters)) {
    const size_t start_idx = i * kDatapointIndicesPerRegister;
    __m256i dp_idxs = _mm256_loadu_si256(
        reinterpret_cast<const __m256i*>(&leaf_local_to_global[start_idx]));
    __m256i uint32_idxs = _mm256_srli_epi32(dp_idxs, 5);
    __m256i bit_idxs = _mm256_and_si256(dp_idxs, _mm256_set1_epi32(0x1F));
    __m256i uint32s = _mm256_i32gather_epi32(
        reinterpret_cast<const int*>(global_allowlist.data()), uint32_idxs, 4);
    __m256i shifted = _mm256_srlv_epi32(uint32s, bit_idxs);
    __m256i mask = _mm256_slli_epi32(shifted, 31);
    // scann-core: explicit bit cast; static_cast between vector types is a
    // clang extension that GCC rejects. Same bits.
    size_t bitmask_bits = _mm256_movemask_ps(_mm256_castsi256_ps(mask));
    leaf_view.data()[start_idx / kSizetBits] |= bitmask_bits
                                                << (start_idx % kSizetBits);
  }
  return num_full_iters * kDatapointIndicesPerRegister;
}

#endif

StatusOr<bool> ValidateDatapointsByToken(
    absl::Span<const std::vector<DatapointIndex>> datapoints_by_token,
    DatapointIndex num_datapoints) {
  bool is_disjoint = true;

  vector<bool> global_bitmap(num_datapoints, false);
  vector<bool> seen_twice(num_datapoints, false);

  for (const std::vector<DatapointIndex>& dp_list : datapoints_by_token) {
    flat_hash_set<DatapointIndex> duplicates;
    for (DatapointIndex dp_index : dp_list) {
      if (!duplicates.insert(dp_index).second) {
        return InvalidArgumentError(
            absl::StrCat("Duplicate datapoint index within a partition of "
                         "datapoints_by_token:  ",
                         dp_index, "."));
      }
      if (dp_index >= num_datapoints) {
        return OutOfRangeError(
            "Datapoint index in datapoints_by_token is >= number of "
            "datapoints in database (%d vs. %d).",
            dp_index, num_datapoints);
      }
      if (global_bitmap[dp_index]) {
        is_disjoint = false;
        if (seen_twice[dp_index]) {
          return InvalidArgumentError(
              StrCat("Datapoint ", dp_index,
                     " represented more than twice in datapoints_by_token.  "
                     "Only TWO_CENTER_ORTHOGONALITY_AMPLIFIED database "
                     "spilling is supported in tree-X hybrid."));
        } else {
          seen_twice[dp_index] = true;
        }
      } else {
        global_bitmap[dp_index] = true;
      }
    }
  }

  const DatapointIndex num_missing =
      std::count(global_bitmap.begin(), global_bitmap.end(), false);
  if (num_missing > 0) {
    auto false_it =
        std::find(global_bitmap.begin(), global_bitmap.end(), false);
    const size_t first_missing = false_it - global_bitmap.begin();
    return InvalidArgumentError(absl::StrCat(
        "Found ", num_missing,
        " datapoint(s) "
        "that are not represented in any partition.  First missing "
        "datapoint index = ",
        first_missing, "."));
  }

  return is_disjoint;
}

vector<uint32_t> SizeByPartition(
    ConstSpan<std::vector<DatapointIndex>> datapoints_by_token) {
  vector<uint32_t> result(datapoints_by_token.size());
  for (size_t i : IndicesOf(datapoints_by_token)) {
    result[i] = datapoints_by_token[i].size();
  }
  return result;
}

// scann-core: duplicates are merged by a stable sort on the datapoint index
// instead of through a flat_hash_map. The merged distances are the same (each
// index's duplicates are still averaged in their original order), but
// upstream emitted the results in the hash map's iteration order, which
// varies from table to table (absl seeds it per table), and the order of the
// candidates changes the last bits of the distances that reordering
// recomputes (SIMD one-to-many kernels round differently depending on a
// datapoint's position): the same search on an unchanged index could return
// slightly different distances. Now the output order, and the search, are
// deterministic.
//
// scann-core: std::sort by (index, distance) rather than std::stable_sort by
// index, which allocated a temporary buffer on every query: the same output.
// A datapoint appears at most twice (SOAR spills it to two partitions), and
// the average of its two distances doesn't depend on their order (0.5 * a +
// 0.5 * b is exact in the halving and commutative in the sum).
void DeduplicateDatabaseSpilledResults(NNResultsVector* results,
                                       size_t final_size) {
  DCHECK_GT(final_size, 0);
  DCHECK_LE(results->size() / 2, final_size);
  std::sort(results->begin(), results->end(),
            [](const pair<DatapointIndex, float>& a,
               const pair<DatapointIndex, float>& b) {
              return a.first < b.first ||
                     (a.first == b.first && a.second < b.second);
            });
  size_t out = 0;
  for (size_t i = 0; i < results->size(); ++i) {
    const auto& neighbor = (*results)[i];
    if (out > 0 && (*results)[out - 1].first == neighbor.first) {
      float& d = (*results)[out - 1].second;
      d = 0.5f * d + 0.5f * neighbor.second;
    } else {
      (*results)[out++] = neighbor;
    }
  }
  results->resize(out);
  if (results->size() > final_size) {
    NthElementBranchOptimized(results->begin(),
                              results->begin() + final_size - 1, results->end(),
                              DistanceComparatorBranchOptimized());
    results->resize(final_size);
  }
}

namespace tree_ah_utils_internal {

namespace {

// scann-core: CombineLeafDatasets returns nothing when the tree has no
// datapoints, as if the leaves had no dataset of that kind, so an index with
// every point deleted serialized without its data and couldn't be loaded.
// Returns an empty dataset of the leaves' dimensionality if a leaf has one.
template <typename T, typename F>
shared_ptr<DenseDataset<T>> EmptyCombinedDataset(size_t n_leaves, F get) {
  for (size_t i = 0; i < n_leaves; ++i) {
    const DenseDataset<T>* leaf = get(i);
    if (leaf != nullptr && leaf->dimensionality() > 0) {
      auto result = make_shared<DenseDataset<T>>();
      result->set_dimensionality(leaf->dimensionality());
      return result;
    }
  }
  return nullptr;
}

}  // namespace

StatusOr<SingleMachineFactoryOptions> FinishMergeAHLeafOptions(
    MutableSpan<SingleMachineFactoryOptions> leaf_opts,
    ConstSpan<std::vector<DatapointIndex>> datapoints_by_token,
    const int expected_size, const float spilling_mult) {
  SingleMachineFactoryOptions opts;

  const auto get_ah = [&](int leaf_idx) {
    return leaf_opts[leaf_idx].hashed_dataset.get();
  };
  if (spilling_mult > 1) {
    using PairOfVectors = pair<vector<uint8_t>, vector<uint8_t>>;
    SCANN_ASSIGN_OR_RETURN(
        PairOfVectors ah_datasets,
        (CombineLeafDatasets<uint8_t, true>(expected_size, "AH",
                                            datapoints_by_token, get_ah)));
    if (!ah_datasets.first.empty()) {
      opts.hashed_dataset = make_shared<DenseDataset<uint8_t>>(
          std::move(ah_datasets.first), expected_size);
      opts.soar_hashed_dataset = make_shared<DenseDataset<uint8_t>>(
          std::move(ah_datasets.second), expected_size);
    }
  } else {
    SCANN_ASSIGN_OR_RETURN(
        vector<uint8_t> ah_dataset,
        (CombineLeafDatasets<uint8_t>(expected_size, "AH", datapoints_by_token,
                                      get_ah)));
    if (!ah_dataset.empty()) {
      opts.hashed_dataset = make_shared<DenseDataset<uint8_t>>(
          std::move(ah_dataset), expected_size);
    }
  }
  const int n_leaves = leaf_opts.size();
  if (n_leaves >= 1) {
    opts.ah_codebook = leaf_opts[0].ah_codebook;
  }
  // scann-core: an empty hashed dataset (one code per codebook block) for a
  // tree with every point deleted; see EmptyCombinedDataset.
  if (expected_size == 0 && opts.hashed_dataset == nullptr &&
      opts.ah_codebook != nullptr &&
      opts.ah_codebook->subspace_centers_size() > 0) {
    opts.hashed_dataset = make_shared<DenseDataset<uint8_t>>();
    opts.hashed_dataset->set_dimensionality(
        opts.ah_codebook->subspace_centers_size());
    if (spilling_mult > 1) {
      opts.soar_hashed_dataset = make_shared<DenseDataset<uint8_t>>();
      opts.soar_hashed_dataset->set_dimensionality(
          opts.ah_codebook->subspace_centers_size());
    }
  }
  if (opts.hashed_dataset != nullptr && !opts.hashed_dataset->empty()) {
    std::string codebook_proto_str;
    leaf_opts[0].ah_codebook->SerializeToString(&codebook_proto_str);

    for (int i = 1; i < n_leaves; i++) {
      std::string codebook_to_compare;
      leaf_opts[i].ah_codebook->SerializeToString(&codebook_to_compare);
      if (codebook_proto_str != codebook_to_compare)
        return FailedPreconditionError("Inconsistent codebooks among leaves");
    }
  }

  const auto get_int8 = [&](int leaf_idx) -> DenseDataset<int8_t>* {
    auto fp = leaf_opts[leaf_idx].pre_quantized_fixed_point;
    if (fp == nullptr) return nullptr;
    return fp->fixed_point_dataset.get();
  };
  SCANN_ASSIGN_OR_RETURN(
      vector<int8_t> int8_dataset,
      (CombineLeafDatasets<int8_t>(expected_size, "INT8", datapoints_by_token,
                                   get_int8)));
  if (int8_dataset.empty() && expected_size == 0) {
    auto empty =
        EmptyCombinedDataset<int8_t>(datapoints_by_token.size(), get_int8);
    if (empty != nullptr) {
      opts.pre_quantized_fixed_point = make_shared<PreQuantizedFixedPoint>();
      opts.pre_quantized_fixed_point->fixed_point_dataset = std::move(empty);
    }
  }
  // scann-core: bfloat16 brute-force leaves (upstream didn't merge them, so
  // serialize() wrote a tree with bfloat16 leaves without any data).
  const auto get_bf16 = [&](int leaf_idx) {
    return leaf_opts[leaf_idx].bfloat16_dataset.get();
  };
  SCANN_ASSIGN_OR_RETURN(
      vector<int16_t> bf16_dataset,
      (CombineLeafDatasets<int16_t>(expected_size, "bfloat16",
                                    datapoints_by_token, get_bf16)));
  if (!bf16_dataset.empty()) {
    opts.bfloat16_dataset = make_shared<DenseDataset<int16_t>>(
        std::move(bf16_dataset), expected_size);
  } else if (expected_size == 0) {
    opts.bfloat16_dataset =
        EmptyCombinedDataset<int16_t>(datapoints_by_token.size(), get_bf16);
  }
  if (!int8_dataset.empty()) {
    opts.pre_quantized_fixed_point = make_shared<PreQuantizedFixedPoint>();
    opts.pre_quantized_fixed_point->fixed_point_dataset =
        make_shared<DenseDataset<int8_t>>(std::move(int8_dataset),
                                          expected_size);

    bool int8_has_norms = false;
    for (int i = 0; i < n_leaves; i++) {
      auto int8 = leaf_opts[i].pre_quantized_fixed_point;
      if (int8 && int8->squared_l2_norm_by_datapoint &&
          !int8->squared_l2_norm_by_datapoint->empty())
        int8_has_norms = true;
    }
    if (int8_has_norms) {
      opts.pre_quantized_fixed_point->squared_l2_norm_by_datapoint =
          make_shared<vector<float>>(expected_size);
      for (int i = 0; i < n_leaves; i++) {
        auto int8 = leaf_opts[i].pre_quantized_fixed_point;
        for (const auto [inner_idx, global_idx] :
             Enumerate(datapoints_by_token[i])) {
          opts.pre_quantized_fixed_point->squared_l2_norm_by_datapoint->at(
              global_idx) = int8->squared_l2_norm_by_datapoint->at(inner_idx);
        }
      }
    }
  }
  return opts;
}

}  // namespace tree_ah_utils_internal

}  // namespace research_scann