Производительность вызова функции .Net (C # F #) VS C ++ - PullRequest
Новая
       0

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

9 голосов
/ 14 июля 2010

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

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 мсс ++ = 130 мсF # = 185 мсJava = Stackoverflow :)

Это сила F # (кроме небольшого количества кода) Если мы хотим использовать .Net и получить немного более быстрое выполнение?Могу ли я оптимизировать любой из этих кодов (особенно F #)?

ОБНОВЛЕНИЕ .Я избавился от Console.WriteLine и запустил код C # без отладчика: C # = 400ms

Ответы [ 4 ]

14 голосов
/ 14 июля 2010

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

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

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

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

6 голосов
/ 14 июля 2010

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

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

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
    )
4 голосов
/ 14 июля 2010

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

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 # интерактивный) он почти на 50% быстрее, чем ваша версия при расчете ackermann 3 12.

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

1 голос
/ 14 июля 2010

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

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

...