32位环境下SkipList插入5200万数据时malloc失败求助

问题背景 #

出于学术目的用C语言实现跳表，插入5200万整数后，尽管Win10 64位系统配备16GB物理内存，仍出现malloc分配失败，errno值为12（表示内存不足）。运行环境为32位Code::Blocks 16.01。

实现代码 #

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

// ===============================================
// SkipList
// ===============================================
struct NO{
    int key;
    struct NO **next;
};

typedef struct SkipList SkipList;
struct SkipList{
    int levelMAX;
    float P;
    int level;
    struct NO *start;
};

struct NO* newNode(int key, int level){
    struct NO* node = malloc(sizeof(struct NO));
    if(node != NULL){
        node->key = key;
        node->next = malloc((level+1)* sizeof(struct NO*));
        int i;
        for(i=0; i<(level+1); i++)
            node->next[i] = NULL;
    }
    return node;
}

SkipList* createSkipList(int levelMAX, float P){
    SkipList *sk = (SkipList*) malloc(sizeof(SkipList));
    if(sk != NULL){
        sk->levelMAX = levelMAX;
        sk->P = P;
        sk->level = 0;
        sk->start = newNode(-1, levelMAX);
    }
    return sk;
}

int drawlevel(SkipList *sk){
    float r = (float)rand()/RAND_MAX;
    int level = 0;
    while(r < sk->P && level < sk->levelMAX){
        level++;
        r = (float)rand()/RAND_MAX;
    }
    return level;
}


int insertSkipList(SkipList *sk, int key){
    if(sk == NULL)
        return 0;

    int i;
    struct NO *atual = sk->start;
    struct NO **aux;
    aux = malloc((sk->levelMAX+1) * sizeof(struct NO*));
    for(i = 0; i <= sk->levelMAX; i++)
        aux[i] = NULL;

    for(i = sk->level; i >= 0; i--){
        while(atual->next[i] != NULL && atual->next[i]->key < key)
            atual = atual->next[i];
        aux[i] = atual;
    }

    atual = atual->next[0];

    if(atual == NULL || atual->key != key){
        int node_level = drawlevel(sk);
        struct NO* node = newNode(key, node_level);
        if(node == NULL){
            free(aux);
            return 0;
        }

        if(node_level > sk->level){
            for(i = sk->level+1; i <= node_level; i++)
                aux[i] = sk->start;

            sk->level = node_level;
        }

        for(i = 0; i <= node_level; i++){
            node->next[i] = aux[i]->next[i];
            aux[i]->next[i] = node;
        }

        free(aux);
        return 1;
    }

    free(aux);
    return 0;
}

void freeSkipList(SkipList* sk){
    if(sk == NULL)
        return;

    struct NO *no, *atual;
    atual = sk->start->next[0];
    while(atual != NULL){
        no = atual;
        atual = atual->next[0];
        free(no->next);
        free(no);
    }

    free(sk->start);
    free(sk);
}

// ===============================================

#define M 30
void Knuth_shuffle(int *array, int n){
    srand(time(NULL));
    int i, j, tmp;
    for(i = n - 1; i > 0; i--){
        j = rand() % (i + 1);
        tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }
}

int* generateNumbers(int N){
    int *V = malloc(N * sizeof(int));
    if(V == NULL)
        return NULL;

    int i;
    for(i=0; i< N; i++)
        V[i] = i;

    Knuth_shuffle(V,N);
    return V;
}

void runSkipList(int *data, int N){
    int i, j, c = 0;
    int k = N / M;
    double ti;
    clock_t start, end;

    srand((unsigned)time(0));
    SkipList *sk = createSkipList(25, 0.5);

    start = clock();
    for(i=0; i < M; i++){
        for(j=0; j < k; j++){
            insertSkipList(sk,data[c]);
            c++;
        }
        end = clock();
        ti = ((double)(end - start)) / CLOCKS_PER_SEC;
        printf("%d) %.10f sec\n",i+1,ti);
    }

    freeSkipList(sk);
}

int main(){
    int i, N = 60000000;
    int *data = generateNumbers(N);

    runSkipList(data, N);

    free(data);
    return 0;
}

原因分析 #

1. 32位进程地址空间限制：Windows下32位进程默认仅能使用2GB虚拟地址空间，即便物理内存充足，进程也无法突破该上限。5200万次插入操作中，每次都分配aux数组（104字节），频繁的malloc/free会导致地址空间碎片化，后续即使总剩余内存足够，也无法找到连续的内存块完成分配。
2. 内存分配效率问题：每次插入都动态分配aux数组，不仅增加了内存开销，还加剧了内存碎片的产生，加速了地址空间的耗尽。

解决方案 #

1. 切换到64位编译环境 #

这是最根本的解决方法：安装64位版本的Code::Blocks或其他支持64位编译的工具（如Visual Studio）。64位进程的虚拟地址空间可达8TB，能充分利用16GB物理内存，彻底规避32位地址空间的限制。

2. 优化内存分配逻辑 #

• 复用aux数组：避免每次插入都重新分配aux，改为在runSkipList中提前分配一次，传入insertSkipList函数复用，减少内存碎片。优化后的关键代码如下：

  // 修改insertSkipList函数，移除内部的aux分配/释放
  int insertSkipList(SkipList *sk, int key, struct NO **aux){
      if(sk == NULL)
          return 0;
  
      int i;
      struct NO *atual = sk->start;
  
      for(i = sk->level; i >= 0; i--){
          while(atual->next[i] != NULL && atual->next[i]->key < key)
              atual = atual->next[i];
          aux[i] = atual;
      }
  
      atual = atual->next[0];
  
      if(atual == NULL || atual->key != key){
          int node_level = drawlevel(sk);
          struct NO* node = newNode(key, node_level);
          if(node == NULL){
              return 0;
          }
  
          if(node_level > sk->level){
              for(i = sk->level+1; i <= node_level; i++)
                  aux[i] = sk->start;
  
              sk->level = node_level;
          }
  
          for(i = 0; i <= node_level; i++){
              node->next[i] = aux[i]->next[i];
              aux[i]->next[i] = node;
          }
  
          return 1;
      }
  
      return 0;
  }
  
  // 修改runSkipList，提前分配aux并复用
  void runSkipList(int *data, int N){
      int i, j, c = 0;
      int k = N / M;
      double ti;
      clock_t start, end;
  
      srand((unsigned)time(0));
      SkipList *sk = createSkipList(25, 0.5);
      // 提前分配aux数组
      struct NO **aux = malloc((sk->levelMAX+1) * sizeof(struct NO*));
      for(i = 0; i <= sk->levelMAX; i++)
          aux[i] = NULL;
  
      start = clock();
      for(i=0; i < M; i++){
          for(j=0; j < k; j++){
              insertSkipList(sk,data[c], aux);
              c++;
          }
          end = clock();
          ti = ((double)(end - start)) / CLOCKS_PER_SEC;
          printf("%d) %.10f sec\n",i+1,ti);
      }
  
      free(aux); // 最后释放aux
      freeSkipList(sk);
  }
  

• 使用内存池：预分配一批节点内存，避免频繁调用malloc，进一步减少内存碎片。
• 合理设置层级上限：根据数据量计算所需的最大层级（如对于N个元素，p=0.5时，最大层级建议设为log2(N)+1），避免不必要的内存占用。

3. 临时缓解方案（不推荐） #

若暂时无法切换到64位环境，可通过修改PE头启用32位进程的4GB地址空间支持：在Code::Blocks中添加链接选项/LARGEADDRESSAWARE，但这仅能将虚拟地址空间上限提升至4GB，无法从根本解决32位架构的限制。

内容的提问来源于stack exchange，提问作者André Backes