Почему C медленно работает с вызовами функций?

Question

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

Мне было интересно, если кто-нибудь может объяснить, почему C так медленно работает с вызовом функции?

Легко дать поверхностный ответ на стандартный вопрос о Рекурсивной Фибоначчи, но я был бы признателен, если бы знал "более глубокую" причину настолько глубоко, насколько это возможно.1008 * Edit1: извините за эту ошибку.Я неправильно понял статью в вики.

Answer 1

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

Это медленно, если ваш код редок и ваши функции очень малы. Это случай функции Фибоначчи. Однако вы должны различать «медленные вызовы» и «медленный алгоритм»: вычисление набора Фибоначчи с рекурсивной реализацией является в значительной степени самым медленным и простым способом сделать это. В теле функции задействовано почти столько же кода, сколько в прологе и эпилоге функции (где происходит нажатие и выталкивание).

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

Итак, нет, C-вызовы не медленные.

Answer 2

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

"В языках (таких как C и Java), которые предпочитают конструкции итеративных циклов,обычно с рекурсивными программами связаны значительные затраты времени и пространства из-за накладных расходов, необходимых для управления стеком, и относительной медленности вызовов функций; "

В контексте рекурсивной реализации вычислений Фибоначчи.

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

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

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

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

Answer 3

C не медленный с вызовами функций. Затраты на вызов функции C чрезвычайно низки.

Я призываю вас предоставить доказательства в поддержку вашего утверждения.

Answer 4

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

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

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

Следует отметить, однако, что оптимизация здесь на самом деле не ускоряет вызовы функций - она избегая (часто многих) вызовов функций.

Answer 5

Причина Recursive Fibonacci, а не язык Си.Рекурсивный Фибоначчи - это что-то вроде

int f(int i)
{
    return i < 2 ? 1 : f(i-1) + f(i-2);
}

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

Answer 6

Я не уверен, что вы подразумеваете под "поверхностным ответом на стандартный вопрос о рекурсивной Фибоначчи".

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

Answer 7

Из всех языков C, вероятно, самый быстрый (если вы не программист на ассемблере). Большинство вызовов функций Си являются стопроцентно чистыми операциями. То есть, когда вы вызываете функцию, то, что это также переводит в вашем двоичном коде, ЦПУ помещает любые параметры, которые вы передаете своей функции, в стек. После этого он вызывает функцию. Затем функция выскакивает ваши параметры. После этого он выполняет любой код, который составляет вашу функцию. Наконец, все возвращаемые параметры помещаются в стек, затем функция завершается и параметры удаляются. Стековые операции на любом процессоре обычно выполняются быстрее, чем на любом другом.

Если вы используете профилировщик или что-то, что говорит, что вызов функции, который вы делаете, медленный, тогда он ДОЛЖЕН быть кодом внутри вашей функции. Попробуйте разместить свой код здесь, и мы увидим, что происходит.

Answer 8

В статье говорится о разнице между рекурсией и итерацией .

Это под темой под названием алгоритм анализа в информатике.

Предположим, я пишу функцию Фибоначчи, и она выглядит примерно так:

//finds the nth fibonacci
int rec_fib(n) {
 if(n == 1)
    return 1;
 else if (n == 2)
    return 1;
 else 
   return fib(n-1) + fib(n - 2)
}

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

Чтобы получить работу, нужны целые лоты.

Однако есть еще один способ написать фибоначчи (есть и несколько других)

int fib(int n) //this one taken from scriptol.com, since it takes more thought to write it out.
{
  int first = 0, second = 1;

  int tmp;
  while (n--)
    {
      tmp = first+second;
      first = second;
      second = tmp;
    }
  return first;
}

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

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

Кроме того, некоторые рекурсивные алгоритмы бывают быстрыми (или их можно обмануть, чтобы они были быстрее). Это зависит от алгоритма - поэтому анализ алгоритма важен и полезен.

Имеет ли это смысл?

Answer 9

Я согласен с Марком Байерсом, так как вы упомянули рекурсивный Фибоначчи. Попробуйте добавить printf, чтобы сообщение печаталось при каждом добавлении. Вы увидите, что рекурсивный Фибоначчи делает гораздо больше дополнений, чем может показаться на первый взгляд.

Answer 10

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

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

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

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