C中的Segmentation Fault 11 由较大的操作数引起

Question

我知道当遇到 segmentation fault 11 时，这意味着程序试图访问不允许访问的内存区域。

我在这里尝试使用以下代码计算傅立叶变换。

它在 nPoints = 2^15 时运行良好（或者当然点数较少），但是当我进一步将点数增加到 2^16 时它会损坏。请问是不是占用内存太多导致的？但是运行过程中并没有发现内存占用太大。尽管它使用递归，但它会就地转换。我认为它不会占用太多内存。那么问题出在哪里呢？

提前致谢

PS: 有一点忘记说了，上面的结果是在MaxOS（8G内存）上的。

当我运行 Windows（16G 内存）上的代码时，它在nPoints = 2^14 时损坏。所以我很疑惑是不是内存分配的问题，因为WindowsPC的内存比较大（但是真的很难说，因为两个操作系统使用不同的内存策略）。

#include <stdio.h>
#include <tgmath.h>
#include <string.h>

// in place FFT with O(n) memory usage

long double PI;
typedef long double complex cplx;

void _fft(cplx buf[], cplx out[], int n, int step)
{
  if (step < n) {
    _fft(out, buf, n, step * 2);
    _fft(out + step, buf + step, n, step * 2);

    for (int i = 0; i < n; i += 2 * step) {
      cplx t = exp(-I * PI * i / n) * out[i + step];
      buf[i / 2]     = out[i] + t;
      buf[(i + n)/2] = out[i] - t;
    }
  }
}

void fft(cplx buf[], int n)
{
  cplx out[n];
  for (int i = 0; i < n; i++) out[i] = buf[i];

  _fft(buf, out, n, 1);
}


int main()
{
  const int nPoints = pow(2, 15);
  PI = atan2(1.0l, 1) * 4;

  double tau = 0.1;
  double tSpan = 12.5;
  long double dt = tSpan / (nPoints-1);
  long double T[nPoints];
  cplx At[nPoints];

  for (int i = 0; i < nPoints; ++i)
  {
    T[i] = dt * (i - nPoints / 2);
    At[i] = exp( - T[i]*T[i] / (2*tau*tau));
  }

    fft(At, nPoints);

  return 0;
}

Answer 1

以下经过检测的代码清楚地表明，OP 代码重复更新 out[] 数组中的相同位置，实际上并没有更新该数组中的大部分位置。

#include <stdio.h>
#include <tgmath.h>
#include <assert.h>



// in place FFT with O(n) memory usage
#define N_POINTS  (1<<15)

double T[N_POINTS];
double At[N_POINTS];
double PI;


// prototypes
void _fft(double buf[], double out[], int step);
void fft( void );


int main( void )
{
    PI = 3.14159;

    double tau = 0.1;
    double tSpan = 12.5;
    double dt = tSpan / (N_POINTS-1);

    for (int i = 0; i < N_POINTS; ++i)
    {
        T[i]  = dt * (i - (N_POINTS / 2));
        At[i] = exp( - T[i]*T[i] / (2*tau*tau));
    }

    fft();

    return 0;
}


void fft()
{
    double out[ N_POINTS ];

    for (int i = 0; i < N_POINTS; i++)
        out[i] = At[i];

    _fft(At, out, 1);
}


void _fft(double buf[], double out[], int step)
{
    printf( "step: %d\n", step );

    if (step < N_POINTS)
    {
        _fft(out, buf, step * 2);
        _fft(out + step, buf + step, step * 2);

        for (int i = 0; i < N_POINTS; i += 2 * step)
        {
            double t = exp(-I * PI * i / N_POINTS) * out[i + step];
            buf[i / 2]     = out[i] + t;
            buf[(i + N_POINTS)/2] = out[i] - t;
            printf( "index: %d buf update: %d, %d\n", i, i/2, (i+N_POINTS)/2 );
        }
    }
}

建议运行通过（其中 untitled1 是可执行文件的名称，在 linux 上）

./untitled1 > out.txt
less out.txt

out.txt 文件是 8630880 字节

对该文件的检查显示缺少覆盖，并显示任何一个条目都不是前两个条目的总和，所以我怀疑这不是有效的傅立叶变换，

Answer 2

您不能在堆栈中分配非常大的数组。 macOS 上的默认堆栈大小为 8 MiB。 cplx 类型的大小是 32 字节，所以 2¹⁶ cplx 元素的数组是 2 MiB，你有两个（一个在 main 和 fft 中的一个），所以这是 4 MiB。这适合堆栈，但是，在那个大小下，程序会在我尝试时运行到完成。在 2¹⁷，它失败了，这是有道理的，因为程序有两个数组在堆栈上占用 8 MiB。分配如此大的数组的正确方法是包含 <stdlib.h> 并使用 cmplx *At = malloc(nPoints * sizeof *At);，然后使用 if (!At) { /* Print some error message about being unable to allocate memory and terminate the program. */ }。您应该为 At、T 和 out 执行此操作。此外，当你完成每个数组时，你应该释放它，就像 free(At);.
要计算 2 的整数次方，请使用整数运算 1 << power，而不是浮点运算 pow(2, 16)。我们在 macOS 上设计得很好 pow，但是，在其他系统上，它可能 return 近似值，即使可能有精确的结果。近似结果可能略小于精确的整数值，因此将其转换为整数会截断为错误的结果。如果它可能是大于 int 的 2 的幂，则使用 (type) 1 << power，其中 type 是一个合适的大整数类型。

C中的Segmentation Fault 11 由较大的操作数引起

Segmentation Fault 11 in C caused by larger operation numbers

c

memory

macos

fft

segmentation-fault