3 ms·

It is a very good blog post. Recommended! Now, I will do my obligatory "burntsushi needs to clag the rest of the Teddy code" post which I must do on every disc

It is a very good blog post. Recommended! Now, I will do my obligatory "burntsushi needs to clag the rest of the Teddy code" post which I must do on every discussion of ripgrep. :-) The "subtitles_alternate_casei" examples would be a good benchmark - these 48 strings should not overwhelm Teddy as they could be sensibly merged into Teddy's 8 "buckets" (in fact, they could be merged into 5 buckets) using the simple greedy merging strategy in the original Teddy implementation. This would probably be a quite good project for someone who wants to contribute to ripgrep and could likely get some nice performance wins...

burntsushi 8y ago
I agree, this could be a nice project! If anyone wants to work on it, this is the place to start: https://github.com/rust-lang/regex/blob/master/src/literal/teddy_ssse3/imp.rs https://github.com/rust-lang/regex/blob/master/src/literal/t... I'll get to it myself eventually if someone else doesn't, but it will likely be a while.
- glangdale 8y ago
  I've been thinking about a Teddy successor (which I suppose needs to be called "Taft"). Teddy is very much 'of its time' (SSSE3) and there are a lot of new approaches that seem interesting (AVX512 of Skylake generation, VBMI, Sunny Cove's even bigger slate of instructions, ARM NEON, SVE). I also have better ideas about followup confirm than I used to. There are also some prospect to pick a 'fragment' out of the whole string within Teddy or equivalent at a position not strictly at its suffix - this can even be done with ordering preserved if you are careful not to make fragment choices that allow o-o-o matches (only possible if strings overlap). I might do a bit of work on this, but I'm a bit jaded on string matching and regex matching after 13 years.
  - dman 8y ago
    On the other hand, by now you probably have more fixed function hardware in your brain for string/regex matching than any other human alive.
    - glangdale 8y ago
      What an unnerving concept! I think there are many more people with better algorithmic understanding of the problems. I am more of a 'bang on the problem with a stick until it kinda works' type meathead with a few cheesy SIMD tricks up my sleeve. I am hoping to move on, but I admit I do have a "few more ideas" in that area - possibly even slightly less 'meatheaded' than previous outings. Maybe (although everything looks better on paper).

burntsushi 8y ago

I agree, this could be a nice project! If anyone wants to work on it, this is the place to start: https://github.com/rust-lang/regex/blob/master/src/literal/teddy_ssse3/imp.rs https://github.com/rust-lang/regex/blob/master/src/literal/t... I'll get to it myself eventually if someone else doesn't, but it will likely be a while.

glangdale 8y ago
I've been thinking about a Teddy successor (which I suppose needs to be called "Taft"). Teddy is very much 'of its time' (SSSE3) and there are a lot of new approaches that seem interesting (AVX512 of Skylake generation, VBMI, Sunny Cove's even bigger slate of instructions, ARM NEON, SVE). I also have better ideas about followup confirm than I used to. There are also some prospect to pick a 'fragment' out of the whole string within Teddy or equivalent at a position not strictly at its suffix - this can even be done with ordering preserved if you are careful not to make fragment choices that allow o-o-o matches (only possible if strings overlap). I might do a bit of work on this, but I'm a bit jaded on string matching and regex matching after 13 years.
- dman 8y ago
  On the other hand, by now you probably have more fixed function hardware in your brain for string/regex matching than any other human alive.
  - glangdale 8y ago
    What an unnerving concept! I think there are many more people with better algorithmic understanding of the problems. I am more of a 'bang on the problem with a stick until it kinda works' type meathead with a few cheesy SIMD tricks up my sleeve. I am hoping to move on, but I admit I do have a "few more ideas" in that area - possibly even slightly less 'meatheaded' than previous outings. Maybe (although everything looks better on paper).