After finding the
problem with listing table contents in the debug console, I decided to go through
utils.lua to see if anything else could use a little polish (I was bored). The good news is that hardly anything does! Here I present the hardlies, and a patch. Note: all benchmark times are obtained via
timecmd.bat using a standalone Lua 5.2 interpreter on an Athlon II x3 450 @3.2GHz running Windows 7 Pro 64-bit. All tests were run once; the running times aren't close enough to worry about tiny variations.
Hardly 1:
table.concatNice()Code:
@@ -29,15 +29,8 @@
end
function table.concatNice(t, sep, endsep)
- if not endsep then return table.concat(t, sep) end
- local str = ""
- for i, s in ipairs(t) do
- if i == #t and i > 1 then str = str..endsep..s
- elseif i == 1 then str = s
- else str = str..sep..s
- end
- end
- return str
+ if not endsep or #t == 1 then return table.concat(t, sep) end
+ return table.concat(t, sep, 1, #t - 1)..endsep..t[#t]
end
function table.min(t)
This replaces several lines with two. It's easier to read and maintain and is substantially faster. Calling this function 20,000,000 times (half with an ending separator, half without) on a table with 9 string elements gives these times:
| old concatNice | proposed replacement |
Time: | 34.93s | 19.48s |
I strongly suspect that tables with more elements would separate the times even further.
Edit 2: Updated to fix a bug with single element tables. Time was 18.65s, now 19.48s. Still faster.
Hardly 2: the
previously mentioned, buggy table.orderedPairs()The current four function set is copied verbatim from
the Sorted Iteration page at lua-users.org and is truly appalling. Included in the patch is a slightly tweaked version of my replacement as well as the removal of repeated tests in the comparison function. Benchmarks of iteration through a table of numbers using
for loops:
| lua-users.org's version (100,000 element table) | proposed replacement (10,000,000 element table) |
Time (rounded): | 9:35 | 1:18 |
Yes, it's that bad. I do suspect that my version may be slower for very small (single digit, probably low single digit)
n, depending on how long it takes to produce the closure. It still fixes the current bugs, though.
Hardly 3:
util.factorial()Code:
@@ -1916,11 +1885,11 @@
end
function util.factorial(n)
- if n == 0 then
- return 1
- else
- return n * util.factorial(n - 1)
+ local f = 1
+ for i = 2, n do
+ f = f * i
end
+ return f
end
function rng.poissonProcess(k, turn_scale, rate)
A basic recursive factorial function replaced with a basic iterative factorial function. It's much faster and uses less memory. Testing from 1! to 100,000!:
| old factorial | proposed replacement |
Time (rounded): | 8:43 | 1:08 |
Max memory usage: | > 15MB | < 750kB |
The high resource usage of the current function is a result of the large
n in the benchmark (which the T-Engine 4 probably never comes close to using). Still, you never know about the future, better safe than sorry, and so on.
Edit: I just double checked and see that Lua doesn't have built-in bignum support (seriously?). I'm not sure whether actually using large numbers would make this one closer.
Patch:
This patch replaces the horrible, buggy
table.orderedPairs() and includes the improvements to
table.concatNice() and
util.factorial() presented above.