Utility function optimizations - updated 2013-01-31
Posted: Fri Jan 25, 2013 2:18 am
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()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:
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:
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()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!:
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.
Hardly 1: table.concatNice()
Code: Select all
@@ -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)
| old concatNice | proposed replacement | |
| Time: | 34.93s | 19.48s |
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 |
Hardly 3: util.factorial()
Code: Select all
@@ -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)
| old factorial | proposed replacement | |
| Time (rounded): | 8:43 | 1:08 |
| Max memory usage: | > 15MB | < 750kB |
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.
