Regex compilation cache

[mscharley]

Hi, looks like discussions aren't enabled for this repo so I'm opening an issue for this.

I recently added library-side compilation caching for regexes and wanted to report back the improvements because they were stark.

On JavaScript (node specifically) it seems like the runtime does this already, there was no improvement.

On Erlang however, there is a ~45% improvement in the overall benchmark speed for the whole parsing algorithm (2.44ms -> ~1.31ms on my hardware) despite regex compilation being a tiny proportion of the overall code and not even on a particularly hot path (only used for parsing blocks, not inline elements).

Given that it is impossible to fully solve on the application side using only Gleam since Gleam doesn't support creating consts with a Regex, it feels like there would be a lot of benefit to adding compilation caching at the stdlib level, perhaps via ets? I'm happy to take a look at adding this, I just wanted to confirm that this is a good idea or if there's perhaps a better way to tackle the problem.

[lpil]

How would this be implemented?

[mscharley]

High level my idea was that gleam/regex.from_string is already implemented as an external and so it shouldn't be too hard to add some kind of global cache on the FFI side to implement a global(ish) cache. Since regex are deterministic based on the string definition and regex implementation in the runtime, caching based on the input string as a cache key seems reasonable and not a breaking change.

On node this seems to be happening already, but if we want to do it there anyway to protect against potential implementation behaviour in JS runtimes we could very easily use a Map or even just a basic object as a cache keyed off the input string.

More relevant though would be Erlang, and this is where I was hoping you might have some input. I'm far less familiar with Erlang having only started looking into it at all as a necessity for dealing with some edge cases in Gleam so I've really not done any Erlang code at all yet. Looking into this issue I found out first hand why it seems you can't do the regex.Regex constants in Gleam, namely that Erlang doesn't seem to have module level constants in the same way that Gleam supports (at the language level) or JavaScript does and the Gleam compiler just inlines it's constants into Erlang code.

Given all the above, and some cursory searching through the Erlang documentation I think it should be possible to implement using an ETS table as the cache mechanism, again keyed by the regex string. This would get us per-process caching at least, which while not universally applicable should at least help. I haven't tried implementing a proof of concept yet though, I was reaching out in part to get some input on feasibility of options from someone who knew Erlang a bit more than "copied and pasted some gleam-generated erlang code and called it FFI".

[mscharley]

Never mind me, I just looked into ETS more deeply and I could have sworn that you could fetch a table by name but I must have been imagining things because I can't see anything like that which would mean you'd need to keep a reference to the table around somewhere which brings us back to the same root problem.

[dvic]

Never mind me, I just looked into ETS more deeply and I could have sworn that you could fetch a table by name but I must have been imagining things because I can't see anything like that which would mean you'd need to keep a reference to the table around somewhere which brings us back to the same root problem.

Yes you can, you give it a name and pass in the named named_table option: https://www.erlang.org/doc/apps/stdlib/ets.html#new/2

[apainintheneck]

I wonder if persistent_term would make more sense here than ETS if we expect compiled regexes to remain unchanged for the lifetime of the program. That's what @lpil pointed me to when I asked about something similar a while ago (#3182).

In terms of the API, I think that having a separate method for cached regexes makes more sense here instead of caching all of them by default. There are times where it might not make sense to cache some regexes for the lifetime of the program.

[mscharley]

@apainintheneck thanks for the heads up, that does look like an interesting option. An opt-in version using that might be a good fallback, but from an API design perspective I think a transparent cache that just does the right thing is still the ideal design. I have some ideas to address Louis's feedback on my PR that I want to try out first. To their first point, your proposal can still lead to a memory leak if people use dynamically generated regex strings with the opt-in cache. We can document that you shouldn't do that, but an API design which you can't use wrong is superior and one that will automatically improve a bunch of already written code is even better.

[lpil]

Given this is the standard library banning dynamically created regex is not an option.

[mscharley]

Yeah, definitely. The two options being discussed were the transparent cache style like what I put into the PR, or an optional second way to compile a regex (eg. regex.from_string_cached) which would cache any input and hence not be recommended to use with a dynamically created regex due to the memory leak issue. I don't think anyone's suggesting just wholesale disallowing dynamically created regexes.

[lpil]

Seeing as we don't have a good regex specific solution I think this may be more suited to being in another library; especially since the current approaches involve adding the concept of mutation to the standard library, something which Gleam deliberately avoids.

[mscharley]

adding the concept of mutation to the standard library, something which Gleam deliberately avoids

This is part of why I thought the stdlib might be a good place for this. If we can provide an immutable-looking API for an implementation that requires mutability internally (for the cache) then it prevents pushing that concern down to user code and we can keep pushing Gleam as an immutable language more easily.

The other reason I was considering the stdlib was discoverability. Specifically, if it's in the stdlib then the JS and Erlang targets become more consistent in that neither need app-level caching of regexes unless they are very performance sensitive. If it's a library, then users need to be aware it's something that they should be worried about, and then go looking for a solution.

That said, I'm happy to move this off to a library if you think that's best.

[lpil]

If you have an idea for an immutable looking API maybe that would make it more appropriate. What might that look like?

[mscharley]

The current PR doesn't require any changes to the API interface at all.

This solution might be a bit heavy for the stdlib, but the thoughts I had for addressing your concerns on that PR were basically:

There's a race condition with the creation of the table which can case the code to crash if two processes attempt to cache a regex at the same time.

Just handle the exception, if it's already been created on another process, then proceed as normal.

If the process that first creates the ETS table shuts down the table is dropped, resulting in the cache being lost.

To prevent the ETS from disappearing, start a new process to own the ETS. This would have very little in the handler, but not nothing because...

The ETS table is never garbage cleaned up, so dynamically generating regexes results in a memory leak as they are caches forever.

If we have our own process managing the ETS table, then we can send a message there whenever something is fetched or inserted. Importantly, it wouldn't use the message to do the fetch or insert for performance reasons, but it would send a notification to the process. The process can use these notifications to update a last used timestamp for each entry on fetch, and trim the oldest entries on insert to keep the table to a fixed size.

I definitely understand if this proposal is a bit heavy for the stdlib though.

[lpil]

That would result in the cache process being unsupervised and unlinked, and it would have to do work every time a regex is used by any other process in the system. Would it be able to keep up in regex heavy systems?

The programmer would need to be able to opt-out of the cache on a per-regex basis, would need to be able to fine-tune the expiration to control memory usage of the cache, and need to be able to flush the cache.

Given these and the fact the API is clearly built around implicit global mutable state, something we have deliberately avoided in Gleam, I don't find this design very compelling.

[mscharley]

Would it be able to keep up in regex heavy systems?

I don't have the experience with Erlang to answer that well, but I suspect the answer is "yes, unless you are using dynamic regex strings extensively" since the major work would only happen on insertion of a new item into the cache. The fetch update could be handled inline in the function rather than being posted over to the cache process - it would really only be one extra call to ets:insert to update the item in the table after it is fetched. The table elements I was considering using was just { ReString, Timestamp, Re }, so after fetching from the cache you could just push it back into the cache with an updated timestamp pretty easily and if two different processes were fetching at the same time and tried to update at the same time it wouldn't really matter too much which won out.

Out of curiosity, why would you ever want or need to flush the cache entirely? Keeping memory usage under control I understand, but regex are deterministic. Flushing the cache would only ever result in recomputing the exact same thing you've already computed. Ditto for expiration, I'd expect people would want to perhaps control a maximum amount of memory to use, but not care enough to expire individual regexes more or less quickly. Given the deterministic nature of regex compilation I was planning on treating this as a most-recently-used cache, ie. keep the n most recently used items whenever it's evaluated for trimming, rather than as a time-based cache.

Per regex opt-out would require a new option in the regex options at least, I'm not sure if you'd consider exposing the fact there is a cache to opted out of to be breaking the immutable style or not. It's borderline for me personally.

That would result in the cache process being unsupervised and unlinked

Unsupervised doesn't feel like a big issue here, we could restart that process with a fresh blank cache if it's not existing when we try to use it? I feel like that's a surmountable issue since the first thing any compilation would need to do is check the ETS table exists, and by proxy if the process exists. I don't have the Erlang experience to know how bad an issue an unlinked process would be though.

---

Honestly, I don't love the design either - this is getting further and further from the simple option I was hoping we could use. I've been writing too much JavaScript for too long and forgotten a lot of the complexities that actually parallel code needs to deal with, and the lack of module-level values in Erlang doesn't make things any easier. I'm definitely very open to other ideas or approaches.

But I can't shake the feeling that some kind of solution is needed, even if it a library. I expected regex compilation to be a performance hit, but I didn't expect 10 lines of code to be ~50% of the runtime of an algorithm that is a couple thousands of lines long and that barely calls those 10 lines of code. Adding to this the difficulty of actually deduplicating the regex compilation calls inside Gleam code, for all the same reasons it's hard in Erlang, this adds up to a difficult problem to solve.

The solution I linked in my original message is contained entirely inside the library and prevents recompiling the regexes for each commonmark document that it parses, but in order to completely remove the overhead I'd have to push that new ParserRegexes type out as a public opaque type (with a better name) and then get users of the library to call something like:

let parser = commonmark.new_parser()
commonmark.parse(parser, document_string)

And then ask them to hold onto that parser and reuse it if they're parsing multiple documents. It's not an untenable option, but it complicates the APIs that people can write with Gleam if they need to use regexes and they care at all about the performance of their code.

[apainintheneck]

@mscharley If this is out of the scope of the standard library, another option would be to use a library like glemo to memoize regexes globally throughout the program and that would work cross-platform too. I also initially considered creating a persistent regex library when I first ran into this but as I wasn't working on anything that used a bunch of regexes so I lost interest. It doesn't surprise me that you've run into this problem with the markdown parser you're working on though.

[mscharley]

@apainintheneck Unfortunately, it looks like glemo only has a JS implementation for now, which is a shame. If you haven't seen it already, gleam-lang/stdlib#656 does have a basic implementation of an ETS cache for regexes, but Louis rightly pointed out a few different shortcomings with that option in the comments on the PR which is what I was trying to address in my last wall of text. This does very much feel like it's getting above the scope of the stdlib, and i know Louis has expressed some reservations about having regex in the stdlib at all in the past. It could well be this should all be it's own separate dedicated thing.

[apainintheneck]

@apainintheneck Unfortunately, it looks like glemo only has a JS implementation for now, which is a shame.

It uses ETS tables on Erlang by way of the carpenter library. I'm not sure if the implementation runs into the same problems discussed in your PR though.

[lpil]

Creation of a timestamp is not necessarily that cheap, which is why BEAM web servers use a cache for that rather than computing it per request.

Here a single process would be doing this work and competing with many thousands of other processes, while also performing the GC scanning work. I don't feel as confident that the single process won't have performance problems.

Flushing and configuring the cache are requirements in order to give the programmer full control of memory usage. The standard library cannot make assumptions about what the resource constraints of Gleam programs might be.

[mscharley]

It uses ETS tables on Erlang by way of the carpenter library. I'm not sure if the implementation runs into the same problems discussed in your PR though.

Yep, Glemo is basically a slightly more generalised version of what I wrote.

Re @lpil 's feedback, that's all fair enough I guess. If timestamps aren't cheap then any other increasing value over time, even a counter would suffice - all that really matters for the algorithm is relative ordering, not specific differences.

Anyway, I think the takeaway from all this is that this is a very hard problem to solve in a generic way and a relatively simple problem to solve in the specific case. If you know which regexes you need to cache then you can throw them all in a single persistent_term tuple and call it a day. I was hesitant to try using persistent_term as a caching option in the stdlib though because of some of the GC implications that module has if you're constantly using write operations.

The Erlang re module includes the following warning:

Compiling the regular expression before matching is useful if the same expression is to be used in matching against multiple subjects during the lifetime of the program. Compiling once and executing many times is far more efficient than compiling each time one wants to match.

But the Gleam stdlib documentation doesn't include anything. Would you be fine with either reproducing this warning or something akin to it Louis? If nothing else, I think that documenting regex compilation as being slow will help. Of particular note is the second sentence. The Gleam stdlib forces you to compile your regex, but the Gleam language doesn't encourage you to reuse it because storing it isn't simple so I suspect that a lot of people will just use regex.from_string in a let assert statement and recompile on every function call. That's definitely where I started at least because looking at the documentation I had a vague sense that compiling a regex must be a fairly complicated thing to do, but I honestly haven't had to think about it in other languages before, and when I have thought about it I've had tools like module level constants or simple global state to easily calculate things once and store them for reuse.

[lpil]

Adding more documentation sounds good!

It's worth nothing that regex compilation is not slow, it's that it's needless work. Few languages have compile time regular expressions so most people know you should not use them in a loop, so it slipped my mind to document this.

It would also be good to look at other designs for this that do not have the problems of this cache dictionary design.

[apainintheneck]

I think it's maybe not always obvious when you're used to a language like JavaScript or Ruby where regex literals exist and those get cached automatically even inside a loop. That being said benchmarking should make it obvious.

[apainintheneck]

I played around with the idea of creating a library for caching regexes globally and my findings matched what @mscharley already posted above.

Basically, there seems to be no clear benefit to caching regexes in JavaScript when using Node.js 22.4.0. It seems like the V8 JavaScript runtime already does that internally. Erlang 27.0 ended up being almost an order of magnitude faster when caching regexes using persistent term internally though which lines up with what we've seen here.

I'm not sure having a library which writes to persistent term is a good API though because it could behave unexpectedly if users try to save large numbers of regexes. It is also heavily dependent on assumptions about the current target implementations which might not hold true over time. It was fun to look at it though out of an abundance of curiosity.

• Repo: https://github.com/apainintheneck/persistent_regex

[mscharley]

I saw a measurable but negligible benefit to caching regexes in JS (~1%) but it was definitely far more pronounced in Erlang (~45%).

I'm still not against the idea of a library if someone could work out some of the consistency issues but I think the real immediate answer is just some articles explaining how to do the equivalent of module level constants in Erlang (ie, something based around persistent_term) and that there are some kinds of deterministic calculations, like compiling regexes, which are useful to precalculate and store that way which, unfortunately, today requires FFI to implement.

Ultimately, I think module level constants that aren't just compile-time constant like we have today would be a really useful language feature. It might be a bit more complicated to compile on Erlang though. It might just end up being a library long term. I had a quick look at your persistent_regex library and I think a slightly more generic version would be really useful - something like:

fn persist(name: String, generator: fn () -> a) -> a

This could be implemented using a Map in Javascript, but use persistent_term in Erlang. Ideally, you wouldn't want to have more than a handful of individual terms per library using it, and this signature would let you easily group up all the calculations into one place like I ended up doing in the CommonMark library.

[apainintheneck]

I agree that an article that touches on how to use persistent_term would be useful for those of us that aren't as familiar with Erlang. It certainly wasn't obvious to me coming from other languages that don't run on the Beam VM that this would be a decent way to mimic runtime caching.

The idea for a more generic interface is cool too and would make for a nice library. I don't think anything similar exists right now in the Gleam ecosystem beyond glemo which doesn't quite do the same thing.

[mscharley]

Have a look at https://github.com/mscharley/alpaca and let me know what you think.

Or if you're on discord, there's a thread there too: https://discord.com/channels/768594524158427167/1260854247709478972/1260854247709478972