第4章：数据结构优化：数组 vs 链表、环形缓冲区、内存池设计

做运动控制这些年，我踩过最大的坑，往往不是算法本身，而是数据结构的选型。你想想看，一个伺服驱动器每100微秒就要跑完一轮位置环计算，如果数据存取慢了几个微秒，整个系统的抖动就上来了。今天咱们就聊聊数据结构优化这件事。

4.1 数组 vs 链表：选对工具，事半功倍

先说数组。数组在内存里是连续存储的，CPU缓存命中率极高。我习惯在运动控制中用数组来存储轨迹点——因为访问模式是顺序的，预取器能提前把数据拉进缓存。

// 轨迹点数组，连续内存，访问效率高
typedef struct {
    float position;
    float velocity;
    float acceleration;
} TrajectoryPoint;

TrajectoryPoint trajectory[1024];  // 预分配，无动态开销

链表呢？它的优势在于动态插入和删除。但代价是什么？每个节点都有额外的指针开销，而且内存不连续，缓存友好性差。我在项目中遇到过用链表管理实时任务队列的情况——结果每次遍历都要等内存访问，延迟直接翻倍。

4.2 环形缓冲区：无锁通信的利器

环形缓冲区，说白了就是一个固定大小的数组，配上两个指针——读指针和写指针。它最妙的地方在于：不需要加锁就能实现单生产者单消费者的通信。

我做过一个多轴同步项目，上位机每1ms下发一批指令，下位机每100μs取一条执行。如果用队列加锁，光锁竞争就能吃掉30%的CPU时间。换成环形缓冲区后，延迟从15μs降到了2μs。

typedef struct {
    float cmd[BUFFER_SIZE];  // 指令缓冲区
    uint32_t head;           // 写指针
    uint32_t tail;           // 读指针
} RingBuffer;

// 写入（生产者）
bool ring_buffer_push(RingBuffer* rb, float value) {
    uint32_t next = (rb->head + 1) % BUFFER_SIZE;
    if (next == rb->tail) return false;  // 缓冲区满
    rb->cmd[rb->head] = value;
    rb->head = next;
    return true;
}

// 读取（消费者）
bool ring_buffer_pop(RingBuffer* rb, float* value) {
    if (rb->tail == rb->head) return false;  // 缓冲区空
    *value = rb->cmd[rb->tail];
    rb->tail = (rb->tail + 1) % BUFFER_SIZE;
    return true;
}

4.3 内存池：告别动态分配的开销

动态内存分配（malloc/free）在运动控制中是大忌。为什么？因为分配时间不确定，可能几微秒，也可能几百微秒。你想想看，一个实时任务被malloc卡住，后果是什么？

内存池的思路很简单：提前分配一大块内存，切成固定大小的块，用链表串起来。需要时直接取一个块，用完再还回去。整个过程没有系统调用，时间确定，纳秒级完成。

typedef struct {
    uint8_t pool[POOL_SIZE][BLOCK_SIZE];  // 预分配内存块
    uint32_t free_list[POOL_SIZE];         // 空闲块索引链表
    uint32_t free_head;                    // 空闲链表头
} MemoryPool;

void* pool_alloc(MemoryPool* pool) {
    if (pool->free_head == INVALID_INDEX) return NULL;
    uint32_t index = pool->free_head;
    pool->free_head = pool->free_list[index];
    return pool->pool[index];
}

void pool_free(MemoryPool* pool, void* ptr) {
    uint32_t index = ((uint8_t*)ptr - pool->pool[0]) / BLOCK_SIZE;
    pool->free_list[index] = pool->free_head;
    pool->free_head = index;
}

4.4 实战对比：三种方案的性能差异

我拿一个实际案例来对比。假设我们要管理1000个运动指令，分别用数组、链表、环形缓冲区+内存池来实现，看看性能差距。

方案	插入耗时	遍历耗时	内存碎片	实时性
动态数组	O(1) 均摊	O(n) 极快	无	高
标准链表	O(1) 但慢	O(n) 慢	严重	低
环形缓冲区+内存池	O(1) 极快	O(n) 快	无	极高

你看，环形缓冲区+内存池的组合，在实时性上完胜。实际测试中，标准链表的遍历时间比数组慢了5-8倍，而内存池分配比malloc快了100倍以上。

4.5 知识体系总览

下面这张图，是我梳理的数据结构优化核心逻辑。你可以把它当作一个决策树来用。

嗯，这张图把核心逻辑讲清楚了。你从根节点往下走，先看访问模式——顺序访问用数组，生产者/消费者用环形缓冲区，需要动态分配就用内存池。三者不是互斥的，实际项目中经常组合使用。

我曾经在一个六轴机器人项目中，把链表全部换成数组+内存池，位置环的执行时间从85μs降到了32μs。你想想看，这多出来的50多微秒，足够再做一轮速度前馈计算了。