11#include "testing/testing.h"
26static const std::array<int64_t, 4>
POINT_COUNTS = {1000, 10000, 100000, 1000000};
80 const int64_t side = std::max<int64_t>(std::ceil(std::cbrt(
double(points_num))), 1);
89 positions[i] = corner + jitter;
102 constexpr int hotspots_num = 16;
112 positions[i] = hotspots[
random.get_int32(hotspots_num)];
150 return impl ==
Impl::BLI ?
"BLI_kdtree" :
"New";
161 const int64_t stride = positions.
size() / queries_num;
166 queries[i] = positions[i * stride] + (offset - 0.5f) * 0.01f;
187 const int iterations = int(std::clamp<int64_t>(2000000 / points_num, 3, 1000));
188 double min_time = 1e30;
189 for (
int repetition = 0; repetition < iterations; repetition++) {
193 min_time = std::min(min_time, time_after - time_before);
207 const int64_t batch_size = std::max<int64_t>(20000 / points_num, 1);
208 double min_time = 1e30;
209 for (
int repetition = 0; repetition < 20; repetition++) {
215 min_time = std::min(min_time, (time_after - time_before) /
double(batch_size));
232 constexpr int64_t batch_size = 256;
233 constexpr double time_budget = 0.25;
234 constexpr int64_t min_queries = 2000;
236 double total_time = 0.0;
238 while (total_time < time_budget || queries_num < min_queries) {
239 const int64_t start = queries_num % queries.
size();
240 const int64_t size = std::min(batch_size, queries.
size() - start);
242 for (
const float3 &query : queries.
slice(start, size)) {
248 return total_time / double(queries_num);
253 if (seconds < 0.000001) {
254 printf(
" %8.1f ns |", seconds * 1000000000.0);
256 else if (seconds < 0.001) {
257 printf(
" %8.2f µs |", seconds * 1000000.0);
260 printf(
" %8.2f ms |", seconds * 1000.0);
265 const char *value_description,
268 printf(
"\n#### %s\n\n(%s)\n\n| distribution | implementation |", title, value_description);
269 for (
const int64_t points_num : point_counts) {
273 for ([[maybe_unused]]
const int64_t points_num : point_counts) {
287 const char *value_description,
298 for (
const Impl impl : implementations) {
300 for (
const int64_t points_num : point_counts) {
301 const Array<float3> positions = distribution.make_points(points_num);
302 print_time(run_cell(impl, positions, points_num));
319 "`kdtree_insert` and `kdtree_balance` vs. the `KDTreeNew` constructor",
331TEST(kdtree_performance, FindNearest)
357TEST(kdtree_performance, FindNearestSkipSelf)
359 run_table(
"Find the nearest point, skipping the search point itself",
360 "time per query, this is what the Index of Nearest node does",
372 const auto query_index = [&](
const float3 &query) {
373 return int(&query - queries.
data());
378 const int i = query_index(query);
383 [i](
const int other,
const float3 & ,
const float ) {
384 return other == i ? 0 : 1;
392 const int i = query_index(query);
394 query, [i](
const int other) {
return other != i; });
402TEST(kdtree_performance, FindNearestN)
430TEST(kdtree_performance, RangeSearch)
432 run_table(
"Visit every point in a radius",
433 "time per query, radius scaled for ~8 points in range",
446 [&](
const int ,
const float3 & ,
const float ) {
457 query, radius, [&](
const int ,
const float ) {
467TEST(kdtree_performance, CalcDuplicates)
470 "time for the whole tree, radius scaled for ~8 points in range, this is what the "
471 "Cluster by Distance node does",
499TEST(kdtree_performance, ThreadedBuild)
501 static const int thread_counts[] = {1, 2, 4, 8, 16, 32};
502 static const int64_t point_counts[] = {1000, 10000, 100000, 1000000};
505 "\n#### Threaded build\n\n(`KDTreeNew` build time by thread count, random. The\n"
506 "tree limits its own thread count by size as well, so the larger counts give the same\n"
507 "time once that limit is the lower of the two.)\n\n");
509 for (
const int threads_num : thread_counts) {
510 printf(
" %d threads |", threads_num);
512 printf(
" speedup |\n|---:|");
513 for ([[maybe_unused]]
const int threads_num : thread_counts) {
519 for (
const int64_t points_num : point_counts) {
522 double single_thread_time = 0.0;
523 double best_time = 1e30;
524 for (
const int threads_num : thread_counts) {
530 const std::clock_t cpu_before = std::clock();
532 const std::clock_t cpu_after = std::clock();
533 cpu_times.
append(
double(cpu_after - cpu_before) /
double(CLOCKS_PER_SEC));
535 if (threads_num == 1) {
536 single_thread_time = time;
538 best_time = std::min(best_time, time);
544 printf(
" %.1fx |\n", single_thread_time / best_time);
547 printf(
"\n(processor time of the same builds, relative to the single threaded build)\n\n");
549 for (
const int threads_num : thread_counts) {
550 printf(
" %d threads |", threads_num);
553 for ([[maybe_unused]]
const int threads_num : thread_counts) {
558 for (
const int64_t points_num : point_counts) {
560 const double base = cpu_times[cpu_time_i];
561 for ([[maybe_unused]]
const int threads_num : thread_counts) {
562 printf(
" %.1fx |", cpu_times[cpu_time_i++] / base);
581TEST(kdtree_performance, TinyTreesBuild)
584 "Building a tiny tree",
585 "time to build and free one tree",
611TEST(kdtree_performance, TinyTreesFindNearestOther)
614 "Building a tiny tree and finding the nearest other point for every point",
615 "time for the whole group, this is what the Index of Nearest node does per group",
627 [i](
const int other,
const float3 & ,
const float ) {
628 return other == int(i) ? 0 : 1;
642 [i](
const int other) {
return other != int(i); });
652TEST(kdtree_performance, TinyTreesCalcDuplicates)
655 "Building a tiny tree and merging its points by distance",
656 "time for the whole group, this is what the Cluster by Distance node does per group",
687TEST(kdtree_performance, KDTreeNewLeafSize)
691 static const int leaf_sizes[] = {4, 8, 10, 16, 32, 64, 128};
692 static const int64_t point_counts[] = {10000, 1000000};
694 for (
const int64_t points_num : point_counts) {
695 printf(
"\n#### KDTreeNew leaf size\n\n(%" PRId64 " points)\n\n", points_num);
696 printf(
"| distribution | leaf size | build | find nearest | 8 nearest | radius |\n");
697 printf(
"|---:|---:|---:|---:|---:|---:|\n");
701 const Array<float3> positions = distribution.make_points(points_num);
703 for (
const int leaf_size : leaf_sizes) {
704 printf(
"| %s | %d |", distribution.name, leaf_size);
711 run_queries(queries, [&](
const float3 &query) { sum += tree.find_nearest(query); }));
715 queries, [&](
const float3 &query) { sum += tree.find_nearest_n(query, nearest); }));
718 tree.foreach_in_radius(
719 query, radius, [&](
const int ,
const float ) { sum++; });
A KD-tree for nearest neighbor search.
Platform independent time functions.
SIMD_FORCE_INLINE const btScalar & z() const
Return the z value.
MutableSpan< T > as_mutable_span()
IndexRange index_range() const
constexpr IndexRange()=default
void foreach_in_radius(const T &position, const value_type radius, Fn &&fn) const
int find_nearest(const T &position, value_type *r_distance_sq=nullptr) const
int find_nearest_filtered(const T &position, Filter &&filter, value_type *r_distance_sq=nullptr) const
int find_nearest_n(const T &position, MutableSpan< Nearest > r_nearest) const
void provide_buffer(void *buffer, const int64_t size)
constexpr Span slice(int64_t start, int64_t size) const
constexpr const T * data() const
constexpr int64_t size() const
constexpr IndexRange index_range() const
constexpr Span take_front(int64_t n) const
void append(const T &value)
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
#define EXPECT_GT(result, expect)
int calc_duplicates(const KDTreeNew< T > &tree, typename T::base_type range, Span< int > visit_order, MutableSpan< int > duplicates)
static constexpr int64_t QUERY_COUNT
void kdtree_balance(KDTree< CoordT > *tree)
static Array< float3 > make_random_points(const int64_t points_num)
static double run_queries(const Span< float3 > queries, const FunctionRef< void(const float3 &query)> query_fn)
static Array< float3 > make_duplicate_points(const int64_t points_num)
static double run_batched(const int64_t points_num, const FunctionRef< void()> function)
int kdtree_find_nearest_cb(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest, Filter &&filter_cb)
void kdtree_range_search_cb(const KDTree< CoordT > *tree, const CoordT &co, typename KDTree< CoordT >::ValueType range, Fn &&search_cb)
void BLI_system_num_threads_override_set(int num)
void BLI_task_scheduler_exit()
static const std::array< int64_t, 5 > TINY_POINT_COUNTS
static double run_iterations(const int64_t indices_num, const FunctionRef< void()> function)
Array< float3 >(*)(int64_t) MakePointsFn
static constexpr double NEIGHBORS_IN_RANGE
static const Distribution DISTRIBUTIONS[]
KDTree< CoordT > * kdtree_new(uint nodes_len_capacity)
FunctionRef< double(Impl impl, const Span< float3 > positions, int64_t points_num)> RunCellFn
static void run_table(const char *title, const char *value_description, const RunCellFn run_cell, const Span< int64_t > point_counts=POINT_COUNTS, const Span< Impl > implementations=IMPLEMENTATIONS)
int kdtree_find_nearest_n(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > r_nearest[], uint nearest_len_capacity)
static const char * impl_name(const Impl impl)
void kdtree_insert(KDTree< CoordT > *tree, int index, const CoordT &co)
static const std::array< int64_t, 4 > POINT_COUNTS
int kdtree_find_nearest(const KDTree< CoordT > *tree, const CoordT &co, KDTreeNearest< CoordT > *r_nearest)
static void print_time(const double seconds)
void kdtree_free(KDTree< CoordT > *tree)
static constexpr int NEAREST_N
static Array< float3 > make_contiguous_points(const int64_t points_num)
static KDTree< float3 > * build_bli_tree(const Span< float3 > positions)
int kdtree_calc_duplicates_fast(const KDTree< CoordT > *tree, const typename KDTree< CoordT >::ValueType range, const bool use_index_order, int *duplicates)
static Array< float3 > make_query_points(const Span< float3 > positions)
double BLI_time_now_seconds()
void BLI_task_scheduler_init(bool use_flush_denormals_to_zero=true)
static void print_table_header(const char *title)
static float radius_for_neighbor_count(const int64_t points_num)
VecBase< float, 3 > float3
static const std::array< Impl, 2 > IMPLEMENTATIONS
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float