Code Optimization Tips:

Question

I am using the following ASM routine to bubble sort an array. I want to know of the inefficiencies of my code:

.386
.model flat, c
option casemap:none


.code
            public sample
            sample PROC
            ;[ebp+0Ch]Length
            ;[ebp+08h]Array
                            push ebp
                            mov ebp, esp
                            push ecx
                            push edx
                            push esi
                            push eax
                            mov ecx,[ebp+0Ch]
                            mov esi,[ebp+08h]
                _bubbleSort:
                            push ecx
                            push esi
                            cmp ecx,1
                            je _exitLoop
                            sub ecx,01h
                            _miniLoop:
                                        push ecx
                                        mov edx,DWORD PTR [esi+4]
                                        cmp DWORD PTR [esi],edx
                                        ja _swap
                                        jmp _continueLoop
                            _swap:      
                                        lodsd
                                        mov DWORD PTR [esi-4],edx
                                        xchg DWORD PTR [esi],eax    
                                        jmp _skipIncrementESI
                            _continueLoop:
                                        add esi,4
                            _skipIncrementESI:
                                        pop ecx
                                        loop _miniLoop 
                            _exitLoop:
                            pop esi
                            pop ecx 
                            loop _bubbleSort
                            pop eax
                            pop esi
                            pop edx
                            pop ecx
                            pop ebp
                            ret 
            sample ENDP
            END 

Basically I have two loops, as usual for the bubble sort algorithm. The value of ecx for the outer loop is 10, and for the inner loop it is [ecx-1]. I have tried the routine and it compiles and runs successfully, but I am not sure if it is efficient.

Answer 1

Several simple tips:

1) Try to minimize the number of conditional jumps, because they are very expensive. Unroll if possible. 2) Reorder instructions to minimize stalls because of data depencency:

cmp DWORD PTR [esi],edx ;// takes some time to compute,
mov edx,DWORD PTR [esi+4] ; 
ja _swap ;// waits for results of cmp

3) Avoid old composite instructions (dec, jnz pair is faster than loop and is not bound to ecx register)

It would be quite difficult to write assembly code that is faster than the code generated by optimizing C compiler, because you should consider lots of factors: size of data and instruction caches, alignments, pipeline, instruction timings. You can find some good documentation about this here. I especially recommend the first book: Optimizing software in C++