8 ms·
RE#: how we built the fastest regex engine in F#
- sourcegrift 7mo agoI've had nothing but great experience with F#. If it wasn't associated with Microsoft, it'd be more popular than haskell
- raincole 7mo agoI think if it weren't a 'first class' member of .NET ecosystem[0], no one would know F#. After all Haskell and Ocaml already exist. [0]: my very charitable take, as MS obviously cares C# much much more than F#.
- deleted 7mo ago[deleted]
- pjmlp 7mo agoManagement has always behaved as if they repent having added F# to VS 2010, at least it hasn't yet suffered the same stagnation as VB, even C++/CLI was updated to C++20 (minus modules). In any case, those of us that don't have issues with .NET, or Java (also cool to hate these days), get to play with F# and Scala, and feel no need to be amazed with Rust's type system inherited from ML languages. It is yet another "Rust but with GC" that every couple of months pops up in some forums.
- deleted 7mo ago[deleted]
- Copyrightest 7mo ago[dead]
- lynx97 7mo agoYou realize that Microsoft Research employed Simon for many many years?
- deleted 7mo ago[deleted]
- dude250711 7mo ago> ...it'd be more popular than haskell https://steve-yegge.blogspot.com/2010/12/haskell-researchers-announce-discovery.html https://steve-yegge.blogspot.com/2010/12/haskell-researchers...
- sourcegrift 7mo ago> But they all just skip the press releases and go straight to the not using it part Lol
- brabel 7mo agoDid they ever get the full extra person who gives a shit?
- anentropic 7mo agoFantastic stuff! FYI some code snippets are unreadable in 'light mode' ("what substrings does the regex (a|ab)+ match in the following input?")
- ieviev 7mo agoah thank you for letting me know, fixed it now!
- sourcegrift 7mo ago[flagged]
- balakk 7mo agoFinally, an article about humans programming some computers. Thank you!
- gbacon 7mo agoThat’s beautiful work. Check out other examples in the interactive web app: https://ieviev.github.io/resharp-webapp/ https://ieviev.github.io/resharp-webapp/ Back in the Usenet days, questions came up all the time about matching substrings that do not contain whatever. It’s technically possible without an explicit NOT operator because regular languages are closed under complement — along with union, intersection, Kleene star, etc. — but a bear to get right by hand for even simple cases. Unbounded lookarounds without performance penalty at search time are an exciting feature too.
- ngruhn 7mo agoI built a similar library in TypeScript (also based on regex derivatives). You can really built cool tools with complement / intersection. E.g. 1) regex equivalence checker (check if intersection of complements is empty): https://gruhn.github.io/regex-utils/equiv-checker.html https://gruhn.github.io/regex-utils/equiv-checker.html 2) password generator from regex constraints (16+ chars, at least on upper case char, etc). Just take the intersection of all constraints and generate random matches from that: https://gruhn.github.io/regex-utils/password-generator.html https://gruhn.github.io/regex-utils/password-generator.html
- gbacon 7mo agoThat’s really slick! I’m glad someone paid attention in automata theory.
- agnishom 7mo agoThe author mentions that they found Mamouras et al. (POPL 2024), but not the associated implementation. While the Rust implementation is not public, a Haskell implementation can be found here: https://github.com/Agnishom/lregex https://github.com/Agnishom/lregex
- andriamanitra 7mo agoThis is very interesting. I'm a bit skeptical about the benchmarks / performance claims because they seem almost too good to be true but even just the extended operators alone are a nice improvement over existing regex engines. The post mentions they also have a native library implemented in Rust without dependencies but I couldn't find a link to it. Is that available somewhere? I would love to try it out in some of my projects but I don't use .NET so the NuGET package is of no use to me.
- ieviev 7mo agoThere's currently only a string solver with the same core library, but not a full regex engine https://github.com/ieviev/cav25-resharp-smt https://github.com/ieviev/cav25-resharp-smt I will open source the rust engine soon as well, some time this month. As for the benchmarks, it's the fastest for large patterns and lookarounds, where leftmost-longest lets you get away with less memory usage so we don't need to transition from DFA to NFA. In the github readme benchmarks it's faster than the exponential implementations of .NET Compiled so the 35 000x can be an arbitrary multiplier, you can keep adding alternatives and make it 1000000x. for a small set of string literals it will definitely lose to Hyperscan and Rust regex since they have a high effort left-to-right SIMD algorithm that we cannot easily use.
- feldrim 7mo agoWould SearchValues<char> help there for a fallback to a SIMD optimized simple string literal search rather than the happy path?
- ieviev 7mo agoYes, that's exactly what we did to be competitive in the benchmarks. There's a lot of simple cases where you don't really need a regex engine at all. integrating SearchValues as a multi-string prefix search is a bit harder since it doesn't expose which branch matched so we would be taking unnecessary steps. Also .NET implementation of Hyperscan's Teddy algorithm only goes left to right.. if it went right to left it would make RE# much faster for these cases.
- noelwelsh 7mo agoI love regular expression derivatives. One neat thing about regular expression derivatives is they are continuation-passing style for regular expressions. The derivative is "what to do next" after seeing a character, which is the continuation of the re. It's a nice conceptual connection if you're into programming language theory. Low-key hate the lack of capitalization on the blog, which made me stumble over every sentence start. Great blog post a bit marred by unnecessary divergence from standard written English.
- u_sama 7mo agoin what is it different ?
- murkt 7mo agoStarts of sentences are not capitalized, which makes it a bit harder to read. English language prescribes capitalization after a period.
- spankalee 7mo agoIt's so uncomfortable to read. Why do people do this? They capitalize names, so clearly their shift key works. Do they do it feel special or like some sort of rebel?
- trashface 7mo agoMaybe they drafted it on a phone where capitalization is harder. My guess is the all-lowercase world is mostly people who do most of their text creation on phones and similar, not keyboards.
- layer8 7mo agoI don’t really see how capitalization is harder on phones, I do it all the time.
- 7mo ago
- meindnoch 7mo ago@burnsushi is that true?
- keybored 7mo agoTentative doubt until/if he confirms. (but specifically in F# though. Edit: No, comparisons to Rust etc. are made in TFA)
- masfuerte 7mo agoThis is very impressive. > how does RE# find the leftmost-longest match efficiently? remember the bidirectional scanning we mentioned earlier - run the DFA right to left to find all possible match starts, then run a reversed DFA left to right to find the ends. the leftmost start paired with the rightmost end gives you leftmost-longest. two linear DFA scans, no backtracking, no ambiguity. I'm pretty sure that should say "the leftmost start paired with the leftmost end". This also implies that the algorithm has to scan the entire input to find the first match, and the article goes on to confirm this. So the algorithm is a poor choice if you just want the first match in a very long text. But if you want all matches it is very good.
- mananaysiempre 7mo ago> I'm pretty sure that should say "the leftmost start paired with the leftmost end". I’m pretty sure it shouldn’t, that would give you the leftmost shortest match instead of leftmost longest.
- masfuerte 7mo agoAs originally written, doesn't it go from the start of the first match to the end of the last match? I feel like I'm missing something.
- ieviev 7mo agoIt goes from start of the first match to the longest "alive" end, in practice it will go to a dead state and return after finding the match end. there's an implicit `.*` in front of the first pass but i felt it would've been a long tangent so i didn't want to get into it. so given input 'aabbcc' and pattern `b+`, first reverse pass (using `.*b+`) marks 'aa|b|bcc'<- the forward pass starts from the first match: 'aa->b|b|cc' marking 2 ends then enters a dead state after the first 'c' and returns the longest end: aa|bb|cc i hope this explains it better
- masfuerte 7mo ago
- FrustratedMonky 7mo agoF# is one of the biggest 'What could have beens'. Great language, that just didn't hit the right time, or reach critical mass of the gestalt of the community.
- nbevans 7mo agoIt uses far less tokens than C#, so watch this space...
- nodra 7mo agoCare to explain? Pattern matching, type inference, etc.?
- balakk 7mo agoIt's all about the goddamned machines.. since F# is terse, they figure agent-generated F# code is cheaper.
- KurtMueller 7mo agoI like to think of F# as concise.
- Nelkins 7mo agoVarious investigations have found it to be one of the most token efficient statically typed programming languages https://martinalderson.com/posts/which-programming-languages-are-most-token-efficient/ https://martinalderson.com/posts/which-programming-languages...
- delta_p_delta_x 7mo agoMl-family languages (and frankly, all natively functional languages) are just incredibly terse and information-dense second only to stuff like APL. And yet when written idiomatically and with good object and type naming they are surprisingly readable and writeable. 'Twas a bad idea to train LLMs on the corpus of leaky, verbose C and C++ first instead of on these strict, strongly-typed, highly structural languages.
- feldrim 7mo agoYou got me at TalTech. Great job and the paper is high quality. I'll have to learn F# but I believe it is worth it.
- mananaysiempre 7mo agoWorth mentioning (haven’t checked if the paper talks about this) that while the industry mostly forgot about derivatives and extended REs (i.e. REs with intersection and negation), academia did not. Unfortunately, there have been some pretty discouraging results: the DFA for an extended RE (including a lazy DFA implemented using derivatives, as here) is worst-case doubly exponential in the length of the expression[1], not just exponential as for normal REs. So there is a potential reason not to support intersections in one’s RE matcher, even if they are enticingly easy to implement in terms of derivatives (and even if I personally like to see experimentation in this direction). [1] https://www.sciencedirect.com/science/article/pii/S0304397510002537 https://www.sciencedirect.com/science/article/pii/S030439751...
- someplaceguy 7mo ago> the DFA for an extended RE (including a lazy DFA implemented using derivatives, as here) is worst-case doubly exponential in the length of the expression The authors seem to claim linear complexity: > the result is RE#, the first general-purpose regex engine to support intersection and complement with linear-time guarantees, and also the overall fastest regex engine on a large set of benchmarks
- ieviev 7mo agoWe refer to this in the paper as well, The standard way to do intersection / complementation of regexes with NFAs requires determinization, which causes a huge blowup, whereas for us this is the cost of a derivative. It is true that we cannot avoid enormous DFA sizes, a simple case would be (.*a.*)&(.*b.*)&(.*c.*)&(.*d.*)... which has 2^4 states and every intersection adds +1 to the exponent. How we get around this in the real world is that we create at most one state per input character, so even if the full DFA size is 1 million, you need an input that is at least 1 million characters long to reach it. The real argument to complexity is how expensive can the cost of taking a lazy derivative get? The first time you use the engine with a unique input and states, it is not linear - the worst case is creating a new state for each character. The second time the same (or similar) input is used these states are already created and it is linear. So as said in the article it is a bit foggy - Lazy DFAs are not linear but appear as such for practical cases
- andix 7mo agoIt should be possible to directly compile this library to native code and use it in any other language. Maybe adding some C-style wrappers will be needed.
- sieep 7mo agoCool stuff. Reminds me of the content you used to see on here all the time before AI took over
- andix 7mo agoI'm sometimes wondering if the AI content here really starts trending organically, or if it is somehow pushed by AI companies. Not necessarily with bots, just posting a few links in a company Slack with the request for everyone to upvote it from their personal account could be enough.
- klibertp 7mo agoIf you claim it's the fastest, how does it compare to one-more-re-nightmare? - https://github.com/telekons/one-more-re-nightmare https://github.com/telekons/one-more-re-nightmare - https://applied-langua.ge/posts/omrn-compiler.html https://applied-langua.ge/posts/omrn-compiler.html OMRN is a regex compiler that leverages Common Lisp's compiler to produce optimized assembly to match the given regex. It's incredibly fast. It does omit some features to achieve that, though.
- mananaysiempre 7mo agoAs a potential user (not the author), what jumps out at me about the two is: OMRN: No lookaround, eager compilation, can output first match RE#: No submatches, lazy compilation, must accumulate all matches Both lookaround and submatch extraction are hard problems, but for practical purposes the lack of lazy compilation feels like it would be the most consequential, as it essentially disqualifies the engine from potentially adversarial REs (or I guess not with the state limit, but then it’s questionable if it actually counts as a full RE engine in such an application).
- nanoxide 7mo agoCalling this RE# (resharp), when there is a much more popular and established product already named R# (ReSharper, by JetBrains) in the. NET world will probably hurting your SEO and/or could potentially cause some legal grief.
- systems 7mo agoI am a bit worried about the state of F# thought, Don Syme seem to no longer be acting as the project lead, and I didn't hear of any successor Compared to most actively developed languages F# look very stale currently
- phillipcarter 7mo agoDon has always been the language design BDFL, but has ensured it was community driven since at least 2012. In all practicality the team at Microsoft has always been the main drivers of the F# project. It comes with the territory when you’re the primary group maintaining the compiler, core library, SDK, FSI, and Editor integrations.
- cognisent 7mo agoOne thing I don't understand is what does _* mean? It seems like the paper refers to .* (which I understand) and _* (which I don't) in sometimes the same context? Normally _* would mean "an underscore zero or more times".
- shmolyneaux 7mo agoThat's noted further down the page: - `_*` = any string
- dejongh 7mo agoCool article. I wonder why they decided to start sentences with lower case? Free association!?