1use std::ops::Range;
2
3use criterion::{
4 BatchSize, BenchmarkId, Criterion, Throughput, black_box, criterion_group, criterion_main,
5};
6use rand::prelude::*;
7use rand::rngs::StdRng;
8use rope::{Point, Rope};
9use sum_tree::Bias;
10use util::RandomCharIter;
11
12fn generate_random_text(mut rng: StdRng, text_len: usize) -> String {
13 RandomCharIter::new(&mut rng).take(text_len).collect()
14}
15
16fn generate_random_rope(rng: StdRng, text_len: usize) -> Rope {
17 let text = generate_random_text(rng, text_len);
18 let mut rope = Rope::new();
19 rope.push(&text);
20 rope
21}
22
23fn generate_random_rope_ranges(mut rng: StdRng, rope: &Rope) -> Vec<Range<usize>> {
24 let range_max_len = 50;
25 let num_ranges = rope.len() / range_max_len;
26
27 let mut ranges = Vec::new();
28 let mut start = 0;
29 for _ in 0..num_ranges {
30 let range_start = rope.clip_offset(
31 rng.random_range(start..=(start + range_max_len)),
32 sum_tree::Bias::Left,
33 );
34 let range_end = rope.clip_offset(
35 rng.random_range(range_start..(range_start + range_max_len)),
36 sum_tree::Bias::Right,
37 );
38
39 let range = range_start..range_end;
40 if !range.is_empty() {
41 ranges.push(range);
42 }
43
44 start = range_end + 1;
45 }
46
47 ranges
48}
49
50fn generate_random_rope_points(mut rng: StdRng, rope: &Rope) -> Vec<Point> {
51 let num_points = rope.len() / 10;
52
53 let mut points = Vec::new();
54 for _ in 0..num_points {
55 points.push(rope.offset_to_point(rng.random_range(0..rope.len())));
56 }
57 points
58}
59
60fn rope_benchmarks(c: &mut Criterion) {
61 static SEED: u64 = 9999;
62 static KB: usize = 1024;
63
64 let rng = StdRng::seed_from_u64(SEED);
65 let sizes = [4 * KB, 64 * KB];
66
67 let mut group = c.benchmark_group("push");
68 for size in sizes.iter() {
69 group.throughput(Throughput::Bytes(*size as u64));
70 group.bench_with_input(BenchmarkId::from_parameter(size), &size, |b, &size| {
71 let text = generate_random_text(rng.clone(), *size);
72
73 b.iter(|| {
74 let mut rope = Rope::new();
75 for _ in 0..10 {
76 rope.push(&text);
77 }
78 });
79 });
80 }
81 group.finish();
82
83 let mut group = c.benchmark_group("append");
84 for size in sizes.iter() {
85 group.throughput(Throughput::Bytes(*size as u64));
86 group.bench_with_input(BenchmarkId::from_parameter(size), &size, |b, &size| {
87 let mut random_ropes = Vec::new();
88 for _ in 0..5 {
89 random_ropes.push(generate_random_rope(rng.clone(), *size));
90 }
91
92 b.iter(|| {
93 let mut rope_b = Rope::new();
94 for rope in &random_ropes {
95 rope_b.append(rope.clone())
96 }
97 });
98 });
99 }
100 group.finish();
101
102 let mut group = c.benchmark_group("slice");
103 for size in sizes.iter() {
104 group.throughput(Throughput::Bytes(*size as u64));
105 group.bench_with_input(BenchmarkId::from_parameter(size), &size, |b, &size| {
106 let rope = generate_random_rope(rng.clone(), *size);
107
108 b.iter_batched(
109 || generate_random_rope_ranges(rng.clone(), &rope),
110 |ranges| {
111 for range in ranges.iter() {
112 rope.slice(range.clone());
113 }
114 },
115 BatchSize::SmallInput,
116 );
117 });
118 }
119 group.finish();
120
121 let mut group = c.benchmark_group("bytes_in_range");
122 for size in sizes.iter() {
123 group.throughput(Throughput::Bytes(*size as u64));
124 group.bench_with_input(BenchmarkId::from_parameter(size), &size, |b, &size| {
125 let rope = generate_random_rope(rng.clone(), *size);
126
127 b.iter_batched(
128 || generate_random_rope_ranges(rng.clone(), &rope),
129 |ranges| {
130 for range in ranges.iter() {
131 let bytes = rope.bytes_in_range(range.clone());
132 assert!(bytes.into_iter().count() > 0);
133 }
134 },
135 BatchSize::SmallInput,
136 );
137 });
138 }
139 group.finish();
140
141 let mut group = c.benchmark_group("chars");
142 for size in sizes.iter() {
143 group.throughput(Throughput::Bytes(*size as u64));
144 group.bench_with_input(BenchmarkId::from_parameter(size), &size, |b, &size| {
145 let rope = generate_random_rope(rng.clone(), *size);
146
147 b.iter_with_large_drop(|| {
148 let chars = rope.chars().count();
149 assert!(chars > 0);
150 });
151 });
152 }
153 group.finish();
154
155 let mut group = c.benchmark_group("clip_point");
156 for size in sizes.iter() {
157 group.throughput(Throughput::Bytes(*size as u64));
158 group.bench_with_input(BenchmarkId::from_parameter(size), &size, |b, &size| {
159 let rope = generate_random_rope(rng.clone(), *size);
160
161 b.iter_batched(
162 || generate_random_rope_points(rng.clone(), &rope),
163 |offsets| {
164 for offset in offsets.iter() {
165 black_box(rope.clip_point(*offset, Bias::Left));
166 black_box(rope.clip_point(*offset, Bias::Right));
167 }
168 },
169 BatchSize::SmallInput,
170 );
171 });
172 }
173 group.finish();
174
175 let mut group = c.benchmark_group("point_to_offset");
176 for size in sizes.iter() {
177 group.throughput(Throughput::Bytes(*size as u64));
178 group.bench_with_input(BenchmarkId::from_parameter(size), &size, |b, &size| {
179 let rope = generate_random_rope(rng.clone(), *size);
180
181 b.iter_batched(
182 || generate_random_rope_points(rng.clone(), &rope),
183 |offsets| {
184 for offset in offsets.iter() {
185 black_box(rope.point_to_offset(*offset));
186 }
187 },
188 BatchSize::SmallInput,
189 );
190 });
191 }
192 group.finish();
193}
194
195criterion_group!(benches, rope_benchmarks);
196criterion_main!(benches);