Repository: pest-parser/pest (language: rust)

Issue:
Pest 2.1 performance regression
I have a similar problem to #279 and #378 on Pest 2.1, and there seems to be a massive performance regression from previous versions of Pest in my code base between 2.1 and 2.0.

Previously I could load models with 1000s lines from debugging builds practically instantly. Since I switched to 2.1, the same models take "infinitely" long (I run out of patience after a few minutes).

One observation I made is that the length of the whole file seems to affect the time it takes to parse individual lines. In a simple test where I `println!` within `for line in parsed.into_inner() {}`, the speed between printed lines varies with the number of total lines.

Running Instruments, I get the following profiler output:

```
7.84 s  100.0%	0 s	 	                          ffsvm::parser::_$LT$impl$u20$core..convert..TryFrom$LT$$RF$$u27$a$u20$str$GT$$u20$for$u20$ffsvm..parser..raw..ModelFile$LT$$u27$a$GT$$GT$::try_from::h18a6cfd922c8ed7c
7.84 s   99.9%	0 s	 	                           _$LT$pest..iterators..pairs..Pairs$LT$$u27$i$C$$u20$R$GT$$u20$as$u20$core..iter..traits..iterator..Iterator$GT$::next::h09b47153f8ca7064
7.83 s   99.9%	0 s	 	                            _$LT$pest..iterators..pairs..Pairs$LT$$u27$i$C$$u20$R$GT$$GT$::peek::hd5e391ef9b3bd4a5
7.82 s   99.7%	1.17 s	 	                             pest::iterators::pair::new::h6f918a45a21ac4ca
5.12 s   65.2%	154.00 ms	 	                              core::str::_$LT$impl$u20$str$GT$::get::h8e194b7c827218ed
4.96 s   63.2%	340.00 ms	 	                               core::str::traits::_$LT$impl$u20$core..slice..SliceIndex$LT$str$GT$$u20$for$u20$core..ops..range..RangeFrom$LT$usize$GT$$GT$::get::hb7a80d56daccaebf
2.91 s   37.1%	841.00 ms	 	                                core::str::_$LT$impl$u20$str$GT$::is_char_boundary::heba54db0f6b30891
1.46 s   18.6%	135.00 ms	 	                                 core::slice::_$LT$impl$u20$$u5b$T$u5d$$GT$::get::h6ea878e5fd88bc3c
559.00 ms    7.1%	223.00 ms	 	                                 core::str::_$LT$impl$u20$str$GT$::len::hdc7068d95f08cfc7
45.00 ms    0.5%	45.00 ms	 	                                 core::str::_$LT$impl$u20$str$GT$::as_bytes::hb983c1a31bd2996f
7.00 ms    0.0%	0 s	 	                                 <Unknown Address>
1.68 s   21.4%	397.00 ms	 	                                core::str::traits::_$LT$impl$u20$core..slice..SliceIndex$LT$str$GT$$u20$for$u20$core..ops..range..RangeFrom$LT$usize$GT$$GT$::get_unchecked::h555020fa357d7a96
28.00 ms    0.3%	0 s	 	                                <Unknown Address>
```

Navigating there in Instruments gives these lines:

```
// TODO(safety): QueueableTokens must be valid indices into input.
pub fn new<R: RuleType>(queue: Rc<Vec<QueueableToken<R>>>, input: &str, start: usize) -> Pair<R> {
    if cfg!(debug_assertions) {
        for tok in queue.iter() {
            match *tok {
                QueueableToken::Start { input_pos, .. } | QueueableToken::End { input_pos, .. } => {
                    assert!(
                        input.get(input_pos..).is_some(),
                        "💥 UNSAFE `Pair` CREATED 💥"
                    )
                }
            }
        }
    }
```
(This code might or might not be related to the actual problem, just providing the output I got.)

Similarly to #378 the speed gets _dramatically_ faster if I run with `--release`. Unfortunately this is not a solution for me, because in dependent projects I have many unit tests with "larger" files to be parsed on `cargo test`, which now all timeout. 
Reinforce invariants on Position
`Position` currently uses `unsafe` in quite a few places. Maybe there is a better way to model this in order to minimize the use of `unsafe` and strengthen its invariants.


Discussion / hints:
**Update** - I [pushed a branch](https://github.com/ralfbiedert/ffsvm-rust/tree/pest_performance) that exhibits the problem when running `cargo test`. The test `svm_parsing::load_large` loads a 200k text file and takes forever. 

The problem persists when switching `pest` to the lastest Github master in `Cargo.toml`. Unfortunately I can't switch `pest_derive`, as it will panic in `/pest_meta-807ef3ca8bc96e00/build-script-build`.
Yep, this is a pretty expensive correctness check.

As a temporary workaround, you can disable debug assertions on the test/debug profile to get the faster path.

cc #301
By pretty expensive, I mean that every time this path to create a tree ref (`Pair`) is used, the debug assertion iterates the full tree to make sure that none of the indexes are outside the source string. When I added it I didn't realize this would be a hot path.

Removing the check is just a matter of a) going back to trusting or b) properly tracing the dependencies such that there's no chance of breaking safety invariants in safe code.
Ping. This prevents me from using my crate in debug mode, which is a bit inconvenient...
You should be [able to do](https://doc.rust-lang.org/cargo/reference/manifest.html#the-profile-sections)

```
[profile.dev]
debug-assertions = false
```

and that will disable the checks as a workaround for now. I don't have much time to work on pest right now and dragostis is spending his limited time experimenting with v3, so unfortunately it might be a while before we can attack this correctness assertion.
AFAIU you could just remove the assertion for now? Its addition is a clear regression, so a revert would make sense until you have figured out a suitable replacement.
@birkenfeld, does `debug-assertions = false` solve this?
For applications this might just work, but not for libraries.  

In my case I provide a model loader that might be embedded in other libraries, which, in turn, might be embedded in even other libraries or applications. 

Unless I'm missing something all upstream users would have to set (and each in turn communicate upstream to set) `debug-assertions = false`. Some of those might even rely on debug assertions themselves. 
@ralfbiedert, very good point. We should find a solution on our side and do a point release. Is reverting back to trusting tertiary code a fine trade-off?
I'm fine with removing the debug_assert so long as a comment remains reminding us that the code is relying on weakly enforced guarantees. #301 can continue to track the improvement (though i suppose as v3 will retire the `Pairs` API, it will be automatically outdated then).
Related to #293.
Is this still going, @dragostis? I'm asking because there is a merged PR already
@wisn, thanks for the ping. I think this is fine. If @CAD97 is fine with the current state of affairs, we can close this.
#383 is a case where one of the expensive correctness checks (gated on debug assertions) is causing unacceptable performance degredation in debug mode (therefore making it useless). (When I added it, I thought/hoped it wasn't on a hot path.)

I think we need to make that invariant obvious on the type so that this sanity check can be removed, and then we can consider this closed.

All that needs to happen performance wise is an `unsafe` path that's used when the invariant is guaranteed (on pain of nasal demons) to hold. A type combining the queue Rc and the input ref to guarantee that the queue refers to that input seems the way to go.

Fix patch:
diff --git a/pest/src/iterators/flat_pairs.rs b/pest/src/iterators/flat_pairs.rs
index 89ce8291..bb5bbb18 100644
--- a/pest/src/iterators/flat_pairs.rs
+++ b/pest/src/iterators/flat_pairs.rs
@@ -20,13 +20,19 @@ use RuleType;
 /// [`Pair`]: struct.Pair.html
 /// [`Pairs::flatten`]: struct.Pairs.html#method.flatten
 pub struct FlatPairs<'i, R> {
+    /// # Safety
+    ///
+    /// All `QueueableToken`s' `input_pos` must be valid character boundary indices into `input`.
     queue: Rc<Vec<QueueableToken<R>>>,
     input: &'i str,
     start: usize,
     end: usize,
 }
 
-pub fn new<R: RuleType>(
+/// # Safety
+///
+/// All `QueueableToken`s' `input_pos` must be valid character boundary indices into `input`.
+pub unsafe fn new<R: RuleType>(
     queue: Rc<Vec<QueueableToken<R>>>,
     input: &str,
     start: usize,
@@ -100,7 +106,7 @@ impl<'i, R: RuleType> Iterator for FlatPairs<'i, R> {
             return None;
         }
 
-        let pair = pair::new(Rc::clone(&self.queue), self.input, self.start);
+        let pair = unsafe { pair::new(Rc::clone(&self.queue), self.input, self.start) };
 
         self.next_start();
 
@@ -116,7 +122,7 @@ impl<'i, R: RuleType> DoubleEndedIterator for FlatPairs<'i, R> {
 
         self.next_start_from_end();
 
-        let pair = pair::new(Rc::clone(&self.queue), self.input, self.end);
+        let pair = unsafe { pair::new(Rc::clone(&self.queue), self.input, self.end) };
 
         Some(pair)
     }
diff --git a/pest/src/iterators/pair.rs b/pest/src/iterators/pair.rs
index 77053528..88844a35 100644
--- a/pest/src/iterators/pair.rs
+++ b/pest/src/iterators/pair.rs
@@ -41,21 +41,14 @@ pub struct Pair<'i, R> {
     start: usize,
 }
 
-// TODO(safety): QueueableTokens must be valid indices into input.
-pub fn new<R: RuleType>(queue: Rc<Vec<QueueableToken<R>>>, input: &str, start: usize) -> Pair<R> {
-    if cfg!(debug_assertions) {
-        for tok in queue.iter() {
-            match *tok {
-                QueueableToken::Start { input_pos, .. } | QueueableToken::End { input_pos, .. } => {
-                    assert!(
-                        input.get(input_pos..).is_some(),
-                        "💥 UNSAFE `Pair` CREATED 💥"
-                    )
-                }
-            }
-        }
-    }
-
+/// # Safety
+///
+/// All `QueueableToken`s' `input_pos` must be valid character boundary indices into `input`.
+pub unsafe fn new<R: RuleType>(
+    queue: Rc<Vec<QueueableToken<R>>>,
+    input: &str,
+    start: usize,
+) -> Pair<R> {
     Pair {
         queue,
         input,
diff --git a/pest/src/iterators/pairs.rs b/pest/src/iterators/pairs.rs
index 42072c0f..446607fe 100644
--- a/pest/src/iterators/pairs.rs
+++ b/pest/src/iterators/pairs.rs
@@ -141,7 +141,7 @@ impl<'i, R: RuleType> Pairs<'i, R> {
     /// ```
     #[inline]
     pub fn flatten(self) -> FlatPairs<'i, R> {
-        flat_pairs::new(self.queue, self.input, self.start, self.end)
+        unsafe { flat_pairs::new(self.queue, self.input, self.start, self.end) }
     }
 
     /// Returns the `Tokens` for the `Pairs`.
@@ -175,7 +175,7 @@ impl<'i, R: RuleType> Pairs<'i, R> {
     #[inline]
     pub fn peek(&self) -> Option<Pair<'i, R>> {
         if self.start < self.end {
-            Some(pair::new(Rc::clone(&self.queue), self.input, self.start))
+            Some(unsafe { pair::new(Rc::clone(&self.queue), self.input, self.start) })
         } else {
             None
         }
@@ -233,7 +233,7 @@ impl<'i, R: RuleType> DoubleEndedIterator for Pairs<'i, R> {
 
         self.end = self.pair_from_end();
 
-        let pair = pair::new(Rc::clone(&self.queue), self.input, self.end);
+        let pair = unsafe { pair::new(Rc::clone(&self.queue), self.input, self.end) };
 
         Some(pair)
     }


Test patch: