程序员
编程
效率
C++

strstr函数的效率为什么那么高？

我想测试一下sunday算法和strstr算法在字符串长度只有30左右的效率的，但是发现为什么strstr函数的效率和一个近乎空的（只有判断传入的参数…
关注者
7
被浏览
9,247

2 个回答

104 实现strstr函数
1839 播放 · 1 赞同
发布于 2021-07-27 23:18· 721 次播放

简要答案：

因为你没利用strstr的返回值，这个函数根本就没被调用。而编译器不敢优化你自己写的函数。

具体过程：

我们来进行一下测试：

1. g++ 5.3.0, Linux x64

编译选项：g++ -g -o test test.cpp

运行结果：

➜  ~ git:(master) ✗ ./test   
0
1
➜  ~ git:(master) ✗ ./test
0
1
➜  ~ git:(master) ✗ ./test
1
0
➜  ~ git:(master) ✗ ./test
0
1
➜  ~ git:(master) ✗ ./test
0
1
➜  ~ git:(master) ✗ ./test
1
0
➜  ~ git:(master) ✗ ./test
0
1
➜  ~ git:(master) ✗ ./test
1
0

总体来说，两者速度差不多

反汇编看看：

objdump -dS test

test函数调用：

    int start_t, end_t, i;
    start_t = time(NULL);
  4008bd:       bf 00 00 00 00          mov    $0x0,%edi
  4008c2:       e8 89 fe ff ff          callq  400750 <time@plt>
  4008c7:       89 45 f8                mov    %eax,-0x8(%rbp)
    for( i = 0; i < 200000000; i++)
  4008ca:       c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)
  4008d1:       81 7d fc ff c1 eb 0b    cmpl   $0xbebc1ff,-0x4(%rbp)
  4008d8:       7f 19                   jg     4008f3 <main+0x67> //比较，>=200000000 则跳出循环
    {
        test(src, des);
  4008da:       48 8d 55 d0             lea    -0x30(%rbp),%rdx //可以看出，这里对test的调用是通过寄存器传值的，用了一个call，需要压栈
  4008de:       48 8d 45 e0             lea    -0x20(%rbp),%rax
  4008e2:       48 89 d6                mov    %rdx,%rsi
  4008e5:       48 89 c7                mov    %rax,%rdi
  4008e8:       e8 69 ff ff ff          callq  400856 <_Z4testPKcS0_>
    char src[] = "GCGCBGGAGTCAGAe";
    char des[] = "CAGAG";

    int start_t, end_t, i;
    start_t = time(NULL);
    for( i = 0; i < 200000000; i++)
  4008ed:       83 45 fc 01             addl   $0x1,-0x4(%rbp)
  4008f1:       eb de                   jmp    4008d1 <main+0x45> //进行下一轮循环
    {
        test(src, des);
    }
    end_t = time(NULL);
  4008f3:       bf 00 00 00 00          mov    $0x0,%edi //结束循环
  4008f8:       e8 53 fe ff ff          callq  400750 <time@plt>

而strstr：

start_t = time(NULL);
  40091f:       bf 00 00 00 00          mov    $0x0,%edi
  400924:       e8 27 fe ff ff          callq  400750 <time@plt>
  400929:       89 45 f8                mov    %eax,-0x8(%rbp)
    for( i = 0; i < 200000000; i++)    // 这里根本就没有strstr相关的调用，因为被优化掉了
  40092c:       c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)
  400933:       81 7d fc ff c1 eb 0b    cmpl   $0xbebc1ff,-0x4(%rbp)
  40093a:       7f 06                   jg     400942 <main+0xb6>
  40093c:       83 45 fc 01             addl   $0x1,-0x4(%rbp)
  400940:       eb f1                   jmp    400933 <main+0xa7>
    {
        strstr(src, des);
    }
    end_t = time(NULL);
  400942:       bf 00 00 00 00          mov    $0x0,%edi
  400947:       e8 04 fe ff ff          callq  400750 <time@plt>
  40094c:       89 45 f4                mov    %eax,-0xc(%rbp)

总结：因为你的test函数基本都是寄存器操作，所以耗时也很少。而strstr根本就没被调用，所以两者速度差不多，


2. clang++ 3.7

编译选项：

clang++ -g -o test test.cpp

运行结果：

➜  ~ git:(master) ✗ ./test
0
2
➜  ~ git:(master) ✗ ./test
0
2
➜  ~ git:(master) ✗ ./test
0
2

有了明显差距。

看一看反汇编：

objdump -dS test
    start_t = time(NULL);
  400a18:       48 89 45 c0             mov    %rax,-0x40(%rbp)
  400a1c:       e8 7f fd ff ff          callq  4007a0 <time@plt>
  400a21:       89 c1                   mov    %eax,%ecx
  400a23:       89 4d d4                mov    %ecx,-0x2c(%rbp)
    for( i = 0; i < 200000000; i++)
  400a26:       c7 45 cc 00 00 00 00    movl   $0x0,-0x34(%rbp)
  400a2d:       81 7d cc 00 c2 eb 0b    cmpl   $0xbebc200,-0x34(%rbp)
  400a34:       0f 8d 1f 00 00 00       jge    400a59 <main+0xf9>
  400a3a:       48 8d 75 da             lea    -0x26(%rbp),%rsi
  400a3e:       48 8d 7d e0             lea    -0x20(%rbp),%rdi
    {
        strstr(src, des);
  400a42:       e8 59 00 00 00          callq  400aa0 <_ZSt6strstrPcPKc>
// 不出所料，发生了调用
  400a47:       48 89 45 b8             mov    %rax,-0x48(%rbp)
    }
    end_t = time(NULL);
    cout<<end_t - start_t<<endl;

    start_t = time(NULL);
    for( i = 0; i < 200000000; i++)
  400a4b:       8b 45 cc                mov    -0x34(%rbp),%eax