代码之家  ›  专栏  ›  技术社区  ›  John Ilacqua

C++算法的回路融合优化

  •  2
  • John Ilacqua  · 技术社区  · 7 年前

    vector<int> 要得到第一个元素的值,高于某个阈值,以及高于该阈值的元素总数:

    constexpr auto GetValuesSTL(const std::vector<int>& testdata)
    {
        constexpr auto value_above_threshold = [](const auto value) constexpr { return value > THRESHOLD; };
        constexpr auto optional_from_iterator = [](const auto it, const auto end) constexpr { return it != end ? std::make_optional(*it) : std::nullopt; };
    
        return std::make_tuple(
            std::accumulate(testdata.begin(), testdata.end(), 0L),
            optional_from_iterator(std::find_if(testdata.begin(), testdata.end(), value_above_threshold), testdata.end()),
            std::count_if(testdata.begin(), testdata.end(), value_above_threshold) );
    }
    

    但我可以更有效地把它写成一个原始循环:

    constexpr auto GetValuesRawLoop(const std::vector<int>& testdata)
    {
        auto sum = 0L;
        std::optional<int> first_above_threshold = std::nullopt;
        auto num_above_threshold = 0;
    
        auto it = testdata.begin();
        for (; it != testdata.end(); ++it)
        {
            const auto value = *it;
    
            if (value > THRESHOLD)
            {
                first_above_threshold = value;
                break;
            }
    
            sum += value;
        }
        for (; it != testdata.end(); ++it)
        {
            const auto value = *it;
    
            sum += value;
    
            if (value > THRESHOLD)
            {
                ++num_above_threshold;
            }
        }
    
        return std::make_tuple( sum, first_above_threshold, num_above_threshold );
    }
    

    我希望编译器能够将算法调用融合到一个循环中,因为它有足够的信息知道向量没有被修改,但是在随机生成的int的不同长度向量上分析这两个函数(用 g++-9 -O3 )显示了STL版本的函数持续占用的时间是原始循环的2-2.5倍,这与没有循环融合时所期望的完全一样。

    0 回复  |  直到 7 年前
        1
  •  0
  •   Anton    7 年前

    我只想回答你问题的最后一部分:

    有没有其他方法可以像 原始循环和算法版本一样有表现力?

    根据您认为的“表现力”,使用单个std::accumulate可能如下所示:

    constexpr auto GetValuesACC(const std::vector<int>& testdata)
        auto accumulator = [](std::tuple<int, std::optional<int>, int> init, int val) {
            return std::make_tuple(
                std::get<0>(init) + val, 
                std::get<1>(init).has_value() ? std::get<1>(init) : 
                    (val > THRESHOLD ? std::make_optional(val) : std::nullopt),
                std::get<2>(init) + int(val > THRESHOLD));
    };
    
        return std::accumulate(testdata.begin(), testdata.end(),
            std::make_tuple(0, std::nullopt, 0), accumulator);
    }
    

    • 上面的第一个是迄今为止所见的-或者-nullopt
    • 到目前为止高于阈值计数

    :我没有将此算法的性能与原始版本或原始循环进行基准测试,因为结果会因硬件和编译器的不同而有所不同。但是,这应该相当于一个手写循环。

    编辑 :我在本地做了一些基准测试。。。

    • 硬件:MacOS,1.8GHz Intel Core i5
    • 测试使用3次运行,每次10次迭代,输入5x10^7个元素向量,包含顺序整数(std::iota),阈值=5。
    • 使用“time”命令的“user”输出记录的数据,所有值均以秒为单位,并按升序排序。

      GetValuesRawLoop:3.7、4.0、4.2 GetValuesACC:78s(只运行了一次)

    目前总结:

    • GetValuesRawLoop 和 GetValuesSTL 在我的环境中 .
    • GetValuesACC

    跟随@John Ilacqua关于 std::optional int 以及使用 THRESHOLD 因为保护值意味着“没有超过阈值的值”。

    示例 无可选:

    auto GetValuesACC2(const std::vector<int>& testdata)
    {
        auto accumulator = [](const std::tuple<int, int, int>& init, int val) {
            return std::make_tuple(
                std::get<0>(init) + val, 
                std::get<1>(init) > THRESHOLD ? std::get<1>(init) : 
                    (val > THRESHOLD ? val : THRESHOLD),
                std::get<2>(init) + int(val > THRESHOLD));
        };
    
        return std::accumulate(testdata.begin(), testdata.end(),
            std::make_tuple(0, THRESHOLD, 0), accumulator);
    }
    

    新结果:

    GetValuesRawLoop2: 0.3, 0.3, 0.6
    GetValuesSTL2:     4.4, 4.4, 4.5
    GetValuesACC2:     1.7, 1.8, 1.9
    

    新摘要:

    • 在我的LLVM版本中,optional的实现在这种情况下很慢
      • 但并不真正影响GetValuesSTL
    • 单个累加器比3个循环快,但比原始循环慢

    一如既往,“您的里程数可能会有所不同!”这些结果强调了为什么在尝试优化之前,在实际使用中进行分析是很重要的。