Цель этих постов

Эти сообщения созданы с целью узнать больше о современном C ++ и изучить некоторые общепринятые мнения, которые я всегда принимал как должное. Я собираюсь начать с создания библиотеки матриц и посмотреть, к чему это приведет. Этот первый пост будет посвящен оспариванию некоторых из этих общепринятых представлений и рассмотрению основного варианта реализации. В следующем посте я расскажу об использовании современного C ++ и добавлении концепций в библиотеку.

Обзор идеи

Одна вещь, которую необходимо сделать библиотеке матриц, - это представлять матрицы разных размеров. В этом случае идеально, если объект матрицы поддерживается контейнером с динамическим размером. В идеале этот контейнер имеет быстрое время доступа, а это означает, что такой контейнер, как связанный список, не идеален для этого сценария. Из общих структур данных этим критериям соответствуют массивы и хэш-таблицы, у обеих которых время доступа O (1). Поскольку можно сопоставить каждый элемент в матрице с уникальным индексом (его местоположением), структура данных типа массива имеет смысл для нижележащего контейнера.

Обычный совет в программировании - использовать стандартную библиотеку. Однако стандартная библиотека C ++ часто подвергалась тщательной проверке из-за того, что она слишком общая, и из-за этой универсальности часто может быть побеждена решениями, созданными вручную. Давайте посмотрим, есть ли разница между использованием указателя на массив в куче и векторным типом стандартной библиотеки для реализации базовой матрицы.

Код

Код для двух матриц можно увидеть здесь и ниже.

#ifndef __MATRIX2D_HPP__
#define __MATRIX2D_HPP__
#include <vector>
template <typename T>
class MatrixVec2D
{
 std::vector<T> mat;
 std::size_t rows;
 std::size_t cols;
 std::size_t rcToIdx(std::size_t r, std::size_t c) const
 {
 	return cols * r + c;
 }
public:
 MatrixVec2D<T>(std::size_t r, std::size_t c) : 
	mat(r*c, 0),
	rows(r),
	cols(c)
 {
 }
  MatrixVec2D<T>(const MatrixVec2D<T> & m): 
	mat(m.mat), 
	rows(m.rows), 
	cols(m.cols)
 {
 }
 std::size_t getNumRows() const
 {
 	return rows;
 }
 std::size_t getNumCols() const
 {
 	return cols;
 }
 const T& at(std::size_t row, std::size_t col) const
 {
 	return mat[rcToIdx(row, col)];
 }
 T& at(std::size_t row, std::size_t col)
 {
 	return mat[rcToIdx(row, col)];
 }
};
template <typename T>
class MatrixArr2D
{
 T * mat;
 std::size_t rows;
 std::size_t cols;
 std::size_t rcToIdx(std::size_t r, std::size_t c) const
 {
 	return cols * r + c;
 }
public:
 MatrixArr2D<T>(std::size_t r, std::size_t c): 
	mat(new T[r*c]), 
	rows(r), 
	cols(c)
 {
 	for(auto i = 0; i < r*c; ++i)
 	{
 		mat[i] = 0;
 	}
 }
 
MatrixArr2D<T>(const MatrixArr2D<T> & m): 
	mat(new T[m.rows * m.cols]), 
	rows(m.rows), 
	cols(m.cols)
 {
 	for(auto i = 0; i < rows*cols; ++i)
 	{
 		mat[i] = m.mat[i];
 	}
 }
 
~MatrixArr2D()
 {
 	delete [] mat;
 }
 
 std::size_t getNumRows() const
 {
 	return rows;
 }
 std::size_t getNumCols() const
 {
 	return cols;
 }
 const T& at(std::size_t row, std::size_t col) const
 {
 	return mat[rcToIdx(row, col)];
 }
 T& at(std::size_t row, std::size_t col)
 {
 	return mat[rcToIdx(row, col)];
 }
};
#endif

Основное различие между двумя реализациями - это базовый контейнер. MatrixVec2D использует вектор из стандартной библиотеки для хранения данных, тогда как MatrixArr2D использует динамически распределенный массив. Поскольку векторы обычно реализуются с помощью динамически выделяемого массива, реализация вектора должна действовать как другой уровень косвенного обращения при выполнении доступа к элементу. За счет исключения этого уровня косвенного обращения и использования динамически выделяемого массива ожидается, что MatrixArr2D будет быстрее, чем MatrixVec2D для доступа.

Платформа тестирования

При тестировании двух реализаций тест не должен зависеть от базовой реализации. Это можно реализовать двумя способами: с помощью абстрактного базового класса, от которого оба являются производными, или с помощью шаблонной функции. Чтобы не беспокоиться о затратах на вызов виртуального метода, был выбран подход с использованием шаблонных функций.

Для тестирования была написана функция умножения, которую можно увидеть ниже. Это использует O (n³) доступов для квадратных матриц, где n - длина столбца. Используемый тест заполняет две матрицы случайными числами с помощью функции rand (), а затем умножает их.

template <template <class S> class T, typename S>
T<S> mult(const T<S>& A, const T<S>& B)
{
  assert(A.getNumCols() == B.getNumRows());
  T<S> result(A.getNumRows(), B.getNumCols());
  for(std::size_t r = 0; r < result.getNumRows(); ++r)
  {
    for(std::size_t c = 0; c < result.getNumCols(); ++c)
    {
      S sum = 0;
      for(std::size_t m = 0; m < A.getNumCols(); ++m)
      {
        sum += A.at(r,m) * B.at(m,c);
      }
      result.at(r,c) = sum;
    }
  }
  return result;
}

Полученные результаты

Результаты представлены на графиках в конце, и их можно увидеть в таблице ниже.

Эти результаты были тем, что было предсказано, когда никакие оптимизации не применялись, однако на более высоких уровнях оптимизации разница между ними стала незначительной, а в точках, отличных от конечной, реализация вектора была быстрее, чем реализация массива. Это указывает на то, что на более высоких уровнях оптимизации (-O1 для GCC и -O2 для Clang) компилятор может каким-то образом либо оптимизировать дополнительный уровень косвенности, вызываемый вектором.

Еще одна интересная вещь, которую следует отметить, это то, что для всего теста уровень оптимизации clang -Ofast работал хуже, чем уровень оптимизации -O3. Это подкрепляет идею профилирования и не всегда веры в то, что больше оптимизаций сделают код быстрее.

Заключение

Поскольку на более высоких уровнях оптимизации не было значимой разницы между матрицей с массивом и векторной матрицей, использование необработанного массива для этой реализации малоэффективно. Вектор, предоставляемый стандартной библиотекой, менее подвержен ошибкам, связанным с памятью, таким как утечки, чем необработанный указатель. Кроме того, векторный класс предоставляет доступ ко многим стандартным библиотечным алгоритмам, которые могут быть полезны при расширении матричного класса.

Если вы видите, что что-то, с чем вы не согласны или считаете, что можно улучшить, не стесняйтесь отправить мне сообщение!

Приложение: Тестирование оборудования

Эти тесты были выполнены на поверхностной книге Microsoft с использованием подсистемы linux-windows. GCC версии 6.2 для ubuntu 14.04. Clang версии 3.8.0. Intel i5–6300U @ 2,40 ГГц 2,50 ГГц, 8 ГБ ОЗУ

Приложение: графики результатов

Хакерский полдень - это то, с чего хакеры начинают свои дни. Мы часть семьи @AMI. Сейчас мы принимаем заявки и рады обсуждать рекламные и спонсорские возможности.

Если вам понравился этот рассказ, мы рекомендуем прочитать наши Последние технические истории и Современные технические истории. До следующего раза не воспринимайте реалии мира как должное!