Как получить оптимизацию от «чистой функции» в C #?

Question

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

public static int AddOne(int x) { return x + 1; }

Насколько я понимаю, если среда выполнения понимает функциональную чистоту, она может оптимизировать выполнение, так что возвращаемые значения не нужно пересчитывать.

Есть ли способ добиться такого рода оптимизации времени выполнения в C #? И я предполагаю, что есть название для этого вида оптимизации. Как это называется?

Редактировать: Очевидно, что мой пример функции не принесет много пользы от такого рода оптимизации. Был приведен пример, чтобы выразить тот тип чистоты, который я имел в виду, а не реальный пример.

Answer 1

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

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

Эта область будет становиться все более важной, так как массовые многоядерные машины становятся менее дорогими и более распространенными. Мы ставим перед собой цель долгосрочного исследования языка C #, чтобы выяснить, как воспользоваться преимуществами чистых функций (и нечистых, но «изолированных» функций) в языке, компиляторе и среде выполнения. Но это связано со многими трудными проблемами, проблемами, относительно которых в промышленности или научных кругах не существует единого мнения относительно наилучшего подхода. Высшие умы думают об этом, но не ожидают каких-либо серьезных результатов в ближайшее время.

Answer 2

если расчет был дорогостоящим, вы могли бы кешировать результат в словаре?

    static Dictionary<int, int> cache = new Dictionary<int, int>();
    public static int AddOne(int x)
    {
        int result;
        if(!cache.TryGetValue(x, out result))
        {
            result = x + 1;
            cache[x] = result;
        }
        return result;
    }

Конечно, поиск в словаре в этом случае обходится дороже, чем add:)

Есть еще один гораздо более крутой способ сделать функциональное запоминание, объясненный Уэсом Дайером здесь: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx - если вы сделаете много этого кэширования, то его функция Memoize может сэкономить вам много кода ...

Answer 3

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

Answer 4

Я думаю, что вы ищете функциональная памятка

Answer 5

Это, вероятно, будет встроено (иначе встроенное расширение ) компилятором ...

Просто убедитесь, что вы компилируете свой код с установленным флагом «Оптимизировать код» (в VS: свойства проекта / вкладка сборки / Оптимизировать код)

---

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

Существует также влияние на память, но этим можно управлять с помощью умного использования слабых ссылок .

---

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

В вашем примере среда выполнения будет вынуждена вычислять результат, если x не известен во время компиляции. В этом случае ваш код будет дополнительно оптимизирован за счет использования постоянного свертывания

Answer 6

Другой вариант - использовать плагин fody https://github.com/Dresel/MethodCache Вы можете украсить методы, которые должны быть кэшированы. При использовании этого вы, конечно, должны принимать во внимание все комментарии, упомянутые в других ответах.

Answer 7

Как мог компилятор сделать это? Как он узнает, какие значения x будут переданы во время выполнения?

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

Answer 8

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

AddOne(5);

AddOne может быть встроен:

5 + 1;

Постоянное распространение может затем упростить выражение:

6;

( Устранение мертвого кода может затем еще больше упростить это выражение, но это только пример).

Знание того, что AddOne() не имеет побочных эффектов, может также позволить компилятору выполнить устранение общего подвыражения , так что:

AddOne(3) + AddOne(3)

может быть преобразовано в:

int x = AddOne(3);
x + x;

или снижение прочности , даже:

2*AddOne(3);

Нет способа дать команду компилятору JIT c # выполнить эти оптимизации; оптимизирует по своему усмотрению. Но это довольно умно, и вы должны чувствовать себя комфортно, полагаясь на него, чтобы выполнять такого рода преобразования без вашего вмешательства.