세그먼트 화 오류 11이 더 큰 작업 번호로 인해 발생 함

Question

segmentation fault 11이 발생하면 프로그램에서 액세스가 허용되지 않는 메모리 영역에 액세스하려고 시도했음을 알고있었습니다.

다음 코드를 사용하여 푸리에 변환을 계산하려고합니다.

nPoints = 2^15 (또는 적은 점수의 점)이 좋을 때 작동하지만, 점을 2^16까지 추가로 늘리면 손상됩니다. 너무 많은 기억을 차지함으로써 야기 된 것인가 궁금합니다. 그러나 나는 수술 도중 너무 많은 기억 점령을 알아 차리지 못했다. 그리고 재귀를 사용하지만 내부에서 변환됩니다. 나는 그것이 많은 기억을 차지하지 않을 것이라고 생각했다. 그렇다면 문제는 어디에 있습니까? 미리

감사

PS : I 말할 깜빡 한가지이고, 최대 OS (8G 메모리)에 있던 상기 결과.

Windows (16G 메모리)에서 코드를 실행하면 nPoints = 2^14 일 때 오류가 발생합니다. 따라서 Windows PC의 메모리가 크기 때문에 메모리 할당으로 인한 것인지 혼란 스럽습니다 (두 운영 체제가 서로 다른 메모리 전략을 사용하기 때문에 실제로 말하기는 어렵습니다).

#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

1. 스택에 매우 큰 배열을 할당 할 수 없습니다. 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. 2의 제곱을 계산하려면 부동 소수점 연산 pow(2, 16)이 아닌 정수 연산 1 << power을 사용하십시오. 우리는 macOS에서 pow을 잘 설계했지만, 다른 시스템에서는 정확한 결과가 가능할지라도 근사치를 반환 할 수 있습니다. 근사 결과는 정확한 정수 값보다 약간 작을 수 있으므로 정수로 변환하면 잘못된 결과가 잘립니다.int에 적합한 것보다 큰 2의 거듭 제곱 인 경우 (type) 1 << power을 사용하십시오. 여기서 type은 적절하게 큰 정수 유형입니다.

Answer 2

다음, 계측은, 코드는 명확하게 작전 코드가 반복적으로 그 배열 위치의 대부분을 업데이트하지 않습니다 실제로 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 > out.txt 
less out.txt 

out.txt 파일이 8,630,880 바이트

(untitled1 리눅스 실행 파일과의 이름입니다) 해당 파일의 검사 부족을 보여줍니다 어떤 하나의 항목이 이전의 두 항목의 합이 아니라는 것을 보여주기 때문에 이것이 유효한 푸리에 변환이 아닌 것으로 의심됩니다.