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

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 兼容就会简单得多。