Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
maxm
63 / 35 / 25
Регистрация: 17.07.2014
Сообщений: 457
1

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

19.02.2016, 10:13. Просмотров 536. Ответов 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
Ответы с готовыми решениями:

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

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

Ошибка доступа к памяти
При нескольких проходах выдает ошибку доступа к памяти int hod_comp(int...

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

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

17
AlexVRud
479 / 191 / 72
Регистрация: 04.07.2014
Сообщений: 538
19.02.2016, 18:33 2
x[i][k] - больше вопрос к этому. если было double **x то расположение строк в памяти не предсказуемо и может свести на нет все твои оптимизации.
0
maxm
63 / 35 / 25
Регистрация: 17.07.2014
Сообщений: 457
19.02.2016, 23:01  [ТС] 3
При чем здесь x[i][k] ?
Я спрашивал, даст ли что то такая замена реально для матрицы большого размера, или нет? И если нет, то почему? Оптимизирует компилятор?
0
avgoor
1041 / 609 / 157
Регистрация: 05.12.2015
Сообщений: 1,732
19.02.2016, 23:17 4
maxm, Во первых, у вас код не для умножения матриц.
Во вторых, да оптимизирует.
В третьих, если нужно произведение плотных матриц - используйте BLAS и не парьтесь (там, ЕМНИП, для оптимизации попадания в кэш 7 вложенных циклов).
0
hoggy
Нарушитель
Эксперт С++
7086 / 3129 / 648
Регистрация: 15.11.2014
Сообщений: 7,209
Завершенные тесты: 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
479 / 191 / 72
Регистрация: 04.07.2014
Сообщений: 538
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
1350 / 401 / 144
Регистрация: 22.10.2014
Сообщений: 863
Завершенные тесты: 2
20.02.2016, 16:33 7
Цитата Сообщение от AlexVRud Посмотреть сообщение
другие могут дать неожиданный прирост
На таких крупных матрицах ваш вариант mul_v4_ArrMatrix избавляетсяя от кэшмиссов, поэтому такой хороший прирост.
В общем случае для научных рассчётов лучше использовать SSE али CUDA.
Если же это 3D'шные матрицы, то алгоритм оставить самый простой, но при этом размеры матрицы определить в компайлтайме -> все циклы развернутся.

Но однозначно хороший пример, да.
0
avgoor
1041 / 609 / 157
Регистрация: 05.12.2015
Сообщений: 1,732
20.02.2016, 16:47 8
Цитата Сообщение от Nosey Посмотреть сообщение
В общем случае для научных рассчётов лучше использовать SSE али CUDA.
Вы правы, но есть одно но: перевести алгоритм на CUDA может быть очень нетривиальной задачей. Повторюсь: для алгоритмов на плотных матрицах лучше всего BLAS (в т.ч. CUBLAS).
1
AlexVRud
479 / 191 / 72
Регистрация: 04.07.2014
Сообщений: 538
21.02.2016, 15:37 9
Цитата Сообщение от maxm Посмотреть сообщение
При чем здесь x[i][k] ?
Замени на x[i*n+k] и сравни время
0
maxm
63 / 35 / 25
Регистрация: 17.07.2014
Сообщений: 457
21.02.2016, 17:23  [ТС] 10
Киньте sample как измерить время нормально, я гуглил, добился только в секундах

И не опасный ли такой прием ?
Цитата Сообщение от AlexVRud Посмотреть сообщение
Замени на x[i*n+k] и сравни время
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
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
479 / 191 / 72
Регистрация: 04.07.2014
Сообщений: 538
21.02.2016, 23:07 12
Цитата Сообщение от maxm Посмотреть сообщение
Киньте sample как измерить время нормально,
А выше то по тексту ты смотрел примеры?
0
return 0
6 / 6 / 1
Регистрация: 21.02.2016
Сообщений: 36
21.02.2016, 23:57 13
Интересно, местные знатоки слышали о сложности алгоритмов
0
maxm
63 / 35 / 25
Регистрация: 17.07.2014
Сообщений: 457
22.02.2016, 00:10  [ТС] 14
Это к чему ты сказал
Цитата Сообщение от return 0 Посмотреть сообщение
Интересно, местные знатоки слышали о сложности алгоритмов
0
hoggy
Нарушитель
Эксперт С++
7086 / 3129 / 648
Регистрация: 15.11.2014
Сообщений: 7,209
Завершенные тесты: 1
22.02.2016, 00:52 15
Цитата Сообщение от Somebody Посмотреть сообщение
Это так, но в первом посте был вариант с переменной f для суммирования, а это не всегда так просто сделать - для этого компилятор должен знать, что x[][] не пересекается с a[][] и b[][].
не вижу такой потребности.
как факт печесенения/непересечение может влиять на эквивалент?
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
22.02.2016, 11:06 16
Цитата Сообщение от hoggy Посмотреть сообщение
как факт печесенения/непересечение может влиять на эквивалент?
Если промежуточные результаты будут в x[i][j], то одним из значений a[i][k] или b[k][j] может оказаться это самое x[i][j], значение которого уже не будет совпадать с исходным.

Добавлено через 1 минуту
Конечно, в таком случае и с f реализация алгоритма будет некорректной, но это уже другая история.
0
hoggy
Нарушитель
Эксперт С++
7086 / 3129 / 648
Регистрация: 15.11.2014
Сообщений: 7,209
Завершенные тесты: 1
22.02.2016, 11:19 17
Цитата Сообщение от Somebody Посмотреть сообщение
Если промежуточные результаты будут в x[i][j], то одним из значений a[i][k] или b[k][j] может оказаться это самое x[i][j], значение которого уже не будет совпадать с исходным.
неужели?

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

приведите пожалуйста пример-иллюстрацию возможной проблемы.
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
22.02.2016, 11:23 18
Так я про это ничего не говорил, я только заметил, что в первом посте спрашивалось про другую замену.
Цитата Сообщение от Somebody Посмотреть сообщение
Это так, но в первом посте был вариант с переменной f для суммирования...
0
22.02.2016, 11:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.02.2016, 11:23

не работает strncmp - нет доступа к памяти
после того, как принимается первое значение symbol выбрасывается ошибка...

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

Ошибка доступа к памяти при выходе из программы
Подскажите почему после завершения работы выдаётся ошибка, что идёт запись...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

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