Fastest Trigger Types

rand
Posts: 2
Joined: Sat Jan 04, 2020 2:08 am

Fastest Trigger Types

Post by rand »

For someone in the know, what is the order from fastest to slowest of the following trigger types?

Start of line (fastest?)
Exact Match or Substring (middle?)
Regex (slowest)

I read somewhere that substring is, but that sounds illogical (assuming I understand correctly). Start of line should instantly reject entire lines if the first character doesn't match, where as substring would have to check an entire line before moving to the next.

If I am way off base (very possible) please explain.

Thanks!

User avatar
demonnic
Posts: 647
Joined: Sat Dec 05, 2009 3:19 pm

Re: Fastest Trigger Types

Post by demonnic »

From fastest to slowest:

Exact Match/Start of line are just about the same, as they both fail as you describe
substring
regex

and I forget where the lua/prompt/color trigger types fit in with all that. The start of line and exact match are the fastest, followed by substring, Then really all the other types sort of fall into the same general lump of "slower than the substring types."
They all match pretty quickly though. That being said, using start of line/exact match/substring triggers to shield/gate off your regex triggers definitely gives performance increases in trigger matching time.

User avatar
Vadi
Posts: 4833
Joined: Sat Mar 14, 2009 3:13 pm

Re: Fastest Trigger Types

Post by Vadi »

I think Lua is last after regex, with regex being the 2nd slowest. Haven't run the benchmarks in a while though!

fordpinto
Posts: 32
Joined: Wed Sep 25, 2019 4:59 pm

Re: Fastest Trigger Types

Post by fordpinto »

This was touched upon in another thread, which is why I ended up here. My first reaction to the suggestion that start of line/exact match is faster than regex was "Yeah, makes sense". But I am now wondering it's a bit more nuanced than that. Some second thoughts:

1) The basic algorithmic steps for beginning of line match to a string of "Start of the " and regex match to the pattern "^Start of the " I think would have to be pretty similar. Regex would have more complex logic, but most of that logic would not be needed for such a simple pattern, and I would expect it to include optimization (i.e. check for match to ^ before any other logic rather than after) that would also narrow the difference between the two.
2) Arbitrary regex expressions would be of course much slower, but that's primarily because they allow that additional logic complexity. Any speed comparisons would have to be made between equivalent patterns, such as the example in the first item above.
3) There are different timings. Time-to-fail is much more important that time-to-match, since triggers are supposed to fail vast majority of the time.
4) In light of the above, how much slower would be time-to-fail of a complex regex that does include the beginning of the line match (starts with ^ followed by exact string) as compared to a trigger shielded by another one with begin of line type?

I am actually curious what are rough throughput numbers in terms of "trigger fails per second" just to get a gauge Mudlet's trigger prowess.

User avatar
Vadi
Posts: 4833
Joined: Sat Mar 14, 2009 3:13 pm

Re: Fastest Trigger Types

Post by Vadi »

That would be good to measure!

fordpinto
Posts: 32
Joined: Wed Sep 25, 2019 4:59 pm

Re: Fastest Trigger Types

Post by fordpinto »

I did a test (and this is done on an ancient i5 machine, numbers should be significantly higher on a modern computer):
1. Begin of line trigger reaches ~7 million trigger-fails per second throughput
2. Exact match trigger reaches ~5 million trigger-fails per second throughput
3. Regex begin of line equivalent (no-wildcard regex starting with ^) reaches 4 million trigger-fails per second throughput

Since I do not think a mud would send more than 10 lines per second typically, that allows 100s of thousands of triggers of any of those types to be active in order for this difference to start to matter.

That said, the actual throughputs could be even higher and the underlying difference more significant, since the numbers account for not only the CPU load required for trigger processing, but the feedTrigger() CPU load too. I generated 1000 triggers and used 1000 feedTriggers. I tried to weigh it more heavily towards trigger impact, but something isn't working quite well if the trigger number is much higher than 1000. I tried creating 10000 triggers, and the code got somehow stuck on ~1600. No error message, nothing. Did not investigate further, but I thought it's strange.

fordpinto
Posts: 32
Joined: Wed Sep 25, 2019 4:59 pm

Re: Fastest Trigger Types

Post by fordpinto »

Ran a test using feedTriggers() without adding any triggers to correct for their CPU load in the above tests. Corrected numbers are
Begin of line: 12 million trigger-fails per second
Exact match: 7 million trigger-fails per second
Regex: 5 million trigger-fails per second

User avatar
Vadi
Posts: 4833
Joined: Sat Mar 14, 2009 3:13 pm

Re: Fastest Trigger Types

Post by Vadi »

Nice! Thanks for testing it out. Good to see the old wisdom still holding up.

User avatar
demonnic
Posts: 647
Joined: Sat Dec 05, 2009 3:19 pm

Re: Fastest Trigger Types

Post by demonnic »

I'm a little surprised begin of line and exact match are so far apart, I'd have figured they'd both fail at the first nonmatching character and test pretty close together. I wonder why begin of line has almost double the fail throughput.

User avatar
Vadi
Posts: 4833
Joined: Sat Mar 14, 2009 3:13 pm

Re: Fastest Trigger Types

Post by Vadi »

It goes into the bowels of Qt and many many optimisations they have. I suspect if it were that algorithm, it'd actually be way slower than the speeds we're getting now.

https://catchchallenger.first-world.inf ... ion#String
+ QStringView got added to Qt since, which we don't make use of...

@fordpinto want to package up your benchmarks?

Post Reply