编辑 下面的部分解决方案(编辑2),但我仍然有一个问题(见最后)
我正在尝试使用 gcc-4.9.2 编译以下 C 程序,在 Windows 7 上,32 位,运行在奔腾 G3220 上(根据 Windows 系统信息)。如果我理解正确,这个处理器没有AVX扩展,所以发生一些事情是很自然的,我只是不确定到底是什么。最初,我正在使用gcc进行优化,并且我"意外"地尝试了-mavx。
以下程序计算数字 0 ...按字典顺序排列的 n-1(以 n 作为参数给出),以及每个排列的秩(它在此顺序中的位置)和"unrank"(从秩中恢复排列),并检查所有这些都是正确的。它最后应该只打印"确定"或"错误"。
- 使用
gcc -O3
,程序在我检查的所有整数输入(1 <= n <= 11)的情况下正常运行。 - 使用
gcc -O3 -mavx
,它在 1 <= n <= 7 的情况下正确运行,对于 n>= 8,它什么也不打印,实际上它什么也不做(退出前几乎没有延迟)。我没有从程序或 Windows 收到任何消息(我本来预计可能会因未知指令而崩溃,但它没有发生)。
(在另一台装有 Windows 7 64 位、core-i5 和相同 gcc-4.9.2 的计算机上,当以 32 位或 64 位编译时,该程序似乎在没有 -mavx 的情况下运行良好)
我不明白的是为什么它在某些输入值上正确运行,而对其他输入值失败。有人对此有所提示吗?
这是完整的程序,然后是具有相同问题的较短程序。
#include <stdlib.h>
#include <stdio.h>
#define SWAP(a,b) {int c; c = a; a = b; b = c;}
int next_perm(int n, int a[n]) {
int i, j, k;
for(i = n - 1; i > 0 && a[i - 1] > a[i]; i--);
for(j = i, k = n - 1; j < k; j++, k--) SWAP(a[j], a[k]);
if(i == 0) return 0;
for(j = i--; a[j] < a[i]; j++);
SWAP(a[i], a[j]);
return 1;
}
#undef SWAP
void copyvec(int n, int dst[n], int src[n]) {
int i;
for(i = 0; i < n; i++) {
dst[i] = src[i];
}
}
int eqvec(int n, int a[n], int b[n]) {
int i;
for(i = 0; i < n; i++) {
if(a[i] != b[i]) return 0;
}
return 1;
}
int rank(int n, int a[n]) {
int v[n], i, j, r;
v[n - 1] = 1;
for(j = n - 2; j >= 0; j--) v[j] = v[j + 1]*(n - 1 - j);
for(r = i = 0; ; i++) {
for(j = i; j < n; j++) {
if(a[j] > j) goto cont;
}
return r;
cont:
i = j;
r += v[i]*(a[i] - i);
for(j = i + 1; j < n; j++) {
if(a[j] < a[i]) a[j]++;
}
}
}
void unrank(int n, int a[n], int p) {
int v[n], i, j, r, s;
v[n - 1] = 1;
for(i = n - 2; i >= 0; i--) v[i] = v[i + 1]*(n - 1 - i);
p %= n*v[0];
for(i = 0; i < n; i++) a[i] = i;
for(i = 0; p > 0; i++) {
for(; v[i] > p; i++);
r = p/v[i];
p %= v[i];
for(s = a[j = i + r]; j >= i; j--) a[j] = a[j - 1];
a[i] = s;
}
}
int main(int argc, char **argv) {
int n, i, r, s = 0, q = 0;
int *a = NULL, *b = NULL, *c = NULL;
if(argc == 2 && (n = strtol(argv[1], NULL, 0)) > 0) {
a = malloc(n*sizeof(int));
b = malloc(n*sizeof(int));
c = malloc(n*sizeof(int));
if(!a || !b || !c) {
puts("Unable to allocate memory");
goto end;
} else {
for(i = 0; i < n; i++) a[i] = i;
do {
copyvec(n, b, a);
r = rank(n, b);
unrank(n, c, r);
q |= s++ != r || !eqvec(n, a, c);
} while(next_perm(n, a));
puts(q?"Error":"OK");
}
} else {
puts("perm n - Check all permutations of {0 ... n - 1}, with n > 0");
}
end:
if(a) free(a);
if(b) free(b);
if(c) free(c);
return 0;
}
编辑
根据Brian Cain的评论,这是一个具有相同问题的较短程序。我删除了对输入值的所有检查,所有排名/取消排名的东西,我用大小为 20 的数组替换了 malloc/free(现在只有一个,因为 b 和 c 不再使用)。现在,程序仅使用 while(next_perm(n, a));
循环计算排列,而不对它们执行任何操作。不过,它最终仍应打印"OK",因为在初始 q=0 之后 q 的值不会改变。
#include <stdlib.h>
#include <stdio.h>
#define SWAP(a,b) {int c; c = a; a = b; b = c;}
int next_perm(int n, int a[n]) {
int i, j, k;
for(i = n - 1; i > 0 && a[i - 1] > a[i]; i--);
for(j = i, k = n - 1; j < k; j++, k--) SWAP(a[j], a[k]);
if(i == 0) return 0;
for(j = i--; a[j] < a[i]; j++);
SWAP(a[i], a[j]);
return 1;
}
#undef SWAP
int main(int argc, char **argv) {
int n, i, r, s = 0, q = 0, a[20];
n = strtol(argv[1], NULL, 0);
for(i = 0; i < n; i++) a[i] = i;
while(next_perm(n, a));
puts(q?"Error":"OK");
return 0;
}
编辑2:程序集输出的说明
我还添加了 gcc 的反汇编输出(采用英特尔语法),可在 gcc -O3 -mavx -S -masm=intel
和 gcc-4.9.2 中找到(有关编译器的实际二进制文件,请参阅上面的链接)。但是,它需要一些工作,因为 gcc 将内联对next_perm的调用,并且它的可读性较差。我还删除了 CFI 指令和对齐方式以及实际上所有其他指令,以提高可读性:
_next_perm:
LFB0:
push ebp
push edi
push esi
push ebx
mov ecx, DWORD PTR [esp+20]
mov edx, DWORD PTR [esp+24]
lea eax, [ecx-1]
test eax, eax
jle L12
mov edi, DWORD PTR [edx-4+ecx*4]
cmp DWORD PTR [edx-8+ecx*4], edi
mov ecx, eax
jg L5
jmp L11
L28:
mov esi, DWORD PTR [edx+ecx*4]
cmp DWORD PTR [edx-4+ecx*4], esi
jle L27
L5:
sub ecx, 1
jne L28
L4:
mov ebx, ecx
L7:
mov esi, DWORD PTR [edx+ebx*4]
mov edi, DWORD PTR [edx+eax*4]
mov DWORD PTR [edx+ebx*4], edi
mov DWORD PTR [edx+eax*4], esi
add ebx, 1
sub eax, 1
cmp ebx, eax
jl L7
L2:
xor eax, eax
test ecx, ecx
je L23
L11:
sal ecx, 2
lea esi, [edx+ecx]
lea ebp, [edx-4+ecx]
mov ebx, DWORD PTR [esi]
mov edi, DWORD PTR [ebp+0]
cmp edi, ebx
jle L9
lea eax, [edx+4+ecx]
L10:
mov esi, eax
add eax, 4
mov ebx, DWORD PTR [eax-4]
cmp ebx, edi
jl L10
L9:
mov DWORD PTR [ebp+0], ebx
mov eax, 1
mov DWORD PTR [esi], edi
L23:
pop ebx
pop esi
pop edi
pop ebp
ret
L27:
cmp eax, ecx
jg L4
jmp L11
L12:
mov ecx, eax
jmp L2
程序集输出与或不带 -mavx 是相同的,除了标签编号:没有 AVX 指令,这意味着问题实际上出在main
上。
这可以通过在main中添加一些puts
来检查:
int main(int argc, char **argv) {
int n, i, q = 0, a[20];
puts("X");
n = strtol(argv[1], NULL, 0);
puts("Y");
for(i = 0; i < n; i++) a[i] = i;
puts("Z");
while(next_perm(n, a));
puts(q?"Error":"OK");
return 0;
}
然后,程序在失败时只打印 X 和 Y,因此问题来自用于在 Y 和 Z 之间的 for 循环中构建"a"的 AVX 指令。
这是 main
的程序集输出,同样没有指令(LC2 指向"Y",LC3 指向"Z")。在 main 的汇编 ouptut 中唯一的 AVX 指令在这两个puts
之间,它们用于构建初始 'a' 的for
循环,即数组 {0, 1, ..., n-1}。实际上,AVX 指令用于一次构建"a"的多个元素(我猜是 4),如果"a"的长度不是 4 的倍数,那么还有一个额外的步骤(在 L4 和 L9 之间),在 L9 调用 puts("Z")之前,然后是 while(next_perm(n, a));在 L3。因此,问题非常简单:如果n
足够小,那么AVX循环实际上没有运行,并且没有错误。这里的最大有效n
是 4,但它在不同的 gcc 运行之间有所不同,似乎有点随机(我昨天得到了 8)。
LC0 和 LC4 标签指向 AVX 指令使用的两个由 4 个元素组成的数组:LC0 是 {0,1,2,3},LC4 是 {4,4,4,4}。难怪他们为什么在这里,即使对 AVX 没有深入了解,它闻起来就像一个展开的循环:-)
_main:
push ebp
mov ebp, esp
push edi
push esi
push ebx
and esp, -16
sub esp, 96
call ___main
mov DWORD PTR [esp], OFFSET FLAT:LC1
call _puts
mov eax, DWORD PTR [ebp+12]
mov DWORD PTR [esp+8], 0
mov DWORD PTR [esp+4], 0
mov eax, DWORD PTR [eax+4]
mov DWORD PTR [esp], eax
call _strtol
mov DWORD PTR [esp], OFFSET FLAT:LC2
mov ebx, eax
call _puts
test ebx, ebx
jle L17
lea edx, [ebx-4]
lea ecx, [ebx-1]
shr edx, 2
add edx, 1
cmp ecx, 3
lea eax, [0+edx*4]
jbe L10
vmovdqa xmm1, XMMWORD PTR LC4
lea esi, [esp+16]
xor ecx, ecx
vmovdqa xmm0, XMMWORD PTR LC0
L5:
mov edi, ecx
add ecx, 1
sal edi, 4
cmp edx, ecx
vmovaps XMMWORD PTR [esi+edi], xmm0
vpaddd xmm0, xmm0, xmm1
ja L5
cmp ebx, eax
je L9
L4:
lea edx, [eax+1]
mov DWORD PTR [esp+16+eax*4], eax
cmp ebx, edx
jle L9
mov DWORD PTR [esp+16+edx*4], edx
lea edx, [eax+2]
cmp ebx, edx
jle L9
add eax, 3
mov DWORD PTR [esp+16+edx*4], edx
cmp ebx, eax
jle L9
mov DWORD PTR [esp+16+eax*4], eax
L9:
mov DWORD PTR [esp], OFFSET FLAT:LC3
call _puts
L3:
mov DWORD PTR [esp+4], esi
mov DWORD PTR [esp], ebx
call _next_perm
test eax, eax
jne L3
mov DWORD PTR [esp], OFFSET FLAT:LC5
call _puts
lea esp, [ebp-12]
xor eax, eax
pop ebx
pop esi
pop edi
pop ebp
ret
L10:
xor eax, eax
lea esi, [esp+16]
jmp L4
L17:
lea esi, [esp+16]
jmp L9
现在,我了解了实际发生的情况,但仍然存在一个问题:为什么当程序尝试运行AVX指令时没有任何错误消息?它只是退出,或者被杀死,但没有任何迹象表明出了什么问题。
This code always results in:
where parameter = n
a[] = {0,0,2, 3, ...,n-2,n-1}
b[] = {n-1, n-1, ... , n-1}
c[] = {n-1, n-2, ... , 0}
when it reaches the above conditions,
then it exits with "OK"
the amount of time spent executing the code
climbs at an exponential rate
as the value of the parameter is increased