Blender V5.3
BLI_group_indices.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include <algorithm>
6#include <cinttypes>
7#include <cmath>
8
9#include "testing/testing.h"
10
11#include "BLI_array.hh"
12#include "BLI_array_utils.hh"
13#include "BLI_function_ref.hh"
14#include "BLI_offset_indices.hh"
15#include "BLI_rand.hh"
16#include "BLI_task_c.hh"
17#include "BLI_time.hh"
18
19namespace blender {
20
21static const int64_t GROUP_COUNTS[] = {8, 64, 512, 4096, 32768, 262144, 1048576, 4194304};
22static const int64_t INDEX_COUNTS[] = {100000, 1000000, 10000000};
23
24static Array<int> make_random_indices(const int64_t groups_num, const int64_t indices_num)
25{
27 Array<int> indices(indices_num);
28 for (const int64_t i : indices.index_range()) {
29 indices[i] = random.get_int32(int32_t(groups_num));
30 }
31 return indices;
32}
33
34static Array<int> make_clustered_indices(const int64_t groups_num, const int64_t indices_num)
35{
36 /* Approximately sorted with a small amount of jittering, more similar to real
37 * topology than fully random indices. */
39 Array<int> indices(indices_num);
40 const int64_t jitter = std::max<int64_t>(sqrt(groups_num), 1);
41 for (const int64_t i : indices.index_range()) {
42 const int64_t center = i * groups_num / indices_num;
43 const int64_t value = center + random.get_int32(int32_t(2 * jitter)) - jitter;
44 indices[i] = int(std::clamp(value, int64_t(0), groups_num - 1));
45 }
46 return indices;
47}
48
49static double run_iterations(const int64_t indices_num, const FunctionRef<void()> function)
50{
51 const int iterations = (indices_num >= 10000000) ? 4 : 8;
52 double min_time = 1e30;
53 for (int repetition = 0; repetition < iterations; repetition++) {
54 const double time_before = BLI_time_now_seconds();
55 function();
56 const double time_after = BLI_time_now_seconds();
57 min_time = std::min(min_time, time_after - time_before);
58 }
59 return min_time;
60}
61
62static void print_time(const double seconds)
63{
64 if (seconds < 0.001) {
65 printf(" %8.1f µs |", seconds * 1000000.0);
66 }
67 else {
68 printf(" %8.2f ms |", seconds * 1000.0);
69 }
70}
71
72static void print_table_header(const char *title)
73{
74 printf("\n#### %s\n\n| groups |", title);
75 for (const int64_t indices_num : INDEX_COUNTS) {
76 printf(" %" PRId64 " indices |", indices_num);
77 }
78 printf("\n|---:|");
79 for ([[maybe_unused]] const int64_t indices_num : INDEX_COUNTS) {
80 printf("---:|");
81 }
82 printf("\n");
83}
84
86
87static void run_count_table(const char *title, const MakeIndicesFn make_indices)
88{
89 print_table_header(title);
90 for (const int64_t groups_num : GROUP_COUNTS) {
91 printf("| %" PRId64 " |", groups_num);
92 for (const int64_t indices_num : INDEX_COUNTS) {
93 const Array<int> indices = make_indices(groups_num, indices_num);
94 Array<int> counts(groups_num, 0);
95 print_time(run_iterations(indices_num, [&]() {
96 counts.as_mutable_span().fill(0);
97 array_utils::count_indices(indices, counts);
98 }));
99 fflush(stdout);
100 }
101 printf("\n");
102 }
103}
104
105static void run_build_groups_table(const char *title, const MakeIndicesFn make_indices)
106{
107 print_table_header(title);
108 for (const int64_t groups_num : GROUP_COUNTS) {
109 printf("| %" PRId64 " |", groups_num);
110 for (const int64_t indices_num : INDEX_COUNTS) {
111 const Array<int> indices = make_indices(groups_num, indices_num);
112 Array<int> offset_data;
113 Array<int> index_data;
114 print_time(run_iterations(indices_num, [&]() {
116 indices, int(groups_num), offset_data, index_data);
117 }));
118 fflush(stdout);
119 }
120 printf("\n");
121 }
122}
123
124TEST(group_indices_performance, CountIndices)
125{
127 run_count_table("`array_utils::count_indices`, random", make_random_indices);
128 run_count_table("`array_utils::count_indices`, clustered", make_clustered_indices);
129}
130
131TEST(group_indices_performance, BuildGroupsFromIndices)
132{
134 run_build_groups_table("`offset_indices::build_groups_from_indices`, random",
136 run_build_groups_table("`offset_indices::build_groups_from_indices`, clustered",
138}
139
140} // namespace blender
Platform independent time functions.
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
IndexRange index_range() const
Definition BLI_array.hh:371
#define PRId64
Definition inttypes.h:78
void count_indices(Span< int > indices, MutableSpan< int > counts)
GroupedSpan< int > build_groups_from_indices(Span< int > indices, int groups_num, Array< int > &offset_data, Array< int > &index_data)
BMesh Iterators.
__int64 int64_t
Definition BKE_text.h:90
static Array< int > make_random_indices(const int64_t groups_num, const int64_t indices_num)
static void run_count_table(const char *title, const MakeIndicesFn make_indices)
static double run_iterations(const int64_t indices_num, const FunctionRef< void()> function)
static const int64_t GROUP_COUNTS[]
TEST(array_store, Nop)
static void run_build_groups_table(const char *title, const MakeIndicesFn make_indices)
sqrt(x)+1/max(0
static void print_time(const double seconds)
static const int64_t INDEX_COUNTS[]
signed int int32_t
Definition BKE_text.h:78
double BLI_time_now_seconds()
Definition time.cc:30
void BLI_task_scheduler_init(bool use_flush_denormals_to_zero=true)
static void print_table_header(const char *title)
static Array< int > make_clustered_indices(const int64_t groups_num, const int64_t indices_num)
Array< int >(*)(int64_t, int64_t) MakeIndicesFn