RegexSet match first [feature request]

[jayanderson]

The common case (for me at least) is to expect only one of the regular expressions in the set to match. I assume the is_match function works by finding the first match. It'd be nice to be able to know which regular expression that was. The (somewhat contrived) benchmark below shows that performing the full match and then getting the first match is slower than is_match. Could adding a function to return the index of the first match have the same performance as is_match? Let me know if I'm off in my assumptions or if there's something else causing the slowdown.

#[cfg(test)]
mod tests {
  use regex::RegexSet;
  use test::Bencher;

  #[bench]
  fn is_match_regex_set(b: &mut Bencher) {
    let regexset = RegexSet::new(&[
      r"^0+",
      r"^1+",
      r"^2+",
      r"^3+",
      r"^4+",
      r"^a+",
      r"^5+",
      r"^6+",
      r"^7+",
      r"^8+",
      r"^9+",
    ]).unwrap();
    b.iter(|| regexset.is_match("aaaaa"));
  }

  #[bench]
  fn match_first_regex_set(b: &mut Bencher) {
    let regexset = RegexSet::new(&[
      r"^0+",
      r"^1+",
      r"^2+",
      r"^3+",
      r"^4+",
      r"^a+",
      r"^5+",
      r"^6+",
      r"^7+",
      r"^8+",
      r"^9+",
    ]).unwrap();
    b.iter(|| regexset.matches("aaaaa").into_iter().next().unwrap());
  }
}

running 2 tests
test tests::is_match_regex_set    ... bench:          13 ns/iter (+/- 1)
test tests::match_first_regex_set ... bench:         320 ns/iter (+/- 8)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured

[BurntSushi]

This sounds interesting and potentially plausible, but I have to think about whether it's possible or not. The RegexSet additions to the DFA can be pretty tricky to reason about. In theory, it seems quite possible, since is_match does indeed have to observe a Match state, and if it observes a Match state, then it must also observe the identifier stored in that Match state (which corresponds to the regex in the set that matched).

I am also a little surprised at the speed difference in your benchmark, particularly given that only one regex will match and all of them are anchored (so that both regexes will short circuit). The only real extra work involved is looping over all of the NFA states in the final DFA state to find the precise Match states (which contain the ids of the regexes that matched). This same exact step would be required for your use case too, which suggests one wouldn't realize any performance gains. Therefore, I think one would have to change how that initial Match state is observed such that we wouldn't have to loop over all of the NFA states to find it at the end.

With that said, it's probably worth an experiment to make sure I've got the performance analysis correct. Unfortunately, that experiment requires a bit of plumbing through both the DFA and the execution planner, so it's probably not very accessible.

[jayanderson]

(I don't know good ways to get profiling data and I'm out of my depth in this code and rust really, but here's a try.) Playing with https://github.com/pegasos1/cargo-profiler I was able to run this code for testing:

  let regexset = RegexSet::new(&[
    r"^0+",
    r"^1+",
    r"^2+",
    r"^3+",
    r"^4+",
    r"^a+",
    r"^5+",
    r"^6+",
    r"^7+",
    r"^8+",
    r"^9+",
  ]).unwrap();
  for _ in 0..10000 {
    regexset.is_match("aaaaa");
    //regexset.matches("aaaaa");
  }

I put this in a main file and swapped out which method it ran against. Then I used cargo profiler callgrind -n 20 --bin ./target/release/regex_set to get the callgrind data. Here's with `is_match:

Profiling regex_set with callgrind...

Total Instructions...2,353,786

770,108 (32.7%) dfa.rs:regex::re_set::unicode::RegexSet::is_match
-----------------------------------------------------------------------
300,002 (12.7%) re_set.rs:regex::re_set::unicode::RegexSet::is_match
-----------------------------------------------------------------------
170,004 (7.2%) exec.rs:regex::re_set::unicode::RegexSet::is_match
-----------------------------------------------------------------------
75,295 (3.2%) dl-lookup.c:do_lookup_x
-----------------------------------------------------------------------
63,269 (2.7%) ???:je_arena_tcache_fill_small
-----------------------------------------------------------------------
51,459 (2.2%) ???:je_arena_boot
-----------------------------------------------------------------------
50,979 (2.2%) vfscanf.c:_IO_vfscanf
-----------------------------------------------------------------------
50,000 (2.1%) cell.rs:regex::re_set::unicode::RegexSet::is_match
-----------------------------------------------------------------------
40,504 (1.7%) dl-lookup.c:_dl_lookup_symbol_x
-----------------------------------------------------------------------
34,041 (1.4%) ???:sdallocx
-----------------------------------------------------------------------
33,799 (1.4%) ???:mallocx
-----------------------------------------------------------------------
31,518 (1.3%) dl-machine.h:_dl_relocate_object
-----------------------------------------------------------------------
31,179 (1.3%) strcmp.S:strcmp'2
-----------------------------------------------------------------------
30,077 (1.3%) vec.rs:regex_set::main
-----------------------------------------------------------------------
30,003 (1.3%) cmp.rs:regex_set::main
-----------------------------------------------------------------------
30,003 (1.3%) lib.rs:regex::re_set::unicode::RegexSet::is_match
-----------------------------------------------------------------------
25,087 (1.1%) strtol_l.c:____strtoul_l_internal
-----------------------------------------------------------------------
20,079 (0.9%) dfa.rs:regex::compile::Compiler::new
-----------------------------------------------------------------------
20,008 (0.9%) main.rs:regex_set::main
-----------------------------------------------------------------------
20,006 (0.8%) pthread_self.c:pthread_self
-----------------------------------------------------------------------

Here's with matches:

Profiling regex_set with callgrind...

Total Instructions...27,953,521

4,410,053 (15.8%) dfa.rs:regex::exec::ExecNoSync::many_matches_at
-----------------------------------------------------------------------
3,247,128 (11.6%) ???:rallocx
-----------------------------------------------------------------------
2,584,953 (9.2%) ???:je_arena_ralloc_no_move
-----------------------------------------------------------------------
2,271,827 (8.1%) dfa.rs:regex::dfa::Fsm::next_state
-----------------------------------------------------------------------
1,634,549 (5.8%) ???:sdallocx
-----------------------------------------------------------------------
1,614,489 (5.8%) ???:mallocx
-----------------------------------------------------------------------
1,448,503 (5.2%) ???:je_arena_ralloc
-----------------------------------------------------------------------
1,191,288 (4.3%) dfa.rs:regex::dfa::Fsm::cached_state
-----------------------------------------------------------------------
910,872 (3.3%) sip.rs:_..std..collections..hash..map..DefaultHasher..as..core..hash..Hasher..::write
-----------------------------------------------------------------------
720,003 (2.6%) exec.rs:regex::exec::ExecNoSync::many_matches_at
-----------------------------------------------------------------------
709,978 (2.5%) slice.rs:regex::exec::ExecNoSync::many_matches_at
-----------------------------------------------------------------------
500,400 (1.8%) sip.rs:_..std..collections..hash..map..DefaultHasher..as..core..hash..Hasher..::finish
-----------------------------------------------------------------------
400,118 (1.4%) map.rs:_..std..collections..hash..map..HashMap..K$C$..V$C$..S....::get
-----------------------------------------------------------------------
380,317 (1.4%) raw_vec.rs:_..alloc..raw_vec..RawVec..T....::double
-----------------------------------------------------------------------
360,001 (1.3%) re_set.rs:regex::re_set::unicode::RegexSet::matches
-----------------------------------------------------------------------
290,222 (1.0%) sparse.rs:regex::dfa::Fsm::next_state
-----------------------------------------------------------------------
260,126 (0.9%) vec.rs:regex::dfa::Fsm::next_state
-----------------------------------------------------------------------
239,994 (0.9%) vec.rs:regex::exec::ExecNoSync::many_matches_at
-----------------------------------------------------------------------
210,215 (0.8%) slice.rs:regex::dfa::Fsm::next_state
-----------------------------------------------------------------------
200,042 (0.7%) table.rs:_..std..collections..hash..map..HashMap..K$C$..V$C$..S....::get
-----------------------------------------------------------------------

I'm not sure how helpful this really is. I can play with it a bit more if so.

[BurntSushi]

That is certainly interesting. The fact that matches has entries for things like next_state and cached_state but is_match doesn't is surprising. I'll have to investigate when I get the chance.

[kevincox]

This would be useful for me as well. I can imagine a number of use cases that require taking only the first match. For example URL routers in web frameworks often use regexes for flexibility and they want to provide a sequential match semantics. In this case only the first match is required. (Although you can imagine a warning in development if a URL would have had multiple matches).

[BurntSushi]

While this may not be available on RegexSet in the immediate future, you will be able to do this with regex-automata 0.3 once it's out. It will expose complete support for multi-regex APIs, including even asking for capture groups (in the non-overlapping case anyway).