if(!x) is slower than if(x){}else

ID:2834439
 
Nov 12 2022, 1:12 am (Edited on Nov 12 2022, 12:39 pm)
BYOND Version:514
Operating System:Windows 10 Pro
Web Browser:Firefox 106.0
Applies to:DM Language
Status: Open
Issue hasn't been assigned a status value.
Descriptive Problem Summary:
if(!x) is slower than if(x){}else

Numbered Steps to Reproduce Problem:

Code Snippet (if applicable) to Reproduce Problem:
/proc/main()
 var/count = 0
 var/n = null
 var/x = 0

 // your setup code here

 sleep(1)

 var/start = world.tick_usage
 while (world.tick_usage - start < 100)
  count += 1
  // Uncomment whichever you want to test
  // if (n) {} else { x++; }
  // if (!n) { x++; }

 world.log << count


Expected Results:
These should be equivalent in speed, as they are equivalent in functionality. While it's not surprising that `isnull` would be faster than `!`, these are identical in behavior.

Actual Results:
if(n){} is consistently about 10% faster.

Equivalent testing gives results of 4,994,761 iterations with the inverted-if, and 4,559,987 iterations with isnull when the timescale is in a full second.
Nov 12 2022, 4:02 pm (Edited on Nov 12 2022, 4:14 pm)
These should be equivalent in speed, as they are equivalent in functionality.

They are not equivalent in functionality, unless you are expecting the compiler to optimize your code for you.

if(n){} else {x++;}



access n (push)
cndjmp else (pop)
case:
jmp end
else:
postinc x (push) (pop)
end:
return



if(!n) {x++;}



access n (push)
lnot (pop) (push)
cndjmp end (pop)
case:
postinc x (push) (pop)
end:
return


Not BYOND's exact bytecode, but the naive compilation would have an extra operation, push and pop for the !n case, while the n case would just have a jump. As jumps would be implemented as numeric offsets in most virtual machines, they'd be less costly than just about anything else.

Modern programming languages might have optimization that look for cases with redundant branching, and optimize them into the simpler pattern. DM has very little of this kind of optimization. A modern programming language would offer you a different pattern than the one you wrote. DM hardly ever does that.
Nov 12 2022, 4:19 pm
unless you are expecting the compiler to optimize your code for you.

Yes. Basic language constructs being unnecessarily slower than equivalent language constructs is a bug.
Nov 12 2022, 4:29 pm (Edited on Nov 12 2022, 4:34 pm)
I think I just disagree with you on your use of the word equivalent here. They are only equivalent as high level patterns. They are not equivalent in function because BYOND's compiler lacks the feature of pattern substitution in this case.

When you look at the extra lnot operation, and additional stack/heap management of the second pattern, they really are not equivalent at all.
Nov 12 2022, 5:42 pm
It's not a bug, just like it's not a bug that different algorithms that produce the same result can perform differently. It is, however, a relatively simple compiler optimization to add, at least for the trivial case of just negating the entire condition.
Nov 13 2022, 12:11 am
Yeah, I've moved this to feature requests. Ter is right that the compiler not recognizing the equivalent pattern is just a missing feature.

There are also more complex ways pattern equivalency can come up: for instance, (!a || !b) is logically the same as !(a && b) but it might not be trivial for the compiler to make a leap from one to the other. And there are cases where the patterns aren't the same, like (!a || b) vs. !(a && !b) where they have completely different meanings because || and && aren't strictly boolean.

BYOND 515 introduced a little bit of pattern recognition in the new optimizations for expressions like (a+1)*(a+1), where it recognizes a+1 is a repeated sub-expression for this specific case of squaring it. Importantly, the expression has no potential for side effects, which also means list access can't be optimized in this way because of operator overloads. (At least, it can't be done currently. In the future I do plan to have type checking see if a list is expected to be an actual list or something else.) More complex sub-expression recognition is a tricky beast but could be really helpful for certain types of expressions.

Anyway, on the topic of this specific request, it is doable as a future optimization to modify if() in this way.
Jan 8 2023, 2:56 pm
BYOND's compiler is quite basic and this leads to a lot of runtime overhead performing redundant operations. Which is a shame, but I gather the time and money available for Lummox to work on BYOND is not very high.