粗粒度与细粒度链表性能对比异常问题求助

我正在研究并发数据结构，实现了粗粒度锁链表与细粒度（Hand-over-Hand）锁链表并开展时间性能对比测试，但结果与预期相反——细粒度锁链表的性能表现更差。我想知道这完全是锁开销导致的，还是我的实现存在错误。

粗粒度锁链表代码 #

struct Node {
    int data;
    Node* next;

    Node(int k) : data(k), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;
    mutex lock;

public:
    LinkedList() : head(nullptr) {}

    void insert_node(int data) {
        Node* new_node = new Node(data);
        
        lock.lock();
        if(head == nullptr) {
            head = new_node;
        } else if(head->data >= data) {
            new_node->next = head;
            head = new_node;
        }
        else {
            Node* prev = nullptr;
            Node* curr = head;

            while(curr != nullptr and data > curr->data) {
                prev = curr;
                curr = curr->next;
            }
            prev->next = new_node;
            new_node->next = curr;
        }
        lock.unlock();
    }

    void delete_node(int data) {
        Node* prev = nullptr;

        lock.lock();
        Node* curr = head;
        while(curr != nullptr) {
            if(curr->data == data) {
                if(prev == nullptr)
                    head = curr->next;
                else
                    prev->next = curr->next;

                delete curr;
                break;
            }

            prev = curr;
            curr = curr->next;
        }
        lock.unlock();
    }
};

细粒度（Hand-over-Hand）锁链表代码 #

struct HOHNode {
    int data;
    HOHNode* next;
    mutex node_lock;

    HOHNode(int k) : data(k), next(nullptr) {}
};

class HOHLinkedList {
private:
    HOHNode* head;
    mutex list_lock;
public:
    HOHLinkedList() : head(nullptr) {}

    void insert_node(int data) {
        HOHNode* new_node = new HOHNode(data);
        
        list_lock.lock();
        if(head == nullptr or head->data >= data) {
            if(head != nullptr)
                head->node_lock.lock();
            new_node->next = head;
            head = new_node;
            list_lock.unlock();
            if(new_node->next != nullptr)
                new_node->next->node_lock.unlock();
        }
        else {
            HOHNode* prev = head;
            HOHNode* curr = head->next;

            prev->node_lock.lock();
            list_lock.unlock();
            if(curr != nullptr)
                curr->node_lock.lock();
            
            while(curr != nullptr and data > curr->data) {
                HOHNode* temp = prev;
                prev = curr;
                curr = curr->next;
                temp->node_lock.unlock();
                if(curr != nullptr)
                    curr->node_lock.lock();
            }

            new_node->next = curr;
            prev->next = new_node;
            prev->node_lock.unlock();
            if(curr != nullptr)
                curr->node_lock.unlock();
        }
    }

    void delete_node(int data) {
        list_lock.lock();
        HOHNode* prev = head;
        prev->node_lock.lock();
        if(prev->data == data) {
            head = prev->next;
            prev->node_lock.unlock(); // editted
            delete prev;
            list_lock.unlock();
        } else {
            HOHNode* curr = head->next;
            list_lock.unlock();
            if(curr != nullptr) {
                curr->node_lock.lock();
            }
            
            while(curr != nullptr and data >= curr->data) {
                if(curr->data == data) {
                    prev->next = curr->next;
                    curr->node_lock.unlock(); // editted
                    delete curr;
                    prev->node_lock.unlock();
                    return;
                }

                HOHNode* temp = prev;
                prev = curr;
                curr = curr->next;
                temp->node_lock.unlock();
                curr->node_lock.lock();
            }
        }
    }
};

测试场景与结果 #

• 环境：4核8线程，g++ 9.4.0编译器
• 测试流程：对1到1000的数字进行乱序插入，再执行乱序删除（未处理删除不存在元素的情况）
• 结果：细粒度锁链表的插入、删除耗时均显著高于粗粒度锁链表，性能表现不如预期。

问题分析与修正建议 #

一、实现中的核心错误 #

1. Hand-over-Hand锁顺序颠倒
   遍历链表时，代码先释放前一个节点的锁，再获取下一个节点的锁：

   temp->node_lock.unlock();
   if(curr != nullptr)
       curr->node_lock.lock();
   

   这会导致在释放prev锁到获取curr锁的间隙，其他线程可能修改prev的next指针，导致curr指向错误节点，破坏链表一致性。正确顺序应该是先获取下一个节点的锁，再释放当前节点的锁：

   if(curr != nullptr)
       curr->node_lock.lock();
   temp->node_lock.unlock();
   

2. delete操作的空指针崩溃风险
   在delete的while循环中，当curr变为nullptr时，代码仍然执行curr->node_lock.lock()，直接触发空指针解引用，导致程序崩溃。必须在加锁前检查curr是否为nullptr。

3. 全局list_lock的过度使用
   insert和delete开头都持有list_lock，这相当于在操作初始阶段加了全局锁，大幅削弱了细粒度锁的并发优势。建议用**哨兵节点（dummy head）**替代list_lock，初始时链表包含一个空的哨兵节点，所有操作从哨兵节点开始遍历加锁，避免全局锁的使用。

4. 删除头部节点的时序问题
   删除头部节点时，先释放prev的锁再释放list_lock，此时其他线程可能通过list_lock获取到已经被删除的节点指针，存在线程安全隐患。正确顺序应该是先更新head，再释放list_lock，最后释放node_lock并删除节点。

二、锁开销的影响 #

当测试数据量小（仅1000个元素）、线程数不多时，细粒度锁的多次加解锁开销（内核态切换）会超过并发带来的收益。粗粒度锁只需要一次加解锁，在这种场景下开销更低。若要体现细粒度锁的优势，建议：

• 增大测试数据量（比如10万或100万元素）
• 增加并发线程数（比如8或16线程）
  此时全局锁会导致大量线程阻塞，而细粒度锁允许不同线程同时操作链表的不同段，性能优势会凸显。

内容的提问来源于stack exchange，提问作者Ma Joonyoung