Page 1 of 2

Fastest Trigger Types

Posted: Sat Jan 04, 2020 2:16 am
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!

Re: Fastest Trigger Types

Posted: Wed Jan 08, 2020 12:16 am
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.

Re: Fastest Trigger Types

Posted: Mon Jan 20, 2020 9:27 pm
by Vadi
I think Lua is last after regex, with regex being the 2nd slowest. Haven't run the benchmarks in a while though!

Re: Fastest Trigger Types

Posted: Fri Mar 13, 2020 8:41 pm
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.

Re: Fastest Trigger Types

Posted: Fri Mar 13, 2020 9:35 pm
by Vadi
That would be good to measure!

Re: Fastest Trigger Types

Posted: Sat Mar 14, 2020 11:26 pm
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.

Re: Fastest Trigger Types

Posted: Sun Mar 15, 2020 1:41 am
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

Re: Fastest Trigger Types

Posted: Sun Mar 15, 2020 4:33 am
by Vadi
Nice! Thanks for testing it out. Good to see the old wisdom still holding up.

Re: Fastest Trigger Types

Posted: Sun Mar 15, 2020 3:25 pm
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.

Re: Fastest Trigger Types

Posted: Sun Mar 15, 2020 4:27 pm
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?