1
\$\begingroup\$

I wish to transpose a square matrix, permanently overwriting it.
This is not the same as creating a 2nd matrix with the transposed contents of the 1st matrix.

I call the procedure with 3 parameters: the address of the original matrix, its rank, and the address of a scratch buffer that is large enough.
First, all the elements are spread out over the scratch buffer. Later the scratch buffer is copied back to the original storage.

How can I optimize this code?

; TransposeSquareMatrix(Address, Rank, Scratch)
Q:  push    ebp
    mov     ebp, esp
    push    ecx edx esi edi
    mov     esi, [ebp+8]    ; Address
    mov     edx, [ebp+12]   ; Rank
    mov     edi, [ebp+16]   ; Scratch buffer
    lea     eax, [edx-1]    ; Additional address increment
.a: push    edi             ; (1)
    mov     ecx, [ebp+12]   ; Rank
.b: movsb                   ; Spreading out the elements of one row
    add     edi, eax
    dec     ecx
    jnz     .b
    pop     edi             ; (1)
    inc     edi
    dec     edx
    jnz     .a              ; Repeating it for every row
    mov     edi, [ebp+8]    ; Address
    mov     ecx, [ebp+12]   ; Rank
    imul    ecx, ecx
    mov     esi, [ebp+16]   ; Scratch buffer
    rep movsb               ; Overwriting the original matrix
    pop     edi esi edx ecx
    pop     ebp
    ret     12
; --------------------------
\$\endgroup\$
  • \$\begingroup\$ Below is a self-answer. Please don't let that stop you from writing a review. Code improvements or perhaps suggesting an alternative approach? \$\endgroup\$ – Sep Roland May 29 at 23:50
3
\$\begingroup\$

20+ percent faster using the stack for the extra buffer.

Matrix     Question     Answer(1)    Faster
-------------------------------------------
16 x 16    3.62 µsec    2.62 µsec    27.6 %
13 x 13    2.67 µsec    2.05 µsec    23.2 %
10 x 10    1.77 µsec    1.35 µsec    23.7 %
 7 x  7    1.02 µsec    0.77 µsec    24.5 %
 4 x  4    0.56 µsec    0.44 µsec    21.4 %

Setting up a temporary scratch buffer in the stack proved to be a winner. A decent speed increase, no need for the 3rd parameter, and with a single branch target, applying code alignment could be a bit easier.

This pushes the same 5 registers but delays assigning EBP so it can be used as an EndOfBuffer marker. A minor drawback is that the easy recognizable EBP-offsets for the parameters (+8, +12, ...) are gone. Requires some more attention to detail like in the ESP-offsets of today.

Nothing is pushed on the stack below the local stack buffer and so keeping ESP dword-aligned is not needed.

This is cleaner code. I think addressing the parameters several times over, looked a bit untidy.

Transpose via copying

; TransposeSquareMatrix(Address, Rank)
A1: push    ecx edx esi edi ebp
    mov     ebp, esp
    mov     esi, [ebp+24]   ; Address
    mov     edx, [ebp+28]   ; Rank
    mov     ecx, edx
    imul    ecx, ecx        ; -> Size of matrix
    sub     esp, ecx        ; Local buffer
    mov     edi, esp
    lea     eax, [edx-1]    ; (Rank - 1)
.a: movsb                   ; -> EDI += 1
    add     edi, eax        ; -> EDI += (Rank - 1)
    cmp     edi, ebp        ; Until end of local buffer
    jb      .a
    sub     edi, ecx        ; Back to start of current column
    inc     edi             ; Go to start next column
    dec     edx
    jnz     .a              ; Repeat rank times
    sub     esi, ecx        ; Copy to original storage
    mov     edi, esi        ; -> EDI is Address
    mov     esi, esp        ; -> ESI is local buffer
    rep movsb
    mov     esp, ebp
    pop     ebp edi esi edx ecx
    ret     8
; --------------------------

50+ percent faster without even using an extra buffer.

Matrix     Question     Answer(2)    Faster
-------------------------------------------
16 x 16    3.62 µsec    1.80 µsec    50.1 %
13 x 13    2.67 µsec    1.22 µsec    54.3 %
10 x 10    1.77 µsec    0.77 µsec    56.0 %
 7 x  7    1.02 µsec    0.44 µsec    56.9 %
 4 x  4    0.56 µsec    0.23 µsec    58.9 %

The elements on the main diagonal are never touched. All the other elements are flipped across the main diagonal.

Transpose via swapping

; TransposeSquareMatrix(Address, Rank)
A2: push    ebx ecx edx esi edi ebp
    mov     ebx, [esp+28]   ; Address
    mov     ecx, [esp+32]   ; Rank
    mov     ebp, ecx
    dec     ecx
    jz      .c              ; It's a (1 x 1) matrix
.a: push    ecx             ; (1)
    mov     esi, ebx        ; Column address
    mov     edi, ebx        ; Row address
.b: inc     esi             ; To next element in this row
    add     edi, ebp        ; To next element in this column
    mov     al, [esi]       ; Swap 2 elements
    mov     dl, [edi]
    mov     [edi], al
    mov     [esi], dl
    dec     ecx
    jnz     .b
    add     ebx, ebp        ; To next element on main diagonal
    inc     ebx
    pop     ecx             ; (1)
    dec     ecx
    jnz     .a              ; Continu until (1 x 1) matrix
.c: pop     ebp edi esi edx ecx ebx
    ret     8
; --------------------------
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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