Fastest way to permute elements of an array

I want to create a function template to permute the elements of an array (of ints or uint8_ts, or maybe something else), where the template parameter determines the permutation that is applied to the array. My main concern here is performance, so the function needs to be as fast as possible. Below is my attempt so far, with some code for performance testing.

#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];
}

Explanation:

1. permute1 takes a Vector of Vectors corresponding to the disjoint cycles of a permutation, and permutes arr accordingly.
2. permute2 does the same thing, but with the Vector of Vectors contained inside another Vector. The reason I want to do this is because in my real code, my Foo struct contains multiple arrays that need permuting, and I want to permute them all in different ways.
3. permute3 is just a hard-coded specific example of what permute1 and permute2 do. Ideally, I want permute1 and permute2 to compile to the same assembly code that permute3 compiles to.

Results:

I am compiling with CXX main.cpp -std=c++20 -O3 where CXX is either g++ or clang++. I am using gcc 10.1 and clang trunk. Below are the results for various runs of the program:

Results with the code as written above:

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

Results with the 1, 5 cycle removed:

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

Results with the 1, 5 cycle removed, and with Foo::arr being an array of ints instead of an array of uint8_ts:

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

Results with the three functions having __attribute__ ((always_inline))

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

Results with the code as written above, compiled with profile-guided optimisation

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

Questions:

1. Why are there such huge differences in speed between some of these functions? I would have expected them to all be about the same. In particular, I don't see why permute1 and permute2 are ever different at all.

2. How can I modify permute2 to make it as fast as permute3 (ideally compiling down to the same assembly code)?