I have noticed you care about `SumTree` (and `Rope`) construction
performance, hence using rayon for parallelism and careful `Chunk`
splitting to avoid reallocation in `Rope::push`. It seemed strange to me
that using multi-threading is that beneficial there, so I tried to
investigate why the serial version (`SumTree::from_iter`) is slow in the
first place.
From my analysis I believe there are two main factors here:
1. `SumTree::from_iter` stores temporary `Node<T>` values in a vector
instead of heap-allocating them immediately and storing `SumTree<T>`
directly, as `SumTree::from_par_iter` does.
2. `Chunk::new` is quite slow: for some reason the compiler does not
vectorize it and seems to struggle to optimize u128 shifts (at least on
x86_64).
For (1) the solution is simple: allocate `Node<T>` immediately after
construction, just like `SumTree::from_par_iter`.
For (2) I was able to get better codegen by rewriting it into a simpler
per-byte loop and splitting computation into smaller chunks to avoid
slow u128 shifts.
There was a similar effort recently in #43193 using portable_simd
(currently nightly only) to optimize `Chunk::push_str`. From what I
understand from that discussion, you seem okay with hand-rolled SIMD for
specific architectures. If so, then I also provide sse2 implementation
for x86_64. Feel free to remove it if you think this is unnecessary.
To test performance I used a big CSV file (~1GB, mostly ASCII) and
measured `Rope::from` with this program:
```rust
fn main() {
let text = std::fs::read_to_string("big.csv").unwrap();
let start = std::time::Instant::now();
let rope = rope::Rope::from(text);
println!("{}ms, {}", start.elapsed().as_millis(), rope.len());
}
```
Here are results on my machine (Ryzen 7 4800H)
| | Parallel | Serial |
| ------------ | -------- | ------ |
| Before | 1123ms | 9154ms |
| After | 497ms | 2081ms |
| After (sse2) | 480ms | 1454ms |
Since serial performance is now much closer to parallel, I also
increased `PARALLEL_THRESHOLD` to 1000. In my tests the parallel version
starts to beat serial at around 150 KB strings. This constant might
require more tweaking and testing though, especially on ARM64.
<details>
<summary>cargo bench (SSE2 vs before)</summary>
```
Running benches\rope_benchmark.rs (D:\zed\target\release\deps\rope_benchmark-3f8476f7dfb79154.exe)
Gnuplot not found, using plotters backend
push/4096 time: [43.592 µs 43.658 µs 43.733 µs]
thrpt: [89.320 MiB/s 89.473 MiB/s 89.610 MiB/s]
change:
time: [-78.523% -78.222% -77.854%] (p = 0.00 < 0.05)
thrpt: [+351.56% +359.19% +365.61%]
Performance has improved.
Found 2 outliers among 100 measurements (2.00%)
1 (1.00%) high mild
1 (1.00%) high severe
push/65536 time: [632.36 µs 634.03 µs 635.76 µs]
thrpt: [98.308 MiB/s 98.576 MiB/s 98.836 MiB/s]
change:
time: [-51.521% -50.850% -50.325%] (p = 0.00 < 0.05)
thrpt: [+101.31% +103.46% +106.28%]
Performance has improved.
Found 18 outliers among 100 measurements (18.00%)
11 (11.00%) low mild
6 (6.00%) high mild
1 (1.00%) high severe
append/4096 time: [11.635 µs 11.664 µs 11.698 µs]
thrpt: [333.92 MiB/s 334.89 MiB/s 335.72 MiB/s]
change:
time: [-24.543% -23.925% -22.660%] (p = 0.00 < 0.05)
thrpt: [+29.298% +31.450% +32.525%]
Performance has improved.
Found 12 outliers among 100 measurements (12.00%)
2 (2.00%) low mild
2 (2.00%) high mild
8 (8.00%) high severe
append/65536 time: [1.1287 µs 1.1324 µs 1.1360 µs]
thrpt: [53.727 GiB/s 53.900 GiB/s 54.075 GiB/s]
change:
time: [-44.153% -37.614% -29.834%] (p = 0.00 < 0.05)
thrpt: [+42.518% +60.292% +79.061%]
Performance has improved.
slice/4096 time: [28.340 µs 28.372 µs 28.406 µs]
thrpt: [137.52 MiB/s 137.68 MiB/s 137.83 MiB/s]
change:
time: [-8.0798% -6.3955% -4.4109%] (p = 0.00 < 0.05)
thrpt: [+4.6145% +6.8325% +8.7900%]
Performance has improved.
Found 3 outliers among 100 measurements (3.00%)
1 (1.00%) low mild
1 (1.00%) high mild
1 (1.00%) high severe
slice/65536 time: [527.51 µs 528.17 µs 528.90 µs]
thrpt: [118.17 MiB/s 118.33 MiB/s 118.48 MiB/s]
change:
time: [-53.819% -45.431% -34.578%] (p = 0.00 < 0.05)
thrpt: [+52.853% +83.256% +116.54%]
Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
1 (1.00%) low severe
3 (3.00%) low mild
1 (1.00%) high mild
bytes_in_range/4096 time: [3.2545 µs 3.2646 µs 3.2797 µs]
thrpt: [1.1631 GiB/s 1.1685 GiB/s 1.1721 GiB/s]
change:
time: [-3.4829% -2.4391% -1.7166%] (p = 0.00 < 0.05)
thrpt: [+1.7466% +2.5001% +3.6085%]
Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
6 (6.00%) high mild
2 (2.00%) high severe
bytes_in_range/65536 time: [80.770 µs 80.832 µs 80.904 µs]
thrpt: [772.52 MiB/s 773.21 MiB/s 773.80 MiB/s]
change:
time: [-1.8710% -1.3843% -0.9044%] (p = 0.00 < 0.05)
thrpt: [+0.9126% +1.4037% +1.9067%]
Change within noise threshold.
Found 8 outliers among 100 measurements (8.00%)
5 (5.00%) high mild
3 (3.00%) high severe
chars/4096 time: [790.50 ns 791.10 ns 791.88 ns]
thrpt: [4.8173 GiB/s 4.8220 GiB/s 4.8257 GiB/s]
change:
time: [+0.4318% +1.4558% +2.0256%] (p = 0.00 < 0.05)
thrpt: [-1.9854% -1.4349% -0.4299%]
Change within noise threshold.
Found 6 outliers among 100 measurements (6.00%)
1 (1.00%) low severe
1 (1.00%) low mild
2 (2.00%) high mild
2 (2.00%) high severe
chars/65536 time: [12.672 µs 12.688 µs 12.703 µs]
thrpt: [4.8046 GiB/s 4.8106 GiB/s 4.8164 GiB/s]
change:
time: [-2.7794% -1.2987% -0.2020%] (p = 0.04 < 0.05)
thrpt: [+0.2025% +1.3158% +2.8588%]
Change within noise threshold.
Found 15 outliers among 100 measurements (15.00%)
1 (1.00%) low mild
12 (12.00%) high mild
2 (2.00%) high severe
clip_point/4096 time: [63.009 µs 63.126 µs 63.225 µs]
thrpt: [61.783 MiB/s 61.880 MiB/s 61.995 MiB/s]
change:
time: [+2.0484% +3.2218% +5.2181%] (p = 0.00 < 0.05)
thrpt: [-4.9593% -3.1213% -2.0073%]
Performance has regressed.
Found 13 outliers among 100 measurements (13.00%)
12 (12.00%) low mild
1 (1.00%) high severe
Benchmarking clip_point/65536: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 7.7s, enable flat sampling, or reduce sample count to 50.
clip_point/65536 time: [1.2420 ms 1.2430 ms 1.2439 ms]
thrpt: [50.246 MiB/s 50.283 MiB/s 50.322 MiB/s]
change:
time: [-0.3495% -0.0401% +0.1990%] (p = 0.80 > 0.05)
thrpt: [-0.1986% +0.0401% +0.3507%]
No change in performance detected.
Found 7 outliers among 100 measurements (7.00%)
6 (6.00%) high mild
1 (1.00%) high severe
point_to_offset/4096 time: [16.104 µs 16.119 µs 16.134 µs]
thrpt: [242.11 MiB/s 242.33 MiB/s 242.56 MiB/s]
change:
time: [-1.3816% -0.2497% +2.2181%] (p = 0.84 > 0.05)
thrpt: [-2.1699% +0.2503% +1.4009%]
No change in performance detected.
Found 6 outliers among 100 measurements (6.00%)
3 (3.00%) low mild
1 (1.00%) high mild
2 (2.00%) high severe
point_to_offset/65536 time: [356.28 µs 356.57 µs 356.86 µs]
thrpt: [175.14 MiB/s 175.28 MiB/s 175.42 MiB/s]
change:
time: [-3.7072% -2.3338% -1.4742%] (p = 0.00 < 0.05)
thrpt: [+1.4962% +2.3896% +3.8499%]
Performance has improved.
Found 1 outliers among 100 measurements (1.00%)
1 (1.00%) low mild
cursor/4096 time: [18.893 µs 18.934 µs 18.974 µs]
thrpt: [205.87 MiB/s 206.31 MiB/s 206.76 MiB/s]
change:
time: [-2.3645% -2.0729% -1.7931%] (p = 0.00 < 0.05)
thrpt: [+1.8259% +2.1168% +2.4218%]
Performance has improved.
Found 12 outliers among 100 measurements (12.00%)
12 (12.00%) high mild
cursor/65536 time: [459.97 µs 460.40 µs 461.04 µs]
thrpt: [135.56 MiB/s 135.75 MiB/s 135.88 MiB/s]
change:
time: [-5.7445% -4.2758% -3.1344%] (p = 0.00 < 0.05)
thrpt: [+3.2358% +4.4668% +6.0946%]
Performance has improved.
Found 2 outliers among 100 measurements (2.00%)
1 (1.00%) high mild
1 (1.00%) high severe
append many/small to large
time: [38.364 ms 38.620 ms 38.907 ms]
thrpt: [313.75 MiB/s 316.08 MiB/s 318.19 MiB/s]
change:
time: [-0.2042% +1.0954% +2.3334%] (p = 0.10 > 0.05)
thrpt: [-2.2802% -1.0836% +0.2046%]
No change in performance detected.
Found 21 outliers among 100 measurements (21.00%)
9 (9.00%) high mild
12 (12.00%) high severe
append many/large to small
time: [48.045 ms 48.322 ms 48.648 ms]
thrpt: [250.92 MiB/s 252.62 MiB/s 254.07 MiB/s]
change:
time: [-6.5298% -5.6919% -4.8532%] (p = 0.00 < 0.05)
thrpt: [+5.1007% +6.0354% +6.9859%]
Performance has improved.
Found 11 outliers among 100 measurements (11.00%)
2 (2.00%) high mild
9 (9.00%) high severe
```
</details>
Release Notes:
- N/A *or* Added/Fixed/Improved ...
Tracing code is not included in normal release builds
Documents how to use them in our performance docs
Only the maps and cursors are instrumented atm
# Compile times:
current main: fresh release build (cargo clean then build --release)
377.34 secs
current main: fresh debug build (cargo clean then build )
89.31 secs
tracing tracy: fresh release build (cargo clean then build --release)
374.84 secs
tracing tracy: fresh debug build (cargo clean then build )
88.95 secs
tracing tracy: fresh release build with timings (cargo clean then build
--release --features tracing)
375.77 secs
tracing tracy: fresh debug build with timings (cargo clean then build
--features tracing)
90.03 secs
Release Notes:
- N/A
---------
Co-authored-by: localcc <work@localcc.cc>
While logically not really correct, its better than tearing down the
application until we figure out the root cause here
Release Notes:
- N/A *or* Added/Fixed/Improved ...
The `SumTree::append` method is slow when appending large trees to small
trees. The reason is this code here:
f57f4cd360/crates/sum_tree/src/sum_tree.rs (L628-L630)
`append` is called recursively until `self` and `other` have the same
height, effectively making this code `O(log^2 n)` in the number of
leaves of `other` tree in the worst case.
There are no algorithmic reasons why appending large trees must be this
much slower.
This PR proves it by providing implementation of `append` that works in
logarithmic time regardless if `self` is smaller or larger than `other`.
The helper method `append_large` has the symmetric logic to
`push_tree_recursive` but moves the (unlikely) case of merging
underflowing node in a separate helper function to reduce stack usage. I
am a bit unsure about some implementation choices made in
`push_tree_recursive` and would like to discuss some of these later, but
at the moment I didn't change anything there and tried to follow the
same logic in `append_large`.
We might also consider adding `push_front`/`prepend` methods to
`SumTree`.
I did not find a good benchmark that covers this case so I added a new
one to rope benchmarks.
<details>
<summary>cargo bench (compared to current main)</summary>
```
Running benches\rope_benchmark.rs (D:\zed\target\release\deps\rope_benchmark-59c669d2895cd2c4.exe)
Gnuplot not found, using plotters backend
push/4096 time: [195.67 µs 195.75 µs 195.86 µs]
thrpt: [19.944 MiB/s 19.955 MiB/s 19.964 MiB/s]
change:
time: [+0.2162% +0.3040% +0.4057%] (p = 0.00 < 0.05)
thrpt: [-0.4040% -0.3030% -0.2157%]
Change within noise threshold.
Found 14 outliers among 100 measurements (14.00%)
2 (2.00%) low mild
6 (6.00%) high mild
6 (6.00%) high severe
Benchmarking push/65536: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 7.8s, enable flat sampling, or reduce sample count to 50.
push/65536 time: [1.4431 ms 1.4485 ms 1.4546 ms]
thrpt: [42.966 MiB/s 43.147 MiB/s 43.310 MiB/s]
change:
time: [-3.2257% -1.2013% +0.6431%] (p = 0.27 > 0.05)
thrpt: [-0.6390% +1.2159% +3.3332%]
No change in performance detected.
Found 11 outliers among 100 measurements (11.00%)
1 (1.00%) low mild
5 (5.00%) high mild
5 (5.00%) high severe
append/4096 time: [15.107 µs 15.128 µs 15.149 µs]
thrpt: [257.86 MiB/s 258.22 MiB/s 258.58 MiB/s]
change:
time: [+0.9650% +1.5256% +1.9057%] (p = 0.00 < 0.05)
thrpt: [-1.8701% -1.5026% -0.9557%]
Change within noise threshold.
Found 2 outliers among 100 measurements (2.00%)
1 (1.00%) low mild
1 (1.00%) high severe
append/65536 time: [1.2870 µs 1.4496 µs 1.6484 µs]
thrpt: [37.028 GiB/s 42.106 GiB/s 47.425 GiB/s]
change:
time: [-28.699% -16.073% -0.3133%] (p = 0.04 < 0.05)
thrpt: [+0.3142% +19.151% +40.250%]
Change within noise threshold.
Found 17 outliers among 100 measurements (17.00%)
1 (1.00%) high mild
16 (16.00%) high severe
slice/4096 time: [30.580 µs 30.611 µs 30.639 µs]
thrpt: [127.49 MiB/s 127.61 MiB/s 127.74 MiB/s]
change:
time: [-2.2958% -0.9674% -0.1835%] (p = 0.08 > 0.05)
thrpt: [+0.1838% +0.9769% +2.3498%]
No change in performance detected.
slice/65536 time: [614.86 µs 795.04 µs 1.0293 ms]
thrpt: [60.723 MiB/s 78.613 MiB/s 101.65 MiB/s]
change:
time: [-12.714% +7.2092% +30.676%] (p = 0.52 > 0.05)
thrpt: [-23.475% -6.7244% +14.566%]
No change in performance detected.
Found 14 outliers among 100 measurements (14.00%)
14 (14.00%) high severe
bytes_in_range/4096 time: [3.3298 µs 3.3416 µs 3.3563 µs]
thrpt: [1.1366 GiB/s 1.1416 GiB/s 1.1456 GiB/s]
change:
time: [+2.0652% +3.0667% +4.3765%] (p = 0.00 < 0.05)
thrpt: [-4.1930% -2.9754% -2.0234%]
Performance has regressed.
Found 2 outliers among 100 measurements (2.00%)
2 (2.00%) high severe
bytes_in_range/65536 time: [80.640 µs 80.825 µs 81.024 µs]
thrpt: [771.38 MiB/s 773.28 MiB/s 775.05 MiB/s]
change:
time: [-0.6566% +1.0994% +2.9691%] (p = 0.27 > 0.05)
thrpt: [-2.8835% -1.0875% +0.6609%]
No change in performance detected.
Found 10 outliers among 100 measurements (10.00%)
2 (2.00%) high mild
8 (8.00%) high severe
chars/4096 time: [763.17 ns 763.68 ns 764.36 ns]
thrpt: [4.9907 GiB/s 4.9952 GiB/s 4.9985 GiB/s]
change:
time: [-2.1138% -0.7973% +0.1096%] (p = 0.18 > 0.05)
thrpt: [-0.1095% +0.8037% +2.1595%]
No change in performance detected.
Found 10 outliers among 100 measurements (10.00%)
1 (1.00%) low severe
6 (6.00%) low mild
3 (3.00%) high severe
chars/65536 time: [12.479 µs 12.503 µs 12.529 µs]
thrpt: [4.8714 GiB/s 4.8817 GiB/s 4.8910 GiB/s]
change:
time: [-2.4451% -1.0638% +0.6633%] (p = 0.16 > 0.05)
thrpt: [-0.6589% +1.0753% +2.5063%]
No change in performance detected.
Found 11 outliers among 100 measurements (11.00%)
4 (4.00%) high mild
7 (7.00%) high severe
clip_point/4096 time: [63.148 µs 63.182 µs 63.229 µs]
thrpt: [61.779 MiB/s 61.825 MiB/s 61.859 MiB/s]
change:
time: [+1.0107% +2.1329% +4.2849%] (p = 0.02 < 0.05)
thrpt: [-4.1088% -2.0883% -1.0006%]
Performance has regressed.
Found 5 outliers among 100 measurements (5.00%)
4 (4.00%) high mild
1 (1.00%) high severe
Benchmarking clip_point/65536: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 7.8s, enable flat sampling, or reduce sample count to 50.
clip_point/65536 time: [1.2578 ms 1.2593 ms 1.2608 ms]
thrpt: [49.573 MiB/s 49.631 MiB/s 49.690 MiB/s]
change:
time: [+0.4881% +0.8942% +1.3488%] (p = 0.00 < 0.05)
thrpt: [-1.3308% -0.8863% -0.4857%]
Change within noise threshold.
Found 15 outliers among 100 measurements (15.00%)
1 (1.00%) high mild
14 (14.00%) high severe
point_to_offset/4096 time: [16.211 µs 16.235 µs 16.257 µs]
thrpt: [240.28 MiB/s 240.61 MiB/s 240.97 MiB/s]
change:
time: [-1.4913% +0.1685% +2.2662%] (p = 0.89 > 0.05)
thrpt: [-2.2159% -0.1682% +1.5139%]
No change in performance detected.
Found 2 outliers among 100 measurements (2.00%)
1 (1.00%) high mild
1 (1.00%) high severe
point_to_offset/65536 time: [360.06 µs 360.58 µs 361.16 µs]
thrpt: [173.05 MiB/s 173.33 MiB/s 173.58 MiB/s]
change:
time: [+0.0939% +0.8792% +1.8751%] (p = 0.06 > 0.05)
thrpt: [-1.8406% -0.8715% -0.0938%]
No change in performance detected.
Found 10 outliers among 100 measurements (10.00%)
3 (3.00%) high mild
7 (7.00%) high severe
cursor/4096 time: [19.266 µs 19.282 µs 19.302 µs]
thrpt: [202.38 MiB/s 202.58 MiB/s 202.75 MiB/s]
change:
time: [+1.2457% +2.2477% +2.8702%] (p = 0.00 < 0.05)
thrpt: [-2.7901% -2.1983% -1.2304%]
Performance has regressed.
Found 4 outliers among 100 measurements (4.00%)
2 (2.00%) high mild
2 (2.00%) high severe
cursor/65536 time: [467.63 µs 468.36 µs 469.14 µs]
thrpt: [133.22 MiB/s 133.44 MiB/s 133.65 MiB/s]
change:
time: [-0.2019% +1.3419% +2.8915%] (p = 0.10 > 0.05)
thrpt: [-2.8103% -1.3241% +0.2023%]
No change in performance detected.
Found 12 outliers among 100 measurements (12.00%)
3 (3.00%) high mild
9 (9.00%) high severe
append many/small to large
time: [37.419 ms 37.656 ms 37.929 ms]
thrpt: [321.84 MiB/s 324.17 MiB/s 326.22 MiB/s]
change:
time: [+0.8113% +1.7361% +2.6538%] (p = 0.00 < 0.05)
thrpt: [-2.5852% -1.7065% -0.8047%]
Change within noise threshold.
Found 9 outliers among 100 measurements (9.00%)
9 (9.00%) high severe
append many/large to small
time: [51.289 ms 51.437 ms 51.614 ms]
thrpt: [236.50 MiB/s 237.32 MiB/s 238.00 MiB/s]
change:
time: [-87.518% -87.479% -87.438%] (p = 0.00 < 0.05)
thrpt: [+696.08% +698.66% +701.13%]
Performance has improved.
Found 13 outliers among 100 measurements (13.00%)
4 (4.00%) high mild
9 (9.00%) high severe
```
</details>
Release Notes:
- sum_tree: Make SumTree::append run in logarithmic time
This PR introduces a new `MultiBufferOffset` new type wrapping size. The
goal of this is to make it clear at the type level when we are
interacting with offsets of a multi buffer versus offsets of a language
/ text buffer. This improves readability of things quite a bit by making
it clear what kind of offsets one is working with while also reducing
accidental bugs by using the wrong kin of offset for the wrong API.
This PR also uncovered two minor bugs due to that.
Does not yet introduce the MultiBufferPoint equivalent, that is for a
follow up PR.
Release Notes:
- N/A *or* Added/Fixed/Improved ...
Thread stacks in rust by default have 2 megabytes of stack which for
sumtrees (or ropes in this case) can easily be exceeded depending on the
workload.
Release Notes:
- Fixed stack overflows when constructing large ropes
Using compiler explorer I saw that the compiler wasn't clever enough to
optimise away the branches in the masking code. I thought the compiler
would have a better chance if we always branched, which [turned out to
be the case](https://godbolt.org/z/PM594Pz18).
Running the benchmarks the biggest benefit I saw was:
```
push/65536 time: [2.9067 ms 2.9243 ms 2.9417 ms]
thrpt: [21.246 MiB/s 21.373 MiB/s 21.502 MiB/s]
change:
time: [-8.3452% -7.2617% -6.2009%] (p = 0.00 < 0.05)
thrpt: [+6.6108% +7.8303% +9.1050%]
Performance has improved.
```
But I did also see some regressions:
```
slice/4096 time: [66.195 µs 66.815 µs 67.448 µs]
thrpt: [57.915 MiB/s 58.464 MiB/s 59.012 MiB/s]
change:
time: [+3.7131% +5.1698% +6.6971%] (p = 0.00 < 0.05)
thrpt: [-6.2768% -4.9157% -3.5802%]
Performance has regressed.
```
Release Notes:
- N/A
Fixes a regression introduced in
https://github.com/zed-industries/zed/pull/39857. As for the exact
reason this causes this issue I am not yet sure will investigate (as per
the todos in code)
Fixes ZED-23R
Release Notes:
- N/A *or* Added/Fixed/Improved ...
Closes https://github.com/zed-industries/zed/issues/38453
Current `Buffer` API only allows getting buffer text with `\n` line
breaks — even if the `\r\n` was used in the original file's text.
This it not correct in certain cases like LSP formatting, where language
servers need to have original document context for e.g. formatting
purposes.
Added new `Buffer` API, replaced all buffer LSP registration places with
the new one and added more tests.
Release Notes:
- Fixed ESLint linebreak-style errors by preserving line endings in LSP
communication
---------
Co-authored-by: Claude <noreply@anthropic.com>
Co-authored-by: Kirill Bulatov <kirill@zed.dev>
We still see a bunch of panics here but the default slicing panic
doesn't tell which side of the range is bad
Release Notes:
- N/A *or* Added/Fixed/Improved ...
This simplifies some code and is also more correct in some others (I
believe some of these might've overflowed causing panics in sentry)
Release Notes:
- N/A *or* Added/Fixed/Improved ...
Follows on from https://github.com/zed-industries/zed/pull/39949.
Again I'm not 100% sure of the intent but I think this is a fix:
`generate_random_string(rng, 4096)` would previously give you a string
of 4096 *chars* which could be anywhere between 4kB and 16kB in bytes.
This seems probably not what was intended, because Ropes generally work
in bytes not chars, including for the offsets used to index into them.
This seems to possibly cause a _regression_ in benchmark performance,
which is surprising because it should generally cause smaller test data.
But, possibly it's doing better at exercising different paths?
cc @mrnugget
Release Notes:
- N/A
In an attempt to figure out what's wrong with `point_to_buffer_offset`
for crash https://github.com/zed-industries/zed/issues/40453. We want to
know which branch among these two is the bad one.
Release Notes:
- N/A
Co-authored-by: Lukas Wirth <lukas@zed.dev>
Reduces peak stack usage in these functions and should generally be a
bit performant.
Display map benchmark results
```
To tab point/to_tab_point/1024
time: [531.40 ns 532.10 ns 532.97 ns]
change: [-2.1824% -2.0054% -1.8125%] (p = 0.00 < 0.05)
Performance has improved.
Found 1 outliers among 100 measurements (1.00%)
1 (1.00%) high severe
To fold point/to_fold_point/1024
time: [530.81 ns 531.30 ns 531.80 ns]
change: [-2.0295% -1.9054% -1.7716%] (p = 0.00 < 0.05)
Performance has improved.
Found 3 outliers among 100 measurements (3.00%)
2 (2.00%) high mild
1 (1.00%) high severe
```
Release Notes:
- N/A *or* Added/Fixed/Improved ...
We've been considering removing workspace-hack for a couple reasons:
- Lukas ran into a situation where its build script seemed to be causing
spurious rebuilds. This seems more likely to be a cargo bug than an
issue with workspace-hack itself (given that it has an empty build
script), but we don't necessarily want to take the time to hunt that
down right now.
- Marshall mentioned hakari interacts poorly with automated crate
updates (in our case provided by rennovate) because you'd need to have
`cargo hakari generate && cargo hakari manage-deps` after their changes
and we prefer to not have actions that make commits.
Currently removing workspace-hack causes our workspace to grow from
~1700 to ~2000 crates being built (depending on platform), which is
mainly a problem when you're building the whole workspace or running
tests across the the normal and remote binaries (which is where
feature-unification nets us the most sharing). It doesn't impact
incremental times noticeably when you're just iterating on `-p zed`, and
we'll hopefully get these savings back in the future when
rust-lang/cargo#14774 (which re-implements the functionality of hakari)
is finished.
Release Notes:
- N/A
Using a seeded PRNG to produce consistent test data and reduce
variability makes sense.
However, the way it was used previously, by always cloning the RNG,
means that every generated string is the same, and every offset is the
same. After this change, the tested value stream should still be the same on
each run of the benchmark, but the values within each run will vary.
The `generate_random_text` measured in chars also seems possibly
inconsistent with later comments about it being a number of bytes.
Release Notes:
- N/A
The previous code clones all the rope chunks, but the rope is passed by
value so the chunks are about to be dropped anyhow.
I thought this may slightly help performance but it has no very
noticeable effect, with a mix of small changes up and down probably
attributable to noise on my machine?
I wonder if the benchmarks might just not hit this path well? I'm
looking into that separately (see #39949, #39951), but this seemed clear
enough to be worth proposing by itself.
Incidentally it surprised me this did not generate a warning already,
but I think it's because we're taking only one field from the struct
that's about to be dropped:
https://github.com/rust-lang/rust-clippy/issues/7429.
<details>
```
Running benches/rope_benchmark.rs (target/release/deps/rope_benchmark-4c5c71666e7c1729)
push/4096 time: [362.58 µs 366.40 µs 370.69 µs]
thrpt: [10.538 MiB/s 10.661 MiB/s 10.773 MiB/s]
change:
time: [+0.0646% +1.2362% +2.4681%] (p = 0.04 < 0.05)
thrpt: [-2.4086% -1.2211% -0.0646%]
Change within noise threshold.
Found 10 outliers among 100 measurements (10.00%)
7 (7.00%) high mild
3 (3.00%) high severe
Benchmarking push/65536: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 8.4s, enable flat sampling, or reduce sample count to 50.
push/65536 time: [1.6185 ms 1.6353 ms 1.6557 ms]
thrpt: [37.747 MiB/s 38.219 MiB/s 38.616 MiB/s]
change:
time: [+1.9135% +2.9548% +3.9838%] (p = 0.00 < 0.05)
thrpt: [-3.8312% -2.8700% -1.8776%]
Performance has regressed.
Found 6 outliers among 100 measurements (6.00%)
5 (5.00%) high mild
1 (1.00%) high severe
append/4096 time: [1.1052 µs 1.1104 µs 1.1162 µs]
thrpt: [3.4177 GiB/s 3.4354 GiB/s 3.4516 GiB/s]
change:
time: [-2.5075% -0.3430% +1.5095%] (p = 0.76 > 0.05)
thrpt: [-1.4871% +0.3441% +2.5720%]
No change in performance detected.
Found 8 outliers among 100 measurements (8.00%)
7 (7.00%) high mild
1 (1.00%) high severe
append/65536 time: [12.404 µs 12.444 µs 12.487 µs]
thrpt: [4.8881 GiB/s 4.9049 GiB/s 4.9204 GiB/s]
change:
time: [-0.1408% +0.5573% +1.2016%] (p = 0.10 > 0.05)
thrpt: [-1.1874% -0.5542% +0.1410%]
No change in performance detected.
Found 5 outliers among 100 measurements (5.00%)
2 (2.00%) high mild
3 (3.00%) high severe
slice/4096 time: [32.963 µs 33.185 µs 33.466 µs]
thrpt: [116.72 MiB/s 117.71 MiB/s 118.51 MiB/s]
change:
time: [-6.4303% -5.1234% -3.6394%] (p = 0.00 < 0.05)
thrpt: [+3.7769% +5.4000% +6.8722%]
Performance has improved.
Found 2 outliers among 100 measurements (2.00%)
1 (1.00%) high mild
1 (1.00%) high severe
slice/65536 time: [668.67 µs 670.49 µs 672.65 µs]
thrpt: [92.916 MiB/s 93.215 MiB/s 93.469 MiB/s]
change:
time: [+0.0846% +0.5573% +1.0199%] (p = 0.02 < 0.05)
thrpt: [-1.0096% -0.5542% -0.0845%]
Change within noise threshold.
Found 10 outliers among 100 measurements (10.00%)
6 (6.00%) high mild
4 (4.00%) high severe
bytes_in_range/4096 time: [5.1513 µs 5.1594 µs 5.1674 µs]
thrpt: [755.95 MiB/s 757.12 MiB/s 758.31 MiB/s]
change:
time: [-4.9410% -4.2051% -3.3835%] (p = 0.00 < 0.05)
thrpt: [+3.5020% +4.3897% +5.1978%]
Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
1 (1.00%) low mild
3 (3.00%) high severe
bytes_in_range/65536 time: [139.87 µs 140.17 µs 140.55 µs]
thrpt: [444.67 MiB/s 445.89 MiB/s 446.85 MiB/s]
change:
time: [-0.6267% -0.0474% +0.4635%] (p = 0.87 > 0.05)
thrpt: [-0.4614% +0.0475% +0.6306%]
No change in performance detected.
Found 9 outliers among 100 measurements (9.00%)
7 (7.00%) high mild
2 (2.00%) high severe
chars/4096 time: [1.0243 µs 1.0250 µs 1.0257 µs]
thrpt: [3.7190 GiB/s 3.7217 GiB/s 3.7243 GiB/s]
change:
time: [+4.0106% +4.5396% +5.3062%] (p = 0.00 < 0.05)
thrpt: [-5.0388% -4.3425% -3.8559%]
Performance has regressed.
Found 10 outliers among 100 measurements (10.00%)
2 (2.00%) high mild
8 (8.00%) high severe
chars/65536 time: [17.540 µs 17.576 µs 17.614 µs]
thrpt: [3.4652 GiB/s 3.4727 GiB/s 3.4797 GiB/s]
change:
time: [+2.5201% +3.3922% +4.1639%] (p = 0.00 < 0.05)
thrpt: [-3.9974% -3.2809% -2.4581%]
Performance has regressed.
Found 7 outliers among 100 measurements (7.00%)
4 (4.00%) high mild
3 (3.00%) high severe
clip_point/4096 time: [58.857 µs 59.162 µs 59.490 µs]
thrpt: [65.662 MiB/s 66.026 MiB/s 66.368 MiB/s]
change:
time: [+1.6900% +2.8088% +3.8521%] (p = 0.00 < 0.05)
thrpt: [-3.7092% -2.7321% -1.6619%]
Performance has regressed.
Found 3 outliers among 100 measurements (3.00%)
3 (3.00%) high mild
clip_point/65536 time: [1.8609 ms 1.8633 ms 1.8660 ms]
thrpt: [33.494 MiB/s 33.543 MiB/s 33.585 MiB/s]
change:
time: [+0.0577% +0.2579% +0.4495%] (p = 0.01 < 0.05)
thrpt: [-0.4474% -0.2572% -0.0577%]
Change within noise threshold.
Found 5 outliers among 100 measurements (5.00%)
3 (3.00%) high mild
2 (2.00%) high severe
point_to_offset/4096 time: [19.246 µs 19.287 µs 19.331 µs]
thrpt: [202.07 MiB/s 202.54 MiB/s 202.97 MiB/s]
change:
time: [+1.1073% +2.9754% +5.3818%] (p = 0.00 < 0.05)
thrpt: [-5.1069% -2.8894% -1.0951%]
Performance has regressed.
Found 13 outliers among 100 measurements (13.00%)
5 (5.00%) high mild
8 (8.00%) high severe
Benchmarking point_to_offset/65536: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 6.6s, enable flat sampling, or reduce sample count to 60.
point_to_offset/65536 time: [741.87 µs 743.28 µs 744.74 µs]
thrpt: [83.922 MiB/s 84.086 MiB/s 84.247 MiB/s]
change:
time: [+5.0577% +5.6751% +6.3133%] (p = 0.00 < 0.05)
thrpt: [-5.9384% -5.3703% -4.8142%]
Performance has regressed.
Found 7 outliers among 100 measurements (7.00%)
4 (4.00%) high mild
3 (3.00%) high severe
cursor/4096 time: [27.407 µs 27.483 µs 27.600 µs]
thrpt: [141.53 MiB/s 142.13 MiB/s 142.53 MiB/s]
change:
time: [-7.1479% -6.2928% -5.6378%] (p = 0.00 < 0.05)
thrpt: [+5.9747% +6.7154% +7.6981%]
Performance has improved.
Found 9 outliers among 100 measurements (9.00%)
1 (1.00%) high mild
8 (8.00%) high severe
cursor/65536 time: [848.91 µs 849.70 µs 850.59 µs]
thrpt: [73.478 MiB/s 73.555 MiB/s 73.624 MiB/s]
change:
time: [+0.0281% +0.3487% +0.6686%] (p = 0.04 < 0.05)
thrpt: [-0.6642% -0.3475% -0.0281%]
Change within noise threshold.
Found 9 outliers among 100 measurements (9.00%)
5 (5.00%) high mild
4 (4.00%) high severe
```
</details>
Release Notes:
- N/A
I was looking at the rope implementation and some of the existing bugs
that crash in there, and I ran cargo-mutants to inspect test coverage. I
was motivated by bugs like
https://github.com/zed-industries/zed/issues/38556 but this doesn't fix
it and the bug may well be at a higher layer.
This PR adds coverage for a few functions that aren't tested today. I
didn't find any actual bugs yet.
I can see this tree is pretty sparse on docstrings so if you think these
are too verbose I can take them out or drop the whole PR.
Release Notes:
- N/A
This panic only happened in debug builds because of a left shift
overflow. The slice range has bounds between 0 and 128. The 128 case
caused the overflow.
We now do an unbounded shift and a wrapped sub to get the correct
bitmask. If the slice range is 128 left, it should make 1 zero. Then the
wrapped sub would flip all bits, which is expected behavior.
Release Notes:
- N/A
Co-authored-by: Nia <nia@zed.dev>
## Context
While looking into: #32051 and #16120 with instruments, I noticed that
`TabSnapshot::to_tab_point` and `TabSnapshot::to_fold_point` are a
common bottleneck between the two issues. This PR takes the first steps
into closing the stated issues by improving the performance of both
those functions.
### Method
`to_tab_point` and `to_fold_point` iterate through each character in
their rows to find tab characters and translate those characters into
their respective transformations. This PR changes this iteration to take
advantage of the tab character bitmap in the `Rope` data structure and
goes directly to each tab character when iterating.
The tab bitmap is now passed from each layer in-between the `Rope` to
the `TabMap`.
### Testing
I added several randomized tests to ensure that the new `to_tab_point`
and `to_fold_point` functions have the same behavior as the old methods
they're replacing. I also added `test_random_chunk_bitmap` on each layer
the tab bitmap is passed up to the `TabMap` to make sure that the bitmap
being passed is transformed correctly between the layers of
`DisplayMap`.
`test_random_chunk_bitmap` was added to these layers:
- buffer
- multi buffer
- custom_highlights
- inlay_map
- fold_map
## Benchmarking
I setup benchmarks with criterion that is runnable via `cargo bench -p
editor --profile=release-fast`. When benchmarking I had my laptop
plugged in and did so from the terminal with a minimal amount of
processes running. I'm also on a m4 max
### Results
#### To Tab Point
Went from completing 6.8M iterations in 5s with an average time of
`736.13 ns` to `683.38 ns` which is a `-7.1875%` improvement
#### To Fold Point
Went from completing 6.8M iterations in 5s with an average time of
`736.55 ns` to `682.40 ns` which is a `-7.1659%` improvement
#### Editor render
Went from having an average render time of `62.561 µs` to `57.216 µs`
which is a `-8.8248%` improvement
#### Build Buffer with one long line
Went from having an average buffer build time of `3.2549 ms` to `3.2635
ms` which is a `+0.2151%` regression within the margin of error
#### Editor with 1000 multi cursor input
Went from having an average edit time of `133.05 ms` to `122.96 ms`
which is a `-7.5776%` improvement
Release Notes:
- N/A
---------
Co-authored-by: Remco Smits <djsmits12@gmail.com>
Co-authored-by: Cole Miller <cole@zed.dev>
Co-authored-by: Piotr Osiewicz <24362066+osiewicz@users.noreply.github.com>
Extracts and cleans up GPUI's scheduler code into a new `scheduler`
crate, making it pluggable by external runtimes. This will enable
deterministic integration testing with cloud components by providing a
unified test scheduler across Zed and backend code. In Zed, it will
replace the existing GPUI scheduler for consistent async task management
across platforms.
## Changes
- **Core Implementation**: `TestScheduler` with seed-based
randomization, session tracking (`SessionId`), and foreground/background
task separation for reproducible testing.
- **Executors**: `ForegroundExecutor` (!Send, thread-local) and
`BackgroundExecutor` (Send, with blocking/timeout support) as
GPUI-compatible wrappers.
- **Clock and Timer**: Controllable `TestClock` and future-based `Timer`
for time-sensitive tests.
- **Testing APIs**: `once()`, `with_seed()`, and `many()` methods for
configurable test runs.
- **Dependencies**: Added `async-task`, `chrono`, `futures`, etc., with
updates to `Cargo.toml` and lock file.
## Benefits
- **Integration Testing**: Facilitates reliable async tests involving
cloud sessions, reducing flakiness via deterministic execution.
- **Pluggability**: Trait-based design (`Scheduler`) allows easy
integration into non-GPUI runtimes while maintaining GPUI compatibility.
- **Cleanup**: Refactors GPUI scheduler logic for clarity, correctness
(no `unwrap()`, proper error handling), and extensibility.
Follows Rust guidelines; run `./script/clippy` for verification.
- [x] Define and test a core scheduler that we think can power our cloud
code and GPUI
- [ ] Replace GPUI's scheduler
Release Notes:
- N/A
---------
Co-authored-by: Antonio Scandurra <me@as-cii.com>
This removes around 900 unnecessary clones, ranging from cloning a few
ints all the way to large data structures and images.
A lot of these were fixed using `cargo clippy --fix --workspace
--all-targets`, however it often breaks other lints and needs to be run
again. This was then followed up with some manual fixing.
I understand this is a large diff, but all the changes are pretty
trivial. Rust is doing some heavy lifting here for us. Once I get it up
to speed with main, I'd appreciate this getting merged rather sooner
than later.
Release Notes:
- N/A
This is a bit of a readability improvement IMHO; I often find myself
confused when dealing when dimension pairs, as there's no easy way to
jump to the implementation of a dimension for tuples to remind myself
for the n-th time how exactly that impl works. Now it should be possible
to jump directly to that impl.
Another bonus is that Dimension supports 3-ary tuples as well - by using
a () as a default value of a 3rd dimension.
Release Notes:
- N/A
This gets rid of the need to pass context to all cursor functions. In
practice context is always immutable when interacting with cursors.
A nicety of this is in the follow-up PR we will be able to implement
Iterator for all Cursors/filter cursors (hell, we may be able to get rid
of filter cursor altogether, as it is just a custom `filter` impl on
iterator trait).
Release Notes:
- N/A
