如何为基于Trie的拼写检查器实现内存池以减少malloc调用？

我完成了CS50x课程中基于Trie的字典拼写检查器，已通过check50测试和valgrind内存检测，无内存错误。目前想通过实现**内存池（memory arena）**减少malloc调用次数，优化加载和卸载性能。

现有代码 #

dictionary.h #

// Declares a dictionary's functionality

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>

// Maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45
#define N 27
// Trie node definition
typedef struct TrieNode
{
    struct TrieNode *children[N];
    bool isEnd;
} TrieNode;

// Prototypes
bool check(const char *word);
bool load(const char *dictionary);
unsigned int size(void);
bool unload(void);

TrieNode *create_trie(void);
bool trie_insert(TrieNode **head, const char *word);
void trie_clear(TrieNode *root_ref);

#endif // DICTIONARY_H

dictionary.c #

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "dictionary.h"

// Macros
#define key(c) (c>='a'&&c<='z')?(c-'a'):(c>='A'&&c<='Z')?(c-'A'):26

// word count
unsigned int word_count = 0;

// Root trie node
TrieNode *root;

// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    // Declare tmp ptr to root
    TrieNode *tmp = root;

    for (int i = 0 , n = strlen(word); i < n; i++)
    {
        int t = key(word[i]);
        if (tmp->children[t] == NULL)
        {
            return false;
        }
        tmp = tmp->children[t];
    }
    // Did index values lead to valid terminal?
    return tmp->isEnd;
}

TrieNode *create_trie(void)
{
    TrieNode *result = malloc(sizeof(*result));
    for (int i = 0; i < N; i++)
    {
        result->children[i] = NULL;
    }
    result->isEnd = false;
    return result;
}

// Double ptr allows us to alter the root node
bool trie_insert(TrieNode **head, const char *word)
{
    if (*head == NULL)
    {
        *head = create_trie();
    }

    TrieNode *tmp = *head;

    for (int i = *word++; *word; i = *word++)
    {
        unsigned int t = key(i);
        if (tmp->children[t] == NULL)
        {
            tmp->children[t] = create_trie();
        }
        tmp = tmp->children[t];
    }
    tmp->isEnd = true;
    return true;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    // open dictionary file
    FILE *dict = fopen(dictionary, "rb");
    if (!dict)
    {
        return false;
    }
    // allocate more memory than needed for LENGTH chars
    char *word = malloc(sizeof(char) * LENGTH + 2);
    if (!word)
    {
        fclose(dict);
        return false;
    }
    // Keep reading infile word by word until NULL
    while (fgets(word, LENGTH + 2, dict))
    {
        // Skip all words that exceed length limit
        size_t word_length = strlen(word);
        if (word_length > LENGTH + 1)
        {
            break;
        }

        if (trie_insert(&root, word))
        {
            word_count++;
        }
    }

    // Free buffer and close infile
    free(word);
    fclose(dict);
    return true;
}

bool unload(void)
{
    trie_clear(root);
    return true;
}

void trie_clear(TrieNode *root_ref)
{
    TrieNode *tmp = root_ref;

    for (int i = 0; i < N; i++)
    {
        if (tmp->children[i])
        {
            trie_clear(tmp->children[i]);
        }
    }
    free(tmp);
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    return word_count;
}

初始测试结果 #

对比官方实现，我的方案在加载和卸载阶段耗时明显更长：

My solution                                             Staff solution

WORDS MISSPELLED:     955                               WORDS MISSPELLED:     955
WORDS IN DICTIONARY:  143091                            WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        17756                             WORDS IN TEXT:        17756
TIME IN load:         0.08                            | TIME IN load:         0.03
TIME IN check:        0.02                              TIME IN check:        0.02
TIME IN size:         0.00                              TIME IN size:         0.00
TIME IN unload:       0.04                            | TIME IN unload:       0.01
TIME IN TOTAL:        0.14                            | TIME IN TOTAL:        0.06

优化需求与问题 #

我认为加载慢的核心原因是逐个Trie节点调用malloc申请内存。调研后发现内存池方案可以减少malloc总调用次数，但多数资料仅提供理论说明，仅找到一个适用于哈希表拼写检查器的内存池实现：

哈希节点定义：

typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
    unsigned int hash;
} node;

内存段定义：

// adjust this value to suit
#define ARENASIZE       1000

// Structure for slab allocation of 1000 hash nodes as a linked list
typedef struct seg seg_t;
struct seg
{
    seg_t *seg_next;                // next segment
    int seg_count;                  // number of used nodes in this segment
    node seg_node[ARENASIZE];       // nodes in this segment
};

请问将该结构适配到我的Trie实现中，仅把哈希节点数组替换为Trie节点数组（TrieNode seg_node[ARENASIZE]）即可，还是需要做其他修改？

优化更新成果 #

已成功为现有代码添加内存池分配功能，测试结果如下：

WORDS MISSPELLED:     12544                 WORDS MISSPELLED:     12544
WORDS IN DICTIONARY:  143091                WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        265867                WORDS IN TEXT:        265867
TIME IN load:         0.07                | TIME IN load:         0.03
TIME IN check:        0.24                | TIME IN check:        0.26
TIME IN size:         0.00                  TIME IN size:         0.00
TIME IN unload:       0.00                | TIME IN unload:       0.02
TIME IN TOTAL:        0.32                | TIME IN TOTAL:        0.30

意外的是加载时间未明显减少，但卸载时间几乎降为0；同时改用calloc后，查询时间始终持平或优于官方方案，总耗时仅比官方慢0.02-0.04秒。

内容的提问来源于stack exchange，提问作者Jordan Chen