Improve blacklist performance

[talflon]

The text blacklists and watchlists are slower than they need to be, because under the current implementation, every entry is added to a huge regular expression. However, many of the entries are simple strings, or start with simple strings. This opens up the possibility of using map lookups (set, dict, etc.) on these strings to speed up matching. Map lookups are faster than regular expressions in Python, and have better Big-O scaling than regex | alternation.

This is already used for the phone number lists. The easiest places to add this sort of optimization appear to be where we have bookending:

• the keyword watchlist, because it's full of single words, domains and email addresses: 77% of it appears to match [a-z0-9]++(?:[\./@-][a-z0-9]++)*+ after stripping comments
• the username blacklist, because many of its entries are manually anchored to the start and end of the string

For non-bookended matches like the website blacklist, I wonder if there would be any speedup to splitting up the regular expressions into groups, and "switching" on the first few initial characters. All things equal, it's of course fastest to stay in a single call to regex.search(), but all things aren't equal—the methods scale differently.

To accomplish something like this, we would need a little refactoring of how blacklist rules are created and updated in the code. It wouldn't need to change anything user-facing.

[makyen]

While using map lookups may gain some performance, I expect it would not result in as much of a performance gain as you might think. The regex package is written in C and releases the GIL when in operation. SD is tuned to keep all available CPU cores chugging away on separate scanning tasks in order to take advantage of that concurrency. Given that there are, typically, multiple CPU cores available to SD, moving the code into Python only would result in a substantial reduction in concurrency, effectively cutting available CPU capability by about 75% (assuming the 4 CPU cores which Cerberus uses), depending on the exact circumstances and underlying compute instance. This reduction in concurrency will eat significantly into any performance gains. That doesn't mean that there wouldn't be a gain from this approach. However, the portions of what you're wanting to split out are the entries on which the regex package spends the least amount of time, at least individually.

As to splitting the entries into groups (both bookended and non-bookended), I've already tried a couple of versions of that and saw a performance degradation. I still have a couple more ideas about how to implement it which might result in performance improvement. I expect to continue to experiment. Yes, some, now small, amount of refactoring how the blacklist Rules are created and updated is necessary, but much of that has already been done, and, IIRC, pushed back into production, or at least some portions of those changes have been, but there were some more.

[talflon]

@makyen thanks, that makes sense. That changes things.

I had been pleasantly surprised how fast a loop like the following ran over the 3/4 of the watchlist for which it should be sufficient to find all matches: seems like a fraction of a second despite the thousands of entries, but for that fraction of a second there's no real concurrency:

for m_u in regex.finditer(r'[a-z0-9]++(?:[\./@-][a-z0-9]++)*+', text, overlapped=True, flags=regex.I):
    urlish = m_u.group().lower()
    if urlish in urlish_set:
        yield m_u.start(), m_u.end()
    for m_s in regex.finditer(r'[\./@-]', urlish):
        sub_urlish = urlish[:m_s.start()]
        if sub_urlish in urlish_set:
            yield m_u.start() + m_s.start(), m_u.end()

Pushing them into a named list (\L) might keep it more concurrent? With my insufficient testing, it looks like a named list might take more time to run than the above, but less time than the current regex.