| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2026 Tiger Data, Inc. | ||
| 3 | * Licensed under the PostgreSQL License. See LICENSE for details. | ||
| 4 | * | ||
| 5 | * topk.c - Top-K collection | ||
| 6 | * | ||
| 7 | * Threshold heap: max-heap of K Distance values (upper bounds). | ||
| 8 | * Candidate buffer: growable array of all entries that passed | ||
| 9 | * the threshold check. | ||
| 10 | * Id map: heap position of each id, for vs_topk_insert's dedup lookup. | ||
| 11 | * | ||
| 12 | * Used by both standalone and PG builds. | ||
| 13 | */ | ||
| 14 | |||
| 15 | #include <stdlib.h> | ||
| 16 | #include <string.h> | ||
| 17 | |||
| 18 | #include "algo/topk.h" | ||
| 19 | #include "core/idset.h" | ||
| 20 | #include "core/memory.h" | ||
| 21 | #include "core/platform.h" | ||
| 22 | |||
| 23 | #define VS_TOPK_INITIAL_CAP_MIN 32 | ||
| 24 | |||
| 25 | /* ---------------------------------------------------------------- | ||
| 26 | * Id -> heap position map | ||
| 27 | * | ||
| 28 | * Linear probing over a power-of-two slot array sized for at most half | ||
| 29 | * load at k_capacity. Deletion shifts later entries back into the hole | ||
| 30 | * rather than leaving tombstones, so probe chains stay short however | ||
| 31 | * many evictions a scan makes. | ||
| 32 | * ---------------------------------------------------------------- */ | ||
| 33 | |||
| 34 | #define VS_TOPK_MAP_EMPTY UINT32_MAX | ||
| 35 | |||
| 36 | static inline uint32_t | ||
| 37 | 961724 | map_home(const VsTopK *topk, uint64_t id) | |
| 38 | { | ||
| 39 | 961724 | return (uint32_t)((id * VS_HASH_GOLDEN_GAMMA) >> topk->map_shift); | |
| 40 | } | ||
| 41 | |||
| 42 | /* Slot holding `id`, or VS_TOPK_MAP_EMPTY if it is not in the heap. */ | ||
| 43 | static inline uint32_t | ||
| 44 | 821419 | map_find(const VsTopK *topk, uint64_t id) | |
| 45 | { | ||
| 46 | 821419 | uint32_t slot = map_home(topk, id); | |
| 47 |
2/2✓ Branch 0 taken 366346 times.
✓ Branch 1 taken 815549 times.
|
1181895 | while (topk->map_pos[slot] != VS_TOPK_MAP_EMPTY) |
| 48 | { | ||
| 49 |
2/2✓ Branch 0 taken 16108 times.
✓ Branch 1 taken 350238 times.
|
366346 | if (topk->map_ids[slot] == id) |
| 50 | 5394 | return slot; | |
| 51 | 360476 | slot = (slot + 1) & topk->map_mask; | |
| 52 | } | ||
| 53 | 782201 | return VS_TOPK_MAP_EMPTY; | |
| 54 | } | ||
| 55 | |||
| 56 | /* Record that heap position `pos` holds `id` (absent from the map). */ | ||
| 57 | static inline void | ||
| 58 | 124190 | map_add(VsTopK *topk, uint64_t id, uint32_t pos) | |
| 59 | { | ||
| 60 | 124190 | uint32_t slot = map_home(topk, id); | |
| 61 |
2/2✓ Branch 0 taken 18201 times.
✓ Branch 1 taken 124190 times.
|
142391 | while (topk->map_pos[slot] != VS_TOPK_MAP_EMPTY) |
| 62 | 18201 | slot = (slot + 1) & topk->map_mask; | |
| 63 | 124190 | topk->map_ids[slot] = id; | |
| 64 | 124190 | topk->map_pos[slot] = pos; | |
| 65 | 124190 | topk->ub_slot[pos] = slot; | |
| 66 | 124190 | } | |
| 67 | |||
| 68 | static void | ||
| 69 | 59340 | map_remove(VsTopK *topk, uint32_t slot) | |
| 70 | { | ||
| 71 | 59340 | uint32_t mask = topk->map_mask; | |
| 72 | 59340 | uint32_t hole = slot; | |
| 73 | |||
| 74 |
2/2✓ Branch 0 taken 16115 times.
✓ Branch 1 taken 59340 times.
|
75455 | for (uint32_t j = (hole + 1) & mask; topk->map_pos[j] != VS_TOPK_MAP_EMPTY; |
| 75 | 16115 | j = (j + 1) & mask) | |
| 76 | { | ||
| 77 | /* Move j into the hole unless that would put it before its | ||
| 78 | * home slot, where lookups would no longer reach it. */ | ||
| 79 | 16115 | uint32_t home = map_home(topk, topk->map_ids[j]); | |
| 80 |
2/2✓ Branch 0 taken 4181 times.
✓ Branch 1 taken 11934 times.
|
16115 | if (((j - home) & mask) >= ((j - hole) & mask)) |
| 81 | { | ||
| 82 | 4181 | topk->map_ids[hole] = topk->map_ids[j]; | |
| 83 | 4181 | topk->map_pos[hole] = topk->map_pos[j]; | |
| 84 | 4181 | topk->ub_slot[topk->map_pos[hole]] = hole; | |
| 85 | 4181 | hole = j; | |
| 86 | } | ||
| 87 | } | ||
| 88 | 59340 | topk->map_pos[hole] = VS_TOPK_MAP_EMPTY; | |
| 89 | 59340 | } | |
| 90 | |||
| 91 | /* Allocate the map on the first deduping insert, indexing whatever | ||
| 92 | * unique inserts already put in the heap. */ | ||
| 93 | static void | ||
| 94 | 798 | map_build(VsTopK *topk) | |
| 95 | { | ||
| 96 | 798 | uint32_t bits = 1; | |
| 97 |
2/2✓ Branch 0 taken 3683 times.
✓ Branch 1 taken 798 times.
|
4481 | while ((1ull << bits) < 2ull * topk->k_capacity) |
| 98 | 3683 | bits++; | |
| 99 | |||
| 100 | 798 | uint32_t nslots = 1u << bits; | |
| 101 | 798 | topk->map_ids = vs_memctx_alloc(topk->memctx, nslots * sizeof(uint64_t)); | |
| 102 | 798 | topk->map_pos = vs_memctx_alloc(topk->memctx, nslots * sizeof(uint32_t)); | |
| 103 | 1146 | topk->ub_slot = | |
| 104 | 798 | vs_memctx_alloc(topk->memctx, topk->k_capacity * sizeof(uint32_t)); | |
| 105 | 798 | topk->map_mask = nslots - 1; | |
| 106 | 798 | topk->map_shift = 64 - bits; | |
| 107 | |||
| 108 | 798 | memset(topk->map_pos, 0xFF, nslots * sizeof(uint32_t)); | |
| 109 |
2/2✓ Branch 0 taken 64 times.
✓ Branch 1 taken 798 times.
|
862 | for (uint32_t i = 0; i < topk->ub_count; i++) |
| 110 | 64 | map_add(topk, topk->ub_ids[i], i); | |
| 111 | 798 | } | |
| 112 | |||
| 113 | /* ---------------------------------------------------------------- | ||
| 114 | * Threshold heap (max-heap of Distance values) | ||
| 115 | * | ||
| 116 | * The sifts take the heap's arrays as locals, so stores through them | ||
| 117 | * don't force reloads of the pointers from VsTopK. With `track`, every | ||
| 118 | * move also updates the id map. | ||
| 119 | * ---------------------------------------------------------------- */ | ||
| 120 | |||
| 121 | typedef struct HeapArrays | ||
| 122 | { | ||
| 123 | Distance *ub; | ||
| 124 | uint64_t *ids; | ||
| 125 | uint32_t *slot; /* ub_slot, used only when tracking */ | ||
| 126 | uint32_t *pos; /* map_pos, used only when tracking */ | ||
| 127 | } HeapArrays; | ||
| 128 | |||
| 129 | static inline HeapArrays | ||
| 130 | 28063450 | heap_arrays(const VsTopK *topk) | |
| 131 | { | ||
| 132 | 33957114 | return (HeapArrays){ | |
| 133 | 28063450 | .ub = topk->ub_heap, | |
| 134 | 28063450 | .ids = topk->ub_ids, | |
| 135 | 28063450 | .slot = topk->ub_slot, | |
| 136 | 28063450 | .pos = topk->map_pos, | |
| 137 | }; | ||
| 138 | } | ||
| 139 | |||
| 140 | static inline void | ||
| 141 | 55020951 | ub_swap(HeapArrays h, uint32_t a, uint32_t b, bool track) | |
| 142 | { | ||
| 143 | 55020951 | Distance tmp = h.ub[a]; | |
| 144 | 55020951 | h.ub[a] = h.ub[b]; | |
| 145 | 55020951 | h.ub[b] = tmp; | |
| 146 | 55020951 | uint64_t tid = h.ids[a]; | |
| 147 | 55020951 | h.ids[a] = h.ids[b]; | |
| 148 | 55020951 | h.ids[b] = tid; | |
| 149 | |||
| 150 |
2/2✓ Branch 0 taken 170130 times.
✓ Branch 1 taken 54850821 times.
|
55020951 | if (track) |
| 151 | { | ||
| 152 | 170130 | uint32_t sa = h.slot[a]; | |
| 153 | 170130 | uint32_t sb = h.slot[b]; | |
| 154 | 170130 | h.slot[a] = sb; | |
| 155 | 170130 | h.slot[b] = sa; | |
| 156 | 170130 | h.pos[sb] = a; | |
| 157 | 170130 | h.pos[sa] = b; | |
| 158 | } | ||
| 159 | 55020951 | } | |
| 160 | |||
| 161 | static inline void | ||
| 162 | 15805200 | ub_sift_up(HeapArrays h, uint32_t i, bool track) | |
| 163 | { | ||
| 164 |
2/2✓ Branch 0 taken 29348477 times.
✓ Branch 1 taken 3089077 times.
|
32437554 | while (i > 0) |
| 165 | { | ||
| 166 | 29348477 | uint32_t parent = (i - 1) / 2; | |
| 167 |
2/2✓ Branch 0 taken 16036767 times.
✓ Branch 1 taken 13311710 times.
|
29348477 | if (h.ub[i] <= h.ub[parent]) |
| 168 | 2350194 | break; | |
| 169 | 16632354 | ub_swap(h, i, parent, track); | |
| 170 | 16632354 | i = parent; | |
| 171 | } | ||
| 172 | 15805200 | } | |
| 173 | |||
| 174 | static inline void | ||
| 175 | 12258250 | ub_sift_down(HeapArrays h, uint32_t count, uint32_t i, bool track) | |
| 176 | { | ||
| 177 | 68148974 | for (;;) | |
| 178 | 38388597 | { | |
| 179 | 50646847 | uint32_t left = 2 * i + 1; | |
| 180 | 50646847 | uint32_t right = 2 * i + 2; | |
| 181 | 50646847 | uint32_t largest = i; | |
| 182 | |||
| 183 |
4/4✓ Branch 0 taken 15448469 times.
✓ Branch 1 taken 35198378 times.
✓ Branch 2 taken 15241629 times.
✓ Branch 3 taken 28934491 times.
|
50646847 | if (left < count && h.ub[left] > h.ub[largest]) |
| 184 | 46920091 | largest = left; | |
| 185 |
4/4✓ Branch 0 taken 15825669 times.
✓ Branch 1 taken 34821178 times.
✓ Branch 2 taken 22677291 times.
✓ Branch 3 taken 20787847 times.
|
50646847 | if (right < count && h.ub[right] > h.ub[largest]) |
| 186 | 43226865 | largest = right; | |
| 187 | |||
| 188 |
2/2✓ Branch 0 taken 32236289 times.
✓ Branch 1 taken 18410558 times.
|
50646847 | if (largest == i) |
| 189 | 2860618 | break; | |
| 190 | |||
| 191 | 38388597 | ub_swap(h, i, largest, track); | |
| 192 | 38388597 | i = largest; | |
| 193 | } | ||
| 194 | 12258250 | } | |
| 195 | |||
| 196 | /* Add an id that isn't in the heap. It is appended while the heap holds | ||
| 197 | * fewer than k entries and otherwise replaces the root if ub beats it. */ | ||
| 198 | __attribute__((always_inline)) static inline void | ||
| 199 | 22184574 | ub_insert(VsTopK *topk, Distance ub, uint64_t id, bool track) | |
| 200 | { | ||
| 201 |
6/6✓ Branch 0 taken 53188 times.
✓ Branch 1 taken 729013 times.
✓ Branch 2 taken 2979770 times.
✓ Branch 3 taken 2806946 times.
✓ Branch 4 taken 88 times.
✓ Branch 5 taken 340 times.
|
28753919 | if (topk->ub_count < topk->k) |
| 202 | { | ||
| 203 | 15805200 | uint32_t i = topk->ub_count++; | |
| 204 | 15805200 | topk->ub_heap[i] = ub; | |
| 205 | 15805200 | topk->ub_ids[i] = id; | |
| 206 |
3/6✓ Branch 0 taken 53188 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2979770 times.
✓ Branch 4 taken 88 times.
✗ Branch 5 not taken.
|
15805200 | if (track) |
| 207 | 64786 | map_add(topk, id, i); | |
| 208 | 15805200 | ub_sift_up(heap_arrays(topk), i, track); | |
| 209 | } | ||
| 210 |
5/6✓ Branch 0 taken 59182 times.
✓ Branch 1 taken 691669 times.
✓ Branch 2 taken 12197528 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 158 times.
✓ Branch 5 taken 182 times.
|
12948719 | else if (ub < topk->ub_heap[0]) |
| 211 | { | ||
| 212 |
3/6✓ Branch 0 taken 52240 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2806946 times.
✓ Branch 4 taken 158 times.
✗ Branch 5 not taken.
|
12256868 | if (track) |
| 213 | 59340 | map_remove(topk, topk->ub_slot[0]); | |
| 214 | 12256868 | topk->ub_heap[0] = ub; | |
| 215 | 12256868 | topk->ub_ids[0] = id; | |
| 216 |
3/6✓ Branch 0 taken 52240 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 2806946 times.
✓ Branch 4 taken 158 times.
✗ Branch 5 not taken.
|
12256868 | if (track) |
| 217 | 59340 | map_add(topk, id, 0); | |
| 218 | 12256868 | ub_sift_down(heap_arrays(topk), topk->ub_count, 0, track); | |
| 219 | } | ||
| 220 | 6569345 | } | |
| 221 | |||
| 222 | /* ---------------------------------------------------------------- | ||
| 223 | * Comparator for qsort (ascending by distance) | ||
| 224 | * ---------------------------------------------------------------- */ | ||
| 225 | |||
| 226 | static int | ||
| 227 | 69206673 | cmp_by_distance(const void *a, const void *b) | |
| 228 | { | ||
| 229 | 69206673 | const VsTopKEntry *ea = (const VsTopKEntry *)a; | |
| 230 | 69206673 | const VsTopKEntry *eb = (const VsTopKEntry *)b; | |
| 231 |
2/2✓ Branch 0 taken 36056865 times.
✓ Branch 1 taken 33149808 times.
|
69206673 | if (ea->distance < eb->distance) |
| 232 | 5568603 | return -1; | |
| 233 |
2/2✓ Branch 0 taken 35878627 times.
✓ Branch 1 taken 86418 times.
|
35965045 | if (ea->distance > eb->distance) |
| 234 | 35878627 | return 1; | |
| 235 | 84571 | return 0; | |
| 236 | } | ||
| 237 | |||
| 238 | /* ---------------------------------------------------------------- | ||
| 239 | * Init / cleanup / create / destroy | ||
| 240 | * ---------------------------------------------------------------- */ | ||
| 241 | |||
| 242 | void | ||
| 243 | 42506 | vs_topk_init(VsTopK *topk, uint32_t k) | |
| 244 | { | ||
| 245 | 42506 | topk->memctx = vs_memctx_create(NULL, "topk"); | |
| 246 | 42506 | topk->k = k; | |
| 247 | 42506 | topk->k_capacity = k; | |
| 248 | 42506 | topk->ub_heap = vs_memctx_alloc(topk->memctx, k * sizeof(Distance)); | |
| 249 | 42506 | topk->ub_ids = vs_memctx_alloc(topk->memctx, k * sizeof(uint64_t)); | |
| 250 | 42506 | topk->ub_count = 0; | |
| 251 | |||
| 252 | 42506 | uint32_t cap = k * 2; | |
| 253 |
2/2✓ Branch 0 taken 474 times.
✓ Branch 1 taken 466 times.
|
42506 | if (cap < VS_TOPK_INITIAL_CAP_MIN) |
| 254 | 474 | cap = VS_TOPK_INITIAL_CAP_MIN; | |
| 255 | 84072 | topk->candidates = | |
| 256 | 42506 | vs_memctx_alloc(topk->memctx, cap * sizeof(VsTopKEntry)); | |
| 257 | 42506 | topk->cand_count = 0; | |
| 258 | 42506 | topk->cand_capacity = cap; | |
| 259 | /* Stamped onto every insert; only the query scan ever sets it. */ | ||
| 260 | 42506 | topk->cur_src = 0; | |
| 261 | |||
| 262 | 42506 | topk->map_ids = NULL; | |
| 263 | 42506 | topk->map_pos = NULL; | |
| 264 | 42506 | topk->ub_slot = NULL; | |
| 265 | 42506 | topk->map_mask = 0; | |
| 266 | 42506 | topk->map_shift = 0; | |
| 267 | 42506 | } | |
| 268 | |||
| 269 | void | ||
| 270 | 42502 | vs_topk_cleanup(VsTopK *topk) | |
| 271 | { | ||
| 272 |
2/2✓ Branch 0 taken 41562 times.
✓ Branch 1 taken 940 times.
|
42502 | if (topk == NULL) |
| 273 | ✗ | return; | |
| 274 |
1/2✓ Branch 0 taken 42502 times.
✗ Branch 1 not taken.
|
42502 | if (topk->memctx != NULL) |
| 275 | { | ||
| 276 | 42502 | vs_memctx_delete(topk->memctx); | |
| 277 | 42502 | topk->memctx = NULL; | |
| 278 | } | ||
| 279 | 42502 | topk->ub_heap = NULL; | |
| 280 | 42502 | topk->ub_ids = NULL; | |
| 281 | 42502 | topk->candidates = NULL; | |
| 282 | 42502 | topk->map_ids = NULL; | |
| 283 | 42502 | topk->map_pos = NULL; | |
| 284 | 42502 | topk->ub_slot = NULL; | |
| 285 | } | ||
| 286 | |||
| 287 | VsTopK * | ||
| 288 | 6 | vs_topk_create(uint32_t k) | |
| 289 | { | ||
| 290 | /* The handle comes from the caller's context rather than from the arena | ||
| 291 | * it owns. vs_topk_reset_to_k resets that arena when k outgrows it, | ||
| 292 | * which would reclaim the object being reset through. */ | ||
| 293 | 6 | VsTopK *topk = vs_alloc(sizeof(VsTopK)); | |
| 294 | 6 | vs_topk_init(topk, k); | |
| 295 | 6 | return topk; | |
| 296 | } | ||
| 297 | |||
| 298 | void | ||
| 299 | 6 | vs_topk_destroy(VsTopK *topk) | |
| 300 | { | ||
| 301 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
|
6 | if (topk == NULL) |
| 302 | ✗ | return; | |
| 303 | 6 | vs_topk_cleanup(topk); | |
| 304 | 6 | vs_free(topk); | |
| 305 | } | ||
| 306 | |||
| 307 | void | ||
| 308 | 4 | vs_topk_reset(VsTopK *topk) | |
| 309 | { | ||
| 310 | 4 | vs_topk_reset_to_k(topk, topk->k); | |
| 311 | 4 | } | |
| 312 | |||
| 313 | void | ||
| 314 | 938572 | vs_topk_reset_to_k(VsTopK *topk, uint32_t k) | |
| 315 | { | ||
| 316 | /* O(1) reset: buffers are retained across resets (grow-only), so a | ||
| 317 | * reused top-K reaches a steady state with zero allocator traffic. | ||
| 318 | * Only a k above the allocated capacity re-allocates — reset the | ||
| 319 | * arena first so the outgrown blocks are reclaimed rather than | ||
| 320 | * leaked into the context. The candidate buffer keeps its | ||
| 321 | * high-water capacity, avoiding the doubling-regrowth copies that | ||
| 322 | * a fresh buffer paid on every use. */ | ||
| 323 |
2/2✓ Branch 0 taken 18 times.
✓ Branch 1 taken 938554 times.
|
938572 | if (vs_unlikely(k > topk->k_capacity)) |
| 324 | { | ||
| 325 | 18 | uint32_t cand_cap = topk->cand_capacity; | |
| 326 | 18 | uint32_t min_cap = k * 2; | |
| 327 | |||
| 328 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 14 times.
|
18 | if (cand_cap < min_cap) |
| 329 | 4 | cand_cap = min_cap; | |
| 330 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
|
18 | if (cand_cap < VS_TOPK_INITIAL_CAP_MIN) |
| 331 | ✗ | cand_cap = VS_TOPK_INITIAL_CAP_MIN; | |
| 332 | |||
| 333 | 18 | vs_memctx_reset(topk->memctx); | |
| 334 | 18 | topk->ub_heap = vs_memctx_alloc(topk->memctx, k * sizeof(Distance)); | |
| 335 | 18 | topk->ub_ids = vs_memctx_alloc(topk->memctx, k * sizeof(uint64_t)); | |
| 336 | 18 | topk->candidates = | |
| 337 | 18 | vs_memctx_alloc(topk->memctx, cand_cap * sizeof(VsTopKEntry)); | |
| 338 | 18 | topk->cand_capacity = cand_cap; | |
| 339 | 18 | topk->k_capacity = k; | |
| 340 | 18 | topk->map_ids = NULL; | |
| 341 | 18 | topk->map_pos = NULL; | |
| 342 | 18 | topk->ub_slot = NULL; | |
| 343 | } | ||
| 344 |
2/2✓ Branch 0 taken 8709 times.
✓ Branch 1 taken 929845 times.
|
938554 | else if (topk->map_pos != NULL) |
| 345 | { | ||
| 346 | /* Clear only the occupied slots. */ | ||
| 347 |
2/2✓ Branch 0 taken 16012 times.
✓ Branch 1 taken 8709 times.
|
24721 | for (uint32_t i = 0; i < topk->ub_count; i++) |
| 348 | 16012 | topk->map_pos[topk->ub_slot[i]] = VS_TOPK_MAP_EMPTY; | |
| 349 | } | ||
| 350 | |||
| 351 | 938572 | topk->k = k; | |
| 352 | 938572 | topk->ub_count = 0; | |
| 353 | 938572 | topk->cand_count = 0; | |
| 354 | 938572 | } | |
| 355 | |||
| 356 | void | ||
| 357 | 54476234 | vs_topk_insert_unique( | |
| 358 | VsTopK *topk, Distance distance, Distance error, uint64_t id) | ||
| 359 | { | ||
| 360 | 54476234 | Distance lb = distance - error; | |
| 361 | 54476234 | Distance ub = distance + error; | |
| 362 | |||
| 363 | /* Prune: lower bound exceeds threshold. Written NaN-safe: a NaN | ||
| 364 | * estimate (e.g. a zero vector normalized for cosine) fails every | ||
| 365 | * comparison, so the naive lb >= threshold guard would admit it -- | ||
| 366 | * and one NaN upper bound in the heap corrupts the threshold for | ||
| 367 | * the rest of the scan. */ | ||
| 368 |
4/4✓ Branch 0 taken 29226370 times.
✓ Branch 1 taken 19462720 times.
✓ Branch 2 taken 27938370 times.
✓ Branch 3 taken 19835788 times.
|
83702604 | if (!(lb < vs_topk_threshold(topk))) |
| 369 | 6702076 | return; | |
| 370 | |||
| 371 | /* No dedup lookup: caller guarantees ids are unique. A map that | ||
| 372 | * vs_topk_insert built is kept current. */ | ||
| 373 |
2/2✓ Branch 0 taken 27937942 times.
✓ Branch 1 taken 428 times.
|
27938370 | if (topk->map_pos == NULL) |
| 374 |
2/2✓ Branch 0 taken 12760644 times.
✓ Branch 1 taken 9390582 times.
|
22151226 | ub_insert(topk, ub, id, false); |
| 375 | else | ||
| 376 | ✗ | ub_insert(topk, ub, id, true); | |
| 377 | |||
| 378 | /* Grow candidate buffer if needed (old buffer freed with memctx) */ | ||
| 379 |
2/2✓ Branch 0 taken 38 times.
✓ Branch 1 taken 27938332 times.
|
27938370 | if (topk->cand_count == topk->cand_capacity) |
| 380 | { | ||
| 381 | 38 | uint32_t new_cap = topk->cand_capacity * 2; | |
| 382 | 26 | VsTopKEntry *new_buf = | |
| 383 | 38 | vs_memctx_alloc(topk->memctx, new_cap * sizeof(VsTopKEntry)); | |
| 384 | 38 | memcpy(new_buf, | |
| 385 | 38 | topk->candidates, | |
| 386 | 38 | topk->cand_count * sizeof(VsTopKEntry)); | |
| 387 | 38 | topk->candidates = new_buf; | |
| 388 | 38 | topk->cand_capacity = new_cap; | |
| 389 | } | ||
| 390 | |||
| 391 | 27938370 | topk->candidates[topk->cand_count++] = (VsTopKEntry){ | |
| 392 | .distance = distance, | ||
| 393 | .error = error, | ||
| 394 | .id = id, | ||
| 395 | 27938370 | .src = topk->cur_src, | |
| 396 | }; | ||
| 397 | } | ||
| 398 | |||
| 399 | /* ---------------------------------------------------------------- | ||
| 400 | * Insert | ||
| 401 | * ---------------------------------------------------------------- */ | ||
| 402 | |||
| 403 | void | ||
| 404 | 1178565 | vs_topk_insert(VsTopK *topk, Distance distance, Distance error, uint64_t id) | |
| 405 | { | ||
| 406 | 1178565 | Distance lb = distance - error; | |
| 407 | 1178565 | Distance ub = distance + error; | |
| 408 | |||
| 409 | /* Prune: lower bound exceeds threshold. Written NaN-safe: a NaN | ||
| 410 | * estimate (e.g. a zero vector normalized for cosine) fails every | ||
| 411 | * comparison, so the naive lb >= threshold guard would admit it -- | ||
| 412 | * and one NaN upper bound in the heap corrupts the threshold for | ||
| 413 | * the rest of the scan. */ | ||
| 414 |
4/4✓ Branch 0 taken 22400 times.
✓ Branch 1 taken 368570 times.
✓ Branch 2 taken 821419 times.
✓ Branch 3 taken 333 times.
|
1200965 | if (!(lb < vs_topk_threshold(topk))) |
| 415 | 356813 | return; | |
| 416 | |||
| 417 | /* Dedup: if this ID is already in the heap, keep only the better | ||
| 418 | * (smaller) upper bound. This prevents duplicates (e.g. SOAR | ||
| 419 | * replicas) from occupying multiple heap slots and inflating the | ||
| 420 | * threshold. */ | ||
| 421 |
2/2✓ Branch 0 taken 798 times.
✓ Branch 1 taken 820621 times.
|
821419 | if (vs_unlikely(topk->map_pos == NULL)) |
| 422 | 798 | map_build(topk); | |
| 423 | |||
| 424 | 821419 | uint32_t slot = map_find(topk, id); | |
| 425 |
2/2✓ Branch 0 taken 5870 times.
✓ Branch 1 taken 815549 times.
|
821419 | if (slot != VS_TOPK_MAP_EMPTY) |
| 426 | { | ||
| 427 | 5870 | uint32_t i = topk->map_pos[slot]; | |
| 428 |
2/2✓ Branch 0 taken 1382 times.
✓ Branch 1 taken 4488 times.
|
5870 | if (ub < topk->ub_heap[i]) |
| 429 | { | ||
| 430 | 1382 | topk->ub_heap[i] = ub; | |
| 431 | 1382 | ub_sift_down(heap_arrays(topk), topk->ub_count, i, true); | |
| 432 | } | ||
| 433 | 5870 | goto append; | |
| 434 | } | ||
| 435 | |||
| 436 |
2/2✓ Branch 0 taken 11510 times.
✓ Branch 1 taken 21838 times.
|
33348 | ub_insert(topk, ub, id, true); |
| 437 | |||
| 438 | 821419 | append: | |
| 439 | /* Grow candidate buffer if needed (old buffer freed with memctx) */ | ||
| 440 |
2/2✓ Branch 0 taken 715 times.
✓ Branch 1 taken 820704 times.
|
821419 | if (topk->cand_count == topk->cand_capacity) |
| 441 | { | ||
| 442 | 715 | uint32_t new_cap = topk->cand_capacity * 2; | |
| 443 | 269 | VsTopKEntry *new_buf = | |
| 444 | 715 | vs_memctx_alloc(topk->memctx, new_cap * sizeof(VsTopKEntry)); | |
| 445 | 715 | memcpy(new_buf, | |
| 446 | 715 | topk->candidates, | |
| 447 | 715 | topk->cand_count * sizeof(VsTopKEntry)); | |
| 448 | 715 | topk->candidates = new_buf; | |
| 449 | 715 | topk->cand_capacity = new_cap; | |
| 450 | } | ||
| 451 | |||
| 452 | /* Append to candidate buffer */ | ||
| 453 | 821419 | topk->candidates[topk->cand_count++] = (VsTopKEntry){ | |
| 454 | .distance = distance, | ||
| 455 | .error = error, | ||
| 456 | .id = id, | ||
| 457 | 821419 | .src = topk->cur_src, | |
| 458 | }; | ||
| 459 | } | ||
| 460 | |||
| 461 | /* | ||
| 462 | * Deduplicate a distance-sorted candidate prefix in place, keeping the | ||
| 463 | * first (best-distance) entry per ID, tracked in an id set. A rescan | ||
| 464 | * of prior survivors per entry would go quadratic in the survivor | ||
| 465 | * count; the set keeps this pass linear. Returns the deduplicated | ||
| 466 | * count, additionally truncated to `cap` unique entries when cap > 0. | ||
| 467 | */ | ||
| 468 | static uint32_t | ||
| 469 | 9440 | dedup_sorted_prefix(VsTopKEntry *results, uint32_t n, uint32_t cap) | |
| 470 | { | ||
| 471 |
2/2✓ Branch 0 taken 4241 times.
✓ Branch 1 taken 5199 times.
|
9440 | if (n <= 1) |
| 472 | 3880 | return n; | |
| 473 | |||
| 474 | 361 | VsIdSet seen; | |
| 475 | 5553 | vs_idset_init(&seen, n); | |
| 476 | |||
| 477 | 5553 | uint32_t w = 0; | |
| 478 |
3/3✓ Branch 0 taken 157719 times.
✓ Branch 1 taken 17115 times.
✓ Branch 2 taken 286 times.
|
175120 | for (uint32_t r = 0; r < n; r++) |
| 479 | { | ||
| 480 |
2/2✓ Branch 1 taken 6015 times.
✓ Branch 2 taken 168378 times.
|
174393 | if (!vs_idset_test_add(&seen, results[r].id)) |
| 481 | 6015 | continue; | |
| 482 | 168378 | results[w++] = results[r]; | |
| 483 |
4/4✓ Branch 0 taken 109661 times.
✓ Branch 1 taken 58717 times.
✓ Branch 2 taken 4751 times.
✓ Branch 3 taken 89062 times.
|
168378 | if (cap > 0 && w == cap) |
| 484 | 4751 | break; | |
| 485 | } | ||
| 486 |
1/2✓ Branch 0 taken 361 times.
✗ Branch 1 not taken.
|
5553 | vs_idset_cleanup(&seen); |
| 487 | 5192 | return w; | |
| 488 | } | ||
| 489 | |||
| 490 | /* | ||
| 491 | * Partially order `results` so the `want` smallest-distance entries | ||
| 492 | * occupy the front (in arbitrary order within each side). Iterative | ||
| 493 | * Hoare quickselect with median-of-three pivots: expected O(n), no | ||
| 494 | * recursion, no external randomness. | ||
| 495 | */ | ||
| 496 | static void | ||
| 497 | 3248 | quickselect_by_distance(VsTopKEntry *results, uint32_t n, uint32_t want) | |
| 498 | { | ||
| 499 | 3248 | uint32_t lo = 0, hi = n; | |
| 500 | |||
| 501 |
6/6✓ Branch 0 taken 22432 times.
✓ Branch 1 taken 1676 times.
✓ Branch 2 taken 22350 times.
✓ Branch 3 taken 82 times.
✓ Branch 4 taken 20470 times.
✓ Branch 5 taken 1490 times.
|
24108 | while (hi - lo > 1 && want > lo && want < hi) |
| 502 | { | ||
| 503 | 20860 | uint32_t mid = lo + (hi - lo) / 2; | |
| 504 | 20860 | Distance a = results[lo].distance; | |
| 505 | 20860 | Distance b = results[mid].distance; | |
| 506 | 20860 | Distance c = results[hi - 1].distance; | |
| 507 | 390 | Distance pivot; | |
| 508 |
8/8✓ Branch 0 taken 10687 times.
✓ Branch 1 taken 10173 times.
✓ Branch 2 taken 6438 times.
✓ Branch 3 taken 4249 times.
✓ Branch 4 taken 10371 times.
✓ Branch 5 taken 5925 times.
✓ Branch 6 taken 4151 times.
✓ Branch 7 taken 6220 times.
|
20860 | if ((a <= b && b <= c) || (c <= b && b <= a)) |
| 509 | 8325 | pivot = b; | |
| 510 |
8/8✓ Branch 0 taken 6097 times.
✓ Branch 1 taken 6264 times.
✓ Branch 2 taken 3069 times.
✓ Branch 3 taken 3028 times.
✓ Branch 4 taken 6226 times.
✓ Branch 5 taken 3024 times.
✓ Branch 6 taken 3196 times.
✓ Branch 7 taken 3030 times.
|
12361 | else if ((b <= a && a <= c) || (c <= a && a <= b)) |
| 511 | 6091 | pivot = a; | |
| 512 | else | ||
| 513 | 6444 | pivot = c; | |
| 514 | |||
| 515 | /* The median-of-three pivot exists in the range, so each scan | ||
| 516 | * has a stopper; the explicit bounds checks make that local | ||
| 517 | * rather than an invariant to trust (j is unsigned, so an | ||
| 518 | * unchecked descent past lo would wrap). */ | ||
| 519 | 20860 | uint32_t i = lo, j = hi - 1; | |
| 520 |
2/2✓ Branch 0 taken 222060 times.
✓ Branch 1 taken 20860 times.
|
263780 | while (i <= j) |
| 521 | { | ||
| 522 |
4/4✓ Branch 0 taken 525655 times.
✓ Branch 1 taken 1014 times.
✓ Branch 2 taken 304609 times.
✓ Branch 3 taken 221046 times.
|
526669 | while (i < hi - 1 && results[i].distance < pivot) |
| 523 | 304609 | i++; | |
| 524 |
4/4✓ Branch 0 taken 526883 times.
✓ Branch 1 taken 534 times.
✓ Branch 2 taken 305357 times.
✓ Branch 3 taken 221526 times.
|
527417 | while (j > lo && results[j].distance > pivot) |
| 525 | 305357 | j--; | |
| 526 |
2/2✓ Branch 0 taken 19997 times.
✓ Branch 1 taken 202063 times.
|
222060 | if (i <= j) |
| 527 | { | ||
| 528 | 208112 | VsTopKEntry tmp = results[i]; | |
| 529 | 208112 | results[i] = results[j]; | |
| 530 | 208112 | results[j] = tmp; | |
| 531 | 208112 | i++; | |
| 532 |
2/2✓ Branch 0 taken 6311 times.
✓ Branch 1 taken 201801 times.
|
208112 | if (j == 0) |
| 533 | ✗ | break; | |
| 534 | 208112 | j--; | |
| 535 | } | ||
| 536 | } | ||
| 537 | /* Entries [lo, j] <= pivot <= entries [i, hi). Recurse into the | ||
| 538 | * side containing the selection boundary. */ | ||
| 539 |
2/2✓ Branch 0 taken 10911 times.
✓ Branch 1 taken 9949 times.
|
20860 | if (want <= j + 1) |
| 540 | 10732 | hi = j + 1; | |
| 541 |
1/2✓ Branch 0 taken 9917 times.
✗ Branch 1 not taken.
|
9917 | else if (want >= i) |
| 542 | 9738 | lo = i; | |
| 543 | else | ||
| 544 | ✗ | return; /* boundary falls in the pivot-equal middle band */ | |
| 545 | } | ||
| 546 | } | ||
| 547 | |||
| 548 | /* ---------------------------------------------------------------- | ||
| 549 | * Extract sorted | ||
| 550 | * ---------------------------------------------------------------- */ | ||
| 551 | |||
| 552 | /* The uncapped form of vs_topk_extract_sorted_capped. */ | ||
| 553 | void | ||
| 554 | 426 | vs_topk_extract_sorted(VsTopK *topk, VsTopKEntry *results, uint32_t *count_out) | |
| 555 | { | ||
| 556 | 426 | vs_topk_extract_sorted_capped(topk, results, count_out, 0); | |
| 557 | 426 | } | |
| 558 | |||
| 559 | /* | ||
| 560 | * Extract the threshold survivors sorted by distance ascending and | ||
| 561 | * deduplicated (first, i.e. best-distance, entry per id), keeping at | ||
| 562 | * most the best `cap` unique candidates; cap == 0 keeps them all. The | ||
| 563 | * survivor count is unbounded when distance estimates are noisy -- a | ||
| 564 | * loose threshold admits most scanned entries, every SOAR replica | ||
| 565 | * included -- so sorting all survivors is wasted work when only a | ||
| 566 | * small prefix is kept. A quickselect partition narrows to the | ||
| 567 | * smallest 3*cap entries first: every id occurs at most twice (primary | ||
| 568 | * posting plus at most one SOAR replica), so the smallest 2*cap | ||
| 569 | * entries already contain the best cap unique ids and 3*cap leaves | ||
| 570 | * margin. | ||
| 571 | */ | ||
| 572 | void | ||
| 573 | 9440 | vs_topk_extract_sorted_capped( | |
| 574 | VsTopK *topk, VsTopKEntry *results, uint32_t *count_out, uint32_t cap) | ||
| 575 | { | ||
| 576 |
2/2✓ Branch 0 taken 351 times.
✓ Branch 1 taken 17 times.
|
9440 | Distance threshold = vs_topk_threshold(topk); |
| 577 | |||
| 578 | 9440 | uint32_t out = 0; | |
| 579 |
2/2✓ Branch 0 taken 803613 times.
✓ Branch 1 taken 9440 times.
|
813053 | for (uint32_t i = 0; i < topk->cand_count; i++) |
| 580 | { | ||
| 581 | 803613 | Distance lb = topk->candidates[i].distance - topk->candidates[i].error; | |
| 582 |
2/2✓ Branch 0 taken 525675 times.
✓ Branch 1 taken 277938 times.
|
803613 | if (lb <= threshold) |
| 583 | 525675 | results[out++] = topk->candidates[i]; | |
| 584 | } | ||
| 585 | |||
| 586 | 9440 | uint32_t sel = out; | |
| 587 |
4/4✓ Branch 0 taken 9011 times.
✓ Branch 1 taken 429 times.
✓ Branch 2 taken 3248 times.
✓ Branch 3 taken 5763 times.
|
9440 | if (cap > 0 && out > cap * 3) |
| 588 | { | ||
| 589 | 3248 | sel = cap * 3; | |
| 590 | 3248 | quickselect_by_distance(results, out, sel); | |
| 591 | } | ||
| 592 | |||
| 593 |
2/2✓ Branch 0 taken 5553 times.
✓ Branch 1 taken 3887 times.
|
9440 | if (sel > 1) |
| 594 | 5553 | qsort(results, sel, sizeof(VsTopKEntry), cmp_by_distance); | |
| 595 | |||
| 596 | 9440 | *count_out = dedup_sorted_prefix(results, sel, cap); | |
| 597 | 9440 | } | |
| 598 | |||
| 599 | /* | ||
| 600 | * Same as vs_topk_extract_sorted but skips the duplicate-id pass. | ||
| 601 | * For callers whose ids are unique by construction (array indices, | ||
| 602 | * beam-search buffer positions), the dedup scan can never remove | ||
| 603 | * anything and is quadratic in the survivor count. | ||
| 604 | */ | ||
| 605 | void | ||
| 606 | 929752 | vs_topk_extract_sorted_unique( | |
| 607 | VsTopK *topk, VsTopKEntry *results, uint32_t *count_out) | ||
| 608 | { | ||
| 609 |
2/2✓ Branch 0 taken 584821 times.
✓ Branch 1 taken 122057 times.
|
929752 | Distance threshold = vs_topk_threshold(topk); |
| 610 | |||
| 611 | /* Filter stale candidates and copy survivors to results */ | ||
| 612 | 929752 | uint32_t out = 0; | |
| 613 |
2/2✓ Branch 0 taken 27937874 times.
✓ Branch 1 taken 929752 times.
|
28867626 | for (uint32_t i = 0; i < topk->cand_count; i++) |
| 614 | { | ||
| 615 | 27937874 | Distance lb = topk->candidates[i].distance - topk->candidates[i].error; | |
| 616 |
2/2✓ Branch 0 taken 15740375 times.
✓ Branch 1 taken 12197499 times.
|
27937874 | if (lb <= threshold) |
| 617 | 15740375 | results[out++] = topk->candidates[i]; | |
| 618 | } | ||
| 619 | |||
| 620 | /* Sort by distance ascending */ | ||
| 621 |
2/2✓ Branch 0 taken 602341 times.
✓ Branch 1 taken 327411 times.
|
929752 | if (out > 1) |
| 622 | 602341 | qsort(results, out, sizeof(VsTopKEntry), cmp_by_distance); | |
| 623 | |||
| 624 | 929752 | *count_out = out; | |
| 625 | 929752 | } | |
| 626 |