LINUX.ORG.RU
← [kernel dev] прерывание для pci
Физически смежные страницы памяти, userspace →

Надо не вектор в векторе использовать, а просто вектор с индексацией i * n + j

Reset ★★★★★
()
Ответ на: комментарий от Reset

Но удобнее и надёжнее его обернуть. А ещё лучше не изобретать велосипед и взять boost::multi_array, кfr правильно посоветовали.

legolegs ★★★★★
()

>вектор в векторе.
Вот вас бы в отдел по оптимизации производительности кода.
Все бы летало.

antroX
()
Ответ на: комментарий от antroX

А в чем принципиальная разница в производительности? Overhead будет только при создании вектора, доступ же к элементам вектора отлично разворачивается.

#include <vector>

int test(const std::vector< std::vector<int> >& vec, std::size_t i, std::size_t j)
{
        return vec[i][j];
}

ASM:

        .cfi_startproc
        mov     rax, QWORD PTR [rdi]
        lea     rcx, [rsi+rsi*2]
        mov     rax, QWORD PTR [rax+rcx*8]
        mov     eax, DWORD PTR [rax+rdx*4]
        ret
        .cfi_endproc

ASM-код для *(vec + i*N + j) будет меньше на одну инструкцию, но не факт, что быстрее, ибо в первом варианте mov и lea будут выполнены параллельно:

        .cfi_startproc
        lea     rax, [rsi+rsi*4]
        lea     rax, [rdx+rax*2]
        mov     eax, DWORD PTR [rdi+rax*4]
        ret
        .cfi_endproc
sjinks ★★★
()
Ответ на: комментарий от sjinks

А в чем принципиальная разница в производительности?

Почитайте K&R: если вы создадите массив указателей на указатели, а затем каждый его элемент инициализируете одномерным массивом, обращение mas[y][x] будет содержать два суммирования, а вот если вы создадите двумерный массив, или будете использовать одномерный в качестве двумерного, то адресация потребует одно умножение и одно сложение - вот вам и разница в производительности. Попробуйте засечь время скалярного перемножения двух матриц 5000х5000 при обоих способах адресации.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Почитайте K&R: если вы создадите массив указателей на указатели, а затем каждый его элемент инициализируете одномерным массивом, обращение mas[y][x] будет содержать два суммирования, а вот если вы создадите двумерный массив, или будете использовать одномерный в качестве двумерного, то адресация потребует одно умножение и одно сложение - вот вам и разница в производительности.

1) K&R - это гуру С, здесь же разговор идёт за С++

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

3) resize

shty ★★★★★
()
Ответ на: комментарий от Eddy_Em

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

Reset ★★★★★
()
Ответ на: комментарий от sjinks

> mov rax, QWORD PTR [rax+rcx*8]

mov eax, DWORD PTR [rax+rdx*4]


Второй mov нельзя будет выполнить до того, как завершится первый. Даже если повезло, и первый mov попал в l1-кэш, а это не меньше 3 тактов.. И тактов 10-15 при (вполне вероятном) промахе в l1 и попадании в l2.

Manhunt ★★★★★
()
Ответ на: комментарий от Eddy_Em

> Попробуйте засечь время скалярного перемножения двух матриц 5000х5000 при обоих способах адресации.

Кстати, и правда интересно было бы сравнить. Опубликуешь свои результаты?

Manhunt ★★★★★
()
Ответ на: комментарий от Manhunt

Ну так о чем и речь. В случае с vector<vector<int> > mov и lea выполнятся параллельно, на следующих двух mov будет AGI. Получится по производительности не хуже, чем с int[][].

sjinks ★★★
()
Ответ на: комментарий от Eddy_Em

> Почитайте K&R

Я правильно понимаю, что в случае с int** a получим более быстрый код, чем в случае int a[][]?

sjinks ★★★
()
Ответ на: комментарий от Manhunt

Кстати, и правда интересно было бы сравнить. Опубликуешь свои результаты?

Сейчас, тест сваяю...

sjinks

Я правильно понимаю, что в случае с int** a получим более быстрый код, чем в случае int a[][]?

Как получу результаты - напишу.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Manhunt

Результаты.

«Наколенная» тестировалка: 

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define SIZE 5000
#define SIZE2 25000000
double dtime(){
  struct timeval tv;
  struct timezone tz;
  double t;
  gettimeofday(&tv, &tz);
  t = (double)tv.tv_sec + (double)tv.tv_usec*1e-6;
  return(t);
}

int main(int argc, char** argv){
   int i, j, size, k, step, pos, res;
   double tmp;
   int *m0 = (int*)malloc(SIZE2*sizeof(int));
   int *m1 = (int*)malloc(SIZE2*sizeof(int));
   for(i=0; i<size; i++)
      for(j=0; j<size; j++){
         m0[i + j * size] = i* size + j;
         m1[i + j * size] = i* 1000 + j;
     }
   printf("multiplying 1\n");
   double t0 = dtime();
   for(i=0; i<SIZE; i++)
     for(j=0; j<SIZE; j++)
   		tmp = m0[i*SIZE+j] * m1[i*SIZE+j];
   printf("time: %.3f\n", dtime()-t0);
   int *m4[SIZE], *m5[SIZE], sz=SIZE*sizeof(int);
   for(i=0; i<SIZE; i++){
   	  m4[i] = (int*)malloc(sz);
   	  m5[i] = (int*)malloc(sz);
   }
   for(i=0; i<SIZE; i++)
      for(j=0; j<SIZE; j++){
         m4[i][j] = random();
         m5[i][j] = random();
     }
   printf("multiplying 2\n");
   t0 = dtime();
   for(i=0; i<SIZE; i++)
     for(j=0; j<SIZE; j++)
   		tmp = m4[i][j] * m5[i][j];
   printf("time: %.3f\n", dtime()-t0);
}
Результаты: 
gcc simplematrix.c -o simple && ./simple 
multiplying 1
time: 0.380
multiplying 2
time: 0.171
Для двумерных массивов результаты совпадают с результатами для двойных указателей, т.к. инициализируются они как массивы указателей. Проверил это на практике, получив ошибку при компиляции 
simplematrix.c:14: замечание: expected 'int **' but argument is of type 'int (*)[1000]'
(до этого хотел сделать общую функцию инициализации матриц для m[][] и **m)

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Eddy_Em

Странно, у меня получилось с точностью до наоборот :-) Правда, я с -O2 собирал.

Код такой:

#include <vector>
#include <cstddef>
#include <iostream>
#include <sys/time.h>

#define N 10000

static double dt(void)
{
	timeval tv;

	gettimeofday(&tv, 0);
	return tv.tv_sec + 1E-6 * tv.tv_usec;
}


static void mul1(const std::vector<std::vector<double> >& v1, const std::vector<std::vector<double> >& v2, std::size_t n, std::vector<double>& v3)
{
	std::size_t i, j;

	for (i=0; i<n; ++i) {
		v3[i] = 0;
		for (j=0; j<n; ++j) {
			v3[i] += v1[i][j] * v2[j][i];
		}
	}
}

static void mul2(double** v1, double** v2, std::size_t n, std::vector<double>& v3)
{
	std::size_t i, j;

	for (i=0; i<n; ++i) {
		v3[i] = 0;
		for (j=0; j<n; ++j) {
			v3[i] += v1[i][j] * v2[j][i];
		}
	}
}

static void mul3(const double* v1, const double* v2, std::size_t n, std::vector<double>& v3)
{
	std::size_t i, j;

	for (i=0; i<n; ++i) {
		v3[i] = 0;
		for (j=0; j<n; ++j) {
			v3[i] += v1[i*n+j] * v2[j*n+i];
		}
	}
}

int main(int, char**)
{
	std::size_t n = N;
	std::size_t i, j;

	std::vector<double> res;
	double s, e;

	{
		std::vector<std::vector<double> > v1, v2;
		v1.resize(n);
		v2.resize(n);
		res.resize(n);

		for (i=0; i<n; ++i) {
			v1[i].resize(n);
			v2[i].resize(n);
			for (j=0; j<n; ++j) {
				v1[i][j] = i*n+j;
				v2[i][j] = i*n+j;
			}
		}

		s = dt();
		mul1(v1, v2, n, res);
		e = dt();

		std::cout << "vector<vector<double> >: " << (e - s) << std::endl;

		for (i=0; i<n; ++i) {
			v1[i].clear();
			v2[i].clear();
		}

		v1.clear();
		v2.clear();
		res.clear();
		res.resize(n);
	}

	{
		double** v1 = new double*[n];
		double** v2 = new double*[n];

		for (i=0; i<n; ++i) {
			v1[i] = new double[n];
			v2[i] = new double[n];
			for (j=0; j<n; ++j) {
				v1[i][j] = i*n+j;
				v2[i][j] = i*n+j;
			}
		}

		s = dt();
		mul2(v1, v2, n, res);
		e = dt();

		std::cout << "double**: " << (e - s) << std::endl;

		for (i=0; i<n; ++i) {
			delete[] v1[i];
			delete[] v2[i];
		}

		delete[] v1;
		delete[] v2;
		res.clear();
		res.resize(n);
	}

	{
		double* v1 = new double[n*n];
		double* v2 = new double[n*n];

		for (i=0; i<n; ++i) {
			for (j=0; j<n; ++j) {
				v1[i*n+j] = i*n+j;
				v2[i*n+j] = i*n+j;
			}
		}

		s = dt();
		mul3(v1, v2, n, res);
		e = dt();

		std::cout << "double*: " << (e - s) << std::endl;

		delete[] v1;
		delete[] v2;
		res.clear();
		res.resize(n);
	}


	return 0;
}

Собиралось так: g++ test.cpp -o test -O2

Результат:

$ ./test 
vector<vector<double> >: 3.20962
double**: 3.17741
double*: 2.98655

После 10 запусков:

vector<vector<double> >: 3.24287
double**: 3.17827
double*: 3.1184
vector<vector<double> >: 3.21145
double**: 3.17882
double*: 3.04051
vector<vector<double> >: 3.21105
double**: 3.17848
double*: 3.02677
vector<vector<double> >: 3.21043
double**: 3.1786
double*: 2.91319
vector<vector<double> >: 3.21116
double**: 3.18011
double*: 2.92758
vector<vector<double> >: 3.21062
double**: 3.17953
double*: 3.0366
vector<vector<double> >: 3.21078
double**: 3.17902
double*: 3.15091
vector<vector<double> >: 3.26491
double**: 3.17802
double*: 2.95182
vector<vector<double> >: 3.21093
double**: 3.17969
double*: 2.93249
vector<vector<double> >: 3.21252
double**: 3.17858
double*: 3.07989

Если в опции сборки добавлять -march=native (для правильного планирования инструкций), то vector<vector<double> > и double** показывают очень близкие результаты (я стандартное отклонение не считал, но с виду результаты в пределах статистической погрешности), а double* явно выходит вперед (2.9 против 3.18).

Вообще интересно посмотреть на других платформах (у меня AMD Phenom(tm) II X4 940 Processor), разных версиях gcc/icc, но без Sylvia тут не обойтись.

sjinks ★★★
()
Ответ на: комментарий от sjinks

Intel(R) Xeon(R) CPU E5420 @ 2.50GHz

vector<vector<double> >: 1.39127
double**: 1.33119
double*: 1.22736
vector<vector<double> >: 1.39658
double**: 1.33539
double*: 1.22806
vector<vector<double> >: 1.39579
double**: 1.33512
double*: 1.22214
vector<vector<double> >: 1.39085
double**: 1.331
double*: 1.22526
...

разница все таки есть, пусть и не большая

AlexVR ★★★★★
()
Ответ на: комментарий от sjinks

У меня (C2Q 2.5GGz, 2Gb RAM) вообще интересные результаты: 

19:10 /dev/shm
g++ 1.c -o test -O2

19:10 /dev/shm
./test 
vector<vector<double> >: 8.45809
double**: 7.97306
double*: 2.71873

19:11 /dev/shm
g++ 1.c -o test && ./test 
vector<vector<double> >: 18.1506
double**: 8.91551
double*: 5.92917

19:12 /dev/shm
g++ 1.c -o test -march=native && ./test 
vector<vector<double> >: 16.0304
double**: 9.95741
double*: 6.87652
Видимо, чего-то компилятор плюсов оптимизирует (или наоборот).

Eddy_Em ☆☆☆☆☆
()

Ради интереса изобразил перемножение прямоугольных матриц. Использовались 3 разных алгоритма:

  • Slow multiplication: обычная тривиальная свёртка
  • Fast multiplication: пытается учитывать факт существования l1-кэша
  • UltraFast multiplication: пытается учитывать факт существования l1-кэша и l2-кэша

Параметры должны быть подобраны так, чтобы «Expected small block size» был в 3-4 раза меньше размера l1 data cache, а «Expected big block size» был в 3-4 раза меньше размера l2 cache вашего процессора.

Результаты такие (Core2 E8200): 

$ g++  -O2 c.cc
$ ./a.out

Multiply matrix 2048x3072 by matrix 3072x2560
Expected memory usage: 77594624 bytes
Expected small block size: 4096 bytes
Expected big block size: 1048576 bytes

Testing vector[i * size_j + j]:
Slow multiplication: 258.297 seconds
Fast multiplication: 44.1382 seconds
UltraFast multiplication: 42.857 seconds

Testing (vector[i])[j]:
Slow multiplication: 149.886 seconds
Fast multiplication: 57.8372 seconds
UltraFast multiplication: 25.8969 seconds

Testing vector[i * size_j + j]:
Slow multiplication: 252.399 seconds
Fast multiplication: 43.0248 seconds
UltraFast multiplication: 41.5412 seconds

Testing (vector[i])[j]:
Slow multiplication: 150.364 seconds
Fast multiplication: 57.2947 seconds
UltraFast multiplication: 26.2496 seconds

То есть:

  • Slow multiplication: просто вектор намного медленнее, чем вектор векторов
  • Fast multiplication: просто вектор быстрее чем вектор векторов
  • UltraFast multiplication: просто вектор ничего не выиграл по сравнению с Fast multiplication, за то вектор векторов показал наилучший из всех результатов

Объяснить столь неустойчивое поведение я пока не могу. Смотрел дизассемблер на предмет инлайна в процедурах умножения, вроде бы все что нужно - инлайнится.

Manhunt ★★★★★
()
Ответ на: комментарий от Manhunt 
#include <vector>
#include <iostream>
#include <cstdlib>
#include <cassert>
#include <sys/time.h>

typedef unsigned Scalar;

struct MatrixBase1
{
	size_t m_size_i, m_size_j;
	std::vector<Scalar> m_array;

	MatrixBase1(size_t size_i, size_t size_j) :
		m_size_i(size_i), m_size_j(size_j),
		m_array(size_i * size_j)
	{}
	Scalar &At(size_t i, size_t j)
	{ return m_array[i * m_size_j + j]; }
	const Scalar &At(size_t i, size_t j) const
	{ return m_array[i * m_size_j + j]; }
};

struct MatrixBase2
{
	size_t m_size_i, m_size_j;
	std::vector<std::vector<Scalar> > m_array;

	MatrixBase2(size_t size_i, size_t size_j) :
		m_size_i(size_i), m_size_j(size_j),
		m_array(size_i, std::vector<Scalar>(size_j))
	{}
	Scalar &At(size_t i, size_t j)
	{ return (m_array[i])[j]; }
	const Scalar &At(size_t i, size_t j) const
	{ return (m_array[i])[j]; }
};

template<class MatrixBase>
class Matrix
{
	MatrixBase base;
public:
	Matrix(size_t size_i, size_t size_j) : base(size_i, size_j) {}
	void SetToRand()
	{
		for(size_t i = 0; i < base.m_size_i; ++i)
		for(size_t j = 0; j < base.m_size_j; ++j)
			base.At(i, j) = ( std::rand() & 3 );
	}
	void SetToZero()
	{
		for(size_t i = 0; i < base.m_size_i; ++i)
		for(size_t j = 0; j < base.m_size_j; ++j)
			base.At(i, j) = 0;
	}
	bool IsEqual(const Matrix &arg) const
	{
		if(base.m_size_i != arg.base.m_size_i || base.m_size_j != arg.base.m_size_j)
			return false;

		for(size_t i = 0; i < base.m_size_i; ++i)
		for(size_t j = 0; j < base.m_size_j; ++j)
		if(base.At(i, j) != arg.base.At(i, j))
			return false;

		return true;
	}
	Matrix MulSlow(const Matrix &arg) const
	{
		assert(base.m_size_j == arg.base.m_size_i);

		const size_t size_k = base.m_size_j;

		Matrix dst(base.m_size_i, arg.base.m_size_j);

		dst.SetToRand();

		for(size_t i = 0; i < dst.base.m_size_i; ++i)
		for(size_t j = 0; j < dst.base.m_size_j; ++j)
		{
			Scalar t = 0;
			for(size_t k = 0; k < size_k; ++k)
			{
				t += base.At(i, k) * arg.base.At(k, j);
			}
			dst.base.At(i, j) = t;
		}

		return dst;
	}
	Matrix MulFast(const Matrix &arg, size_t block_size) const
	{
		assert(base.m_size_j == arg.base.m_size_i);

		const size_t size_k = base.m_size_j;

		Matrix dst(base.m_size_i, arg.base.m_size_j);

		assert(dst.base.m_size_j % block_size == 0);
		assert(dst.base.m_size_i % block_size == 0);
		assert(size_k % block_size == 0);

		const size_t size_ii = dst.base.m_size_i / block_size;
		const size_t size_jj = dst.base.m_size_j / block_size;
		const size_t size_kk = size_k / block_size;

		dst.SetToZero();

		for(size_t ii = 0; ii < size_ii; ++ii)
		for(size_t jj = 0; jj < size_jj; ++jj)
		for(size_t kk = 0; kk < size_kk; ++kk)
		for(size_t iii = 0; iii < block_size; ++iii)
		for(size_t jjj = 0; jjj < block_size; ++jjj)
		{
			size_t i  = ii * block_size + iii;
			size_t j  = jj * block_size + jjj;
			size_t k_ = kk * block_size;

			Scalar t = 0;
			for(size_t kkk = 0; kkk < block_size; ++kkk)
			{
				size_t k = k_ + kkk;
				t += base.At(i, k) * arg.base.At(k, j);
			}
			dst.base.At(i, j) += t;
		}

		return dst;
	}
	Matrix MulUltraFast(const Matrix &arg, size_t block_size_big, size_t block_size_small) const
	{
		assert(base.m_size_j == arg.base.m_size_i);

		const size_t size_k = base.m_size_j;

		Matrix dst(base.m_size_i, arg.base.m_size_j);

		assert(block_size_big % block_size_small == 0);

		assert(dst.base.m_size_j % block_size_big == 0);
		assert(dst.base.m_size_i % block_size_big == 0);
		assert(size_k % block_size_big == 0);

		const size_t size_ii = dst.base.m_size_i / block_size_big;
		const size_t size_jj = dst.base.m_size_j / block_size_big;
		const size_t size_kk = size_k / block_size_big;

		const size_t block_size_ratio = block_size_big / block_size_small;

		dst.SetToZero();

		for(size_t ii = 0; ii < size_ii; ++ii)
		for(size_t jj = 0; jj < size_jj; ++jj)
		for(size_t kk = 0; kk < size_kk; ++kk)
		for(size_t iii = 0; iii < block_size_ratio; ++iii)
		for(size_t jjj = 0; jjj < block_size_ratio; ++jjj)
		for(size_t kkk = 0; kkk < block_size_ratio; ++kkk)
		for(size_t iiii = 0; iiii < block_size_small; ++iiii)
		for(size_t jjjj = 0; jjjj < block_size_small; ++jjjj)
		{
			size_t i  = ii * block_size_big + iii * block_size_small + iiii;
			size_t j  = jj * block_size_big + jjj * block_size_small + jjjj;
			size_t k_ = kk * block_size_big + kkk * block_size_small;

			Scalar t = 0;
			for(size_t kkkk = 0; kkkk < block_size_small; ++kkkk)
			{
				size_t k = k_ + kkkk;
				t += base.At(i, k) * arg.base.At(k, j);
			}
			dst.base.At(i, j) += t;
		}

		return dst;
	}
};

typedef Matrix<MatrixBase1> Matrix1;
typedef Matrix<MatrixBase2> Matrix2;

double dt(void) 
{ 
   timeval tv; 
 
   gettimeofday(&tv, 0); 
   return tv.tv_sec + 1E-6 * tv.tv_usec; 
}

template <class Matrix>
void DoTest(size_t i, size_t j, size_t k, size_t block_size_big, size_t block_size_small)
{
	Matrix m1(i, k);
	Matrix m2(k, j);

	m1.SetToRand();
	m2.SetToRand();

	double t31 = dt();
	Matrix m3(m1.MulSlow(m2));
	double t32 = dt();

	std::cout << "Slow multiplication: " << t32 - t31 << " seconds" << std::endl;

	double t41 = dt();
	Matrix m4(m1.MulFast(m2, block_size_small));
	double t42 = dt();

	std::cout << "Fast multiplication: " << t42 - t41 << " seconds" << std::endl;

	double t51 = dt();
	Matrix m5(m1.MulUltraFast(m2, block_size_big, block_size_small));
	double t52 = dt();

	std::cout << "UltraFast multiplication: " << t52 - t51 << " seconds" << std::endl;

	assert(m3.IsEqual(m4));
	assert(m4.IsEqual(m5));
}

void DoTests(size_t i, size_t j, size_t k, size_t block_size_big, size_t block_size_small)
{
	std::cout << std::endl << "Testing vector[i * size_j + j]:" << std::endl;
	DoTest<Matrix1>(i, j, k, block_size_big, block_size_small);

	std::cout << std::endl << "Testing (vector[i])[j]:" << std::endl;
	DoTest<Matrix2>(i, j, k, block_size_big, block_size_small);
}

int main()
{
	size_t small_block = 32;
	size_t big_block = 512;

	size_t i = (1 << 11);
	size_t j = i + big_block;
	size_t k = j + big_block;

	std::cout << "Multiply matrix " << i << "x" << k << " by matrix " << k << "x" << j << std::endl;
	std::cout << "Expected memory usage: " << (i*k + k*j + i*j) * sizeof(Scalar) << " bytes" << std::endl;
	std::cout << "Expected small block size: " << small_block * small_block * sizeof(Scalar) << " bytes" << std::endl;
	std::cout << "Expected big block size: " << big_block * big_block * sizeof(Scalar) << " bytes" << std::endl;

	while(true)
	{
		DoTests(i, j, k, big_block, small_block);
	}

	return 0;
}
Manhunt ★★★★★
()
Ответ на: комментарий от sjinks 
gcc -v
Используются внутренние спецификации.
Целевая архитектура: i586-manbo-linux-gnu
Параметры конфигурации: ../configure --prefix=/usr --libexecdir=/usr/lib --with-slibdir=/lib --mandir=/usr/share/man --infodir=/usr/share/info --enable-checking=release --enable-languages=c,c++,fortran,objc,obj-c++,java --build=i586-manbo-linux-gnu --host=i586-manbo-linux-gnu --with-cpu=generic --with-system-zlib --enable-threads=posix --enable-shared --enable-long-long --enable-__cxa_atexit --disable-libunwind-exceptions --enable-clocale=gnu --enable-java-awt=gtk --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-1.5.0.0/jre --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-gtk-cairo --disable-libjava-multilib --enable-ssp --disable-libssp --disable-werror
Модель многопотоковости: posix
gcc версия 4.3.2 (GCC)

мандрива 9.1.

Eddy_Em ☆☆☆☆☆
()
Ответ на: комментарий от Manhunt

> Объяснить столь неустойчивое поведение я пока не могу.

Похоже, что эта неустойчивость как-то связана с размерами матриц.

Например, для матриц на основе «просто вектора», на Slow multiplication мартиц 2048x2048 и 2048x2048 уходит 160 секунд, а на Slow multiplication мартиц 2048x2112 и 2112x2080 уходит 70 секунд. То есть почти в 2 (!!!!) раза меньше.

Manhunt ★★★★★
()
Ответ на: комментарий от Manhunt

> Объяснить столь неустойчивое поведение я пока не могу.

Возможно, из-за выравнивания строк по восьмибайтной границе?

sjinks ★★★
()
Ответ на: комментарий от Manhunt

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

Manhunt ★★★★★
()
Ответ на: комментарий от sjinks

Сравните только :D

Multiply matrix 2048x3072 by matrix 3072x2560 
Expected memory usage: 77594624 bytes 
Expected small block size: 4096 bytes 
Expected big block size: 1048576 bytes 
 
Testing vector[i * size_j + j]: 
Slow multiplication: 258.297 seconds 
Fast multiplication: 44.1382 seconds 
UltraFast multiplication: 42.857 seconds 
 
Testing (vector[i])[j]: 
Slow multiplication: 149.886 seconds 
Fast multiplication: 57.8372 seconds 
UltraFast multiplication: 25.8969 seconds
Multiply matrix 2000x3000 by matrix 3000x2500
Expected memory usage: 74000000 bytes
Expected small block size: 2500 bytes
Expected big block size: 1000000 bytes

Testing vector[i * size_j + j]:
Slow multiplication: 135.988 seconds
Fast multiplication: 25.6748 seconds
UltraFast multiplication: 24.3637 seconds

Testing (vector[i])[j]:
Slow multiplication: 127.981 seconds
Fast multiplication: 25.3058 seconds
UltraFast multiplication: 24.7332 seconds
Manhunt ★★★★★
()
Ответ на: комментарий от Reset

> Надо не вектор в векторе использовать, а просто вектор с индексацией i * n + j

Пока выходит, что вектор в векторе ведет себя предсказуемее. ЧЯДНТ?

Manhunt ★★★★★
()
Ответ на: комментарий от Manhunt

Manhunt, такой вопрос: каковы характеристики кэшей на Вашем компьютере?

for i in /sys/devices/system/cpu/cpu0/cache/index*; do cat $i/{level,type,size,coherency_line_size,number_of_sets,ways_of_associativity}; done

sjinks ★★★
()
Ответ на: комментарий от Manhunt

У меня получается так:

L1: 64K, 2 ways associativity
L2: 512K, 16 ways associativity

Critical Stride = Cache Size / Ways of Associativity = 32K

То есть при доступе к данным, которые отстоят друг от друга на 32K, начинаются cache contentions.

Multiply matrix 2048x2304 by matrix 2304x2176
Expected memory usage: 56754176 bytes
Expected small block size: 16384 bytes
Expected big block size: 65536 bytes

Testing vector[i * size_j + j]:
Slow multiplication: 134.448 seconds
Fast multiplication: 17.119 seconds
UltraFast multiplication: 18.6634 seconds

Testing (vector[i])[j]:
Slow multiplication: 142.65 seconds
Fast multiplication: 37.209 seconds
UltraFast multiplication: 18.1762 seconds

sjinks ★★★
()
Ответ на: комментарий от sjinks

> В случае с vector<vector<int> > mov и lea выполнятся параллельно, на следующих двух mov будет AGI

Кого интересует количество инстукций? Считай число обращений в память, это только имеет значение...

anonymous
()

Смотря шо надо делать. Многоуважаемые доны экономят даже на i*n + j:

Код примерно такой:

size_t Stride /*= количество элементов в строке */;

T* data = static_cast<T*>( malloc (Stride*Height*sizeof(T)) ); /*проверочку опустим ;) */ T**row_descriptor = static_cast<T**>( malloc (Height*sizeof(T*)) ); /* опять проверочку опустим ;) */

/*инициализируем*/

for (size_t i=0, j=0; i < Height; ++i, j += Stride ) row_descriptor[i] = data + j;

В дальнейшем, радостно используем row_descriptor[i][j] для доступа к j-му элементу в i-й строке.

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

Можно играться в выравнивание, тогда Stride будет означать не количество _элементов_, а количество байт между строками (подобным образом устроен QImage в Qt).

nikitos ★★★
()
Ответ на: комментарий от sjinks

флаг -O2 не включает векторизацию для GCC, надо или -O3 или отдельно указывать -ftree-vectorize

Core2 Duo,

Intel C/C++ compiler v11.1
icpc11 -O2 -xT -ip test.cpp -o test && ./test

vector<vector<double> >: 1.40601
double**: 1.10591
double*: 1.40177

GCC 4.5.1pre
c++45 -O2 -ftree-vectorize -march=core2 -mssse3 test.cpp -o test && ./test
vector<vector<double> >: 1.23303
double**: 1.16918
double*: 1.40975

GCC 4.4.4 (4.4.5 svn-redhat)
c++44 -O2 -ftree-vectorize -march=core2 -mssse3 test.cpp -o test && ./test
vector<vector<double> >: 1.22611
double**: 1.15511
double*: 1.34644

GCC 4.3.5
c++43 -O2 -ftree-vectorize -march=core2 -mssse3 test.cpp -o test && ./test
vector<vector<double> >: 1.63565
double**: 1.40796
double*: 1.38816

GCC 4.2.4 (nocona, sse3)
c++42 -O2 -ftree-vectorize -march=nocona -msse3 test.cpp -o test && ./test
vector<vector<double> >: 1.65644
double**: 1.43716
double*: 1.39468

GCC 4.1.2 (Redhat -27)
c++41 -O2 -ftree-vectorize -march=core2 -mssse3 test.cpp -o test && ./test
removed `test'
vector<vector<double> >: 1.36422
double**: 1.33117
double*: 1.36476

clang version 2.0 (trunk 105935)
vector<vector<double> >: 1.52785
double**: 1.42268
double*: 1.34642

Sylvia ★★★★★
()
Ответ на: комментарий от Sylvia

для сравнения Atom, 32 и 64 бита
GCC 4.4.4 (redhat-svn)

-m64 -ftree-vectorize -O2 -march=atom -msse3

vector<vector<double> >: 27.5617
double**: 27.7288
double*: 21.6155


-m32 -ftree-vectorize -O2 -march=atom -msse3

vector<vector<double> >: 27.5338
double**: 26.4639
double*: 21.8002

Sylvia ★★★★★
()
Ответ на: комментарий от nikitos

И чем оно лучше просто массива, а не массива указателей? В двумерном массиве тоже можно съэкономить умножение если очень надо, точно таким же способом. Причём у вас row_descriptor[i][j] - двойное обращение в память, а там будет только одно.

anonymous
()
Ответ на: комментарий от anonymous

row_descriptor обычно кешируется лучше чем вектор векторов, ну и это динамическая структура данных, да, когда известен размер во время компиляции - то простой двумерный массив конечно предпочтительнее.

Лучше эта конструкция когда j (индекс строки) сложно предсказуем, например, в таких алгоритмах как neighborhood floodfill на изображении.

nikitos ★★★
()
Ответ на: комментарий от Manhunt

Погонял код под cachegrind'ом (правда, только свой), получил такую картину:

vector<vector<double> >:
L1D read misses: 38.99%
L2 read misses: 45.05%

double**:
L1D read misses: 31.47%
L2 read misses: 44.75%

double*:
L1D read misses: 29.23%
L2 read misses: 10.10%

cachegrind гонялся так: valgrind --tool=cachegrind --cache-sim=yes --I1=65536,2,64 --D1=65536,2,64 --L2=524288,16,64 ./test

В зависимости от размера матрицы результаты будут меняться, но на тестах лучше всего ведет себя m[i*n+j]. Такие вот пироги.

sjinks ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← [kernel dev] прерывание для pci
Development
Физически смежные страницы памяти, userspace →