CodeWars - Assembly Language - Check List For Value

Question

I'm doing assembly language problems on CodeWars, a website with practice problems.

Problem

https://www.codewars.com/kata/545991b4cbae2a5fda000158/train/nasm

Create a method that accepts a list and an item, and returns true if the item belongs to the list, otherwise false.

Solution In C

To give you an idea what the assembly code will be doing.

#include <stdbool.h>
#include <stddef.h>

bool include(const int* arr, size_t size, int item)
{
    int i = 0;
    loop:
    if ( i < size ) {
        if ( arr[i] == item ) {
            return true;
        }
        i++;
        goto loop;
    } 
    return false;
}

Solution In NASM Assembly (Linux x64)

CodeWars provided the 7 lines at the top.

SECTION .text
global include
include:

    ; bool include(const int* arr, size_t size, int item)
    ; sizeof(int) = 4 bytes (32bit)
    ; sizeof(size_t) = 8 bytes (64bit)
    
    ;rdi = &arr    pointer, 8 bytes
    ;   arr[i]          signed int, 4 bytes (dd)
    ;rsi = size    size_t, unsigned int, 8 bytes
    ;edx = item    signed int, 4 bytes
    
    ; Avoid using registers that we need to preserve (RBX, RBP, R12-R15). Else we'd have to push and pop them onto the stack.

    mov rcx, 0      ; unsigned int i = 0;
loop1:
    cmp rcx, rsi    ; if ( i < size ) {
    jae skip_loop
    
    mov r8d, [rdi + 4 * rcx]        ; make a temp variable so we can see this in step debugging
    cmp edx, r8d    ; if ( arr[i] == item ) {
    jne skip_if
    mov rax, 1      ; return true;
    ret
    
skip_if:
    inc rcx         ; i++;
    jmp loop1
    
skip_loop:
    mov rax, 0      ; return false;
    ret

Questions

I'm brand new to assembly. Any feedback on patterns and best practices would be appreciated. For example

• Is there a standard pattern to use when writing loops?
• Is there a standard pattern to use when writing if/elseif/else?
• Are there better word choices and formatting for the labels?

Answer 1

First of all, props for the copious comments, particularly how you included a representation in C. The C representation itself has a signed vs unsigned comparison, which can cause weird bugs when and where you don't expect them, but I'm going to stick to the assembly code itself in this review. I would just recommend declaring the loop counter i as size_t, since that's what the type of the stop condition is.

I assembled your C function using gcc version 10.2.0 with -O3 -march=native, so I'll include the output here so I can walk through it step by step, comparing the two implementations. This is a really good idea, by the way, because working backwards through what the C compiler did helps you see real assembly language, not just practice examples you wrote. Compiler Explorer is a great tool for this.

Anyways, here is my input file.

#include <stdbool.h>
#include <stddef.h>

bool include(const int* arr, size_t size, int item) {
    for (size_t i = 0; i < size; ++i) {
        if (arr[i] == item) {
            return true;
        }
    }

    return false;
}

To assemble it, I use the following command. Note the -masm=intel argument; the default assembly syntax is AT&T for GNU tools.

gcc -S -O3 -march=native -masm=intel -o output.asm input.c

You can filter out auxiliary metadata and its containing labels using the following command.

cat output.asm | sed -E '/^\s+\./d;/^\.L[A-Z]/d'

And here is my output.

include:
        test    rsi, rsi
        je      .L4
        xor     eax, eax
        jmp     .L3
.L8:
        inc     rax
        cmp     rsi, rax
        je      .L4
.L3:
        cmp     DWORD PTR [rdi+rax*4], edx
        jne     .L8
        mov     eax, 1
        ret
.L4:
        xor     eax, eax
        ret

Notice that the first line is already different. In your version, you started by setting the rcx register to 0, using the mov instruction, whereas the compiler output test rsi, rsi. Why?

Well, as you noted, Intel x86-64 Linux assembly programming calling convention dictates that the rsi register contains the second argument to your function, in this case the size of the array. From the Intel x86-64 documentation (pg. 1866), the test instruction performs a logical AND test on its arguments. If the result is zero, it sets the zero flag ZF equal to 1. The following instruction therefore makes sense, since the "jump near if equal" (je) instruction is carried out when the the zero flag is set (ZF=1).

In other words, the subroutine begins by checking whether or not the input array actually contains any items before actually doing anything with it. Note that you weren't checking for this edge case in your original code (nor did you verify the array pointer wasn't NULL), and it's a great example of compilers being awesome. Matt Godbolt (the guy who made Compiler Explorer) has an awesome talk about this kind of stuff that I highly recommend you check out if you like this sort of thing.

Anyways, if you look at the .L4 label, you'll notice it's semantically equivalent to your skip_loop. However, you literally set the rax register (i.e., the return value of the function) equal to zero by moving a 0 into it, whereas the compiler uses the exclusive-or xor instruction on eax with itself, which will obviously always be zero. You're not semantically wrong for doing it the way you did, but you can read this SO post that describes in significant detail why you should opt for the xor eax, eax method. The short version is that it's more efficient, and the longer version is that it's much more efficient, but there are other benefits, like power consumption. That post goes into a lot more detail, though, and it's a great read.

Your loop itself looks okay to me. The compiler used the rax register for the loop counter, which both you and the compiler then used to get the value of the array at the appropriate index. The only real difference between the two versions is that the compiler used an unconditional jump jmp instruction to skip the first part of its main loop, which contained the loop counter increment, whereas your code had that last.

I genuinely don't think this difference has any real impact, because both implementations contain two conditional jumps, which significantly impact performance because they trigger unconditional instruction fetches and involve more advanced processor features like branch prediction, which itself introduces problems via an optimization called speculative execution. (Long story short, optimization is complicated, you won't really know until you profile it, and you probably shouldn't even care about optimization until you have a working something to optimize, but you're "probably" fine.)

Something I found really interesting (although not particularly impactful or world-view shattering), was that believe it or not, creating that temporary variable and then comparing takes exactly as many bytes to encode as the direct comparison the compiler output in my version.

Here is a snippet from the objdump output for your version. (To generate this on your local machine, the command I used after assembling with nasm was objdump -Mx86-64,intel -D -S -s input.o.)

0000000000000005 <loop1>:
loop1:
    cmp rcx, rsi    ; if ( i < size ) {
   5:   48 39 f1                cmp    rcx,rsi
    jae skip_loop
   8:   73 14                   jae    1e <skip_loop>
    
    mov r8d, [rdi + 4 * rcx]        ; make a temp variable so we can see this in step debugging
   a:   44 8b 04 8f             mov    r8d,DWORD PTR [rdi+rcx*4]
    cmp edx, r8d    ; if ( arr[i] == item ) {
   e:   44 39 c2                cmp    edx,r8d
    jne skip_if
  11:   75 06                   jne    19 <skip_if>
    mov rax, 1      ; return true;
  13:   b8 01 00 00 00          mov    eax,0x1
    ret
  18:   c3                      ret    

Now here's a snippet from the output for the compiler's version that contains the comparison operation.

0000000000000011 <include.L3>:
.L3:
    cmp     [dword rdi+rax*4], edx
  11:   39 94 87 00 00 00 00    cmp    DWORD PTR [rdi+rax*4+0x0],edx
    jne     .L8
  18:   75 ef                   jne    9 <include.L8>
    mov     eax, 1
  1a:   b8 01 00 00 00          mov    eax,0x1
    ret
  1f:   c3                      ret   

Notice how in your version, the assignment to a temporary variable takes four bytes. You specified the r8d register as the destination register, so this isn't exactly groundbreaking stuff, but the following comparison instruction required only three bytes to encode:

44 8b 04 8f             mov    r8d,DWORD PTR [rdi+rcx*4]
44 39 c2                cmp    edx,r8d

The compiler's version skipped the intermediate variable assignment, but the resulting instruction required seven bytes to encode.

39 94 87 00 00 00 00    cmp    DWORD PTR [rdi+rax*4+0x0],edx

To explain why those extra zeroes at the end matter, I will borrow once again from this great post which you should definitely read.

Smaller machine-code size [...] is always an advantage: Higher code density leads to fewer instruction-cache misses, and better instruction fetch and potentially decode bandwidth.

To really drive this point home, let us read the conditional jump instruction documentation (pg. 1109 in the combined manual [vols 1-4]):

All conditional jumps are converted to code fetches of one or two cache lines, regardless of jump address or cache-ability.

I now leave this link to the latency numbers every programmer should know for your edification, although it should be noted this document is from 2012. Here's a cool updated version where you can look at the latency numbers by year (including 2020), but I actually just found this myself, so I admit I haven't vetted the source for accuracy. I am including it for completeness nonetheless.

As far as the labels themselves are concerned, since loop1, skip_if, and skip_loop are all logically related to the include subroutine, I would recommend using local labels to more intuitively organize your assembly code. Local labels are particularly useful because the subroutine name serves as a sort of namespace, allowing you to reuse the local label names defined therein. You can see the include version above assembled by gcc uses local labels.

The only recommendation I would make regarding loops is to be wary of using the right conditional jump for your situation. From the documentation:

The terms "less" and "greater" are used for comparisons of signed integers and the terms "above" and "below" are used for unsigned integers.

This isn't pedantry, either. Take for example, the "jump if above or equal" jae instruction in your code. It follows a cmp instruction, which subtracts the second operand from the first and modifies the EFLAGS register accordingly. Specifically, the intermediate sub instruction performs both signed and unsigned subtraction, setting the overflow and carry flags, respectively. However, by using the jae instruction, you are implicitly only checking the carry flag, so hopefully your loop counter and stop conditions are of the same type.

The C standard defines how this should be done, which does help mitigate bugs by both converting as properly and safely as possible, and by providing helpful warnings and even error messages (depending on the compilation strictness settings). Of course, if you're going to be writing assembly language directly, this obviously does not help you.

For reference, the EFLAGS condition codes can be found in Volume 1 Appendix B of the Intel® 64 and IA-32 Architectures Software Developer’s Manuals, and the conditional jumps reference table starts on page 1106 of Volume 2.