Benchmarks for multiple behavior tree implementations in C++17
A Behavior Tree is an hierarchical abstraction utilized in robotics and AI (See the Wikipedia
page
for more information).
This repository aims to benchmark three behavior tree implementations:
std::unique_ptr
to derived classesstd::function
-basedstd::tuple
-basedThe first two use heap allocations, the second one can be entirely allocated on the stack.
All tree implementations followed similar design:
()
was utilized for the tick and the operator returns bt::Status
std::vector
for storageThe benchmark utilized a simple tree:
- Fallback
- Conditional: returns a random boolean
- Sequence
- Action: always returns Success
- Action: increments a counter and returns Success
A “default implementation” was also provided, where the behavior tree is reduced toif(!random_boolean()) count++;
, in order to compare the overhead of each implementation.
The bench.cpp file contains the benchmark code and can be compiled with Google
Benchmark, using the provided CMake file.
-----------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------
oop_style 9.05 ns 8.79 ns 74666667
functions 13.4 ns 13.5 ns 49777778
tuples 1.44 ns 1.41 ns 497777778
default_implementation 1.41 ns 1.41 ns 497777778
-----------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------
oop_style 13.1 ns 12.8 ns 56000000
functions 11.6 ns 11.5 ns 64000000
tuples 1.64 ns 1.61 ns 407272727
default_implementation 1.60 ns 1.60 ns 448000000
-----------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------
oop_style 12.7 ns 12.2 ns 49777778
functions 13.1 ns 13.1 ns 56000000
tuples 1.71 ns 1.69 ns 407272727
default_implementation 1.70 ns 1.69 ns 407272727
-----------------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------------
oop_style 15.3 ns 15.0 ns 44800000
functions 14.2 ns 14.2 ns 56000000
tuples 3.38 ns 3.30 ns 213333333
default_implementation 3.47 ns 3.38 ns 203636364
std::function
were really interesting. Faster thanlibstdc++
‘s implementation, even though the vtable performance from the inheritance test wasThe code in this repository is public domain, released under The Unlicense.
Feel free to use any standalone Behavior Tree implementation in your applications or as a base for
your own implementations!