Plain Text Trigger Performance

Posted by Candido on Fri 03 Jun 2011 08:14 AM — 8 posts, 32,372 views.

Candido USA Fri 03 Jun 2011 08:14 AM #0

I've been thinking a long time about this, but I want to check and make sure I'm not totally off track before I do something that's going to be a pretty big undertaking.

Assume a sample size of around 500-1000 simple triggers that require no wildcards. Just plain matches. In theory/guessing, which of these is fastest?

1. Make each an individual trigger with anchored regex (^ and $).

2. Make each an individual plain text trigger, no regex.

3. Create a catchall trigger ^(.+)$ which passes its match to a function. The function uses the plain text of the match as a key in a hash table that is constructed with every one of the plain text matches of the 'triggers' as keys, and functions of what each one should do when matched (what would otherwise normally be the Send To of the trigger).

As you can probably guess, I'm here because I think 3 would be the fastest. A hash table lookup is, when best implemented, a constant time operation no matter the size of the table, and I have no reason to believe Lua is lacking in this respect.

The underlying question then is the performance of ^(.+)$. Is it slow because is can be anything, or is it fast because it can be anything? My instinct is that even if it's slow (observation seems to confirm this), it isn't so slow that its matching time plus a constant time hash table lookup is greater than the time needed to evaluate 500-1000 separate triggers.

Opinions?

Candido USA Fri 03 Jun 2011 08:18 AM #1

Forum is logging me out whenever I try to edit, but by Send To above I just meant Send.

Nick Gammon Australia Forum Administrator Fri 03 Jun 2011 08:31 AM #2

First, options 1 and 2 will be the same. Internally all triggers are compiled to regular expressions.

As for option 3, I'm inclined to agree with you. For a large number, exercising the trigger evaluation code (plus the associated overhead inside the client) 1000 times per line sounds like it will take longer than finding a single match and then doing a lookup.

Especially since in Lua table lookups are pretty efficient.

As for the slowness of the "catch all" trigger I tried a bit of test code:


re = rex.new ("^.+$")
--re = rex.new ("^.")

local str = "While traversing the busy, cobbled streets of Darkhaven, you notice"

local s, e, t

start = utils.timer ()
for i = 1, 1e6 do
  s, e, t = re:exec (str)
end -- for
finish = utils.timer ()

print ("time taken = ", finish - start)

I tried two different ideas here, because for a "catch all" trigger you don't really need to make the regexp handler go to the end of the line, do you? After all, triggers always return the matching line. So all you really want is something that always triggers. Hence matching on "." should do it. The regexp engine will find a single character, matching anything, and quickly exit.

Then use the second argument to the trigger (the matching line) and do your table lookup.

My testing above seems to indicate that matching a single "." indeed runs faster than trying to match "^.+$" but not by a very large amount.

To put it into context, I got the million matches from the script in around 0.89 seconds using "." but 1.10 seconds using "^.+$".

So either way, I wouldn't really call a million matches a second "slow".

Candido USA Fri 03 Jun 2011 09:07 AM #3

Awesome, that's what I was hoping to hear, and at the same time not hoping to hear :P

Also, you might consider implementing this directly into Mushclient. Not that I'm trying to offload work that can be done on the user side, but I think a lot of people with big bloated worlds on ludicrously spammy MUDs (Iron Realms, anyone?), could benefit from it.

This is an oversimplification no doubt, but I imagine all you'd have to do is make it so when it comes time to evaluate a plain text trigger, it goes to table lookup instead of the usual Mush trigger engine. Plain text is determined by the trigger having only special characters of ^, $, and \ when interpreted as regex, which can be flagged in the trigger itself to avoid having to determine it during run time.

Imagine the freedom that would come from knowing you can add any amount of plain text triggers and not incur the slightest performance decrease, of course provided you don't add so many that you run out of memory...

It's something to consider. Also, totally did not know we had a time function with granularity finer than a millisecond. Here I am doing all my speed testing with os.clock().

Nick Gammon Australia Forum Administrator Fri 03 Jun 2011 10:21 AM #4

Well, I understand what you are saying. But triggers right now are self-contained. That is not only might they match on plain text but they might all do different things. Your case seems to me to be a fairly specialized case, which currently can be handled quite quickly.

It sounds like an interesting system you are working on. You could almost consider doing a SQLite3 database lookup. That might be slower than a table lookup, but the database would probably cache things and be quite fast.

Look at this for example:

The mapper reads a database to draw those rooms. Admittedly it caches the room information in memory once they are read, but it seems quite fast, as each box on the screen is a room.

Candido USA Sun 05 Jun 2011 06:54 AM #5

That's a really cool mapper, though I suspect helped a bit by aardwolf being so grid-like.

SQLite is an interesting idea, but after all I am trying to go for maximum speed here. Also my experience with SQLite in Mushclient has not been the best to begin with. Could very well just be improper use or foolish expectations on my part, but I once made a script that did about 10k INSERTs by putting DatabaseExec in a for loop, and it froze so bad I had to close Mush. I have a hunch that using the for loop to build a massive sql string and then doing it in one DatabaseExec would probably help things. Also, once things are built, just using SELECT might be a lot faster, but I haven't timed it or tested it extensively.

Nick Gammon Australia Forum Administrator Sun 05 Jun 2011 07:46 AM #6

You should have used a transaction. That is MUCH faster. Try this code:


DatabaseOpen ("db", GetInfo (66) .. "mytestdb.sqlite", 6)

DatabaseExec ("db", [[
DROP TABLE IF EXISTS weapons;
CREATE TABLE weapons(
        weapon_id INTEGER NOT NULL PRIMARY KEY autoincrement,
        name  TEXT NOT NULL,
        damage INT default 10,
        weight REAL
      );
      ]])

start = utils.timer ()

DatabaseExec ("db", "BEGIN TRANSACTION")

for i = 1, 10000 do  
  DatabaseExec ("db", "INSERT INTO weapons (name, damage) VALUES ('sword', 42)")
end -- for
  
DatabaseExec ("db", "COMMIT")

finish = utils.timer ()

print ("time taken = ", finish - start)
print ("changes = ", DatabaseTotalChanges ("db"))

DatabaseClose ("db")  -- close it

That inserts 10000 records, and printed this:


time taken =  0.76090487452166
changes =  10000

That's 10000 inserts in under a second!

And to read all 10000 back again ...



DatabaseOpen ("db", GetInfo (66) .. "mytestdb.sqlite", 6)

start = utils.timer ()

local count = 0

DatabasePrepare ("db", "SELECT * from weapons")

-- execute to get the first row
rc = DatabaseStep ("db")  -- read first row

-- now loop, displaying each row, and getting the next one
while rc == sqlite3.ROW do
  
  count = count + 1
  local id =  DatabaseColumnValue ("db", 1)  -- get some data
 
  rc = DatabaseStep ("db")  -- read next row
end -- while loop

-- done with statement
DatabaseFinalize ("db")

finish = utils.timer ()

print ("time taken = ", finish - start)
print ("read = ", count)

DatabaseClose ("db")  -- close it

That printed:


time taken =  0.022610129890381
read =  10000

So we read 10000 records in 22 milliseconds. Again, not too bad.

Candido USA Mon 06 Jun 2011 06:07 AM #7

Thanks. I knew it was something simple.