4 января 2020 г.

Ускорение за счёт работы с float вместо double

Как-то раз я столкнулся с библиотекой, которая позволяла явно указывать тип обрабатываемых данных. Сначала я подумал, что это нужно только для совместимости с входными данными, но тесты показали значительную разницу в работе с данными double и float.

TL;DR: Если достаточно сокращения времени работы процентов на 30-40 при необходимости следить за точностью вычислений, то можно пробовать.

Конечно, разница очевидна - меньше бит, меньше работы, однако меня сбило с толку то, что double полностью ложится в 64 бита, что на 64-битной системе должно давать какое-то преимущество, либо разница с 32-битным float будет небольшой. Однако оказалось, что всё совсем не так, и двойной размер данных даёт сравнимое падение производительности, по крайней мере в MQL и той библиотеке (Intel DAAL).

С одной стороны, меньший объём данных типа float в пределе может удвоить скорость. А обработка вдвое меньшего числа бит - это ещё один двойной прирост. Итого в пределе - четырёхкратный рост. Но это наивная оценка, не учитывающая вообще никаких внутренних процессов при вычислении разных типов данных. И вряд ли есть алгоритмы, которые полностью состоят лишь из математических операций для исследуемых типов, разве что развернуть все циклы, что компиляторы вряд ли будут делать для больших объёмов данных, где разница между float и double вообще может интересовать.

Разберём три примера. Первый будет только считать, второй будет использовать большие массивы данных, а третий будет делать и то, и другое. Тесты, конечно, почти полностью синтетические (кроме второго), но здесь синтетика как раз и интересует, т.к. необходимо прощупать предел.

Первый пример. Только вычисления

Этот пример будет полностью искусственным. И нацелен он больше на сами вычисления, здесь даже не будет массивов. Сложно придумать реальный пример вычислений, в контексте трейдинга особенно, не требующий массива данных. Чтобы не зависеть от встроенных функций, которые объявлены только для типа double, ограничимся простыми вычислениями на основе четырёх основных действий, вычислим число пи по формуле Валлиса.

template<typename T>
T calc_pi_wallis(int max_iter)
{
    T pi = (T)2.0;
    T one = (T)1.0;
    T two = (T)2.0;

    for (int i = 1; i <= max_iter; i++)
    {
        T n = (T)i;
        pi *= (two * n) * (two * n) / (two * n - one) / (two * n + one);
    }

    return(pi);
}

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

Код теста:

void OnStart()
{
    for (int max_iter = 1; max_iter <= 100000000; max_iter *= 10)
    {
INTERVAL_START(0);
        double pi_dbl = calc_pi_wallis<double>(max_iter);
INTERVAL_STOP(0);

INTERVAL_START(1);
        float  pi_flt = calc_pi_wallis<float>(max_iter);
INTERVAL_STOP(1);

        string max_iter_str = IntegerToString(max_iter, 9);
        Print(VAR(max_iter_str), VAR(pi_dbl), VAR(pi_flt));
    }

INTERVAL_PRINTALL;
}

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

Без оптимизации:
  max_iter_str=        1  pi_dbl=2.666666666666667  pi_flt=2.66667
  max_iter_str=       10  pi_dbl=3.0677038066435  pi_flt=3.0677
  max_iter_str=      100  pi_dbl=3.133787490628166  pi_flt=3.13379
  max_iter_str=     1000  pi_dbl=3.140807746030404  pi_flt=3.1408
  max_iter_str=    10000  pi_dbl=3.141514118681947  pi_flt=3.14138
  max_iter_str=   100000  pi_dbl=3.141584799657206  pi_flt=3.14353
  max_iter_str=  1000000  pi_dbl=3.141591868191791  pi_flt=3.15521
  max_iter_str= 10000000  pi_dbl=3.141592575029863  pi_flt=3.23202
  max_iter_str=100000000  pi_dbl=3.141592658346339  pi_flt=4.00005
Interval #0:  time=1687.621 ms,  count=9,  avg=187.513444 ms  [OnStart, 10]
Interval #1:  time=1251.001 ms,  count=9,  avg=139.000111 ms  [OnStart, 14]

С оптимизацией:
  max_iter_str=        1  pi_dbl=2.666666666666667  pi_flt=2.66667
  max_iter_str=       10  pi_dbl=3.0677038066435  pi_flt=3.0677
  max_iter_str=      100  pi_dbl=3.133787490628166  pi_flt=3.13379
  max_iter_str=     1000  pi_dbl=3.140807746030404  pi_flt=3.1408
  max_iter_str=    10000  pi_dbl=3.141514118681947  pi_flt=3.14138
  max_iter_str=   100000  pi_dbl=3.141584799657206  pi_flt=3.14353
  max_iter_str=  1000000  pi_dbl=3.141591868191791  pi_flt=3.15521
  max_iter_str= 10000000  pi_dbl=3.141592575029863  pi_flt=3.23202
  max_iter_str=100000000  pi_dbl=3.141592658346339  pi_flt=4.00005
Interval #0:  time=1628.138 ms,  count=9,  avg=180.904222 ms  [OnStart, 10]
Interval #1:  time=987.430 ms,  count=9,  avg=109.714444 ms  [OnStart, 14]

Сразу заметна сильная потеря точности для float после большого числа итераций. Подобные проблемы нередки при переходе с double на float, когда вычисления содержат формулы с накоплением (последовательное сложение, умножение). Мои попытки избежать проблем с точностью в этом коде привели к исчезновению разницы в скорости работы, а она изначально есть. Причём оптимизатор компилятора сделал больше для float, чем для double, в итоге дав время исполнения почти на 40% меньше, что близко к желаемым 50% за счёт этой оптимизации.

Итак, польза от перехода на float даже при простых массовых вычислениях вполне может быть. Однако не надо забывать про возможную существенную потерю точности. По возможности, лучше создавать шаблонные функции, чтобы была возможность сравнить результат для double и float хотя бы в некоторые моменты, например при отладке, переходе на другие размеры и типы исходных данных.

Второй пример. Массивы

Пользуясь случаем, приведу пример, который очень близок к тому коду, который используется в некоторых моих индикаторах. Так получилось, что он хорошо подходит для оценки только доступа к данным разных типов.

Возьмём расчёт индикатора Bollinger Bands. Здесь будет использован быстрый алгоритм расчёта стандартного отклонения, и с ним есть одна небольшая проблема при переходе на float. Когда необходимо рассчитать последовательно множество значений, и в индикаторах обычно это так и есть, то за несколько сотен или тысяч баров накапливается заметная ошибка, поэтому аккумуляторам следует оставлять максимальную точность.

Для одного периода и одного бара расчёт может выглядеть так:

// bar: слева направо
template<typename T>
bool calc_bb(int period, double dev, const T &data[], const bar, T ma, T upper, T lower)
{
    double sum = 0.0;
    double sq_sum = 0.0;

    for (int i = 0, shift = bar; i < period; i++, shift--)
    {
        sum += data[shift];
        sq_sum += data[shift] * data[shift];
    }

    ma = T(sum / period);
    double sd = sqrt(sq_sum / period - ma * ma);
    upper = T(ma + sd * dev);
    lower = T(ma - sd * dev);
}

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

#define CTARR const T &
#define CIARR const int &
#define TARR T &

template <typename T>
void BBArrsCULT(
    CTARR price_arr[],
    const int first_bar, const int bar_count,
    CIARR period_arr[], const int period_count,
    CTARR sigma,
    TARR center_arr[], TARR upper_arr[], TARR lower_arr[]
)
{
    double sigma_d = sigma;

    for (int p = 0, res_shift = 0; p < period_count; p++, res_shift += bar_count)
    {
        int period = period_arr[p];

        double sum = 0;
        double sq_sum = 0;
        double mean;

        // сумма для -1-го бара с периодом на 1 меньше
        for (int i = (first_bar - 1) - (period - 1) + 1, end = first_bar - 1; i <= end; i++)
        {
            double price = price_arr[i];
            sum += price;
            sq_sum += price * price;
        }

        // Перебор слева направо
        for (int i = 0, res_i = res_shift; i < bar_count; i++, res_i++)
        {
            int bar = first_bar + i;
            double price = price_arr[bar];

            // добавить значение текущего
            sum += price;
            sq_sum += price * price;

            // окончательный расчёт центра и границ, sma и sd
            mean = sum / period;
            double ds = sigma_d * sqrt(sq_sum / period - mean * mean);
            center_arr[res_i] = T(mean);
            upper_arr[res_i] = T(mean + ds);
            lower_arr[res_i] = T(mean - ds);

            // убрать первое значение диапазона расчёта
            double first_price = price_arr[bar - period + 1];
            sum -= first_price;
            sq_sum -= first_price * first_price;
        }
    }
}

Трюки с определениями типа CTARR здесь нужны для совместимости с C++, где они определены по-другому.

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

Тип T используется лишь для входных данных и результата, промежуточные расчёты выполняются всегда в double. Таким образом, по большей части тестируется не скорость самих вычислений, а скорее доступ к массивам чисел разной точности. Кроме того, в данном случае (алгоритме) было обнаружено, что ошибка накопления здесь критична, и double использовать обязательно. Индикаторы, построенные по грубым расчётам слегка, но заметно, отличаются от значений, полученных по классическому алгоритму или с полной точностью.

В этом примере будет код, более приближенный к реальности.

void OnStart()
{
    // параметры
    int bars_count = 500;
    int periods_start = 1;
    int periods_count = 10000;
    int periods_step = 1;
    int periods_end = periods_start + (periods_count - 1) * periods_step;
    
    int periods_max = periods_end;
    int data_count = bars_count + periods_max - 1;
    int first_bar = periods_max - 1;
    
    int periods[];
    ArrayResize(periods, periods_count);
    for (int i = 0; i < periods_count; i++)
        periods[i] = periods_start + i * periods_step;
    
    // получить данные
    double data[];
    
    if (CopyClose(_Symbol, _Period, 0, data_count, data) != data_count)
    {
        Print("Недостаточно истории");
        return;
    }

    float data_f[];
    ArrayCopy(data_f, data);
    
    int res_size = bars_count * periods_count;
    double center[], upper[], lower[];
    ArrayResize(center, res_size);
    ArrayResize(upper, res_size);
    ArrayResize(lower, res_size);

    float center_f[], upper_f[], lower_f[];
    ArrayResize(center_f, res_size);
    ArrayResize(upper_f, res_size);
    ArrayResize(lower_f, res_size);

    for (int i = 0; i < 10; i++)
    {
INTERVAL_START(0);
        MQLMATH::BBArrsCUL(data, first_bar, bars_count, periods, periods_count, 2.0, center, upper, lower);
INTERVAL_STOP(0);

INTERVAL_START(1);
        MQLMATH::BBArrsCULF(data_f, first_bar, bars_count, periods, periods_count, 2.0, center_f, upper_f, lower_f);
INTERVAL_STOP(1);
    }

INTERVAL_PRINTALL;
}

Здесь я случайно наткнулся на особенность (скорее баг) текущего билда MT (2280), который приводит к резкому замедлению работы, например вот так:

time=1962.794 ms,  count=10,  avg=196.279400 ms  [OnStart, 49]
time=1956.743 ms,  count=10,  avg=195.674300 ms  [OnStart, 49]
time=2927.533 ms,  count=10,  avg=292.753300 ms  [OnStart, 49] <---- bug
time=7487.895 ms,  count=10,  avg=748.789500 ms  [OnStart, 49] <---- bug
time=1959.859 ms,  count=10,  avg=195.985900 ms  [OnStart, 49]

Первые три запуска идут нормально, четвертый почти в четыре раза медленнее. И так снова и снова, увеличивая среднее время работы в два раза. Раньше я такого, вроде бы, не видел, наверняка это баг последних сборок. Если увеличить число прогонов с 10 до 20, то проблемным будет каждый второй запуск, причём среднее время будет также в 4 раза больше, увеличивая общее среднее время ещё больше. Проблема здесь точно в MQL, ровно тот же код, скомпилированный как C++ и вызванный из DLL, такой проблемы не вызывает. Ещё один повод не считать ничего на MQL, меня лично убеждать давно уже не нужно.

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

Без оптимизации, double:
bb (NZDUSD,H1)  Interval #0:  time=7542.211 ms,  count=10,  avg=754.221100 ms  [OnStart, 57]
bb (NZDUSD,H1)  Interval #0:  time=7501.232 ms,  count=10,  avg=750.123200 ms  [OnStart, 57]
bb (NZDUSD,H1)  Interval #0:  time=7508.570 ms,  count=10,  avg=750.857000 ms  [OnStart, 57]

Без оптимизации, float:
bb (NZDUSD,H1)  Interval #1:  time=7675.927 ms,  count=10,  avg=767.592700 ms  [OnStart, 61]
bb (NZDUSD,H1)  Interval #1:  time=7672.022 ms,  count=10,  avg=767.202200 ms  [OnStart, 61]
bb (NZDUSD,H1)  Interval #1:  time=7676.213 ms,  count=10,  avg=767.621300 ms  [OnStart, 61]

С оптимизацией, double:
bb (NZDUSD,H1)  Interval #0:  time=2941.484 ms,  count=10,  avg=294.148400 ms  [OnStart, 55]
bb (NZDUSD,H1)  Interval #0:  time=2927.187 ms,  count=10,  avg=292.718700 ms  [OnStart, 55]
bb (NZDUSD,H1)  Interval #0:  time=7476.405 ms,  count=10,  avg=747.640500 ms  [OnStart, 55] <---- bug
bb (NZDUSD,H1)  Interval #0:  time=7476.663 ms,  count=10,  avg=747.666300 ms  [OnStart, 55] <---- bug
bb (NZDUSD,H1)  Interval #0:  time=2927.846 ms,  count=10,  avg=292.784600 ms  [OnStart, 55]

С оптимизацией, float:
bb (NZDUSD,H1)  Interval #1:  time=2104.677 ms,  count=10,  avg=210.467700 ms  [OnStart, 59]
bb (NZDUSD,H1)  Interval #1:  time=2077.550 ms,  count=10,  avg=207.755000 ms  [OnStart, 59]
bb (NZDUSD,H1)  Interval #1:  time=2076.843 ms,  count=10,  avg=207.684300 ms  [OnStart, 59]
bb (NZDUSD,H1)  Interval #1:  time=2073.930 ms,  count=10,  avg=207.393000 ms  [OnStart, 59]
bb (NZDUSD,H1)  Interval #1:  time=2080.614 ms,  count=10,  avg=208.061400 ms  [OnStart, 59]

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

Здесь разница поменьше, но почти 30% тоже неплохо, особенно учитывая то, что собственно вычисления в обоих случаях идут с double, а если учесть баг, который почему-то не проявился на float, то всё, возможно, ещё лучше. Здесь не представлено время копирования исходных данных из double в float, но оно настолько мало (~0.030 ms), что на результат не влияет.

Бонусом покажу лог ровно того же кода вычисления BB, который скомпилирован как C++ и вызван из DLL:

C++ DLL, double:
bb (NZDUSD,H1)  Interval #0:  time=1728.659 ms,  count=10,  avg=172.865900 ms  [OnStart, 57]
bb (NZDUSD,H1)  Interval #0:  time=1722.218 ms,  count=10,  avg=172.221800 ms  [OnStart, 57]
bb (NZDUSD,H1)  Interval #0:  time=1719.188 ms,  count=10,  avg=171.918800 ms  [OnStart, 57]
bb (NZDUSD,H1)  Interval #0:  time=1724.195 ms,  count=10,  avg=172.419500 ms  [OnStart, 57]

C++ DLL, float:
bb (NZDUSD,H1)  Interval #1:  time=1867.243 ms,  count=10,  avg=186.724300 ms  [OnStart, 61]
bb (NZDUSD,H1)  Interval #1:  time=1868.819 ms,  count=10,  avg=186.881900 ms  [OnStart, 61]
bb (NZDUSD,H1)  Interval #1:  time=1864.915 ms,  count=10,  avg=186.491500 ms  [OnStart, 61]
bb (NZDUSD,H1)  Interval #1:  time=1867.252 ms,  count=10,  avg=186.725200 ms  [OnStart, 61]

Всё ещё быстре, всё стабильнее, никаких провалов скорости. Интересно то, что float здесь работает чуть медленнее double. Возможно, работа с double в C++ лучше оптимизирована (вернее, в используемом мной компиляторе). В Intel DAAL смена типа на float давала почти двукратное ускорение. Есть повод покопаться в настройках компилятора или даже сменить его.

Третий пример. Массивы и расчёты

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

Вызывающий код останется прежним, но поменяем функцию calc_pi_wallis.

template<typename T>
T calc_pi_wallis(int max_iter)
{
    T pi = (T)2.0;
    T one = (T)1.0;
    T two = (T)2.0;

    T arr[];
    ArrayResize(arr, max_iter + 1);

    for (int i = 1; i <= max_iter; i++)
    {
        T n = (T)i;
        arr[i] = (two * n) * (two * n) / (two * n - one) / (two * n + one);
    }

    for (int i = 1; i <= max_iter; i++)
    {
        pi *= arr[i];
    }

    return(pi);
}

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

Без оптимизации, double:
Interval #0:  time=3032.762 ms,  count=9,  avg=336.973556 ms  [OnStart, 10]

Без оптимизации, float:
Interval #1:  time=2269.330 ms,  count=9,  avg=252.147778 ms  [OnStart, 14]


С оптимизацией, double:
Interval #0:  time=2366.834 ms,  count=9,  avg=262.981556 ms  [OnStart, 10]

С оптимизацией, float:
Interval #1:  time=1398.744 ms,  count=9,  avg=155.416000 ms  [OnStart, 14]

Как и в первый раз, оптимизация сработала лучше для float, однако общее ускорение за счёт использования float стало лишь на 1-2 процента лучше, болтаясь около тех же 40%. Т.к. тест синтетический, это вполне можно считать пределом, по крайней мере для MQL5 и 64-битного MT5.

Посмотрим, что произойдёт в 32-битной четвёрке на этом же примере.

double:
Interval #0:  time=11372.155 ms,  count=9,  avg=1263.572778 ms  [OnStart, 10]

float:
Interval #1:  time=5092.790 ms,  count=9,  avg=565.865556 ms  [OnStart, 14]

Здесь, как обычно, заброшенный разработчиками MQL4 не идёт ни в какое сравнение с MQL5. Но вот ускорение здесь заметно больше - уже 55%.

Выводы

Замена типа исходных данных, результата или самого расчёта с double на float может иметь смысл в MQL, но я бы ограничился только случаями, когда время расчёта начинает слегка выходить за рамки комфортного. Например, для индикатора может потребоваться уложиться в пол секунды, и если при типовых сценариях никак не удаётся загнать расчёты в эти рамки, и достаточно лишь 30%-40%, то такой переход может быть оправдан. Либо когда расчёты длятся часами, днями или даже неделями, такая оптимизация скорости тоже имеет смысл. В MT4 такой переход чуть более оправдлан (55% ускорения в 4 против 40% в 5),однако переход с 4 на 5 или на расчёты в DLL даст гораздо больший прирост.

Можно попробовать расчёты на C++ в DLL, т.к. ровно тот же код для double может быть исполнен на те же ~40% быстрее. Кроме того, на C++ доступно гораздо больше готовых библиотек, и вообще разработка намного приятнее за счёт более удобных инструментов.

Эта оптимизация из тех, которые делаются тогда, когда другие либо не помогают, либо недоступны. Оптимизация может быть слишком сложна (например, требуется изучить новый язык, библиотеку, окружение), использовать дорогое оборудование или платные облачные вычисления. У меня часто бывает, что можно ускорить старый код раз в 10-100 без применения подобных трюков, но иногда приходится использовать вообще всё, что приходит в голову, например такую вот смену типа данных. Если заранее знать, что вычисления будут тяжёлыми, то можно сразу писать для float или шаблонами под оба варианта.

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

Комментариев нет:

Отправить комментарий