Форум программистов, компьютерный форум CyberForum.ru

Оптимизация доступа к памяти - C++

Восстановить пароль Регистрация
 
maxm
 Аватар для maxm
33 / 20 / 6
Регистрация: 17.07.2014
Сообщений: 351
19.02.2016, 10:13     Оптимизация доступа к памяти #1
Интересует вопрос. При умножении матриц даст ли результат такая замена или компилятор видит что в цыкле адрес ячейки тот же и сам оптимизирует? И какой компилятор так сделает а какой нет?

C++
1
2
3
4
5
6
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < n; ++k)
{
x[i][j] = a[i][k] + b[k][j];
}
на

C++
1
2
3
4
5
6
7
8
9
10
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
{
int f = 0;
for (int k = 0; k < n; ++k)
{
f += a[i][k] + b[k][j];
}
x[i][j] = f;
}
Добавлено через 2 минуты
Речь идет о времени доступа к элементу х
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
19.02.2016, 18:33     Оптимизация доступа к памяти #2
x[i][k] - больше вопрос к этому. если было double **x то расположение строк в памяти не предсказуемо и может свести на нет все твои оптимизации.
maxm
 Аватар для maxm
33 / 20 / 6
Регистрация: 17.07.2014
Сообщений: 351
19.02.2016, 23:01  [ТС]     Оптимизация доступа к памяти #3
При чем здесь x[i][k] ?
Я спрашивал, даст ли что то такая замена реально для матрицы большого размера, или нет? И если нет, то почему? Оптимизирует компилятор?
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
19.02.2016, 23:17     Оптимизация доступа к памяти #4
maxm, Во первых, у вас код не для умножения матриц.
Во вторых, да оптимизирует.
В третьих, если нужно произведение плотных матриц - используйте BLAS и не парьтесь (там, ЕМНИП, для оптимизации попадания в кэш 7 вложенных циклов).
hoggy
5225 / 2116 / 403
Регистрация: 15.11.2014
Сообщений: 4,800
Завершенные тесты: 1
19.02.2016, 23:21     Оптимизация доступа к памяти #5
Цитата Сообщение от maxm Посмотреть сообщение
даст ли результат такая замена или компилятор видит что в цыкле адрес ячейки тот же и сам оптимизирует?
нужно смотреть асм-листинги.

но вообще то,код вида:
C++
1
2
3
4
for (size_t i = 0; i < n; ++i)
    for (size_t j = 0; j < n; ++j)
        for (size_t k = 0; k < n; ++k)
            x[i][j] = a[i][k] + b[k][j];
эквивалентен:
C++
1
2
3
4
5
6
7
8
for (size_t i = 0; i < n; ++i)
    for (size_t j = 0; j < n; ++j)
    {
        auto& val = x[i][j];
        auto& ar = a[i];
        for (size_t k = 0; k < n; ++k)
            val = ar[k] + b[k][j];
    }
компиляторы уже давным давно научились
оптимизировать промежуточные вычисления.

поэтому, я бы не стал заморачиваться,
и экономить на спичках.
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
20.02.2016, 16:20     Оптимизация доступа к памяти #6
Цитата Сообщение от maxm Посмотреть сообщение
При умножении матриц даст ли результат такая замена
Если бы ты замерил время, то были бы другие вопросы .Вот тебе пример для раздумий. А так, некоторые "оптимизации" в коде могут и испортить, другие могут дать неожиданный прирост

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
 
double **genArrMatrix(size_t height, size_t width) {
  std::default_random_engine generator;
  std::uniform_real_distribution<double> distribution(0.0,1.0);
 
  double **a = new double*[height];
  for(size_t i=0; i<height; ++i) {
    a[i] = new double[width];
    for(size_t j=0; j<width; ++j) {
      a[i][j] = distribution(generator);
    }
  }
  return a;
}
 
double **newArrMatrix(size_t height, size_t width) {
  std::default_random_engine generator;
  std::uniform_real_distribution<double> distribution(0.0,1.0);
 
  double **a = new double*[height];
  for(size_t i=0; i<height; ++i) {
    a[i] = new double[width];
  }  
  return a;
}
 
 
void deleteArrMatrix(double ** &arr_matrix, size_t height) {
  for(size_t i=0; i<height; ++i) {
    delete(arr_matrix[i]);
  }
  delete arr_matrix;
  arr_matrix = nullptr;
}
 
double **mul_v1_ArrMatrix(double **left, size_t height_left, size_t width_left, double **right, size_t width_right) {
  double **result = newArrMatrix(height_left, width_right);
  for (size_t i = 0; i < height_left; ++i) {
    for (size_t j = 0; j < width_right; ++j) {
      for (size_t k = 0; k < width_left; ++k)
      {
        result[i][j] += left[i][k] * right[k][j];
      }
    }
  }
  return result;
}
 
double **mul_v2_ArrMatrix(double **left, size_t height_left, size_t width_left, double **right, size_t width_right) {
  double **result = newArrMatrix(height_left, width_right);
  for (size_t i = 0; i < height_left; ++i) {
    for (size_t j = 0; j < width_right; ++j) {
      double sum =0;
      for (size_t k = 0; k < width_left; ++k)
      {
        sum += left[i][k] * right[k][j];
      }
      result[i][j] = sum;
    }
  }
  return result;
}
 
double **mul_v3_ArrMatrix(double **left, size_t height_left, size_t width_left, double **right, size_t width_right) {
  double **result = newArrMatrix(height_left, width_right);
  for (size_t j = 0; j < width_right; ++j) {
    for (size_t i = 0; i < height_left; ++i) {
      for (size_t k = 0; k < width_left; ++k)
      {
        result[i][j] += left[i][k] * right[k][j];
      }
    }
  }
  return result;
}
 
double **mul_v4_ArrMatrix(double **left, size_t height_left, size_t width_left, double **right, size_t width_right) {
  double **result = newArrMatrix(height_left, width_right);
  for (size_t j = 0; j < width_right; ++j) {
 
    double *tmp_column = new double[width_left];
    for(size_t k=0; k<width_left; ++k)
      tmp_column[k]=right[k][j];
 
    for (size_t i = 0; i < height_left; ++i) {
      for (size_t k = 0; k < width_left; ++k)
      {
        result[i][j] += left[i][k] * tmp_column[k];
      }
    }
 
    delete tmp_column;
  }
  return result;
}
 
int main() {
  const size_t n = 1000;
  const size_t m = 1000;
  const size_t k = 1000;
  
  using namespace std::chrono;
  high_resolution_clock::time_point t1, t2;
 
  std::cout << "Start:...\n";
 
  t1 = high_resolution_clock::now();
  double **A = genArrMatrix(n, m);
  t2 = high_resolution_clock::now();
  std::cout << "Time for generate A: "
            << duration_cast<duration<double>>(t2 - t1).count()
            << std::endl;
 
  t1 = high_resolution_clock::now();
  double **B = genArrMatrix(m, k);
  t2 = high_resolution_clock::now();                                       
  std::cout << "Time for generate B: "
            << duration_cast<duration<double>>(t2 - t1).count()
            << std::endl;
 
  t1 = high_resolution_clock::now();
  double **C1 = mul_v1_ArrMatrix(A, n, m, B, k);
  t2 = high_resolution_clock::now();
  std::cout << "Time for A*B v1: "
            << duration_cast<duration<double>>(t2 - t1).count()
            << std::endl;
 
//  deleteArrMatrix(C1, n);
 
  t1 = high_resolution_clock::now();
  double ** C2 = mul_v2_ArrMatrix(A, n, m, B, k);
  t2 = high_resolution_clock::now();
  std::cout << "Time for A*B v2: "
            << duration_cast<duration<double>>(t2 - t1).count()
            << std::endl;
 
  t1 = high_resolution_clock::now();
  double ** C3 = mul_v3_ArrMatrix(A, n, m, B, k);
  t2 = high_resolution_clock::now();
  std::cout << "Time for A*B v3: "
            << duration_cast<duration<double>>(t2 - t1).count()
            << std::endl;
 
  t1 = high_resolution_clock::now();
  double ** C4 = mul_v4_ArrMatrix(A, n, m, B, k);
  t2 = high_resolution_clock::now();
  std::cout << "Time for A*B v4: "
            << duration_cast<duration<double>>(t2 - t1).count()
            << std::endl;
 
  deleteArrMatrix(A, n);
  deleteArrMatrix(B, m);
  deleteArrMatrix(C1, n);
  deleteArrMatrix(C2, n);
  deleteArrMatrix(C3, n);
  deleteArrMatrix(C4, n);
  return 0;
}
Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$ g++ -Wall -O -std=c++11 test_mult_matrix.cpp && ./a.out 
Start:...
Time for generate A: 0.0135852
Time for generate B: 0.0137066
Time for A*B v1: 7.86627
Time for A*B v2: 8.02966
Time for A*B v3: 7.41704
Time for A*B v4: 2.94677
$ g++ -Wall -std=c++11 test_mult_matrix.cpp && ./a.out 
Start:...
Time for generate A: 0.163797
Time for generate B: 0.16573
Time for A*B v1: 14.8662
Time for A*B v2: 10.3445
Time for A*B v3: 7.78858
Time for A*B v4: 4.48194
Nosey
 Аватар для Nosey
1184 / 351 / 102
Регистрация: 22.10.2014
Сообщений: 786
Завершенные тесты: 2
20.02.2016, 16:33     Оптимизация доступа к памяти #7
Цитата Сообщение от AlexVRud Посмотреть сообщение
другие могут дать неожиданный прирост
На таких крупных матрицах ваш вариант mul_v4_ArrMatrix избавляетсяя от кэшмиссов, поэтому такой хороший прирост.
В общем случае для научных рассчётов лучше использовать SSE али CUDA.
Если же это 3D'шные матрицы, то алгоритм оставить самый простой, но при этом размеры матрицы определить в компайлтайме -> все циклы развернутся.

Но однозначно хороший пример, да.
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
20.02.2016, 16:47     Оптимизация доступа к памяти #8
Цитата Сообщение от Nosey Посмотреть сообщение
В общем случае для научных рассчётов лучше использовать SSE али CUDA.
Вы правы, но есть одно но: перевести алгоритм на CUDA может быть очень нетривиальной задачей. Повторюсь: для алгоритмов на плотных матрицах лучше всего BLAS (в т.ч. CUBLAS).
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
21.02.2016, 15:37     Оптимизация доступа к памяти #9
Цитата Сообщение от maxm Посмотреть сообщение
При чем здесь x[i][k] ?
Замени на x[i*n+k] и сравни время
maxm
 Аватар для maxm
33 / 20 / 6
Регистрация: 17.07.2014
Сообщений: 351
21.02.2016, 17:23  [ТС]     Оптимизация доступа к памяти #10
Киньте sample как измерить время нормально, я гуглил, добился только в секундах

И не опасный ли такой прием ?
Цитата Сообщение от AlexVRud Посмотреть сообщение
Замени на x[i*n+k] и сравни время
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
21.02.2016, 18:50     Оптимизация доступа к памяти #11
Цитата Сообщение от hoggy Посмотреть сообщение
но вообще то,код вида:
...
эквивалентен:
C++
1
2
3
4
5
6
7
8
for (size_t i = 0; i < n; ++i)
    for (size_t j = 0; j < n; ++j)
    {
        auto& val = x[i][j];
        auto& ar = a[i];
        for (size_t k = 0; k < n; ++k)
            val = ar[k] + b[k][j];
    }
Это так, но в первом посте был вариант с переменной f для суммирования, а это не всегда так просто сделать - для этого компилятор должен знать, что x[][] не пересекается с a[][] и b[][].
AlexVRud
413 / 142 / 36
Регистрация: 04.07.2014
Сообщений: 413
21.02.2016, 23:07     Оптимизация доступа к памяти #12
Цитата Сообщение от maxm Посмотреть сообщение
Киньте sample как измерить время нормально,
А выше то по тексту ты смотрел примеры?
return 0
2 / 2 / 1
Регистрация: 21.02.2016
Сообщений: 28
21.02.2016, 23:57     Оптимизация доступа к памяти #13
Интересно, местные знатоки слышали о сложности алгоритмов
maxm
 Аватар для maxm
33 / 20 / 6
Регистрация: 17.07.2014
Сообщений: 351
22.02.2016, 00:10  [ТС]     Оптимизация доступа к памяти #14
Это к чему ты сказал
Цитата Сообщение от return 0 Посмотреть сообщение
Интересно, местные знатоки слышали о сложности алгоритмов
hoggy
5225 / 2116 / 403
Регистрация: 15.11.2014
Сообщений: 4,800
Завершенные тесты: 1
22.02.2016, 00:52     Оптимизация доступа к памяти #15
Цитата Сообщение от Somebody Посмотреть сообщение
Это так, но в первом посте был вариант с переменной f для суммирования, а это не всегда так просто сделать - для этого компилятор должен знать, что x[][] не пересекается с a[][] и b[][].
не вижу такой потребности.
как факт печесенения/непересечение может влиять на эквивалент?
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
22.02.2016, 11:06     Оптимизация доступа к памяти #16
Цитата Сообщение от hoggy Посмотреть сообщение
как факт печесенения/непересечение может влиять на эквивалент?
Если промежуточные результаты будут в x[i][j], то одним из значений a[i][k] или b[k][j] может оказаться это самое x[i][j], значение которого уже не будет совпадать с исходным.

Добавлено через 1 минуту
Конечно, в таком случае и с f реализация алгоритма будет некорректной, но это уже другая история.
hoggy
5225 / 2116 / 403
Регистрация: 15.11.2014
Сообщений: 4,800
Завершенные тесты: 1
22.02.2016, 11:19     Оптимизация доступа к памяти #17
Цитата Сообщение от Somebody Посмотреть сообщение
Если промежуточные результаты будут в x[i][j], то одним из значений a[i][k] или b[k][j] может оказаться это самое x[i][j], значение которого уже не будет совпадать с исходным.
неужели?

если вы обратили внимание,
то кэшируются ссылки, а не копии.

приведите пожалуйста пример-иллюстрацию возможной проблемы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.02.2016, 11:23     Оптимизация доступа к памяти
Еще ссылки по теме:

C++ Оптимизация программы по памяти
не работает strncmp - нет доступа к памяти C++
C++ Ошибка доступа к памяти при выходе из программы

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
22.02.2016, 11:23     Оптимизация доступа к памяти #18
Так я про это ничего не говорил, я только заметил, что в первом посте спрашивалось про другую замену.
Цитата Сообщение от Somebody Посмотреть сообщение
Это так, но в первом посте был вариант с переменной f для суммирования...
Yandex
Объявления
22.02.2016, 11:23     Оптимизация доступа к памяти
Ответ Создать тему
Опции темы

Текущее время: 13:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru