在c++中优化指针拷贝

Question

所以今天我试图优化链表遍历。我的想法是，当我只需要复制一次时，把一个拷贝到最后一个，然后再拷贝到另一个，效率会更低。希望下面的代码能让它更清晰:

struct Node{
    int body;
    Node* next;
};
Node* construct(int len){
    Node *head, *ptr, *end;
    head = new Node();
    ptr = head;
    ptr->body = 0;
    for(int i=1; i<len; i++){
        end = new Node();
        end->next = NULL;
        end->body = i;
        ptr->next = end;
        ptr = end;
    }
    return head;
}
int len(Node* ptr){
    int i=1;
    while(ptr->next){
        ptr = ptr->next;
        i += 1;
    }
    return i;
}
void trim(Node* head){
    Node *last, *cur;
    cur = head;
    while(cur->next){
        last = cur;
        cur = cur->next;
    }
    last->next = NULL;
}
void tumble_trim(Node* head){ // This one uses less copies per traverse
    Node *a, *b;
    a = head;
    while(true){
        if(!a->next){
            b->next = NULL;
            break;
        }
        b = a->next;
        if(!b->next){
            a->next = NULL;
            break;
        }
        a = b->next;
    }
}
int main(){
    int start;
    Node *head;
    start = clock();
    head = construct(100000);
    for(int i=0; i<5000; i++){
        trim(head);
    }
    cout << clock()-start << endl;
    start = clock();
    head = construct(100000);
    for(int i=0; i<5000; i++){
        tumble_trim(head);
    }
    cout << clock()-start << endl;
}

然而，结果让我很惊讶。事实上，拷贝数少的那张更慢:

1950000
2310000 // I expected this one to be faster

谁能解释为什么tumble_trim()函数这么慢?

Answer 1

你的编译器显然比tumble_trim()更能优化trim()。这是保持代码简单易读的最好例子，在通过性能分析确定瓶颈后，只尝试任何优化。即使这样，您也很难在这样一个简单的循环中击败编译器。

Answer 2

下面是为这两个函数生成的程序集的相关部分:(只是while循环:

修剪:

LBB2_1:                                 ## =>This Inner Loop Header: Depth=1
    movq    %rcx, %rax
    movq    %rdi, %rcx
    movq    8(%rdi), %rdi
    testq   %rdi, %rdi
    jne LBB2_1
## BB#2:

tumbletrim:

LBB3_1:                                 ## =>This Inner Loop Header: Depth=1
    movq    %rdi, %rax
    movq    8(%rax), %rdx
    testq   %rdx, %rdx
    je  LBB3_2
## BB#3:                                ##   in Loop: Header=BB3_1 Depth=1
    movq    8(%rdx), %rdi
    testq   %rdi, %rdi
    movq    %rdx, %rcx
    jne LBB3_1
## BB#4:
    movq    $0, 8(%rax)
    popq    %rbp
    ret
LBB3_2:

现在，让我们试着描述在每个

中发生了什么:

在trim中，执行以下步骤:

1. 复制3个指针大小的值
2. 测试while循环
的条件
3. 如果条件满足，跳到循环的开始

换句话说，每次迭代包含3个拷贝，1个测试和1个跳转指令。

现在，你聪明地优化了tumbletrim:

1. 复制2个指针大小的值
2. 测试断开条件
3. 如果条件满足，跳到循环的末尾
4. else复制指针大小的值
5. 测试while循环
的条件
6. 复制指针大小的值
7. 跳到循环的开始

换句话说，在最后的迭代中，当退出循环时，执行的指令总数为:

• 修剪:3个指针拷贝，1个比较
• tumbletrim: 2个指针，1个比较，1个跳转

在所有其他迭代中，总数如下所示:

• 修剪:3个指针复制，1个比较，1个跳转
• tumbletrim: 4个指针复制，2个比较，1个跳转

因此，在极少数情况下(退出循环前的最后一次迭代)，您的实现更便宜当且仅当跳转指令比从寄存器复制指针大小的值更便宜(事实并非如此)

在一般情况下(所有其他迭代)，您的实现有更多的拷贝和比较。指令越多，指令缓存的负载就越大。和更多的分支语句，在分支缓存上增加更多的负载)

现在，如果你首先关心性能，那么有两件更基本的事情你做错了:

1. 您正在使用链表。链表之所以慢，是因为它们执行的算法(因为节点不是连续分配的，所以需要在内存中跳转)，而不是因为实现。所以无论你的实现有多聪明，它都无法弥补底层算法的糟糕
2. 你在写你自己的链表。如果你绝对必须使用链表，请使用专家编写的链表(std::list)