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