| 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() |