3 ms·

> A fun experience 12 years ago was implementing Thompson NFA from the original 1960s paper into C# to improve a NLP lab's regex processing speed. Speed up was

> A fun experience 12 years ago was implementing Thompson NFA from the original 1960s paper into C# to improve a NLP lab's regex processing speed. Speed up was crazy, like 1200 times versus the custom bespoke matching method they had been using until then. I don’t quite understand, were they not using regexes, or were they using regexes which triggered classic NFA misbehaviours in .net’s regex engine which thompson’s was safe from (and they didn’t use advanced features)?

keepamovin 3y ago
Oh, I understand what you're saying. No they weren't using native .net regexes. As an aside, I'm not sure the specifics of the .net regex engine at the time, but you seem to be suggesting that it used an NFA. I suspect it might not have but I don't know. Certainly a few languages didn't use NFAs, yet others did indeed! :) To your point: it was many years ago so perhaps I will get some details wrong in what follows. I apologize in advance for the fuzziness! The most clear thing in my memory was the beauty of Thompson's work and how much using it sped things up. Anyway, their system had a custom pattern matching algorithm specific to a couple NLP domains and conceptual models they were working in, that was like regex but extended. It was an academic invention, sophisticated and ambitious, and IIRC, they hadn't fully implemented all their ideas. Turned out their implementation just wasn't particularly efficient. IIRC, it was a recursive implementation, but it's so many years I can't recall really, especially as I was mainly focused on making it faster. This necessitated replacing much of their code, but luckily the implementation and ideas were clean enough that the replacement was almost as if a clean interface had been planned all along, IIRC. Turns out it could be sped up mightily by replacing a lot of their implementation with Thompson NFA and then adding their custom weird stuff on top of that. I tried to push the NFA as far as it could to utilize its own concepts to implement their ideas, but some things simply couldn't fit, so had to be bolted on. Still, it was far more efficient. That's what it was. As another aside: I think it was Russ Cox's article online about Thompson NFA that I found and which led me down that path. IIRC, he has this super simple HTML page with maybe a powder blue background telling all about it. His article was also a great help in clearly understanding the concept. It was fun to go back and forth between article, paper and code to get it to work!
- vidarh 3y ago
  No powder blue background so maybe it's a different page or has been redesigned, but Cox has a page linking to several articles on regexps here [1]. [1] https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/
  - keepamovin 3y ago
    That's the page! Man it was 12 years, could be my memory :) https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html It might have had a more "retro geocities" type design in the past, tho haha
    - burntsushi 3y ago
      This is exactly what was linked and discussed in my OP. ;-)
      - keepamovin 3y ago
        Yeah, very good overview, no?

keepamovin 3y ago

Oh, I understand what you're saying. No they weren't using native .net regexes. As an aside, I'm not sure the specifics of the .net regex engine at the time, but you seem to be suggesting that it used an NFA. I suspect it might not have but I don't know. Certainly a few languages didn't use NFAs, yet others did indeed! :) To your point: it was many years ago so perhaps I will get some details wrong in what follows. I apologize in advance for the fuzziness! The most clear thing in my memory was the beauty of Thompson's work and how much using it sped things up. Anyway, their system had a custom pattern matching algorithm specific to a couple NLP domains and conceptual models they were working in, that was like regex but extended. It was an academic invention, sophisticated and ambitious, and IIRC, they hadn't fully implemented all their ideas. Turned out their implementation just wasn't particularly efficient. IIRC, it was a recursive implementation, but it's so many years I can't recall really, especially as I was mainly focused on making it faster. This necessitated replacing much of their code, but luckily the implementation and ideas were clean enough that the replacement was almost as if a clean interface had been planned all along, IIRC. Turns out it could be sped up mightily by replacing a lot of their implementation with Thompson NFA and then adding their custom weird stuff on top of that. I tried to push the NFA as far as it could to utilize its own concepts to implement their ideas, but some things simply couldn't fit, so had to be bolted on. Still, it was far more efficient. That's what it was. As another aside: I think it was Russ Cox's article online about Thompson NFA that I found and which led me down that path. IIRC, he has this super simple HTML page with maybe a powder blue background telling all about it. His article was also a great help in clearly understanding the concept. It was fun to go back and forth between article, paper and code to get it to work!

vidarh 3y ago
No powder blue background so maybe it's a different page or has been redesigned, but Cox has a page linking to several articles on regexps here [1]. [1] https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/
- keepamovin 3y ago
  That's the page! Man it was 12 years, could be my memory :) https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html It might have had a more "retro geocities" type design in the past, tho haha
  - burntsushi 3y ago
    This is exactly what was linked and discussed in my OP. ;-)
    - keepamovin 3y ago
      Yeah, very good overview, no?