Thread Tools Display Modes
03-31-09, 02:03 AM   #21
Foxlit
A Warpwood Thunder Caller
AddOn Author - Click to view addons
Join Date: Nov 2006
Posts: 91
Originally Posted by watchout View Post
O(1) (for lookup) is only average case for your typical hash table implementation, and that only if the key-hashes follow the perfect distribution that the hash-function designer thought to be universal.
You might have a point if you can show that hash collisions occur more frequently in the global environment than they would in your small table, taking into account the difference in the amount of allocated hash buckets. Personally, I don't think that's the case.

Worst case is O(n). Reality will be somewhere in between, especially since best case O(1) = average case O(1) should give you a hint on why the O-notation is not always the perfect method to judge the performance of an algorithm.
I don't see a problem with the O-notation here.

This however... is wrong. In the specific way that you did not correctly guess what performance difference I observed. [...] I reran my bench when writing this post and found that the performance of the global table has significantly improved (it's still not completely the same as an empty table though, about 2-5% off *cough*), I apologize for this. I just should have rerun the bench when writing my previous post.
Unfortunately, I can only guess at what testing you're doing without looking at the code. A 2-5% difference seems small enough to be caused by some form of noise.

It [the number of entries in the global environment] used to be much bigger - so big actually that my client locked up and disconnected before finishing counting.
Iterating over a table with one million string keys and incrementing a counter each iteration takes slightly over 0.3s using lua on my laptop. It's possible that WoW's Lua implementation, or your PC (or both) are slower than what I'm testing against; on the other hand, I doubt the difference is much greater than 1:10. Extrapolating on that, it'd take at least several million entries to freeze your client long enough to force a disconnect. The most obvious conclusion is that your counting code did something other than just count entries.
__________________
... and you do get used to it, after a while.

Last edited by Foxlit : 03-31-09 at 03:14 AM.
  Reply With Quote
03-31-09, 06:14 AM   #22
Aezay
A Theradrim Guardian
 
Aezay's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2007
Posts: 66
Now that we are already talking about "efficient" Lua code, I have a few things I've been wondering about lately.
String concats, I know they are bad to do many times as it will create a new sting each time, but I was curious which one of these lines would be the best to use? Does a concat of an empty string mean much?
Code:
label:SetText(FormatTime(timeLeft)..(showTotalTime and " / "..duration or ""));
label:SetText(showTotalTime and FormatTime(timeLeft).." / "..duration or FormatTime(timeLeft));
Is there any performance benefits in assigning multiple variables at the same times compared to one per line?
Code:
tbl.name, tbl.value, tbl.color = name, value, color;

tbl.name = name;
tbl.value = value;
tbl.color = color;
Also, what is this O-notation you're talking about?

watchout
Doh, you're right, ah well, not like it really means anything
  Reply With Quote
03-31-09, 08:49 AM   #23
Slakah
A Molten Giant
 
Slakah's Avatar
AddOn Author - Click to view addons
Join Date: Aug 2007
Posts: 863
Originally Posted by Aezay View Post
Is there any performance benefits in assigning multiple variables at the same times compared to one per line?
Code:
tbl.name, tbl.value, tbl.color = name, value, color;

tbl.name = name;
tbl.value = value;
tbl.color = color;
Code:
local clock = os.clock
local insert, sort = table.insert, table.sort

local orderednames = {}
local names = setmetatable({}, {__newindex = function(t, k, v)
    insert(orderednames, k)
    rawset(t, k, v)
end})

local function bench(name, func, ...)
    local start = clock()
    for i = 1, 1e7 do
        func(...)
    end
    names[name] = clock() - start
end

local function printresults()
    sort(orderednames, function(a, b)
        return names[a] < names[b]
    end)

    for i, v in pairs(orderednames) do
        print(string.format("%d  %s took %.5f secs", i, v, names[v]))
    end
end

local tbl = {}
tbl.cat, tbl.dog, tbl.cow, tbl.pig = "Meow", "Woof", "Moo", "Oink"


bench("1 line assign", function()
    tbl.cat, tbl.dog, tbl.cow, tbl.pig = "Meow", "Woof", "Moo", "Oink"
end)

bench("multi line assign", function()
    tbl.cat = "Meow"
    tbl.dog = "Woof"
    tbl.cow = "Moo"
    tbl.pig = "Oink"
end)

printresults()
I'm consistently getting these results
Code:
1  multi line assign took 11.77000 secs
2  1 line assign took 12.55000 secs
I can't explain it.
  Reply With Quote
03-31-09, 10:42 AM   #24
Aezay
A Theradrim Guardian
 
Aezay's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2007
Posts: 66
I completely forgot I had a lua5.1.exe lying around, so I just ran your code and come up with this, same results really, just faster. What did you use to run the code in?
Code:
1  multi line assign took 2.01600 secs
2  1 line assign took 2.54600 secs

Using your benchmark code, I tried running this to see which was fastest. It is more or less a copy/paste from one of my addons, from an OnUpdate script on a timer.
Code:
local text;
local showTotalTime = false;
local timeLeft, endTime;
local duration = 60;

local function FormatTime(sec)
	if (abs(sec) <= 60) then
		return string.format("%.1f",sec);
	else
		return string.format("%d:%.2d",sec / 60,abs(sec) % 60);
	end
end

endTime = clock() + duration;
bench("empty string concat",function()
	timeLeft = (endTime - clock());
	text = FormatTime(timeLeft)..(showTotalTime and " / "..duration or "");
end);

endTime = clock() + duration;
bench("no concat",function()
	timeLeft = (endTime - clock());
	text = showTotalTime and FormatTime(timeLeft).." / "..duration or FormatTime(timeLeft);
end);
To my surprise it didn't really matter which way it's done, I guess that is because the concat of an empty string is on the same line as the FormatTime call, and thus is done in the same go, meaning it wont actually create a new Lua string.
Code:
1  no concat took 13.15700 secs
2  empty string concat took 13.21800 secs
Setting the showTotalTime to true produces these results, which again is pretty much the same.
Code:
1  no concat took 23.56300 secs
2  empty string concat took 24.56200 secs

Last edited by Aezay : 03-31-09 at 11:24 AM.
  Reply With Quote
03-31-09, 11:23 AM   #25
Slakah
A Molten Giant
 
Slakah's Avatar
AddOn Author - Click to view addons
Join Date: Aug 2007
Posts: 863
Originally Posted by Aezay View Post
What did you use to run the code in?
I'm on my netbook, so that's to be expected .
  Reply With Quote
03-31-09, 11:26 AM   #26
Aezay
A Theradrim Guardian
 
Aezay's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2007
Posts: 66
Just updated my post above, while you posted, with some tests about string concats.

What about meant with where you ran your code, was which program, was it also lua5.1.exe?
  Reply With Quote
03-31-09, 11:49 AM   #27
Slakah
A Molten Giant
 
Slakah's Avatar
AddOn Author - Click to view addons
Join Date: Aug 2007
Posts: 863
Yeah I'm using lua 5.1 on Fedora Core 10, on an Asus Aspire One.

Also, what is this O-notation you're talking about?
I was also interested so I found this http://www.perlmonks.org/?node_id=227909.

So if my understanding is correct, if a table lookup is O(1) then the size of the table doesn't affect the speed of the lookup?

Last edited by Slakah : 03-31-09 at 11:52 AM.
  Reply With Quote
03-31-09, 01:00 PM   #28
IBLJerry
A Deviate Faerie Dragon
AddOn Author - Click to view addons
Join Date: Dec 2006
Posts: 12
O(1) means that the time taken to perform an algorithm is a constant, whatever the input size. O(n) means that the time is a multiple of the input size (plus a possible constant).

Algorithm complexity is interesting as a tool to compare how algorithm scale with the input size. But what this tool doesn't tell you, is which algorithm is the fastest. An O(1) algorithm that takes one hour to complete is worthless compared to an O(n) algorithm that takes seconds to do the same for reasonable input sizes.
  Reply With Quote
03-31-09, 01:32 PM   #29
Aezay
A Theradrim Guardian
 
Aezay's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2007
Posts: 66
Thanks for the explanation IBLJerry.

I'm a little curious though, can anyone give an example of an algorithm that doesn't scale with the data?
  Reply With Quote
03-31-09, 01:47 PM   #30
Zergreth
A Fallenroot Satyr
 
Zergreth's Avatar
AddOn Author - Click to view addons
Join Date: Oct 2008
Posts: 24
"Determining if a number is even or odd; using a constant-size lookup table or hash table" is the example delivered by Wikipedia.
  Reply With Quote
03-31-09, 04:46 PM   #31
Shadowed
...
Premium Member
Featured
Join Date: Feb 2006
Posts: 387
You guys are vastly over-complicating this, from a fun abstract random curiosity type of question sure, but for practical applications, all you really need to ask yourself is "Am I doing something really stupid?" The majority of the mistakes I see new people make are they create a static table every time a function is loaded instead of once on file load like you see below. Creating options tables only when needed instead of all the time as Slakah mentioned as well.

Code:
function foo()
     local staticColor = { r = 1.0, g = 1.0, b = 1.0 };
end
Where you can shift it up so it becomes

Code:
local staticColor = { r = 1.0, g = 1.0, b = 1.0 };
function foo()
end
So you only create one table instead of the same table every time the function is called.

Eggi touched on this, but always ask yourself what the function is doing. If you're writing a mod for checking if the player has a buff and warning them, efficiency is a good goal but you shouldn't worry about it; on the other hand, if you're writing a mod to monitor the auras of 25 people in a raid during combat, then efficiency should be something you care more about. If you it requires user interface (GUIs, and that kind of thing) or they can't do it in combat then efficiency should be a lot lower on your list.
  Reply With Quote
03-31-09, 07:31 PM   #32
watchout
A Fallenroot Satyr
Join Date: Mar 2008
Posts: 20
More tips:
  • Turn off what you don't need. Think about whether you really always need those 1000 lines of OnEvent/OnUpdate function. Maybe you can split it into smaller functions that you switch on rare events? (like entering/leaving combat or switching gear, etc.)
  • reuse your frames
  • maybe split multiple events on multiple frames so that C-code handles the distribution and you don't have to manually check if it's actually the right event when the handler is called
  • Strings generate their hashes when created - that's pretty fast but it can't hurt to keep string generations at a minimum.
  • Use numbers over strings where possible.
  • Don't create functions that are called only directly (that means not through some table like I did in my example above) and in one place.
  • Memory usually comes cheap, while processor time is expensive.
@Aezay: of course, I just saw it and... just... had to say it... aaah the dark side of the force is beckoning!
  Reply With Quote
04-02-09, 03:05 PM   #33
Aezay
A Theradrim Guardian
 
Aezay's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2007
Posts: 66
If I want to store a list of strings, let's say for some kind of filter, what is the fastest way to do it, store them as keys, or as values?
Storing them as keys looks better code wise, but that doesn't mean it is faster. But based on the previous talk in this thread, I assume that keys is just as fast, if not faster?
Code:
if (tableFilter[name]) then
	frame:Show();
end
Code:
for index, entry in ipairs(tableFilter) do
	if (name == entry) then
		frame:Show();
		break;
	end
end
  Reply With Quote
04-02-09, 03:09 PM   #34
Tekkub
A Molten Giant
 
Tekkub's Avatar
AddOn Author - Click to view addons
Join Date: Dec 2005
Posts: 960
Keys are always faster for that sort of thing. Iterating over the table makes a bunch of function calls.
  Reply With Quote
04-03-09, 03:24 AM   #35
IBLJerry
A Deviate Faerie Dragon
AddOn Author - Click to view addons
Join Date: Dec 2006
Posts: 12
Originally Posted by Tekkub View Post
Keys are always faster for that sort of thing.
Unless you want to sort the keys :-)
  Reply With Quote
04-03-09, 03:56 AM   #36
Tekkub
A Molten Giant
 
Tekkub's Avatar
AddOn Author - Click to view addons
Join Date: Dec 2005
Posts: 960
Which wouldn't be "that sort of thing" (finding out if the value is in the talbe)
  Reply With Quote
04-04-09, 03:39 PM   #37
Aezay
A Theradrim Guardian
 
Aezay's Avatar
AddOn Author - Click to view addons
Join Date: Jul 2007
Posts: 66
To save a function call, many uses next() as the iterater in a for loop, why not do the same for ipairs(), should be easily obtainable using this code. Or is there an iterator function already available for array type tables, like next?
This would probably be quite silly normally, unless it's code run often like in an OnUpdate script.

Code:
local iterator = ipairs(_G);
  Reply With Quote
04-04-09, 03:46 PM   #38
Tekkub
A Molten Giant
 
Tekkub's Avatar
AddOn Author - Click to view addons
Join Date: Dec 2005
Posts: 960
You'd only save one function call out of all the ones made while looping. It'd be better to optimize so that you don't need to iter at all.
  Reply With Quote
04-04-09, 03:46 PM   #39
Shadowed
...
Premium Member
Featured
Join Date: Feb 2006
Posts: 387
Originally Posted by Aezay View Post
To save a function call, many uses next() as the iterater in a for loop, why not do the same for ipairs(), should be easily obtainable using this code. Or is there an iterator function already available for array type tables, like next?
This would probably be quite silly normally, unless it's code run often like in an OnUpdate script.

Code:
local iterator = ipairs(_G);
I think I've seen maybe one or two people use next, I'm not sure I would call it common at all. This gets into premature/unnecessary optimization
  Reply With Quote
04-14-09, 07:27 AM   #40
shiin
A Fallenroot Satyr
Join Date: Feb 2005
Posts: 23
Regarding events, I was always wondering would be the better coding style:
a) Catching all events of one type (i.e. UNIT_BUFF) in one central location and distributing them to the relevant frames (i.e. RaidFrameNumberXY),
b) Having decentralised event handlers for each frame, each listening for all relevant events.

Evidently, variant b) uses more CPU time, since each event would have to be analysed once for each frame, but having frames as independent building blocks seems to be more manageable and extendable.
  Reply With Quote

WoWInterface » Developer Discussions » Lua/XML Help » Efficient LUA code?

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off