Go regular expressions vs caching - which is faster in the long run?

I've got a service that somewhere in its internals does a validation on whether something is "allowed" or "not allowed" (to keep it simple), which is based on a regular expression match. In pseudo-code:

func isAllowed(s string) {
  return regex.match(pattern, s)
}

Now, I know that regex is slow, and even though Golang has a slightly dumbed-down flavor of regex to meet its performance SLAs, it's still not going to be the same as an exact string comparison. And I also know that my function is going to be called quite often with repeated values. So, I thought of making a cache:

var cache = make(map[string]bool)

func isAllowed(s string) {
  if result, found := cache
展开收缩
; found {
	return result
  }
  allowed := regex.match(pattern, s) // ignore syntax here; I'm simplifying this as pseudo-code
  cache
展开收缩
 = allowed
  return allowed
}

So now I can avoid the regex operation if the string is already in my cache. But...there are potentially going to be a lot, like thousands or 10,000s of values in this cache. So just to look up values in the cache I might have to do 10,000 string comparisons, rather than a single regex operation.

So, I guess my question is, how much faster is a string comparison than a Go regex match? Is caching going help or hurt my efficiency?

This technique is called memoization.

A [hash]map lookup is O(1) [constant] time. The regular expressions in Go's regexp package are guaranteed to run in O(N) (linear) time, where N is the length of the input (see https://pkg.go.dev/regexp#pkg-overview, and https://swtch.com/~rsc/regexp/regexp1.html for details).

So that means you are trading time for space: TANSTAAFL

As to how much faster a map lookup might be over the regular expression might be, the only way to find out would be to run some benchmarks on something using something representative of your actual input.

Some questions you might want to consider:

• Is the time spent in this authorization function actually significant from a performance perspective?
• How often will you get a cache hit versus a cache miss?
• If this is a long-running service/daemon, is the cache going to grow without limit and ultimately crash your service/daemon?
• Might you want to use a more sophisticated cache where cache entries will expire or get evicted to keep growth within limits?

And finally,

• If you're having to parse bits out of a string for authorization purposes, perhaps a better performance improvement might be to rethink your approach and maintain your authorization rules/flags as some sort of datatype (a structure or bit map) with associated functions for performing authorization tests.

For the record, I ran benchmarks and found that caching improved my performance by two orders of magnitude. So, I think I will pay the price in memory, and pocket the performance gain.