3
\$\begingroup\$

Hello I made a sieve of Eratosthenes algorithm on x86 assembly using NASM.

The highest number it can take is about 2 million and it takes like 2 seconds to complete.

Here's the code:

section .bss 
    buffer resb 100
    numbers resb 0

section .data
    arrayLength db 0

section .text
    global _start

    _start:
        call getLength
        call initList
        call algorithm
        call printNumbers
        
        exit

        algorithm: 
            mov r10, 0     ;starting index
            mov r11, 2     ;every nth number to be crossed out
            loop3:
                mov rax, [numbers]
                mov rbp, [arrayLength]
                crossOut rax, r10, r11, rbp           ;if this returns 0 it means all non primes are already crossed out   
                jz return               
                call getIndex                           ; get next r10d and r11d
                jmp loop3
            return:
                ret

        getIndex:                 ;gets the next item that isnt already crossed out (0 means not crossed)
            mov rax, [numbers]
            loop2:
                inc r10
                inc r11

                mov r12b, byte [rax + r10]             
                cmp r12b, 0                     
                jnz loop2

                ret

        getLength:
            mov eax, SYSREAD
            mov edi, 1
            mov esi, buffer
            mov edx, 100
            syscall
            stringToNumber buffer         ; returns edi as number
        
            mov rbp, rdi                ; store in ebp
            sub rbp, 2                  ; if user enters 30 then array length should be 28
                                        ; since first array item is 2

            mov [arrayLength], rbp      ; save in pointer
            extern malloc
            call malloc
            mov [numbers], rax          
            ret

        initList:
            mov rbx, 0          ;index
            mov rbp, [arrayLength]
            mov rax, [numbers]
            
            initloop:
                mov byte [rax + rbx], 0

                inc rbx
                cmp rbx, rbp
                jl initloop
            ret

        printNumbers:
            mov rbp, [arrayLength]
            mov r8d, 2          ; value
            mov r9d, 0          ; index
            
            printLoop:
                mov rax, [numbers]
                mov r11b, byte [rax + r9]

                cmp r11b, 0
                je handlePrime
                
                loopend:
                    inc r9d
                    inc r8d
                    cmp r9, rbp        ;return at array length
                    jnge printLoop
                    ret
                    
            handlePrime:
                printNumber r8
                jmp loopend
  
    
    %macro crossOut 4
    xor rdi, rdi     ;edi keeps track of how many numbers were crossed out
                     ;if 0 end loop
    mov rbx, %1     ;array
    add rbx, %2     ;move position to starting index
    mov rax, %3     ;every nth number to be crossed out 

    mov rbp, %4     ; array length
    mov rcx, 0      ;counter
    
    %%loop:

        add rcx, rax
        cmp rcx, rbp
        jge %%exit

        add rbx, rax
        cmp byte [rbx], 0           
        je %%crossout

        jmp %%loop
    %%crossout:
        mov byte [rbx], 1
        inc rdi
        jmp %%loop

    %%exit:
        cmp rdi, 0
%endmacro


;example:
;"123"  -> starting from 1

;1 + 0 * 10  = 1
;2 + 1 * 10  = 12
;3 + 12 * 10 = 123

%macro stringToNumber 1
    mov rdi, 0                 ; number stored here
    mov ebx, %1  
    mov ecx, 0   

    %%loop:
    xor esi, esi
    mov sil, byte [ebx + ecx]
    sub sil, 48

    cmp esi, 9                  ;if this is greater than 9 the string has ended
    jg %%exit

    mov rax, 10
    mul rdi                     ; multiply by 10
    add rsi, rax
    mov rdi, rsi

    inc ecx
    jmp %%loop
    
    %%exit:
%endmacro
\$\endgroup\$
12
  • 1
    \$\begingroup\$ Your program suffers from buffer overrun. See my answer on stackoverflow stackoverflow.com/questions/72502132/… \$\endgroup\$
    – Sep Roland
    Jun 5, 2022 at 21:41
  • \$\begingroup\$ Are you aiming for performance at all? And/or for small/efficient code? There's a lot of really inefficient stuff here, especially stuff like je %%crossout over a jmp %%loop instead of a jne %%loop. And the fact that you're branching at all instead of unconditionally storing; is that an attempt to save cache bandwidth for larger problem sizes, by being read-only for cache lines you don't modify, instead of reading + dirtying it? Or is that just a mistake? If I was going to write an answer, not sure how much CPU performance detail would be relevant. (agner.org/optimize) \$\endgroup\$ Jun 6, 2022 at 2:55
  • \$\begingroup\$ Have you tried writing this in C and looking at optimized compiler output? Since you have silly inefficiencies like that jcc over a jmp, a compiler could show you better way for some things. It wouldn't do major changes, though, except maybe turning malloc + memset(0) into calloc for you. (Also, why malloc? That's the only libc function you use. Unless you use any in printNumber or exit which you forgot to define) \$\endgroup\$ Jun 6, 2022 at 3:33
  • \$\begingroup\$ Also, what CPU did you benchmark it on? e.g. i7-6700k at 4.2 GHz (echo 1000000 | perf stat ./sieve can show you the average CPU frequency while it was running) \$\endgroup\$ Jun 6, 2022 at 3:34
  • 1
    \$\begingroup\$ @user259137: Use perf record --all-user ./a.out / perf report -Mintel to profile clock cycles. Or perf stat --all-user -d. To find the max value that caused a problem for my version; I just ran it under GDB and looked at the value in R11 when it (intentionally) crashed. Note the jc abort check after tzcnt in the sieve outer loop (to implement your getIndex search): if there's no prime in the next 63 to 56 bits of the bitmap, it just bails out because I didn't bother to write a loop. But it bails out to a ud2 instruction that will SIGILL, so I can see the current state in GDB. \$\endgroup\$ Jun 6, 2022 at 17:33

2 Answers 2

3
\$\begingroup\$

vnp has already covered some excellent naming and organizational points. I won’t repeat them.


Your data structure is awkward. You allocate N - 2 bytes for the sieve, saving 2 bytes of memory, at the cost of needing to maintain both a value and index variables in registers, and needing to increment both. If you just allocated the full N bytes, then value and index would be the same, only one variable would be needed.


Crossing out multiples of 2’s means when you cross out multiples of a larger prime, p > 2, you don’t need to cross out 2p since it has already been done. Similarly, crossing out multiples of 3 means when you cross out multiples of a prime p > 3, you don’t have to cross out 3p since that has already been done. In general, crossOut should begin crossing out at p*p. For small prime numbers, this doesn’t save much, but as the primes get larger, the saved work becomes significant.


keeps track of how many numbers were crossed out; if 0 end loop`.

It took me a while to convince myself that this loop termination condition wasn’t flawed. It does work, but it is overly complex and slowing your code down.

First, why does it work? If p is prime, then p*p will never be crossed out by any preceding step. If p*p is less than your sieve limit, you will cross out that value at the very least, and the count will not be zero. If p*p is greater than the sieve limit, then every smaller multiple of p will have been crossed out, and the count will be zero.

So, blindly executing mov byte [rbx], 1 is all that is required. No testing cmp byte [rbx], 0 and no counting. Less memory cycles, less testing and less jumping will significantly improve the speed of the loop. Start the crossOut loop at p*p until that exceeds the sieve length.

\$\endgroup\$
4
  • \$\begingroup\$ ok thanks, but how will i stop the algorithm loop then? If i dont do counting \$\endgroup\$
    – user259137
    Jun 5, 2022 at 18:52
  • \$\begingroup\$ if I do p*p on every iteration isnt that gonna take a lot of perforamcne aswell? \$\endgroup\$
    – user259137
    Jun 5, 2022 at 19:11
  • 2
    \$\begingroup\$ You stop the algorithm loop when p*p exceeds the sieve length. You run the inner crossOut loop starting from p*p and running up to the sieve length. Computing p*p isn’t a performance penalty, especially if you reuse the value calculated in the outer loop for the inner loop’s start, instead of recalculating it. \$\endgroup\$
    – AJNeufeld
    Jun 5, 2022 at 23:33
  • 1
    \$\begingroup\$ This code didn't need separate registers for value and index in the first place in printNumbers. If it wanted to save 2 bytes of dynamic allocation, it could have spent 1 byte of code-size on a displacement in the addressing-mode, like movzx r11d, byte [rax + r8 - 2]. But yes, as it is now, that's a big over-complication, and multiple places need extra code-size (e.g. sub rbp, 2) to deal with the offset so it doesn't pay for itself. Of course, code size can be shared between multiple running processes, but the size saving (or cost) is either 1 or 0 pages. (Almost always 0 pages). \$\endgroup\$ Jun 6, 2022 at 3:01
3
\$\begingroup\$
  • NASM supports local labels. Using .loop instead of loop2, loop3 etc improves readability.

  • getIndex should be getNextPrime.

  • call malloc does not belong to getLength. Do it in initList. BTW, you may as well call calloc, and don't bother to zero-fill the buffer manually.

  • Instead of hand-rolled loops in initList and getIndex consider much more performant rep stosb and rep scasb respectively. Ditto for printNumbers.

  • It seems that you try to avoid linking with libc. There is no reason to do it. getLength may benefit from calling fgets and strtol.

  • What is printNumber? Yet again, I suspect that it does not call printf.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ rep stosb is a fairly efficient memset (Enhanced REP MOVSB for memcpy), but conditional-rep operations like repne scasb don't have any fast-strings support in current CPUs, let alone ERMSB, so they go at 1 iteration per clock at best, unlike an SSE2 search that could easily go 16 bytes per clock. (Or maybe 32 bytes per clock finding a non-zero, but with extra start/end overhead). Twice that with AVX2. (There is no rep scasb, only repe or repne. f3 rep is the same prefix byte as f3 repe, depending on which instruction it's applied to.) \$\endgroup\$ Jun 6, 2022 at 2:35
  • 1
    \$\begingroup\$ Implementing your own int->string and string->int is an interesting exercise in seeing the algorithms for the really basic things that libc code does for you under the hood. And it's not that much code (How do I print an integer in Assembly Level Programming without printf from the c library?). There's a call malloc so apparently they're not really trying to avoid libc, otherwise they'd want mmap or a big BSS buffer. But yes calloc also gives you zeroed memory, usually taking advantage of mmap having zeroed it. \$\endgroup\$ Jun 6, 2022 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.