rope_benchmark.cc File Reference

Benchmarks Aleph::Rope against std::string for the two access patterns each type is respectively built for. More...

#include <tpl_rope.H>
#include <chrono>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <random>
#include <string>
#include <string_view>

Include dependency graph for rope_benchmark.cc:

Go to the source code of this file.

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

Detailed Description

Benchmarks Aleph::Rope against std::string for the two access patterns each type is respectively built for.

What this measures

• Large concatenation: building a big sequence by repeatedly appending small chunks. std::string::operator+= is the natural baseline here – it is already amortized O(1) per append (geometric growth), so this benchmark is not "Rope wins trivially"; it exists to confirm Rope's leaf-absorption fast path (see tpl_rope.H's "Leaf absorption" note) keeps it competitive rather than falling back to its pre-fix near-O(n^2/LeafSize) behavior for this exact pattern.
• Structural editing: repeatedly inserting/erasing in the middle of a large, already-built sequence. This is where Rope is expected to win decisively: insert/erase are typically O(log n) (share whole subtrees and only touch boundary leaves in the common case), while std::string::insert/erase are O(n) (shift every following byte).

Usage

./rope_benchmark
./rope_benchmark --chunks 500000 --edits 20000

See also

tpl_rope.H for the full complexity contract.

Author

Leandro Rabindranath Leon

Definition in file rope_benchmark.cc.

Function Documentation

main()

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

Definition at line 186 of file rope_benchmark.cc.

References Aleph::and, and Aleph::blossom_maximum_cardinality_matching().