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