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