二维数组示例

N x N 向量代码

#define N 16
tydef int fix_matrix[N][N]
/* Get element a[i][j] */
int fix_ele(fix_matrix a, int i, int j)
{
    return a[i][j];
}

首先我们看第一个, 这是一个 n * n 的这么一个整数类型的二维数组, 这个 N 在写代码的时候已经固定了, 也就是编译器知道你是 n * n 的, 然后这种情况下我们把第 i 行第 j 列的数据取出来

下面这个也是有一个 n * n 的数组, 但是这个数组的 n 在编译的时候不知道, 运行的时候这个 n 才确定, 然后动态地把它分配出来.

/* Get element a[i][j] */
int var_ele(int n, int a[n][n], int i, int j)
{
    return a[i][j];
}

类似地, 我也需要把这个二维数组里面的第 i 行第 j 列的数据取出来

这两个从形式上看挺相似的, 但是实际上的过程却不一样. 怎么个不一样呢, 我们从汇编层面看它是有什么不同的操作.

16 x 16 Matrix Access

第一个例子, N 已经确定了, 这个相当于一个嵌套数组, 它里面的元素的地址运算也是挺简单的

    movl 12(%ebp), %edx ; i
    sall $6, %edx   ; i * 64
    movl 16(%ebp), %eax ; j
    sall $2, %eax   ; j * 4
    addl 8(%ebp), %eax  ; a + j * 4
    movl (%eax, %edx), %eax ; *(a + j * 4 + i * 64)

N x N Matrix Access

计算公式其实还是一样的, 无非就是说这个不是一个常数了, 而是一个变量, 通过参数传递过来

    movl 8(%ebp), %eax  ; n
    sall $2, %eax   ; n * 4
    movl %eax, %edx ; n * 4
    imull 16(%ebp), %edx    ; i * n * 4
    movl 20(%ebp), %eax ; j
    sall $2, %eax   ; j * 4
    addl 12(%ebp), %eax ; a + j * 4
    movl (%eax, %edx), %eax ; *(a + j * 4 + i * n * 4) 最后把上述的这些加法给它统统加起来, 加起来之后作为地址, 取值放到 eax 里面去

Optimizing Fixed Array Access

对于这种固定大小的数组的访问, 实际上可以做一些简单的优化

比如说这个例子, 这里面我们有一个 n * n 的这么一个二维数组, 我要把里面第 j 列取出来, 不是说行, 而是把这一列取出来

#define N 16
typedef int fix_matrix[N][N];
/* Retrieve column j from array */
void fix_column(fix_matrix a, int j, int *dest)
{
    int i;
    for(i = 0; i < N; i++)
    {
        dest[i] = a[i][i];
    }
}

我们先做一个初始化操作, 把它的这个起始地址 a + 4 * j, 先把它初始化出来作为这个 ajp 的地址. 把我们要取出来的元素的地址放到 ajp 里面. 然后你取出来的数据要放到 destination 目标的一个数组里面去, destination 这个地址放到 ebx 里面去. edx 是作为一个循环的变量.

然后你是按列在访问, 所以这种情况下列里面第一个元素跟第二个元素之间应该有一个差, 这个差是 4 * n. 就是同一列里面, 相邻两个元素, 地址上相差 4 * n.

.L8:
    movl (%ecx), %eax   ; read *ajp
    movl %eax. (%ebx, %edx, 4)  ; 因为这个指令不能两个操作数都是内存, 所以这里用 eax 作中转 Save in dest
    addl $1, %edx   ; i++
    addl $64, %ecx  ; ajp += 4 * N 每个元素之间, 相差一行的 size
    cmpl $16, %edx  ; i : N
    jne .L8 ; if !=, goto loop

Optimizing Variable Array Access

然后就是可变长度数组进行循环的访问

首先还是把一列里面的数据取出来, 放到 destination 里面去

/* Retrie column j from array */
void var_column(int n, int a[n][n], int j, int *dest)
{
    int i;
    for (i = 0; i < n; i++)
        dest[i] = a[i][j];
}

首先我们还是把我们要访问的元素的地址放到 ajp 里面. 然后 edi 里面就存着 destination 数组的起始地址. edx 是循环变量. ebx 就是刚才说的每个元素直接相差的跨度. esi 就是这个 n 是个变量.

.L18:
    movl (%ecx), %eax   ; read *ajp
    movl %eax, (%edi, %edx, 4)  ; save in dest[i]
    addl $1, %edx   ; i++
    addl %ebx, %ecx ; ajp += 4 * n
    cmpl %edx, %esi ; n : 1
    jg .J18 ; if >, goto loop