c++ - 为什么我的模板元代码比 for 循环慢？

Question

我正在尝试对一组 std::array 中位置 n 中的所有元素求和。总和的值存储在传递给我的函数 add_rows 的 std::array 中。求和是通过递归“调用”模板化类方法来对列的索引递减的列求和，直到我命中第 0 列，对下一行进行相同的计算，直到我命中第 0 行。

我还有一个执行相同操作的循环版本，我比较了执行两种计算总和的方式所花费的时间。我期待看到模板化版本表现更好，但它的输出说慢了 25 倍。模板化版本有什么问题导致速度变慢吗？

在开始之前，我受到了 this article 的启发。 “使用元程序展开循环”

程序的输出是:

Templated version took: 23 ns.
Loop version took:      0 ns.

代码:

#include <iostream>
#include <array>
#include <numeric>
#include <chrono>

template<size_t num_rows, size_t row_index, size_t num_columns, size_t column_index>
class sumRow;

template<size_t num_rows, size_t row_index, size_t num_columns>
class sumRow<num_rows, row_index, num_columns, 0>
{
 public:
  static inline int result(const std::array<std::array<int, num_rows>, num_columns>& arrays) noexcept
  {
    return arrays[0][row_index];
  }
};

template<size_t num_rows, size_t row_index, size_t num_columns, size_t column_index>
class sumRow
{
 public:
  static inline int result(const std::array<std::array<int, num_rows>, num_columns>& arrays) noexcept
  {
    return arrays[column_index][row_index] + sumRow<num_rows, row_index, num_columns, column_index - 1>::result(arrays);
  }
};

// Array of arrays

template<size_t num_rows, size_t row_index, size_t num_columns>
class sumRows;

template<size_t num_rows, size_t num_columns>
class sumRows<num_rows, 0, num_columns>
{
 public:
  static inline void result(const std::array<std::array<int, num_rows>, num_columns>& arrays, std::array<int, num_rows>& result) noexcept
  {
    result[0] = sumRow<num_rows, 0, num_columns, num_columns - 1>::result(arrays);
  }
};

template<size_t num_rows, size_t row_index, size_t num_columns>
class sumRows
{
 public:
  static inline void result(const std::array<std::array<int, num_rows>, num_columns>& arrays, std::array<int, num_rows>& result) noexcept
  {
    result[row_index - 1] = sumRow<num_rows, row_index - 1, num_columns, num_columns - 1>::result(arrays);
    sumRows<num_rows, row_index - 1, num_columns>::result(arrays, result);
  }
};

template<size_t num_rows, size_t num_columns>
inline void sum_rows(const std::array<std::array<int, num_rows>, num_columns>& arrays, std::array<int, num_rows>& result)
{
  sumRows<num_rows, num_rows, num_columns>::result(arrays, result);
};

template<size_t num_channels, size_t channel_size>
inline void loop_sum(const std::array<std::array<int, channel_size>, num_channels>& channels, std::array<int, channel_size>& results) noexcept
{
  for (size_t sample_index = 0; sample_index < channel_size; ++sample_index)
  {
    int result = 0;
    for (size_t channel_index = 0; channel_index < num_channels; ++channel_index)
    {
      result += channels[channel_index][sample_index];
    }
    results[sample_index] = result;
  }
};

// Inspired by from https://stackoverflow.com/a/21995693/2996272
struct measure_cpu_clock
{
  template<typename F, typename ...Args>
  static clock_t execution(F&& func, Args&&... args)
  {
    auto start = std::clock();
    std::forward<decltype(func)>(func)(std::forward<Args>(args)...);
    return std::clock() - start;
  }
};

const int num_channels = 850;

const int num_samples = 32;
using channel = std::array<int, num_samples>;

int main()
{
  std::array<channel, num_channels> channels{};
  for (auto&& item : channels)
  {
    std::iota(item.begin(), item.end(), 1);
  }
  // Templated version
  channel results = {};

  auto execution_time = measure_cpu_clock::execution(sum_rows<num_samples, num_channels>, channels, results);
  std::cout << "Templated version took: " << execution_time << " ns." << std::endl;

  // Loop version
  channel results2 = {};

  execution_time = measure_cpu_clock::execution(loop_sum<num_channels, num_samples>, channels, results2);
  std::cout << "Loop version took:      " << execution_time << " ns." << std::endl;

}

Answer 1

阅读上面的评论后，我添加了一个循环，该循环执行 10000 次求和，并在每次迭代后打印输出。

然后，在每次迭代之前，要求和的数组也用随机值初始化，现在时间测量表明这两种方法的速度几乎相等(两者都约为 15 个时钟)。

#include <iostream>
#include <array>
#include <numeric>
#include <chrono>
#include <functional>
#include <random>

template<size_t num_rows, size_t row_index, size_t num_columns, size_t column_index>
class sumRow;

template<size_t num_rows, size_t row_index, size_t num_columns>
class sumRow<num_rows, row_index, num_columns, 0>
{
 public:
  static inline int result(const std::array<std::array<int, num_rows>, num_columns>& arrays) noexcept
  {
    return arrays[0][row_index];
  }
};

template<size_t num_rows, size_t row_index, size_t num_columns, size_t column_index>
class sumRow
{
 public:
  static inline int result(const std::array<std::array<int, num_rows>, num_columns>& arrays) noexcept
  {
    return arrays[column_index][row_index] + sumRow<num_rows, row_index, num_columns, column_index - 1>::result(arrays);
  }
};

// Array of arrays

template<size_t num_rows, size_t row_index, size_t num_columns>
class sumRows;

template<size_t num_rows, size_t num_columns>
class sumRows<num_rows, 0, num_columns>
{
 public:
  static inline void result(const std::array<std::array<int, num_rows>, num_columns>& arrays, std::array<int, num_rows>& result) noexcept
  {
    result[0] = sumRow<num_rows, 0, num_columns, num_columns - 1>::result(arrays);
  }
};

template<size_t num_rows, size_t row_index, size_t num_columns>
class sumRows
{
 public:
  static inline void result(const std::array<std::array<int, num_rows>, num_columns>& arrays, std::array<int, num_rows>& result) noexcept
  {
    result[row_index - 1] = sumRow<num_rows, row_index - 1, num_columns, num_columns - 1>::result(arrays);
    sumRows<num_rows, row_index - 1, num_columns>::result(arrays, result);
  }
};

template<size_t num_rows, size_t num_columns>
inline void sum_rows(const std::array<std::array<int, num_rows>, num_columns>& arrays, std::array<int, num_rows>& result)
{
  sumRows<num_rows, num_rows, num_columns>::result(arrays, result);
};

template<size_t channel_size, size_t num_channels>
inline void loop_sum(const std::array<std::array<int, channel_size>, num_channels>& channels, std::array<int, channel_size>& results) noexcept
{
  for (size_t sample_index = 0; sample_index < channel_size; ++sample_index)
  {
    int result = 0;
    for (size_t channel_index = 0; channel_index < num_channels; ++channel_index)
    {
      result += channels[channel_index][sample_index];
    }
    results[sample_index] = result;
  }
};

// Inspired by from https://stackoverflow.com/a/21995693/2996272
struct measure_cpu_clock
{
  template<typename F, typename ...Args>
  static clock_t execution(F&& func, Args&&... args)
  {
    auto start = std::clock();
    std::forward<decltype(func)>(func)(std::forward<Args>(args)...);
    return std::clock() - start;
  }
};

template<typename T>
T get_random_int(T min, T max)
{
  std::random_device rd;
  std::mt19937 gen(rd());
  std::uniform_int_distribution <T> dis(min, max);
  return dis(gen);
}

template<size_t num_values>
void print_values(std::array<int, num_values>& array)
{
  for (auto&& item : array)
  {
    std::cout << item << "<";
  }
  std::cout << std::endl;
}

const int num_columns = 850;
const int num_rows = 32;
using channel = std::array<int, num_rows>;

using func = std::function<void(const std::array<std::array<int, num_rows>, num_columns>&, std::array<int, num_rows>&)>;

clock_t perform_many(const func& f)
{
  clock_t total_execution_time = 0;
  int num_iterations = 10000;
  for (int i = 0; i < num_iterations; ++i)
  {
    std::array<channel, num_columns> channels{};
    for (auto&& item : channels)
    {
      std::iota(item.begin(), item.end(), get_random_int(0, 3));
    }
    channel results = {};

    auto start = std::clock();
    f(channels, results);
    total_execution_time += (std::clock() - start);

    print_values(results);
  }
  return total_execution_time / num_iterations;
}

int main()
{
  // Templated version
  auto template_execution_time = perform_many(sum_rows<num_rows, num_columns>);

  auto loop_execution_time = perform_many(loop_sum<num_rows, num_columns>);

  std::cout << "Templated version took: " << template_execution_time << " clocks" << std::endl;
  std::cout << "Loop version took:      " << loop_execution_time << " clock" << std::endl;

}