ToME: the Tales of Maj'Eyal

Everything about ToME
It is currently Sun Jun 25, 2017 5:18 am

All times are UTC




Post new topic Reply to topic  [ 5 posts ] 
Author Message
PostPosted: Fri Jan 25, 2013 2:18 am 
Offline
Wyrmic

Joined: Wed Aug 22, 2012 12:16 am
Posts: 200
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 concatNiceproposed replacement
Time:34.93s19.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:351: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 factorialproposed replacement
Time (rounded):8:431: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.


Attachments:
File comment: utils.lua patch for svn r6365
utils.txt [2.97 KiB]
Downloaded 60 times
Top
 Profile  
 
PostPosted: Fri Feb 01, 2013 1:10 am 
Offline
Wyrmic

Joined: Wed Aug 22, 2012 12:16 am
Posts: 200
Bump for bug fix update.


Top
 Profile  
 
PostPosted: Mon Feb 04, 2013 8:39 pm 
Offline
Perspiring Physicist

Joined: Thu Feb 17, 2011 5:20 am
Posts: 887
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 :)

_________________
darkgod wrote:
OMFG tiger eye you are my hero!


Top
 Profile  
 
PostPosted: Tue Feb 05, 2013 1:36 am 
Offline
Wyrmic

Joined: Wed Aug 22, 2012 12:16 am
Posts: 200
tiger_eye wrote:
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.


Top
 Profile  
 
PostPosted: Tue Feb 05, 2013 1:06 pm 
Offline
Master of Eyal

Joined: Wed Jul 24, 2002 9:26 pm
Posts: 10121
Location: Angolwen
Thanks!
Applied

_________________
[tome] joylove: You can't just release an expansion like one would release a Kraken XD
--
[tome] phantomfrettchen: your ability not to tease anyone is simply stunning ;)


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group