Speed up RssIgnores::matches

[Minoru]

I have 7 ignore-article commands and set ignore-mode to "display", and I noticed that if I comment them out, startup time goes down by 10% (when cache.db is already in the disk cache). GNU Prof shows that quite a bit of time is spent in RssIgnores::matches.

That method takes an RssItem, loops through all ignore-article rules looking for the ones that match item's feed, and checks if their associated regexes match. There are two inefficiencies here:

1. ignore-article rules are stored in vector<pair<string, regex>>, which is basically an std::map<string, regex> in disguise. If we switch to an actual map, the lookup time will become near-zero and won't grow with the number of ignore-article rules. std::unordered_multimap seems the most fitting;
2. as far as I can see, that method is only used in RssFeed::update_items, where it is called on all items of each feed. In that scenario, we can get feed's URL once, lookup the associated ignore-article rules, and use that "shortlist" when checking individual items.

RssIgnores::matches lacks any tests. They need to be written before doing any of the aforementioned optimizations.

Evaluation

Since we don't have benchmarks, I have to describe how I'll evaluate the results of these optimizations.

I have a large cache file: over 400 feeds, almost 1 gigabyte of data. I'll put in on tmpfs to make sure I/O doesn't screw the results.

I'll run the following command five times in a row and take the smallest result:

$ echo q | time ./newsboat --cache-file=/dev/shm/cache.db

Newsboat will be compiled in release mode (i.e. just make newsboat).

My config file will contain one ignore-mode "display" entry and 0 to 20 ignore-article entries. I will be looking at two things:

1. how startup time depends on presence of ignore-article entries; and
2. how startup time depends on the number of ignore-article entries.

I will be comparing the results to results from then-current master. The goal is to improve on master.

[Minoru]

@danieloh0714 asked me to elaborate on this:

as far as I can see, that method is only used in RssFeed::update_items, where it is called on all items of each feed. In that scenario, we can get feed's URL once, lookup the associated ignore-article rules, and use that "shortlist" when checking individual items.

First of all, this idea is wrong about the places where RssIgnores::matches() is used. Currently they are:

1. RssParser::add_item_to_feed() -- used when parsing an RSS file we fetched from the network. If ignore-mode is download, ignored articles are dropped here, so they never make it to the database at all;
2. Cache::internalize_rssfeed() -- used when reading a feed from the database. If ignore-mode is display, we have to re-apply the ignore rules every time we load an article, because the rules might have changed since the last time we applied them;
3. Cache::search_for_items() -- when searching, the database returns everything it finds, and we drop ignored articles in this method.

All three methods just loop through items and call RssIgnores::matches() on each one. However, the first two methods operate on a single feed, i.e. they know the feed's URL before they even start looping. That gives them ability to find all applicable rules once, and then apply them to each item. That should save us the repeated lookup of the same feed URL.

This optimization has the most potential for regex rules, because "looking them up" involves compiling a regex and applying it to the feed URL. If we do it just once per feed, we could save some time.

[danieloh0714]

Ok, I think I understand now. Thanks for elaborating. I'll handle this in a separate PR from #2706.