那些不应该的优化

看到遍历就不舒服，奈何还知道空间换时间，并且屡次从 “给结构体加字段而大幅度优化程序运行性能” 这种事里拿到不少甜头，就会形成条件反射，看到循环遍历就想优化。

Linux 内核 Hash 链表有一个陈年接口，它的 add_tail 竟然还要遍历：

static inline void hlist_add_tail_rcu(struct hlist_node *n,
                                      struct hlist_head *h)
{
        struct hlist_node *i, *last = NULL;

        /* Note: write side code, so rcu accessors are not needed. */
        for (i = h->first; i; i = i->next)
                last = i;

        if (last) {
                n->next = last->next;
                WRITE_ONCE(n->pprev, &last->next);
                rcu_assign_pointer(hlist_next_rcu(last), n);
        } else {
                hlist_add_head_rcu(n, h);
        }
}

上面的这个接口实现很容易被信手 “优化”：

struct hlist_head {
    struct hlist_node *first;
    // 增加一个 last 字段，记录锚点
    struct hlist_node *last;
};
static inline void hlist_add_tail_rcu(struct hlist_node *n,
                                      struct hlist_head *h)
{
        if (h->last) {
                n->next = h->last->next;
                WRITE_ONCE(n->pprev, &h->last->next);
                rcu_assign_pointer(hlist_next_rcu(h->last), n);
        } else {
                hlist_add_head_rcu(n, h);
        }
        h->last = n;
}

遍历没有了，代价是每个 hlist_head 增加一个 8 字节字段，1000 个就要消耗 8KB 的空间，但这说服不了谁，没人在乎那 8KB，就算 80MB 又如何。

但以上的修改却节省不了多少时间。

hlist 就是冲 Hash 的 O(1) 去的，正常情况下它一定很短，如果太长了，要么 Hash 函数不良，要么 Hash bucket 太少，首要解决 Hash 冲突问题，而不是遍历冲突链表的问题。

所以 hlist_add_tail_rcu 很好，无需优化。

这涉及到解决问题的思路问题，你是盯着问题还是盯着方法，还是让问题消失，下图就是一个例子：

浙江温州皮鞋湿，下雨进水不会胖。