Debian Codegraph @

perf_tests/bench_hnsw.py

raw
1 # Copyright (c) Meta Platforms, Inc. and affiliates.
2 #
3 # This source code is licensed under the MIT license found in the
4 # LICENSE file in the root directory of this source tree.
5
6 import argparse
7 import resource
8 import time
9 from contextlib import contextmanager
10 from dataclasses import dataclass
11 from typing import Dict, Generator, List, Optional
12
13 import faiss # @manual=//faiss/python:pyfaiss
14 import numpy as np
15 from faiss.contrib.datasets import ( # @manual=//faiss/contrib:faiss_contrib
16 Dataset,
17 SyntheticDataset,
18 )
19
20 US_IN_S = 1_000_000
21
22
23 @dataclass
24 class PerfCounters:
25 wall_time_s: float = 0.0
26 user_time_s: float = 0.0
27 system_time_s: float = 0.0
28
29
30 @contextmanager
31 def timed_execution() -> Generator[PerfCounters, None, None]:
32 pcounters = PerfCounters()
33 wall_time_start = time.perf_counter()
34 rusage_start = resource.getrusage(resource.RUSAGE_SELF)
35 yield pcounters
36 wall_time_end = time.perf_counter()
37 rusage_end = resource.getrusage(resource.RUSAGE_SELF)
38 pcounters.wall_time_s = wall_time_end - wall_time_start
39 pcounters.user_time_s = rusage_end.ru_utime - rusage_start.ru_utime
40 pcounters.system_time_s = rusage_end.ru_stime - rusage_start.ru_stime
41
42
43 def is_perf_counter(key: str) -> bool:
44 return key.endswith("_time_us")
45
46
47 def accumulate_perf_counter(
48 phase: str,
49 t: PerfCounters,
50 counters: Dict[str, int]
51 ):
52 counters[f"{phase}_wall_time_us"] = int(t.wall_time_s * US_IN_S)
53 counters[f"{phase}_user_time_us"] = int(t.user_time_s * US_IN_S)
54
55
56 def run_on_dataset(
57 ds: Dataset,
58 M: int,
59 num_threads: int,
60 num_add_iterations: int,
61 num_search_iterations: int,
62 efSearch: int = 16,
63 efConstruction: int = 40,
64 search_bounded_queue: bool = True,
65 ) -> Dict[str, int]:
66 xq = ds.get_queries()
67 xb = ds.get_database()
68
69 nb, d = xb.shape
70 nq, d = xq.shape
71
72 k = 10
73 # pyre-ignore[16]: Module `faiss` has no attribute `omp_set_num_threads`.
74 faiss.omp_set_num_threads(num_threads)
75 index = faiss.IndexHNSWFlat(d, M)
76 index.hnsw.efConstruction = efConstruction # default
77 with timed_execution() as t:
78 for _ in range(num_add_iterations):
79 index.add(xb)
80 counters = {}
81 accumulate_perf_counter("add", t, counters)
82 counters["nb"] = nb
83 counters["num_add_iterations"] = num_add_iterations
84
85 index.hnsw.efSearch = efSearch
86 index.hnsw.search_bounded_queue = search_bounded_queue
87 with timed_execution() as t:
88 for _ in range(num_search_iterations):
89 D, I = index.search(xq, k)
90 accumulate_perf_counter("search", t, counters)
91 counters["nq"] = nq
92 counters["efSearch"] = efSearch
93 counters["efConstruction"] = efConstruction
94 counters["M"] = M
95 counters["d"] = d
96 counters["num_search_iterations"] = num_search_iterations
97
98 return counters
99
100
101 def run(
102 d: int,
103 nb: int,
104 nq: int,
105 M: int,
106 num_threads: int,
107 num_add_iterations: int = 1,
108 num_search_iterations: int = 1,
109 efSearch: int = 16,
110 efConstruction: int = 40,
111 search_bounded_queue: bool = True,
112 ) -> Dict[str, int]:
113 ds = SyntheticDataset(d=d, nb=nb, nt=0, nq=nq, metric="L2", seed=1338)
114 return run_on_dataset(
115 ds,
116 M=M,
117 num_add_iterations=num_add_iterations,
118 num_search_iterations=num_search_iterations,
119 num_threads=num_threads,
120 efSearch=efSearch,
121 efConstruction=efConstruction,
122 search_bounded_queue=search_bounded_queue,
123 )
124
125
126 def _accumulate_counters(
127 element: Dict[str, int], accu: Optional[Dict[str, List[int]]] = None
128 ) -> Dict[str, List[int]]:
129 if accu is None:
130 accu = {key: [value] for key, value in element.items()}
131 return accu
132 else:
133 assert accu.keys() <= element.keys(), (
134 "Accu keys must be a subset of element keys: "
135 f"{accu.keys()} not a subset of {element.keys()}"
136 )
137 for key in accu.keys():
138 accu[key].append(element[key])
139 return accu
140
141
142 def main():
143 parser = argparse.ArgumentParser(description="Benchmark HNSW")
144 parser.add_argument("--M", type=int, default=32)
145 parser.add_argument("--num-threads", type=int, default=5)
146 parser.add_argument("--warm-up-iterations", type=int, default=0)
147 parser.add_argument("--num-search-iterations", type=int, default=1)
148 parser.add_argument("--num-add-iterations", type=int, default=1)
149 parser.add_argument("--num-repetitions", type=int, default=1)
150 parser.add_argument("--ef-search", type=int, default=16)
151 parser.add_argument("--ef-construction", type=int, default=40)
152 parser.add_argument("--search-bounded-queue", action="store_true")
153
154 parser.add_argument("--nb", type=int, default=5000)
155 parser.add_argument("--nq", type=int, default=500)
156 parser.add_argument("--d", type=int, default=128)
157 args = parser.parse_args()
158
159 if args.warm_up_iterations > 0:
160 print(f"Warming up for {args.warm_up_iterations} iterations...")
161 # warm-up
162 run(
163 num_search_iterations=args.warm_up_iterations,
164 num_add_iterations=args.warm_up_iterations,
165 d=args.d,
166 nb=args.nb,
167 nq=args.nq,
168 M=args.M,
169 num_threads=args.num_threads,
170 efSearch=args.ef_search,
171 efConstruction=args.ef_construction,
172 search_bounded_queue=args.search_bounded_queue,
173 )
174 print(
175 f"Running benchmark with dataset(nb={args.nb}, nq={args.nq}, "
176 f"d={args.d}), M={args.M}, num_threads={args.num_threads}, "
177 f"efSearch={args.ef_search}, efConstruction={args.ef_construction}"
178 )
179 result = None
180 for _ in range(args.num_repetitions):
181 counters = run(
182 num_search_iterations=args.num_search_iterations,
183 num_add_iterations=args.num_add_iterations,
184 d=args.d,
185 nb=args.nb,
186 nq=args.nq,
187 M=args.M,
188 num_threads=args.num_threads,
189 efSearch=args.ef_search,
190 efConstruction=args.ef_construction,
191 search_bounded_queue=args.search_bounded_queue,
192 )
193 result = _accumulate_counters(counters, result)
194 assert result is not None
195 for counter, values in result.items():
196 if is_perf_counter(counter):
197 print(
198 "%s t=%.3f us (± %.4f)" %
199 (counter, np.mean(values), np.std(values))
200 )
201
202
203 if __name__ == "__main__":
204 main()