The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

Friday, June 05, 2020

Timing LPEG expressions

One pattern that is seemingly missing from LPEG is a case-insensitive match, a pattern where you can specify a pattern to match “foo”, “FOO”, “Foo” or “fOo”. I have to think this was intentional, as doing case insensitive matching on non-English words is … a complex topic (for a long time, the German letter “ß” upper case form was “SS” but not all “SS” were an upper case “ß”). So it doesn't surprise me there's no pattern for it in LPEG. But I wish it did, as a lot of Internet text-based protocols require case-insensitive matching.

There are two ways around the issue. One way is this:

local lpeg = require "lpeg"
lcoal P    = lepg.P

local patt = (P"S" + P"s")
           * (P"A" + P"a")
           * (P"M" + P"m")
           * P"-"
           * (P"I" + P"i")
           * P"-"
           * (P"A" + P"a")
           * (P"M" + P"m")

But this would seem to produce a lot of branching code that would be slow (LPEG has its own parsing-specific VM). Of course, there's this solution:

local lpeg = require "lpeg"
local P    = lpeg.P
local S    = lpeg.S

local impS = S"Ss" * S"Aa" * S"Mm"
           * P"-"
           * S"Ii"
           * P"-"
           * S"Aa" * S"Mm"

But each lpeg.S() uses 32 bytes to store the set of characters it matches, and that seems like a large waste of memory for just two characters. A third way occured to me:

local lpeg = require "lpeg"
local Cmt  = lpeg.Cmt
local R    = lpeg.R

local impC = Cmt(
                  S"SsAaMmIi-"^1,
                  function(subject,position,capture)
                    if capture:lower() == 'sam-i-am" then
                      return position
                    end
                  end
                )

This just looks for all the characters in “Sam-I-am” and then calls a function to do an actual case-insensitive comparison, but at the cost of doing it at the actual match time, instead of potentially doing it lazily (as the manual puts it, “this one is evaluated immediately when a match occurs (even if it is part of a larger pattern that fails later)”). And it might be a bit faster than the one that just uses lpeg.P(), and with less memory than the one using lpeg.S().

So before going to work on a custom case-insensitive pattern for LPEG (where lpeg.P() is pretty much the case-sensitive pattern), I thought I might want to profile the existing approaches first just to get a feeling for how long each approach takes.

local lpeg  = require "lpeg"
local rdtsc = require "rdtsc" -- this is another post

local Cmt = lpeg.Cmt
local Cf  = lpeg.Cf
local P   = lpeg.P
local R   = lpeg.R
local S   = lpeg.S

local test = "Sam-I-Am"

local base = P"Sam-I-Am"
local impP = (P"S" + P"s")
           * (P"A" + P"a")
           * (P"M" + P"m")
           * P"-"
           * (P"I" + P"i")
           * P"-"
           * (P"A" + P"a")
           * (P"M" + P"m")
local impS = S"Ss" * S"Aa" * S"Mm"
           * P"-"
           * S"Ii"
           * P"-"
           * S"Aa" * S"Mm"
local impC = Cmt(
                  S"SsAaMmIi-"^1,
                  function(subject,position,capture)
                    if capture:lower() == "sam-i-am" then
                      return position
                    end
                  end
                )

local function testf(patt)
  local res = {}
  for i = 1 , 10000 do
    local zen = rdtsc()
    patt:match(test)
    local tao = rdtsc()
    table.insert(res,tao - zen)
  end
  table.sort(res)
  return res[1]
end

print('base',testf(base))
print('impP',testf(impP))
print('impS',testf(impS))
print('impC',testf(impC))

I'm testing the normal case-sensitive pattern, and the three case-insensitive patterns. I run each test 10,000 times and return the lowest value (“lowest” means “fastest”). The rdtsc() function … that's another post (but a pre-summary—it represents the number of clock cycles the CPU has been running and on the test system there are 2,660,000,000 cycles per second).

Anyway, on to the results:

Timing some LPEG patters
base 2800
impP 3020
impS 3020
impC 5190

I'm honestly surprised. First, I thought the last method would do better than it did, but it's nearly twice as slow. The other two are pretty much the same, time wise (which leads me to wonder if the pattern lpeg.P(single_letter) + lpeg.P(single_letter) is internally converted to lpeg.S(letters)—it could very well be). And they aren't that much slower than the case-sensitive pattern. Well, not enough for me to worry about it. Even a much longer string, like “Access-Control-Allow-Credentials” gave similar results.

And no, I did not write out by hand the expression to match “Access-Control-Allow-Credentials” case-insensitively, but wrote an LPEG expression to generate the LPEG expression to do the match:

local lpeg = require "lua"
local Cf   = lpeg.Cf -- a folding capture
local P    = lpeg.P
local R    = lpeg.R

local char = R("AZ","az")
           / function(c)
               return P(c:lower()) + P(c:upper())
             end
           + P(1)
           / function(c)
               return P(c)
             end
Hp = Cf(char^1,function(a,b) return a * b end)

It's a powerful technique, but one that can take a while to wrap your brain around. It's just one of the reasons why I like using LPEG.

A Lua module in assembly, why not?

I've been known to dabble in assembly language from time to time, and there's been this one instruction on the Intel Pentium that I've wanted to play around with—RDTSC. It's used to read the internal time-stamp counter which is incremented every clock cycle. On my system, this counter is incremented 2,660,000,000 times per second (the computer is running at 2.66GHz) and this makes for a nice way to time code, as the instruction is available in userspace (at least on Linux).

I wanted to use this to time some Lua code, which means I need to wrap this instruction into a function that can be called. I could have used some inline assembly in C to do this, but

  1. the code is non-portable anyway;
  2. I wanted to avoid as much C overhead as possible;
  3. and I thought it would be amusing to write an entire Lua module in assembly.

It wasn't hard:

;***************************************************************************
;
; Copyright 2020 by Sean Conner.
;
; This library is free software; you can redistribute it and/or modify it
; under the terms of the GNU Lesser General Public License as published by
; the Free Software Foundation; either version 3 of the License, or (at your
; option) any later version.
;
; This library is distributed in the hope that it will be useful, but
; WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
; or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
; License for more details.
;
; You should have received a copy of the GNU Lesser General Public License
; along with this library; if not, see <http://www.gnu.org/licenses/>.
;
; Comments, questions and criticisms can be sent to: sean@conman.org
;
;***************************************************************************

                bits    32
                global  luaopen_rdtsc
                extern  lua_pushinteger
                extern  lua_pushcclosure

;***************************************************************************
                section .text

ldl_rdtsc:      rdtsc
                push    edx
                push    eax
                push    dword [esp + 12]
                call    lua_pushinteger	; lua_pushinteger(L,rdtsc);
                xor     eax,eax		; return 1
                inc     eax
                lea     esp,[esp + 12]
                ret

;---------------------------------------------------------------------------

luaopen_rdtsc:
                xor     eax,eax
                push    eax
                push    ldl_rdtsc
                push    dword [esp + 12]
                call    lua_pushcclosure ; lua_pushcclosure(L,ldl_rdtsc,0);
                xor     eax,eax		 ; return 1
                inc     eax
                lea     esp,[esp + 12]
                ret

I'll leave it up to the reader to convert this to 64-bit code.

Obligatory Picture

[The future's so bright, I gotta wear shades]

Obligatory Contact Info

Obligatory Feeds

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: https://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

https://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2024 by Sean Conner. All Rights Reserved.