tarantool / tarantool / 8142632044

88%

push

github

perf: add a BPS tree benchmark

The benchmark tests the tree build, key search, insert and delete
operations performance. The latter are tested both including and
excluding the tree reballancing overhead.

A very simple allocator had been introduced to mitigate the memory
management overhead and noise.

The benchmark functions are templated. This allows to test multiple
tree configurations using the same benchmarking routines.

The simplest tree configuration is used, though it's possible to add
new configurations to the benchmark. Example on how to create a tree
similar to the one used by the memtx index is shown in the appendix A.

Closes #9630

NO_DOC=new benchmark
NO_TEST=new benchmark
NO_CHANGELOG=new benchmark

APPENDIX A: Adding a new tree configuration to the benchmark.

```C
/* Instantiate the tree. */

#define tree_s128_EXTENT_SIZE 16 * 1024
#define tree_s128_elem_t struct tree_s128_elem
#define tree_s128_key_t struct tree_s128_key

struct tree_s128_elem {
	void *tuple; /* Unused. */
	int64_t hint;

	tree_s128_elem() = default;
	tree_s128_elem(int64_t hint) : hint(hint) {}
};

struct tree_s128_key {
	void *key; /* Unused. */
	uint32_t part_count; /* Unused. */
	int64_t hint;

	tree_s128_key(int64_t hint) : hint(hint) {}
};

#define BPS_TREE_NAME tree_s128_t
#define BPS_TREE_BLOCK_SIZE 512
#define BPS_TREE_EXTENT_SIZE tree_s128_EXTENT_SIZE
#define BPS_TREE_IS_IDENTICAL(a, b) ((a).hint == (b).hint)
#define BPS_TREE_COMPARE(a, b, arg) ((a).hint - (b).hint)
#define BPS_TREE_COMPARE_KEY(a, b, arg) ((a).hint - (b).hint)
#define bps_tree_elem_t tree_s128_elem_t
#define bps_tree_key_t tree_s128_key_t
#define bps_tree_arg_t int
#include "salad/bps_tree.h"
#undef BPS_TREE_NAME
#undef BPS_TREE_BLOCK_SIZE
#undef BPS_TREE_EXTENT_SIZE
#undef BPS_TREE_IS_IDENTICAL
#undef BPS_TREE_COMPARE
#undef BPS_TREE_COMPARE_KEY
#undef bps_tree_elem_t
#undef bps_tree_key_t
#undef bps_tree_arg_t

/** Add the new tree to the `generate_benchmarks` macro. */

#define genera... (continued)

66946 of 119342 branches covered (56.1%)

99418 of 114351 relevant lines covered (86.94%)

2670012.72 hits per line