Сравнение скорости Resize матриц и динамических массивов структур с динамическим массивом

Новый комментарий
 
До появления матриц создание их аналог делался через  динамический массив структур с динамическим массивом:
struct dar{double d[];};
dar d[];
И обоим измерениям можно в процессе работы изменять размер:
ArrayResize(a,rows);
ArrayResize(a[row].d,cols);

Обращение к ним только непривычное, не d[r][c], a d[r].d[c].

C появлением матриц обращение к элементам стало привычным, как в других ЯП d[r][c].
Судя по описанию, вся матрица помещается в один блок в памяти (как одномерный массив).

Часто заранее не знаешь, сколько строк и столбцов будет в матрице, поэтому нужно делать Resize по мере необходимости. Обычно число столбцов становится известным после заполнения первой строки, дальше оно не меняется. А вот число строк неизвестно. При оптимизации в зависимости от выбранных параметров оно может отличаться в сотни/тысячи раз.

Сравним скорость выполнения resize. Советник:

input int rows_=1000;
input int cols_=1000;
input bool matrix_arr=false;
input int rows_reserv=0;

input int repeats=10;

struct dar{double d[];};
dar d[];
matrix m;

void resizeDar(dar &a[], int rows, int prew_rows, int cols){
   ArrayResize(a,rows,rows_reserv);
   for(int r=prew_rows;r<rows;r++){
      ArrayResize(a[r].d,cols);
   }
}
void OnInit(){
   int prew_rows=0;
   for(int r=0;r<rows_;r++){
      if(matrix_arr){m.Resize(r, cols_, rows_reserv*cols_);}
      else{resizeDar(d, r,prew_rows, cols_); prew_rows=r; }
   }
}

Переключая matrix_arr будем переключаться с матриц на массивы структур.

Самый оптимальный вариант сравнения скорости - оптимизация одним потоком (откл. все агенты, кроме первого) по параметру repeats, который ни на что не влияет в коде.



Сравним скорость Resize для 1000 столбцов и 2000, 10000 и 100000 строк:

rows=2000 cols=1000 rows_reserv=0
arr str
pass 0 returned result 1000000000.00 in 0:00:00.935
pass 1 returned result 1000000000.00 in 0:00:00.946
pass 2 returned result 1000000000.00 in 0:00:00.931
pass 3 returned result 1000000000.00 in 0:00:00.939
pass 4 returned result 1000000000.00 in 0:00:00.913
pass 5 returned result 1000000000.00 in 0:00:00.914
pass 6 returned result 1000000000.00 in 0:00:00.913
pass 7 returned result 1000000000.00 in 0:00:00.924
pass 8 returned result 1000000000.00 in 0:00:00.911
pass 9 returned result 1000000000.00 in 0:00:00.915
pass 10 returned result 1000000000.00 in 0:00:00.930
optimization finished, total passes 11
optimization done in 0 minutes 10 seconds
shortest pass 0:00:00.911, longest pass 0:00:00.946, average pass 0:00:00.924

matrix
EURUSD: ticks synchronized already [43 bytes]
pass 0 returned result 1000000000.00 in 0:00:11.146
pass 1 returned result 1000000000.00 in 0:00:09.709
pass 2 returned result 1000000000.00 in 0:00:09.702
pass 3 returned result 1000000000.00 in 0:00:09.717
pass 4 returned result 1000000000.00 in 0:00:09.728
pass 5 returned result 1000000000.00 in 0:00:09.755
pass 6 returned result 1000000000.00 in 0:00:09.740
pass 7 returned result 1000000000.00 in 0:00:09.728
pass 8 returned result 1000000000.00 in 0:00:09.736
pass 9 returned result 1000000000.00 in 0:00:09.754
pass 10 returned result 1000000000.00 in 0:00:09.742
optimization finished, total passes 11
optimization done in 1 minutes 49 seconds
shortest pass 0:00:09.702, longest pass 0:00:11.146, average pass 0:00:09.859


rows=10000 cols=1000 rows_reserv=0
ar
pass 0 returned result 1000000000.00 in 0:00:02.057
pass 1 returned result 1000000000.00 in 0:00:02.024
pass 2 returned result 1000000000.00 in 0:00:02.016
pass 3 returned result 1000000000.00 in 0:00:02.099
pass 4 returned result 1000000000.00 in 0:00:02.012
pass 5 returned result 1000000000.00 in 0:00:02.022
pass 6 returned result 1000000000.00 in 0:00:02.028
pass 7 returned result 1000000000.00 in 0:00:02.020
pass 8 returned result 1000000000.00 in 0:00:02.072
pass 9 returned result 1000000000.00 in 0:00:02.145
pass 10 returned result 1000000000.00 in 0:00:02.076
optimization finished, total passes 11
optimization done in 0 minutes 22 seconds
shortest pass 0:00:02.012, longest pass 0:00:02.145, average pass 0:00:02.051

matrix
pass 0 returned result 1000000000.00 in 0:04:10.468
pass 1 returned result 1000000000.00 in 0:04:08.391
дальше - не стал ждать

Для 2000 на 1000 массивы изменяют размер  за 0,9 сек, матрицы за 9,7 сек. Разница в 10 раз
Для 10000 на 1000 массивы изменяют размер  за 2 сек, матрицы за 4 мин 8 сек. Разница в 124 раза.

Добавим резервирование памяти через 3-й параметр. Резервировать будем по 100 строк. Массивам добавляем резерв добавляем только когда меняем размер основного массива. Матрице резерв умножим на число столбцов, чтобы тесты были эквивалентными.

Сравниваем скорость:

rows=10 000 cols=1000 rows_reserv=100
ar
pass 0 returned result 1000000000.00 in 0:00:02.268
pass 1 returned result 1000000000.00 in 0:00:00.936
pass 2 returned result 1000000000.00 in 0:00:00.934
pass 3 returned result 1000000000.00 in 0:00:00.930
pass 4 returned result 1000000000.00 in 0:00:00.928
pass 5 returned result 1000000000.00 in 0:00:00.929
pass 6 returned result 1000000000.00 in 0:00:00.929
pass 7 returned result 1000000000.00 in 0:00:00.928
pass 8 returned result 1000000000.00 in 0:00:00.922
pass 9 returned result 1000000000.00 in 0:00:00.932
pass 10 returned result 1000000000.00 in 0:00:00.935
optimization finished, total passes 11
optimization done in 1 minutes 01 seconds
shortest pass 0:00:00.922, longest pass 0:00:02.268, average pass 0:00:01.051

matrix
pass 0 returned result 1000000000.00 in 0:00:03.334
pass 1 returned result 1000000000.00 in 0:00:03.296
pass 2 returned result 1000000000.00 in 0:00:03.258
pass 3 returned result 1000000000.00 in 0:00:03.265
pass 4 returned result 1000000000.00 in 0:00:03.285
pass 5 returned result 1000000000.00 in 0:00:03.300
pass 6 returned result 1000000000.00 in 0:00:03.274
pass 7 returned result 1000000000.00 in 0:00:03.264
pass 8 returned result 1000000000.00 in 0:00:03.271
pass 9 returned result 1000000000.00 in 0:00:03.272
pass 10 returned result 1000000000.00 in 0:00:03.258
optimization finished, total passes 11
optimization done in 0 minutes 36 seconds
shortest pass 0:00:03.258, longest pass 0:00:03.334, average pass 0:00:03.279

rows=100 000 cols=1000 rows_reserv=100
ar
pass 0 returned result 1000000000.00 in 0:00:03.566
pass 1 returned result 1000000000.00 in 0:00:02.213
pass 2 returned result 1000000000.00 in 0:00:02.199
pass 3 returned result 1000000000.00 in 0:00:02.202
pass 4 returned result 1000000000.00 in 0:00:02.205
pass 5 returned result 1000000000.00 in 0:00:02.197
pass 6 returned result 1000000000.00 in 0:00:02.200
pass 7 returned result 1000000000.00 in 0:00:02.207
pass 8 returned result 1000000000.00 in 0:00:02.199
pass 9 returned result 1000000000.00 in 0:00:02.193
pass 10 returned result 1000000000.00 in 0:00:02.215
optimization finished, total passes 11
optimization done in 0 minutes 26 seconds
shortest pass 0:00:02.193, longest pass 0:00:03.566, average pass 0:00:02.326

matrix
pass 0 returned result 1000000000.00 in 0:04:00.677
дальше - не стал ждать

Резерв помог, оба варианта стали быстрее.

Для 10 000 на 1000 массивы изменяют размер  за 0,9 сек, матрицы за 3,2 сек. Разница в 3 раза
Для 100 000 на 1000 массивы изменяют размер  за 2,2 сек, матрицы за 4 мин. Разница в 110 раз.

Полагаю столь существенная разница из за того, что массив структур не хранит сами структуры, а адреса на них (или адреса на массив в их составе). Т.е при добавлении новой строки создается массив размером в число столбцов в любой свободной области памяти, где есть для нее место.
При увеличении  числа строк в мартице, которая идет одним блоком памяти, в ранее выбранной области памяти может не хватить свободного места в этот момент и появляется замедление - нужно занять новую область памяти, где есть требуемый размер и в нее копируется матрица из старого места. И это может происходить много раз, когда памяти в выбранном месте будет не хватать.
В общем то причина тормозов понятна.


На С++ аналогичную матрицу (с привычным доступом d[r][c] )  можно получить:

a = new double* [rows];  for (int i = 0; i < rows; i++) { a[i] = new double[cols]; }

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

Жаль что MQ не пошли таким же путем, возможно работа с массивом массивов была бы быстрее, чем с единым блоком данных.

Я уже думаю о возврате к массивам структур из за существенной разницы в скорости. Непривычность всего лишь в доступе d[r].d[c].
Так же пока не сделано сохранение матриц в файл. Полагаю скопировать 1Гг памяти одним блоком в разы быстрее, чем 100 млн раз копировать поэлементно. Это второй тормоз в работе с матрицами.
Думаю старый вариант с дин. массивом структур в которой дин. массив будет быстрее, т.к. массив в структуре можно целиком в файл скинуть rows число раз.

Документация по MQL5: Основы языка / Типы данных / Объект динамического массива
Документация по MQL5: Основы языка / Типы данных / Объект динамического массива
  • www.mql5.com
Объект динамического массива - Типы данных - Основы языка - Справочник MQL5 - Справочник по языку алгоритмического/автоматического трейдинга для MetaTrader 5
 
Forester:

Судя по описанию, вся матрица помещается в один блок в памяти (как одномерный массив).

Поэтому бесплатный такой Resize:  Cols1xRows1 =  Cols2xRows2 = ... Чаще всего это преобразование матрица<->вектор.

Я уже думаю о возврате к массивам структур из за существенной разницы в скорости.

Заполнить через массив структур, а затем скопировать (кратковременное двойное потребление памяти) данные в matrix, работая уже с ней.

Полезное исследование, спасибо.

 
fxsaber #:

Заполнить через массив структур, а затем скопировать (кратковременное двойное потребление памяти) данные в matrix, работая уже с ней.

Кроме заполнения и сохранения в файл мне пока больше ничего не нужно. И там и там матрицы проигрывают.

 
fxsaber #:

Поэтому бесплатный такой Resize:  Cols1xRows1 =  Cols2xRows2 = ... Чаще всего это преобразование матрица<->вектор.

Заполнить через массив структур, а затем скопировать (кратковременное двойное потребление памяти) данные в matrix, работая уже с ней.

Полезное исследование, спасибо.

А как то можно вместо обращения d[r].d[c] сделать d[r][c] для массивов структур (и чтение и запись)?  Макросы или еще что-то? В таких вещах я не разбираюсь.

 
Forester #:

А как то можно вместо обращения d[r].d[c] сделать d[r][c] для массивов структур (и чтение и запись)?  Макросы или еще что-то? В таких вещах я не разбираюсь.

Если перейти на классы, то несложно чтение сделать. Запись - тоже возможно. Одновременно - нет.

Однако, можно d[a[r][c]] и d[b[r][c]] для чтения и записи. Но стоит ли...

 
fxsaber #:

Если перейти на классы, то несложно чтение сделать. Запись - тоже возможно. Одновременно - нет.

Теперь ясно, почему в старом алглибе чтение было через [][], а запись через Set().
Сейчас Алглиб уже на матрицы переделали.

 
Forester #:

Теперь ясно, почему в старом алглибе чтение было через [][], а запись через Set().
Сейчас Алглиб уже на матрицы переделали.

Интересная ветка, да только все началось и кончилось на ресайзах. А эти операции довольно редкие. Я обычно заказываю статический массив с запасом. Один форумчанин (ник не помню (: ) писал, что, по его тестам, они работают быстрее динамических. Было бы интересно протестировать векторы, матрицы и массивы на арифметических операциях.

Я сейчас разрабатываю прототип EA на Matlab. А там как раз все операции все операции матричные. Даже умножение двух переменных типа double рассматривается, как произведение матриц :). 
Задача первого этапа сделать на Matlab нативную DLL с возможностью использовать из ЕА МТ5. Пока компилирую ее в стиле С, возможно перейду на стили С++ и/или C#. Ну, а в финале придется переписывать все матлабовское на MQL5. Так что тема реального быстродействия очень интересна.  

Новый комментарий
Причина обращения: