Особенности языка mql5, тонкости и приёмы работы - страница 117

 

Вот родился у меня такой вариант:

int log2_(ulong n)
{
  if (n==0) return -1;

  #define M(n, i, base, S) ( n >= (ulong(1)<<(i)) ? S(n, i+base/2) : S(n, i-(base+1)/2) )

  #define S_0(n, i)  i
  #define S_1(n, i)  M(n, i, 1, S_0)
  #define S_2(n, i)  M(n, i, 2, S_1)
  #define S_4(n, i)  M(n, i, 4, S_2)
  #define S_8(n, i)  M(n, i, 8, S_4)
  #define S_16(n, i) M(n, i, 16, S_8)
  #define S(n)       M(n, 32, 32, S_16)

  return S(n); 
}

По идее, это самый быстрый из всех возможных.  Все вычисления производятся с константами, поэтому рассчитываются при компиляции.  Итого, всё сводится лишь к 6 последовательным сравнениям, и ничего более.  Однако, этот вариант у меня работает медленнее, чем предыдущий.  Не могу понять, в чём причина.

 
Alexey Navoykov:

Вот родился у меня такой вариант:

По идее, это самый быстрый из всех возможных.  Все вычисления производятся с константами, поэтому рассчитываются при компиляции.  Итого, всё сводится лишь к 6 последовательным сравнениям, и ничего более.  Однако, этот вариант у меня работает медленнее, чем предыдущий.  Не могу понять, в чём причина.

Деление на два замедляет ? Попробовать заменить сдвигом ?  Подозрение, что вычисляемые константы - надо вычислять сразу (в этом случае - и сдвиг в дефайне - также надо заменить константой).

Кроме того - "вопросик" - как я знаю, это довольно спорный оператор, когда-то, двадцать лет назад проверяли на С++, иногда "вопросик" генерирует более длинный код, чем обычный оператор if. Может и здесь так ?

И, я бы сделал код возврата uint - вдруг там какие-то проверки идут при преобразовании знаковых и беззнаковых величин ?

Пока нет возможности поэксперементировать самому - процессор загружен под завязку... Даже текст набирается "с пробуксовками"...

 
Georgiy Merts:

Деление на два замедляет ? Попробовать заменить сдвигом ?  Подозрение, что вычисляемые константы - надо вычислять сразу (в этом случае - и сдвиг в дефайне - также надо заменить константой). 

Кроме того - "вопросик" - как я знаю, это довольно спорный оператор ...

Замена деления сдвигом не влияет.  Я подозреваю, что получающееся выражение слишком длинное, поэтому компилятор его не оптимизировал до конца.

Однако это я проводил тесты при Optimize=0.  А при включении оптимизации всё встало на свои места: второй вариант быстрее примерно в полтора раза. Бинго!

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

 
Alexey Navoykov:

Вот родился у меня такой вариант:

По идее, это самый быстрый из всех возможных.  Все вычисления производятся с константами, поэтому рассчитываются при компиляции.  Итого, всё сводится лишь к 6 последовательным сравнениям, и ничего более.  Однако, этот вариант у меня работает медленнее, чем предыдущий.  Не могу понять, в чём причина.

Все верно - Ваш вариант самый быстрый.

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

Ведь это логично - какой смысл? Это как в квантовой суперпозиции. Зачен существовать луне, если на нее никто не смотрит. "Неужели Луна существует только потому, что на нее смотрит мышь?" (Альберт Эйнштейн). :))

Поэтому такой вариант теста с вычислением контрольной суммы и печати её будет правильнее:

#property strict
#define   test(M,S,EX)        {long sum=0; uint nn=(uint)pow(10,M); ulong mss=GetMicrosecondCount(); for(uint t12=1;t12<=nn;t12++){EX;sum+=(long)n1;} \
                                Print(S+": loops="+(string)nn+" μs="+string(GetMicrosecondCount()-mss)+" Контрольная сумма="+string(sum));}

int log2(ulong n){
  if (n==0) return -1;
  #define S(k) if (n >= (ulong(1)<<k)) { i += k;  n >>= k; }
  int i=0;  S(32);  S(16);  S(8);  S(4);  S(2);  S(1);  return i;
  #undef S}


static const uint ulLogTable[64] = {
0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,
51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,
57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };

uint _FastLog2(ulong ulInput){
   ulInput |= ulInput >> 1;
   ulInput |= ulInput >> 2;
   ulInput |= ulInput >> 4;
   ulInput |= ulInput >> 8;
   ulInput |= ulInput >> 16;
   ulInput |= ulInput >> 32;  
   return(ulLogTable[(uint)((ulInput * 0x03f6eaf2cd271461) >> 58)]);};
   
int log2_(ulong n)
{
  if (n==0) return -1;

  #define M(n, i, base, S) ( n >= (ulong(1)<<(i)) ? S(n, i+base/2) : S(n, i-(base+1)/2) )

  #define S_0(n, i)  i
  #define S_1(n, i)  M(n, i, 1, S_0)
  #define S_2(n, i)  M(n, i, 2, S_1)
  #define S_4(n, i)  M(n, i, 4, S_2)
  #define S_8(n, i)  M(n, i, 8, S_4)
  #define S_16(n, i) M(n, i, 16, S_8)
  #define S(n)       M(n, 32, 32, S_16)

  return S(n); 
}

void OnStart(){
  srand(GetTickCount());
  ulong n1;
  test(8,"MathLog",n1=ulong(MathLog((double)t12)/MathLog(2.0)))
  test(8,"log2",n1=log2(t12))
  test(8,"log2_",n1=log2_(t12))
  test(8,"_FastLog2",n1=_FastLog2(t12))}

Результат:

2019.01.05 02:30:03.681 TestLog (.BrentCrud,H4) MathLog:   loops=100000000 μs=805196 Контрольная сумма=2465782300
2019.01.05 02:30:04.092 TestLog (.BrentCrud,H4) log2:      loops=100000000 μs=410657 Контрольная сумма=2465782300
2019.01.05 02:30:04.234 TestLog (.BrentCrud,H4) log2_:     loops=100000000 μs=141975 Контрольная сумма=2465782300
2019.01.05 02:30:04.432 TestLog (.BrentCrud,H4) _FastLog2: loops=100000000 μs=198015 Контрольная сумма=2465782300
А второе место все же _FastLog2, а не log2 :))
 
Nikolai Semko:

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

Ведь это логично - какой смысл? Это как в квантовой суперпозиции. Зачен существовать луне, если на нее никто не смотрит. "Неужели Луна существует только потому, что на нее смотрит мышь?" (Альберт Эйнштейн). :))

Поэтому такой вариант теста с вычислением контрольной суммы и печати её будет правильнее:

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

Кстати, зачем у вас srand в коде?  Я, увидев его, сначала и подумал, что у вас используется рандом, но по факту - нет.

Вот мой код:

void OnStart()
{
  Print("OnStart");
  srand(GetTickCount());
  int count= 50000000;
   
  #define TEST(func) { \ 
    ulong sum=0; \
    ulong mcscount= GetMicrosecondCount(); \
    for (int i=0; i<count; i++) \
      sum += func(rand() | rand()<<15); \
    Print("Result "+#func+":  sum=",sum,"  time=",(GetMicrosecondCount()-mcscount)/1000," ms"); \    
  }
  
  TEST(log2);
  TEST(log2_);
}
 
Alexey Navoykov:

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

Кстати, зачем у вас srand в коде?  Я, увидев его, сначала и подумал, что у вас используется рандом, но по факту - нет.

Вот мой код:

код не мой. Я лишь его подправил и выкинул rand, чтобы проверить одинаковость контрольных сумм и убрать из цикла относительно затратные функции rand, а srand просто забыл выкинуть.

Возвращаю rand. Вы правы - компилятор действительно оптимизирует цикл суммы логарифмов из последовательных значений. Хотя я удивлен. Не понимаю, как он это делает. Возможно, что-то мы не учитываем.

#property strict
#define   test(M,S,EX)        {srand(45); long sum=0; uint nn=(uint)pow(10,M); ulong mss=GetMicrosecondCount(); for(uint t12=1;t12<=nn;t12++){EX;sum+=(long)n1;} \
                                Print(S+": loops="+(string)nn+" μs="+string(GetMicrosecondCount()-mss)+" Контрольная сумма="+string(sum));}

int log2(ulong n){
  if (n==0) return -1;
  #define S(k) if (n >= (ulong(1)<<k)) { i += k;  n >>= k; }
  int i=0;  S(32);  S(16);  S(8);  S(4);  S(2);  S(1);  return i;
  #undef S}


static const uint ulLogTable[64] = {
0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,
51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,
57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };

uint _FastLog2(ulong ulInput){
   ulInput |= ulInput >> 1;
   ulInput |= ulInput >> 2;
   ulInput |= ulInput >> 4;
   ulInput |= ulInput >> 8;
   ulInput |= ulInput >> 16;
   ulInput |= ulInput >> 32;  
   return(ulLogTable[(uint)((ulInput * 0x03f6eaf2cd271461) >> 58)]);};
   
int log2_(ulong n)
{
  if (n==0) return -1;

  #define M(n, i, base, S) ( n >= (ulong(1)<<(i)) ? S(n, i+base/2) : S(n, i-(base+1)/2) )

  #define S_0(n, i)  i
  #define S_1(n, i)  M(n, i, 1, S_0)
  #define S_2(n, i)  M(n, i, 2, S_1)
  #define S_4(n, i)  M(n, i, 4, S_2)
  #define S_8(n, i)  M(n, i, 8, S_4)
  #define S_16(n, i) M(n, i, 16, S_8)
  #define S(n)       M(n, 32, 32, S_16)

  return S(n); 
}

void OnStart(){
  ulong n1,n;
  test(8,"MathLog",n=(rand()+1)*(rand()+1);n1=ulong(MathLog((double)n)/MathLog(2.0)))
  test(8,"log2",n=(rand()+1)*(rand()+1);n1=log2(n))
  test(8,"log2_",n=(rand()+1)*(rand()+1);n1=log2_(n))
  test(8,"_FastLog2",n=(rand()+1)*(rand()+1);n1=_FastLog2(n))}

Результат:

2019.01.05 04:10:25.808 TestLog (EURUSD,H1)     MathLog:   loops=100000000 μs=1168737 Контрольная сумма=2661391201
2019.01.05 04:10:26.474 TestLog (EURUSD,H1)     log2:      loops=100000000 μs=665631  Контрольная сумма=2661391201
2019.01.05 04:10:27.315 TestLog (EURUSD,H1)     log2_:     loops=100000000 μs=841299  Контрольная сумма=2661391201
2019.01.05 04:10:27.694 TestLog (EURUSD,H1)    _FastLog2:  loops=100000000 μs=378627  Контрольная сумма=2661391201
   

Текущий победитель _FastLog2

 
Nikolai Semko:

Результат:

Текущий победитель _FastLog2

Интересно, каким образом у вас получилась везде одинаковая контрольная сумма, если значения рандомные.

 
Alexey Navoykov:

Интересно, каким образом у вас получилась везде одинаковая контрольная сумма, если значения рандомные.

srand(45) для всех функций

просто сначала тоже так сделал, но получил разные контрольные суммы, т.к. не учел что rand()*rand() может быть 0, а это ломает контрольную сумму. Сейчас добавил единицу, чтобы уйти от нуля.

 
Nikolai Semko:

srand(45) для всех функций

просто сначала тоже так сделал, но получил разные контрольные суммы, т.к. не учел что rand()*rand() может быть 0, а это ломает контрольную сумму. Сейчас добавил единицу, чтобы уйти от нуля.

А зачем вам одинаковая контрольная сумма, если речь идёт конкретно о замере скорости?  Суть суммы в этом случае - просто не дать компилятору вырезать код, вот и всё.  А делая srand(45), вы опять-таки позволяете оптимизировать тест.

Кстати, по поводу нуля.  В FastLog2 нет проверки на нуль, это соответственно и фору ему даёт. Но он всё-равно в полтора-два раза медленнее, чем log2, если тестировать корректно )

 
Alexey Navoykov:
А зачем вам одинаковая контрольная сумма, если речь идёт конкретно о замере скорости?  Суть суммы в этом случае - просто не дать компилятору вырезать код, вот и всё.  А делая srand(45), вы опять-таки позволяете оптимизировать тест.

Здесь Вы переоцениваете возможности компилятора. Уберите srand(45) - контрольные суммы станут разными, но результат скорости сохраниться.

Тем более я руководствовался тем, чтобы вычисления были одинаковыми для чистоты эксперимента, т.к. не вдавался в подробности всех функций. Иногда значение параметра функции могут влиять на время её выполнения.  

Тем более заодно проверить правильность алгоритмов.