| View previous topic :: View next topic |
| Author |
Message |
Lanthar D'Alton
Joined: 10 Feb 2005
Posts: 100
|
 Posted: Fri Feb 25, 2005 6:10 Post subject: Terrible discovery |
 |
|
So... dguntner questioned my wisdom in using a switch/case instead of if/elseif/elseif... so I decided that rather then explain why, I'd demonstrate by numbers...
except... well, here's a function called by the main() in switchtest, and switchtest2.
| Code: |
void check(int variable)
{
switch(variable)
{
case 0:
{
SetLocalInt(OBJECT_SELF, "sw1", variable);
break;
}
case 1:
{
SetLocalInt(OBJECT_SELF, "sw1", variable);
break;
}
...
case 9999:
{
SetLocalInt(OBJECT_SELF, "sw1", variable);
break;
}
}
}
|
here's the main() from switchtest
| Code: |
void main()
{
int i=0;
for(i; i<100; i++)
check(i);
}
|
here's the main() from switchtest2
| Code: |
void main()
{
int i=0;
for(i=5000; i<5100; i++)
check(i);
}
|
Both test scripts should result in O(100). However, switchtest2 never finished. It TMId. Even worse... I made 2 if/else if/else if test scripts in the same way... the check function was different:
| Code: |
void check(int variable)
{
if(variable==0)
{
SetLocalInt(OBJECT_SELF, "if1", variable);
}
else if(variable==1)
{
SetLocalInt(OBJECT_SELF, "if1", variable);
}
else if(variable==2)
{
SetLocalInt(OBJECT_SELF, "if1", variable);
}
....
else if(variable==9999)
{
SetLocalInt(OBJECT_SELF, "if1", variable);
}
}
|
well, here is the result as measured by profiler:
| Code: |
switchtest (R2) 0.001618S iterations=99
switchtest2 (R2) 0.006961S iterations=5+
ifelsetest (R2) 0.001668S iterations=99
ifelsetest2 (R2) 0.006134S iterations=4+
|
Both switchtest2 and ifelsetest2 TMIed. The switchtest made it to one higher number than the if/elseif test.
So... guess switches are ever so slightly faster... ever so slightly more efficient... and ever so moronically coded without a map lookup behavior that makes a switch statement really worthwhile.
-Lanthar |
|
| Back to top |
|
 |
dguntner
Joined: 31 Dec 2004
Posts: 116
|
| Posted: Fri Feb 25, 2005 6:43 Post subject: Re: Terrible discovery |
|
|
| Lanthar D'Alton wrote: | | So... dguntner questioned my wisdom in using a switch/case instead of if/elseif/elseif... so I decided that rather then explain why, I'd demonstrate by numbers... |
Um, just for the record, I wasn't questioning the "wisdom" of anything - I just wanted to know why you preferred one over the other.  People generally have reasons why they prefer one over the other. You had made a statement that if...else if statments were much slower than switch/case sets. I don't have that much exposer with switch/case so I have no real basis for comparison. But I haven't noticed if...else being all that slow. Thus, my inquiry.
| Quote: |
So... guess switches are ever so slightly faster... ever so slightly more efficient... and ever so moronically coded without a map lookup behavior that makes a switch statement really worthwhile. |
Er, can I have a translation of that last sentence? 
--Dave |
|
| Back to top |
|
|
Lanthar D'Alton
Joined: 10 Feb 2005
Posts: 100
|
| Posted: Fri Feb 25, 2005 7:49 Post subject: More fun efficiency code... |
|
|
Here are a few more things about efficiency for those not so keyed to it...
two scripts:
strcompare
| Code: |
void main()
{
int i=0;
for(i=0; i<8191; i++)
check(i);
SendMessageToPC(GetLastUsedBy(), "strcompare done");
}
void check(int variable)
{
if("123"=="abc")
1;
}
|
The code I used for ints (main was same as above):
intcompare
| Code: |
void check(int variable)
{
if(1==variable)
1;
}
|
That strcompare one will run precisely 1 too many commands for nwn... causing a TMI error, AND sending the message anyway... oddly the intcompare one also TMIs but never sent the message. Both scripts do complete if I change the for(...) to only go to 8190.
Anyway, that's just something I always wondered... how many instructions are too many. I'm not surprised that it comes rather close to a power of 2 in the loop (8192)...
As for the importance of running this test... well, it gave me efficiency results that are very good to demonstrate why using ints is better than using FindSubString or any of that.
| Code: |
intcompare : 0.007793 per call
strcompare : 0.037566 per call
|
So... Comparing 3 letters to 3 other letters eats ... 4.82 times the cpu as comparing 2 integers.
Anyway, that's just a bit of example to explain why we programmers don't like to run string comparisons unless we absolutely have to.
-Lanthar |
|
| Back to top |
|
|
Grinning Fool
Joined: 12 Feb 2005
Posts: 264
|
| Posted: Fri Feb 25, 2005 8:03 Post subject: |
|
|
| At least switches remain more aesthetically pleasing... |
|
| Back to top |
|
|
Grinning Fool
Joined: 12 Feb 2005
Posts: 264
|
| Posted: Fri Feb 25, 2005 8:07 Post subject: |
|
|
| Quote: | | Er, can I have a translation of that last sentence? |
C/C++ compilers will convert switch statement into a map lookup -- I forget the exact details, but the end result is that a switch statement (when properly optimized) will not check every condition in the list the same way that if/else if/else if/else will do. |
|
| Back to top |
|
|
dguntner
Joined: 31 Dec 2004
Posts: 116
|
| Posted: Fri Feb 25, 2005 8:52 Post subject: |
|
|
Thanks for the rundown, both of you. I still prefer to do things in a way that is easier for the end user (most people can remember BALOR, for example, but how many are going to remember what number that is when they're typing it in because they want to make someone look like a balor? ), but you've got good points there. So I can see where the preference comes from, and I can see where there are going to be times when using the numeric code is going to be preferable to using a string.
--Dave |
|
| Back to top |
|
|
Lanthar D'Alton
Joined: 10 Feb 2005
Posts: 100
|
| Posted: Fri Feb 25, 2005 8:59 Post subject: Why we like using switch statements |
|
|
Imagine a long vine with leaves with increasing number values (but with some numbers missing) all along it. To get to the leaf you want, you must go along the vine and check the value of each leaf and keep going if it's not the one you want. This means that using if/else if/else if requires the total average number of comparisons you make must be
number_of_leaves / 2.0
This is notated by us programmers as O(n/2).
Now, imagine a tree... which only ever splits into two branches at branch points. Also, there's always a leaf at ever branching point. Now consider that the leaves are kept in order such that always following the left branch leads you to a leaf with a lower number, and taking the branch on the right branch will always take you to a higher numbered leaf. Ideally, the leaf at the base of the tree will be the leaf closest to the middle of the lowest and highest. This is getting to be a bit complex, but we're almost done... Now, every time you reach another branching point as you climb the tree, you've narrowed your search by a power of two...
Maybe I should try explaining this like a number guessing game... i.e. you have 10 guesses to get the right number between 1 and 1000, and I'll tell you higher or lower based on your guesses. What will your guesses be?
(say my chosen number is 657)
You will say:
500
750 (250 diff)
625 (125 diff)
688 (63 diff)
656 (31 diff)
671 (15 diff)
664 (7 diff)
661 (3 diff)
658 (3 diff)
657 (1 diff)
and you have it. You guessed by going up or down by half the last amount and it took you 10 guesses. Switch cases work the same way. Whereas if/else if/else if would've taken 657 guesses, the switch case only took 10. That's actually not even as good as it can be.. because at every level of guessing, the chances you will get it right double... anyway, in the end, you wind up with the number of average searches taking log(number of choices) attempts to get the number you want.
so... if nwscript did it right, switch/case calls would take log n comparisons to get to the code it needs to run... and if/else if/else if calls would take n calls.
Sadly, they didn't do it right... it seems that switch/case winds up replaced with if/elses... *shrugs*
Now you see why it's such a terrible discovery.
-Lanthar
a link for you c++ folks with an excellent in depth explanation:
http://lists.gnu.org/archive/html/texmacs-dev/2003-11/msg00042.html |
|
| Back to top |
|
|
dguntner
Joined: 31 Dec 2004
Posts: 116
|
| Posted: Fri Feb 25, 2005 8:59 Post subject: |
|
|
[quote="Grinning Fool"] | Quote: |
C/C++ compilers will convert switch statement into a map lookup -- I forget the exact details, but the end result is that a switch statement (when properly optimized) will not check every condition in the list the same way that if/else if/else if/else will do. |
Question: Will switch/case sets work with strings, or are they all numeric? I.E., will something like
switch (variable)
case "somestring"
{blah}
Work? Never tried it, but I'm curious. If it does work, I wonder if you get the speed improvements over if..else if.. that you get with using switch/case on integers....
--Dave |
|
| Back to top |
|
|
Lanthar D'Alton
Joined: 10 Feb 2005
Posts: 100
|
| Posted: Fri Feb 25, 2005 9:09 Post subject: No, that's pointless... |
|
|
Switches give gains only for numeric comparisons. Comparing strings requires that they be compared every time, or hashed by the compiler(turned into a number by a function of some kind that always gives unique value despite length differences etc... never perfect).
I don't know of any compilers that actually allow it... nwscript will give you this error :
2/25/2005 1:04:13 AM: Error. 'switchtest3' did not compile.
switchtest3.nss(13): ERROR: NON INTEGER EXPRESSION WHERE INTEGER REQUIRED
when given this code :
| Code: |
void check(string variable)
{
switch(variable) //this is line 13 where the error is.
{
case "ABC":
{
SetLocalInt(OBJECT_SELF, "sw1", variable);
break;
}
case "123":
{
SetLocalInt(OBJECT_SELF, "sw1", variable);
break;
}
case "XYZ":
{
SetLocalInt(OBJECT_SELF, "sw1", variable);
break;
}
}
}
|
-Lanthar |
|
| Back to top |
|
|
Grinning Fool
Joined: 12 Feb 2005
Posts: 264
|
| Posted: Fri Feb 25, 2005 9:16 Post subject: |
|
|
Someting you may want to consider, if readability is the concern, is this:
| Code: |
const int MONSTER_BUGBEAR = 1;
const int MONSTER_ORC = 2;
const int MONSTER_WYRM = 3;
....
switch (nMonster) {
case MONSTER_BUGBEAR:
...
break;
case MONSTER_BUGBEAR:
...
break;
case MONSTER_WYRM:
...
break;
default:
...
break;
}
|
|
|
| Back to top |
|
|
Primogenitor
Joined: 08 Jan 2005
Posts: 88
|
| Posted: Fri Feb 25, 2005 9:36 Post subject: |
|
|
And while we are on the topic of if vs switch.
This is valid code
| Code: |
if(X==5)
{
int A = X;
A = A*2
X = A;
}
|
but this isnt
| Code: |
switch(X)
{
case 5:
int A = X;
A = A*2
X = A;
break;
}
|
because it wont let you define new variables inside the switch statment. (see pre-edit at bottom) One solution would be:
| Code: |
int A;
switch(X)
{
case 5:
A = X;
A = A*2
X = A;
break;
}
|
but thats not all that pretty, and separates the variabled declaration from where its actually used.
The other solution is:
| Code: |
switch(X)
{
case 5:
{
int A = X;
A = A*2
X = A;
break;
}
}
|
Pre-Edit: Or at least that used to be the case, just when to test it and it looks like bioware actually fixed this bug in 1.65, so now both solutions work and the original. |
|
| Back to top |
|
|
dguntner
Joined: 31 Dec 2004
Posts: 116
|
| Posted: Fri Feb 25, 2005 11:10 Post subject: Re: Why we like using switch statements |
|
|
| Lanthar D'Alton wrote: |
Sadly, they didn't do it right... it seems that switch/case winds up replaced with if/elses... *shrugs*
Now you see why it's such a terrible discovery. |
So you're saying that what Bioware ended up doing was internally a bunch of if/elses when you use switch/case?
Eeeeeew. Particulary now that I'm following how it works (thanks for the great examples) and you've got me sold on the idea that they're better. 
I suppose they're still better to use just the same?
--Dave |
|
| Back to top |
|
|
dguntner
Joined: 31 Dec 2004
Posts: 116
|
| Posted: Fri Feb 25, 2005 11:11 Post subject: |
|
|
| Grinning Fool wrote: | Someting you may want to consider, if readability is the concern, is this:
| Code: |
const int MONSTER_BUGBEAR = 1;
const int MONSTER_ORC = 2;
const int MONSTER_WYRM = 3;
....
switch (nMonster) {
case MONSTER_BUGBEAR:
...
break;
case MONSTER_BUGBEAR:
...
break;
case MONSTER_WYRM:
...
break;
default:
...
break;
}
|
|
Hey, I *like* that. I hope Lanther can be persuaded to do it that way.
--Dave |
|
| Back to top |
|
|
NoMercy
Joined: 03 Jan 2005
Posts: 123
Location: UK
|
| Posted: Fri Feb 25, 2005 14:22 Post subject: |
|
|
Some languages (like php) support strings in switch cases, it's highly likely that when the strings given are constants:
| Code: | switch ( sName )
{
case: "alfred": somecode(); break;
case: "fred": somecode(); break;
case: "fiona": somecode(); break;
case: "fibble": somecode(); break;
case: "tom": somecode(); break;
} |
The whole thing is converted to a tree, if the first letter is f, then only compare for fred, fiona and fibble, if the next letters an r, it's fred, if not check the 3rd letter for an o, if so it's fiona, if not fibble.
The checking to see what each character is, would probably be done in the same way as a normal switch statement for intergers.
Definately wouln't mind switch( string ) as a feature for NWN2.. in the mean time there might be a few programs which can convert them into the equliviant if/else structure :)
... One thing came to mind, what's Torlack's NSS compilers preformance on switch() statements?
... Binary Search, that's the term I was looking for earlier :)
Last edited by NoMercy on Sat Feb 26, 2005 1:21; edited 1 time in total |
|
| Back to top |
|
|
dguntner
Joined: 31 Dec 2004
Posts: 116
|
| Posted: Fri Feb 25, 2005 22:01 Post subject: |
|
|
| NoMercy wrote: |
... One thing came to mind, what's Torlack's NSS compilers preformance on switch() statements? |
That's a really good question. Hadn't even thought of that. Torlack hasn't updated in ages, so it doesn't work with SoU/HotU, but the PRC group took it over and released the compiler. I use that compiler for my module (I never bother with Build/Compile Scripts in the toolset anymore.
I can't try Lanthar's test with the two scripts that he used because no one has ported the profiler plugin to Linux. Lanthar, have you tried using the PRC compiler on your test module to see what happens when you run those two scripts? It's at:
http://nwvault.ign.com/Files/other/data/1098057351000.shtml
in case you don't currently use it and want to try it out. Any chance you could be persuaded to give it a shot? It'd be interesting to see if they handle switch/case differently than Bioware did....
--Dave |
|
| Back to top |
|
|
|
|
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 vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
