4 ms·

Man, I only gave some friendly feedback ;) "this will absolutely trash the performance of a DFA search loop." Do you happen to have some hard data to quantify

• burntsushi 4y ago
  Yes. I work on regex engines. Here's the code with all the crazy checks that return errors that can never happen: fn find_fwd_imp<A: Automaton + ?Sized>( dfa: &A, input: &Input<'_, '_>, pre: Option<&'_ dyn Prefilter>, earliest: bool, ) -> Result<Option<HalfMatch>, MatchError> { let mut mat = None; let mut sid = init_fwd(dfa, input)?; let mut at = input.start(); while at < input.end() { let byte = match input.haystack().get(at) { None => return Err(MatchError::GaveUp { offset: at }), Some(&byte) => byte, }; sid = dfa.try_next_state(sid, byte)?; if dfa.is_special_state(sid) { if dfa.is_match_state(sid) { let pattern = dfa.match_pattern(sid, 0); mat = Some(HalfMatch::new(pattern, at)); } else if dfa.is_dead_state(sid) { return Ok(mat); } } at = match at.checked_add(1) { None => return Err(MatchError::GaveUp { offset: at }), Some(at) => at, }; } eoi_fwd(dfa, input, &mut sid, &mut mat)?; Ok(mat) } And here's a search (I ran it a few times): $ regex-cli count matches dfa dense @$medium '\w{42}' parse time: 45.331µs translate time: 28.767µs compile nfa time: 9.577558ms nfa memory: 698148 compile dense dfa time: 516.497476ms dense dfa memory: 6562848 dense alphabet length: 113 dense stride: 128 search time: 531.808124ms counts: [2] Here's code that's safe that will panic when there's a bug: fn find_fwd_imp<A: Automaton + ?Sized>( dfa: &A, input: &Input<'_, '_>, pre: Option<&'_ dyn Prefilter>, earliest: bool, ) -> Result<Option<HalfMatch>, MatchError> { let mut mat = None; let mut sid = init_fwd(dfa, input)?; let mut at = input.start(); while at < input.end() { sid = dfa.next_state(sid, input.haystack()[at]); if dfa.is_special_state(sid) { if dfa.is_match_state(sid) { let pattern = dfa.match_pattern(sid, 0); mat = Some(HalfMatch::new(pattern, at)); } else if dfa.is_dead_state(sid) { return Ok(mat); } } at += 1; } eoi_fwd(dfa, input, &mut sid, &mut mat)?; Ok(mat) } And here's a search with it: $ regex-cli count matches dfa dense @$medium '\w{42}' parse time: 33.701µs translate time: 24.264µs compile nfa time: 9.55935ms nfa memory: 698148 compile dense dfa time: 550.959698ms dense dfa memory: 6562848 dense alphabet length: 113 dense stride: 128 search time: 468.932568ms counts: [2] So that's 10% right there. We can keep going though. Let's get rid of the bounds checks. We have to use unsafe though. The stakes have risen. Now if there's a bug, we probably won't get a panic. Instead we get UB. Which might lead to all sorts of bad stuff. fn find_fwd_imp<A: Automaton + ?Sized>( dfa: &A, input: &Input<'_, '_>, pre: Option<&'_ dyn Prefilter>, earliest: bool, ) -> Result<Option<HalfMatch>, MatchError> { let mut mat = None; let mut sid = init_fwd(dfa, input)?; let mut at = input.start(); while at < input.end() { sid = unsafe { let byte = *input.haystack().get_unchecked(at); dfa.next_state_unchecked(sid, byte) }; if dfa.is_special_state(sid) { if dfa.is_match_state(sid) { let pattern = dfa.match_pattern(sid, 0); mat = Some(HalfMatch::new(pattern, at)); } else if dfa.is_dead_state(sid) { return Ok(mat); } } at += 1; } eoi_fwd(dfa, input, &mut sid, &mut mat)?; Ok(mat) } And now the same search: $ regex-cli count matches dfa dense @$medium '\w{42}' parse time: 22.511µs translate time: 26.843µs compile nfa time: 8.709352ms nfa memory: 698148 compile dense dfa time: 565.365005ms dense dfa memory: 6562848 dense alphabet length: 113 dense stride: 128 search time: 456.402963ms counts: [2] For a smaller gain.
  • fatherzine 4y ago
    This is so awesome, thanks for sharing! I am happy that the "~10% perf hit" intuition is reasonably close to what the data shows. What is the right tradeoff? I am not an author of widely popular regex engines, so I'll leave that evaluation to more qualified people.
    • burntsushi 4y ago
      10% is an excellent win. And given that I consider the first code snippet to be effectively nonsense, the right trade off is obvious to me. :) I bet if me and you sat down with a big codebase side-by-side, I could convince you that the style you're proposing is totally unworkable. Now, whether it's worth it to use unsafe and elide bounds checks is harder. The gain I showed here is small, but it can be bigger in other examples. It depends. But it is certainly less clear. It helps that this is probanly the easiest kind of unsafe to justify, because you just have to make sure the index is in bounds. Other types of unsafe can be quite tricky to justify.
• ninkendo 4y ago
  One additional data point: The Rust compiler got ~2% faster when they made some of the core traits in the serializer infallible (ie. panic instead of using Result): https://github.com/rust-lang/rust/pull/93066 https://github.com/rust-lang/rust/pull/93066 Writeup from the contributor: https://nnethercote.github.io/2022/02/25/how-to-speed-up-the-rust-compiler-in-2022.html https://nnethercote.github.io/2022/02/25/how-to-speed-up-the... > The Decoder trait used for metadata decoding was fallible, using Result throughout. But decoding failures should only happen if something highly unexpected happens (e.g. metadata is corrupted) and on failure the calling code would just abort. This PR changed Decoder to be infallible throughout—panicking immediately instead of panicking slightly later—thus avoiding lots of pointless Result propagation, for wins across many benchmarks of up to 2%.