Runtimes 1

So I’ve been doing a lot of DSA questions

In preparation for coding interviews I’ve been studying a lot of data structures and algorithms problems. The main goal when solving these problems is to work out a solution that has low time and space complexity. However when you submit questions on a online judge such as Leetcode, you tend to notice that some minor changes in your code, such as the order or way you write out if statements, can impact your runtime through the judge. Most of the time, this is not useful information. The judge will give you different runtimes for the exact same code, that’s just how timing code works, some runs will be faster than others. But deep down I always wondered, if you broke it down to the bytecode, would there be a noticeable difference between some lines of code that don’t seem very different at a high level?

Combo inequality vs two inequalities combined with an and operator

x < y < z v.s. x < y and y < z

At a high level, these are the same. But when we use Godbolt to dive deeper and look at the bytecode, we will see that there are some differences.

For the first case, x < y < z, we can represent it with the following code snippet:

def compare(target, lower, upper):
    if lower < target < upper:
        return True

The second case, x < y and y < x$`:

def compare(target, lower, upper):
    if lower < target and target < upper:
        return True

Now we look at the bytecode for the first case:

 2 LOAD_FAST                1 (lower)
 4 LOAD_FAST                0 (target)
 6 SWAP                     2
 8 COPY                     2
10 COMPARE_OP               2 (<)
14 POP_JUMP_IF_FALSE        5 (to 26)
16 LOAD_FAST                2 (upper)
18 COMPARE_OP               2 (<)
22 POP_JUMP_IF_FALSE        3 (to 30)

24 RETURN_CONST             1 (True)

26 POP_TOP
28 RETURN_CONST             0 (None)
30 RETURN_CONST             0 (None)

And the bytecode for the second case:

 2 LOAD_FAST                1 (lower)
 4 LOAD_FAST                0 (target)
 6 COMPARE_OP               2 (<)
10 POP_JUMP_IF_FALSE        7 (to 26)
12 LOAD_FAST                0 (target)
14 LOAD_FAST                2 (upper)
16 COMPARE_OP               2 (<)
20 POP_JUMP_IF_FALSE        1 (to 24)

22 RETURN_CONST             1 (True)

24 RETURN_CONST             0 (None)
26 RETURN_CONST             0 (None)

The first thing that jumps out are the extra SWAP and COPY instructions in the first case. To compensate for not having two occurrences of the target parameter, the code will make a copy of target to use in the 18 COMPARE_OP instruction.

Because of the extra SWAP and COPY instructions, the first COMPARE_OP and POP_JUMP_IF_FALSE instructions occur earlier in the second case than the first case.

In essence, the AND operator doesn’t make any extra work for the virtual machine, but omitting a second target in the python code does as the virtual machine needs to make a copy of it for the comparison operation.

The actual runtime trade off is negligible when running timeit, it’s random which one of the two code samples executes faster. For conceptual simplicity, I’ll stick to writing these types of statements with the combo operator, but it’s interesting to know that it makes just a tiny bit more work for the virtual machine.