GCC Code Coverage Report

Directory:	src/
File:	src/algo/kmeans_internal.h
Date:	2026-09-30 11:11:31

	Exec	Total	Coverage
Lines:	3	3	100.0%
Functions:	0	0	-%
Branches:	27	60	45.0%

  
      Line
      Branch
      Exec
      Source
    
      /*
    
       * Copyright (c) 2026 Tiger Data, Inc.
    
       * Licensed under the PostgreSQL License. See LICENSE for details.
    
       *
    
       * kmeans_internal.h - Shared internal types for k-means implementations
    
       *
    
       * This header is shared between kmeans.c (Lloyd's / CBLAS), and variant
    
       * algorithm files (kmeans_hamerly.c, kmeans_elkan.c, etc.).
    
       *
    
       * Not part of the public API — do not include from outside src/algo/.
    
       */
    
      #ifndef VS_KMEANS_INTERNAL_H
    
      #define VS_KMEANS_INTERNAL_H
    
      #include <float.h>
    
      #include <stdint.h>
    
      #include "algo/kmeans.h"
    
      #include "types/vec16.h"
    
      #include "types/vec32.h"
    
      /* Block size for assignment step (matches FAISS) */
    
      #define KMEANS_BLOCK_SIZE 4096
    
      /*
    
       * Redefine VS_TARGET_CLONES locally to avoid pulling in <immintrin.h>
    
       * from simd_utils.h, which can affect codegen for the CBLAS path.
    
       */
    
      #ifndef VS_TARGET_CLONES
    
      #if !defined(VS_SIMD_NONE) && !defined(VS_COVERAGE) && \
    
      		__has_attribute(target_clones) &&              \
    
      		(defined(__x86_64__) || defined(__i386__))
    
      #define VS_TARGET_CLONES \
    
      	__attribute__((      \
    
      			target_clones("default", "arch=x86-64-v3", "arch=x86-64-v4")))
    
      #else
    
      #define VS_TARGET_CLONES
    
      #endif
    
      #endif
    
      /*
    
       * Internal state for one k-means run.
    
       *
    
       * Shared across all algorithm variants. The core fields (vectors through
    
       * total_cost) are used by every variant. Algorithm-specific state is
    
       * stored externally (e.g., HamerlyState) and passed alongside.
    
       */
    
      typedef struct KMeansState
    
      {
    
      	void *memctx; /* Arena context (VsMemCtx) — used by kmeans.c */
    
      	/* Input (not owned) */
    
      	const void	   *vectors;
    
      	const uint32_t *indices;  /* NULL = identity mapping [0..nvecs) */
    
      	VecType			vec_type; /* element type (f32, f16, f16c) */
    
      	uint32_t		nvecs;
    
      	uint32_t		nlist;
    
      	Dimension		dim;
    
      	DistanceMetric	metric;
    
      	/* Working state (owned) — always float32 */
    
      	float	  *centroids;	  /* [nlist * dim] */
    
      	float	  *vec_block;	  /* [BLOCK_SIZE * dim] BLAS convert buf */
    
      	ClusterId *assignments;	  /* [nvecs] */
    
      	uint32_t  *cluster_sizes; /* [nlist] */
    
      	float	  *norms_x;		  /* [nvecs] precomputed ||x||^2 (L2) */
    
      	float	  *norms_c;		  /* [nlist] precomputed ||c||^2 (L2) */
    
      	float	  *dist_block;	  /* [KMEANS_BLOCK_SIZE * nlist] work buf */
    
      	float	  *new_centroids; /* [nlist * dim] accumulator */
    
      	float	   total_cost;
    
      } KMeansState;
    
      /* Get pointer to vector i in the input array */
    
      __attribute__((always_inline)) static inline const void *
    
      6483461
      km_get_vector(const KMeansState *st, uint32_t i, size_t elem_size)
    
      {
    
        21/36✗ Branch 0 not taken.
✓ Branch 1 taken 1400 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8718 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 6600 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 8720 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✓ Branch 13 taken 2000 times.
✗ Branch 14 not taken.
✓ Branch 15 taken 12 times.
✗ Branch 16 not taken.
✓ Branch 17 taken 2000 times.
✗ Branch 18 not taken.
✓ Branch 19 taken 32 times.
✗ Branch 20 not taken.
✓ Branch 21 taken 5600 times.
✗ Branch 22 not taken.
✓ Branch 23 taken 13600 times.
✓ Branch 24 taken 441119 times.
✓ Branch 25 taken 337079 times.
✓ Branch 26 taken 2175 times.
✓ Branch 27 taken 475 times.
✓ Branch 28 taken 462339 times.
✓ Branch 29 taken 349239 times.
✓ Branch 30 taken 10125 times.
✓ Branch 31 taken 4002 times.
✓ Branch 32 taken 3353869 times.
✓ Branch 33 taken 4124001 times.
✗ Branch 34 not taken.
✓ Branch 35 taken 22800 times.

      9155905
      	uint32_t idx = st->indices ? st->indices[i] : i;
    
        6/24✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✓ Branch 24 taken 551656 times.
✓ Branch 25 taken 2000 times.
✓ Branch 26 taken 14020 times.
✗ Branch 27 not taken.
✓ Branch 29 taken 5134844 times.
✓ Branch 30 taken 60000 times.
✓ Branch 31 taken 158394 times.
✗ Branch 32 not taken.

      9155905
      	return (const char *)st->vectors + (size_t)idx * st->dim * elem_size;
    
      }
    
      /*
    
       * Max centroid movement between two centroid arrays.
    
       * Returns the maximum squared L2 shift.
    
       */
    
      float kmeans_max_centroid_shift_between(
    
      		const float *a, const float *b, uint32_t nlist, Dimension dim);
    
      /*
    
       * Merge per-worker centroid accumulators and update centroids.
    
       *
    
       * This is the reduce step of parallel k-means (BSP pattern).
    
       * Called by the leader between barrier-synchronized iterations.
    
       *
    
       * Inputs:
    
       *   worker_sums:  [nworkers][nlist * dim] per-worker centroid sums
    
       *   worker_cnts:  [nworkers][nlist] per-worker cluster counts
    
       *   worker_costs: [nworkers] per-worker total costs
    
       *   nworkers:     number of workers
    
       *   old_cents:    [nlist * dim] centroids from before this iteration
    
       *
    
       * Outputs:
    
       *   centroids:    [nlist * dim] updated centroid positions (in-place)
    
       *   norms_c:      [nlist] updated centroid norms (for L2, may be NULL)
    
       *
    
       * Returns the maximum squared centroid shift (for convergence check).
    
       */
    
      float kmeans_merge_centroids(
    
      		float				  *centroids,
    
      		float				  *norms_c,
    
      		const float			  *old_cents,
    
      		const float *const	  *worker_sums,
    
      		const uint32_t *const *worker_cnts,
    
      		const float			  *worker_costs,
    
      		uint32_t			   nworkers,
    
      		uint32_t			   nlist,
    
      		Dimension			   dim,
    
      		DistanceMetric		   metric,
    
      		float				  *out_total_cost);
    
      /*
    
       * Scalar assign+accumulate kernel for a range of vectors.
    
       *
    
       * For each vector in [start, end): find nearest centroid, add
    
       * to per-worker sums/counts. Supports optional root-assignment
    
       * filtering for hierarchical child k-means — when filter is
    
       * non-NULL, only vectors where filter[i] == filter_val are
    
       * processed.
    
       *
    
       * Used by both standalone (via Lloyd iterate) and PG parallel
    
       * workers (via Barrier iterate). The CBLAS path in Lloyd uses
    
       * its own batched sgemm kernel instead.
    
       */
    
      void kmeans_assign_accumulate(
    
      		const float	   *vectors,
    
      		const uint32_t *indices,
    
      		uint32_t		start,
    
      		uint32_t		end,
    
      		const float	   *centroids,
    
      		const float	   *norms_c,
    
      		uint32_t		k,
    
      		Dimension		dim,
    
      		DistanceMetric	metric,
    
      		const uint32_t *filter,
    
      		uint32_t		filter_val,
    
      		float		   *out_sums,
    
      		uint32_t	   *out_cnts,
    
      		float		   *out_cost);
    
      /*
    
       * Assignment-only kernel for a range of vectors.
    
       *
    
       * For each vector in [start, end): find nearest centroid and
    
       * write the centroid index to out_assignments[i]. Unlike
    
       * kmeans_assign_accumulate, this does not accumulate sums
    
       * or counts — it only outputs assignments.
    
       *
    
       * Used for root assignment in hierarchical k-means (both
    
       * standalone and PG paths).
    
       */
    
      void kmeans_assign(
    
      		const float	  *vectors,
    
      		uint32_t	   start,
    
      		uint32_t	   end,
    
      		const float	  *centroids,
    
      		const float	  *norms_c,
    
      		uint32_t	   k,
    
      		Dimension	   dim,
    
      		DistanceMetric metric,
    
      		uint32_t	  *out_assignments);
    
      #endif /* VS_KMEANS_INTERNAL_H */

Line	Branch	Exec	Source
1			/*
2			* Copyright (c) 2026 Tiger Data, Inc.
3			* Licensed under the PostgreSQL License. See LICENSE for details.
4			*
5			* kmeans_internal.h - Shared internal types for k-means implementations
6			*
7			* This header is shared between kmeans.c (Lloyd's / CBLAS), and variant
8			* algorithm files (kmeans_hamerly.c, kmeans_elkan.c, etc.).
9			*
10			* Not part of the public API — do not include from outside src/algo/.
11			*/
12
13			#ifndef VS_KMEANS_INTERNAL_H
14			#define VS_KMEANS_INTERNAL_H
15
16			#include <float.h>
17			#include <stdint.h>
18
19			#include "algo/kmeans.h"
20			#include "types/vec16.h"
21			#include "types/vec32.h"
22
23			/* Block size for assignment step (matches FAISS) */
24			#define KMEANS_BLOCK_SIZE 4096
25
26			/*
27			* Redefine VS_TARGET_CLONES locally to avoid pulling in <immintrin.h>
28			* from simd_utils.h, which can affect codegen for the CBLAS path.
29			*/
30			#ifndef VS_TARGET_CLONES
31			#if !defined(VS_SIMD_NONE) && !defined(VS_COVERAGE) && \
32			__has_attribute(target_clones) && \
33			(defined(__x86_64__) \|\| defined(__i386__))
34			#define VS_TARGET_CLONES \
35			__attribute__(( \
36			target_clones("default", "arch=x86-64-v3", "arch=x86-64-v4")))
37			#else
38			#define VS_TARGET_CLONES
39			#endif
40			#endif
41
42			/*
43			* Internal state for one k-means run.
44			*
45			* Shared across all algorithm variants. The core fields (vectors through
46			* total_cost) are used by every variant. Algorithm-specific state is
47			* stored externally (e.g., HamerlyState) and passed alongside.
48			*/
49			typedef struct KMeansState
50			{
51			void memctx; / Arena context (VsMemCtx) — used by kmeans.c */
52
53			/* Input (not owned) */
54			const void *vectors;
55			const uint32_t indices; / NULL = identity mapping [0..nvecs) */
56			VecType vec_type; /* element type (f32, f16, f16c) */
57			uint32_t nvecs;
58			uint32_t nlist;
59			Dimension dim;
60			DistanceMetric metric;
61
62			/* Working state (owned) — always float32 */
63			float centroids; / [nlist * dim] */
64			float vec_block; / [BLOCK_SIZE * dim] BLAS convert buf */
65			ClusterId assignments; / [nvecs] */
66			uint32_t cluster_sizes; / [nlist] */
67			float norms_x; / [nvecs] precomputed \|\|x\|\|^2 (L2) */
68			float norms_c; / [nlist] precomputed \|\|c\|\|^2 (L2) */
69			float dist_block; / [KMEANS_BLOCK_SIZE * nlist] work buf */
70			float new_centroids; / [nlist * dim] accumulator */
71			float total_cost;
72			} KMeansState;
73
74			/* Get pointer to vector i in the input array */
75			__attribute__((always_inline)) static inline const void *
76		6483461	km_get_vector(const KMeansState *st, uint32_t i, size_t elem_size)
77			{
78	21/36 ✗ Branch 0 not taken. ✓ Branch 1 taken 1400 times. ✗ Branch 2 not taken. ✓ Branch 3 taken 8718 times. ✗ Branch 4 not taken. ✓ Branch 5 taken 6600 times. ✗ Branch 6 not taken. ✓ Branch 7 taken 8720 times. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 11 not taken. ✗ Branch 12 not taken. ✓ Branch 13 taken 2000 times. ✗ Branch 14 not taken. ✓ Branch 15 taken 12 times. ✗ Branch 16 not taken. ✓ Branch 17 taken 2000 times. ✗ Branch 18 not taken. ✓ Branch 19 taken 32 times. ✗ Branch 20 not taken. ✓ Branch 21 taken 5600 times. ✗ Branch 22 not taken. ✓ Branch 23 taken 13600 times. ✓ Branch 24 taken 441119 times. ✓ Branch 25 taken 337079 times. ✓ Branch 26 taken 2175 times. ✓ Branch 27 taken 475 times. ✓ Branch 28 taken 462339 times. ✓ Branch 29 taken 349239 times. ✓ Branch 30 taken 10125 times. ✓ Branch 31 taken 4002 times. ✓ Branch 32 taken 3353869 times. ✓ Branch 33 taken 4124001 times. ✗ Branch 34 not taken. ✓ Branch 35 taken 22800 times.	9155905	uint32_t idx = st->indices ? st->indices[i] : i;
79	6/24 ✗ Branch 2 not taken. ✗ Branch 3 not taken. ✗ Branch 4 not taken. ✗ Branch 5 not taken. ✗ Branch 7 not taken. ✗ Branch 8 not taken. ✗ Branch 9 not taken. ✗ Branch 10 not taken. ✗ Branch 13 not taken. ✗ Branch 14 not taken. ✗ Branch 15 not taken. ✗ Branch 16 not taken. ✗ Branch 18 not taken. ✗ Branch 19 not taken. ✗ Branch 20 not taken. ✗ Branch 21 not taken. ✓ Branch 24 taken 551656 times. ✓ Branch 25 taken 2000 times. ✓ Branch 26 taken 14020 times. ✗ Branch 27 not taken. ✓ Branch 29 taken 5134844 times. ✓ Branch 30 taken 60000 times. ✓ Branch 31 taken 158394 times. ✗ Branch 32 not taken.	9155905	return (const char )st->vectors + (size_t)idx st->dim * elem_size;
80			}
81
82			/*
83			* Max centroid movement between two centroid arrays.
84			* Returns the maximum squared L2 shift.
85			*/
86			float kmeans_max_centroid_shift_between(
87			const float a, const float b, uint32_t nlist, Dimension dim);
88
89			/*
90			* Merge per-worker centroid accumulators and update centroids.
91			*
92			* This is the reduce step of parallel k-means (BSP pattern).
93			* Called by the leader between barrier-synchronized iterations.
94			*
95			* Inputs:
96			* worker_sums: [nworkers][nlist * dim] per-worker centroid sums
97			* worker_cnts: [nworkers][nlist] per-worker cluster counts
98			* worker_costs: [nworkers] per-worker total costs
99			* nworkers: number of workers
100			* old_cents: [nlist * dim] centroids from before this iteration
101			*
102			* Outputs:
103			* centroids: [nlist * dim] updated centroid positions (in-place)
104			* norms_c: [nlist] updated centroid norms (for L2, may be NULL)
105			*
106			* Returns the maximum squared centroid shift (for convergence check).
107			*/
108			float kmeans_merge_centroids(
109			float *centroids,
110			float *norms_c,
111			const float *old_cents,
112			const float const worker_sums,
113			const uint32_t const worker_cnts,
114			const float *worker_costs,
115			uint32_t nworkers,
116			uint32_t nlist,
117			Dimension dim,
118			DistanceMetric metric,
119			float *out_total_cost);
120
121			/*
122			* Scalar assign+accumulate kernel for a range of vectors.
123			*
124			* For each vector in [start, end): find nearest centroid, add
125			* to per-worker sums/counts. Supports optional root-assignment
126			* filtering for hierarchical child k-means — when filter is
127			* non-NULL, only vectors where filter[i] == filter_val are
128			* processed.
129			*
130			* Used by both standalone (via Lloyd iterate) and PG parallel
131			* workers (via Barrier iterate). The CBLAS path in Lloyd uses
132			* its own batched sgemm kernel instead.
133			*/
134			void kmeans_assign_accumulate(
135			const float *vectors,
136			const uint32_t *indices,
137			uint32_t start,
138			uint32_t end,
139			const float *centroids,
140			const float *norms_c,
141			uint32_t k,
142			Dimension dim,
143			DistanceMetric metric,
144			const uint32_t *filter,
145			uint32_t filter_val,
146			float *out_sums,
147			uint32_t *out_cnts,
148			float *out_cost);
149
150			/*
151			* Assignment-only kernel for a range of vectors.
152			*
153			* For each vector in [start, end): find nearest centroid and
154			* write the centroid index to out_assignments[i]. Unlike
155			* kmeans_assign_accumulate, this does not accumulate sums
156			* or counts — it only outputs assignments.
157			*
158			* Used for root assignment in hierarchical k-means (both
159			* standalone and PG paths).
160			*/
161			void kmeans_assign(
162			const float *vectors,
163			uint32_t start,
164			uint32_t end,
165			const float *centroids,
166			const float *norms_c,
167			uint32_t k,
168			Dimension dim,
169			DistanceMetric metric,
170			uint32_t *out_assignments);
171
172			#endif /* VS_KMEANS_INTERNAL_H */
173