Про выравнивание данных

Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий
Vict
417
Vict  

Привет. Недавно мы беседовали на тему варавнивания https://www.mql5.com/ru/forum/1111/page2497#comment_12349444.

На эту тему попалась статья https://developer.ibm.com/articles/pa-dalign/. Она хороша тем, что на её основе народ сделал тест https://gist.github.com/koyedele/bf8d32c43989b784b8883dcf59e40f79. Результат примерно такой https://docs.google.com/spreadsheets/d/17tfu_kl4w5Ad8Sqpdh4nl5GEenH8VF6vZY0lh7MDxhI/edit#gid=513137982. Можно заметить, что не просматривается особой связи между приростом производительности и выравниванием. У меня же всё иначе (неверное выравнивание даёт замедление в 1.5-2 раза):

munge8:  0.022813 | 0.022802 | 0.022796 | 0.022812 | 0.022812 | 0.022808 | 0.022814 | 0.022797 | 0.022810 | 0.022792 | 0.022805 | 0.022797 | 0.022811 | 0.022798 |
munge16: 0.011534 | 0.019017 | 0.011536 | 0.019024 | 0.011552 | 0.019007 | 0.011544 | 0.019030 | 0.011551 | 0.019026 | 0.011539 | 0.019056 | 0.011538 | 0.019017 |
munge32: 0.006068 | 0.009124 | 0.009120 | 0.009119 | 0.006053 | 0.009111 | 0.009126 | 0.009111 | 0.006049 | 0.009115 | 0.009105 | 0.009111 | 0.006056 | 0.009119 |
munge64: 0.003696 | 0.006464 | 0.006459 | 0.006459 | 0.006470 | 0.006459 | 0.006477 | 0.006463 | 0.003659 | 0.006460 | 0.006459 | 0.006462 | 0.006450 | 0.006478 |

Ещё один тест:

//c++, компилировать без оптимизации
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

int main()
{
   alignas(64) char buf[100];
   for (int q = 0; q < 66;  q+=1) {
      cout << "offset = " << q << endl;;
      unsigned *s = new(buf+q) unsigned{};
      high_resolution_clock::time_point t1 = high_resolution_clock::now();
      for (unsigned i = 0;  i<1'000'000'000;  ++ i)
         ++ *s;
      high_resolution_clock::time_point t2 = high_resolution_clock::now();
      auto duration = duration_cast<microseconds>( t2 - t1 ).count();
      cout << "time = " << duration << endl;
   }
   return 0;
}
/*
offset = 58
time = 4298315
offset = 59
time = 4302791
offset = 60
time = 4312154
offset = 61
time = 17063499
offset = 62
time = 17546037
offset = 63
time = 17249903
offset = 64
time = 4055626
offset = 65
time = 4033978
*/

У меня кэш-линия == 64 байта. Заметно, что когда данные не влезают целиком в кэш-линию, то это даёт замедление около 4 раз.

Вывод направшивается один - архитектура современных ЦПУ сильно изменилась (у меня весьма старая модель). Я х.з. насколько эта "защита от дурака" повсеместна в современных архитектура и что будет в будущем. Думаю, что как минимум нужно потестить свою железяку и решить заморачиваться или нет.

ЗЫ: но выравнивать это в любом случае хорошая практика, думаю, ведь никто не отменял проблемы с атомарностью, невозможность некоторых инструкций работать с невыровненными данными, да и вопрос - все ли инструкции какого-то современного цпу не дадут разницы при выровненных/невыровненных данных? Из интел мануала

Intel® AVX has relaxed some memory alignment requirements, so now Intel AVX by default allows unaligned access; however, this access may come at a performance slowdown, so the old rule of designing your data to be memory aligned is still good practice (16-byte aligned for 128-bit access and 32-byte aligned for 256-bit access). The main exceptions are the VEX-extended versions of the SSE instructions that explicitly required memory-aligned data: These instructions still require aligned data

ЗЗЫ: может кому будет интересно http://igoro.com/archive/gallery-of-processor-cache-effects/.

Vict
417
Vict  

Кстати, ребята, я понимаю зачем делать выравнивание больше натурального для типа (4 для инта, например), но зачем делать выравнивание менее натурального, может мне кто объяснить? Стандартными плюсовыми способами эта сделать вообще нельзя. Как сказал Ilyas

Именно при добавлении поддержки dotnet библиотек и было добавлено выравнивание полей структур/классов pack.

Если говорить коротко и просто, то работает оно так:

Для каждого из типов (char, short, int, ...) есть свой allignment (1, 2, 4, байта соответственно) по умолчанию.
Для поля структуры выбирается минимальное из двух выравниваний:  по-умолчанию и заданное пользователем (через pack)
Быть может это такой хитрый ход мелкомягких с друзьями - колдуют там с выравниванием в своём шарпе, а производители железок расслабляют требования по выравниванию, и удивительным образом шарп-софт начинает работать значительно быстрее на новом железе. Хомячки в магазин за железом, Intel с мелкомягкими считают баблишко ...
Alexey Navoykov
4413
Alexey Navoykov  
Vict:

ЗЫ: но выравнивать это в любом случае хорошая практика

Хорошая практика для программиста?  А много ли выигрыша у вас останется после включения оптимизации?   Полагаю, лучше доверить эти вопросы компилятору.  Если только вы не занимаетесь сугубо низкоуровневым программированием. Но к тематике данного ресурса это мало относится.  Особенно учитывая, что мы работаем в медленной управляемой среде, то все эти выравнивания - что мёртвому припарки )
Vict
417
Vict  
Alexey Navoykov:
Хорошая практика для программиста?  А много ли выигрыша у вас останется после включения оптимизации?   Полагаю, лучше доверить эти вопросы компилятору.  Если только вы не занимаетесь сугубо низкоуровневым программированием. Но к тематике данного ресурса это мало относится.  Особенно учитывая, что мы работаем в медленной управляемой среде, то все эти выравнивания - что мёртвому припарки )

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

mov    0x70(%rsp),%rax
mov    (%rax),%eax         // читаем из памяти в eax
not    %eax                // делаем побитовую ~
mov    %eax,%edx
mov    0x70(%rsp),%rax
mov    %edx,(%rax)         // пишем обратно в память

с оптимизацией цикл вырождается в:

not    %edx       // побитовая ~
cmp    %ecx,%eax
jne               // уход на следующую итерацию


Надеяться на МКЛ компилятор бесполезно - он выравниванием, в отличии от порядочных компиляторов, не занимается. Ну и про очень медленную среду вы зря, не такая она уж и медленная.

Дело каждого, конечно, просто поделился своим исследованием в этой области. Каждый сам может потестить своё железо и, возможно, решит выравнивать ручками.

fxsaber
14164
fxsaber  
Vict:

Каждый сам может потестить своё железо и, возможно, решит выравнивать ручками. 

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

В MQL чаще всего такие массивы - это MqlRates[] и MqlTick[].


Каким должен быть код, чтобы проверить их скорость?

Vict
417
Vict  
fxsaber:

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

В MQL чаще всего такие массивы - это MqlRates[] и MqlTick[].


Каким должен быть код, чтобы проверить их скорость?

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

Alexey Navoykov
4413
Alexey Navoykov  
Vict:

Надеяться на МКЛ компилятор бесполезно - он выравниванием, в отличии от порядочных компиляторов, не занимается.

Ну почему же, думаю надеяться можно, если дёргать разработчиков по этому поводу, а не плакать в подушку )   Они как-раз таки очень любят улучшать именно быстродействие (чего не скажешь о функционале языка, к сожалению). Хлебом не корми - дай поускорять чего-нибудь )
fxsaber
14164
fxsaber  
Alexey Navoykov:
Хлебом не корми - дай поускорять чего-нибудь )

Не всегда так.

Vict
417
Vict  
Alexey Navoykov:
Ну почему же, думаю надеяться можно, если дёргать разработчиков по этому поводу, а не плакать в подушку )   Они как-раз таки очень любят улучшать именно быстродействие (чего не скажешь о функционале языка, к сожалению). Хлебом не корми - дай поускорять чего-нибудь )

Вряд ли. Они ведь сразу не стали заморачиваться с этим, а сейчас и подавно, когда поменяются размеры структур и поломается какая-то часть вызовов во внешний мир.

Vict
417
Vict  

Код для теста, как обещал (ожидается, что у вас x64):

#define CACHE_LINE_SIZE 64   // ваш размер кэш-линии, скорее всего правильно, но желательно уточнить
#define TEST_CNT 1000000000
#define TRIES_FOR_AVG 5     
             
struct Aligned_double {
   double data[CACHE_LINE_SIZE/8];
};
struct Unaligned_double {
   uint pad; double data[CACHE_LINE_SIZE/8];
};
struct Aligned_ulong {
   ulong data[CACHE_LINE_SIZE/8];
};
struct Unaligned_ulong {
   uint pad; ulong data[CACHE_LINE_SIZE/8];
};
#import "msvcrt.dll"
  ulong memcpy(Aligned_double &, Aligned_double &, long);
  ulong memcpy(Unaligned_double &, Unaligned_double &, long);
  ulong memcpy(Aligned_ulong &, Aligned_ulong &, long);
  ulong memcpy(Unaligned_ulong &, Unaligned_ulong &, long);
#import
#define getaddr(x) memcpy(x, x, 0)

template <typename T>
ulong test(T &t) {
   uint index = uint(CACHE_LINE_SIZE - getaddr(t) % CACHE_LINE_SIZE) / 8 - 1;
   ulong time_1 = GetMicrosecondCount();
   for (ulong i = 0;  i < TEST_CNT;  ++ i)
      ++ t.data[index];
   return GetMicrosecondCount() - time_1;
}

template <typename T>
ulong test_avg(T &t) {
   ulong time_sum = 0;
   for (uint i = 0;  i < TRIES_FOR_AVG;  ++ i)
      time_sum += test(t);
   return time_sum / TRIES_FOR_AVG;
}

void OnStart()
{
#define RUN_TEST(T) {               \
   T t;                             \
   if (getaddr(t) % 8  != 0) {      \
      Alert("error, exit");         \
      return;                       \
   }                                \
   Alert(test_avg(t), " us - ", #T);\
}

   RUN_TEST(Aligned_double);
   RUN_TEST(Unaligned_double);
   RUN_TEST(Aligned_ulong);
   RUN_TEST(Unaligned_ulong);
}

1. Перед компиляцией отключить оптимизацию https://www.mql5.com/ru/forum/165399#comment_3968004

2. Будет выполнено TRIES_FOR_RUN тестов для выровненного/невыровненного ulong/double, в каждом тесте TEST_CNT инкрементов. Из TRIES_FOR_RUN серии будет напечатано среднее время в микросекундах.

3. Каких-то чудес ждать не стоит, думаю. Скорее всего возможности имеются лишь среди старого железа.


Мои результаты (можно заметить, что время выровненного и невыровненного тестов отличаются в несколько раз):

6651080 us - Aligned_double
20090289 us - Unaligned_double
7018687 us - Aligned_ulong
18373733 us - Unaligned_ulong

Железо:

Model name:              Intel(R) Core(TM)2 Duo CPU     P7350  @ 2.00GHz


ЗЫ: если кто тестит, то неплохо пришпиливать свои результаты сюда.

Dmitry Fedoseev
53994
Dmitry Fedoseev  

Vict:

///

ЗЫ: если кто тестит, то неплохо пришпиливать свои результаты сюда.


Вот, пришпиливаю: 


1

123
Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий