+ open.mp forum (https://forum.open.mp)
-- Forum: SA-MP (https://forum.open.mp/forumdisplay.php?fid=3)
--- Forum: Tutorials (https://forum.open.mp/forumdisplay.php?fid=37)
--- Thread: The internals of switch and chained else ifs and which one should you use (/showthread.php?tid=322)
The internals of switch and chained else ifs and which one should you use - kristo - 2019-04-17
The internals of switch and chained else ifs and which one should you use
This tutorial takes a look into how if and switch statements work on the assembly level and helps determine, where to use a switch and where to prefer chained else ifs. I decided to write this tutorial, because one of the topics I am about to address is a semi-common issue and currently there is no good place to refer to when it comes to it. In addition to that, the research I did for this tutorial helped me understand the AMX structure quite a bit more than I used to before.
The internals
I used the -a flag to generate the assembly of two simple snippets of code that perform the same task, one using switch and the other using chained else ifs. I also took the time to rewrite them in a more human-readable form (using variable names instead of raw addresses, named labels instead of numbered ones prefixed with l., etc.) and to document them. It is worth noting that while the rewritten assembly is valid, it does not currently compile due to a compiler bug related to forward jumps.
Chained else ifs
PHP Code:
new val;
if (val == 1) {
? ?// do something here
} else if (2 <= val <= 4) {
? ?// do something here
} else {
? ?// do something here
}
For the sake of simplicity I used the form 2 <= val <= 4 instead of val >= 2 && val <= 4 for the range check. If written the other way, the code would use 7 jump instructions instead of 4 and keeping track of the instructions would be more difficult. It would also be a tiny bit slower since it would have to load the value of val to the primary register one more time.
When using chained else ifs, the assembly contains the AMX instructions for each individual check. If the check fails, it jumps to the next check, otherwise it jumps to the end of the chain. Here is the assembly equivalent to this code:
PHP Code:
new val;
// if (val == 1)
#emit LOAD.S.pri ? ?val ? ? ? ? // load the value of val to the primary register
#emit EQ.C.pri ? ? ?1 ? ? ? ? ? // compare the value in the primary register to constant 1: they must be equal; store the result in the primary register
#emit JZER ? ? ? ? ?range ? ? ? // if the result of the comparison is false, jump to "range" to perform the next check
// do something here
#emit JUMP ? ? ? ? ?done ? ? ? ?// everything is done, jump to "done"
// else if (2 <= val <= 4)
range:
#emit CONST.pri ? ? 2 ? ? ? ? ? // store the constant value 2 in the primary register
#emit LOAD.S.alt ? ?val ? ? ? ? // load the value of val to the alternate register
#emit SLEQ ? ? ? ? ? ? ? ? ? ? ?// compare the values in the registers to eachother: 2 (primary) must be less than or equal to val (alternate); store the result in the primary register
#emit PUSH.pri ? ? ? ? ? ? ? ? ?// load the value to the primary register (the result of the comparison) in the stack
#emit CONST.pri ? ? 4 ? ? ? ? ? // store the constant value 4 in the primary register
#emit SGEQ ? ? ? ? ? ? ? ? ? ? ?// compare the values in the registers to eachother: 4 (primary) must be greater than or equal to val (alternate); store the result in the primary register
#emit POP.alt ? ? ? ? ? ? ? ? ? // load the value of the first comparison from the stack to the alternate register
#emit AND ? ? ? ? ? ? ? ? ? ? ? // check if both of the comparisons were true by checking if both registers contain a non-zero value
#emit JZER ? ? ? ? ?otherwise ? // if the result of the comparison is false, jump to "otherwise"
// do something here
#emit JUMP ? ? ? ? ?done ? ? ? ?// everything is done, jump to "done"
// else
otherwise:
// do something here
// no jump needed since "done" is just after this code
done:
If the value of val is 1, the code uses four instructions:
PHP Code:
LOAD.S.pri? val
EQ.C.pri? ? 1
JZER? ? ? ? range ; the jump does not happen, but the instruction is still used
JUMP? ? ? ? done
If the value of val is 2, 3 or 4, the code uses 13 instructions:
PHP Code:
LOAD.S.pri? val
EQ.C.pri? ? 1
JZER? ? ? ? range
CONST.pri? ?2
LOAD.S.alt? val
SLEQ
PUSH.pri
CONST.pri? ?4
SGEQ
POP.alt
AND
JZER? ? ? ? otherwise ; the jump does not happen, but the instruction is still used
JUMP? ? ? ? done
If the value is not matched by any of the previous checks, the code uses 12 instructions:
PHP Code:
LOAD.S.pri? val
EQ.C.pri? ? 1
JZER? ? ? ? range
CONST.pri? ?2
LOAD.S.alt? val
SLEQ
PUSH.pri
CONST.pri? ?4
SGEQ
POP.alt
AND
JZER? ? ? ? otherwise
The longer your chain is and the more failed checks there are, the more instructions the code uses. Each failed single value check adds 3 instructions and each failed range check adds 9 instructions.
switch
PHP Code:
new val;
switch (val) {
? ?case 1: {
? ? ? ?// do something here
? ?}
? ?case 2 .. 4: {
? ? ? ?// do something here
? ?}
? ?default: {
? ? ? ?// do something here
? ?}
}
When using switch, the compiler generates a case table that contains the value and jump address for every single case, including the default case. Here is the assembly equivalent to this code:
PHP Code:
new val;
#emit LOAD.S.pri ? ?val ? ? ? ? // load the value of val to the primary register
#emit SWITCH ? ? ? ?casetable ? // jump to the case table
// case 1:
single:
// do something here
#emit JUMP ? ? ? ? ?done ? ? ? ?// everything is done, jump to "done"
range:
// do something here
#emit JUMP ? ? ? ? ?done ? ? ? ?// everything is done, jump to "done"
otherwise:
// do something here
#emit JUMP ? ? ? ? ?done ? ? ? ?// everything is done, jump to "done"
casetable:
#emit CASETBL
// default:
#emit CASE ? ? ? ? ?4 otherwise // the amount of case table items; the jump address of "default"
// case 1:
#emit CASE ? ? ? ? ?1 single ? ?// the value and jump address of the case
// case 2 .. 4:
#emit CASE ? ? ? ? ?2 range
#emit CASE ? ? ? ? ?3 range
#emit CASE ? ? ? ? ?4 range
done:
Whatever the value of val is 1, the code always uses just three instructions:
PHP Code:
LOAD.S.pri? val
SWITCH? ? ? casetable
JUMP? ? ? ? done
The SWITCH instruction jumps to the case table, performs a linear search on the cases and jumps to the correct one. If the search does not find a matching case, it jumps to the default case instead. It is similar to the behaviour of chained else ifs, but since it is done in native code instead of using AMX instructions, the performance is a lot better.
When NOT to use switch?
Large ranges
As seen before, case tables can only use single values as cases, which means that if you use a range of 10000 elements in your switch, the compiler will have to write 10000 entries to the case table and the runtime will have to search through 10000 entries. Using the following benchmarking script I determined that the runtime performance of a case table becomes worse than the one of a single a <= x <= b check at around 30 entries.
PHP Code:
#define MAX 30
#define ITERATIONS 1000000
new tick = GetTickCount();
for (new i; i < ITERATIONS; i) {
? ?switch ((i % MAX) 1) {
? ? ? ?case 1 .. MAX: {}
? ?}
}
printf("switch: %i", GetTickCount() - tick);
tick = GetTickCount();
for (new i; i < ITERATIONS; i) {
? ?if (1 <= (i % MAX) 1 <= MAX) {}
}
printf("if: %i", GetTickCount() - tick);
However, runtime performance is not the biggest issue. As seen from this forum topic, the amount of time it takes for the compiler to generate large case tables can be so long that it seems for the user that the compiler has ran into an infinite loop. Even ranges small enough to only have a small impact on the compilation time (for example, 1000 elements) can eventually make the compilation process painful if the delays stack up.
Floating point values
When using switch with floating point values, the case table must also contain every single value within the range. The step between two cases grows as the values grow, but it starts at the smallest possible floating point value in the IEEE754 specification, which is 1.4E-45. This means that each entry differs from the previous and next one by just 0.0000000000000000000000000000000000000000000014.
Some examples of ranges with the respective amounts of case table elements:
Code:
|? ? ? ? ? ? ? ? ? ? ? ?Range? ? ? ? ? ? ? ? ? ? ? ?| Amount of entries |
|---------------------------------------------------|-------------------|
| 0.0 .. 0.0000000000000000000000000000000000000001 |? ? ? ?71363? ? ? ?|
|? ? ? ? ? ? ? ? ? ? 1.0 .. 1.01? ? ? ? ? ? ? ? ? ? |? ? ? ?83887? ? ? ?|
|? ? ? ? ? ? ? ? ? ?10.0 .. 10.1? ? ? ? ? ? ? ? ? ? |? ? ? ?104859? ? ? |
|? ? ? ? ? ? ? ? ? 100.0 .. 101.0? ? ? ? ? ? ? ? ? ?|? ? ? ?131073? ? ? |
|? ? ? ? ? ? ? ? ?1000.0 .. 1010.0? ? ? ? ? ? ? ? ? |? ? ? ?163841? ? ? |
|? ? ? ? ? ? ? ? 10000.0 .. 10100.0? ? ? ? ? ? ? ? ?|? ? ? ?102401? ? ? |
|? ? ? ? ? ? ? ?100000.0 .. 101000.0? ? ? ? ? ? ? ? |? ? ? ?128001? ? ? |This test should be enough to show that using switch with floating point values relevant in the context of SA-MP (coordinates, health, etc.) is completely unreasonable.
When to use switch?
I would say that everywhere where there are chains of comparisons against constant values. I have seen people saying that switch is faster no matter what and using a switch with two cases is much faster than an if-else. However, their runtime performance is about the same and where an if and an else make more sense, they should be used instead.
Tips and tricks
Using switch with floatcmp to compare floating point values
Comparison operators for variables with the Float tag are overloaded to use the floatcmp native instead of comparing them with AMX instructions. When comparing floating point values to eachother and having different outcomes depending of if one of the values is larger than the other or they are equal, you can save a floatcmp call by comparing them using switch instead. floatcmp returns 0 if the values are equal, 1 if the first value is larger and -1 if the second value is larger, so the following snippets of code are equivalent, but the second one performs better:
PHP Code:
if (a > b) { // floatcmp called implicitly
? ?// a is larger than b
} else if (a < b) { // floatcmp called implicitly
? ?// a is smaller than b
} else {
? ?// a and b are equal
}
PHP Code:
switch (floatcmp(a, b)) {
? ?case 1: {
? ? ? ?// a is larger than b
? ?}
? ?case -1: {
? ? ? ?// a is smaller than b
? ?}
? ?case 0: {
? ? ? ?// a and b are equal
? ?}
}
Using switch to compare strings
Comparing strings with strcmp has been notorious being both slow and tedious for a long time. Although most of that bad reputation came when ZCMD became the goto command processor and strcmp is still very useful elsewhere, there is a grain of truth in every joke. When comparing a string to a long chain of other strings, comparing their hashes would be more efficient and also convenient due to the ability to use switch, because the hashes are in the form of integers. The PAWN language does not support such thing natively, but y_stringhash from YSI does just the job. According to Y_Less? tests, comparing strings using hashes becomes more efficient than using strcmp at around 10 comparisons. More information about y_stringhash and its usage can be found from this topic.
PHP Code:
if (!strcmp(number, "one")) {
} else if (!strcmp(number, "two") || !strcmp(number, "three")) {
} else {
}
PHP Code:
switch (YHash(number)) {
? ?case _H<one>: {
? ?}
? ?case _H<two>, _H<three>: {
? ?}
? ?default: {
? ?}
}
Credits
- Yashas for the excellent AMX Assembly documentation.
- Y_Less for reviewing the tutorial prior to me publishing it.
- Users of the SA-MP Discord for productive conversations on this topic.