V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
csfreshman
V2EX  ›  C++

c++ string 函数优化后,执行反而耗时很高,求解惑

  •  
  •   csfreshman · 2023-10-28 16:20:43 +08:00 · 2246 次点击
    这是一个创建于 390 天前的主题,其中的信息可能已经有所发展或是发生改变。
    #include <iostream>
    
    //优化前函数 remove_ctrl
    std::string remove_ctrl(std::string s) {
        std::string result;
        for(int i = 0;i < s.length();i++) {
            if(s[i] >= 0x20)
                result = result + s[i];
        }
        return result;
    }
    
    //优化后函数 remove_ctrl_opt
    std::string remove_ctrl_opt(const std::string& src,std::string& dst) {
        int n = src.size();
        dst.reserve(n);
        for(auto it = src.begin();it != src.end();it++) {
            if(*it >= 0x20)
                dst +=  *it;
        }
        return dst;
    }
    
    int main(){
        std::string src = "hello,world,hello,world,hello,world,hello,world,hello,world,hello,world,hello,world,hello,world";
        std::string result;
        for(int i = 0;i < 1000000;i++)
            std::string result = remove_ctrl(src);
    
        for(int i = 0;i < 1000000;i++)
            remove_ctrl_opt(src,result);
        
        return 0;
    }
    

    优化函数,从参数拷贝,string 提前 reserve,减少临时变量,结果分别循环 1000000 次,使用 time ./a.out 测试执行时间,优化后的耗时反而很高(优化前 6s 左右,优化后 60s 没执行完直接 control+c 了)。

    排查原因,发现将函数 remove_ctrl_opt 的返回类型修改为 void,函数体 return;优化后耗时提升 6 倍左右。 这到底是什么原因? return string ,难道开销这么大?但是优化前函数也是这样,执行才 6s 。

    15 条回复    2023-10-29 12:32:08 +08:00
    liberize
        1
    liberize  
       2023-10-28 16:35:07 +08:00
    remove_ctrl 返回一个 local string ,编译器做 RVO (Return value optimization) ,避免拷贝

    remove_ctrl_opt 返回值无法优化,肯定会拷贝
    agagega
        2
    agagega  
       2023-10-28 16:38:50 +08:00 via iPhone
    remove_ctrl_opt 都把 dst 作为引用传进来了,为什么还要 return ?这个 return 必然导致 copy
    exiledkingcc
        3
    exiledkingcc  
       2023-10-28 16:46:01 +08:00
    remove_ctrl_opt 都是错的没发现吗? dst 要先 clear 。
    即便改对了也是不行,因为 remove_ctrl 有 RVO 优化,楼上已经提到了。
    另外,为什么不用 std::copy_if 或者 std::move_if ?
    lovelylain
        4
    lovelylain  
       2023-10-28 16:56:50 +08:00 via Android
    因为你这优化出 bug 了,原来的版本编译器本身会做返回值优化,所以返回 string 没有性能问题,你优化为传入引用后,每次调用复用同一个对象且没有 clear ,string 越来越长占用内存越来越多,不慢才怪了。
    Inn0Vat10n
        5
    Inn0Vat10n  
       2023-10-28 16:57:04 +08:00
    这俩函数逻辑都不等价,你是想比较什么?
    cnbatch
        6
    cnbatch  
       2023-10-28 17:41:59 +08:00
    第二个优化是错的,楼上各位已经给出错误原因。
    如果真想优化,可以这么写:
    std::string& remove_ctrl_opt(const std::string& src,std::string& dst)
    没错,也就是返回值是个引用。
    然后记得 dst.clear() 再 dst.reserve(n)。

    不过看着还是很累赘,不如这样写:

    std::string remove_ctrl_a(const std::string& s)
    {
    std::string result;
    std::copy_if(s.begin(), s.end(), std::back_inserter(result), [](auto ch){ return ch >= 0x20; } );
    return result;
    }

    或者:

    std::string& remove_ctrl_b(const std::string& s, std::string& dst)
    {
    dst.clear();
    dst.reserve(s.size());
    std::copy_if(s.begin(), s.end(), std::back_inserter(dst), [](auto ch){ return ch >= 0x20; } );
    return dst;
    }

    经 O3 选项优化后,remove_ctrl_b 是最快的,比起手动使用迭代器更快。

    至于 remove_ctrl_a 和修改正确后的 remove_ctrl_opt 谁更快,那得视乎优化选项,以及编译器版本。在三大编译器( MSVC, GCC Clang) 不同优化选项都测了下,这两个互有胜负。
    xiangyuecn
        7
    xiangyuecn  
       2023-10-28 19:30:37 +08:00
    100 万次,为啥 js 只需 1 秒😂


    remove_ctrl=(s)=>{
    var result="";
    for(var i = 0;i < s.length;i++) {
    if(s.charCodeAt(i) >= 0x20)
    result = result + s.charAt(i);
    }
    return result;
    }

    main=()=>{
    var src = "hello,world,hello,world,hello,world,hello,world,hello,world,hello,world,hello,world,hello,world";
    var result;
    for(var i = 0;i < 1000000;i++)
    result = remove_ctrl(src);

    return result;
    }

    console.time(1)
    console.log(main())
    console.timeEnd(1)
    cnbatch
        8
    cnbatch  
       2023-10-28 20:38:51 +08:00
    @xiangyuecn 机器型号大家都没说,差异可以很大的
    再说了,JS 解释器也有 RVO 吧

    我自己尝试了好几台机器、不同的系统,原始版本的写法从用时 16 秒到用时 1.7 秒都有,优化后的版本从 124 毫秒到 1.4 秒都有,脱离具体机器谈速度就很不可靠了
    20230710
        9
    20230710  
       2023-10-29 01:33:28 +08:00
    @cnbatch 不是很懂 c++, debug 模式下测试的, remove_ctrl_b 慢出的这些速度是不是 predicate 函数调用产生的. O3 选项能优化掉吗

    // 901 milliseconds
    std::string remove_ctrl(const std::string &s) {
    std::string result;
    for (int i = 0; i < s.length(); i++) {
    if (s[i] >= 0x20)
    result.push_back(s[i]);
    }
    return result;
    }

    // 1648 milliseconds
    std::string remove_ctrl_b(const std::string &s) {
    std::string dst;
    dst.clear();
    dst.reserve(s.size());
    std::copy_if(s.begin(), s.end(), std::back_inserter(dst), [](auto ch) { return ch >= 0x20; });
    return dst;
    }
    crystalyouth
        10
    crystalyouth  
       2023-10-29 08:22:24 +08:00 via Android
    已经有人提出修复意见了,修改后推荐用 google benchmark 去测一下
    csfreshman
        11
    csfreshman  
    OP
       2023-10-29 10:38:03 +08:00
    @lovelylain 学习了,感谢
    csfreshman
        12
    csfreshman  
    OP
       2023-10-29 10:40:07 +08:00
    @cnbatch 学习了,主要 3 个方面 1.函数 remove_ctrl 返回临时变量,编译器有优化 2.remove_ctrl_opt 循环执行时没 clear ,每次越来越大 3.传入 dst ,就不需要 return dst 了。
    csfreshman
        13
    csfreshman  
    OP
       2023-10-29 10:41:03 +08:00
    @cnbatch 机器型号大家都不一样,只是用相同机型,执行两次对比即可,看了大家的回复,学习到了,感谢。
    csfreshman
        14
    csfreshman  
    OP
       2023-10-29 10:47:09 +08:00
    @crystalyouth @20230710 @cnbatch @xiangyuecn @Inn0Vat10n @lovelylain @exiledkingcc @agagega @liberize benchmark 测试,符合预期,感谢各位大佬们指出。改进点:
    1.传参 dst ,无需 return dst,未优化的函数返回之所以不耗时,因为有编译器优化&&局部变量不会一直追加
    2.优化函数里传引用参,函数体内未 clear,依赖外部传入变量
    3.copy 逻辑,可以使用 std::copy_if
    cnbatch
        15
    cnbatch  
       2023-10-29 12:32:08 +08:00
    @20230710 不但是 Lambda 函数调用产生的,还有迭代器的函数调用,也就是 begin()和 end()。O3 的优化会把迭代器的调用优化掉。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5595 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 02:41 · PVG 10:41 · LAX 18:41 · JFK 21:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.