排列数组元素的最快方法

Question

我想要创建一个函数模板来改变数组的元素(int或uint8_t的元素，或者其他的元素)，其中模板参数决定了应用于数组的置换。这里我主要关心的是性能，因此函数需要尽可能快。下面是我到目前为止的尝试，还有一些用于性能测试的代码。

#include <array>
#include <chrono>
#include <iostream>
#include <stdexcept>

template<typename T, std::size_t MaxSize = 12>
struct Vector{
    std::array<T, MaxSize> m_data{};
    std::size_t m_size{0};

    constexpr Vector() = default;
    constexpr Vector(std::initializer_list<T> list){
        for(auto t : list){
            push_back(t);
        }
    }
    constexpr void pop_back(){
        m_size--;
    }
    constexpr void push_back(T t){
        m_data[m_size] = t;
        m_size++;
    }
    constexpr std::size_t size() const{
        return m_size;
    }
    constexpr T& operator[](int n){
        if(n < 0 || n >= m_size){
            throw std::out_of_range("Vector index is out of bounds");
        }
        return m_data[n];
    }
    constexpr const T& operator[](int n) const{
        if(n < 0 || n >= m_size){
            throw std::out_of_range("Vector index is out of bounds");
        }
        return m_data[n];
    }
};

struct Foo{
    std::array<uint8_t, 8> arr {5,2,4,7,1,3,0,6};

    template<Vector<Vector<int>> cycles>
    void permute1(){
        for(int j=0; j<cycles.size(); j++){
            const Vector<int> &cycle = cycles[j];
            const int size = cycle.size();

            int temp = arr[cycle[0]];
            for(int k=0; k<size-1; k++){
                arr[cycle[k]] = arr[cycle[k+1]];
            }
            arr[cycle[size-1]] = temp;
        }
    }

    template<Vector<Vector<Vector<int>>> cycles>
    void permute2(){
        for(int i=0; i<cycles.size(); i++){
            for(int j=0; j<cycles[i].size(); j++){
                const Vector<int> &cycle = cycles[i][j];
                const int size = cycle.size();

                int temp = arr[cycle[0]];
                for(int k=0; k<size-1; k++){
                    arr[cycle[k]] = arr[cycle[k+1]];
                }
                arr[cycle[size-1]] = temp;
            }
        }
    }

    void permute3(){
        int x = arr[2];
        arr[2] = arr[7];
        arr[7] = arr[6];
        arr[6] = arr[3];
        arr[3] = x;
        x = arr[1];
        arr[1] = arr[5];
        arr[5] = x;
    }
};

int main(){
    constexpr Vector<Vector<int>> v1{{2,7,6,3},{1,5}};
    constexpr Vector<Vector<Vector<int>>> v2{{{2,7,6,3},{1,5}}};

    Foo f;

    auto t1 = std::chrono::high_resolution_clock::now();
    for(int i=0; i<1000000000; i++){
        f.permute1<v1>();
    }
    auto t2 = std::chrono::high_resolution_clock::now();
    for(int i=0; i<1000000000; i++){
        f.permute2<v2>();
    }
    auto t3 = std::chrono::high_resolution_clock::now();
    for(int i=0; i<1000000000; i++){
        f.permute3();
    }
    auto t4 = std::chrono::high_resolution_clock::now();

    auto d1 = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count();
    auto d2 = std::chrono::duration_cast<std::chrono::microseconds>(t3-t2).count();
    auto d3 = std::chrono::duration_cast<std::chrono::microseconds>(t4-t3).count();

    std::cout << "permute1: " << d1 << " us\n";
    std::cout << "permute2: " << d2 << " us\n";
    std::cout << "permute3: " << d3 << " us\n";

    //use f in some way so the compiler doesn't completely optimise everything away
    return f.arr[2];
}

解释：

1. permute1获取对应于置换的不相交循环的Vector的Vector，并相应地对arr进行置换。
2. permute2也做了同样的事情，但是将Vector of Vector包含在另一个Vector中。我之所以要这样做，是因为在我的实际代码中，我的Foo结构包含需要置换的多个数组，并且我希望以不同的方式对它们进行置换。
3. permute3只是permute1和permute2所做工作的一个硬编码的具体例子。理想情况下，我希望permute1和permute2编译成与permute3编译相同的程序集代码。

结果：

我正在用CXX main.cpp -std=c++20 -O3编译，其中CXX要么是g++，要么是clang++。我使用gcc 10.1和clang后备箱。以下是该项目各种运行的结果：

使用上面所写的代码的结果：

function |    g++     |  clang++  
----------------------------------
permute1 | 6562221 μs |   44437 μs
permute2 | 6778576 μs | 4760381 μs
permute3 |  601333 μs |   39218 μs

删除1, 5循环后的结果：

function |    g++     |  clang++  
----------------------------------
permute1 |  616979 μs |   28000 μs
permute2 | 1512795 μs | 2433898 μs
permute3 |  601762 μs |   23977 μs

结果删除了1, 5循环，并且Foo::arr是int的数组，而不是uint8_t的数组：

function |    g++     |  clang++  
----------------------------------
permute1 |  607681 μs |   32471 μs
permute2 |  997331 μs | 2431138 μs
permute3 |  624083 μs |   24020 μs

具有__attribute__ ((always_inline))的三种功能的结果

function |    g++     |  clang++  
----------------------------------
permute1 | 6545779 μs |   43103 μs
permute2 | 6799692 μs |  919098 μs
permute3 |  603414 μs |   24288 μs

上面所写的代码的结果，用配置文件引导的优化编译。

function |    g++     |  clang++  
----------------------------------
permute1 | 5478490 μs |   43818 μs
permute2 | 7274339 μs | 5398051 μs
permute3 |  731976 μs |   44324 μs

问题：

1. 为什么这些功能在速度上有如此巨大的差异？我原以为他们都是一样的。特别是，我不明白为什么permute1和permute2永远是不同的。
2. 我如何修改permute2，使其与permute3一样快(理想情况下编译到相同的汇编代码)？

Answer 1

您的循环是运行时的，因此您可以松掉constexpr，使用等效于constexpr循环的方法似乎甚至允许进行更好的优化，即使是手工编写的优化：

template<Vector<Vector<int>> cycles>
void permute4(){
    auto loop2 = [&]<std::size_t ...Js>(std::index_sequence<Js...>, auto I)
    {
        constexpr Vector<int> cycle = cycles[I];

        int temp = arr[cycle[0]];
        ((arr[cycle[Js]] = arr[cycle[Js+1]]), ...);
        arr[cycle[sizeof...(Js)]] = temp;
    };

    [&]<std::size_t ...Is>(std::index_sequence<Is...>)
    {
        (loop2(std::make_index_sequence<cycles[Is].size() - 1>(),
               std::integral_constant<std::size_t, Is>{}),
        ...);
    }(std::make_index_sequence<cycles.size()>());
}

演示 (以确保行为相同)

基准测试