Nearest Neighbor

Random values

Write a function producing a std::vector of random float values.

TIP

Boilerplate for random number generation

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<float> rnd0_10(0.f, 10.f);

Find nearest neighbor

Given another random value, find the closest neighbor in the random vector and return its index in the vector.

Vectorize

Copy the code (or generalize via template) and work with stdx::native_simd<float> instead.

1. Use simd(address, stdx::element_aligned) to load from an array of float
2. Use std::vector<native_simd<float>>

Which one is better, if at all? When?

Benchmark

Benchmark the three variants, over different sizes of the vector

TIP

One benchmark function, benchmarking different vector sizes

void name(benchmark::State& state) {
  const std::size_t n = state.range(0);
  std::vector<float> values(n);
  // ...
}

BENCHMARK(name)->Range(8, 8 << 20);

3-D

Go from 1-dim to three dimensional.

1. AoS
2. SoA
3. AoVS
4. kd-tree (kidding nothing for today, at least)

… and benchmark

Further Reading

Data-Structure Vectorization