Transposing a square matrix (n x n) 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
; --------------------------
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.



; 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        ; -&gt; Size of matrix
    sub     esp, ecx        ; Local buffer
    mov     edi, esp
    lea     eax, [edx-1]    ; (Rank - 1)
.a: movsb                   ; -&gt; EDI += 1
    add     edi, eax        ; -&gt; 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        ; -&gt; EDI is Address
    mov     esi, esp        ; -&gt; 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.



; 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
; --------------------------