Производительность функции .NET вызов (C# F#) VS C++

Так как F# 2.0 стал частью VS2010, я интересуюсь F#. Я задался вопросом какой смысл того, чтобы использовать его. Я читал немного, и я сделал сравнительный тест для измерения вызова функций. Я использовал функцию Ackermann :)

C#

sealed class Program
{
    public static int ackermann(int m, int n)
    {
        if (m == 0)
            return n + 1;
        if (m > 0 && n == 0)
        {
            return ackermann(m - 1, 1);
        }
        if (m > 0 && n > 0)
        {
            return ackermann(m - 1, ackermann(m, n - 1));
        }
        return 0;
    }

    static void Main(string[] args)
    {

        Stopwatch stopWatch = new Stopwatch();

        stopWatch.Start();
        Console.WriteLine("C# ackermann(3,10) = " + Program.ackermann(3, 10));
        stopWatch.Stop();

        Console.WriteLine("Time required for execution: " + stopWatch.ElapsedMilliseconds + "ms");
        Console.ReadLine();
    }
}

C++

class Program{
public:
static inline int ackermann(int m, int n)
{
  if(m == 0)
       return n + 1;
  if (m > 0 && n == 0)
  {
      return ackermann(m - 1, 1);
  }
  if (m > 0 && n > 0)
  {
      return ackermann(m - 1, ackermann(m, n - 1));
  }
  return 0;
 }
};

int _tmain(int argc, _TCHAR* argv[])
{
 clock_t start, end;

  start = clock();
 std::cout << "CPP: ackermann(3,10) = " << Program::ackermann(3, 10) << std::endl;
 end = clock();
 std::cout << "Time required for execution: " << (end-start) << " ms." << "\n\n";
 int i;
 std::cin >> i;
 return 0;
}

F#

// Ackermann
let rec ackermann m n  =
  if m = 0 then n + 1
  elif m > 0 && n = 0 then ackermann (m - 1) 1
  elif m > 0 && n > 0 then ackermann (m - 1)  (ackermann m (n - 1))
  else 0

open System.Diagnostics;
let stopWatch = Stopwatch.StartNew()
let x = ackermann 3 10 
stopWatch.Stop();

printfn "F# ackermann(3,10) = %d"  x
printfn "Time required for execution: %f"  stopWatch.Elapsed.TotalMilliseconds

Java

public class Main 
{
 public static int ackermann(int m, int n)
 {
 if (m==0) 
   return n + 1;
if (m>0 && n==0)
{
 return ackermann(m - 1,1);
}
if (m>0 && n>0)
{
  return ackermann(m - 1,ackermann(m,n - 1));
 }
 return 0;
}

  public static void main(String[] args)
  { 
   System.out.println(Main.ackermann(3,10));
  }
}

Затем
C# = 510 мс
C++ = 130 мс
F# = 185 мс
Java = Stackoverflow :)

Действительно ли это - питание F# (кроме небольшого объема кода), Если мы хотим использовать .NET и получить немного более быстрое выполнение? Я могу оптимизировать какой-либо из этих кодов (особенно F#)?

ОБНОВЛЕНИЕ. Я избавился от Консоли. WriteLine и выполненный C# кодируют без отладчика: C# = 400 мс

9
задан Lukasz Madon 16 March 2011 в 20:54
поделиться

4 ответа

Я считаю, что в данном случае разница между C # и F # заключается в оптимизации хвостового вызова.

Хвостовой вызов - это когда у вас есть рекурсивный вызов, который выполняется "последним" в функции. В этом случае F # фактически не генерирует инструкцию вызова, а вместо этого компилирует код в цикл (поскольку вызов является «последним делом», мы можем повторно использовать текущий кадр стека и просто перейти к началу метода) .

В вашей реализации ackermann два вызова являются хвостовыми вызовами, и только один из них нет (тот, где результат передается в качестве аргумента другому ackermann вызов). Это означает, что версия F # на самом деле вызывает инструкцию «вызова» (намного?) Реже.

В целом профиль производительности примерно такой же, как профиль производительности C #. Здесь довольно много сообщений, связанных с производительностью F # и C #:

14
ответ дан 4 December 2019 в 08:32
поделиться

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

Вы можете сделать этот тип рекурсивной функции быстрее с помощью мемоизации (кэширования). Вы также можете сделать это в C# (пример.) Я получил 18 мс.

open System.Collections.Generic

let memoize2 f =
    let cache = Dictionary<_, _>()
    fun x y ->
        if cache.ContainsKey (x, y) then 
            cache.[(x, y)]
        else 
            let res = f x y
            cache.[(x, y)] <- res
            res

// Ackermann
let rec ackermann =
    memoize2 (fun m n ->
        if m = 0 then n + 1
        elif m > 0 && n = 0 then ackermann (m - 1) 1
        elif m > 0 && n > 0 then ackermann (m - 1)  (ackermann m (n - 1))
        else 0
    )
6
ответ дан 4 December 2019 в 08:32
поделиться

Для F # вы можете попробовать встроенное ключевое слово.

Кроме того, как упоминалось на предыдущем плакате, версии C # и F # различаются из-за операторов Console.WriteLine.

1
ответ дан 4 December 2019 в 08:32
поделиться

Не имеет прямого отношения к вопросу, но достаточно интересен, чтобы упомянуть: попробуйте эту версию

let rec ackermann2 m n  =
  match m,n with
  | 0,0 -> 0
  | 0,n -> n+1
  | m,0 -> ackermann2 (m-1) 1
  | m,n -> ackermann2 (m-1) (ackermann2 m (n-1))

На моем ПК (VS2010, F# interactive) она почти на 50% быстрее, чем ваша версия при вычислении Аккермана 3 12.

Я не могу точно объяснить, почему такая разница в производительности. Думаю, это связано с тем, что компилятор F# переводит выражение match в оператор switch вместо серии операторов if. Возможно, также помогло размещение теста (m=0,n=0) первым.

4
ответ дан 4 December 2019 в 08:32
поделиться
Другие вопросы по тегам:

Похожие вопросы: