动态分配和重新分配树中的内存算法

Question

我正在为模拟编程树算法。每个处理器都有自己的树。在程序中的特定点，我必须检查是否有特定树中的粒子不属于那里。我收集它们并将它们发送到正确的树/处理器。

我的问题是关于我收集粒子并将它们放入动态大小列表的过程。由于我必须发送给另一棵树的粒子数量不是恒定的，我必须使用动态数组。

我实现了一个小程序，所有这些都应该发生。但它只适用于小型N。但也为小N有时会出现错误。重新分配过程可能不起作用。

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define DIM 2 

// Struct for particles 
typedef struct { 
    double m; 
    double x[DIM]; 
    int id; 
} Particle; 

// Structs for lists I want to fill with particle data 
typedef struct { 
    double **list; // every processor has its own list 
    int *counter; // length of the list 
} ParticleList; 

void generateParticles(Particle *p, int N); 
void buildList(Particle *p, ParticleList *plist, int numprocs, int N); 

int main() { 
    time_t t; 
    srand((unsigned)time(&t)); 

    // Generate and print data 
    int N = 3; 
    Particle *p = (Particle*)malloc(N * sizeof(*p)); 
    generateParticles(p, N); 

    for (int i = 0; i < N; i++) { 
     printf("id: %d m: %lf x: %lf %lf\n", p[i].id, p[i].m, p[i].x[0], p[i].x[1]); 
    } 

    // Fill lists 
    int numprocs = 4; 
    ParticleList plist; 
    plist.list = malloc(sizeof(double*) * numprocs); 
    // At the beginning every list should be of size zero 
    // Therefore I initialize lists for every processor of size zero 
    for (int k = 0; k < numprocs; k++) 
     plist.list[k] = malloc(sizeof(double) * 0); 
    plist.counter = calloc(numprocs, sizeof(int)); 
    // Fill the lists randomly 
    buildList(p, &plist, numprocs, N); 

    for (int k = 0; k < numprocs; k++) { 
     printf("%d\n", plist.counter[k]); 
     for (int c = 0; c < (DIM * plist.counter[k]); c++) { 
      printf("%lf ", plist.list[k][c]); 
     } 
     printf("\n"); 
    } 

    free(p); 
    return 0; 
} 

void buildList(Particle *p, ParticleList *plist, int numprocs, int N) { 
    for (int k = 0; k < numprocs; k++) { 
     for (int i = 0; i < N; i++) { 
      if (rand() % 10 < 3) { // randomly choose particles to fill the list 
       plist->counter[k]++; 
       // Here might be the problem? 
       plist->list[k] = realloc(plist->list[k], DIM * sizeof(plist->list[k])); 
       for (int j = plist->counter[k]; j < (plist->counter[k] + DIM); j++) 
        plist->list[k][j] = p[i].x[j]; 
      } 
     } 
    } 
} 

void generateParticles(Particle *p, int N) { 
    for (int i = 0; i < N; i++) { 
     for (int d = 0; d < DIM; d++) { 
      p[i].x[d] = rand() % 10; 
     } 
     p[i].m = rand() % 10; 
     p[i].id = i; 
    } 
} 

的问题可能是在这一行：plist->list[k] = realloc(plist->list[k], DIM * sizeof(plist->list[k]));

我收到以下错误：

*** Error in `./append_struct': realloc(): invalid next size: 0x00000000015df540 *** 
======= Backtrace: ========= 
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7fc931b3e7e5] 
/lib/x86_64-linux-gnu/libc.so.6(+0x834aa)[0x7fc931b4a4aa] 
/lib/x86_64-linux-gnu/libc.so.6(realloc+0x179)[0x7fc931b4b839] 
./append_struct[0x400b5e] 
./append_struct[0x4009bf] 
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7fc931ae7830] 
./append_struct[0x4007b9] 
======= Memory map: ======== 
00400000-00401000 r-xp 00000000 08:02 3670408       /home/exp/append_struct 
00601000-00602000 r--p 00001000 08:02 3670408       /home/exp/append_struct 
00602000-00603000 rw-p 00002000 08:02 3670408       /home/exp/append_struct 
015df000-01600000 rw-p 00000000 00:00 0         [heap] 
7fc92c000000-7fc92c021000 rw-p 00000000 00:00 0 
7fc92c021000-7fc930000000 ---p 00000000 00:00 0 
7fc9318b1000-7fc9318c7000 r-xp 00000000 08:02 4985364     /lib/x86_64-linux-gnu/libgcc_s.so.1 
7fc9318c7000-7fc931ac6000 ---p 00016000 08:02 4985364     /lib/x86_64-linux-gnu/libgcc_s.so.1 
7fc931ac6000-7fc931ac7000 rw-p 00015000 08:02 4985364     /lib/x86_64-linux-gnu/libgcc_s.so.1 
7fc931ac7000-7fc931c87000 r-xp 00000000 08:02 4994073     /lib/x86_64-linux-gnu/libc-2.23.so 
7fc931c87000-7fc931e87000 ---p 001c0000 08:02 4994073     /lib/x86_64-linux-gnu/libc-2.23.so 
7fc931e87000-7fc931e8b000 r--p 001c0000 08:02 4994073     /lib/x86_64-linux-gnu/libc-2.23.so 
7fc931e8b000-7fc931e8d000 rw-p 001c4000 08:02 4994073     /lib/x86_64-linux-gnu/libc-2.23.so 
7fc931e8d000-7fc931e91000 rw-p 00000000 00:00 0 
7fc931e91000-7fc931ea9000 r-xp 00000000 08:02 4994056     /lib/x86_64-linux-gnu/libpthread-2.23.so 
7fc931ea9000-7fc9320a8000 ---p 00018000 08:02 4994056     /lib/x86_64-linux-gnu/libpthread-2.23.so 
7fc9320a8000-7fc9320a9000 r--p 00017000 08:02 4994056     /lib/x86_64-linux-gnu/libpthread-2.23.so 
7fc9320a9000-7fc9320aa000 rw-p 00018000 08:02 4994056     /lib/x86_64-linux-gnu/libpthread-2.23.so 
7fc9320aa000-7fc9320ae000 rw-p 00000000 00:00 0 
7fc9320ae000-7fc9320d4000 r-xp 00000000 08:02 4994051     /lib/x86_64-linux-gnu/ld-2.23.so 
7fc9322b5000-7fc9322b8000 rw-p 00000000 00:00 0 
7fc9322d0000-7fc9322d3000 rw-p 00000000 00:00 0 
7fc9322d3000-7fc9322d4000 r--p 00025000 08:02 4994051     /lib/x86_64-linux-gnu/ld-2.23.so 
7fc9322d4000-7fc9322d5000 rw-p 00026000 08:02 4994051     /lib/x86_64-linux-gnu/ld-2.23.so 
7fc9322d5000-7fc9322d6000 rw-p 00000000 00:00 0 
7ffc92bdb000-7ffc92bfc000 rw-p 00000000 00:00 0       [stack] 
7ffc92bfc000-7ffc92bfe000 r--p 00000000 00:00 0       [vvar] 
7ffc92bfe000-7ffc92c00000 r-xp 00000000 00:00 0       [vdso] 
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0     [vsyscall] 
Aborted (core dumped) 

编辑：

我的示例代码仅仅是一个粗略的草图，我认为我自己是C的初学者。这可能是我的问题不明确的原因。在我的实际代码中，我正在每个处理器上使用我的粒子（2D中的四叉树和3D中的八叉树）构建树结构。每个处理器都有其他粒子。我使用递归树行走中树的位置来识别错误的粒子，并将它们发送给其他处理器，因为我想要紧凑的树结构。为了做到这一点，我必须将错误的粒子放入一个列表中，然后我可以将它传递给MPI库，以便将数据发送到其他处理器。粒子的数量通常远大于处理器的数量（N >> numProc）。

Answer 1

我不太明白你的推理，它可能会优化计算速度，但你需要有一个工作程序来考虑这样做。

此外，您的分配粒子到处理器的算法不起作用。正如它所写，粒子有70％的机会不被分配到任何列表。

在你申报颗粒的名单：

typedef struct { 
    double **list; // a list of double* ? It's going to be hard to find which double 
        // belongs to which Particle, this makes your app more confusing 
        // and much harder to write than it ought to. 
    int *counter; // a length of lengths? what's its length? 
} ParticleList; 

您应该考虑做这样的事情吧。这可能会更好，我省略了calloc（）的结果的错误检查，你应该始终这样做。我选择了calloc（），因为它清除了它分配的内存。

typedef struct { 
    struct Particle* next; 
    double m; 
    double x[DIM]; 
    int id; 
} Particle; 

typedef struct Particle* ParticleList; 

// this should look familiar to you. 
void insert_particle(ParticleList* list, struct Particle* part) 
{ 
    part->next = NULL; // just to make sure we don't introduce bugs here 
    if (*list == NULL) 
    { 
    *list = part; 
    return; 
    } 
    struct Particle* p = *list; 
    while (p) 
    { 
    if (p->next == NULL) 
    { 
     p->next = part 
     return; 
    } 
    p = p->next; 
    } 
} 

int main() 
{ 
    int i; 
    int numProcs = 4; 
    int assigned_proc; 
    int N = 3; // less particles than threads? This does not sound right... 
    // ... 
    // allocate empty lists and all particles. 
    ParticleList* procparts = calloc(numprocs, sizeof(ParticleList)); 
    struct Particle* particles = calloc(N, sizeof(struct Particle)); 

    for (i = 0; i < N; ++i)      // for each particle ... 
    { 
    // initialize particle location... 
    particles[i].id = i; 
    // ... and x[]... 

    assigned_proc = rand() % numprocs;   // pick a processor... 

    insert_particle(&procparts[assigned_proc], &particles[i]); 
    } 

    // ... 
} 

注意，此实现不需要任何调用realloc（）的执行过程中。

一旦你的应用程序使用'普通'线程工作，它将更加简单，使其MPI兼容。