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:
| 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
- the code is non-portable anyway;
- I wanted to avoid as much C overhead as possible;
- 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.
Monday, June 08, 2020
I can code that FizzBuzz function with only two tests
My favorite implementation of FizzBuzz is the Ruby version based upon nothing more than lambda calculus and Church numbers, i.e. nothing but functions all the way down.
Then I saw an interesting version of it in the presentation “Clean Coders Hate What Happens to Your Code When You Use These Enterprise Programming Tricks.” The normal implementation usually involves thee tests, one for divisibility by 3, one for divisibility by 5, and an annoyingly extra one for both or for divisibility by 15. But the version given in the presentation only had two tests. Here's a version of that in Lua:
function fizzbuzz(n)
local test = function(d,s,x)
return n % d == 0
and function(_) return s .. x('') end
or x
end
local fizz = function(x) return test(3,'Fizz',x) end
local buzz = function(x) return test(5,'Buzz',x) end
return fizz(buzz(function(x) return x end))(tostring(n))
end
for i = 1 , 100 do
print(i,fizzbuzz(i))
end
The function test() will return a new function that returns a string,
or whatever was passed in x.
fizz() and buzz() are functions that return what test() returns.
The last line can be broken down into the following statements:
_0 = function(x) return x end _1 = buzz(_0) _2 = fizz(_1) _3 = _2(tostring(n)) return _3
And we can see how this works by following a few runs through the code. Let's first start with a number that is not divisible by 3 or 5, say, 1.
_0 = function(x) return x end
_1 = buzz(_0) = function(x) return x end
_2 = fizz(_1) = function(x) return x end
_3 = _2("1") == "1"
return _3
_0 is the identity function—just return whatever it is given.
buzz() is called,
which calls test(),
but since the number is not divisible by 5,
test() returns the passed in identity function,
which in turn is returned by buzz().
fizz() is then called,
and again,
since the number is not divisible by 3,
_test() returns the identity function,
which is returned by fizz().
_3 is the result of the identity function called with “1”,
which results in the string “1”.
Next, the number 3 is passed in.
_0 = function(x) return x end
_1 = buzz(_0) = function(x) return x end
_2 = fizz(_1) = function(_) return 'Fizz' .. _1('') end
_3 = _2("3") == 'Fizz'
return _3
_0 is the identify function.
buzz() just returns it since 3 isn't divisible by 5.
fizz(),
however,
returns a new function,
one that returns the string “Fizz” concatenated with the empty string as returned by the identify function.
This function is then called,
which results in the string “Fizz”.
The number 5 works similarly:
_0 = function(x) return x end
_1 = buzz(_0) = function(_) return 'Buzz' .. _0('') end
_2 = fizz(_1) = function(_) return 'Buzz' .. _0('') end
_3 = _2("5") == 'Buzz'
return _3
Here,
buzz() returns a new function which returns the string “Buzz” concatenated with the empty string returned by the identify function.
fizz() returns the function generated by buzz() since 5 isn't divisible by 3,
and thus we end up with the string “Buzz”.
It's the case with 15 where all this mucking about with the identify function is clarified.
_0 = function(x) return x end
_1 = buzz(_0) = function(_) return 'Buzz' .. _0('') end
_2 =_fizz(_1) = function(_) return 'Fizz' .. _1('') end
_3 = _2("15") = 'FizzBuzz'
return _3
Again,
_0 is the identify function.
buzz() returns a new function because 15 is divisible by 5,
and this function returns the string “Buzz” concatenated by the empty string returned by the identity function.
fizz() also returns a new function,
because 15 is also divisible by 3.
This function returns the string “Fizz”, concatenated by the passed in function,
which in this case is not the identity function,
but the function returned from buzz().
This final function returns “Fizz” concatenated with the string of the function that returns “Buzz” concatenated with the empty string returned by the identity function,
resulting in the string “FizzBuzz”.
Yes, it's quite a bit of work just to avoid an extra test, but fear not! Here's a way to do FizzBuzz with just two tests that is vastly simpler:
function fizzbuzz(n)
local list = { 'Fizz' , 'Buzz' , 'FizzBuzz' }
list[0] = tostring(n)
local m = (n % 3 == 0 and 1 or 0)
+ (n % 5 == 0 and 2 or 0)
return list[m]
end
for i = 1 , 100 do
print(i,fizzbuzz(i))
end
Here we generate an index into an array of four possible responses, the original number as a string, “Fizz”, “Buzz” and “FizzBuzz”. If the number isn't divisible by either 3 or 5, the index is 0; if it's divisible by 3, the index is 1, if divisible by 5, the index is 2, and if both, the index ends up as 3. It's not quite as mind blowing as the first version, but it is easier to translate to a language that lacks closures, like C.
Wednesday, June 10, 2020
The email situation has been solved
I finally solved the email issue on my server—the physical host was NATing connections from my virtual server. There's no need for that. Once the bypass for the NAT was added, outgoing packets were finally coming from my server's IP address.
Monday, June 15, 2020
Dear Apple
You must really not want my money. I know, I know, you aren't discrimiting against my race, or sex, or religion, or the fact that I'm voting for Velma Owen for President. But I find it puzzling that this is the third time you rejected my attempt to drunkenly spend money to fix a problem. The first time I was ready to buy the K2 of Mac computers only to learn I had to buy one online—I wasted my time in coming to the store. The second time I was going to buy an iPad (long stupid story there, not worth going into) only to be shoved towards Best Buy where it was cheaper.
And then today. I've walked into your Apple Store looking to buy a new monitor. Earlier, when I went to turn on the monitor on my Mac, it briefly lit up, decided it had enough of life and immediately shut off, never to turn back on again. Granted, the monitor was from 2005, and I bought it used around ten years ago so I'm not terribly upset over it dying an inglorious dimming death.
But alas, Apple no longer supports that monitor, so fixing it was out of the question. The interface on the Mac mini it's attached to is, itself, obsolete, and Apple no longer carries the appropriate adaptors. And the other interface on the Mac mini, the HDMI port, is not supported by any new Apple monitor. So I was told my best bet was to head of to … Best Buy.
Why did I even bother coming to your store, Apple? Why do you even bother to have a store in the first place?
Saturday, June 27, 2020
Yet another repair job, this time involving solder!
“Are you ever going to finish repairing the clock?”
“Oh! I was waiting to see if you had any solder.”
“I thought I already told you I didn't have any, and that you were going to check your tool box.”
“Ah. Okay, let me do that.”
And so I found myself repairing an old-style alarm clock with the bells on top. It's not actually that old, having been manufactured in China some time in the last decade. The battery had died and leaked, causing some corrosion around the batter terminals. The corrosion wasn't coming off that easy, so last week (month? Day? Year? I HAVE NO CONCEPT OF TIME ANYMORE!) I soaked the back of the clock, which hosed the battery compartment, in vinegar overnight to clean up the corrosion. That worked beautifully, but some wires had come loose and needed to be resoldered.
The hard part of doing the repair? Finding a pair of wire strippers that wouldn't just cut the wire. The second hardest part? The actual soldering job. It had been way too long since I last used a soldering iron [Nothing worse than a programmer with a soldering iron. –Editor.] [Shut up, you! –Sean] but I managed to only burn one finger and resolder everything only twice. Not bad [If you say so yourself. –Editor] if I say so—[Shut up! –Sean].
Anyway, the clock has been repaired, it works, and we saved ourselves having to buy a new one.
