Почему умножение матрицы 8x8 медленнее чем 10x10?

Question

[Dyikot]

Именно в одном потоке всегда 10x10 быстрее 8x8.

main

#include <iostream>
#include <format>
#include <chrono>
#include <vector>
#include <functional>

#include "Random.h"
#include "MatrixOperations.h"

int main()
{   
	setlocale(LC_ALL, "ru");

	auto& random = Random::Current();

	auto GenerateSquareMatrix = [&random](int size)
	{
		std::vector<int> matrix(size * size);

		for(auto& element : matrix)
		{
			element = random.GenerateNumber(1, 9);
		}

		return matrix;
	};

	auto MeasureTaskTime = [](std::function<void()> action)
	{
		auto startTime = std::chrono::high_resolution_clock::now();
		action();
		auto endTime = std::chrono::high_resolution_clock::now();

		return endTime - startTime;
	};

	auto PrintMultiplyMatrixTime = [](int matrixSize, int threadsAmount, auto time)
	{
		std::cout << std::format(
			"Время умножения матрицы {} x {} при числе потоков {} = {}\n",
			matrixSize,
			matrixSize,
			threadsAmount,
			time
		);
	};

	const int OneThread = 1;
	const int FourThreads = 4;
	const int MatrixSize8x8 = 8;
	const int MatrixSize10x10 = 10;

	// Умножение матриц 8x8

	std::vector<int> matrixA = GenerateSquareMatrix(MatrixSize8x8);
	std::vector<int> matrixB = GenerateSquareMatrix(MatrixSize8x8);
	
	auto timeMultiplying8x8By1Thread = MeasureTaskTime([&]()
	{
		MatrixOperations::Multiply(matrixA, matrixB);
	});

	auto timeMultiplying8x8By4Thread = MeasureTaskTime([&]()
	{
		MatrixOperations::Multiply(matrixA, matrixB, FourThreads);
	});

	// Умножение матриц 10x10

	matrixA = GenerateSquareMatrix(MatrixSize10x10);
	matrixB = GenerateSquareMatrix(MatrixSize10x10);

	auto timeMultiplying10x10By1Thread = MeasureTaskTime([&]()
	{
		MatrixOperations::Multiply(matrixA, matrixB);
	});

	auto timeMultiplying10x10By4Thread = MeasureTaskTime([&]()
	{
		MatrixOperations::Multiply(matrixA, matrixB, FourThreads);
	});

	// Вывод результата

	PrintMultiplyMatrixTime(
		MatrixSize8x8,
		OneThread,
		std::chrono::duration_cast<std::chrono::microseconds>(timeMultiplying8x8By1Thread)
	);

	PrintMultiplyMatrixTime(
		MatrixSize8x8,
		FourThreads,
		std::chrono::duration_cast<std::chrono::microseconds>(timeMultiplying8x8By4Thread)
	);

	PrintMultiplyMatrixTime(
		MatrixSize10x10,
		OneThread,
		std::chrono::duration_cast<std::chrono::microseconds>(timeMultiplying10x10By1Thread)
	);

	PrintMultiplyMatrixTime(
		MatrixSize10x10,
		FourThreads,
		std::chrono::duration_cast<std::chrono::microseconds>(timeMultiplying10x10By4Thread)
	);
}

Метод умножения матриц

#include "MatrixOperations.h"

std::vector<int> MatrixOperations::Multiply(
	const std::vector<int>& first, 
	const std::vector<int>& second,
	const int threadAmount
)
{
	const int Size = sqrt(first.size());	
	const int Step = float(Size) / threadAmount == Size / threadAmount ?
					 Size / threadAmount :
					 Size / threadAmount + 1;
	int row = 0;

	std::vector<int> result(first.size());
	std::vector<std::thread> threads;
	
	auto CalculateCellValue = [&](int row, int column)
	{
		int cellValue = 0;

		for(int i = 0; i < Size; i++)
		{
			cellValue += first[row * Size + i] * second[i * Size + column];
		}

		return cellValue;
	};

	auto MultiplyMatrix = [&](int startRow, int lastRow)
	{
		for(int row = startRow; row < lastRow; row++)
		{
			for(int column = 0; column < Size; column++)
			{
				result[row * Size + column] = CalculateCellValue(row, column);
			}
		}
	};

	// Запуск потоков
	int lastRow;
	for(int i = 0; i < threadAmount; i++)
	{
		lastRow = row + Step <= Size ? row + Step : Size;
		threads.emplace_back(MultiplyMatrix, row, lastRow);
		
		row += Step;
	}

	// Ожидание завершения потоков
	for(auto& thread : threads)
	{
		thread.join();
	}

	return result;
}

Comments

[rPman]

дай код MatrixOperations::Multiply

[Dyikot]

rPman, он в спойлере "Метод умножения матриц"

Answer 1

[Wataru]

Скорее всего тут дело в кеше процессора. После первых запусков так получилось, что данные оказались в кеше.

Вообще, писать бенчмарки - очень сложно. Надо сначала прогонять тест несколько раз и отбрасывать результаты, а уже потом мерять. Надо быть очень внимательным, если вы запускакте разные тесты в одной программе подряд: результаты работы одного теста могут повлиять на остальные.

Ну и главное, выполнять такое короткое действие всего один раз - это вообще моветон. Надо выполнить его сотню тысяч раз и потом общее время делить на количество запусков. Иначе вы меряете случайный шум в основном. Может тут вам просто все время (не)везет и вот так третий тест оказывается быстрее остальных.

Comments

[Dyikot]

Ну вот сделал 10 000 циклов

Примерно одинаково

[Wataru]

Dyikot, Одна вещь логична: создание потоков сильно более тяжелая операция чем перемножение матриц, поэтому вариант с 4 потоками в ~4 раза медленнее.

Разница между 8x8 и 10x10 все еще укладывается впогрешность. Гоняйте тест 100000 или лучше миллион раз.

Плюс, возможно тут дело в том, что 8 - степень двойки. Так вот получается, что ячейки памяти, к которым вы обращаетесь при проходе по столбу чаще оказываются отстоящими ровно на 64 байта, что есть размер кеш линии. Т.е. они будут вытеснять значения из кеша и там будет больше промахов.

У вас очень короткая и операция и там почти нет вычислений - в основном обращения к памяти. Так что можно получить весьма неожиданные результаты из-за каких-то тонких деталей работы с кешем.

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

[rPman]

еще надо посмотреть как компилятор оптимизировал код Multiply, если он описан в заголовочном файле, он может по умолчанию стать inline и развернуться в процессе для каждой матрицы в свой код, и да, все будет зависеть как в памяти данные лягут