Benchmark Aleph-w binary search trees (timed insert/remove + height/IPL across powers of 2). More...

#include <gsl/gsl_rng.h>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <array>
#include <chrono>
#include <iostream>
#include <limits>
#include <tuple>
#include <vector>
#include <tpl_binNodeUtils.H>
#include <tpl_sort_utils.H>
#include <tpl_binTree.H>
#include <tpl_avl.H>
#include <tpl_treap.H>
#include <tpl_treapRk.H>
#include <tpl_avlRk.H>
#include <tpl_splay_tree.H>
#include <tpl_splay_treeRk.H>
#include <tpl_rb_tree.H>
#include <tpl_rbRk.H>
#include <tpl_tdRbTree.H>
#include <tpl_tdRbTreeRk.H>
#include <tpl_rand_tree.H>
#include <tpl_dynMapTree.H>
#include <argp.h>

Include dependency graph for timeAllTree.C:

Classes
struct	Cmp_Sample< Key >

struct	TreeBenchmark

struct	Parameters

Typedefs
typedef tuple< double, double, double, double, double >	Stat

typedef tuple< int, double >	Sample

Enumerations
enum class	TreeType { BIN , AVL , AVL_RK , SPLAY , SPLAY_RK , TREAP , TREAP_RK , RB , RB_RK , TD_RB , TD_RB_RK , RAND }

enum	OptionKey { OPT_ALL = 'l' , OPT_AVL_RK = 1000 , OPT_SPLAY_RK , OPT_TREAP_RK , OPT_RB_RK , OPT_TD_RB , OPT_TD_RB_RK }

Functions
template<class Node >
static void	printNode (Node *node, int, int)

bool	is_two_power (const unsigned int x)

template<template< typename, class > class TreeType, typename Key , class Compare = Aleph::less<Key>>
tuple< Stat, Stat, int, int >	sample_tree (TreeType< Key, Compare > &tree, gsl_rng *r, int n, int k)

template<template< typename, class > class TreeType>
void	test (unsigned long n, gsl_rng *r)

template<template< typename, class > class Tree>
void	run_tree (unsigned long n, gsl_rng *r)

static const TreeBenchmark *	find_benchmark (TreeType type)

static error_t	parser_opt (int key, char , struct argp_state state)

int	main (int argc, char *argv[])

Variables
constexpr int	Num_Samples = 37

static const std::array< TreeBenchmark, 12 >	kBenchmarks

const char *	argp_program_version = "timeAllTree 0.0"

const char *	argp_program_bug_address = "lrleon@lavabit.com"

static char	doc [] = "timeAllTree -- Benchmark Aleph tree implementations"

static char	argDoc [] = "-n num_nodes -m seed_for_random [tree options]\n"

static struct argp_option	options []

static struct argp	argDefs = {options, parser_opt, argDoc, doc, 0, 0, 0}

Detailed Description

Benchmark Aleph-w binary search trees (timed insert/remove + height/IPL across powers of 2).

Overview

This program benchmarks several Aleph-w binary search tree implementations by growing a tree up to n inserted keys and sampling performance at sizes 2^k.

At each sampled size it reports:

Structural metrics: height and internal path length (IPL).
Timing statistics for insertion and deletion: min / average / median / standard deviation / max.

The benchmark is meant for comparative evaluation across tree types, not as a micro-benchmarking framework.

Data model

Keys are random integers generated by GSL (gsl_rng_mt19937).
Each benchmarked tree is instantiated as Tree<int, Aleph::less<int>>.

Supported tree types (selection flags)

You can benchmark individual implementations by selecting them with CLI flags:

--bin / -b: unbalanced BST (BinTree)
--avl / -a: AVL (Avl_Tree)
--avlrk: AVL ranked (Avl_Tree_Rk)
--redblack / -r: RB (Rb_Tree)
--redblackrk: RB ranked (Rb_Tree_Rk)
--tdrb: top-down RB (TdRbTree)
--tdrbrk: top-down RB ranked (TdRbTreeRk)
--splay / -s: splay (Splay_Tree)
--splayrk: splay ranked (Splay_Tree_Rk)
--treap / -p: treap (Treap)
--treaprk: treap ranked (Treap_Rk)
--rand / -d: randomized tree (Rand_Tree)

Or you can benchmark all of them with --all / -l.

Usage / CLI

# Benchmark all trees for n=10000 with seed=42
./timeAllTree --all -n 10000 -m 42
 
# Benchmark only a subset
./timeAllTree -n 50000 -m 123 --avl --redblack
./timeAllTree -n 20000 -m 456 --splay --treap
 
# Ranked variants are long-only flags
./timeAllTree -n 20000 -m 456 --avlrk --redblackrk --treaprk

Options:

--nodes / -n <num_nodes>: number of inserted nodes (default 1000).
--seed / -m <seed_for_random>: RNG seed (default time(0)).

If no tree types are selected (and --all is not provided), the program aborts.

Methodology

The tree is built by inserting random distinct keys up to n.
At each sampled size 2^k, it measures:
- Height and IPL.
- For 37 random keys not currently in the tree:
  - perform 100 insert/remove pairs for the same key and average the time.
  - collect the 37 averaged times and compute min/avg/median/sigma/max.

Output

For each selected tree, it prints markers:

timeAllTree<...> n seed (start/end)

and a table with columns:

2^k, n, h (height), ipc (IPL)
insertion stats: [min ins med sigma max]
removal stats: [min ins med sigma max]

Complexity

Running time is dominated by repeated insert/remove operations and depends on the selected tree type. Expected per-operation costs are typically:

balanced trees: O(log n)
unbalanced BST: O(n) worst case

Total benchmark cost is roughly proportional to:

number of sampled sizes (≈ log2(n))
number of samples (37) × measures per sample (100)

Pitfalls and edge cases

This is a synthetic benchmark (random keys) and may not represent your workload (e.g. ordered inserts, locality).
Uses GSL; you must link with it to run (e.g. -lgsl -lgslcblas).
Times are printed in raw chrono tick units as used in the program.

References / see also

dynset_trees.C (practical container usage)
tpl_avl.H, tpl_rb_tree.H, tpl_splay_tree.H, tpl_treap.H

Author: Leandro Rabindranath León

Definition in file timeAllTree.C.

Typedef Documentation

◆ Sample

typedef tuple<int, double> Sample

Definition at line 197 of file timeAllTree.C.

◆ Stat

typedef tuple<double, double, double, double, double> Stat

Definition at line 195 of file timeAllTree.C.

Enumeration Type Documentation

◆ OptionKey

enum OptionKey

Enumerator
OPT_ALL
OPT_AVL_RK
OPT_SPLAY_RK
OPT_TREAP_RK
OPT_RB_RK
OPT_TD_RB
OPT_TD_RB_RK

Definition at line 444 of file timeAllTree.C.

◆ TreeType

enum class TreeType

strong

Enumerator
BIN
AVL
AVL_RK
SPLAY
SPLAY_RK
TREAP
TREAP_RK
RB
RB_RK
TD_RB
TD_RB_RK
RAND

Definition at line 366 of file timeAllTree.C.

Function Documentation

◆ find_benchmark()

static const TreeBenchmark * find_benchmark ( TreeType type )

static

Definition at line 413 of file timeAllTree.C.

References kBenchmarks, and Aleph::maps().

Referenced by main().

◆ is_two_power()

bool is_two_power ( const unsigned int x )

inline

Definition at line 190 of file timeAllTree.C.

References Aleph::maps().

Referenced by test().

◆ main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 557 of file timeAllTree.C.

References AH_ERROR, argDefs, BIN, Aleph::DynList< T >::empty(), StlAlephIterator< SetName >::end(), find_benchmark(), kBenchmarks, Aleph::maps(), Parameters::n, Parameters::run_all, Parameters::seed, and Parameters::selected.

◆ parser_opt()

static error_t parser_opt	(	int	key,
		char *	,
		struct argp_state *	state
	)

static

Definition at line 480 of file timeAllTree.C.

References AVL, AVL_RK, BIN, Aleph::maps(), OPT_ALL, OPT_AVL_RK, OPT_RB_RK, OPT_SPLAY_RK, OPT_TD_RB, OPT_TD_RB_RK, OPT_TREAP_RK, RAND, RB, RB_RK, SPLAY, SPLAY_RK, TD_RB, TD_RB_RK, TREAP, and TREAP_RK.

◆ printNode()

template<class Node >

static void printNode	(	Node *	node,
		int	,
		int
	)

static

Definition at line 182 of file timeAllTree.C.

References Aleph::maps().

◆ run_tree()

template<template< typename, class > class Tree>

void run_tree	(	unsigned long	n,
		gsl_rng *	r
	)

Definition at line 383 of file timeAllTree.C.

References Aleph::maps().

◆ sample_tree()

template<template< typename, class > class TreeType, typename Key , class Compare = Aleph::less<Key>>

tuple< Stat, Stat, int, int > sample_tree	(	TreeType< Key, Compare > &	tree,
		gsl_rng *	r,
		int	n,
		int	k
	)

Definition at line 211 of file timeAllTree.C.

References Aleph::computeHeightRec(), Aleph::count(), Aleph::internal_path_length(), KEY, Aleph::maps(), Num_Samples, sqrt(), and Aleph::Tree.

Referenced by test().

◆ test()

template<template< typename, class > class TreeType>

void test	(	unsigned long	n,
		gsl_rng *	r
	)

Definition at line 318 of file timeAllTree.C.

References Aleph::destroyRec(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::insert(), is_two_power(), log(), Aleph::maps(), N, pow(), sample_tree(), Aleph::Gen_Rand_Tree< NodeType, Key, Compare >::search(), and Aleph::Tree.

Variable Documentation

◆ argDefs

struct argp argDefs = {options, parser_opt, argDoc, doc, 0, 0, 0}

static

Definition at line 555 of file timeAllTree.C.

Referenced by main().

◆ argDoc

char argDoc[] = "-n num_nodes -m seed_for_random [tree options]\n"

static

Definition at line 442 of file timeAllTree.C.

◆ argp_program_bug_address

const char* argp_program_bug_address = "lrleon@lavabit.com"

Definition at line 439 of file timeAllTree.C.

◆ argp_program_version

const char* argp_program_version = "timeAllTree 0.0"

Definition at line 438 of file timeAllTree.C.

◆ doc

char doc[] = "timeAllTree -- Benchmark Aleph tree implementations"

static

Definition at line 441 of file timeAllTree.C.

◆ kBenchmarks

const std::array<TreeBenchmark, 12> kBenchmarks

static

Initial value:

= {
      {
        {TreeType::BIN, "BinTree", run_tree<BinTree>},
        {TreeType::AVL, "Avl_Tree", run_tree<Avl_Tree>},
        {TreeType::AVL_RK, "Avl_Tree_Rk", run_tree<Avl_Tree_Rk>},
        {TreeType::SPLAY, "Splay_Tree", run_tree<Splay_Tree>},
        {TreeType::SPLAY_RK, "Splay_Tree_Rk", run_tree<Splay_Tree_Rk>},
        {TreeType::TREAP, "Treap", run_tree<Treap>},
        {TreeType::TREAP_RK, "Treap_Rk", run_tree<Treap_Rk>},
        {TreeType::RB, "Rb_Tree", run_tree<Rb_Tree>},
        {TreeType::RB_RK, "Rb_Tree_Rk", run_tree<Rb_Tree_Rk>},
        {TreeType::TD_RB, "TdRbTree", run_tree<TdRbTree>},
        {TreeType::TD_RB_RK, "TdRbTreeRk", run_tree<TdRbTreeRk>},
        {TreeType::RAND, "Rand_Tree", run_tree<Rand_Tree>}
      }
    }

Definition at line 396 of file timeAllTree.C.

Referenced by find_benchmark(), and main().

◆ Num_Samples

constexpr int Num_Samples = 37

constexpr

Definition at line 188 of file timeAllTree.C.

Referenced by sample_tree().

◆ options

struct argp_option options[]

static

Initial value:

= {
      {"bin", 'b', 0, OPTION_ARG_OPTIONAL, "Pure binary tree", 0},
      {"avl", 'a', 0, OPTION_ARG_OPTIONAL, "AVL tree", 0},
      {"avlrk", OPT_AVL_RK, 0, OPTION_ARG_OPTIONAL, "AVL tree (rank)", 0},
      {"splay", 's', 0, OPTION_ARG_OPTIONAL, "Splay tree", 0},
      {"splayrk", OPT_SPLAY_RK, 0, OPTION_ARG_OPTIONAL, "Splay tree (rank)", 0},
      {"redblack", 'r', 0, OPTION_ARG_OPTIONAL, "Red-black tree", 0},
      {"redblackrk", OPT_RB_RK, 0, OPTION_ARG_OPTIONAL, "Red-black tree (rank)", 0},
      {"tdrb", OPT_TD_RB, 0, OPTION_ARG_OPTIONAL, "Top-down red-black tree", 0},
      {"tdrbrk", OPT_TD_RB_RK, 0, OPTION_ARG_OPTIONAL, "Top-down red-black tree (rank)", 0},
      {"rand", 'd', 0, OPTION_ARG_OPTIONAL, "Randomized tree", 0},
      {"treap", 'p', 0, OPTION_ARG_OPTIONAL, "Treap tree", 0},
      {"treaprk", OPT_TREAP_RK, 0, OPTION_ARG_OPTIONAL, "Treap tree (rank)", 0},
      {"all", OPT_ALL, 0, OPTION_ARG_OPTIONAL, "Benchmark all tree types", 0},
      {
        "nodes", 'n', "num_nodes", OPTION_ARG_OPTIONAL,
        "Specify the number of nodes to be generated", 0
      },
      {
        "seed", 'm', "seed_for_random", OPTION_ARG_OPTIONAL,
        "Specify the seed for randon number generator", 0
      },
      {0, 0, 0, 0, 0, 0}
    }

Definition at line 455 of file timeAllTree.C.

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Overview

Data model

Supported tree types (selection flags)

Usage / CLI

Methodology

Output

Complexity

Pitfalls and edge cases

References / see also

Typedef Documentation

◆ Sample

◆ Stat

Enumeration Type Documentation

◆ OptionKey

◆ TreeType

Function Documentation

◆ find_benchmark()

◆ is_two_power()

◆ main()

◆ parser_opt()

◆ printNode()

◆ run_tree()

◆ sample_tree()

◆ test()

Variable Documentation

◆ argDefs

◆ argDoc

◆ argp_program_bug_address

◆ argp_program_version

◆ doc

◆ kBenchmarks

◆ Num_Samples

◆ options