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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
maxm
 Аватар для maxm
38 / 25 / 6
Регистрация: 17.07.2014
Сообщений: 378
#1

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

19.02.2016, 10:13. Просмотров 384. Ответов 17
Метки нет (Все метки)

Интересует вопрос. При умножении матриц даст ли результат такая замена или компилятор видит что в цыкле адрес ячейки тот же и сам оптимизирует? И какой компилятор так сделает а какой нет?

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 минуты
Речь идет о времени доступа к элементу х
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.02.2016, 10:13     Оптимизация доступа к памяти
Посмотрите здесь:

Оптимизация C++
почему обявление уровня доступа является нежелательным способом предявления доступа, в отличии от использования пространстрва имён? C++
C++ Выделить в памяти 1024 ячейки по 8 байт и вывести их адреса(МИНИ менеджер памяти))
C++ Распределение памяти. Динамическое выделение памяти
резервирование памяти/освобождение памяти для трехмерного массива C++
C++ Оптимизация памяти
C++ Линейный список прямого доступа в связанной памяти
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AlexVRud
440 / 150 / 38
Регистрация: 04.07.2014
Сообщений: 424
19.02.2016, 18:33     Оптимизация доступа к памяти #2
x[i][k] - больше вопрос к этому. если было double **x то расположение строк в памяти не предсказуемо и может свести на нет все твои оптимизации.
maxm
 Аватар для maxm
38 / 25 / 6
Регистрация: 17.07.2014
Сообщений: 378
19.02.2016, 23:01  [ТС]     Оптимизация доступа к памяти #3
При чем здесь x[i][k] ?
Я спрашивал, даст ли что то такая замена реально для матрицы большого размера, или нет? И если нет, то почему? Оптимизирует компилятор?
avgoor
 Аватар для avgoor
788 / 430 / 93
Регистрация: 05.12.2015
Сообщений: 1,272
19.02.2016, 23:17     Оптимизация доступа к памяти #4
maxm, Во первых, у вас код не для умножения матриц.
Во вторых, да оптимизирует.
В третьих, если нужно произведение плотных матриц - используйте BLAS и не парьтесь (там, ЕМНИП, для оптимизации попадания в кэш 7 вложенных циклов).
hoggy
5730 / 2312 / 419
Регистрация: 15.11.2014
Сообщений: 5,163
Завершенные тесты: 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
440 / 150 / 38
Регистрация: 04.07.2014
Сообщений: 424
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
1204 / 371 / 106
Регистрация: 22.10.2014
Сообщений: 813
Завершенные тесты: 2
20.02.2016, 16:33     Оптимизация доступа к памяти #7
Цитата Сообщение от AlexVRud Посмотреть сообщение
другие могут дать неожиданный прирост
На таких крупных матрицах ваш вариант mul_v4_ArrMatrix избавляетсяя от кэшмиссов, поэтому такой хороший прирост.
В общем случае для научных рассчётов лучше использовать SSE али CUDA.
Если же это 3D'шные матрицы, то алгоритм оставить самый простой, но при этом размеры матрицы определить в компайлтайме -> все циклы развернутся.

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

И не опасный ли такой прием ?
Цитата Сообщение от AlexVRud Посмотреть сообщение
Замени на x[i*n+k] и сравни время
Somebody
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 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
440 / 150 / 38
Регистрация: 04.07.2014
Сообщений: 424
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
38 / 25 / 6
Регистрация: 17.07.2014
Сообщений: 378
22.02.2016, 00:10  [ТС]     Оптимизация доступа к памяти #14
Это к чему ты сказал
Цитата Сообщение от return 0 Посмотреть сообщение
Интересно, местные знатоки слышали о сложности алгоритмов
hoggy
5730 / 2312 / 419
Регистрация: 15.11.2014
Сообщений: 5,163
Завершенные тесты: 1
22.02.2016, 00:52     Оптимизация доступа к памяти #15
Цитата Сообщение от Somebody Посмотреть сообщение
Это так, но в первом посте был вариант с переменной f для суммирования, а это не всегда так просто сделать - для этого компилятор должен знать, что x[][] не пересекается с a[][] и b[][].
не вижу такой потребности.
как факт печесенения/непересечение может влиять на эквивалент?
Somebody
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 1
22.02.2016, 11:06     Оптимизация доступа к памяти #16
Цитата Сообщение от hoggy Посмотреть сообщение
как факт печесенения/непересечение может влиять на эквивалент?
Если промежуточные результаты будут в x[i][j], то одним из значений a[i][k] или b[k][j] может оказаться это самое x[i][j], значение которого уже не будет совпадать с исходным.

Добавлено через 1 минуту
Конечно, в таком случае и с f реализация алгоритма будет некорректной, но это уже другая история.
hoggy
5730 / 2312 / 419
Регистрация: 15.11.2014
Сообщений: 5,163
Завершенные тесты: 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++
C++ Оптимизация программы по памяти
не работает strncmp - нет доступа к памяти C++
C++ Ошибка доступа к памяти при выходе из программы
оптимизация C++

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

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

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