3 ms·

I've written a linear-time regex matcher in 65 lines of code: https://jasonhpriestley.com/regex https://jasonhpriestley.com/regex

by jhp123 3y ago

vidarh 3y ago
That's beautiful. And I think a great illustration of how much more impactful the "next n lines" or so are going to be than the "last n lines" EDIT: Also, the impact is even greater when looking at your performance improvements with the dfa conversion as well: https://jasonhpriestley.com/regex-dfa https://jasonhpriestley.com/regex-dfa
saberience 3y ago
What features does it support? What if I pass in a complex regexp with data several GB in size? There is a large difference between toy examples and hardened enterprise ready code.
- vidarh 3y ago
  The features are less important than the linear complexity. It lowers to an NFA. An NFA can recognise any linear language, so adding more features affects the generation of the NFA, while increasing the performance involves faster matching against the NFA. In this case he's done a followup with benchmarks where he's converting the NFA to a DFA ajd comparing favourably against both Node and your browers regexp engine with only a tiny little bit extra code: https://jasonhpriestley.com/regex-dfa https://jasonhpriestley.com/regex-dfa That doesn't mean there isn't value to the rest of those 20k lines of code I referenced - that was not the point. A lot of them adds a bunch of convenience, like a more expressive syntax that saves you from writing more convoluted regexps, and it presumably bought more performance than their previous, smaller iteration, every step up from a much smaller engine way back. I'm sure one could do better with less, but I'm also not dismissing that I'm sure each step was reasonable given the constraints. But that too is also not the point. It was not about dismissing the size of the Ruby regexp engine as not worth it. The point was that there is a very significant and rapid diminishing return, and that this explains why you can do so seemingly much with so very little, because the leap from no capability to something usable takes very little, but each subsequent increment will tend to buy you less, for more work. That doesn't mean people should stop putting in that extra work and squeeze out a bit more. It just gives an answer to the question in the link.
  - nine_k 3y ago
    Being O(n) is important, but the size of the constant factor is important, too. E.g. the theoretically most efficient known matrix multiplication algorithm only outperforms the less efficient common algorithms at ludicrous matrix sizes, because of the huge constant factor.
    - vidarh 3y ago
      Yes, but this is again totally besides the point, and addressed by the second link to the version that does dfa conversion in a few dozen more lines and is competitive with the regexp implementation in chrome.
hinkley 3y ago
I think this is a good base case for exploring how achieving feature parity affects the code.

I've written a linear-time regex matcher in 65 lines of code: https://jasonhpriestley.com/regex https://jasonhpriestley.com/regex

by jhp123 3y ago

I've written a linear-time regex matcher in 65 lines of code: https://jasonhpriestley.com/regex https://jasonhpriestley.com/regex

vidarh 3y ago

That's beautiful. And I think a great illustration of how much more impactful the "next n lines" or so are going to be than the "last n lines" EDIT: Also, the impact is even greater when looking at your performance improvements with the dfa conversion as well: https://jasonhpriestley.com/regex-dfa https://jasonhpriestley.com/regex-dfa

saberience 3y ago

What features does it support? What if I pass in a complex regexp with data several GB in size? There is a large difference between toy examples and hardened enterprise ready code.

vidarh 3y ago
The features are less important than the linear complexity. It lowers to an NFA. An NFA can recognise any linear language, so adding more features affects the generation of the NFA, while increasing the performance involves faster matching against the NFA. In this case he's done a followup with benchmarks where he's converting the NFA to a DFA ajd comparing favourably against both Node and your browers regexp engine with only a tiny little bit extra code: https://jasonhpriestley.com/regex-dfa https://jasonhpriestley.com/regex-dfa That doesn't mean there isn't value to the rest of those 20k lines of code I referenced - that was not the point. A lot of them adds a bunch of convenience, like a more expressive syntax that saves you from writing more convoluted regexps, and it presumably bought more performance than their previous, smaller iteration, every step up from a much smaller engine way back. I'm sure one could do better with less, but I'm also not dismissing that I'm sure each step was reasonable given the constraints. But that too is also not the point. It was not about dismissing the size of the Ruby regexp engine as not worth it. The point was that there is a very significant and rapid diminishing return, and that this explains why you can do so seemingly much with so very little, because the leap from no capability to something usable takes very little, but each subsequent increment will tend to buy you less, for more work. That doesn't mean people should stop putting in that extra work and squeeze out a bit more. It just gives an answer to the question in the link.
- nine_k 3y ago
  Being O(n) is important, but the size of the constant factor is important, too. E.g. the theoretically most efficient known matrix multiplication algorithm only outperforms the less efficient common algorithms at ludicrous matrix sizes, because of the huge constant factor.
  - vidarh 3y ago
    Yes, but this is again totally besides the point, and addressed by the second link to the version that does dfa conversion in a few dozen more lines and is competitive with the regexp implementation in chrome.

hinkley 3y ago

I think this is a good base case for exploring how achieving feature parity affects the code.