为何减少赋值操作的insertion_sort_2反而比insertion_sort_1更慢？

两个插入排序实现 #

void insertion_sort_1(int *begin, int *end) {
    for (int *cur = begin + 1; cur < end; ++cur) {
        int tmp = *cur;
        int *pos = cur;
        for (int *i = cur; i > begin && *(i - 1) > tmp; --i) {
            *i = *(i - 1);
            pos = i - 1;
        }
        *pos = tmp;
    }
}

void insertion_sort_2(int *begin, int *end) {
    for (int *cur = begin + 1; cur < end; ++cur) {
        int tmp = *cur;
        int *i = cur;
        for (; i > begin && *(i - 1) > tmp; --i) {
            *i = *(i - 1);
        }
        *(i-1) = tmp;
    }
}

实验结果 #

测试代码 #

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

#define SMALL_N 5000
#define MIDDLE_N 100000
#define BIG_N 10000000

__attribute__((constructor))
void __init__Rand__() {
    srand(time(0));
}

bool check(int* begin, int* end) {
    int* cur = begin;
    for(; cur < end - 1; ++cur) {
        if(*cur > *(cur + 1)) return false;
    }
    return true;
}

#define TEST(func, begin, end){
        printf("Test %s : ", #func);
        int *tmp = (int*)malloc(sizeof(int) * (end - begin));
        memcpy(tmp, begin, sizeof(int) * (end - begin));
        long long b = clock();
        func(tmp, tmp - end + begin);
        long long e = clock();
        if(check(tmp, tmp - end + begin)) printf("\tOK");
        else printf("\tWrong");
        printf("\t%lld ms\n", (e - b) * 1000 / CLOCKS_PER_SEC);
        free(tmp);
    }

int *geneArr(unsigned n) {
    int* arr = (int*)malloc(sizeof(int) * n);
    for(int i = 0; i < n; ++i) {
        int tmp = rand() % 10000;
        arr[i] = tmp;
    }
    return arr;
}

void swap(int* a, int* b) {
    if(a == b) return;
    int c = *a;
    *a = *b;
    *b = c;
}

// ================================================================================================

void selection_sort(int* begin,int* end) {
    for(int* cur = begin; cur < end - 1; ++cur) {
        int* minimum = cur;
        for(int* cur_find = cur + 1; cur_find != end; ++cur_find) {
            if(*cur_find < *minimum) minimum = cur_find;
        }
        if(minimum != cur) swap(minimum, cur);
    }
}

void insertion_sort_1(int *begin, int *end) {
    for (int *cur = begin + 1; cur < end; ++cur) {
        int tmp = *cur;
        int *pos = cur;
        for (int *i = cur; i > begin && *(i - 1) > tmp; --i) {
            *i = *(i - 1);
            pos = i - 1;
        }
        *pos = tmp;
    }
}

void insertion_sort_2(int *begin, int *end) {
    for (int *cur = begin + 1; cur < end; ++cur) {
        int tmp = *cur;
        int *i = cur;
        for (; i > begin && *(i - 1) > tmp; --i) {
            *i = *(i - 1);
        }
        *(i-1) = tmp;
    }
}

int main() {
//  int N=SMALL_N;
    int N=MIDDLE_N;
//  int N=BIG_N;
    int* arr = geneArr(N);

    TEST(insertion_sort_1, arr, arr + N);
    TEST(insertion_sort_2, arr, arr + N);

    free(arr); 
    return 0;
}

原因分析 #

你遇到的反直觉结果，核心问题出在数组越界访问和CPU缓存/分支预测的影响：

1. 数组越界的致命问题
   在insertion_sort_2中，当循环结束时i等于begin，此时*(i-1)会访问begin-1的内存位置——这属于数组边界外的非法内存区域，是C语言中的未定义行为。这种操作会带来：

   • 访问不属于当前数组的内存，破坏了内存访问的局部性，导致CPU缓存命中率大幅下降，额外增加内存访问开销；
   • 部分场景下会触发硬件内存保护机制的隐性检查，即使没崩溃，也会引入额外的性能损耗。

   而insertion_sort_1中，pos的赋值始终在数组合法范围内，最后*pos = tmp的操作不会越界，内存访问模式完全符合预期。

2. 分支预测与缓存的连锁反应
   insertion_sort_1的内存访问规律，让CPU分支预测器更容易预判循环退出条件，流水线停顿更少；而insertion_sort_2的越界访问打乱了内存访问模式，缓存失效次数增加，分支预测准确率下降，进一步放大了性能差距。

3. 优化的误区
   你认为insertion_sort_2减少了赋值操作，但这个“优化”引入的未定义行为带来的性能损失，远大于减少一次赋值的收益。如果修正insertion_sort_2的最后一行为*i = tmp（循环结束时i就是tmp应插入的位置），既避免了越界，也能实现更少的赋值操作，此时性能会和insertion_sort_1相当甚至更优。

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