9 réponses à ce sujet

[Kato -]

Hi,

One of my favorite hobbies is to study the code written by those I consider as the best coders in the NWN community(in purely alphabetical order, Acaos, Axe, Funky, Lightfoot, ShadoOoW and Whizard, no surprise here, I guess). So, lately, I stumbled on a very long switch wich was broken down into smaller parts(imbricated switches), and I found the idea very instructive and clever. Which makes me wonder: In order to correctly use the concept and get some real benefits from it, how many case statements one should tolerate before deciding to break down the switch? I mean, is it worth to split a 40 case statements switch into 4(or perhaps 2), or would the benefits be real only with giant switches holding hundreds of case statements?
I'm asking this both because I'm writing a loot system wich could possibly benefit from the concept and because I'm always eager to learn and improve my coding skills, so, many thanks for sharing any insight.

Kato

Modifié par Kato_Yang, 06 juin 2012 - 04:48 .

[Lightfoot8]

As a general rule the fewer decisions that have to be made at run time the more efficent the script is. 

Since the switch statment compiles just about the same as the if.. else if.. statments, There is normally no real gain in efficiency in using one over the other.   In breaking up the cases you can limit the maximum number of decisions the script could possibly make at run time.   

as an example with your 40 case switch.  Cases 0 through 39. 

int x = random(40);
switch (x)
{
     case 0:
     case 1:
     case 2:
     ...   
     case 39:
     default :
}   


With the code above 1 to 39 comparisons will be made every time the switch is ran.  
If x = 0;  only 1 comparision is made. 
if x= 39;   40 comparisons are made. 
if x is not in the {0..39} set,  all 40 comparisons are still made and the defualt is then ran.    

Now take the following code.  

int x = random(40);
int y = x/10;

switch (y)
{
  case 0:
          switch(x)
         {
              case 0:
              case 2:
              ...
              case 9:
         } 
         break;

  case 1:
          switch(x)
         {
              case 10:
              case 12:
              ...
              case 19:
       
         } 
         break;

  case 2:
          switch(x)
         {
              case 20:
              case 22:
              ...
              case 29:
       
         } 
         break;

  case 3:
          switch(x)
         {
              case 30:
              case 32:
              ...
              case 39:
       
         } 
         break;
  default :

}
 
In this example the switch will make 2 - 14 comparisons every time the switch is ran.  
2 comparisons when x =0 :   1 in the y switch, and 1  in the x switch.
14 comparisions when x = 39 :  4 in the y switch, and 10 in the x switch. 
4 comparisons when x<0 || x> 39;   (default case). 

now with the : int y = x/10;  we have  add about 7 VM instructions to the compiled code that will get executed every time the script runs.   But since every comparison on the script is about 6 VM instructions, this is no big deal.

Hope that helps.
L8

Note:  The discusion would be entirely different in other languages. the above applies to how nwn handles switches.

Modifié par Lightfoot8, 06 juin 2012 - 01:12 .

[Kato -]

Yes, tyvm L8!

EDIT: I initially thought that switches were faster than if statements, good info once more

Kato

Modifié par Kato_Yang, 06 juin 2012 - 04:35 .

[Leurnid]

*from the cheap seats in the back of the room*

Just to make sure I have grasped this, using 'imbricated switches' is more efficient, and you could use it to break down say 1000 variants into about 3 to 30 comparisons (as opposed to 1 to 1000)?

[Kato -]

Yes, nested switches reduce the number of needed comparisons/checks.


Kato

[Leurnid]

*raises his hand again*

At what point would the number of comparisons/checks become big enough to warrant going from a simple switch to nested switches?

[Kato -]

Well, I guess it depends what the code does and how often it runs. According to my own tests(with the profiler), up to 10 cases seem very fast, the code takes around 1 fourth of a millisecond to execute in a loot system, vs around 1 millisecond with 30 cases(the numbers include the time it takes to create the randomly picked item from ref). I have seen an immense switch broken down in clusters of 25 cases(written by Funky) which was also doing well, but it was in a script wich did not fire often, unlike in a loot system(when many players are on) or a custom on-hit cast spell, where speed is rather important. I remember a reading in the excellent book "Game Coding" by Mike McShaffry where the author mentioned that anything above 50 milliseconds should be avoided, yet I don't know for sure if the rule applies to NWScript...

Kato

Modifié par Kato_Yang, 06 juin 2012 - 11:00 .

[WhiZard]

Kato_Yang wrote...

Well, I guess it depends what the code does and how often it runs. According to my own tests(with the profiler), up to 10 cases seem very fast, the code takes around 1 fourth of a millisecond to execute in a loot system, vs around 1 millisecond with 30 cases(the numbers include the time it takes to create the randomly picked item from ref). I have seen an immense switch broken down in clusters of 25 cases(written by Funky) which was also doing well, but it was in a script wich did not fire often, unlike in a loot system(when many players are on) or a custom on-hit cast spell, where speed is rather important. I remember a reading in the excellent book "Game Coding" by Mike McShaffry where the author mentioned that anything above 50 milliseconds should be avoided, yet I don't know for sure if the rule applies to NWScript...

Kato

NWScript cuts off the script after too many instructions.  So if you put too much into a script it will simply stop mid-way through.  The major time saver is when loops are involved. For example consider the following code:

void main()
{
int n = 0;
while(++n)
  {
 SendMessageToPC(OBJECT_SELF, IntToString(n));
  }
}

This code sends a number count up to 16383.

If instead I structured it as below it would only count to 13106:

void main()
{
int n = 0;
while(TRUE)
  {
  n++;
  SendMessageToPC(OBJECT_SELF, IntToString(n));
  }
}

Now let's start adding if clauses.  All I will add (to the more efficient script) is: if(TRUE) {} inside the loop the number of times indicated in the below table, and then express the number of times the loop is performed before the script is terminated.

#ifs  #loops
0   16383
1   11915
2   9361
3   7709
4   6553
5   5698

Modifié par WhiZard, 07 juin 2012 - 05:15 .

[Kato -]

Wow, very instructive WhiZard, tyvm for the infos. A difference of 4468 allowed loops between 0 and a single if statement! I'll have to revise some of my scripts lol.

Kato

Modifié par Kato_Yang, 07 juin 2012 - 09:48 .

[Leurnid]

Thanks WhiZard, you have delighted my evil-engineer side by building a rig to test to failure.