Assembly program that finds second largest value in array

Question

I wrote a assembly program that finds the max value in an array, but now I would like it to find the second largest number in the array. How would I modify my program to do this?

This is the program I wrote and it does work. The program prints all the values in the array and then finds the max value of the array. Now I want it to find the second largest value.

 %include "io.mac"
.STACK 100H 

.DATA
   Numbers DW 3,4,5,2,6,0
   msg0  db "Printing values in array",0
   msg1  db "Max",0
   msg2  db "Min",0

   .CODE
        .STARTUP
    PutStr msg0
    mov dx, Numbers 
    mov si, dx ;point to array
    printValues:
    cmp word [si], 0
    je procedure
    nwln
    PutInt [si]
    add si, 2
    jmp printValues

    procedure:
    push Numbers ;push Number to stack to pass parameter by stack
    call maxMeth
    nwln
    PutStr msg1
    nwln

    PutInt ax
    nwln




    complete:
.EXIT





maxMeth:
    enter 0,0 ;save old bp and set bp to sp
    mov si, [bp+4] ;point to array 
    mov ax, [si]   ; ax holds max
    add si,2 ; Increment si to next number

;Now entering loop
max:   
    cmp word [si],0   ; checks to see if the number is 0 and if it is, then we are done.
    je finish
    cmp ax, [si]        ; ax holds the max . So if ax is greater than si, then dont assign si to ax. 
    jge increment
    jmp newMax
newMax: 
    mov ax, [si] ; Otherwise we have a new a max

increment:   
    add si, 2   ;now increment si to check the next value and jump back to the main loop.
    jmp max

finish: ;clean up.
    leave ;pop bp
    ret   ;return

I edited my program to keep track of the second max and the result I receive for the second max value is 3. I was expecting the program to output 5. Im not sure why I am getting the wrong output. Here are my edits to the program.

%include "io.mac"
.STACK 100H 

.DATA
   Numbers DW 3,4,5,2,6,0
   msg0  db "Printing values in array",0
   msg1  db "Max",0


   .CODE
        .STARTUP
    PutStr msg0
    mov dx, Numbers 
    mov si, dx ;point to array
    printValues:
    cmp word [si], 0
    je procedure
    nwln
    PutInt [si]
    add si, 2
    jmp printValues

    procedure:
    push Numbers ;push Number to stack to pass parameter by stack
    call maxMeth
    nwln
    PutStr msg1
    nwln

    PutInt ax
    nwln

   PutInt bx
    nwln


    complete:
.EXIT





maxMeth:
    enter 0,0 ;save old bp and set bp to sp
    mov si, [bp+4] ;point to array 
    mov ax, [si]   ; ax holds max
    mov bx, [si]   ; ax holds max
    add si,2 ; Increment si to next number

;Now entering loop
max:   
    cmp word [si],0   ; checks to see if the number is 0 and if it is, then we are done.
    je finish          ;equals 0, then finished
    cmp ax, [si]         
    jg testSecondMax   ;So if ax is greater than si, then dont assign si to ax and check second max
    jmp newMax         ;otherwise go to new max


newMax: 
    mov ax, [si] ; save new max
    jmp increment ; and increment

testSecondMax:
    cmp bx, [si]
    jl secondMax
    jg increment

secondMax:
    mov bx, [si]
    jmp increment

increment:  
    add si, 2   ;now increment si to check the next value and jump back to the main loop.
    jmp max 



finish: ;clean up.
    leave ;pop bp
    ret   ;return

Answer 1

I ended up writing code for this because it made me wonder how efficiently I could implement the loop. If you want to solve your homework yourself, don't look at my code, just the bullet points in English. Use a debugger to single-step through your code.

---

Here's how I would change your code:

• NASM style: use local labels (like .noswap:) within functions. Indent operands to a consistent column so it doesn't look ragged. Comment your function with inputs / return value and calling convention (what registers it clobbers).

• optimize out the jmp next_instruction before newMax: because it's just an expensive no-op to jump where execution was going to fall through anyway.

• Unless maybe optimizing for a real 8086, don't use enter, it's slow.

• Load each element being checking into a register, instead of using the same memory operand multiple times. (x86-16 has 6 integer registers other than BP/SP; use them.)

• put the loop-exit conditional branch at the bottom. (Jump to there for the loop entry point if needed).

• Keep a max and 2nd-max in two registers, like you're keeping max in AX.

• When you find an element greater than 2nd-max, keep the highest 2 of the 3 numbers you have. i.e. maintain a 2-element queue / sorted list in 2 registers.

Untested:

; word max2Meth(word *array);
; Input: implicit-length array (terminated by a 0 element),
;        pointed to by pointer passed on the stack.  (DS segment)
; returns in ax
; clobbers: cx, dx
global max2Meth
max2Meth:
    push  bp
    mov   bp, sp     ; make a stack frame.  (ENTER is slow, don't use it)
    push  si         ; SI is call-preserved in many calling conventions.  Omit this if you want to just clobber it.

    mov   si, [bp+4] ; pointer to array 

    mov   ax, [si]   ; assume that the list is non-empty
    mov   dx, ax     ; start with max = max2 instead of putting a conditional xchg outside the loop

    jmp   .loop_entry   ; enter at the bottom, at the conditional branch
;;; ax: 2nd max
;;; dx: max

.maxloop:              ; do {
    cmp cx, ax         ; check against 2nd-max, because the common case is less than both.
    jg  .updateMaxes   ; optimize for the common case: fall through on not-found

.loop_entry:
    add  si, 2
    mov  cx, [si]      ;   c = *p++;
    test cx, cx
    jnz .maxloop       ; } while (c != 0);

.finish:
   ; 2nd-max is already in AX, just clean up and return

    pop  si
    leave    ;pop bp would be faster because SP is already pointing to the right place
    ret

; This block is part of the function, even though it's placed after the ret
.updateMaxes:
    mov  ax, cx           ; Bump the old 2nd-max unconditionally
    cmp  ax, dx
    jle  .loop_entry      ; if 2nd_max <= max, return to the loop
    xchg ax, dx           ; otherwise swap
    jmp  .loop_entry

Putting the block for a rare case out-of-line is nice, because it means the common case can just fall through with no taken branches. Often putting if/else conditions inline require a jmp somewhere just to avoid running the else part after the if. But .updateMaxes: ends up being rather elegant, IMO: it has to jump back into the loop, and we can do that either before or after swapping.

16-bit xchg is 3 uops (as expensive as 3 mov instructions), but to make that cheaper (and only do mov ax, dx / mov dx, cx) in the new-max case we'd have to make the new-2ndmax case slower. Assuming it's more likely to just update the 2nd max than to update both, I think just mov and cmp/jcc is a win there. You could make that part branchless with cmov (on a 686 CPU), which might be good. Making the whole thing branchless would give you quite a long dependency chain, and not be worth it unless the array elements were on average getting larger towards the end so you had frequent max-updates all the time (but not with a pattern, so you get branch misses).

On Intel Haswell/Skylake, the inner loop is only 4 fused-domain uops (both compare/branches can macro-fuse). Over long runs of no updates, it should run at 1 iteration per clock.

If you're optimizing for code-size over speed (e.g. for a real 8086), use ax as the temporary and lodsw instead of mov ax, [si] and add si, 2. (Keep your max in a different register).

With an implicit-length list, you can't just use scasw with 2nd-max in ax, because you need to check for 0 as well as > 2nd-max :/

As a further optimization, you could use bp instead of si, if you're using the tiny model (SS = DS), because you don't need to access the stack after loading the pointer. You can just pop bp instead of leave

---

Before I thought of simply entering the loop with ax = dx = first element, I was going to use this code before the loop:

    mov   ax, [si]   ; assume that the list is non-empty
    mov   dx, [si+2] ; but check if it's only 1 element long, like maxMeth does
    test  dx, dx
    jz    .finish

    add   si, 4      ; first 2 elements are loaded

    cmp   ax, dx     ; sort them so ax <= dx
    jng  .noswap
    xchg  ax, dx
 .noswap:

---

Another way to structure the inner loop would be like this:

.maxloop:              ; do {
    add  si, 2
    mov  cx, [si]      ;   c = *p++;

    test cx, cx
    jz .finish         ; jz instead of jnz: exit the loop on the sentinel value

    cmp cx, ax         ; check against 2nd-max, because the common case is less than both.
    jng .maxloop

;; .updateMaxes:  ;; conditionally fall through into this part 
    mov  ax, cx           ; Bump the old 2nd-max unconditionally
    cmp  ax, dx
    jle  .maxloop         ; if 2nd_max <= max, return to the loop
    xchg ax, dx           ; otherwise swap
    jmp  .maxloop

.finish:

This is probably better because we can just fall into the top of the loop to start. We get out of the loop with a jz that skips over the conditional-update stuff, so we don't have any branches that exist only to skip over code that's "in the way". (i.e. we've succeeded at laying out our code blocks efficiently.)

The only downside for some CPUs is that the test/jz and cmp/jg are back to back. Some CPUs do better when conditional branches are separated by a couple more instructions than that. (e.g. unless you get lucky on how these hit the decoders on Sandybridge, one of the two branches won't macro-fuse. But they would with the first loop.)

---

Reminder: Stack Overflow user contributions are licensed under cc by-sa 3.0 with attribution required, so if you copy-paste my whole code, make sure you include https://stackoverflow.com/questions/47466116/assembly-program-that-finds-second-largest-value-in-array/47467682#47467682 in a comment.