We often face such a scenario in writing code:<\/p>\n\n\n\n
our_loop:\n \/\/ some code before\n if (flag):\n do_something()\n else:\n do_something_else()\n \/\/ some code after<\/pre>\n\n\n\nThe
flag<\/code> is usually a constant, for example, an argument (e.g. true\/false; 0\/1) we passed to this function at runtime<\/strong>. The functionsdo_something()<\/code> anddo_something_else()<\/code> may also be some code blocks and they’re almost identical. Well, if we know the flag will definitely not<\/em> change within the loop we can move the conditional statement out of the loop so that the flag will only be tested once.<\/p>\n\n\n\nif (flag):\n our_loop:\n \/\/ some code before\n do_something()\n \/\/ some code after\nelse:\n our_loop:\n \/\/ some code before\n do_something_else()\n \/\/ some code after<\/pre>\n\n\n\nThis is great, except, …, well, it really looks ugly and we’re repeating ourselves. If the code within the loop is large, it makes our binary executable a bit larger (.text section).<\/p>\n\n\n\n
To be concrete, let’s consider the following C++ code that computes the rank of the current value in arr[beg, end):<\/p>\n\n\n\n
int get_rank(int arr[], int beg, int end, int cur, bool desc)\n{\n int rank = 1;\n for (int i = beg; i < end; ++i) {\n if (i == cur)\n continue;\n if (!desc) {\n if (arr[i] < arr[cur])\n rank++;\n }\n else {\n if (arr[i] > arr[cur])\n rank++;\n }\n }\n return rank;\n}<\/pre>\n\n\n\nOne may want to compute the ascending rank or the descending rank of a value in an array\/range. Here the order (asc\/desc) is a runtime constant. However, if it’s a compile-time constant one can avoid repeating themselves by using C++17’s
if constexpr<\/code>:<\/p>\n\n\n\ntemplate<bool desc>\nint get_rank(int arr[], int beg, int end, int cur)\n{\n int rank = 1;\n for (int i = beg; i < end; ++i) {\n if (i == cur)\n continue;\n if constexpr(!desc) { \/\/ requires C++17 or later\n if (arr[i] < arr[cur])\n rank++;\n }\n else {\n if (arr[i] > arr[cur])\n rank++;\n }\n }\n return rank;\n}\n\n\/\/ usage:\n\/\/ int rank = get_rank<false>(arr, beg, end, cur);\n\/\/ or\n\/\/ constexpr bool desc = false; \/\/ or some compile-time constant\n\/\/ int rank = get_rank<desc>(arr, beg, end, cur);<\/pre>\n\n\n\nThis solution combines both efficiency and elegance (thanks to the compiler). But how about the efficiency of the non-templated function (the one with an additional parameter
desc<\/code>)? I wasn’t sure if the compiler would do any sort of optimization. But I do know that modern computer architectures are designed to do a great job in branch prediction. The compiler may also aid in generating branch-friendly (or even branchless) code. So, if the prediction was correct, the fitched instructions for this branch will be kept hot (remaining in the cache and busy running in the CPU pipeline). Otherwise, the fitched instructions by the wrong prediction may be discarded (evicted from the cache) and instructions for the other branch will be fetched. Also, the CPU stalls caused by the pipeline invalidation will make it worse. Luckily, here in this case, the branch condition is constant and therefore the CPU is on our side.<\/p>\n\n\n\nNext, let’s see what the compile can do for us. Compiling this function on Godbolt<\/a> using gcc 12.2 with
-O3<\/code> flag yields the following assembly code:<\/p>\n\n\n\nget_rank(int*, int, int, int, bool):\n movq %rdi, %r9\n movl %edx, %edi\n cmpl %edx, %esi\n jge .L9\n movslq %ecx, %rax\n movl $1, %edx\n leaq (%r9,%rax,4), %r10\n movslq %esi, %rax\n testb %r8b, %r8b\n jne .L8\n.L5:\n cmpl %eax, %ecx\n je .L4\n movl (%r10), %esi\n cmpl %esi, (%r9,%rax,4)\n setl %sil\n movzbl %sil, %esi\n addl %esi, %edx\n.L4:\n addq $1, %rax\n cmpl %eax, %edi\n jg .L5\n movl %edx, %eax\n ret\n.L8:\n cmpl %eax, %ecx ; if (i == cur)\n je .L7\n movl (%r10), %esi\n cmpl %esi, (%r9,%rax,4)\n setg %sil\n movzbl %sil, %esi\n addl %esi, %edx\n.L7: ; for (int i = beg; i < end; ++i)\n addq $1, %rax\n cmpl %eax, %edi\n jg .L8\n movl %edx, %eax\n ret\n.L9:\n movl $1, %edx\n movl %edx, %eax\n ret<\/pre>\n\n\n\nWe can see that
desc<\/code> is only tested once. Cheers! With-O0<\/code> flag it gives<\/p>\n\n\n\nget_rank(int*, int, int, int, bool):\n pushq %rbp\n movq %rsp, %rbp\n movq %rdi, -24(%rbp)\n movl %esi, -28(%rbp)\n movl %edx, -32(%rbp)\n movl %ecx, -36(%rbp)\n movl %r8d, %eax\n movb %al, -40(%rbp)\n movl $1, -4(%rbp)\n movl -28(%rbp), %eax\n movl %eax, -8(%rbp)\n jmp .L2\n.L6:\n movl -8(%rbp), %eax\n cmpl -36(%rbp), %eax\n je .L8\n movzbl -40(%rbp), %eax\n xorl $1, %eax\n testb %al, %al\n je .L5\n movl -8(%rbp), %eax\n cltq\n leaq 0(,%rax,4), %rdx\n movq -24(%rbp), %rax\n addq %rdx, %rax\n movl (%rax), %edx\n movl -36(%rbp), %eax\n cltq\n leaq 0(,%rax,4), %rcx\n movq -24(%rbp), %rax\n addq %rcx, %rax\n movl (%rax), %eax\n cmpl %eax, %edx\n jge .L4\n addl $1, -4(%rbp)\n jmp .L4\n.L5:\n movl -8(%rbp), %eax\n cltq\n leaq 0(,%rax,4), %rdx\n movq -24(%rbp), %rax\n addq %rdx, %rax\n movl (%rax), %edx\n movl -36(%rbp), %eax\n cltq\n leaq 0(,%rax,4), %rcx\n movq -24(%rbp), %rax\n addq %rcx, %rax\n movl (%rax), %eax\n cmpl %eax, %edx\n jle .L4\n addl $1, -4(%rbp)\n jmp .L4\n.L8:\n nop\n.L4:\n addl $1, -8(%rbp)\n.L2: ; for (int i = beg; i < end; ++i)\n movl -8(%rbp), %eax\n cmpl -32(%rbp), %eax\n jl .L6\n movl -4(%rbp), %eax\n popq %rbp\n ret<\/pre>\n\n\n\nwhich suggests
desc<\/code> is tested within each loop.<\/p>\n\n\n\nNow we know that compilers can actually perform this optimization (although it’s not enabled by default), we should be relaxed and fearless to choose our seemingly inefficient but shorter & sweeter code. Cheers again ;)<\/p>\n\n\n\n
See also https:\/\/en.wikipedia.org\/wiki\/Loop-invariant_code_motion<\/a>, https:\/\/en.wikipedia.org\/wiki\/Loop_unswitching<\/a>, http:\/\/www.cs.cmu.edu\/afs\/cs\/academic\/class\/15745-s06\/web\/handouts\/06.pdf<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
We often face such a scenario in writing code: The flag is usually a constant, for example, an argument (e.g. true\/false; 0\/1) we passed to this function at runtime. The functions do_something() and do_something_else() may also be some code blocks and they’re almost identical. Well, if we know the flag will definitely not change within … <\/p>\n