Utility function optimizations - updated 2013-01-31

[aardvark]

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: 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)

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: 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)

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.

[aardvark]

Bump for bug fix update.

[tiger_eye]

Hey aardvark, I think this is pretty cool. If you're interested in optimizing more things, just let me/us know and I/we can point you towards some things that could probably be better optimized

[aardvark]

Hey aardvark, I think this is pretty cool. If you're interested in optimizing more things, just let me/us know and I/we can point you towards some things that could probably be better optimized :)

Somewhat, yes. This little foray was mostly because of the table.orderedPairs() bug. Fixing that mess was an almost moral imperative and is the most important part of the patch. After seeing that darkgod (I assume) got those functions from what I would have supposed was a reputable source of Lua info, I was concerned that other utility functions might have come from similar sources and been similarly horrifying.

If you've got a list of other things that need optimizing, I may work on it from time to time.

[darkgod]

Thanks!
Applied