Loop fusion w C++ (jak pomóc kompilatorowi?)

Question

Próbuję zrozumieć, w jakich okolicznościach kompilator C++ jest w stanie przeprowadzić fuzję w pętli, a gdy nie.

Następujący kod mierzy wydajność dwóch różnych sposobów obliczania kwadratów podwójnych (f(x) = (2*x)^2) wszystkich wartości w wektorze.

#include <chrono> 
#include <iostream> 
#include <numeric> 
#include <vector> 

constexpr int square(int x) 
{ 
    return x * x; 
} 

constexpr int times_two(int x) 
{ 
    return 2 * x; 
} 

// map ((^2) . (^2)) $ [1,2,3] 
int manual_fusion(const std::vector<int>& xs) 
{ 
    std::vector<int> zs; 
    zs.reserve(xs.size()); 
    for (int x : xs) 
    { 
     zs.push_back(square(times_two(x))); 
    } 
    return zs[0]; 
} 

// map (^2) . map (^2) $ [1,2,3] 
int two_loops(const std::vector<int>& xs) 
{ 
    std::vector<int> ys; 
    ys.reserve(xs.size()); 
    for (int x : xs) 
    { 
     ys.push_back(times_two(x)); 
    } 

    std::vector<int> zs; 
    zs.reserve(ys.size()); 
    for (int y : ys) 
    { 
     zs.push_back(square(y)); 
    } 
    return zs[0]; 
} 

template <typename F> 
void test(F f) 
{ 
    const std::vector<int> xs(100000000, 42); 

    const auto start_time = std::chrono::high_resolution_clock::now(); 
    const auto result = f(xs); 
    const auto end_time = std::chrono::high_resolution_clock::now(); 

    const auto elapsed = end_time - start_time; 
    const auto elapsed_us = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count(); 
    std::cout << elapsed_us/1000 << " ms - " << result << std::endl; 
} 

int main() 
{ 
    test(manual_fusion); 
    test(two_loops); 
} 

Wersja z dwóch pętli takes about twice as much time w wersji z jednej pętli, nawet -O3 GCC i Clang.

Czy istnieje sposób na umożliwienie kompilatorowi zoptymalizowania two_loops tak szybko, jak manual_fusion bez pracy w miejscu w drugiej pętli? Powodem, dla którego pytam, jest to, że chcę wykonać połączenia łańcuchowe do mojej biblioteki, takie jak FunctionalPlus, takie jak fplus::enumerate(fplus::transform(f, xs)); szybciej.

Answer 1

Można spróbować zmodyfikować funkcję two_loops następująco:

int two_loops(const std::vector<int>& xs) 
{ 
    std::vector<int> zs; 
    zs.reserve(xs.size()); 
    for (int x : xs) 
    { 
     zs.push_back(times_two(x)); 
    } 

    for (int i=0 : i<zs.size(); i++) 
    { 
     zs[i] = (square(zs[i])); 
    } 
    return zs[0]; 
} 

Chodzi o to, aby uniknąć przydzielania pamięci dwukrotnie i push_back do innego wektora