Page MenuHome
Differential D16518

BLI_timeit: tabulate benchmark
AbandonedPublic
Actions

Authored by Iliya Katueshenock (Moder) on Nov 15 2022, 8:16 PM.

Details

Reviewers
Hans Goudey (HooglyBoogly)
Jacques Lucke (JacquesLucke)
Summary

In the process of optimizing DistJoinSet for better use of the cpu cache, I
became interested in knowing more precisely the measurements to be sure that this is not an error.

This tabular test allows you to record the running time in large numbers for various operations in a form convenient for tabular presentation.

Example

P3327 (An Untitled Masterwork)
1diff --git a/source/blender/nodes/geometry/nodes/node_geo_input_mesh_island.cc b/source/blender/nodes/geometry/nodes/node_geo_input_mesh_island.cc
2index d658b14092a..a99d0ac5ef9 100644
3--- a/source/blender/nodes/geometry/nodes/node_geo_input_mesh_island.cc
4+++ b/source/blender/nodes/geometry/nodes/node_geo_input_mesh_island.cc
5@@ -5,6 +5,7 @@
6
7 #include "BKE_mesh.h"
8
9+#include "BLI_timeit.hh"
10 #include "BLI_disjoint_set.hh"
11
12 #include "node_geometry_util.hh"
13@@ -36,15 +37,22 @@ class IslandFieldInput final : public bke::MeshFieldInput {
14 const Span<MEdge> edges = mesh.edges();
15
16 DisjointSet<int> islands(mesh.totvert);
17- for (const int i : edges.index_range()) {
18- islands.join(edges[i].v1, edges[i].v2);
19+ SCOPED_TIMER_TABLE(islands_bench);
20+ {
21+ islands_bench_add("joins");
22+ for (const int i : edges.index_range()) {
23+ islands.join(edges[i].v1, edges[i].v2);
24+ }
25 }
26
27 Array<int> output(mesh.totvert);
28 VectorSet<int> ordered_roots;
29- for (const int i : IndexRange(mesh.totvert)) {
30- const int root = islands.find_root(i);
31- output[i] = ordered_roots.index_of_or_add(root);
32+ {
33+ islands_bench_add("finding");
34+ for (const int i : IndexRange(mesh.totvert)) {
35+ const int root = islands.find_root(i);
36+ output[i] = ordered_roots.index_of_or_add(root);
37+ }
38 }
39
40 return mesh.attributes().adapt_domain<int>(
41@@ -80,16 +88,22 @@ class IslandCountFieldInput final : public bke::MeshFieldInput {
42 const IndexMask /*mask*/) const final
43 {
44 const Span<MEdge> edges = mesh.edges();
45-
46 DisjointSet<int> islands(mesh.totvert);
47- for (const int i : edges.index_range()) {
48- islands.join(edges[i].v1, edges[i].v2);
49+ SCOPED_TIMER_TABLE(islands_bench_counting);
50+ {
51+ islands_bench_counting_add("joins");
52+ for (const int i : edges.index_range()) {
53+ islands.join(edges[i].v1, edges[i].v2);
54+ }
55 }
56
57 Set<int> island_list;
58- for (const int i_vert : IndexRange(mesh.totvert)) {
59- const int root = islands.find_root(i_vert);
60- island_list.add(root);
61+ {
62+ islands_bench_counting_add("counting");
63+ for (const int i_vert : IndexRange(mesh.totvert)) {
64+ const int root = islands.find_root(i_vert);
65+ island_list.add(root);
66+ }
67 }
68
69 return VArray<int>::ForSingle(island_list.size(), mesh.attributes().domain_size(domain));

Benchmark with a large number of repetitions in an arbitrary test scene

Table View
Example recording for 180 repetitions (no changes in progress)

A more illustrative example
Comparison of two versions of the same algorithm, so the result is very obvious.

Diff Detail

Event Timeline

Iliya Katueshenock (Moder) requested review of this revision.Nov 15 2022, 8:16 PM
Iliya Katueshenock (Moder) created this revision.
Iliya Katueshenock (Moder) edited the summary of this revision. (Show Details)Nov 15 2022, 8:33 PM
Iliya Katueshenock (Moder) edited the summary of this revision. (Show Details)
Iliya Katueshenock (Moder) edited the summary of this revision. (Show Details)Nov 16 2022, 2:03 AM
Iliya Katueshenock (Moder) set the repository for this revision to rB Blender.
Iliya Katueshenock (Moder) updated this revision to Diff 57821.Nov 19 2022, 3:20 PM
Iliya Katueshenock (Moder) edited the summary of this revision. (Show Details)
Iliya Katueshenock (Moder) added reviewers: Hans Goudey (HooglyBoogly), Jacques Lucke (JacquesLucke).
Iliya Katueshenock (Moder) edited the summary of this revision. (Show Details)
Iliya Katueshenock (Moder) edited the summary of this revision. (Show Details)Nov 19 2022, 3:24 PM
Iliya Katueshenock (Moder) edited the summary of this revision. (Show Details)Nov 19 2022, 3:27 PM
Iliya Katueshenock (Moder) updated this revision to Diff 57822.Nov 19 2022, 3:32 PM
  • Formatting
Iliya Katueshenock (Moder) updated this revision to Diff 57854.Nov 20 2022, 7:03 PM
  • Simplification
Iliya Katueshenock (Moder) updated this revision to Diff 57855.Nov 20 2022, 7:04 PM
Iliya Katueshenock (Moder) planned changes to this revision.Nov 21 2022, 9:32 PM
Iliya Katueshenock (Moder) updated this revision to Diff 58030.Nov 25 2022, 7:57 PM
  • Small fixes
Hans Goudey (HooglyBoogly) added a comment.Dec 8 2022, 7:16 PM

Maybe I'm missing something, but I don't really see the purpose of visualizing the runtime of every single iteration.
I would think that the exact time of each run isn't important, but it's more important to gather statistics like the average, min, variance, etc.
Do you have a specific use case?

Iliya Katueshenock (Moder) added a comment.EditedDec 8 2022, 7:24 PM

I decided that it's easier to deal with statistics from Google spreadsheets /
From specific examples, here is a table. If not for this, it would be difficult to understand that my attempts to speed up disjoins were failed due to inaccuracies.
And here everything is visually visible https://docs.google.com/spreadsheets/d/1qRpfJjJcHRwABeP-AMTLGhZOXwLgxjWce8cBJ2Z9wnw/edit#gid=0 (Lots of visuals at the bottom part)
Although it may be possible to achieve this with the old methods
Just more control...

Iliya Katueshenock (Moder) abandoned this revision.Dec 14 2022, 7:22 PM

Revision Contents
Changeset List

PathSize
source/
blender/
blenlib/
86 lines

Diff 57667

View Options

source/blender/blenlib/BLI_timeit.hh

Loading...