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

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

Войти
Регистрация
Восстановить пароль
 
 
maxm
61 / 33 / 8
Регистрация: 17.07.2014
Сообщений: 441
#1

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

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

Оптимизация памяти - C++
Доброго времени суток. У меня есть класс(код показывать не буду, он не нужен), в приватном поле есть переменная типа int *, то есть класс...

Оптимизация программы по памяти - C++
Здравствуйте, дорогие коллеги! Прошу вашей помощи. Кто чем поможет. Есть минимальная программа рекомендательной системы( код ниже...

Синхронизация доступа к разделяемой памяти - C++
Когда потоки являются дочерними по отношению к процессу тут все просто - объект мьютекса находится в общей памяти и используя этот объект...

Нет доступа к ячейке памяти?! - C++
День всем добрый. Я понимаю, неприлично как-то по пять раз на день форумчан беспокоить, но тут исключительный случай! Короче,...

не работает strncmp - нет доступа к памяти - C++
после того, как принимается первое значение symbol выбрасывается ошибка Unhandled exception at 0x5c6cf7e0 in lala 3 1.exe: 0xC0000005:...

Ошибка доступа к памяти при выходе из программы - C++
Подскажите почему после завершения работы выдаётся ошибка, что идёт запись данных в память? вроде всё очистил #include &lt;iostream&gt; ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
AlexVRud
442 / 152 / 38
Регистрация: 04.07.2014
Сообщений: 431
19.02.2016, 18:33 #2
x[i][k] - больше вопрос к этому. если было double **x то расположение строк в памяти не предсказуемо и может свести на нет все твои оптимизации.
0
maxm
61 / 33 / 8
Регистрация: 17.07.2014
Сообщений: 441
19.02.2016, 23:01  [ТС] #3
При чем здесь x[i][k] ?
Я спрашивал, даст ли что то такая замена реально для матрицы большого размера, или нет? И если нет, то почему? Оптимизирует компилятор?
0
avgoor
904 / 539 / 117
Регистрация: 05.12.2015
Сообщений: 1,504
19.02.2016, 23:17 #4
maxm, Во первых, у вас код не для умножения матриц.
Во вторых, да оптимизирует.
В третьих, если нужно произведение плотных матриц - используйте BLAS и не парьтесь (там, ЕМНИП, для оптимизации попадания в кэш 7 вложенных циклов).
0
hoggy
Нарушитель
6578 / 2759 / 476
Регистрация: 15.11.2014
Сообщений: 6,105
Завершенные тесты: 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];
    }
компиляторы уже давным давно научились
оптимизировать промежуточные вычисления.

поэтому, я бы не стал заморачиваться,
и экономить на спичках.
0
AlexVRud
442 / 152 / 38
Регистрация: 04.07.2014
Сообщений: 431
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
1
Nosey
1348 / 399 / 107
Регистрация: 22.10.2014
Сообщений: 861
Завершенные тесты: 2
20.02.2016, 16:33 #7
Цитата Сообщение от AlexVRud Посмотреть сообщение
другие могут дать неожиданный прирост
На таких крупных матрицах ваш вариант mul_v4_ArrMatrix избавляетсяя от кэшмиссов, поэтому такой хороший прирост.
В общем случае для научных рассчётов лучше использовать SSE али CUDA.
Если же это 3D'шные матрицы, то алгоритм оставить самый простой, но при этом размеры матрицы определить в компайлтайме -> все циклы развернутся.

Но однозначно хороший пример, да.
0
avgoor
904 / 539 / 117
Регистрация: 05.12.2015
Сообщений: 1,504
20.02.2016, 16:47 #8
Цитата Сообщение от Nosey Посмотреть сообщение
В общем случае для научных рассчётов лучше использовать SSE али CUDA.
Вы правы, но есть одно но: перевести алгоритм на CUDA может быть очень нетривиальной задачей. Повторюсь: для алгоритмов на плотных матрицах лучше всего BLAS (в т.ч. CUBLAS).
1
AlexVRud
442 / 152 / 38
Регистрация: 04.07.2014
Сообщений: 431
21.02.2016, 15:37 #9
Цитата Сообщение от maxm Посмотреть сообщение
При чем здесь x[i][k] ?
Замени на x[i*n+k] и сравни время
0
maxm
61 / 33 / 8
Регистрация: 17.07.2014
Сообщений: 441
21.02.2016, 17:23  [ТС] #10
Киньте sample как измерить время нормально, я гуглил, добился только в секундах

И не опасный ли такой прием ?
Цитата Сообщение от AlexVRud Посмотреть сообщение
Замени на x[i*n+k] и сравни время
0
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 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[][].
0
AlexVRud
442 / 152 / 38
Регистрация: 04.07.2014
Сообщений: 431
21.02.2016, 23:07 #12
Цитата Сообщение от maxm Посмотреть сообщение
Киньте sample как измерить время нормально,
А выше то по тексту ты смотрел примеры?
0
return 0
5 / 5 / 1
Регистрация: 21.02.2016
Сообщений: 36
21.02.2016, 23:57 #13
Интересно, местные знатоки слышали о сложности алгоритмов
0
maxm
61 / 33 / 8
Регистрация: 17.07.2014
Сообщений: 441
22.02.2016, 00:10  [ТС] #14
Это к чему ты сказал
Цитата Сообщение от return 0 Посмотреть сообщение
Интересно, местные знатоки слышали о сложности алгоритмов
0
hoggy
Нарушитель
6578 / 2759 / 476
Регистрация: 15.11.2014
Сообщений: 6,105
Завершенные тесты: 1
22.02.2016, 00:52 #15
Цитата Сообщение от Somebody Посмотреть сообщение
Это так, но в первом посте был вариант с переменной f для суммирования, а это не всегда так просто сделать - для этого компилятор должен знать, что x[][] не пересекается с a[][] и b[][].
не вижу такой потребности.
как факт печесенения/непересечение может влиять на эквивалент?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.02.2016, 00:52
Привет! Вот еще темы с ответами:

Линейный список прямого доступа в связанной памяти - C++
Здравствуйте!Помогите пожалуйста. Не могу понять как сделать чтобы все заданные элементы не удалялись. Задание: Удалить последний по...

Осуществление доступа к памяти в Windows - C++
Помогите, пожалуйста. Возникла проблема. Нужно каким-то образом добраться до памяти по адресам 0xF000:0x0000 и т.д. Под Дос, я так понимаю,...

почему обявление уровня доступа является нежелательным способом предявления доступа, в отличии от использования пространстрва имён? - C++
почему обявление уровня доступа является нежелательным способом предявления доступа, в отличии от использования пространстрва имён?

Выделить в памяти 1024 ячейки по 8 байт и вывести их адреса(МИНИ менеджер памяти)) - C++
Вот тут появилась такая интересная задача: требуется сделать программу которая управляет 1024 ячейками памяти по 8 байт каждая. т.е. за...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.02.2016, 00:52
Ответ Создать тему
Опции темы

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