tenant.openagents/omega

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    let mut group = c.benchmark_group("append many");
243    group.throughput(Throughput::Bytes(128 * 100_000));
244
245    group.bench_function("small to large", |b| {
246        b.iter(|| {
247            let mut rope = Rope::new();
248            let small = Rope::from("A".repeat(128));
249            for _ in 0..100_000 {
250                rope.append(small.clone());
251            }
252            assert_eq!(rope.len(), 128 * 100_000);
253        });
254    });
255
256    group.bench_function("large to small", |b| {
257        b.iter(|| {
258            let mut rope = Rope::new();
259            let small = Rope::from("A".repeat(128));
260            for _ in 0..100_000 {
261                let large = rope;
262                rope = small.clone();
263                rope.append(large);
264            }
265            assert_eq!(rope.len(), 128 * 100_000);
266        });
267    });
268
269    group.finish();
270}
271
272criterion_group!(benches, rope_benchmarks);
273criterion_main!(benches);
274