Re: Lua Performance, IO / Regexp

[David Given <dg@...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Mariano Kamp wrote:
[...]
>   The ruby program mentionend in the article takes roughly 2 seconds [1]
> on my osx box [5] using Lua 5.1 [5] for processing 100k lines.
> With 5.6 seconds my first implementation (wf.lua) takes more than the
> double amount of time [2]. Here I use io.lines() to extract the lines
> and then use string.match() to extract the relevant url parts.

A quick look at your script shows a couple of places where performance could
be improved.

Firstly: you have to be very aware of the difference between locals and
globals. Locals are variables; they're stored on the stack and are fast.
Globals are dictionary entries in a hidden dictionary called _G. Unless you
declare something local, it's a global. (Except for loop iterators, which are
automatically local.) So:

for line in io.lines("o100k.ap") do
	article_key = line:match(PATTERN)
	if (article_key) then hits[article_key] = hits[article_key] + 1 end
end

article_key is undeclared; therefore it's a global; therefore every iteration
is doing up to four dictionary lookups. Simply replacing the second line with:

	local article_key = line:match(PATTERN)

...will speed things up no end. You'll want to localise every variable in your
code.

The same applies to function calls; table.insert() is actually doing two
dictionary lookups before the function get called. Put this at the top of your
code:

local table_insert = table.insert

...and then use table_insert() instead. (You can speed up method calls like
your line:match() the same way, but you have to be careful that you don't end
up calling a method on the wrong object. In this case, you know line is a
string, so you can use string.match(line, PATTERN) instead.)

Secondly: you're using table.insert() to append to an array. That works, but
it's slow. In Lua 5.1, this is faster:

for article_key in pairs(hits) do
  hits_index[#hits_index + 1] = article_key
end

Those two tweaks should make a substantially measurable speed improvement.

(If it's actually too slow in the real world, do check out LuaJIT. It's
exactly what it says on the tin. IA32 only, though.)

...

Incidentally, I'm not very surprised io.lines() is faster than reading the
whole datafile: partly, io.lines() parser is going to be way more efficient
than a regex for that; partly your datafile is pathalogically large and is
probably confusing a lot of memory management routines (it'll boil down to
malloc(191*1024*1024)!); and partly because you made a typo in the regex. That
leading % should be a ^. Without it it won't properly anchor to the beginnings
of lines, and I wouldn't be surprised if that made the pattern a lot slower.

- --
┌── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ─── http://www.cowlark.com ───────────────────
│
│ "There does not now, nor will there ever, exist a programming language in
│ which it is the least bit hard to write bad programs." --- Flon's Axiom
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHF8S+f9E0noFvlzgRAmXAAKCsHfrj2n3qPrRAn3QutA4+f5AoNwCbB4oU
cuXg48KgF8sYPhnzcPBuNKE=
=oFnC
-----END PGP SIGNATURE-----