Математическая оптимизация в C # - PullRequest
53 голосов
/ 05 января 2009

Я профилировал приложение весь день и, оптимизировав пару бит кода, я остался с этим в моем списке задач. Это функция активации для нейронной сети, которая вызывается более 100 миллионов раз. Согласно dotTrace, это составляет около 60% от общего времени работы.

Как бы вы оптимизировали это?

public static float Sigmoid(double value) {
    return (float) (1.0 / (1.0 + Math.Pow(Math.E, -value)));
}

Ответы [ 24 ]

53 голосов
/ 05 января 2009

Попробуйте:

public static float Sigmoid(double value) {
    return 1.0f / (1.0f + (float) Math.Exp(-value));
}

РЕДАКТИРОВАТЬ: Я сделал быстрый тест. На моей машине приведенный выше код примерно на 43% быстрее, чем ваш метод, и этот математически эквивалентный код - самый младший (на 46% быстрее, чем оригинал):

public static float Sigmoid(double value) {
    float k = Math.Exp(value);
    return k / (1.0f + k);
}

РЕДАКТИРОВАТЬ 2: Я не уверен, сколько служебных функций C # имеет, но если вы #include <math.h> в вашем исходном коде, вы сможете использовать это, который использует функцию float-exp , Это может быть немного быстрее.

public static float Sigmoid(double value) {
    float k = expf((float) value);
    return k / (1.0f + k);
}

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

30 голосов
/ 05 января 2009

Если это для функции активации, то имеет ли ужасное значение, если вычисление e ^ x является полностью точным?

Например, если вы используете аппроксимацию (1 + x / 256) ^ 256, в моем тесте Pentium на Java (я предполагаю, что C # по существу компилируется с теми же инструкциями процессора), это примерно в 7-8 раз быстрее, чем e ^ x (Math.exp ()), с точностью до 2 знаков после запятой с точностью до x от +/- 1,5 и в правильном порядке величины в указанном вами диапазоне. (Очевидно, чтобы поднять до 256, вы на самом деле возводите квадрат в квадрат 8 раз - не используйте Math.Pow для этого!) В Java:

double eapprox = (1d + x / 256d);
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;
eapprox *= eapprox;

Продолжайте удваивать или делить пополам 256 (и добавлять / удалять умножение) в зависимости от того, насколько точной должна быть аппроксимация. Даже при n = 4 он по-прежнему дает около 1,5 десятичных знаков точности для значений x в диапазоне от -0,5 до 0,5 (и, по-видимому, в 15 раз быстрее, чем Math.exp ()).

P.S. Я забыл упомянуть - очевидно, вы не должны действительно делить на 256: умножать на константу 1/256. JIT-компилятор Java выполняет эту оптимизацию автоматически (по крайней мере, Hotspot), и я предполагал, что C # должен делать то же самое.

21 голосов
/ 05 января 2009

Посмотрите на этот пост . он имеет приближение для e ^ x, написанного на Java, это должен быть код C # для него (непроверенный):

public static double Exp(double val) {  
    long tmp = (long) (1512775 * val + 1072632447);  
    return BitConverter.Int64BitsToDouble(tmp << 32);  
}

В моих тестах это более чем в 5 раз быстрее, чем Math.exp () (в Java). Аппроксимация основана на работе « Быстрая компактная аппроксимация экспоненциальной функции », которая была разработана именно для использования в нейронных сетях. По сути, это то же самое, что таблица поиска из 2048 записей и линейного приближения между записями, но все это с помощью трюков с плавающей запятой IEEE.

РЕДАКТИРОВАТЬ: Согласно Special Sauce это примерно в 3,25 раза быстрее, чем реализация CLR. Спасибо!

14 голосов
/ 05 января 2009
  1. Помните, что любые изменения в этой функции активации происходят за счет различного поведения . Это даже включает переключение на float (и, следовательно, снижение точности) или использование заменителей активации. Только эксперимент с вашим вариантом использования покажет правильный путь.
  2. В дополнение к простой оптимизации кода, я бы также рекомендовал распараллеливание вычислений (т. Е. Использовать несколько ядер вашей машины или даже машин в облаках Windows Azure) и улучшить обучение алгоритмы.

ОБНОВЛЕНИЕ: Опубликовать таблицы поиска для функций активации ANN

ОБНОВЛЕНИЕ 2: Я удалил точку на LUT, поскольку перепутал их с полным хэшированием. Спасибо Хенрику Густафссону за то, что вернули меня на трассу. Таким образом, память не является проблемой, хотя пространство поиска все еще немного перепутано с локальными экстремумами.

8 голосов
/ 05 января 2009

Если вы можете взаимодействовать с C ++, вы можете рассмотреть возможность сохранения всех значений в массиве и их циклического перебора с использованием SSE следующим образом:

void sigmoid_sse(float *a_Values, float *a_Output, size_t a_Size){
    __m128* l_Output = (__m128*)a_Output;
    __m128* l_Start  = (__m128*)a_Values;
    __m128* l_End    = (__m128*)(a_Values + a_Size);

    const __m128 l_One        = _mm_set_ps1(1.f);
    const __m128 l_Half       = _mm_set_ps1(1.f / 2.f);
    const __m128 l_OneOver6   = _mm_set_ps1(1.f / 6.f);
    const __m128 l_OneOver24  = _mm_set_ps1(1.f / 24.f);
    const __m128 l_OneOver120 = _mm_set_ps1(1.f / 120.f);
    const __m128 l_OneOver720 = _mm_set_ps1(1.f / 720.f);
    const __m128 l_MinOne     = _mm_set_ps1(-1.f);

    for(__m128 *i = l_Start; i < l_End; i++){
        // 1.0 / (1.0 + Math.Pow(Math.E, -value))
        // 1.0 / (1.0 + Math.Exp(-value))

        // value = *i so we need -value
        __m128 value = _mm_mul_ps(l_MinOne, *i);

        // exp expressed as inifite series 1 + x + (x ^ 2 / 2!) + (x ^ 3 / 3!) ...
        __m128 x = value;

        // result in l_Exp
        __m128 l_Exp = l_One; // = 1

        l_Exp = _mm_add_ps(l_Exp, x); // += x

        x = _mm_mul_ps(x, x); // = x ^ 2
        l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_Half, x)); // += (x ^ 2 * (1 / 2))

        x = _mm_mul_ps(value, x); // = x ^ 3
        l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_OneOver6, x)); // += (x ^ 3 * (1 / 6))

        x = _mm_mul_ps(value, x); // = x ^ 4
        l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_OneOver24, x)); // += (x ^ 4 * (1 / 24))

#ifdef MORE_ACCURATE

        x = _mm_mul_ps(value, x); // = x ^ 5
        l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_OneOver120, x)); // += (x ^ 5 * (1 / 120))

        x = _mm_mul_ps(value, x); // = x ^ 6
        l_Exp = _mm_add_ps(l_Exp, _mm_mul_ps(l_OneOver720, x)); // += (x ^ 6 * (1 / 720))

#endif

        // we've calculated exp of -i
        // now we only need to do the '1.0 / (1.0 + ...' part
        *l_Output++ = _mm_rcp_ps(_mm_add_ps(l_One,  l_Exp));
    }
}

Однако помните, что используемые вами массивы следует размещать с помощью _aligned_malloc (some_size * sizeof (float), 16), поскольку SSE требует памяти, выровненной по границе.

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

Кроме того, если число элементов начинает значительно расти, вы можете захотеть обработать эти вещи на GPU (просто создайте 1D-текстуру float4 и запустите очень простой фрагментный шейдер).

8 голосов
/ 05 января 2009

При 100 миллионах звонков я бы начал задаваться вопросом, не влияют ли накладные расходы профилировщика на ваши результаты. Замените вычисление на запрет и посмотрите, если все еще , как сообщается, потребляет 60% времени выполнения ...

Или, что еще лучше, создайте несколько тестовых данных и используйте таймер секундомера, чтобы профилировать около миллиона вызовов.

7 голосов
/ 06 января 2009

FWIW, вот мои тесты C # для уже опубликованных ответов. (Empty - это функция, которая просто возвращает 0, чтобы измерить издержки вызова функции)

Empty Function:       79ms   0
Original:             1576ms 0.7202294
Simplified: (soprano) 681ms  0.7202294
Approximate: (Neil)   441ms  0.7198783
Bit Manip: (martinus) 836ms  0.72318
Taylor: (Rex Logan)   261ms  0.7202305
Lookup: (Henrik)      182ms  0.7204863
public static object[] Time(Func<double, float> f) {
    var testvalue = 0.9456;
    var sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < 1e7; i++)
        f(testvalue);
    return new object[] { sw.ElapsedMilliseconds, f(testvalue) };
}
public static void Main(string[] args) {
    Console.WriteLine("Empty:       {0,10}ms {1}", Time(Empty));
    Console.WriteLine("Original:    {0,10}ms {1}", Time(Original));
    Console.WriteLine("Simplified:  {0,10}ms {1}", Time(Simplified));
    Console.WriteLine("Approximate: {0,10}ms {1}", Time(ExpApproximation));
    Console.WriteLine("Bit Manip:   {0,10}ms {1}", Time(BitBashing));
    Console.WriteLine("Taylor:      {0,10}ms {1}", Time(TaylorExpansion));
    Console.WriteLine("Lookup:      {0,10}ms {1}", Time(LUT));
}
5 голосов
/ 05 января 2009

Примечание: Это продолжение этой записи.

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

Теперь посмотри, что ты заставил меня сделать! Вы заставили меня установить Mono!

$ gmcs -optimize test.cs && mono test.exe
Max deviation is 0.001663983
10^7 iterations using Sigmoid1() took 1646.613 ms
10^7 iterations using Sigmoid2() took 237.352 ms

C вряд ли стоит больше усилий, мир движется вперед:)

Итак, чуть более чем в 10 раз * 10 * 10 6 быстрее. Кто-то, у кого есть окно с Windows, может исследовать использование памяти и производительность с помощью MS-вещи:)

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

Некоторые ошибки с этим:

  • Ошибка возрастает, когда вы выходите за пределы таблицы (но сходится к 0 в крайних случаях); для х прибл + -7,0. Это связано с выбранным коэффициентом масштабирования. Большие значения SCALE дают большие ошибки в среднем диапазоне, но меньше по краям.
  • Как правило, это очень глупый тест, и я не знаю C #, это просто простое преобразование моего C-кода:)
  • Ринат Абдуллин очень правильно сказал, что сглаживание и потеря точности могут вызвать проблемы, но так как я не видел переменных для этого, я могу только посоветовать вам попробовать это. На самом деле, я согласен со всем, что он говорит, за исключением вопроса о таблицах поиска.

Прошу прощения за код-вставку-кодировку ...

using System;
using System.Diagnostics;

class LUTTest {
    private const float SCALE = 320.0f;
    private const int RESOLUTION = 2047;
    private const float MIN = -RESOLUTION / SCALE;
    private const float MAX = RESOLUTION / SCALE;

    private static readonly float[] lut = InitLUT();

    private static float[] InitLUT() {
      var lut = new float[RESOLUTION + 1];

      for (int i = 0; i < RESOLUTION + 1; i++) {
        lut[i] = (float)(1.0 / (1.0 + Math.Exp(-i / SCALE)));
      }
      return lut;
    }

    public static float Sigmoid1(double value) {
        return (float) (1.0 / (1.0 + Math.Exp(-value)));
    }

    public static float Sigmoid2(float value) {
      if (value <= MIN) return 0.0f;
      if (value >= MAX) return 1.0f;
      if (value >= 0) return lut[(int)(value * SCALE + 0.5f)];
      return 1.0f - lut[(int)(-value * SCALE + 0.5f)];
    }

    public static float error(float v0, float v1) {
      return Math.Abs(v1 - v0);
    }

    public static float TestError() {
        float emax = 0.0f;
        for (float x = -10.0f; x < 10.0f; x+= 0.00001f) {
          float v0 = Sigmoid1(x);
          float v1 = Sigmoid2(x);
          float e = error(v0, v1);
          if (e > emax) emax = e;
        }
        return emax;
    }

    public static double TestPerformancePlain() {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < 10; i++) {
            for (float x = -5.0f; x < 5.0f; x+= 0.00001f) {
                Sigmoid1(x);
            }
        }
        sw.Stop();
        return sw.Elapsed.TotalMilliseconds;
    }    

    public static double TestPerformanceLUT() {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        for (int i = 0; i < 10; i++) {
            for (float x = -5.0f; x < 5.0f; x+= 0.00001f) {
                Sigmoid2(x);
            }
        }
        sw.Stop();
        return sw.Elapsed.TotalMilliseconds;
    }    

    static void Main() {
        Console.WriteLine("Max deviation is {0}", TestError());
        Console.WriteLine("10^7 iterations using Sigmoid1() took {0} ms", TestPerformancePlain());
        Console.WriteLine("10^7 iterations using Sigmoid2() took {0} ms", TestPerformanceLUT());
    }
}
5 голосов
/ 06 января 2009

F # имеет лучшую производительность, чем C # в математических алгоритмах .NET. Таким образом, переписывание нейронной сети на F # может улучшить общую производительность.

Если мы повторно реализуем фрагмент кода LUT для бенчмаркинга (я использовал слегка подправленную версию) в F #, то результирующий код:

  • выполняет тест sigmoid1 в 588,8 мс вместо 3899,2 мс
  • выполняет тест Sigmoid2 (LUT) в 156,6 мс вместо 411,4 мс

Более подробную информацию можно найти в блоге . Вот фрагмент кода F #:

#light

let Scale = 320.0f;
let Resolution = 2047;

let Min = -single(Resolution)/Scale;
let Max = single(Resolution)/Scale;

let range step a b =
  let count = int((b-a)/step);
  seq { for i in 0 .. count -> single(i)*step + a };

let lut = [| 
  for x in 0 .. Resolution ->
    single(1.0/(1.0 +  exp(-double(x)/double(Scale))))
  |]

let sigmoid1 value = 1.0f/(1.0f + exp(-value));

let sigmoid2 v = 
  if (v <= Min) then 0.0f;
  elif (v>= Max) then 1.0f;
  else
    let f = v * Scale;
    if (v>0.0f) then lut.[int (f + 0.5f)]
    else 1.0f - lut.[int(0.5f - f)];

let getError f = 
  let test = range 0.00001f -10.0f 10.0f;
  let errors = seq { 
    for v in test -> 
      abs(sigmoid1(single(v)) - f(single(v)))
  }
  Seq.max errors;

open System.Diagnostics;

let test f = 
  let sw = Stopwatch.StartNew(); 
  let mutable m = 0.0f;
  let result = 
    for t in 1 .. 10 do
      for x in 1 .. 1000000 do
        m <- f(single(x)/100000.0f-5.0f);
  sw.Elapsed.TotalMilliseconds;

printf "Max deviation is %f\n" (getError sigmoid2)
printf "10^7 iterations using sigmoid1: %f ms\n" (test sigmoid1)
printf "10^7 iterations using sigmoid2: %f ms\n" (test sigmoid2)

let c = System.Console.ReadKey(true);

И вывод (компиляция релиза по FTP 1.9.6.2 FTP без отладчика):

Max deviation is 0.001664
10^7 iterations using sigmoid1: 588.843700 ms
10^7 iterations using sigmoid2: 156.626700 ms

ОБНОВЛЕНИЕ: обновлен сравнительный анализ для использования 10 ^ 7 итераций, чтобы результаты были сопоставимы с C

UPDATE2: вот результаты производительности реализации C на той же машине для сравнения:

Max deviation is 0.001664
10^7 iterations using sigmoid1: 628 ms
10^7 iterations using sigmoid2: 157 ms
5 голосов
/ 05 января 2009

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

Кроме того, еще один момент: для быстрой подготовки больших сетей используемый вами логистический сигмоид довольно ужасен. См. Раздел 4.4 из Efficient Backprop от LeCun и др. и используйте что-то с центром в нуле (на самом деле, прочитайте всю статью, это очень полезно).

...