/root/doris/contrib/faiss/faiss/utils/partitioning.h
Line | Count | Source |
1 | | /* |
2 | | * Copyright (c) Meta Platforms, Inc. and affiliates. |
3 | | * |
4 | | * This source code is licensed under the MIT license found in the |
5 | | * LICENSE file in the root directory of this source tree. |
6 | | */ |
7 | | |
8 | | #pragma once |
9 | | |
10 | | #include <stdint.h> |
11 | | #include <stdio.h> |
12 | | |
13 | | #include <faiss/impl/platform_macros.h> |
14 | | |
15 | | namespace faiss { |
16 | | |
17 | | /** partitions the table into 0:q and q:n where all elements above q are >= all |
18 | | * elements below q (for C = CMax, for CMin comparisons are reversed) |
19 | | * |
20 | | * Returns the partition threshold. The elements q:n are destroyed on output. |
21 | | */ |
22 | | template <class C> |
23 | | typename C::T partition_fuzzy( |
24 | | typename C::T* vals, |
25 | | typename C::TI* ids, |
26 | | size_t n, |
27 | | size_t q_min, |
28 | | size_t q_max, |
29 | | size_t* q_out); |
30 | | |
31 | | /** simplified interface for when the parition is not fuzzy */ |
32 | | template <class C> |
33 | | inline typename C::T partition( |
34 | | typename C::T* vals, |
35 | | typename C::TI* ids, |
36 | | size_t n, |
37 | 0 | size_t q) { |
38 | 0 | return partition_fuzzy<C>(vals, ids, n, q, q, nullptr); |
39 | 0 | } Unexecuted instantiation: _ZN5faiss9partitionINS_4CMaxItiEEEENT_1TEPS4_PNS3_2TIEmm Unexecuted instantiation: _ZN5faiss9partitionINS_4CMinItiEEEENT_1TEPS4_PNS3_2TIEmm Unexecuted instantiation: _ZN5faiss9partitionINS_4CMaxItlEEEENT_1TEPS4_PNS3_2TIEmm Unexecuted instantiation: _ZN5faiss9partitionINS_4CMinItlEEEENT_1TEPS4_PNS3_2TIEmm |
40 | | |
41 | | /** low level SIMD histogramming functions */ |
42 | | |
43 | | /** 8-bin histogram of (x - min) >> shift |
44 | | * values outside the range are ignored. |
45 | | * the data table should be aligned on 32 bytes */ |
46 | | void simd_histogram_8( |
47 | | const uint16_t* data, |
48 | | int n, |
49 | | uint16_t min, |
50 | | int shift, |
51 | | int* hist); |
52 | | |
53 | | /** same for 16-bin histogram */ |
54 | | void simd_histogram_16( |
55 | | const uint16_t* data, |
56 | | int n, |
57 | | uint16_t min, |
58 | | int shift, |
59 | | int* hist); |
60 | | |
61 | | struct PartitionStats { |
62 | | uint64_t bissect_cycles; |
63 | | uint64_t compress_cycles; |
64 | | |
65 | 1 | PartitionStats() { |
66 | 1 | reset(); |
67 | 1 | } |
68 | | void reset(); |
69 | | }; |
70 | | |
71 | | // global var that collects them all |
72 | | FAISS_API extern PartitionStats partition_stats; |
73 | | |
74 | | } // namespace faiss |